中国科技核心期刊      中国指挥与控制学会会刊     军事装备类重点期刊
Command Control and Simulation

Command Control and Simulation >

2021 , Vol. 43 >Issue 3: 1 - 6

DOI: https://doi.org/10.3969/j.issn.1673-3819.2021.03.001

Theory & Research

Complex Network Attack Strategy Based on Binary Particle Swarm Optimization Algorithm

  • YAN kun ,
  • CHEN Chu-xiang ,
  • GUO Xiao-feng
Expand
  • PLA Strategic Support Force Information Engineering University, Zhengzhou, 450001, China

Received date: 2020-12-23

  Revised date: 2021-01-12

  Online published: 2021-06-10

Fold

Abstract

Aiming at the current complex network attack strategy’s insufficient accuracy in selecting the attack node set, and it is difficult to quickly obtain the core node set of the cyberspace battlefield to destroy the enemy’s cyberspace system, an attack strategy based on binary particle swarm algorithm is proposed. In this strategy, firstly the state of the network nodes is encoded, then the fitness function value based on depth-first search is calculated, and the optimal node set is solved by using the binary particle swarm algorithm, finally a simulation experiment is carried out for the typical network models to compare and analyze the performance and adaptability of the binary particle swarm algorithm-based attack strategy and the degree-oriented (betweenness) selective attack strategy, simulation shows that the attack strategy based on binary particle swarm algorithm is efficient, effective and universal, and it can provide assistant decision support for the commander.

Key words： binary particle swarm optimization algorithm; attack strategy; small-world network; Scale-free network; complex network; auxiliary decision-making

Cite this article

YAN kun , CHEN Chu-xiang , GUO Xiao-feng . Complex Network Attack Strategy Based on Binary Particle Swarm Optimization Algorithm[J]. Command Control and Simulation, 2021 , 43(3) : 1 -6 . DOI: 10.3969/j.issn.1673-3819.2021.03.001

网络空间[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)表示剩余网络的最大连通子图阶数,反映剩余网络的连通能力。为考虑网络攻击的代价问题和网络被攻击后的重构难度问题,全面评价网络毁伤度和攻击效果,把复杂网络攻击策略评价函数定义为
F(G)=min | S | + τ ( G - S ) ω ( G - S )

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]。二进制粒子群算法在原理上与标准粒子群优化算法原理相一致,其速度和位置更新公式为:
v i d t + 1=w* v i d t+c1*rand*( p i d t- x i d t)+c2*rand*( g i d t- x i d t)
v i d t + 1 = v m a x , v i d t + 1 > v m a x v i d t + 1 = v m i n , v i d t + 1 < v m i n
x i d t + 1= 1 , S ( v i d t + 1 ) > r a n d 0 , S ( v i d t + 1 ) ≤ r a n d
S( v i d t + 1)=1/(1+exp(- v i d t + 1))
本文将复杂网络攻击策略评价函数(1)定义为二进制粒子群算法的适应度函数。

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

3.1 二进制粒子群向量表示

将网络空间战场抽象映射为网络G,网络中的节点表示实体,节点之间的连边表示实体与实体之间的关系。网络G全部节点(节点数N)的不同状态集合表示二进制粒子群算法中每个粒子的位置向量 X i t=( x i 1 t, x i 2 t,…, x i N t),其中 X i t的第k维 x i k t=1表示t时刻粒子i的第k个节点有效,如果 x i k t=0表示t时刻粒子i的第k个节点失效。每一个粒子代表一种攻击策略解,粒子群代表解空间。在攻击策略计算中,网络G=(V,E)使用邻接矩阵A=(aij)N×N表示,如公式(6)所示,若节点k失效,则将邻接矩阵A的第k行和第k列置0,得到邻接矩阵A'。矩阵A'表示网络被攻击后的邻接矩阵,通过A'可以计算网络的极大连通子图阶数和连通分支数。
aij= 1 , 如 果 i 和 j 之 间 有 连 边 且 i ≠ j 0 , 其 他

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

攻击策略适应度函数牵涉割点集、连通子图数量和最大连通子图阶数三个量的计算,在函数值计算过程中,本文利用Matlab强大的矩阵运算功能,针对每一个粒子采用深度优先搜索的思想计算割点集、连通子图数量和最大连通子图阶数三个数值,进而求解粒子的适应度值F。其算法步骤如表1所示。
表1 基于二进制粒子群算法的攻击策略适应度求解算法
输入:粒子Xi、邻接矩阵A
输出:粒子Xi的适应度函数值
步骤:① 根据t时刻粒子 X i t,对网络的邻接矩阵A进行置零操作得到剩余网络邻接矩阵A';
② 初始化节点访问向量visited和信息记录矩阵MN×N,令k=1;
③ 根据向量visited和矩阵MN×N两个判定条件,依次遍历粒子 X i t 的每一个节点 x i k t,如果 x i k t 未被访问且存在,利用深度优先搜索的思想递归搜索 x i k t 所在连通子图的所有节点,并将 x i k t 所在连通子图的所有节点记录到矩阵MN×N的第k行,令k=k+1;
④ 若k≤N转③,否则循环结束;
⑤ 根据矩阵M的记录结果计算剩余网络的连通分支数ω(G-S)和最大连通子图的阶数τ(G-S),根据适应度函数计算粒子 X i t 的适应度值。

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

基于二进制粒子群的攻击策略在最优节点集的求解过程中,首先对粒子群的速度和位置进行初始化,其次比较并记录个体和群体的最优适应度值,最后利用循环迭代思想逐步计算粒子群的最优适应度函数值,其算法步骤如表2所示。
表2 基于二进制粒子群的攻击策略求解算法
输入:邻接矩阵A、节点访问向量visited、信息记录矩阵M
输出:网络G的最优适应度函数值和最优粒子解
步骤:① 初始化参数w、c1、c2、Vmin、Vmax、进化次数maxgen和种群规模sizepop。
② 随机初始化粒子位置pop(i,j)和速度V(i,j),并计算适应度值fitness(i);
③ 计算适应度函数个体极值fitnessgmin和群体极值fitnesszmin并利用gmin和zmin记录对应粒子;
④ 利用公式(2)和(3)计算粒子第t+1时刻的速度;
⑤ 根据粒子第t+1时刻的速度,更新第t+1时刻粒子的位置;
⑥ 利用基于二进制粒子群算法的攻击策略适应度值算法计算第t+1时刻粒子的适应度函数值;
⑦ 利用第t+1时刻粒子的适应度值更新fitnessgmin、fitnesszmin、gmin和zmin;
⑧ t达到迭代次数算法停止,否则转④。

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 结束语

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

References

Publishing order | Descend order by publishing year | Descend order by cited within
[1]
司光亚, 王艳正. 网络空间作战建模仿真[M]. 北京: 科学出版社, 2019.

[2]
敖志刚. 网络空间作战机理与筹划[M]. 北京: 电子工业出版社, 2018.

[3]
李天梅. 复杂网络的关键节点识别[D]. 西安: 西安科技大学, 2019.

[4]
陈关荣, 汪小帆, 李翔. 复杂网络引论[M]. 北京: 高等教育出版社, 2015.

[5]
Albert R, Jeong H, Barabasi AL. Error and Attack Tolerance of Complex Networks[J]. Nature, 2000, 406(6794): 378-382.

DOI

[6]
Holme P, Kim B J, Yoon C N, et al. Attack Vulnerability of Complex Networks[J]. Physical Review E Statistical Nonlinear & Soft Matter Physics, 2002, 65(5):056109.

[7]
YIN Yan-Ping, ZHANG Duan-Ming, TAN Jin, PAN Gui-Jun, HE Min-Hua. Multiple Partial Attacks on Complex Networks[J]. Chinese Physics Letters, 2008, 25(2):769-772.

DOI

[8]
郝耀辉. 新型攻击策略下的复杂网络结构脆弱性研究[D]. 郑州: 信息工程大学, 2016.

[9]
王尔申, 王玉伟, 曲萍萍, 等. 基于代价的复杂网络边攻击策略有效性分析[J]. 系统工程与电子技术, 2018, 40(4):919-926.

[10]
陈盼, 吴晓锋, 李怡, 等. 局部信息条件下复杂网络的攻击策略[J]. 计算机应用研究, 2010, 27(12): 4622-4623.

[11]
王建伟, 荣莉莉. 面向相继故障的复杂网络上边袭击策略研究[J]. 系统工程学报, 2011, 26(1):1-8.

[12]
赵志刚, 周根贵, 李虎雄. 复杂加权供应链网络攻击策略和鲁棒性研究[J]. 计算机科学, 2019, 46(8):138-144.

[13]
王玥, 蔡皖东, 段琪. 基于遗传算法的网络脆弱性计算方法[J]. 系统仿真学报, 2009, 21(6):1628-1632.

[14]
王志平, 任光. 一种研究通信网络容错性的新参数--点韧性度的理论综述[J]. 数学进展, 2003, 32(6):641-652.

[15]
K.S. Bagga, L.W. Beineke, W.D. Goddard, M.J. Lipman, R.E. Pippert. A Survey of Integrity[J]. Discrete Applied Mathematics, 1992, 37(7): 13-28.

[16]
L H Clark, R C Entringer, M R Fellows. Computational Complexity of Integrity[J]. Journal of Combinatorial Mathematics and Combinatorial Computing, 1987, 2(2):179-191.

[17]
罗金炎. 改进的二进制粒子群算法求解车辆路径问题[J]. 数学的实践与认识, 2014, 44(23):205-211.

[18]
张长胜, 孙吉贵, 欧阳丹彤. 一种自适应离散粒子群算法及其应用研究[J]. 电子学报, 2009, 37(2):299-304.

[19]
王志刚, 夏慧明, 王明刚, 等. 求解多维背包问题的改进二进制粒子群算法[J]. 数学的实践与认识, 2013, 43(19):129-137.

[20]
Kennedy J, Eberhart R. Particles Warm Optimization[A]//Proceedings of IEEE Conference on Neural Networks[C]// Perth,Australia, 1995, 4:1942-1948.

[21]
Kennedy J, Eberhart R. A Discrete Binary Version of the Particle Swarm Algorithm[C]// Proceedings of 1997 IEEE International Conference on Systems, Man and Cybernetics, 1997, 5:4104-4108.

[22]
DJ Watts, SH Strogatz. Collective Dynamics of ‘Small-world’ Networks[J]. Nature, 1998, 393 (6684):440-442.

DOI

[23]
汪小帆, 李翔, 陈关荣. 网络科学导论[M]. 北京: 高等教育出版社, 2018

[24]
Barabási AL, Albert R. Emergence of Scaling in Random Networks[J]. Science, 1999, 286 (5439):509-512.

DOI

[25]
邓烨. 复杂网络最优攻击策略研究[D]. 长沙: 国防科学技术大学, 2015.

Options
Outlines

/

〈 〉