基于復(fù)雜網(wǎng)絡(luò)的風(fēng)險傳播模型及有效算法

呂元海 孫江輝　杜程

摘 要：提出一種基于復(fù)雜網(wǎng)絡(luò)的風(fēng)險傳播模型及有效算法，通過結(jié)合復(fù)雜網(wǎng)絡(luò)中傳播蔓延現(xiàn)象的推廣模型，將風(fēng)險傳播模型劃分為兩種：主動型風(fēng)險傳播模型與被動型風(fēng)險傳播模型。并對已有風(fēng)險傳播算法進行改進，實驗表明，該模型及算法能健全風(fēng)險傳播機制，提高傳播速度與精確度。

關(guān)鍵詞：復(fù)雜網(wǎng)絡(luò)；推廣模型；風(fēng)險傳播

中圖分類號：TP393.0 文獻標識碼：A

1 引 言

隨著網(wǎng)絡(luò)安全問題的日益突出，風(fēng)險評估越來越受到人們的重視。風(fēng)險評估一般分為靜態(tài)評估和動態(tài)評估兩種，前者評估體系比較完善，評估精確性程度較高，但缺點是評估周期過長，評估模型可能隨著時間的推移而不能適用，不能反映網(wǎng)絡(luò)的實時信息；后者評估能根據(jù)網(wǎng)絡(luò)狀況適時的做出風(fēng)險估計，能及時反映網(wǎng)絡(luò)風(fēng)險的動態(tài)變化，性能好于靜態(tài)評估[1，2]。而針對動態(tài)風(fēng)險評估的研究有：基于免疫的網(wǎng)絡(luò)安全風(fēng)險檢測的模型[3，4]，是一種基于入侵時的檢測模型；基于隱馬爾可夫模型的網(wǎng)絡(luò)風(fēng)險評估方法研究[5，6]；基于貝葉斯模型的網(wǎng)絡(luò)風(fēng)險動態(tài)評估方法[7，8]， 可以對網(wǎng)絡(luò)的總體風(fēng)險和局部要素可能引起風(fēng)險的程度進行評估。以上文獻對網(wǎng)絡(luò)入侵檢測研究較為深入，但側(cè)重于對攻擊的動態(tài)評估，未能考慮已有風(fēng)險如何擴散與轉(zhuǎn)移。針對網(wǎng)絡(luò)風(fēng)險傳播，張永錚等提出了用于評估網(wǎng)絡(luò)信息系統(tǒng)的風(fēng)險傳播模型[9]和一種求解網(wǎng)絡(luò)風(fēng)險傳播問題的近似算法[10]，對已有風(fēng)險在網(wǎng)絡(luò)中的傳播進行研究，但其傳播模型與算法存在一些缺點：首先，模型中僅考慮了風(fēng)險傳播模型，未能考慮風(fēng)險引入模型；其次，一個部件上可能存在多個弱點，則該部件對另一部件的同一方向的可信訪問路徑可多于一種，則部件不能在有向圖中被視為圖節(jié)點。第三，最小入度的部件感染風(fēng)險的概率較低，因此其作為風(fēng)險源的概率不高。第四，若入度最小的部件已經(jīng)感染風(fēng)險，其出度不一定是最大的，正如流感爆發(fā)在人口密集的地區(qū)一樣，則其風(fēng)險不能立即傳播出去，存在滯后性，時效性欠佳。

本文在針對網(wǎng)絡(luò)風(fēng)險傳播問題，結(jié)合復(fù)雜網(wǎng)絡(luò)中傳播蔓延現(xiàn)象的推廣模型 [11，12]，提出了一種網(wǎng)絡(luò)風(fēng)險傳播模型及相關(guān)定義，并改進了風(fēng)險傳播算法。

2 推廣模型下的風(fēng)險傳播

網(wǎng)絡(luò)信息的動態(tài)風(fēng)險不僅僅表現(xiàn)為一般意義的風(fēng)險，其傳播可能會對社會造成不可估量的損失，如病毒的傳播造成的跨域風(fēng)險、有害信息的傳播造成的社會風(fēng)險等。為此我們將借鑒復(fù)雜網(wǎng)絡(luò)的傳播機理和分析的方法，研究網(wǎng)絡(luò)風(fēng)險傳播模型。

按照復(fù)雜網(wǎng)絡(luò)的傳播蔓延現(xiàn)象的推廣模型[11，12]：假設(shè)網(wǎng)絡(luò)中有N個個體，每個個體是三種狀態(tài)的中的一種：易染態(tài)S，感染態(tài)I和移除態(tài)R，在時刻t，個體i隨機的與個體j相連，若i∈S，j∈I，則個體i以概率p得到一個正劑量di（t′），這里di（t′）都服從分布函數(shù)f（d）。每個個體都保留著過去T時期中所接受的總的劑量

在本文中，暫不考慮網(wǎng)絡(luò)風(fēng)險移除狀態(tài)，即僅考慮風(fēng)險在整個網(wǎng)絡(luò)中如何轉(zhuǎn)移，而未考慮網(wǎng)絡(luò)風(fēng)險傳播后所造成情況的如何消除。因此上述推廣模型應(yīng)用于風(fēng)險傳播如下：

計算技術(shù)與自動化2016年6月

第35卷第2期呂元海等：基于復(fù)雜網(wǎng)絡(luò)的風(fēng)險傳播模型及有效算法

每一時刻t，風(fēng)險結(jié)點j對其直連結(jié)點i每發(fā)動一次攻擊，就會從被攻擊結(jié)點i中獲取一定的信息劑量di（t），則在過去T時期中風(fēng)險結(jié)點獲取被攻擊結(jié)點的信息總劑量為：

3 風(fēng)險傳播模型

3.1 相關(guān)定義

定義1.結(jié)點：指網(wǎng)絡(luò)系統(tǒng)中任意一臺網(wǎng)絡(luò)設(shè)備上任意可能被利用的最小單元。其中已經(jīng)被利用的稱為風(fēng)險結(jié)點，而尚未被利用的稱為非風(fēng)險結(jié)點。

定義2.有向路徑：結(jié)點A訪問結(jié)點B時，形成的從A指向B的單向訪問關(guān)系。這里所說的單向訪問關(guān)系是指合法或非法的、由主動發(fā)起方指向被訪問方的訪問，而不代表實際信息傳輸?shù)穆窂?，因為嚴格的講，任何兩個相連結(jié)點之間的鏈路都是雙向的。有向路徑概率即為結(jié)點訪問概率。

定義3.風(fēng)險傳出：指風(fēng)險結(jié)點對其所訪問的任一結(jié)點造成的損失或影響。

定義4.風(fēng)險引入：指非風(fēng)險結(jié)點訪問風(fēng)險結(jié)點時，由于存在實際信息的交換而受到該風(fēng)險結(jié)點的影響。

這里舉例說明一下定義3、4，某病毒利用空氣（相當于網(wǎng)絡(luò)中的信息交換鏈路）進行傳播，當病體A主動接觸易染體B時，A將病毒傳播給B，其中A主動接觸B即為A訪問B，病毒傳播方向為A到B；反之當易染體B主動接觸病體A，也會被感染，同樣病毒傳播方向為A至B，但為B訪問A。

定義5.風(fēng)險傳出公式：設(shè)結(jié)點n被成功利用的概率為Pn，被利用后對網(wǎng)絡(luò)系統(tǒng)的危害程度為Wn，利用至該結(jié)點的有向路徑概率為Pmn，其中m為主動訪問n的風(fēng)險結(jié)點，則對結(jié)點n而言，產(chǎn)生的風(fēng)險為Riskn=Pmn×Pn×Wn。

定義6.風(fēng)險引入公式：設(shè)結(jié)點n為非風(fēng)險結(jié)點，該結(jié)點成功訪問風(fēng)險結(jié)點m的概率為Pm，利用至結(jié)點m的有向路徑概率為Pnm，由結(jié)點n發(fā)出至結(jié)點m的有用消息權(quán)重及概率分別為Unm、pnm，由結(jié)點m發(fā)出至結(jié)點n的有害消息權(quán)重及概率分別為Hmn、pmn，則對結(jié)點n而言，引入的風(fēng)險為Riskn=Pnm×Pm×（Unm×pnm+Hmn×pmn）。

定義7.風(fēng)險網(wǎng)絡(luò)：借鑒張永錚等對風(fēng)險網(wǎng)絡(luò)[4]定義，把一個能夠描述各結(jié)點風(fēng)險分布與有向路徑的網(wǎng)絡(luò)稱為風(fēng)險網(wǎng)絡(luò)。風(fēng)險分布為網(wǎng)絡(luò)系統(tǒng)各個設(shè)備中結(jié)點攜帶風(fēng)險的分布情況，為內(nèi)在風(fēng)險；有向路徑即為各結(jié)點之間的訪問方向，為外來風(fēng)險的傳出與被引入提供可能。

3.2 風(fēng)險傳播模型

1.主動型風(fēng)險傳播模型：也稱為主動型風(fēng)險傳出，即利用風(fēng)險結(jié)點已存在的風(fēng)險對其直連結(jié)點進行主動訪問（包括非法攻擊或可信訪問，下同），產(chǎn)生風(fēng)險擴散（即風(fēng)險傳出）。如圖1（a）所示，結(jié)點A為風(fēng)險源結(jié)點，存在至結(jié)點B、C、D、E的四條有向路徑，設(shè)結(jié)點A風(fēng)險結(jié)點，至結(jié)點B、C、D、E的有向路徑概率為PAJ，（J=B，C，D，E），各結(jié)點自身被成功訪問的概率為PJ，（J=B，C，D，E）[8]，則結(jié)點A以概率PAJ×PJ（J=B，C，D，E）引起其出度所連結(jié)點發(fā)生風(fēng)險，如圖1（b）所示。

在實際網(wǎng)絡(luò)中，路徑傳播概率可由兩結(jié)點的所有可能路徑計算得出，而結(jié)點被成功攻擊的概率則有風(fēng)險傳播推廣模型計算得出。

4 最大出度算法

針對最小入度最近鄰算法[5]的不足，本文設(shè)計了一種能更好反映網(wǎng)絡(luò)風(fēng)險動態(tài)特征的算法——最大出度算法，又分為針對主動型風(fēng)險傳播模型的最大出度算法和針對被動型風(fēng)險傳播模型的最大出度算法。

4.1 風(fēng)險源結(jié)點最大出度算法

Step1：計算未被處理過的風(fēng)險結(jié)點出度值numofoutdegree。

Step2：優(yōu)先選擇最大出度的結(jié)點，利用圖1所示算法將其風(fēng)險值沿其出度傳播給相鄰結(jié)點，風(fēng)險計算方法見定義5。

Step3：傳播風(fēng)險后將該結(jié)點標記為color=red。

Step4：重復(fù)Step1、Step2、Step3，直至所有風(fēng)險結(jié)點全部被標記。

4.2 零入度非風(fēng)險源最大出度算法

嚴格的講，零入度的結(jié)點是不存在的，因此最小入度最近鄰算法關(guān)于零入度的概念未指明其時間范疇，在本文中，零入度的結(jié)點是指在某時間段內(nèi)不接受訪問的結(jié)點。

Step A：將網(wǎng)絡(luò)結(jié)點中所有零入度的非風(fēng)險源結(jié)點標記為color=green。

Step B：計算未被處理過的零入度的非風(fēng)險源的出度值numofoutdegree。

Step C：優(yōu)先選擇最大出度結(jié)點，并判斷其出度中有無風(fēng)險結(jié)點，若有則選擇其出度所連結(jié)點中風(fēng)險值最大的一個作為引入風(fēng)險源，以概率引入風(fēng)險，風(fēng)險計算方法見定義6，將該結(jié)點標記為color=pink，斷開與引入風(fēng)險源的有向鏈接；若無，則重新選擇結(jié)點，對該結(jié)點不進行任何處理直到再次滿足條件。

Step D：引入風(fēng)險后，該結(jié)點已為風(fēng)險結(jié)點，如果滿足最大出度的條件，則跳轉(zhuǎn)至最大出度算法的Step2繼續(xù)風(fēng)險傳播。如果暫不滿足最大出度的條件，則跳轉(zhuǎn)至Step A順序執(zhí)行。

4.3 一般非風(fēng)險源風(fēng)險引入

網(wǎng)絡(luò)結(jié)點的風(fēng)險在傳播最后往往會出現(xiàn)如圖3所示的情況：結(jié)點A、B、C為非風(fēng)險源結(jié)點，D、E為風(fēng)險結(jié)點且RiskD>RiskE，按照文[5]的理論，則其程序在圖3情況下停止運行，為了解決這一問題，引入如下算法：

Step a：計算非風(fēng)險源結(jié)點的出度值numofoutdegree。

Step b：優(yōu)先選擇出度最大的結(jié)點，若其出度所連接結(jié)點中存在風(fēng)險結(jié)點，則選擇風(fēng)險值最大的一個結(jié)點作為風(fēng)險引入源并斷開與該風(fēng)險引入源的有向鏈路，該結(jié)點被標記為color=pink；若不存在，則重新選擇。

Step c：引入風(fēng)險后，該結(jié)點已為風(fēng)險結(jié)點，跳至Step b繼續(xù)執(zhí)行，直至又出現(xiàn)圖3情況，則跳轉(zhuǎn)至Step a繼續(xù)執(zhí)行，直至風(fēng)險傳播完畢。

說明：網(wǎng)絡(luò)結(jié)點被初始化為風(fēng)險結(jié)點（color=pink）和安全可信結(jié)點（color=green）后，運行風(fēng)險源最大出度算法和零入度非風(fēng)險源最大出度算法時，兩者發(fā)執(zhí)行，不存在先后次序，而一般非風(fēng)險源風(fēng)險引入只是在出現(xiàn)如圖3情況下才使用的算法，是為了防止風(fēng)險傳播中忽略此類風(fēng)險引入導(dǎo)致風(fēng)險誤差較大的情況。

5 算法性能比較

5.1 風(fēng)險傳播機制比較

最小入度最近鄰傳播算法[5]雖然能夠?qū)W(wǎng)絡(luò)風(fēng)險傳播給出比較精確的結(jié)論，但其在理論上有一定的缺陷，如圖4所示，假設(shè)結(jié)點1、2為風(fēng)險結(jié)點，按照最小入度最近鄰傳播算法，結(jié)點1為入度最小的滿足條件的風(fēng)險結(jié)點，則其以概率使結(jié)點2、4產(chǎn)生風(fēng)險，同時將自己標記為已處理，如圖5（a）所示，然后結(jié)點2又滿足傳播條件，并以概率使結(jié)點3、5、6產(chǎn)生風(fēng)險，并被標記為已處理，如圖5（b）所示，兩步共計感染四個結(jié)點，但其卻是在第二步才將風(fēng)險傳給結(jié)點6，因而其時效性欠佳。而按照風(fēng)險源最大出度算法，則優(yōu)先選擇結(jié)點2，使其攜帶的風(fēng)險迅速被傳播給結(jié)點3、5、6，如圖6（a）所示，再次結(jié)點6滿足傳播條件，并將風(fēng)險傳播給其出度所連的四個結(jié)點，如圖6（b）所示，兩步共計感染七個結(jié)點，多于最小入度最近鄰傳播算法的新感染結(jié)點，并且其時效性優(yōu)勢隨著網(wǎng)絡(luò)結(jié)點的復(fù)雜化而凸顯，更容易滿足動態(tài)網(wǎng)絡(luò)風(fēng)險評估的要求。

此外，零入度的非風(fēng)險源結(jié)點不會傳出風(fēng)險[5]，因此應(yīng)在風(fēng)險傳播之前對其進行處理：斷開此類結(jié)點的所有出度，如圖7所示，結(jié)點9被認為不會對結(jié)點2及尤其是結(jié)點10造成風(fēng)險傳播，因此可以斷開其所有出度。但本論文認為結(jié)點9雖不會對結(jié)點10造成直接的風(fēng)險傳播，但是它可能會從結(jié)點2引入風(fēng)險，從而使自己變?yōu)轱L(fēng)險結(jié)點，進而對結(jié)點10造成風(fēng)險傳播，如圖8所示。

5.2 實驗結(jié)果對比

本實驗實驗環(huán)境為Microsoft Windows XP Professional，Intel（R） Pentium（R） CPU 1.8GHz，512M RAM。仿真工具為NetLogo 4.0.4、Matlab 7.0.0.19920（R14）。

共同參數(shù)：總結(jié)點為200，平均度為10，風(fēng)險結(jié)點不超過所有結(jié)點入度之和，結(jié)點危害性參數(shù)W=1，風(fēng)險結(jié)點初始風(fēng)險值為1，路徑傳播概率服從[0，0.5] 上的均勻分布。

本文參數(shù)：結(jié)點被成功訪問概率P可利用推廣模型計算，其中推廣模型的參數(shù)p=0.5，f（d）=δ（d-1），g（d*）=δ（d*-3），采用最大出度算法進行傳播。

文[5]參數(shù)：概率權(quán)p（x）=0.5，采用最小入度最近鄰算法進行傳播。

6 結(jié) 論

實驗表明：本文方法則是風(fēng)險呈非線性變化，并且開始變化較快，最后變化緩慢，即在一定的精確度容許的范圍內(nèi)，對風(fēng)險進行任意時刻的抽樣，本文的風(fēng)險值更接近真實風(fēng)險，因而動態(tài)性能更好。另外考慮的非風(fēng)險源結(jié)點的風(fēng)險引入，使風(fēng)險值被忽略的部分被重新計算在內(nèi)，提高了風(fēng)險精確度。

參考文獻

[1] 吳金宇.網(wǎng)絡(luò)安全風(fēng)險評估關(guān)鍵技術(shù)研究[D].北京：北京交通大學(xué)，2010.

[2] 肖曉春.基于模型的網(wǎng)絡(luò)安全風(fēng)險評估的研究[D].上海：復(fù)旦大學(xué)，2008.

[3] 李濤.基于免疫的網(wǎng)絡(luò)安全風(fēng)險檢測[J].中國科學(xué)（F輯一信息科學(xué)），2005，35（8）：798-816.

[4] 劉謙. 網(wǎng)絡(luò)安全風(fēng)險評估研究[J]. 硅谷. 2009，（14）：65-70.

[5] 史志才.網(wǎng)絡(luò)風(fēng)險評估方法研究[J].計算機應(yīng)用， 2008，10：2471-2473.

[6] 陳鋒.基于多目標攻擊圖的層次化網(wǎng)絡(luò)安全風(fēng)險評估方法研究[D].長沙：國防科技大學(xué)，2009.

[7] 梁玲，陳庶民，徐孟春，等.基于貝葉斯模型的網(wǎng)絡(luò)風(fēng)險動態(tài)評估方法[J].信息工程大學(xué)學(xué)報，2007，（1）：53-55.

[8] 付鈺，吳曉平，嚴承華. 基于貝葉斯網(wǎng)絡(luò)的信息安全風(fēng)險評估方法[J].武漢大學(xué)學(xué)報：理學(xué)版，2006，52（5）：631-634.

[9] 張永錚，方濱興，遲悅，等.用于評枯網(wǎng)絡(luò)信息系統(tǒng)的風(fēng)險傳播模型[J].軟件學(xué)報，2007，18（1）： 137-145.

[10]張永錚，田志宏，方濱興，等.求解網(wǎng)絡(luò)風(fēng)險傳播問題的近似算法及其性能分析[J].中國科學(xué)E輯：信息科學(xué)，2008，38（8）：1157-1168.

[11]Peter Sheridan Dodds and Duncan J.Watts. Universal Behavior in a Generalized Model of Contagion[J]. Physical Review Letters，2004，92：21-26.

[12]汪小帆，李翔，陳關(guān)榮.復(fù)雜網(wǎng)絡(luò)理論及其應(yīng)用[M].北京：清華大學(xué)出版社，2006.