kaiyun官方注册
您所在的位置:首页 > 通信与网络 > 设计应用 > 网络化软件中的异常行为传播研究
网络化软件中的异常行为传播研究
2016年微型机与应用第05期
马迎辉,彭成,张文佳,满君丰
(湖南工业大学 计算机与通信学院,湖南 株洲 412000)
摘要: 随着网络化软件应用领域的逐步扩大,软件业对软件的安全性、可靠性提出了更高的要求。软件一旦出现故障,会给人们的生活、工作带来不便,甚至造成严重的危害。因此,研究故障在网络化软件中引起的异常行为迫在眉睫。依据复杂网络上的SIR模型,对网络化软件中异常行为的传播过程进行了理论分析和数值模拟,表明了复杂网络特性对异常行为传播的重要影响。
Abstract:
Key words :

  马迎辉,彭成,张文佳,满君丰

  (湖南工业大学 计算机与通信学院,湖南 株洲 412000)

  摘要:随着网络化软件应用领域的逐步扩大,软件业对软件的安全性、可靠性提出了更高的要求。软件一旦出现故障,会给人们的生活、工作带来不便,甚至造成严重的危害。因此,研究故障在网络化软件中引起的异常行为迫在眉睫。依据复杂网络上的SIR模型,对网络化软件中异常行为的传播过程进行了理论分析和数值模拟,表明了复杂网络特性对异常行为传播的重要影响。

  关键词:网络化软件;复杂网络;软件故障;异常行为

0引言

  软件复杂性的增加直接导致软件故障的增加。软件发生故障或者异常是由于一些内外部的因素,致使软件中类、方法、函数等出现错误,不能够完成软件应有的功能。如果一个或者多个个体发生故障,那么这个故障就会随着调用和依附关系传播到其他的个体甚至导致整个系统无法正常运行,最终导致整个系统的崩溃。这种使系统失效的行为被称为异常行为。目前,各种因素都在引领着软件技术的重大改革,软件的形态也明显呈现出网络化趋势,随着复杂网络技术、服务技术的迅速发展,网络化软件[1]已然成为了现代软件系统的主要形态。总的来说,网络化软件就是以因特网为载体、以互联网上的各种资源信息为元素、以各个元素之间的相互协同和互操作为构造手段、行为与拓扑结构能够动态演变的密集型混合软件系统[2]。另外,网络化软件系统不但组成元素间的交互、代码数量比较庞大,而且数据访问、存取规模和硬件设备也大大超过了传统的软件。规模和数量在各维度上大规模增加,这不仅使得对软件系统的理解和改造难度增加,而且也使得软件故障对系统的破坏能力更加严重[3],因此,研究网络化软件系统中异常行为的传播迫在眉睫,以期在软件系统崩溃前能够得到有效的控制,从而维持系统安全有效地运行。

  目前,研究网络动力学主要是依据病毒传播的行为,近来也取得了很大的发展。另外,研究病毒传播最广泛的模型是SIS模型[45]与SIR模型[6],而无标度网络[78]则是使用最多的网络模型。在复杂网络[9]里,每个单位节点代表一个单独的个体,任意选取其中的一个节点作为感染源,节点与节点之间的连线代表病毒的传播路径。在小世界网络[1011]中广泛使用的是SIS模型,并且,其和SIR模型主要关注的是感染几率阈值的问题。

  鉴于此,本文依据复杂网络中对病毒传播行为的研究,利用SIR模型,对网络化软件系统中的异常行为传播过程进行理论分析和数值模拟,并对影响病毒传播的因素的感染几率、度分布、集聚系数等参数进行分析比较,得出这些参数对网络化软件系统中异常行为传播的影响具有相同的效果。研究异常行为的传播可以为异常行为的控制提供有意义的指导。对异常行为的研究是十分有价值的。

1相关工作

  软件异常作为影响软件正常运行的重要因素,它的一些相关研究引起了研究人员的广泛关注。由于人为的原因,故障在很多人工复杂系统中都有出现。很多领域都有对故障的研究,例如通信网络故障、电路故障、电力系统故障等,提出了许多研究成果和技术。

  现阶段一些相关人员主要基于软件的静态拓扑图,从各个层次对软件故障进行研究。王建等[12]利用软件中函数间的交互关系,通过模型的建立去模拟软件的故障传播,进而研究软件中存在的级联故障。最后,通过对现实中软件进行模拟实验,分析了影响级联故障传播的因素,并研讨了形成这些影响的原因。周宽久等[13]人通过对软件执行路径的提取,建立软件的加权网络,利用耦合映像格子(Coupled MapLattice,CML)模型[14],研究大型软件系统故障的传播过程,并且在此基础上提出了一种依据关键路径进行软件测试的方法。Damien Challet,Andrea Lombardoni等[15]人在Linux系统环境下,基于各个软件包间的相互依存关系,对单一故障进行讨论分析。Mohamed A与Zulkernine M等人也是在组件级别对软件故障传播及其对软件可靠性的影响进行了讨论分析,同时也提出了一种基于架构服务路径(Architectural Service Routes,ASR)的软件故障传播技术,并且分析确认了故障在构建中传播的下限与上限,最后得出架构与系统可靠性间的联系。

2网络化软件异常传播理论分析

  可以把网络化软件系统作为一个复杂的网络,假设这个复杂的网中有n个节点,首先选择其中一个作为感染个体(I),若异常则沿着节点间的连线进行传播,假定感染个体(I)只能将异常传播到其邻居节点。设邻居节点被传播感染的概率为φ,感染个体(I)转化为免疫个体(R)的概率为τ。假定τ=1,意思就是说感染个体只能维持一个时间步长。

  这里用I(t)表示网络里被感染个体的总数。一段时间后,感染节点(I)离感染源越来越远,被感染的节点数目逐渐增多。在有限的时间里,I(t)逐渐减少,当I(t)最终等于零时,则异常传播过程结束。由此可知,φ越大,传播的时间越长,被感染个体也越多;当φ=1时,网络中的所有节点都会被感染。

  依据扩散定义,可以得出异常传播的公式:

  1.png

  其中,Li(t)表示每个感染节点到感染源的最短距离。

  正如前面所说,网络中的三角结构与环形结构会对异常行为传播造成影响。下面用图1所示同心圆来证明。

001.jpg

  图1中,圆心表示异常源点,最内层上的节点与圆心的间距Li(t)=1,第二层上的节点与圆心的距离Li(t)=2,依次类推。当不同层之间有连接时,某层上的异常个体就可能传播到同层或者是比其更低的一层,第二层上的异常点就有可能传播到同层、第一层或者第三层上的个体,不过前两种情况会使得〈L2(t)〉=tη中的η小于2。所以,网络化软件的复杂网络结构就决定了异常传播指数η的大小。

  一般而言,描述网络结构比较重要的两个参数是集聚系数C和度分布P(k)。前者表示某个节点的两个邻居节点仍为邻居的可能性,后者表示网络中度相同的所有节点的密度。集聚系数越大表明网络中的三角结构越多。下面就研究这两个参数对异常传播指数η的影响。

  在某一时刻t,感染个体具有不同的Li(t)。假设Li(t)以δ1(t)的概率取t值,Li(t)以δ2(t)的概率取t-1,…,Li(t)以δt(t)的概率取1。那么〈L2(t)〉可表示为:

  23.jpg

  假定式(3)可写为:

  〈L2(t)〉~tX(4)

  在异常传播过程中,δi(t)是由节点感染概率φ、集聚系数C与度分布P(k)共同决定的。这里只讨论网络结构对传播指数的影响,因此假设φ为定值。集聚系数C的值越大,表明网络中的三角结构越多,异常传播的几率就很小。因此,η的值随C增大而减小。而对于度分布P(k),假如网络为BA无标度网络,那么对于度大的节点而言,则很容易被感染,并会将此异常传播给其他更多节点。假如网络为小世界网络,那么异常的传播是循序渐进的,被感染的节点相对来说比较少。如果把异常行为传播的过程分为两个部分,一个是直接向前传播,另一个是三角形路线传播。沿三角形传播又可分为向前和向后两种,并且概率相同。综上所述,在网络化软件中异常行为传播指数η是大于1的。

3实验分析

  下面通过数值模拟来验证上述结论,本文中选用WS小世界网络模型和HK模型。两个模型中,都可以调节一定的参数来改变集聚系数C的大小。另外,对于固定不变的集聚系数C,WS模型与HK模型的度分布P(k)不同。所以,用这两个模型来研究度分布P(k)和集聚系数C对传播指数的影响。

  对于WS小世界模型,其最初是一个具有N个节点的一维链,其中的各个节点与附近的X个节点相连,接着以概率ω断开并重新相连,但是新连接的节点从网络中的其他节点中随机选择,避免自连接与重复连接。然后,在小世界网中随机选取一个节点作为异常源点,让此异常源点以φ的感染概率进行传播。最终,得出〈L2(t)〉与t的关系随ω与X的变化而变化。

002.jpg

  图2中,圆圈和正方形分别表示ω=0,1。从图2(a)中可以看出,对于ω=0和1,两条直线是重合的,η=2。而在图2(b)中,两条线开始分离,只有ω=1这条线接近于<L2(t)>=t2。这主要是因为当ω=1时,网络成为随机网络,其集聚系数比较小,从而使η接近2。当1<ω<2时,网络有了一定的集聚系数,η也就偏离了2。

  图3中,实心圆、正方形、空心圆分别代表K=2、4、6。

  图2小世界模型中〈L2(t)〉和t的关系图

  图3小世界网络中<L2(t)>和t的关系图

  传播是由δi(t)决定的,并且δi(t)是随着时间而变化的。也就是说δi(t)的分布情况决定着η值的大小。下面对δi(t)和t的关系进行数据分析。图4中上图显示了在不同ω值的情况下δ1(t)和t之间的联系。图中显示,在最初的5个时间段里,随着ω的增大,δ1(t)的减小速度变慢,意思是当ω取最大值时,δ1(t)也最大。除了δ1(t),同样分析了δi(t)的分布情况,结果如图4中下图所示,可以看出δ1(t)与-mt+b的分布趋势是一样的。

003.jpg

  接下来,具体可按照以下步骤来构造HK模型:(1)起始状态,网络中有a个不连接的个体;(2)在接下来的每一步里引入一个新的节点,从这个节点开始一共有a条边连接到初始的所有节点上。新引入的这个节点按照偏好依附机制连接到初始的某个节点上,假设这个节点为θ;新引入的这个节点的其他边则以概率Ut随机连接到θ的邻居节点上,而以概率1-Ut按照依附偏好机制连接到起初的其他节点上。此模型的度分布与无标度模型一样,当Ut=0时,这个模型就是无标度模型。通过改变Ut,就可以得到不一样的集聚系数。

004.jpg

  图5(a)显示了集聚系数随Ut的变化情况,同样也在HK模型中做了异常行为传播仿真,图5(b)显示了不同的Ut下,〈L2(t)〉随t的变化情况。

  另外,从图5(b)可以看出,集聚系数的增大使η偏离了数值2,此结果和小世界模型相同。比较图5(b)与图4(b)可以看出,HK模型相对来说偏离η=2的幅度更小,因此,也就验证了异常行为更容易在非均匀网络中进行传播。同时,不管是小世界网络模型还是HK模型,η的值都是处于1和2之间的。

4结束语

  对网络化软件异常行为的传播过程进行研究,能够提高网络化软件系统的稳定性与可信性。本文利用SIR模型对网络化软件上的异常行为传播过程进行了理论分析和实验模拟。当感染几率一定时,聚集系数C和度分布P(k)都会影响异常行为的传播。异常行为的传播指数η随集聚系数C的增加而变小,随着非均匀度的增强而变大。研究异常行为在网络化软件中的传播可以为以后的异常行为控制提供有意义的指导。它作为网络化软件中异常行为研究的一部分,是十分有价值的。

  参考文献

  [1] 彭成,杨路明,满君丰.网络化软件交互行为动态建模[J].电子学报,2013,41(2):314320.

  [2] 何克清,彭蓉,刘玮,等.网络式软件[M].北京:科学出版社,2008.

  [3] HE K Q, PENG R, LIU J, et al. Design methodology of networked software evolution growth based on software patterns [J]. Journal of Systems Science and Complexity, 2006, 19(2):157181.

  [4] PASTORSATORRAS R, VESPIGNANI A. Epidemic spreading in scalefree networks [J]. Phys. Rev. Lett,2011,86:32003203.

  [5] PASTORSATORRAS R, VESPIGNANI A. Epidemics and immunization in scalefree networks [M]. Berlin: Wiley- VCH,2003.

  [6] HETHCOTE H W.The mathematics of infectious diseases [J]. SIAM Review, 2000, 42(4): 599653.

  [7] COHEN R, HAVLIN S. Scalefree networks are ultrasmall[J]. Phys. Rev. Lett. 2003, 90:058701(14).

  [8] FRONEZAK A, FRONEZAK P, HOLYST J A.Meanfield theory for clustering coefficients in BarabasiAlbert networks[J].Phys.Rev.E,2003,68:046126(14).

  [9] 于静雯,杨冰.基于MapReduce框架下的复杂网络社团发现算法[J].微型机与应用,2014,33(22):7476.

  [10] WATTS D J, STROGATZ S H. Collective dynamics of ‘smallword’ networks [J]. Nature, 1998(393):440442.

  [11] WATTS D J. The‘new’ science of networks [J]. Publ. Math. Inst. Hung. Acad. Sci., 1960(5):1760.

  [12]王健,刘衍珩,刘雪莲,等.复杂软件的级联故障建模[J].计算机学报,2011,34(6):11371147.

  [13] 周宽久,兰文辉,冯金金,等.基于耦合影响格子的软件相继故障研究[J].计算机科学,2011,38(5):129131,174.

  [14] KANEKO K. Perioddoubling of kinkantikink patterns, quasiperiodicity in antiferrolike structures and spatial intermittency in coupled map lattices [J]. Prog. Theor. Phys, 1984, 72(3): 480486.

  [15] CHALLET D, LOMBARDONI A. Bug propagation and debugging in asymmetric software structures [J]. Phys. Rev.E 2004,70(4):10151030.


此内容为AET网站原创,未经授权禁止转载。
Baidu
map