基于二进制粒子群的复杂网络攻击策略

闫 坤，陈楚湘，郭晓峰

(战略支援部队信息工程大学,河南 郑州 450001)

网络空间[1-2]是指由国家关键基础设施网络、军用信息网络以及它们所承载的信息构成的信息活动空间。夺取网络空间制网权,首先对敌方网络进行攻击,直接毁瘫其作战体系。然而网络空间互联程度高,作战节奏快,网络系统不同节点价值迥异,怎样在海量节点中快速精确求解关键节点集进行网络攻击[3],直接关系到网络空间作战攻击效果和战争的胜负。基于网络空间的复杂性和虚拟性[4],本文采用复杂网络原理研究网络空间问题。

在复杂网络攻击策略研究领域,国内外学者进行了相关研究。Albert等[5]最早针对无标度网络进行了分析,提出了随机攻击和蓄意攻击的复杂网络攻击策略;Holme等[6]在Albert等人研究的基础上总结分析了各类网络瓦解策略,提出了基于初始图的面向度选择性攻击策略、基于当前图的面向度的选择性攻击策略、基于初始图的面向介数选择性攻击策略和基于当前图的面向介数选择性攻击策略;殷艳萍等[7]考虑真实网络连边实际意义,提出了一种基于连边权重的攻击策略;郝耀辉[8]依据网络攻击的特点和规律,提出了树形攻击策略、近似最长路径攻击策略、最短路径攻击策略和邻居节点攻击策略,分析了八种真实网络在四种不同攻击策略下的攻击效果;王尔申等[9]针对已有复杂网络攻击策略中未考虑攻击代价的问题,提出了基于代价的复杂网络边攻击策略;陈盼等[10]构建了一种基于局部拓扑结构已知的复杂网络攻击模型,提出了基于局部信息的复杂网络攻击策略;王建伟等[11]采用级联失效的思想,提出了以降序方式删除权值最大的边和以升序方式删除权值最小的边的攻击策略;赵志刚等[12]构建了加权供应链网络模型,分析了基于节点删除和边删除的九种攻击策略。

上述复杂网络攻击策略的研究主要围绕节点度、节点介数、边权值、最短路径和最大连通子图等方法展开,这些方法仅仅针对网络的某一属性特征评价攻击效果的优劣,没有考虑网络攻击的整体难易程度和剩余网络的连通能力,且无法实现攻击策略的自动寻优和自主决策。为解决上述问题,本文基于网络脆弱性中韧性度的概念[13],提出一种基于二进制粒子群算法的攻击策略,该策略能够高效、精确、自主、最优地选择出攻击节点集,能够有效帮助战场指挥员高效精准获取网络攻击态势信息,为指挥员作战指挥提供辅助决策支撑。

1 复杂网络攻击策略

1.1 复杂网络攻击策略评价函数

网络空间一般被抽象为一个由节点集V和边集E表示的网络G=(V,E),其中，节点数N=|V|,边数M=|E|。在网络空间攻击效果的评价指标上,采用韧性度三元组[14]进行描述:{S,ω(G-S),τ(G-S)}。其中,S是割点集,反映网络攻击的代价或攻击强度;G-S表示剩余网络;ω(G-S)表示剩余网络的连通分支总数,反映剩余网络的毁瘫程度;τ(G-S)表示剩余网络的最大连通子图阶数,反映剩余网络的连通能力。为考虑网络攻击的代价问题和网络被攻击后的重构难度问题,全面评价网络毁伤度和攻击效果,把复杂网络攻击策略评价函数定义为

(1)

1.2 复杂网络攻击策略计算

在复杂网络攻击策略研究中,因为太大的割点集|S|对攻击者意味着较大的攻击代价且易被对方反追踪而丧失一种攻击手段和策略,而较小的攻击代价又未必能达成预定的攻击效果。因此,网络空间攻击者希望找到一种高效费比的攻击策略,使得对于一定的|S|能够实现较大的ω(G-S)和较小的τ(G-S)。复杂网络攻击策略评价函数定义(1)的计算已经被K.S.Bagga和L.W.Beineke证明是不存在多项式时间的NP完备问题[15-16],只能通过暴力搜索实现函数最小值的求解,这严重影响了复杂网络攻击策略的求解时间,无法满足网络空间作战的实时性要求。

二进制粒子群算法在车辆路径问题[17]、车间调度[18]、背包问题[19]中已经被证明是一种有效的优化算法。算法速度公式中对粒子个体速度、粒子历史速度和粒子全局最优速度进行了综合考虑。在寻优过程中,每个粒子不仅记忆对自己空间搜索的认知,而且还考虑粒子群整体的认知结果,是一种全面的搜索求解算法。二进制粒子群算法不需遍历节点集的所有组合,而是在粒子群上自动搜索割点集的最优解,在时间效率和自主寻优方面具有显著优势。

2 二进制粒子群算法原理

标准粒子群优化(Particle Swarm Optimization,PSO)算法是1995年由Kennedy和Eberhart通过模拟鸟群觅食中的迁徙和群聚行为而提出的一种基于群体的全局搜索算法[20]。其基本原理是在粒子群空间中迭代计算粒子速度和位置,使其逐步逼近适应度函数的最优解。粒子群算法最初是在实值连续空间进行迭代搜索,然而许多现实问题是离散形式的组合优化问题,因此,Kennedy和Eberhart在粒子群算法的基础上提出了二进制粒子群算法(Binary Particle Swarm Optimization,DPSO)[21]。二进制粒子群算法在原理上与标准粒子群优化算法原理相一致,其速度和位置更新公式为:

(2)

(3)

(4)

(5)

本文将复杂网络攻击策略评价函数(1)定义为二进制粒子群算法的适应度函数。

3 基于二进制粒子群算法的攻击策略

3.1 二进制粒子群向量表示

(6)

3.2 基于二进制粒子群算法的攻击策略适应度求解算法

攻击策略适应度函数牵涉割点集、连通子图数量和最大连通子图阶数三个量的计算,在函数值计算过程中,本文利用Matlab强大的矩阵运算功能,针对每一个粒子采用深度优先搜索的思想计算割点集、连通子图数量和最大连通子图阶数三个数值,进而求解粒子的适应度值F。其算法步骤如表1所示。

表1 基于二进制粒子群算法的攻击策略适应度求解算法

3.3 基于二进制粒子群的攻击策略求解算法

基于二进制粒子群的攻击策略在最优节点集的求解过程中,首先对粒子群的速度和位置进行初始化,其次比较并记录个体和群体的最优适应度值,最后利用循环迭代思想逐步计算粒子群的最优适应度函数值,其算法步骤如表2所示。

表2 基于二进制粒子群的攻击策略求解算法

4 仿真分析

为验证本文所提攻击策略的高效性、精确性和自动择优性,本文采用Holme[6]等提出的面向度的选择性攻击策略和面向介数的选择性攻击策略进行对比分析。为使攻击策略分析更具一般性,本文采用WS小世界网络[22]和BA无标度网络[23-24]两种网络模型,WS小世界网络随机初始化为30个节点,每个节点有4个邻居,以概率0.3随机化重连边;BA无标度网络随机初始化为30个节点,每次加入2条边。利用Networkx随机生成网络如图1和图2所示。图1中共30个节点,60条边;图2中共30个节点,56条边。

图1 WS小世界网络

图2 BA无标度网络

4.1 时间复杂度对比

从基于二进制粒子群算法的攻击策略算法中可以得出算法的时间复杂度为O(N2),而面向度的选择性攻击策略算法和面向介数的选择性攻击策略算法的时间复杂度为O(2N),从图3可以看出,当N>1010时,在时间复杂性方面,基于二进制粒子群的攻击策略显著优于面向度的选择性攻击策略和面向介数的选择性攻击策略。在图1中基于二进制粒子群算法的攻击策略在迭代20 000次后求得最优适应度值1.3077,对应割点集为{v0、v1、v4、v6、v7、v10、v12、v13、v15、v18、v19、v20、v24、v25、v27};在图2中基于二进制粒子群算法的攻击策略在迭代20 000次后即可求得最优适应度值0.6667,对应割点集为{v0、v1、v3、v4、v5、v6、v8、v10、v12、v23}。求解结果与图1和图2实际情况相吻合。

图3 时间复杂度对比

为对比分析基于二进制粒子群的攻击策略和面向度(介数)的选择性攻击策略的时间复杂性,本文采用暴力搜索的思想,即攻击节点集合为网络所有可能失效节点的组合,因此，失效节点组合共230=1 073 741 824个,程序运行时间为50次的算术平均值。针对WS小世界网络,迭代20 000次后,基于二进制粒子群的攻击策略用时约100 s,面向度的选择性攻击策略用时约300 000 s,面向介数的选择性攻击策略用时约300 000 s。针对BA无标度网络,迭代20 000次后,基于二进制粒子群的攻击策略用时约110 s,面向度的选择性攻击策略用时约300 000 s,面向介数的选择性攻击策略用时约300 000 s。从以上数据分析可知,图1和图2在节点数相同而拓扑结构不同时,基于二进制粒子群的攻击策略的计算时间几乎是相同的,而面向度的选择性攻击策略和面向介数的选择性攻击策略在暴力搜索的情况下平均用时是基于二进制粒子群的攻击策略所用时间的3000倍,在时效性要求很强的网络对抗中必然贻误战机。综上,对于典型网络拓扑结构(如WS小世界网络和BA无标度网络),基于二进制粒子群的攻击策略在时间复杂性方面要远远优于面向度(介数)的选择性攻击策略,是一种高效率的攻击策略。

4.2 适应度函数值对比

为验证本文所提攻击策略的精确性和自动择优性,本文采用面向度(介数)的降序选择性攻击策略与基于二进制粒子群的攻击策略进行对比,求解适应度值如图4和图5所示。

图4 WS小世界网络攻击策略对比

图5 BA无标度网络攻击策略对比

图4中,横坐标表示割点集的数量,在割点数量一定的情况下,割点集按照图3节点度值或介数值降序的方式选择,纵坐标表示割点集对应的适应度函数值。从图中可以看出,随着攻击强度变大,适应度函数值先减少后增加,这是因为开始阶段随着攻击强度的增加,连通分支数变大,而最大连通子图阶数变小,适应度函数值逐渐变小,攻击效果逐渐增强;后期随着失效节点增多而适应度值变大是因为失效节点数量变大而连通分支数和最大连通子图阶数同时变小,攻击效果逐渐减弱。面向度的选择性攻击在割点数为11时搜索到最小适应度值1.778;面向介数的选择性攻击在割点数为16时搜索到最小适应度值1.8;基于二进制粒子群算法的攻击无须遍历节点集,可直接迭代搜索出最优适应度值1.307 7,割点数为15,是一种自动择优的攻击策略。面向度的选择性攻击策略和面向介数的选择性攻击策略是两条曲线而基于二进制粒子群的攻击策略是一个孤立点。从上述分析可知,针对WS小世界网络,三种攻击策略的优劣顺序为:基于二进制粒子群的攻击策略≻面向度的选择性攻击策略≻面向介数的选择性攻击策略。

同样在图5中,面向度的选择性攻击在割点数为11时,搜索到最小适应度值0.764 7;面向介数的选择性攻击在割点数为11时搜索到最小适应度值0.764 7;基于二进制粒子群算法的攻击不需遍历节点集直接迭代搜索出最优适应度值0.666 7,割点数为10。从上述分析可知,针对BA无标度网络,三种攻击策略的优劣顺序为:基于二进制粒子群的攻击策略≻面向度的选择性攻击策略=面向介数的选择性攻击策略。

图6、图7和图8分别是三种攻击策略下WS小世界网络和BA无标度网络适应度值的对比图。在三种攻击策略下BA无标度网络均比WS小世界网络更易被毁瘫,这是因为在节点数量和边数量相近的情况下,BA无标度网络存在“富人俱乐部现象”[25],一些节点为“HUB”节点和“桥”节点,而WS小世界网络是一种均匀网络,度分布呈“钟型”分布。这一点与Albert[5]等人对无标度网络瓦解问题的分析相一致,从而间接证明了基于二进制粒子群算法的攻击策略的有效性。

图6 面向度的选择性攻击策略

图7 面向介数的选择性攻击策略

图8 基于二进制粒子群算法的攻击策略

5 结束语

基于二进制粒子群算法的攻击策略是依据粒子自身和全局最优解在粒子群中快速逼近最优解的一种攻击策略。在时间复杂度方面,该策略在粒子群上进行搜索而不是在节点集上进行搜索,提高了策略求解的时间效率;在适应度值求解方面,该策略利用优化算法自动求出最优解而不是程式化比较寻优;在应用性空间方面,该策略在多类网络模型上都能适用且有效,具有一定普适性。在网络空间作战中,本文提出的攻击策略能够快速、精准、自动地计算战场网络的最优毁伤效果节点集,为指挥决策者制定攻击行动和作战方案提供精确、自主、高效的辅助决策支撑。