第 31 卷第 12 期 电 子 与 信 息 学 报 Vol.31No.12 2009 年 12 月 Journal of Electronics & Information Technology Dec..2009 基于流量攻击和边失效的复杂网络脆弱特性 吴 艾 刘心松 刘 丹 (电子科技大学计算机科学与工程学院 成都 610054) 摘 要：基于流量的攻击可能对复杂网络造成严重破坏，现有研究主要针对节点攻击。该文分析了部分边失效时， 复杂网络的脆弱特性。此外，分析了时机策略和网络规模对边失效的影响。通过研究节点负载和度分布特点，发现 复杂网络的脆弱特性源于其幂率度分布引起的节点负载的极度非均匀分布。仿真实验表明，复杂网络对随机的边失 效具有较强的耐受力，但在一定条件下，攻击极少量重要边就可能引发连锁的节点过载失效，而导致网络溃散。 关键词：复杂网络；边失效；负载；度分布 中图分类号：TP393 文献标识码：A 文章编号：1009-5896(2009)12-2997-04 Frangibility of Complex Networks Based on Flow Attack and Edge Failure (School of Computer Science and Engineering, University of Electronic Science & Technology of China, Wu Ai Liu Xin-song Liu Dan Chengdu 610054, China) Abstract: Attacks based on flow may bring tremendous damage to complex networks. In existing works, the cases of nodes attacking are mainly concerned, however, few work is involved to the edges. In this paper, the frangibility of complex networks is discussed in the case of some edges being deleted. Additionally, the effects of time strategy and network size are also discussed. By analyzing the load and degree of complex networks, it is demonstrated that the complex networks possess a high heterogeneous distribution of loads, which is caused by the power-law degree distribution, and the heterogeneity makes the networks particularly vulnerability to attacks. The analytic results show that complex networks exhibit strong error tolerance to random failures of edges, but a large-scale cascade of node failure can be triggered by disabling several key edges, which may result in the collapse of networks. Key words: Complex network; Edge failure; Load; Degree distribution 1 引言 脆 弱 性 问 题 是 复 杂 网 络 研 究 中 的 重 要 内 容 [1 4]− 。在基于流量的网络攻击下，复杂网络可能 变得很脆弱。这类攻击中，攻击者利用网络流量的 变化，使较多流量集中到少数节点或边，造成节点 或边的负载过重而失效，并形成连锁反应，对网络 造成严重破坏 [2 5]− 。对于动态复杂网络的脆弱性， 现有研究 [3 5]− 主要考虑节点攻击的情况，但在一些 实际网络中，连接边更容易被破坏，且已有研究未 考虑时机策略的影响。 本文针对动态复杂网络，讨论部分边失效时网 络的脆弱特性。在边失效模型的基础上，分析少量 边受到攻击或随机失效时，网络结构的变化特点， 同时与其他类型网络的边失效特点比较，并分析复 杂网络脆弱性的原因。 2008-12-08 收到，2009-06-01 改回 现代通信国家重点实验室基金(060C11)资助课题 2 分析模型 初始时刻，网络处于稳定状态。当部分边失效， 某些节点间的路径改变，引起网络流量重新分布， 如节点的负载超过其容量，则会因过载而失效，这 又会引起新的网络流量重分布，如此形成连锁反应， 直到所有节点不过载，网络重新达到稳定状态。 ( , , , ) 根据以上描述，定义网络边失效分析模型为 F α ω ε β 。网络初始节点和边数分别为 N 和 E。 假设网络中每对节点之间均有 1 个单位的持续流量 沿最短路径传输，节点 i 在 t 时刻的负载为 L(t,i)， 其值为此时流经 i 的流量总和。定义节点 i 的容量 c(i)与初始时刻 i 的负载正相关，c(i)等于(1+ α ) L(0,i)。α 为网络负载系数，α 越小表示网络初始负 载越重。 ω 为边失效模式，分为随机模式 RM 和有 针对性攻击模式 AM。AM 模式下，按边权值从大 到小删除边，边权值为边的端节点的度之和。 ε 为 失效边总数。时机策略 β 指删除 ε 条边的规则，定 义 3 种策略：Fot，在 0 时刻删除 ε 条边；Fas，当 

2998 电 子 与 信 息 学 报 第 31 卷 系统处于稳定状态时，每单位时间删除一条边，否 则不删除边，直到删除边数达到 ε ；Fet，每单位时 间都删除一条边，直到删除边数达到 ε 。 定义 1 网络连通率 θ 定义为网络中实际存在 的路径数与理论上的最大路径数之比。 若两节点之间能相互到达，则这两个节点间的 路径数为 1，否则为 0。θ 表示任意节点之间存在路 径的概率，以之来评价网络结构的完整性程度。当 θ 低于常数 cθ ，认为网络溃散，称 cθ 为网络溃散连通 率，本文设 cθ 为 0.3。当 α ，ω 和 β 一定，使网络溃 散所需的最小 ε ，称为网络溃散临界边数量，表示 为 cε 。从初始时刻到网络溃散，即 θ 达到 cθ 时止， 所经历的时间称为网络溃散临界时间，简称临界时 间，表示为 Tc。 假设：所有的边不会由于过载而失效；网络拓 扑在初始时刻都是连通的。 3 复杂网络的脆弱特性 基于上述分析模型，重点研究 SF(Scale-Free) 网络[4,6,7]的脆弱性。文中的模拟 SF 网络用 Inet 模 型[6]生成，除加以说明外，模拟网络的 N 为 2000， E 为 3997，平均度为 4。 3.1 网络连通率 RM 模式下，α 取 0.1 时，θ 的变化如图 1。θ 随 ε 的增加缓慢下降，即使 ε 达到 E 的 25%， θ 也仅 为 0.67，同时，时机策略对随机边失效的结果的影 响很小。AM 模式下，α 为 0.5 时，θ 的变化如图 2， 任意时机策略下， θ 均在 ε 取很小值时，就迅速下 降至 cθ 。 3.2 网络溃散临界点 ε 取 cε 时能得到最佳攻击效率，下面分析 AM 模式下不同负载对应的 cε 和 Tc。 cε 随 α 的变化如图 3。α 较小时，各时机策略对 应的 cε 差别不大，均只需攻击最重要的一条边就可 使网络溃散。 α 增加至 0.7，Fot 和 Fas 对应的 cε 仅 增至 2，而 Fet 的 cε 则已达到 13。随着 α 的进一步 增加，3 条曲线的差异更明显，当 α 为 1.0 时，Fot， Fas 和 Fet 的 cε 分别为 4，20 和 27。虽然在轻网络 负载下，各时机策略对应的 cε 较大，但由于边总数 E 较大，所以仍然可认为 cε 很小。 与图 3 相对应的 Tc 的变化如图 4。 α 较小时， Tc 很小，Tc 随着 α 的增加而增大，Fas 的 Tc 的增速 最快。另外在分析中发现，在 cε 之上再增加少量攻 击边数，可大幅降低 Tc。 因此，在各种网络负载下，删除少量重要边都 会使网络溃散。时机策略对边攻击效果的影响随 α 的增加而增大，而 Fot 策略对应的边攻击的破坏力 最强。 3.3 边失效的网络规模无关性 AM 模式和 Fot 策略下， cε 和 Tc 随网络节点数 N 变化如图 5 和图 6，N 从 500 到 5000，平均节点 度约为 4。如图 5，当 α 不变时， cε 并不随 N 的增 大而发生较大变化，而是在某值附近小幅波动。当 图 1 边随机失效时 SF 网络的 θ 图 2 边攻击下 SF 网络的 θ 图 3 边攻击下 SF 网络的 cε 图 4 边攻击下 SF 网络的 Tc 图 5 cε 随网络规模变化 图 6 Tc 随网络规模变化 

第 12 期 吴 艾等：基于流量攻击和边失效的复杂网络脆弱特性 2999 N 一定时，虽然较大的 α 对应较大的 cε ，但与总边 数 E 相比， cε 仍然很小，即使 N 为 5000，且 α 为 1.0， cε 也不超过 5。同时，α 一定时，Tc 不随 N 的 增加而大幅变化，只随 α 的增加而变大，如图 6。 可见，代表边失效临界状态的 cε 和 Tc 均表现出 与 N 无关的特点，而与网络初始负载有较强相关性。 Fas 和 Fet 的相关特性与 Fot 类似。 3.4 不同类型网络的边失效特性 下面分析部分不同类型的网络在 AM 模式和 Fot 策略下的边失效特性，以作验证和比较。包括 规则网络 NW 和 Cayley，随机网络 RAND 和 Internet AS (Autonomous System)网络[7]。 NW 网络由小世界网络模型 NW[7]生成，其结 构为所有节点首尾相连构成环，再添加少量随机边 而成。Cayley 网络[7]的特点是除端节点外，其余节 点的度相等。RAND 网络的节点之间以一定的概率 建立连接边，由 ER 模型[7]生成。AS 则是实际的 SF 网络。 cε 随 α 变化如图 7，不同类型的网络之间的差 异很大。当 α 变化时，除极少数情况外，NW 和 Cayley 的 cε 分别保持为 3 和 6 不变。RAND 的 cε 随 α的增加而迅速增大， α 为 0.3， cε 已达到 100。AS 属于 SF 类网络，其边失效特性与 Inet 模型生成的 网络类似，如图 7 的 AS 和图 3 的 Fot。 边攻击下，不同类型网络的 Tc 也有较大差异， 如图 8。Cayley 和 NW 的 Tc 几乎不随 cε 的增加而改 变。而 AS 与 SF 的变化趋势相似。 由此可见，不同类型网络的边失效特性有较大 差异。规则网络的边失效特性仅与网络类型有关， 而与网络负载相关性很小，SF 类网络则与网络负载 密切相关，边失效对随机网络的影响则很小。在 Fas 和 Fet 时机策略下的结果与 Fot 类似。 3.5 SF 网络边失效特性根源 3.5.1 节点度和负载 初始时刻，SF 网络中节点的 标准化的负载和度对照如图 9。负载与度表现出较 强的相关性，度较大的节点，其负载也较大。节点 累积负载如图 10，少数节点负担了很重的网络负载， 比如负载最重的 5%的节点承担了网络中 46%的流 量。 形成图 9 和图 10 中节点负载的极度非均匀分布 的原因在于 SF 网络的近似于幂率规律的度分布。 SF 网络中，高度节点相互连接形成核心网[4]，核心 网连接着较多的中小度节点，在流量交换中起到核 心路由的作用，这使大量流量经过核心网，而低度 节点的负载则很轻。 3.5.2 节点负载分布对网络脆弱性的影响 在流量 攻击下，SF 网络的极度非均匀的节点负载分布对网 络的脆弱性会产生重要影响，下面分析模型实例 F( α =0.5, ω =AM, ε =4, β =Fot )。当部分重要边被 删除，高度节点的部分负载将发生转移。度最大的 2.5%的节点负载之和随时间变化如图 11，在初始时 刻占网络负载总量的 40%，当受到边攻击后，很快 下降至 2.1%。转移流量的一部分转由其他高度节点 承担，由于高度节点的容量相对较大，因此过载失 效的情况很少。过载失效节点的度值分布如图 12， 图 7 不同网络的 cε 对比 图 8 不同网络的 Tc 对比 图 9 节点的初始负载与初始度 图 10 节点的累积负载与累积度 图 11 度最大 2.5%节点的负载之和 图 12 过载失效节点的度 

3000 电 子 与 信 息 学 报 第 31 卷 仅有一个过载节点的度超过 13。转移流量的其他部 分则分布到中小度节点，由于中小度节点的容量相 对较小，因此造成部分中小度节点过载失效。如果 攻击边达到一定数量(临界边数)，将形成大规模的 连锁的节点过载失效，并最终导致网络溃散。因此， 造成大部分过载节点为中小度节点，如图 10，绝大 多数过载节点的度介于 3 到 13 之间。 随机选择边失效时，由于随机边连接的节点的 负载较小，因此重分布的流量较小，很快被其他节 点吸收，不会导致网络溃散，如图 1。 针对节点的攻击[2,3,5]则主要是攻击高度或高负 载节点，直接破坏网络的核心结构，从而达到破坏 整个网络的目的，而 AM 模式的边攻击并不直接破 坏核心节点。因此，边攻击与节点攻击存在较大的 不同，在相关研究中，要针对不同的情况来考虑。 4 结论 基于流量的攻击行为可能给复杂网络带来灾难 性后果，本文讨论了边失效的情况下，复杂网络的 脆弱特性，得到以下结论：(1)随机边失效对 SF 网 络的影响很小，但攻击极少量重要边将导致 SF 网 络发生连锁的节点过载失效，并最终使网络溃散， 当攻击边数取临界值时，攻击效率最高。(2)SF 网 络的边失效特性表现出网络规模无关性，但与网络 负载水平密切相关。时机策略对边失效特性的影响 随网络负载的降低而增大，大多数情况下，Fot 策 略的边攻击的破坏力最强。(3)SF 网络与其它类型 网络的边攻击特性有较大差异，规则网络表现为脆 性溃散，随机网络对边攻击不敏感。(4)攻击少量边 引起 SF 网络溃散的重要原因在于网络的幂率度分 布。因此，要提高复杂网络的抗攻击能力，需针对 不同的攻击方式和网络脆弱性特点，采取不同的应 对策略。 参 考 文 献 [1] Sole R V, Casals M R, and Bernat C M, et al.. Robustness of the European power grids under intentional attacks[J]. Physical Review E, 2008, E77(2): 1-7. [2] Kurant M and Thiran P. Error and attack tolerance of layered complex networks[J]. Physical Review E, 2007, E76(2): 1-5. [3] Huang Liang, Lai Ying-cheng, and Chen Guan-rong. Understanding and preventing cascading breakdown in complex clustered networks[J]. Physical Review E, 2008, E78(3): 1-5. Zhou Shi and Mondragon R J. Redundancy and robustness of the AS-level Internet topology and its models[J]. IEE Electronic Letters, 2004, 40(2): 151-152. [4] [5] Xia Yong-xiang and Hill D J. Attack vulnerability of complex communication networks [J]. IEEE Transactions on Circuits and Systems- :ⅡExpress Briefs, 2008, 55(1): 65-69. [6] Winick J and Jamin J. Inet-3.0: Internet topology generator[S]. Tech report UM-CSE-TR-456-02, Department of EECS, University of Michigan, 2002. [7] Albert R and Barabasi A L. Statistical mechanics of complex networks[J]. Reviews of Modern Physics, 2002, 74(1): 47-97. 吴 艾： 男，1973 年生，博士生，研究方向为分布式计算和流媒 体系统. 刘心松： 男，1940 年生，教授，博士生导师，研究方向为宽带网 络、分布并行处理. 刘 丹： 男，1969 年生，博士，副教授，研究方向为网络安全与 分布式技术.