以互联网、电信网和电网为代表的重要网络经常会受到来自外部的蓄意攻击，导致其拓扑结构被破坏，网络功能损失，危害社会稳定，带来不可估量的经济损失.因此，采用异常检测方法及时检测到网络异常具有重要的研究意义和价值.

目前，对网络的异常检测方法主要归纳为4类:基于分解、基于社团或聚类、基于时序窗及基于特征.

基于分解方法，Ishibashi等^[1]采用个体间至其目的主机的重叠情况代替主机间的简单关联来生成邻接矩阵并分解处理来实现异常检测；Koutra等^[2]和Papalexakis等^[3]采用张量分解，将时序及其他额外特征与邻接矩阵结合形成新的张量并分解来实现异常检测.基于社团或聚类方法，Heard等^[4]提出两步贝叶斯方法，通过计算基于贝叶斯学习的p-value来判断现存与消亡的边是否异常.基于时序窗口方法，Peel等^[5]提出一种选取固定长度的滑动窗口，进行广义似然比检验，判断对已有固定模型是否有改变.以上方法基于统计学手段，在反映、描述异常演化的现象上略有欠缺，此外，有的方法^[1-4]计算复杂度较高, 有的方法^[5]受网络类型的限制.

着眼于前三类方法的问题，基于特征方法研究更为深入，且更多关注于图拓扑数据而不是流数据^[6]，包括统计临近图的最大公共子图MCS(maximum common subgraph)方法^[7].统计相邻时刻图编辑距离GED(graph edit distance)^[8]，来量化图的相似程度，若超出阈值则异常. Koutra等^[9]提出Deltacon方法，采用对比一系列图快照的节点亲缘关系，可进行非连续的异常检测.近似地，在基于特征方法中，通常需要较多时序下的数据作为参考，并更多关注于局部特征，为此本文提出一种面向蓄意攻击的异常检测方法，捕捉了异常现象背后真实全局拓扑的变动，并参考全局特征，旨在把参考样本数目降低.

1 异常演化与拓扑变动特征分析 1.1 模型描述

一个复杂网络g=(V, E)，sp(v, u)表示复杂网络中由v到u的一条最短路径，在无权网络中为两个节点最短路径跳数，或者有权网络中边或节点权重最小的路径.其中V, E分别代表网络g的节点集和边集，节点v的传输性能为

(1)

(2)

式中:N(v)为节点v的邻居节点集合；d(v)为某节点对传输性能的最差情况值；p(v)为v到其他节点的平均情况值.

复杂网络g=(V, E)的最大直径:

(3)

复杂网络g的有效直径

(4)

式中: 为节点对总数:为大于等于0.9n的最小整数.

复杂网络g的平均最短路径:

(5)

从各参数的物理意义来看，D_max描述了所有网络连通节点对的最大距离均值，是最差传输性能的描述量，而D_eff是使得网络中至少90%的连通节点对可以互相到达的最小距离，通常比D_max更具有鲁棒性.SP是所有连通节点对最短距离的均值，是最好传输性能的描述量.

1.2 蓄意攻击

以互联网为代表的真实复杂网络大多具有“无标度性”，这决定了它们对随机故障的高鲁棒性及蓄意攻击的脆弱性^[10].蓄意攻击就是对网络中特定中心性节点攻击并使相关节点与链路失效，因此极小程度的蓄意攻击就会导致网络拓扑结构发生较大变动，导致原有的流传输路径或连通路径发生改变，引发相关最优传输路径增长甚至不可达.

这种异常演化会打破原有的网络传输平衡，增加局部节点的传输负载，导致更多节点的链路故障，由此引发网络级联故障，网络传输性能发生非线性变化^[11-12].因此，可以通过量化传输路径的变化，表达网络全局拓扑层面的变动，此度量有助于实现对网络蓄意攻击的异常检测.

1.3 异常演化分析

蓄意攻击引发的网络异常通常伴随着网络特征的显著波动^[13].为进一步观察和验证蓄意攻击导致最优传输路径变动并造成结构突变的现象，通过节点删除法，以节点介数优先为策略，仿真BA网络受蓄意攻击过程.

对具有5 000节点的BA网络进行10次观测.主要关注反映网络连通性能的D_max, D_eff, SP三个特征在蓄意攻击过程中的波动.

蓄意攻击下BA网络特征波动情况如图 1所示，最大子团节点数和边数在5.95%(A线)左右处产生突变；而D_max, D_eff, SP则先急剧变大，然后迅速减小，在5.95%的相关中心节点遭攻击失效时突变，达到极大值.

复杂网络在正常演化时拓扑结构及各特征值相对稳定，通过中心性节点的传输路径不会发生较大变动.当网络受到蓄意攻击时，最先导致高介数节点陆续失效，部分节点对最优传输路径发生改变，D_max, D_eff, SP逐渐上升，传输性能下降.随着蓄意攻击程度逐渐加深，中心性节点与链路的失效对网络结构的影响逐步累积，由量变产生质变，引起拓扑结构崩塌^[14]，此时各特征上升至极值.随着极大子团崩塌形成新的规模较小的极大子团，特征值也随之下降.

因此，各特征值在蓄意攻击导致网络异常产生时通常会达到极值，具有明显波动特征.

2 面向蓄意攻击的异常检测算法 2.1 网络路径相对变化系数

网络的D_max, D_eff, SP特征变化趋势相似，但峰值差异大且D_max较D_eff更敏感，SP次之，三者变化速率与变化范围均不同.

以上特征量定义结合1.1节可知，D_max≥D_eff≥SP，故通过不等式转换得到

(6)

因此，本文设计了能够量化复杂网络结构动态性的指标——网络路径相对变化系数(network path changing coefficient, NPCC)r:

(7)

在正常演化过程中，r会较为平缓；在异常产生时，r会发生明显向下波动，偏离正常演化下的稳态.

2.2 斐波那契演化域

复杂网络作为一个动态系统是不断演化的，r也是实时波动的，因此各时刻正常域也应及时动态调整.本文基于斐波那契数列衍生出斐波那契演化域，旨在对正常和异常演化波动更好地进行区分.首先提出斐波那契演化域:对于任意时序上的拓扑结构度量参数M，记m_i(i∈{1, 2, …, n})为M在时间单元t_i的值.

(8)

式中:R_i(m_i)为m_i的邻域；∈_i为随机变量.

记R_i+R_j=R_i∪R_j，∀i, j∈{1, 2, …, n}，构造域构成的序列:

(9)

则F_i(m_i)为斐波那契演化域序列，i∈{1, 2, …, n}.

基于斐波那契演化域序列的定义，某时刻是否为异常取决于前两个时序值和随机变量∈_i.随机变量∈_i描述的是网络固有的特性及检测算法的敏感性，对网络常态进行观察与统计，得到网络r指标的标准差，再根据检测的敏感性需求进行适当调整，以获得网络近期的随机变量.

2.3 异常检测算法

将r作为核心度量参量，结合斐波那契演化域，构建网络演化的正常域，此方法从真实拓扑结构变动的角度来检测由蓄意攻击产生的网络异常.

给出前两个时刻网络的r值及常态下的∈_i值，就可以对当前网络状态进行异常检测.算法1为异常检测算法.

算法1  网络异常检测算法

输入:正常态前i-1时刻r指标值{…m_i-2, m_i-1}；

该网络正常态下∈_i值；

i时刻待检测网络指标值m_i

输出:该时刻内是否有异常产生y

过程:R_i-2(m_i-2)=[m_i-2-∈_i, m_i-2+1]

        R_i-1(m_i-1)=[m_i-1-∈_i, m_i-1+1]

        F_i(m_i)=R_i-1(m_i-1)∪R_i-2(m_i-2)

        If m_i∈F_i(m_i), y=0

        else y=1

        End If

首先获得i-2与i-1时刻邻域为R_i-2(m_i-2)与R_i-1(m_i-1)，得出i时刻r指标值正常域F_i(m_i)；由于r的向下突变反映网络产生异常，若待检测网络m_i值不属于i时刻正常域，输出为y=1，则算法判断异常产生.

将前两个时刻的正常态作为参考，降低了误判，其中的核心度量参量也可以在未来的工作中进行改进；其次，若想增加时序上的关联性，可以考虑将前k项作为参考，此算法具有一定扩展性.

3 实验结果及分析

采用节点删除法模拟蓄意攻击，验证r指标的量化有效性；将MCS^[7], GED^[8]作为异常检测对比方法，验证本方法的准确性.实验网络为因特网AS级拓扑(AS Internet)、互联网路由级拓扑(computer route view)^[15]、美国电网(power grid).网络相关拓扑参数如表 1所示.

3.1 r有效性分析

采用节点删除法，验证r指标分别在节点度或介数优先的策略下的量化情况.将D_max, D_eff, SP达到极大值时定义为网络异常产生并给出标识，r₀为初始值.

蓄意攻击后网络的r值变化如图 2所示，网络的r值在蓄意攻击过程中呈现先上升再下降的趋势，并且在异常产生时呈现出大幅下降的特征，符合对网络结构动态性变化的分析.

在图 2a中，介数优先策略下，柱形图最高时未对应异常产生，但前一时刻r的波动程度已足够检测出异常.在图 2b~2d中，柱形图最高处均对应着异常产生，说明r的波动情况在异常时刻具有显著特征.

可以看出r指标对不同类型网络进行实验时，均能很好地描述异常带来的拓扑结构损失及所引发的连通路径变化，并且在拓扑损失累积达到质变时也能表现出显著的特征，验证了r指标的有效性，为异常检测算法提供了有效的度量参量.

3.2 异常检测算法准确率分析

采用节点介数优先策略模拟蓄意攻击，PFP模型构造网络正常演化，随机产生不同程度的攻击，将MCS，GED方法与本方法进行对比.每个网络模拟10次，单次时序范围100个时间序列，评价指标采用准确率(Acc)、精确率(Pre):

(10)

式中:FP为假的正样本；FN为假的负样本；TP为检测正确的正样本；TN为检测正确的负样本.

为方便仿真的进行，网络每次遭受攻击后会恢复至最近时刻的正常网络情形；随机变量∈_i的选择为测试数据中正常波动的标准差.

As-rel异常检测核心度量参数变化如图 3所示.在图 3a~3c中，MCS，GED检测方法均出现较多突变，而r值在正常演化中波动较小.在图 3d, 3e中，给出了方法在不同阈值下的准确率、精确率的变化情况.

由图 3可知，异常产生实际为2, 6, 7, 16, 24等时间序列，轻微扰动为9, 21, 26, 43等时间序列，可以看出GED，MCS方法在轻微扰动下，例如9时间序列，波动接近甚至超过实际异常产生时刻，其他正常时刻波动也较大；而r值只是产生轻微向上变化，说明该方法可以更好地刻画异常的产生.GED与MCS方法由于始终比较当前时刻与前一时刻的“网络相似度”，前者比较的是节点与边的增删，后者是统计最大公共子图的规模，而正常演化包含很多节点与边的新生与消亡，因此较难区分出异常.通过图 3d, 3e可以找到较好的准确率与精确率，将其与本文方法的结果进行比较，具体实验统计结果如表 2所示.

实验结果表明，在∈选择适当的情况下，本文检测方法对不同数据集的检测平均准确率约为90%，精确率最高约为80%；而GED，MCS两种对比方法准确率和精确率远低于本文方法.某些蓄意攻击有可能被检测方法忽略，是异常检测算法中斐波那契演化域形成机理导致的，但本文只关注第一个异常的产生.综上，本文构造的异常检测方法在不同类型的数据集上均能表现出良好的有效性，优秀的准确率.

4 结论

1) 分析了网络受蓄意攻击引发异常的现象，提出了在异常演化现象中具有显著特征的r指标，以此为基础，将斐波那契演化域与r结合，区分正常与异常演化，构造了面向蓄意攻击的异常检测方法.

2) 实验结果表明，r有效地描述了网络面向蓄意攻击过程中发生的变化，且异常检测方法针对不同类型真实数据集平均准确率达90%，能较为准确地判断网络是否发生异常演化.