基于二進(jìn)制粒子群的復(fù)雜網(wǎng)絡(luò)攻擊策略

閆 坤，陳楚湘，郭曉峰

(戰(zhàn)略支援部隊(duì)信息工程大學(xué),河南 鄭州 450001)

網(wǎng)絡(luò)空間[1-2]是指由國家關(guān)鍵基礎(chǔ)設(shè)施網(wǎng)絡(luò)、軍用信息網(wǎng)絡(luò)以及它們所承載的信息構(gòu)成的信息活動空間。奪取網(wǎng)絡(luò)空間制網(wǎng)權(quán),首先對敵方網(wǎng)絡(luò)進(jìn)行攻擊,直接毀癱其作戰(zhàn)體系。然而網(wǎng)絡(luò)空間互聯(lián)程度高,作戰(zhàn)節(jié)奏快,網(wǎng)絡(luò)系統(tǒng)不同節(jié)點(diǎn)價值迥異,怎樣在海量節(jié)點(diǎn)中快速精確求解關(guān)鍵節(jié)點(diǎn)集進(jìn)行網(wǎng)絡(luò)攻擊[3],直接關(guān)系到網(wǎng)絡(luò)空間作戰(zhàn)攻擊效果和戰(zhàn)爭的勝負(fù)。基于網(wǎng)絡(luò)空間的復(fù)雜性和虛擬性[4],本文采用復(fù)雜網(wǎng)絡(luò)原理研究網(wǎng)絡(luò)空間問題。

在復(fù)雜網(wǎng)絡(luò)攻擊策略研究領(lǐng)域,國內(nèi)外學(xué)者進(jìn)行了相關(guān)研究。Albert等[5]最早針對無標(biāo)度網(wǎng)絡(luò)進(jìn)行了分析,提出了隨機(jī)攻擊和蓄意攻擊的復(fù)雜網(wǎng)絡(luò)攻擊策略;Holme等[6]在Albert等人研究的基礎(chǔ)上總結(jié)分析了各類網(wǎng)絡(luò)瓦解策略,提出了基于初始圖的面向度選擇性攻擊策略、基于當(dāng)前圖的面向度的選擇性攻擊策略、基于初始圖的面向介數(shù)選擇性攻擊策略和基于當(dāng)前圖的面向介數(shù)選擇性攻擊策略;殷艷萍等[7]考慮真實(shí)網(wǎng)絡(luò)連邊實(shí)際意義,提出了一種基于連邊權(quán)重的攻擊策略;郝耀輝[8]依據(jù)網(wǎng)絡(luò)攻擊的特點(diǎn)和規(guī)律,提出了樹形攻擊策略、近似最長路徑攻擊策略、最短路徑攻擊策略和鄰居節(jié)點(diǎn)攻擊策略,分析了八種真實(shí)網(wǎng)絡(luò)在四種不同攻擊策略下的攻擊效果;王爾申等[9]針對已有復(fù)雜網(wǎng)絡(luò)攻擊策略中未考慮攻擊代價的問題,提出了基于代價的復(fù)雜網(wǎng)絡(luò)邊攻擊策略;陳盼等[10]構(gòu)建了一種基于局部拓?fù)浣Y(jié)構(gòu)已知的復(fù)雜網(wǎng)絡(luò)攻擊模型,提出了基于局部信息的復(fù)雜網(wǎng)絡(luò)攻擊策略;王建偉等[11]采用級聯(lián)失效的思想,提出了以降序方式刪除權(quán)值最大的邊和以升序方式刪除權(quán)值最小的邊的攻擊策略;趙志剛等[12]構(gòu)建了加權(quán)供應(yīng)鏈網(wǎng)絡(luò)模型,分析了基于節(jié)點(diǎn)刪除和邊刪除的九種攻擊策略。

上述復(fù)雜網(wǎng)絡(luò)攻擊策略的研究主要圍繞節(jié)點(diǎn)度、節(jié)點(diǎn)介數(shù)、邊權(quán)值、最短路徑和最大連通子圖等方法展開,這些方法僅僅針對網(wǎng)絡(luò)的某一屬性特征評價攻擊效果的優(yōu)劣,沒有考慮網(wǎng)絡(luò)攻擊的整體難易程度和剩余網(wǎng)絡(luò)的連通能力,且無法實(shí)現(xiàn)攻擊策略的自動尋優(yōu)和自主決策。為解決上述問題,本文基于網(wǎng)絡(luò)脆弱性中韌性度的概念[13],提出一種基于二進(jìn)制粒子群算法的攻擊策略,該策略能夠高效、精確、自主、最優(yōu)地選擇出攻擊節(jié)點(diǎn)集,能夠有效幫助戰(zhàn)場指揮員高效精準(zhǔn)獲取網(wǎng)絡(luò)攻擊態(tài)勢信息,為指揮員作戰(zhàn)指揮提供輔助決策支撐。

1 復(fù)雜網(wǎng)絡(luò)攻擊策略

1.1 復(fù)雜網(wǎng)絡(luò)攻擊策略評價函數(shù)

網(wǎng)絡(luò)空間一般被抽象為一個由節(jié)點(diǎn)集V和邊集E表示的網(wǎng)絡(luò)G=(V,E),其中，節(jié)點(diǎn)數(shù)N=|V|,邊數(shù)M=|E|。在網(wǎng)絡(luò)空間攻擊效果的評價指標(biāo)上,采用韌性度三元組[14]進(jìn)行描述:{S,ω(G-S),τ(G-S)}。其中,S是割點(diǎn)集,反映網(wǎng)絡(luò)攻擊的代價或攻擊強(qiáng)度;G-S表示剩余網(wǎng)絡(luò);ω(G-S)表示剩余網(wǎng)絡(luò)的連通分支總數(shù),反映剩余網(wǎng)絡(luò)的毀癱程度;τ(G-S)表示剩余網(wǎng)絡(luò)的最大連通子圖階數(shù),反映剩余網(wǎng)絡(luò)的連通能力。為考慮網(wǎng)絡(luò)攻擊的代價問題和網(wǎng)絡(luò)被攻擊后的重構(gòu)難度問題,全面評價網(wǎng)絡(luò)毀傷度和攻擊效果,把復(fù)雜網(wǎng)絡(luò)攻擊策略評價函數(shù)定義為

(1)

1.2 復(fù)雜網(wǎng)絡(luò)攻擊策略計(jì)算

在復(fù)雜網(wǎng)絡(luò)攻擊策略研究中,因?yàn)樘蟮母铧c(diǎn)集|S|對攻擊者意味著較大的攻擊代價且易被對方反追蹤而喪失一種攻擊手段和策略,而較小的攻擊代價又未必能達(dá)成預(yù)定的攻擊效果。因此,網(wǎng)絡(luò)空間攻擊者希望找到一種高效費(fèi)比的攻擊策略,使得對于一定的|S|能夠?qū)崿F(xiàn)較大的ω(G-S)和較小的τ(G-S)。復(fù)雜網(wǎng)絡(luò)攻擊策略評價函數(shù)定義(1)的計(jì)算已經(jīng)被K.S.Bagga和L.W.Beineke證明是不存在多項(xiàng)式時間的NP完備問題[15-16],只能通過暴力搜索實(shí)現(xiàn)函數(shù)最小值的求解,這嚴(yán)重影響了復(fù)雜網(wǎng)絡(luò)攻擊策略的求解時間,無法滿足網(wǎng)絡(luò)空間作戰(zhàn)的實(shí)時性要求。

二進(jìn)制粒子群算法在車輛路徑問題[17]、車間調(diào)度[18]、背包問題[19]中已經(jīng)被證明是一種有效的優(yōu)化算法。算法速度公式中對粒子個體速度、粒子歷史速度和粒子全局最優(yōu)速度進(jìn)行了綜合考慮。在尋優(yōu)過程中,每個粒子不僅記憶對自己空間搜索的認(rèn)知,而且還考慮粒子群整體的認(rèn)知結(jié)果,是一種全面的搜索求解算法。二進(jìn)制粒子群算法不需遍歷節(jié)點(diǎn)集的所有組合,而是在粒子群上自動搜索割點(diǎn)集的最優(yōu)解,在時間效率和自主尋優(yōu)方面具有顯著優(yōu)勢。

2 二進(jìn)制粒子群算法原理

標(biāo)準(zhǔn)粒子群優(yōu)化(Particle Swarm Optimization,PSO)算法是1995年由Kennedy和Eberhart通過模擬鳥群覓食中的遷徙和群聚行為而提出的一種基于群體的全局搜索算法[20]。其基本原理是在粒子群空間中迭代計(jì)算粒子速度和位置,使其逐步逼近適應(yīng)度函數(shù)的最優(yōu)解。粒子群算法最初是在實(shí)值連續(xù)空間進(jìn)行迭代搜索,然而許多現(xiàn)實(shí)問題是離散形式的組合優(yōu)化問題,因此,Kennedy和Eberhart在粒子群算法的基礎(chǔ)上提出了二進(jìn)制粒子群算法(Binary Particle Swarm Optimization,DPSO)[21]。二進(jìn)制粒子群算法在原理上與標(biāo)準(zhǔn)粒子群優(yōu)化算法原理相一致,其速度和位置更新公式為:

(2)

(3)

(4)

(5)

本文將復(fù)雜網(wǎng)絡(luò)攻擊策略評價函數(shù)(1)定義為二進(jìn)制粒子群算法的適應(yīng)度函數(shù)。

3 基于二進(jìn)制粒子群算法的攻擊策略

3.1 二進(jìn)制粒子群向量表示

(6)

3.2 基于二進(jìn)制粒子群算法的攻擊策略適應(yīng)度求解算法

攻擊策略適應(yīng)度函數(shù)牽涉割點(diǎn)集、連通子圖數(shù)量和最大連通子圖階數(shù)三個量的計(jì)算,在函數(shù)值計(jì)算過程中,本文利用Matlab強(qiáng)大的矩陣運(yùn)算功能,針對每一個粒子采用深度優(yōu)先搜索的思想計(jì)算割點(diǎn)集、連通子圖數(shù)量和最大連通子圖階數(shù)三個數(shù)值,進(jìn)而求解粒子的適應(yīng)度值F。其算法步驟如表1所示。

表1 基于二進(jìn)制粒子群算法的攻擊策略適應(yīng)度求解算法

3.3 基于二進(jìn)制粒子群的攻擊策略求解算法

基于二進(jìn)制粒子群的攻擊策略在最優(yōu)節(jié)點(diǎn)集的求解過程中,首先對粒子群的速度和位置進(jìn)行初始化,其次比較并記錄個體和群體的最優(yōu)適應(yīng)度值,最后利用循環(huán)迭代思想逐步計(jì)算粒子群的最優(yōu)適應(yīng)度函數(shù)值,其算法步驟如表2所示。

表2 基于二進(jìn)制粒子群的攻擊策略求解算法

4 仿真分析

為驗(yàn)證本文所提攻擊策略的高效性、精確性和自動擇優(yōu)性,本文采用Holme[6]等提出的面向度的選擇性攻擊策略和面向介數(shù)的選擇性攻擊策略進(jìn)行對比分析。為使攻擊策略分析更具一般性,本文采用WS小世界網(wǎng)絡(luò)[22]和BA無標(biāo)度網(wǎng)絡(luò)[23-24]兩種網(wǎng)絡(luò)模型,WS小世界網(wǎng)絡(luò)隨機(jī)初始化為30個節(jié)點(diǎn),每個節(jié)點(diǎn)有4個鄰居,以概率0.3隨機(jī)化重連邊;BA無標(biāo)度網(wǎng)絡(luò)隨機(jī)初始化為30個節(jié)點(diǎn),每次加入2條邊。利用Networkx隨機(jī)生成網(wǎng)絡(luò)如圖1和圖2所示。圖1中共30個節(jié)點(diǎn),60條邊;圖2中共30個節(jié)點(diǎn),56條邊。

圖1 WS小世界網(wǎng)絡(luò)

圖2 BA無標(biāo)度網(wǎng)絡(luò)

4.1 時間復(fù)雜度對比

從基于二進(jìn)制粒子群算法的攻擊策略算法中可以得出算法的時間復(fù)雜度為O(N2),而面向度的選擇性攻擊策略算法和面向介數(shù)的選擇性攻擊策略算法的時間復(fù)雜度為O(2N),從圖3可以看出,當(dāng)N>1010時,在時間復(fù)雜性方面,基于二進(jìn)制粒子群的攻擊策略顯著優(yōu)于面向度的選擇性攻擊策略和面向介數(shù)的選擇性攻擊策略。在圖1中基于二進(jìn)制粒子群算法的攻擊策略在迭代20 000次后求得最優(yōu)適應(yīng)度值1.3077,對應(yīng)割點(diǎn)集為{v0、v1、v4、v6、v7、v10、v12、v13、v15、v18、v19、v20、v24、v25、v27};在圖2中基于二進(jìn)制粒子群算法的攻擊策略在迭代20 000次后即可求得最優(yōu)適應(yīng)度值0.6667,對應(yīng)割點(diǎn)集為{v0、v1、v3、v4、v5、v6、v8、v10、v12、v23}。求解結(jié)果與圖1和圖2實(shí)際情況相吻合。

圖3 時間復(fù)雜度對比

為對比分析基于二進(jìn)制粒子群的攻擊策略和面向度(介數(shù))的選擇性攻擊策略的時間復(fù)雜性,本文采用暴力搜索的思想,即攻擊節(jié)點(diǎn)集合為網(wǎng)絡(luò)所有可能失效節(jié)點(diǎn)的組合,因此，失效節(jié)點(diǎn)組合共230=1 073 741 824個,程序運(yùn)行時間為50次的算術(shù)平均值。針對WS小世界網(wǎng)絡(luò),迭代20 000次后,基于二進(jìn)制粒子群的攻擊策略用時約100 s,面向度的選擇性攻擊策略用時約300 000 s,面向介數(shù)的選擇性攻擊策略用時約300 000 s。針對BA無標(biāo)度網(wǎng)絡(luò),迭代20 000次后,基于二進(jìn)制粒子群的攻擊策略用時約110 s,面向度的選擇性攻擊策略用時約300 000 s,面向介數(shù)的選擇性攻擊策略用時約300 000 s。從以上數(shù)據(jù)分析可知,圖1和圖2在節(jié)點(diǎn)數(shù)相同而拓?fù)浣Y(jié)構(gòu)不同時,基于二進(jìn)制粒子群的攻擊策略的計(jì)算時間幾乎是相同的,而面向度的選擇性攻擊策略和面向介數(shù)的選擇性攻擊策略在暴力搜索的情況下平均用時是基于二進(jìn)制粒子群的攻擊策略所用時間的3000倍,在時效性要求很強(qiáng)的網(wǎng)絡(luò)對抗中必然貽誤戰(zhàn)機(jī)。綜上,對于典型網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)(如WS小世界網(wǎng)絡(luò)和BA無標(biāo)度網(wǎng)絡(luò)),基于二進(jìn)制粒子群的攻擊策略在時間復(fù)雜性方面要遠(yuǎn)遠(yuǎn)優(yōu)于面向度(介數(shù))的選擇性攻擊策略,是一種高效率的攻擊策略。

4.2 適應(yīng)度函數(shù)值對比

為驗(yàn)證本文所提攻擊策略的精確性和自動擇優(yōu)性,本文采用面向度(介數(shù))的降序選擇性攻擊策略與基于二進(jìn)制粒子群的攻擊策略進(jìn)行對比,求解適應(yīng)度值如圖4和圖5所示。

圖4 WS小世界網(wǎng)絡(luò)攻擊策略對比

圖5 BA無標(biāo)度網(wǎng)絡(luò)攻擊策略對比

圖4中,橫坐標(biāo)表示割點(diǎn)集的數(shù)量,在割點(diǎn)數(shù)量一定的情況下,割點(diǎn)集按照圖3節(jié)點(diǎn)度值或介數(shù)值降序的方式選擇,縱坐標(biāo)表示割點(diǎn)集對應(yīng)的適應(yīng)度函數(shù)值。從圖中可以看出,隨著攻擊強(qiáng)度變大,適應(yīng)度函數(shù)值先減少后增加,這是因?yàn)殚_始階段隨著攻擊強(qiáng)度的增加,連通分支數(shù)變大,而最大連通子圖階數(shù)變小,適應(yīng)度函數(shù)值逐漸變小,攻擊效果逐漸增強(qiáng);后期隨著失效節(jié)點(diǎn)增多而適應(yīng)度值變大是因?yàn)槭Ч?jié)點(diǎn)數(shù)量變大而連通分支數(shù)和最大連通子圖階數(shù)同時變小,攻擊效果逐漸減弱。面向度的選擇性攻擊在割點(diǎn)數(shù)為11時搜索到最小適應(yīng)度值1.778;面向介數(shù)的選擇性攻擊在割點(diǎn)數(shù)為16時搜索到最小適應(yīng)度值1.8;基于二進(jìn)制粒子群算法的攻擊無須遍歷節(jié)點(diǎn)集,可直接迭代搜索出最優(yōu)適應(yīng)度值1.307 7,割點(diǎn)數(shù)為15,是一種自動擇優(yōu)的攻擊策略。面向度的選擇性攻擊策略和面向介數(shù)的選擇性攻擊策略是兩條曲線而基于二進(jìn)制粒子群的攻擊策略是一個孤立點(diǎn)。從上述分析可知,針對WS小世界網(wǎng)絡(luò),三種攻擊策略的優(yōu)劣順序?yàn)?基于二進(jìn)制粒子群的攻擊策略?面向度的選擇性攻擊策略?面向介數(shù)的選擇性攻擊策略。

同樣在圖5中,面向度的選擇性攻擊在割點(diǎn)數(shù)為11時,搜索到最小適應(yīng)度值0.764 7;面向介數(shù)的選擇性攻擊在割點(diǎn)數(shù)為11時搜索到最小適應(yīng)度值0.764 7;基于二進(jìn)制粒子群算法的攻擊不需遍歷節(jié)點(diǎn)集直接迭代搜索出最優(yōu)適應(yīng)度值0.666 7,割點(diǎn)數(shù)為10。從上述分析可知,針對BA無標(biāo)度網(wǎng)絡(luò),三種攻擊策略的優(yōu)劣順序?yàn)?基于二進(jìn)制粒子群的攻擊策略?面向度的選擇性攻擊策略=面向介數(shù)的選擇性攻擊策略。

圖6、圖7和圖8分別是三種攻擊策略下WS小世界網(wǎng)絡(luò)和BA無標(biāo)度網(wǎng)絡(luò)適應(yīng)度值的對比圖。在三種攻擊策略下BA無標(biāo)度網(wǎng)絡(luò)均比WS小世界網(wǎng)絡(luò)更易被毀癱,這是因?yàn)樵诠?jié)點(diǎn)數(shù)量和邊數(shù)量相近的情況下,BA無標(biāo)度網(wǎng)絡(luò)存在“富人俱樂部現(xiàn)象”[25],一些節(jié)點(diǎn)為“HUB”節(jié)點(diǎn)和“橋”節(jié)點(diǎn),而WS小世界網(wǎng)絡(luò)是一種均勻網(wǎng)絡(luò),度分布呈“鐘型”分布。這一點(diǎn)與Albert[5]等人對無標(biāo)度網(wǎng)絡(luò)瓦解問題的分析相一致,從而間接證明了基于二進(jìn)制粒子群算法的攻擊策略的有效性。

圖6 面向度的選擇性攻擊策略

圖7 面向介數(shù)的選擇性攻擊策略

圖8 基于二進(jìn)制粒子群算法的攻擊策略

5 結(jié)束語

基于二進(jìn)制粒子群算法的攻擊策略是依據(jù)粒子自身和全局最優(yōu)解在粒子群中快速逼近最優(yōu)解的一種攻擊策略。在時間復(fù)雜度方面,該策略在粒子群上進(jìn)行搜索而不是在節(jié)點(diǎn)集上進(jìn)行搜索,提高了策略求解的時間效率;在適應(yīng)度值求解方面,該策略利用優(yōu)化算法自動求出最優(yōu)解而不是程式化比較尋優(yōu);在應(yīng)用性空間方面,該策略在多類網(wǎng)絡(luò)模型上都能適用且有效,具有一定普適性。在網(wǎng)絡(luò)空間作戰(zhàn)中,本文提出的攻擊策略能夠快速、精準(zhǔn)、自動地計(jì)算戰(zhàn)場網(wǎng)絡(luò)的最優(yōu)毀傷效果節(jié)點(diǎn)集,為指揮決策者制定攻擊行動和作戰(zhàn)方案提供精確、自主、高效的輔助決策支撐。