面向蓄意攻擊的網(wǎng)絡(luò)異常檢測(cè)方法

趙 海， 鄭春陽(yáng),， 王進(jìn)法， 司帥宗

(1. 東北大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院， 遼寧 沈陽(yáng) 110169； 2. 中國(guó)科學(xué)院 信息工程研究所/物聯(lián)網(wǎng)安全北京市重點(diǎn)實(shí)驗(yàn)室， 北京 100093)

以互聯(lián)網(wǎng)、電信網(wǎng)和電網(wǎng)為代表的重要網(wǎng)絡(luò)經(jīng)常會(huì)受到來(lái)自外部的蓄意攻擊，導(dǎo)致其拓?fù)浣Y(jié)構(gòu)被破壞，網(wǎng)絡(luò)功能損失，危害社會(huì)穩(wěn)定，帶來(lái)不可估量的經(jīng)濟(jì)損失.因此，采用異常檢測(cè)方法及時(shí)檢測(cè)到網(wǎng)絡(luò)異常具有重要的研究意義和價(jià)值.

目前，對(duì)網(wǎng)絡(luò)的異常檢測(cè)方法主要?dú)w納為4類(lèi):基于分解、基于社團(tuán)或聚類(lèi)、基于時(shí)序窗及基于特征.

基于分解方法，Ishibashi等[1]采用個(gè)體間至其目的主機(jī)的重疊情況代替主機(jī)間的簡(jiǎn)單關(guān)聯(lián)來(lái)生成鄰接矩陣并分解處理來(lái)實(shí)現(xiàn)異常檢測(cè)； Koutra等[2]和Papalexakis等[3]采用張量分解，將時(shí)序及其他額外特征與鄰接矩陣結(jié)合形成新的張量并分解來(lái)實(shí)現(xiàn)異常檢測(cè).基于社團(tuán)或聚類(lèi)方法，Heard等[4]提出兩步貝葉斯方法，通過(guò)計(jì)算基于貝葉斯學(xué)習(xí)的p-value來(lái)判斷現(xiàn)存與消亡的邊是否異常.基于時(shí)序窗口方法，Peel等[5]提出一種選取固定長(zhǎng)度的滑動(dòng)窗口，進(jìn)行廣義似然比檢驗(yàn)，判斷對(duì)已有固定模型是否有改變.以上方法基于統(tǒng)計(jì)學(xué)手段，在反映、描述異常演化的現(xiàn)象上略有欠缺，此外，有的方法[1-4]計(jì)算復(fù)雜度較高,有的方法[5]受網(wǎng)絡(luò)類(lèi)型的限制.

著眼于前三類(lèi)方法的問(wèn)題，基于特征方法研究更為深入，且更多關(guān)注于圖拓?fù)鋽?shù)據(jù)而不是流數(shù)據(jù)[6]，包括統(tǒng)計(jì)臨近圖的最大公共子圖MCS(maximum common subgraph)方法[7].統(tǒng)計(jì)相鄰時(shí)刻圖編輯距離GED(graph edit distance)[8]，來(lái)量化圖的相似程度，若超出閾值則異常. Koutra等[9]提出Deltacon方法，采用對(duì)比一系列圖快照的節(jié)點(diǎn)親緣關(guān)系，可進(jìn)行非連續(xù)的異常檢測(cè).近似地，在基于特征方法中，通常需要較多時(shí)序下的數(shù)據(jù)作為參考，并更多關(guān)注于局部特征，為此本文提出一種面向蓄意攻擊的異常檢測(cè)方法，捕捉了異常現(xiàn)象背后真實(shí)全局拓?fù)涞淖儎?dòng)，并參考全局特征，旨在把參考樣本數(shù)目降低.

1 異常演化與拓?fù)渥儎?dòng)特征分析

1.1 模型描述

一個(gè)復(fù)雜網(wǎng)絡(luò)g=(V,E)，sp(v,u)表示復(fù)雜網(wǎng)絡(luò)中由v到u的一條最短路徑，在無(wú)權(quán)網(wǎng)絡(luò)中為兩個(gè)節(jié)點(diǎn)最短路徑跳數(shù)，或者有權(quán)網(wǎng)絡(luò)中邊或節(jié)點(diǎn)權(quán)重最小的路徑.其中V,E分別代表網(wǎng)絡(luò)g的節(jié)點(diǎn)集和邊集，節(jié)點(diǎn)v的傳輸性能為

d(v)=max{sp(v,u)|u∈N(v)}，

(1)

(2)

式中:N(v)為節(jié)點(diǎn)v的鄰居節(jié)點(diǎn)集合；d(v)為某節(jié)點(diǎn)對(duì)傳輸性能的最差情況值；p(v)為v到其他節(jié)點(diǎn)的平均情況值.

復(fù)雜網(wǎng)絡(luò)g=(V,E)的最大直徑:

(3)

復(fù)雜網(wǎng)絡(luò)g的有效直徑

(4)

復(fù)雜網(wǎng)絡(luò)g的平均最短路徑:

(5)

從各參數(shù)的物理意義來(lái)看，Dmax描述了所有網(wǎng)絡(luò)連通節(jié)點(diǎn)對(duì)的最大距離均值，是最差傳輸性能的描述量，而Deff是使得網(wǎng)絡(luò)中至少90%的連通節(jié)點(diǎn)對(duì)可以互相到達(dá)的最小距離，通常比Dmax更具有魯棒性.SP是所有連通節(jié)點(diǎn)對(duì)最短距離的均值，是最好傳輸性能的描述量.

1.2 蓄意攻擊

以互聯(lián)網(wǎng)為代表的真實(shí)復(fù)雜網(wǎng)絡(luò)大多具有“無(wú)標(biāo)度性”，這決定了它們對(duì)隨機(jī)故障的高魯棒性及蓄意攻擊的脆弱性[10].蓄意攻擊就是對(duì)網(wǎng)絡(luò)中特定中心性節(jié)點(diǎn)攻擊并使相關(guān)節(jié)點(diǎn)與鏈路失效，因此極小程度的蓄意攻擊就會(huì)導(dǎo)致網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)發(fā)生較大變動(dòng)，導(dǎo)致原有的流傳輸路徑或連通路徑發(fā)生改變，引發(fā)相關(guān)最優(yōu)傳輸路徑增長(zhǎng)甚至不可達(dá).

這種異常演化會(huì)打破原有的網(wǎng)絡(luò)傳輸平衡，增加局部節(jié)點(diǎn)的傳輸負(fù)載，導(dǎo)致更多節(jié)點(diǎn)的鏈路故障，由此引發(fā)網(wǎng)絡(luò)級(jí)聯(lián)故障，網(wǎng)絡(luò)傳輸性能發(fā)生非線性變化[11-12].因此，可以通過(guò)量化傳輸路徑的變化，表達(dá)網(wǎng)絡(luò)全局拓?fù)鋵用娴淖儎?dòng)，此度量有助于實(shí)現(xiàn)對(duì)網(wǎng)絡(luò)蓄意攻擊的異常檢測(cè).

1.3 異常演化分析

蓄意攻擊引發(fā)的網(wǎng)絡(luò)異常通常伴隨著網(wǎng)絡(luò)特征的顯著波動(dòng)[13].為進(jìn)一步觀察和驗(yàn)證蓄意攻擊導(dǎo)致最優(yōu)傳輸路徑變動(dòng)并造成結(jié)構(gòu)突變的現(xiàn)象，通過(guò)節(jié)點(diǎn)刪除法，以節(jié)點(diǎn)介數(shù)優(yōu)先為策略，仿真BA網(wǎng)絡(luò)受蓄意攻擊過(guò)程.

對(duì)具有5 000節(jié)點(diǎn)的BA網(wǎng)絡(luò)進(jìn)行10次觀測(cè).主要關(guān)注反映網(wǎng)絡(luò)連通性能的Dmax,Deff,SP三個(gè)特征在蓄意攻擊過(guò)程中的波動(dòng).

蓄意攻擊下BA網(wǎng)絡(luò)特征波動(dòng)情況如圖1所示，最大子團(tuán)節(jié)點(diǎn)數(shù)和邊數(shù)在5.95%(A線)左右處產(chǎn)生突變；而Dmax,Deff,SP則先急劇變大，然后迅速減小，在5.95%的相關(guān)中心節(jié)點(diǎn)遭攻擊失效時(shí)突變，達(dá)到極大值.

復(fù)雜網(wǎng)絡(luò)在正常演化時(shí)拓?fù)浣Y(jié)構(gòu)及各特征值相對(duì)穩(wěn)定，通過(guò)中心性節(jié)點(diǎn)的傳輸路徑不會(huì)發(fā)生較大變動(dòng).當(dāng)網(wǎng)絡(luò)受到蓄意攻擊時(shí)，最先導(dǎo)致高介數(shù)節(jié)點(diǎn)陸續(xù)失效，部分節(jié)點(diǎn)對(duì)最優(yōu)傳輸路徑發(fā)生改變，Dmax,Deff,SP逐漸上升，傳輸性能下降.隨著蓄意攻擊程度逐漸加深，中心性節(jié)點(diǎn)與鏈路的失效對(duì)網(wǎng)絡(luò)結(jié)構(gòu)的影響逐步累積，由量變產(chǎn)生質(zhì)變，引起拓?fù)浣Y(jié)構(gòu)崩塌[14]，此時(shí)各特征上升至極值.隨著極大子團(tuán)崩塌形成新的規(guī)模較小的極大子團(tuán)，特征值也隨之下降.

因此，各特征值在蓄意攻擊導(dǎo)致網(wǎng)絡(luò)異常產(chǎn)生時(shí)通常會(huì)達(dá)到極值，具有明顯波動(dòng)特征.

2 面向蓄意攻擊的異常檢測(cè)算法

2.1 網(wǎng)絡(luò)路徑相對(duì)變化系數(shù)

網(wǎng)絡(luò)的Dmax,Deff,SP特征變化趨勢(shì)相似，但峰值差異大且Dmax較Deff更敏感，SP次之，三者變化速率與變化范圍均不同.

以上特征量定義結(jié)合1.1節(jié)可知，Dmax≥Deff≥SP，故通過(guò)不等式轉(zhuǎn)換得到

Dmax-Deff≤Dmax-SP.

(6)

因此，本文設(shè)計(jì)了能夠量化復(fù)雜網(wǎng)絡(luò)結(jié)構(gòu)動(dòng)態(tài)性的指標(biāo)——網(wǎng)絡(luò)路徑相對(duì)變化系數(shù)(network path changing coefficient,NPCC)r:

(7)

在正常演化過(guò)程中，r會(huì)較為平緩；在異常產(chǎn)生時(shí)，r會(huì)發(fā)生明顯向下波動(dòng)，偏離正常演化下的穩(wěn)態(tài).

2.2 斐波那契演化域

復(fù)雜網(wǎng)絡(luò)作為一個(gè)動(dòng)態(tài)系統(tǒng)是不斷演化的，r也是實(shí)時(shí)波動(dòng)的，因此各時(shí)刻正常域也應(yīng)及時(shí)動(dòng)態(tài)調(diào)整.本文基于斐波那契數(shù)列衍生出斐波那契演化域，旨在對(duì)正常和異常演化波動(dòng)更好地進(jìn)行區(qū)分.首先提出斐波那契演化域:對(duì)于任意時(shí)序上的拓?fù)浣Y(jié)構(gòu)度量參數(shù)M，記mi(i∈{1,2,…,n})為M在時(shí)間單元ti的值.

Ri(mi)=[mi-i,mi+i].

(8)

式中:Ri(mi)為mi的鄰域；i為隨機(jī)變量.

記Ri+Rj=Ri∪Rj，?i,j∈{1,2,…,n}，構(gòu)造域構(gòu)成的序列:

(9)

則Fi(mi)為斐波那契演化域序列，i∈{1,2,…,n}.

基于斐波那契演化域序列的定義，某時(shí)刻是否為異常取決于前兩個(gè)時(shí)序值和隨機(jī)變量i.隨機(jī)變量i描述的是網(wǎng)絡(luò)固有的特性及檢測(cè)算法的敏感性，對(duì)網(wǎng)絡(luò)常態(tài)進(jìn)行觀察與統(tǒng)計(jì)，得到網(wǎng)絡(luò)r指標(biāo)的標(biāo)準(zhǔn)差，再根據(jù)檢測(cè)的敏感性需求進(jìn)行適當(dāng)調(diào)整，以獲得網(wǎng)絡(luò)近期的隨機(jī)變量.

2.3 異常檢測(cè)算法

將r作為核心度量參量，結(jié)合斐波那契演化域，構(gòu)建網(wǎng)絡(luò)演化的正常域，此方法從真實(shí)拓?fù)浣Y(jié)構(gòu)變動(dòng)的角度來(lái)檢測(cè)由蓄意攻擊產(chǎn)生的網(wǎng)絡(luò)異常.

給出前兩個(gè)時(shí)刻網(wǎng)絡(luò)的r值及常態(tài)下的i值，就可以對(duì)當(dāng)前網(wǎng)絡(luò)狀態(tài)進(jìn)行異常檢測(cè).算法1為異常檢測(cè)算法.

算法 1 網(wǎng)絡(luò)異常檢測(cè)算法

輸入:正常態(tài)前i-1時(shí)刻r指標(biāo)值{…mi-2,mi-1}；

i時(shí)刻待檢測(cè)網(wǎng)絡(luò)指標(biāo)值mi

輸出:該時(shí)刻內(nèi)是否有異常產(chǎn)生y

過(guò)程:Ri-2(mi-2)=[mi-2-i,mi-2+1]

Ri-1(mi-1)=[mi-1-i,mi-1+1]

Fi(mi)=Ri-1(mi-1)∪Ri-2(mi-2)

Ifmi∈Fi(mi),y=0

elsey=1

End If

首先獲得i-2與i-1時(shí)刻鄰域?yàn)镽i-2(mi-2)與Ri-1(mi-1)，得出i時(shí)刻r指標(biāo)值正常域Fi(mi)；由于r的向下突變反映網(wǎng)絡(luò)產(chǎn)生異常，若待檢測(cè)網(wǎng)絡(luò)mi值不屬于i時(shí)刻正常域，輸出為y=1，則算法判斷異常產(chǎn)生.

將前兩個(gè)時(shí)刻的正常態(tài)作為參考，降低了誤判，其中的核心度量參量也可以在未來(lái)的工作中進(jìn)行改進(jìn)；其次，若想增加時(shí)序上的關(guān)聯(lián)性，可以考慮將前k項(xiàng)作為參考，此算法具有一定擴(kuò)展性.

3 實(shí)驗(yàn)結(jié)果及分析

采用節(jié)點(diǎn)刪除法模擬蓄意攻擊，驗(yàn)證r指標(biāo)的量化有效性；將MCS[7],GED[8]作為異常檢測(cè)對(duì)比方法，驗(yàn)證本方法的準(zhǔn)確性.實(shí)驗(yàn)網(wǎng)絡(luò)為因特網(wǎng)AS級(jí)拓?fù)?AS Internet)、互聯(lián)網(wǎng)路由級(jí)拓?fù)?computer route view)[15]、美國(guó)電網(wǎng)(power grid).網(wǎng)絡(luò)相關(guān)拓?fù)鋮?shù)如表1所示.

3.1 r有效性分析

采用節(jié)點(diǎn)刪除法，驗(yàn)證r指標(biāo)分別在節(jié)點(diǎn)度或介數(shù)優(yōu)先的策略下的量化情況.將Dmax,Deff,SP達(dá)到極大值時(shí)定義為網(wǎng)絡(luò)異常產(chǎn)生并給出標(biāo)識(shí)，r0為初始值.

表1 實(shí)驗(yàn)網(wǎng)絡(luò)拓?fù)鋮?shù)

蓄意攻擊后網(wǎng)絡(luò)的r值變化如圖2所示，網(wǎng)絡(luò)的r值在蓄意攻擊過(guò)程中呈現(xiàn)先上升再下降的趨勢(shì)，并且在異常產(chǎn)生時(shí)呈現(xiàn)出大幅下降的特征，符合對(duì)網(wǎng)絡(luò)結(jié)構(gòu)動(dòng)態(tài)性變化的分析.

在圖2a中，介數(shù)優(yōu)先策略下，柱形圖最高時(shí)未對(duì)應(yīng)異常產(chǎn)生，但前一時(shí)刻r的波動(dòng)程度已足夠檢測(cè)出異常.在圖2b～2d中，柱形圖最高處均對(duì)應(yīng)著異常產(chǎn)生，說(shuō)明r的波動(dòng)情況在異常時(shí)刻具有顯著特征.

可以看出r指標(biāo)對(duì)不同類(lèi)型網(wǎng)絡(luò)進(jìn)行實(shí)驗(yàn)時(shí)，均能很好地描述異常帶來(lái)的拓?fù)浣Y(jié)構(gòu)損失及所引發(fā)的連通路徑變化，并且在拓?fù)鋼p失累積達(dá)到質(zhì)變時(shí)也能表現(xiàn)出顯著的特征，驗(yàn)證了r指標(biāo)的有效性，為異常檢測(cè)算法提供了有效的度量參量.

3.2 異常檢測(cè)算法準(zhǔn)確率分析

采用節(jié)點(diǎn)介數(shù)優(yōu)先策略模擬蓄意攻擊，PFP模型構(gòu)造網(wǎng)絡(luò)正常演化，隨機(jī)產(chǎn)生不同程度的攻擊，將MCS，GED方法與本方法進(jìn)行對(duì)比.每個(gè)網(wǎng)絡(luò)模擬10次，單次時(shí)序范圍100個(gè)時(shí)間序列，評(píng)價(jià)指標(biāo)采用準(zhǔn)確率(Acc)、精確率(Pre):

(10)

式中:FP為假的正樣本；FN為假的負(fù)樣本；TP為檢測(cè)正確的正樣本；TN為檢測(cè)正確的負(fù)樣本.

為方便仿真的進(jìn)行，網(wǎng)絡(luò)每次遭受攻擊后會(huì)恢復(fù)至最近時(shí)刻的正常網(wǎng)絡(luò)情形；隨機(jī)變量i的選擇為測(cè)試數(shù)據(jù)中正常波動(dòng)的標(biāo)準(zhǔn)差.

As-rel異常檢測(cè)核心度量參數(shù)變化如圖3所示.在圖3a～3c中，MCS，GED檢測(cè)方法均出現(xiàn)較多突變，而r值在正常演化中波動(dòng)較小.在圖3d,3e中，給出了方法在不同閾值下的準(zhǔn)確率、精確率的變化情況.

由圖3可知，異常產(chǎn)生實(shí)際為2,6,7,16,24等時(shí)間序列，輕微擾動(dòng)為9,21,26,43等時(shí)間序列，可以看出GED，MCS方法在輕微擾動(dòng)下，例如9時(shí)間序列，波動(dòng)接近甚至超過(guò)實(shí)際異常產(chǎn)生時(shí)刻，其他正常時(shí)刻波動(dòng)也較大；而r值只是產(chǎn)生輕微向上變化，說(shuō)明該方法可以更好地刻畫(huà)異常的產(chǎn)生.GED與MCS方法由于始終比較當(dāng)前時(shí)刻與前一時(shí)刻的“網(wǎng)絡(luò)相似度”，前者比較的是節(jié)點(diǎn)與邊的增刪，后者是統(tǒng)計(jì)最大公共子圖的規(guī)模，而正常演化包含很多節(jié)點(diǎn)與邊的新生與消亡，因此較難區(qū)分出異常.通過(guò)圖3d,3e可以找到較好的準(zhǔn)確率與精確率，將其與本文方法的結(jié)果進(jìn)行比較，具體實(shí)驗(yàn)統(tǒng)計(jì)結(jié)果如表2所示.

表2 異常檢測(cè)結(jié)果統(tǒng)計(jì)表

4 結(jié) 論

1) 分析了網(wǎng)絡(luò)受蓄意攻擊引發(fā)異常的現(xiàn)象，提出了在異常演化現(xiàn)象中具有顯著特征的r指標(biāo)，以此為基礎(chǔ)，將斐波那契演化域與r結(jié)合，區(qū)分正常與異常演化，構(gòu)造了面向蓄意攻擊的異常檢測(cè)方法.

2) 實(shí)驗(yàn)結(jié)果表明，r有效地描述了網(wǎng)絡(luò)面向蓄意攻擊過(guò)程中發(fā)生的變化，且異常檢測(cè)方法針對(duì)不同類(lèi)型真實(shí)數(shù)據(jù)集平均準(zhǔn)確率達(dá)90%，能較為準(zhǔn)確地判斷網(wǎng)絡(luò)是否發(fā)生異常演化.