基于复杂网络的风险传播模型及有效算法

基于复杂网络的风险传播模型及有效算法

吕元海孙江辉杜程摘要：提出一种基于复杂网络的风险传播模型及有效算法，通过结合复杂网络中传播蔓延现象的推广模型，将风险传播模型划分为两种：主动型风险传播模型与被动型风险传播模型。并对已有风险传播算法进行改进，实验表明，该模型及算法能健全风险传播机制，提高传播速度与精确度。关键词：复杂网络；推广模型；风险传播TP393.0：A1引言随着网络安全问题的日益突出，风险评估越来越受到人们的重视。风险评估一般分为静态评估和动态评估两种，前者评估体系比较完善，评估精确性程度较高，但缺点是评估周期过长，评估模型可能随着时间的推移而不能适用，不能反映网络的实时信息；后者评估能根据网络状况适时的做出风险估计，能及时反映网络风险的动态变化，性能好于静态评估[1，2]。而针对动态风险评估的研究有：基于免疫的网络安全风险检测的模型[3，4]，是一种基于入侵时的检测模型；基于隐马尔可夫模型的网络风险评估方法研究[5，6]；基于贝叶斯模型的网络风险动态评估方法[7，8]，可以对网络的总体风险和局部要素可能引起风险的程度进行评估。以上文献对网络入侵检测研究较为深入，但侧重于对攻击的动态评估，未能考虑已有风险如何扩散与转移。针对网络风险传播，张永铮等提出了用于评估网络信息系统的风险传播模型[9]和一种求解网络风险传播问题的近似算法[10]，对已有风险在网络中的传播进行研究，但其传播模型与算法存在一些缺点：首先，模型中仅考虑了风险传播模型，未能考虑风险引入模型；其次，一个部件上可能存在多个弱点，则该部件对另一部件的同一方向的可信访问路径可多于一种，则部件不能在有向图中被视为图节点。第三，最小入度的部件感染风险的概率较低，因此其作为风险源的概率不高。第四，若入度最小的部件已经感染风险，其出度不一定是最大的，正如流感爆发在人口密集的地区一样，则其风险不能立即传播出去，存在滞后性，时效性欠佳。本文在针对网络风险传播问题，结合复杂网络中传播蔓延现象的推广模型[11，12]，提出了一种网络风险传播模型及相关定义，并改进了风险传播算法。2推广模型下的风险传播网络信息的动态风险不仅仅表现为一般意义的风险，其传播可能会对社会造成不可估量的损失，如病毒的传播造成的跨域风险、有害信息的传播造成的社会风险等。为此我们将借鉴复杂网络的传播机理和分析的方法，研究网络风险传播模型。按照复杂网络的传播蔓延现象的推广模型[11，12]：假设网络中有N个个体，每个个体是三种状态的中的一种：易染态S，感染态I和移除态R，在时刻t，个体i随机的与个体j相连，若i∈S，j∈I，则个体i以概率p得到一个正剂量di（t′），这里di（t′）都服从分布函数f（d）。每个个体都保留着过去T时期中所接受的总的剂量在本文中，暂不考虑网络风险移除状态，即仅考虑风险在整个网络中如何转移，而未考虑网络风险传播后所造成情况的如何消除。因此上述推广模型应用于风险传播如下：计算技术与自动化2016年6月第35卷第2期吕元海等：基于复杂网络的风险传播模型及有效算法每一时刻t，风险结点j对其直连结点i每发动一次攻击，就会从被攻击结点i中获取一定的信息剂量di（t），则在过去T时期中风险结点获取被攻击结点的信息总剂量为：3风险传播模型3.1相关定义定义1.结点：指网络系统中任意一台网络设备上任意可能被利用的最小单元。其中已经被利用的称为风险结点，而尚未被利用的称为非风险结点。定义2.有向路径：结点A访问结点B时，形成的从A指向B的单向访问关系。这里所说的单向访问关系是指合法或非法的、由主动发起方指向被访问方的访问，而不代表实际信息传输的路径，因为严格的讲，任何两个相连结点之间的链路都是双向的。有向路径概率即为结点访问概率。定义3.风险传出：指风险结点对其所访问的任一结点造成的损失或影响。定义4.风险引入：指非风险结点访问风险结点时，由于存在实际信息的交换而受到该风险结点的影响。这里举例说明一下定义3、4，某病毒利用空气（相当于网络中的信息交换链路）进行传播，当病体A主动接触易染体B时，A将病毒传播给B，其中A主动接触B即为A访问B，病毒传播方向为A到B；反之当易染体B主动接触病体A，也会被感染，同样病毒传播方向为A至B，但为B访问A。定义5.风险传出公式：设结点n被成功利用的概率为Pn，被利用后对网络系统的危害程度为Wn，利用至该结点的有向路径概率为Pmn，其中m为主动访问n的风险结点，则对结点n而言，产生的风险为Riskn=Pmn×Pn×Wn。定义6.风险引入公式：设结点n为非风险结点，该结点成功访问风险结点m的概率为Pm，利用至结点m的有向路径概率为Pnm，由结点n发出至结点m的有用消息权重及概率分别为Unm、pnm，由结点m发出至结点n的有害消息权重及概率分别为Hmn、pmn，则对结点n而言，引入的风险为Riskn=Pnm×Pm×（Unm×pnm+Hmn×pmn）。定义7.风险网络：借鉴张永铮等对风险网络[4]定义，把一个能够描述各结点风险分布与有向路径的网络称为风险网络。风险分布为网络系统各个设备中结点携带风险的分布情况，为内在风险；有向路径即为各结点之间的访问方向，为外来风险的传出与被引入提供可能。3.2风险传播模型1.主动型风险传播模型：也称为主动型风险传出，即利用风险结点已存在的风险对其直连结点进行主动访问（包括非法攻击或可信访问，下同），产生风险扩散（即风险传出）。如图1（a）所示，结点A为风险源结点，存在至结点B、C、D、E的四条有向路径，设结点A风险结点，至结点B、C、D、E的有向路径概率为PAJ，（J=B，C，D，E），各结点自身被成功访问的概率为PJ，（J=B，C，D，E）[8]，则结点A以概率PAJ×PJ（J=B，C，D，E）引起其出度所连结点发生风险，如图1（b）所示。在实际网络中，路径传播概率可由两结点的所有可能路径计算得出，而结点被成功攻击的概率则有风险传播推广模型计算得出。4最大出度算法针对最小入度最近邻算法[5]的不足，本文设计了一种能更好反映网络风险动态特征的算法——最大出度算法，又分为针对主动型风险传播模型的最大出度算法和针对被动型风险传播模型的最大出度算法。4.1风险源结点最大出度算法Step1：计算未被处理过的风险结点出度值numofoutdegree。Step2：优先选择最大出度的结点，利用图1所示算法将其风险值沿其出度传播给相邻结点，风险计算方法见定义5。Step3：传播风险后将该结点标记为color=red。Step4：重复Step1、Step2、Step3，直至所有风险结点全部被标记。4.2零入度非风险源最大出度算法严格的讲，零入度的结点是不存在的，因此最小入度最近邻算法关于零入度的概念未指明其时间范畴，在本文中，零入度的结点是指在某时间段内不接受访问的结点。StepA：将网络结点中所有零入度的非风险源结点标记为color=green。StepB：计算未被处理过的零入度的非风险源的出度值numofoutdegree。StepC：优先选择最大出度结点，并判断其出度中有无风险结点，若有则选择其出度所连结点中风险值最大的一个作为引入风险源，以概率引入风险，风险计算方法见定义6，将该结点标记为color=pink，断开与引入风险源的有向链接；若无，则重新选择结点，对该结点不进行任何处理直到再次满足条件。StepD：引入风险后，该结点已为风险结点，如果满足最大出度的条件，则跳转至最大出度算法的Step2继续风险传播。如果暂不满足最大出度的条件，则跳转至StepA顺序执行。4.3一般非风险源风险引入网络结点的风险在传播最后往往会出现如图3所示的情况：结点A、B、C为非风险源结点，D、E为风险结点且RiskD>RiskE，按照文[5]的理论，则其程序在图3情况下停止运行，为了解决这一问题，引入如下算法：Stepa：计算非风险源结点的出度值numofoutdegree。Stepb：优先选择出度最大的结点，若其出度所连接结点中存在风险结点，则选择风险值最大的一个结点作为风险引入源并断开与该风险引入源的有向链路，该结点被标记为color=pink；若不存在，则重新选择。Stepc：引入风险后，该结点已为风险结点，跳至Stepb继续执行，直至又出现图3情况，则跳转至Stepa继续执行，直至风险传播完毕。说明：网络结点被初始化为风险结点（color=pink）和安全可信结点（color=green）后，运行风险源最大出度算法和零入度非风险源最大出度算法时，两者发执行，不存在先后次序，而一般非风险源风险引入只是在出现如图3情况下才使用的算法，是为了防止风险传播中忽略此类风险引入导致风险误差较大的情况。5算法性能比较5.1风险传播机制比较最小入度最近邻传播算法[5]虽然能够对网络风险传播给出比较精确的结论，但其在理论上有一定的缺陷，如图4所示，假设结点1、2为风险结点，按照最小入度最近邻传播算法，结点1为入度最小的满足条件的风险结点，则其以概率使结点2、4产生风险，同时将自己标记为已处理，如图5（a）所示，然后结点2又满足传播条件，并以概率使结点3、5、6产生风险，并被标记为已处理，如图5（b）所示，两步共计感染四个结点，但其却是在第二步才将风险传给结点6，因而其时效性欠佳。而按照风险源最大出度算法，则优先选择结点2，使其携带的风险迅速被传播给结点3、5、6，如图6（a）所示，再次结点6满足传播条件，并将风险传播给其出度所连的四个结点，如图6（b）所示，两步共计感染七个结点，多于最小入度最近邻传播算法的新感染结点，并且其时效性优势随着网络结点的复杂化而凸显，更容易满足动态网络风险评估的要求。此外，零入度的非风险源结点不会传出风险[5]，因此应在风险传播之前对其进行处理：断开此类结点的所有出度，如图7所示，结点9被认为不会对结点2及尤其是结点10造成风险传播，因此可以断开其所有出度。但本论文认为结点9虽不会对结点10造成直接的风险传播，但是它可能会从结点2引入风险，从而使自己变为风险结点，进而对结点10造成风险传播，如图8所示。5.2实验结果对比本实验实验环境为MicrosoftWindowsXPProfessional，Intel（R）Pentium（R）CPU1.8GHz，512MRAM。仿真工具为NetLogo4.0.4、Matlab7.0.0.19920（R14）。共同参数：总结点为200，平均度为10，风险结点不超过所有结点入度之和，结点危害性参数W=1，风险结点初始风险值为1，路径传播概率服从[0，0.5]上的均匀分布。本文参数：结点被成功访问概率P可利用推广模型计算，其中推广模型的参数p=0.5，f（d）=δ（d-1），g（d*）=δ（d*-3），采用最大出度算法进行传播。文[5]参数：概率权p（x）=0.5，采用最小入度最近邻算法进行传播。6结论实验表明：本文方法则是风险呈非线性变化，并且开始变化较快，最后变化缓慢，即在一定的精确度容许的范围内，对风险进行任意时刻的抽样，本文的风险值更接近真实风险，因而动态性能更好。另外考虑的非风险源结点的风险引入，使风险值被忽略的部分被重新计算在内，提高了风险精确度。参考文献[1]吴金宇.网络安全风险评估关键技术研究[D].北京：北京交通大学，2010.[2]肖晓春.基于模型的网络安全风险评估的研究[D].上海：复旦大学，2008.[3]李涛.基于免疫的网络安全风险检测[J].中国科学（F辑一信息科学），2005，35（8）：798-816.[4]刘谦.网络安全风险评估研究[J].硅谷.2009，（14）：65-70.[5]史志才.网络风险评估方法研究[J].计算机应用，2008，10：2471-2473.[6]陈锋.基于多目标攻击图的层次化网络安全风险评估方法研究[D].长沙：国防科技大学，2009.[7]梁玲，陈庶民，徐孟春，等.基于贝叶斯模型的网络风险动态评估方法[J].信息工程大学学报，2007，（1）：53-55.[8]付钰，吴晓平，严承华.基于贝叶斯网络的信息安全风险评估方法[J].武汉大学学报：理学版，2006，52（5）：631-634.[9]张永铮，方滨兴，迟悦，等.用于评枯网络信息系统的风险传播模型[J].软件学报，2007，18（1）：137-14