基于復雜網絡的風險傳播模型及有效算法

呂元海 孫江輝　杜程

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

關鍵詞：復雜網絡；推廣模型；風險傳播

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

1 引 言

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

本文在針對網絡風險傳播問題，結合復雜網絡中傳播蔓延現象的推廣模型 [11，12]，提出了一種網絡風險傳播模型及相關定義，并改進了風險傳播算法。

2 推廣模型下的風險傳播

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

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

在本文中，暫不考慮網絡風險移除狀態，即僅考慮風險在整個網絡中如何轉移，而未考慮網絡風險傳播后所造成情況的如何消除。因此上述推廣模型應用于風險傳播如下：

計算技術與自動化2016年6月

第35卷第2期呂元海等：基于復雜網絡的風險傳播模型及有效算法

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

3 風險傳播模型

3.1 相關定義

定義1.結點：指網絡系統中任意一臺網絡設備上任意可能被利用的最小單元。其中已經被利用的稱為風險結點，而尚未被利用的稱為非風險結點。

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

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

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

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

定義5.風險傳出公式：設結點n被成功利用的概率為Pn，被利用后對網絡系統的危害程度為Wn，利用至該結點的有向路徑概率為Pmn，其中m為主動訪問n的風險結點，則對結點n而言，產生的風險為Riskn=Pmn×Pn×Wn。

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

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

3.2 風險傳播模型

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

在實際網絡中，路徑傳播概率可由兩結點的所有可能路徑計算得出，而結點被成功攻擊的概率則有風險傳播推廣模型計算得出。

4 最大出度算法

針對最小入度最近鄰算法[5]的不足，本文設計了一種能更好反映網絡風險動態特征的算法——最大出度算法，又分為針對主動型風險傳播模型的最大出度算法和針對被動型風險傳播模型的最大出度算法。

4.1 風險源結點最大出度算法

Step1：計算未被處理過的風險結點出度值numofoutdegree。

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

Step3：傳播風險后將該結點標記為color=red。

Step4：重復Step1、Step2、Step3，直至所有風險結點全部被標記。

4.2 零入度非風險源最大出度算法

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

Step A：將網絡結點中所有零入度的非風險源結點標記為color=green。

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

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

Step D：引入風險后，該結點已為風險結點，如果滿足最大出度的條件，則跳轉至最大出度算法的Step2繼續風險傳播。如果暫不滿足最大出度的條件，則跳轉至Step A順序執行。

4.3 一般非風險源風險引入

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

Step a：計算非風險源結點的出度值numofoutdegree。

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

Step c：引入風險后，該結點已為風險結點，跳至Step b繼續執行，直至又出現圖3情況，則跳轉至Step a繼續執行，直至風險傳播完畢。

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

5 算法性能比較

5.1 風險傳播機制比較

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

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

5.2 實驗結果對比

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

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

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

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

6 結 論

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

參考文獻

[1] 吳金宇.網絡安全風險評估關鍵技術研究[D].北京：北京交通大學，2010.

[2] 肖曉春.基于模型的網絡安全風險評估的研究[D].上海：復旦大學，2008.

[3] 李濤.基于免疫的網絡安全風險檢測[J].中國科學（F輯一信息科學），2005，35（8）：798-816.

[4] 劉謙. 網絡安全風險評估研究[J]. 硅谷. 2009，（14）：65-70.

[5] 史志才.網絡風險評估方法研究[J].計算機應用， 2008，10：2471-2473.

[6] 陳鋒.基于多目標攻擊圖的層次化網絡安全風險評估方法研究[D].長沙：國防科技大學，2009.

[7] 梁玲，陳庶民，徐孟春，等.基于貝葉斯模型的網絡風險動態評估方法[J].信息工程大學學報，2007，（1）：53-55.

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

[9] 張永錚，方濱興，遲悅，等.用于評枯網絡信息系統的風險傳播模型[J].軟件學報，2007，18（1）： 137-145.

[10]張永錚，田志宏，方濱興，等.求解網絡風險傳播問題的近似算法及其性能分析[J].中國科學E輯：信息科學，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]汪小帆，李翔，陳關榮.復雜網絡理論及其應用[M].北京：清華大學出版社，2006.