基于失效概率的网络脆弱性度量及优化方法*

韩养胜，程光权，黄金才

（国防科技大学信息系统工程重点实验室，长沙 410073）

基于失效概率的网络脆弱性度量及优化方法*

韩养胜，程光权，黄金才

（国防科技大学信息系统工程重点实验室，长沙 410073）

对网络脆弱性的研究进行了分析总结。综合考虑了网络节点失效概率和失效后果，将网络节点属性纳入到网络脆弱性度量中，并设计了网络优化框架，通过调整节点属性降低网络整体脆弱性实现网络的优化。实验验证所提出的脆弱性度量方法能合理地反映网络节点属性对网络脆弱性的影响，通过优化实现了网络脆弱性的显著下降。最后总结了所提方法现存的不足及未来研究前景。

网络脆弱性，失效概率，节点属性，网络优化

0 引言

复杂网络可以看作是复杂系统的抽象，比如交通网、电网、互联网、物流网络和军事指挥网等。将系统中的功能单元看作网络的节点，将单元间物质、能量和信息的传递作为网络的边，就建立了系统的网络模型。

系统会因为外界的攻击而造成功能下降或丧失，人们关心研究系统的脆弱性并改善系统性能。从网络的角度来看，就是要对网络脆弱性以及网络优化问题进行研究。对于脆弱性，不同领域有着不同的认识。Einarsson等［1］描述了工业系统的脆弱性：意外事件和外部威胁时使系统能力减弱或受到限制。Berdica［2］把交通系统的脆弱性定义为路网对事故的敏感性。信息安全领域中的脆弱性是指“漏洞的可利用性”［3］。在建筑结构工程中，如果一个小的破坏能对结构造成不成比例的严重后果，则称这个结构是脆弱的［4］。可以看出脆弱性一般是指系统对破坏的敏感度。

现在主流的网络脆弱性研究框架是通过定义网络效能，度量节点失效后网络效能的变化。这种度量脆弱性的框架忽略节点自身抗失效的能力，只考虑节点失效后果，而网络节点对应的系统单元往往具备不同的抵抗失效能力。故认为同时考虑节点失效移除难度和移除的后果才能全面刻画节点的脆弱性。随着对网络的研究越来越深入，独立于网络拓扑结构的节点属性开始凸显其重要性。所以要考虑如何将系统功能单元的更多属性信息纳入到网络的分析中来，以获得更为可靠和真实的结果。

认识网络脆弱性的目的是对网络进行优化，使网络更加强健。在传统的网络模型框架下，人们普遍关注的是对网络结构的调整以增强网络结构的稳定性。前面已经论述将网络节点属性纳入到网络脆弱性度量中来的重要性，进而网络的优化可以通过配置节点属性而实现，使网络脆弱性在一定属性资源的限制下达到理想的低水平。

1 网络脆弱性研究

网络脆弱性的研究已经取得了丰硕的成果，现阶段主流的方法是模拟对网络节点的打击，通过节点失效后果来分析节点重要性和网络脆弱性。

1.1 基于节点失效后果的脆弱性研究

传统观点认为节点越重要，越易成为打击目标，其失效后网络效能下降越大，该节点越脆弱［5］。这种节点脆弱性度量的思路是将脆弱性与节点失效后产生的后果相关，并不考虑失效的过程或失效的概率。在Albert的脆弱性框架［6］内，人们研究不同网络在不同打击模式下的效能变化来反映网络的脆弱性——用随机移除节点模拟网络的随机故障和按重要性测度顺序移除节点模拟网络遭受蓄意攻击。其中节点重要性测度主要包括度和介数及其改进测度［7］，一般用网络的连通性［8］和信息在网络中传播的速度［9］表示网络效能，通过网络效能变化与移除节点比例的关系反映网络脆弱性。

1.2 不足及改进

基于节点失效后果度量脆弱性有以下不足：①各种相关概念是建立在网络拓扑结构上的，对节点属性考虑很少。②重要节点往往强健，将节点脆弱性和重要性均看作节点失效后果会导致矛盾。③只考虑失效后果对异质网络中抗毁属性较强的节点是不公平的，得到的脆弱性不完整。

目前对Albert脆弱性框架的改进包括3个方面：①关注如何建立更有效的网络效能表达［10］。②关注如何更合理地发现重要目标［11］。③跳出拓扑结构局限，考虑实际系统的更多特征属性［7］。

然而这些改进并没有突破以节点失效后果作为脆弱性度量的框架。下面提出一种基于节点失效概率的脆弱性度量方法，将节点与抗毁性相关的属性纳入，能更为全面地考察网络脆弱性。

2 基于失效概率的脆弱性度量方法

将节点脆弱性的形成看成串联的两个部分——节点受打击失效的概率和节点失效的后果，用下式表示节点vi的脆弱性：

其中P（G→G/vi）表示网络中G节点vi失效的概率，主要与该节点的等级和属性配置有关。

diff（E（G/vi，E（G）））表示节点vi的失效后果，通过节点失效后网络效能的变化反映。

将影响脆弱性的节点属性量化，建立上述两项关于节点属性的函数表达，就能度量某特定网络节点的脆弱性，而所考虑的网络节点属性和网络效能指标取决于实际网络的状态以及研究者的侧重点。下面给出一种综合考虑网络节点等级、备份、抗毁等能力的脆弱性度量方法。

2.1 网络节点属性

现实系统抽象出的网络，其节点应能代表与其意义相对应的现实属性。文献［12］中异质节点vi的属性是包含了节点的性能指标向量vi、节点唯一标识di和节点类型ti的三元组vi=（ci，di，ti）。

类似地，将实际系统的更多属性纳入到网络的分析中来。针对防空反导系统，要考虑的属性包括节点的功能等级C（如指挥所级别），节点备份数B（如备份的雷达阵地，冗余的通信线路），节点抗毁性能D（如各功能单元的防守力量）等。

2.2 节点失效概率的计算

失效概率由受攻击的概率和攻击后失效的概率决定，将两者看作是相互独立事件，并将节点的等级、备份、抗毁能力等因素考虑在内，则节点的失效概率为：

其中Pat（vi）表示节点vi受攻击的概率。节点等级系数记为C（vi），C（vi）∈（0，1］。节点等级越高其遭受攻击的概率越大，所以定义Pat（vi）=Kat·C（vi）。

Plost（vi）表示节点vi遭受攻击后失效的概率。节点备份系数记为B（vi），B（vi）∈［0，1），表示对应节点备份能力的大小；节点抗毁系数记为D（vi），D（vi）∈（0，1），表示对节点防守力量的强度。两者对于失效概率的贡献是负的，将备份节点看作并联结构，则可定义

其中K=Kat·Klost为比例系数，由于节点的脆弱性是相对值，仅考虑以上3种属性对失效概率的影响，可取K=1。

以上所考虑的节点的属性为（C，D，B），还可以根据需要将更多影响失效的属性考虑进来（如节点失效后的恢复能力等）。

2.3 节点失效后果的度量

节点失效后果diff（E（G/vi，E（G）））的度量首先要定义网络效能函数，节点失效后果即从网络中移除该节点后，网络效能的变化。

其中E（G）为网络效能函数，一般用网络的平均最短距离、直径、平均聚集系数等来衡量，侧重不同。文献［9］认为网络效能反映信息在网络中的传播速度，定义效能指标如下：

有了网络效能指标，可以进一步定义节点失效后果：

其中E［G/（vi）］为网络表示节点vi从网络G中移除后，形成的新网络的效能。

综合节点失效概率和节点失效后果，可以得到节点脆弱性的表达：

2.4 网络整体脆弱性

文献［13］指出强健的网络需尽可能均匀，即认为分布均匀的网络脆弱性越小。基于同一种思想文献［14］中利用节点抗毁性的分散程度定义全网的脆弱性，认为网络中节点抗毁性波动程度越小，网络抗毁性越高。类似地，利用节点脆弱性度量值的均方差定义网络的整体脆弱性，即：

Vul为节点平均脆弱性度量值；D（Vul）为网络整体脆弱性度量值。D（Vul）越小，说明网络节点属性的配置相对均匀，其脆弱性越小。

3 网络优化方法

目前网络优化的方法集中在网络结构的优化上。Alina等［15］通过添加边的方式，把网络最大团尺寸和平均最短距离作为衡量网络功效性的标准来优化网络。Shargel等［16］以网络直径为网络功效性指标，定义两个可调参数来优化网络结构。以上网络优化方法是开放式的，未考虑优化网络的代价。Sergiu等［17］在保证边数目不变的情况下，利用遗传算法进化网络，降低其脆弱性。Bing Wang等［18］研究了网络对于随机攻击的抗毁能力，认为少量中心节点和高簇聚系数的网络脆弱性更小。而Wang［19］更进一步建立网络的熵优化模型，研究了无标度网络对于随机攻击抵抗力的一些规律。

可以看出以上网络优化方法关注的都是如何降低网络结构上的脆弱性，而无法处理结构相对固定而节点具有异质属性的网络。本文提出优化方法能弥补这方面的不足，即能回答“网络建立后，如何利用配置现有属性资源，使网络的脆弱性最小”这一问题。根据上文建立的脆弱性度量方法，网络优化的数学模型如下：

式中：

D（Vul）表示网络的整体脆弱性

B（vi），D（vi）等表示节点vi配备的属性

B0，D0，…等表示资源约束

该优化模型实现能在各种属性资源的限制下，最小化脆弱性函数D（Vul）数。本文实验中利用遗传算法搜索模型的解。

4 实验分析

首先利用上述脆弱性度量的方法对构造网络的脆弱性进行分析，研究节点属性与脆弱性的关系，利用上述优化方法对节点属性配置进行优化。然后将方法应用于某防空指控系统网络，分析各指控中心的脆弱性及优化方法。

4.1 构造网络实验

构造如图1对称网络，定义网络节点属性，对此网络的节点脆弱性及整体脆弱性进行研究。

实验1

实验1中，把各节点的属性值设置为相等（表1），不考虑节点属性异质性。得到的节点脆弱性结果如图2。

结果分析：本实验中节点属性配置没有差别，结果反映了结构上节点的重要性与其脆弱性一致的传统观点。因为仅就网络结构而言，越重要的节点遭受打击的可能性越大，失效后的网络受到的破坏也越大。从后续实验可以看出，考虑网络节点异质属性时，这种观点是不合理的。此外网络的整体脆弱性为0.001 8。

实验2

实验2中，为各节点配置不同属性如表2，实验结果如图3所示。

结果分析：

1）与实验1比较，节点3的变化说明当仅增大节点功能等级时，会增大其脆弱性。这是因为功能等级影响节点受攻击的概率乃至其失效概率。该变化反映了传统的脆弱性与重要性相关的思想，同时说明本文提出的方法对传统脆弱性度量方法有一定的反映。

2）为节点4提高了备份系数和抗毁系数，将使其失效概率下降，脆弱性降低。仅依赖网络拓扑结构显然无法反映这些差别的。

3）而比较节点1和节点5，同时改变节点的3个属性值，其脆弱性的改变将取决于这3个值的相对大小。当赋予某节点较高的功能要求时，要同时提高其防卫的力量，并做好备份，才能保证该节点脆弱性不降低。

4）整体的脆弱性为0.003 2，比实验1明显增大。这是节点属性分配导致各节点脆弱性更加不均匀造成的。

实验3

本实验为优化实验，将节点备份资源限制为5，节点抗毁系数总和限制为5，各节点等级均保持在0.5。采用遗传算法搜索最优解，需要进行调配的两个属性的种群大小为100，经过100次迭代，得到的节点备份系数和抗毁系数分配以及最小整体脆弱性如表3所示。

分析：从实验1中可以看出，节点3、节点4和节点7、节点8具有较大的结构重要性，使其易受到攻击，且失效后网络效能下降大。优化结果倾向于对这些重要节点采用较高的备份和抗毁能力的配置。对于重要性较低的节点，就可以降低这些能力的要求，以实现节点脆弱性的分布相对均匀（如图4）。另外本实验与实验1中各节点属性资源之和相同，通过优化使网络整体脆弱性由0.001 8下降到8.5×10-5，可以看出优化效果显著。

4.2 防空系统网络实验

如图5为某防空指控网络实例［12］，其中包含12个雷达站（R1～R12）、7个指控中心（C1～C7）和12个导弹阵地（M1～M12）。图中实线箭头表示指控关系，虚线箭头表示上报关系。文献［12］编制了个目标打击难度，计算了目标价值得分。本实验利用这些数据，对指控中心的脆弱性进行分析，并提供了保护该网络的行动方案。

将目标打击难度（表4）对应公式中的节点的抗毁系数；节点备份系数均设为0.2；节点功能等级按命令关系即指控中心的级别划分（表6）；已经计算得到的目标价值可表示节点失效后果。网络脆弱性分析结果如表7所示。

由实验结果可以看到目标脆弱性分析结果和目标的价值评分有着显然的相关性，这是因为目标价值不仅直接决定目标摧毁后的损失，还和目标的功能等级相关，即影响目标受打击的概率。

从保护角度来看，对于重要节点C1和C7的防护显然不够。如果增大对这些重要目标的防护力量，将有效降低重要目标的脆弱性，同时降低整个系统的脆弱性。如提高C1和C7备份系数为0.4，则新的结果如表8所示，整体脆弱性由0.018下降到0.001 2。

5 结束语

通过以上实验和分析可以看出，文中提出的度量网络节点和网络整体脆弱性的方法可以有效地评价网络各节点脆弱性的相对大小并衡量网络整体脆弱性，能实现基于节点属性配置的网络优化。但也存在以下不足有待进一步研究：①对于具体网络还要根据网络的功能，各节点属性的存在及表现形式来构造相应度量公式或通过其他方式学习得到。②节点属性值的确定在实际操作中有一定难度，由于涉及到各参数的组合运算，需要对数据进行规范化，规范化方法有待参考相关领域的专家知识才能确定。

正如文中论述的那样，将更多网络属性纳入到诸如网络脆弱性等网络特征的分析中来是网络科学领域发展的方向。沿着这一方向研究，有望形成基于网络属性的系统优化和破击方法，是对网络结构研究的重要补充和发展。

［1］Einarsson S，Rausand M.An Approach to Vul nerability Analysis of Complex Industrial Systems［J］.Risk Analysis，1998，18（5）:535-546.

［2］Berdica K.An Introduction to Road Vulnerability:What Has Been Done，is Done and Should be Done［J］.Transp Policy 2002（9）:117-27.

［3］Morakis E，Vidalis S，Blyth A.Measuring Vulnerabilities and Their Exploitation Cycle［J］.Information Security Technical Report，2003，8（4）:45-55.

［4］Agarwal J，Blockley D，Woodman N.Vulnerability of Structural Systems［J］.Struct Saf 2003，25:263-86.

［5］强强.网络脆弱性以及鲁棒性理论的近期研究发展［J］.上海理工大学学报，2011，17（3）:12.

［6］Albert R，Jeong H，Barabási A L.Error and Attack Tolerance of Complex Networks［J］.Nature，2000，406（6794）: 378-382.

［7］Bompard E，Wu D，Xue F.Structural Vulnerability of Power Systems:A Topological Approach［J］.Electric Power Systems Research，2011，81（7）:1334-1340.

［8］Criado R，García Del Amo A，Hernández-Bermejo B，et al.New Results on Computable Efficiency and its Stability for Complex Networks［J］.Journal of Computational and Applied Mathematics，2006，192（1）:59-74.

［9］Crucitti P，Latora V，Marchiori M，et al.Efficiency of Scale-free Networks:Error and Attack Tolerance［J］. Physica A:Statistical Mechanics and its Applications，2003，320:622-642.

［10］Mishkovski I，Biey M，Kocarev L.Vulnerability of Complex Networks［J］.Communications in Nonlinear Science and Numerical Simulation，2011，16（1）:341-349.

［11］Petreska I，Tomovski I，Gutierrez E，et al.Application of Modal Analysis in Assessing Attack Vulnerability of Complex Networks［J］.Communications in Nonlinear Science and Numerical Simulation，2010，15（4）:1008-1018.

［12］刘彦君.异质网络的目标评估与脆弱性分析研究［D］.长沙：国防科技大学，2013.

［13］欧阳敏，费奇，余明辉，等.复杂网络的功效性与脆弱性研究综述［J］.计算机科学，2008，32（7）:1-4.

［14］郭虹，兰巨龙，刘洛琨.考虑节点重要度的Ad Hoc网络抗毁性测度研究［J］.小型微型计算机系统，2010，21（6）:1063-1066.

［15］Beygelzimer A，Grinstein G.Improving Network Robustness Byedge Modification［J］.Physica A，2005，357:593-612.

［16］Shargel B，Sayama H，Epstein I R，et a1.Optimization of Robustnessand Connectivityin Complexnetworks［J］. Phys.Rev.Let t.，2003，90（6）:068-701.

［17］Netotea S，Pongor S.Evolution of Robust and Efficient System Topologies［M］.Hungary：Hungary Cellular Immunology，2007.

［18］Wang B，Tang H W.Optimization of Network Structure to Random Failures［J］.Physica A，2006，368:607-614.

［19］Wang B，Tang H W，Guo C H，et al.Entropy Optimization of Scale-free Networks Robustness to Random Failures［J］.Phys-Ica A，2005，363:591-596.

Measurement of Network Vulnerability Based on Probability of Losing Efficacy and Approach to Network Optimization

HAN Yang-sheng，CHENG Guang-quan，HUANG Jin-cai
（Science and Technology on Information Systems Engineering Laboratory，National University of Defense Technology，Changsha 410073，China）

Achievements in the research of network vulnerability have been introduced and the limitation and the improvement method have been analyzed.Taking both probability and consequence of losing efficacy of nodes into account，measurement of networks vulnerability considering the attributes of nodes and optimization approach of network by adjusting the attributes are proposed. Experiments have proved that the measurement can explain the attributes’effects on networks vulnerability reasonably and the optimization approach also works very well.At last the paper discusses the limitation of the study and the research in the future is also illuminated.

network vulnerability，probability of losing efficacy，attributes of nodes，network optimization

N949；TP393

A

1002-0640（2015）09-0016-05

2014-08-03

2014-09-15

国家自然科学基金（61201328）；国家自然科学基金重大计划资助项目（91024006）

韩养胜（1990- ），男，安徽阜阳人，硕士研究生。研究方向：管理科学与工程。