通用有效的動態系統網絡病毒傳播模型方法研究
2009-01-01 00:00:00丁雪楓馬良丁雪松
計算機應用研究 2009年2期
（1. 上海理工大學管理學院，上海 200093； 2. 長春理工大學計算機學院，
長春 130022； 3.吉林大學商學院，
長春 130000）
摘 要：
研究了依存于網絡拓撲的病毒傳播特征，并提出了一個通用的動態系統網絡模型。該模型對爆發一種病毒后，其是很快滅亡還是長期生存，給出了一個簡單易求的傳播臨界值來進行判斷。最后通過對多個網絡實際數據集進行計算機仿真，證明了本模型及傳播臨界值的有效性和精確性。
關鍵詞：動態系統網絡； 病毒傳播模型； SIS模型； 傳播臨界值
中圖分類號：TP309 文獻標志碼：A
文章編號：1001-3695(2009)02-0696-03
Common and effective model of viral propagation with dynamical system network theory
DING Xue-feng1，2， MA Liang1， DING Xue-song3
（1.Bussiness School， University of Shanghai for Science Technology， Shanghai 200093， China; 2. School of Computer Science Technology， Changchun University of Science Technology，Changchun 130022，China; 3. Business School， Jilin University ， Changchun 130000， China）
Abstract:This paper studied the virus propagation characteristics， which depended on the topology of the entire network.And then presented a mathematical model of viruspropagationto derive the epidemic threshold value andthe relativeconditions.Finally， experiment demonstrates the effectiveness and the accuracy of the model.
Key words：dynamical system network，；virus propagation model； SIS model； epidemic threshold
0引言
隨著計算機網絡的飛速發展，在計算機網絡上傳播的病毒也越來越具破壞性和威脅性。有些計算機病毒通過計算機網絡的硬件進行傳播，有些是通過電子郵件、即時消息這類含有大量聯系人地址簿或聯系人列表的形式進行傳播。研究表明，無論哪種方式，計算機網絡的拓撲設計對于病毒傳播具有重要的影響。在某些計算機網絡拓撲中，即使是從一個很微不足道的節點出現的病毒，也有可能會迅速在網絡中蔓延開來，造成巨大破壞。目前的反病毒技術大都是看網絡中計算機某一時刻是否已感染病毒，針對已感染病毒的節點進行治療及防御研究，而不是從網絡中的病毒傳播能否存活的角度考慮以尋求控制及防御辦法。當一種新的計算機網絡病毒出現時，有些網絡情況下它會蔓延開來成為一種傳播病毒，而有些網絡情況下它會自己逐漸自動消失。因此，研究不同計算機網絡拓撲下病毒能否大規模傳播的規律的思想是十分可行的。理論上，一個節點聯系緊密的網絡比一個節點松散的網絡更容易為病毒的生存及傳播提供可能。因此，相同的病毒可能在一個網絡中會很快滅亡；而在另一個網絡中則可能成為傳播病毒。通過對不同網絡拓撲圖的特征研究發現，病毒在傳播過程中存在一個傳播臨界值，低于這個值病毒會逐漸滅亡，高于這個值病毒就會長期生存并蔓延。當處于臨界值之下時，病毒以對數形式逐漸衰減，對現實網絡不會造成破壞影響。
本文基于依賴于網絡拓撲形式的病毒能否存亡的思想，利用圖表示各種計算機網絡拓撲，通過研究病毒在任意網絡拓撲中的傳播行為特性，探討了病毒會最終滅亡以及病毒會流行傳播的條件，進而建立一個適用于任何一種網絡拓撲形式的病毒傳播模型，并詳細討論了決定病毒存亡的傳播臨界值的取值條件。
1 知識背景
一直以來，對于病毒的傳播過程規律，主要從兩個方面進行研究，即網絡圖中單節點的行為和不同網絡拓撲形式對病毒傳播的影響。大多數模型均針對某個特定的網絡提出。
1. 1 單節點行為的主要模型
目前，為了研究網絡中獨立的單節點在病毒傳播過程中的行為，已經提出了很多模型。最重要的幾個是：
a)SIS模型。該模型中，網絡節點表示個體，邊代表個體之間的接觸。節點在任意時刻處于兩種狀態之一：易感染狀態（S）和已感染狀態（I）。一個已感染節點被治愈，但馬上就會轉為易感染狀態；同時已感染節點還可以把病毒傳染給網絡中與之相連的鄰居易感節點。
b)SIR模型。該模型中，節點可處于三種狀態之一：易感染狀態（S）、已感染狀態（I）、移除狀態（R）。一個已感染節點一旦被治愈，它就對此病毒具有免疫能力，可以從傳播網絡中移除。
c)基于SIS、SIR等模型衍生的擴展模型。大多數模型中，描述病毒傳播都使用兩個參數：(a)病毒的出生率β，表示一個已感染節點試圖將病毒傳播給與其相連接的易感鄰居節點的概率；(b)病毒的治愈率δ，表示每個已感染節點可自身治愈的概率。如果δ很低，那么病毒傳播就會存活較長時間；如果β很低，病毒則很快消亡。這說明，病毒能否在網絡中進行傳播是由某個值決定的，稱該值為傳播臨界值。
1. 2 節點關系的主要模型
由于受網絡拓撲方式的限制，目前用來研究節點之間關系的模型方法大多需要引入很多假設條件。主要模型有：
a)KW模型。由Kephart和White提出的有向圖模型，他們給出了此模型下求解已感染節點個數ηKW的穩態方程以及傳播臨界值。例如隨機圖中，ηKW的求解表達式為ηKW=N(1-δ/β〈k〉)；傳播臨界值為τKW=1/〈k〉。其中：N是網絡中所有節點的個數；〈k〉是節點平均度數。該模型僅適用于ER隨機圖、樹型圖等節點分布遵循冪律的網絡。該類網絡中，大多數節點都是低連接度；少數具有高連接度的節點極容易被病毒感染并且傳染其他節點，同時導致網絡中病毒較難被根除。
b)MFA模型。平均空間假設模型。該模型假設網絡中具有相同度的節點都是平等的。該模型對于BA網絡的已感染節點個數穩態求解式為ηMFA=2Ne-δ/mβ，m是網絡中的最小度；傳播臨界值為τKFA=〈k〉/〈k2〉。其中：〈k〉是網絡平均度；〈k2〉是度平方的均值。MFA模型對于滿足冪律分布的網絡不具通用性。
c)關聯網絡模型。該網絡模型假設網絡中一個節點的關聯性與其相鄰節點的關聯性有關。該模型包含一個度分布函數P（k），以及一個用于確定度數為k的節點與度數為k′的節點關聯的概率P（k|k′）函數。雖然現實網絡中存在一些度相關的節點，但是只單純地用P（k|k′）函數來表示其關聯的關系過于籠統，多數情況下該公式求解的值與現實網絡相差甚遠。
2病毒傳播模型
2. 1 病毒傳播特性
在一個包含N個節點的網絡圖中，設每個節點只能處于兩種狀態之一，即已感染狀態和易感狀態。t+1時的狀態只與t時的狀態有關，這樣有2N種可能的傳播情形。病毒傳播以馬爾可夫鏈的形式進行蔓延。理論上不考慮實際因素，當概率為1時，經過一段相當長的時間可以達到所有節點無感染狀態。當一種病毒逐漸衰退時，也同樣是隨時間以指數的形式衰退的。
2.2 建模思想
設任一離散時間步Δt的間斷非常小，即Δt→0。在一個Δt內，一個已感染節點i試圖感染其他鄰居節點的概率為β，同時，節點i被治愈的概率為δ。任一個節點處于兩種狀態之一，并可以進行快速轉換，因此可以把病毒傳播網絡當做一個動態系統來進行研究。為了簡化問題，對于節點N的個數很大，病毒以指數形式增長的網絡，引入節點狀態相互獨立假設，即任一給定的節點所處的狀態與其他節點所處的狀態各自相互獨立，將N代替2N。實驗證明引入該假設并沒有對網絡研究造成影響。
2. 3 數學模型
設一個節點i在t時刻感染病毒的概率函數為pi(t)。當i的所有鄰居都沒有被感染，或者易感染節點沒有成功將病毒傳給i，用函數i(t)表示i在t+1時刻不會被其鄰節點感染的概率：
i(t)=Πj:i′的鄰節點(pj(t-1)(1-β)+(1-pj(t-1)))=
Πj:i的鄰節點(1-β×pj(t-1))
假設每個節點的pj(t-1)是相互獨立的，則有
1-pi(t)=(1-pi(t-1))×i(t)+δ×pi(t-1)×i(t)
i=1，…，N(1)
式(1)將馬爾可夫鏈轉換為一個非線性動態系統（non-linear dynamical system，NLDS）模型來表示，該等式可以有效且精確地描述網絡上的病毒傳播。圖1顯示了節點狀態轉換過程。
模型中每個單一節點在時間步t 時，或者處于易感狀態（S）或者處于已感染狀態（I）。一個易感節點i當前是健康的，但是會以1- i，t的概率被鄰居節點傳染上病毒；一個已感染節點以概率δ被治愈后，馬上變為易感節點；i，t的取值由病毒出生率β以及i節點周圍的網絡拓撲方式決定。為了確定數學模型的傳播臨界值求解表達式，首先給出動態系統模型下的傳播臨界值的定義。
綜合Kephart等人的結論，非線性動態系統模型下的傳播臨界值τNLDS定義為
β/δ＜τNLDS病毒感染隨時間衰敗，pi(t)→0，t→∞i
β/δ＞τNLDS病毒會生存并蔓延
3 傳播臨界值
動態系統網絡可用無向圖描述，一個無向圖可表述為一個鄰接矩陣。通過對現實數據集實驗研究發現，非線性動態系統模型的傳播臨界值取值只與網絡圖鄰接矩陣最大特征值有關。表達式為
τNLDS=1/λ1，A
(2)
其中：λ1，A是網絡鄰接矩陣A的最大特征值。要使得經過一段時間后，病毒逐漸趨于滅亡，即圖中的每個節點感染概率變為0，必須滿足條件β/δ＜τNLDS=1/λ1，A；反之亦成立，如果β/δ＜τNLDS=1/λ1，A，無論最初爆發病毒感染節點的規模大小，病毒傳播都會在一段時間后趨于滅亡，即感染概率將趨于0。
病毒感染以任意一個隨機路徑以(βλ1，A)速度增長，同時還以δ速率滅亡。因此，病毒傳播的有效速率可以近似表達為βλ1，A/δ。為了方便，引入一個刻度值s，使s=β/δ×λ1，A。動態系統下，當s<1時，病毒最終滅絕；s≥1時，病毒將生存下來。只有s取值大于1時，病毒傳播才會傳播蔓延開來。
4 仿真分析
為驗證模型的正確性，根據Barabasi、Albert、密歇根大學等提供的數據，對以下實際數據集進行了仿真實驗。
1)隨機網絡 一個含有256個節點、982條邊、最大特征值為8 691的ER隨機圖。
2)冪律網絡 一個含有3 000個節點、5 980條邊、最大特征值為11 541的BA生成圖。該生成圖冪律度分布指數為3。
3)星型網絡 該星型網絡的中心中轉節點與10 000星節點連接，最大特征值為100。
4)真實網絡 一個美國俄勒岡州的自治系統之間相互連接的真實網絡圖。該網絡包含11 461個節點、32 730條邊、最大特征值為75 241。
對于每個數據集，所有節點都初始為已感染狀態，然后通過計算機進行10 000個時間步，重復100次的仿真。
4. 1 動態系統網絡的精確性
圖2顯示了四個網絡中非線性動態系統模型隨時間推移，s取不同值已感染節點數目的變化。
圖2表明了非線性動態系統模型仿真結果與實際結果十分接近；動態系統的數學模型可以很好地描述任意網絡下的病毒傳播行為。
4. 2 傳播臨界值的精確性
圖3顯示了已感染節點個數取不同刻度值s情況下隨時間變化的情況。
圖3清晰地顯示，當低于臨界值（s<1）時，病毒感染會逐漸滅亡；高于臨界值（s>1）時，病毒就會生存下來。傳播臨界值與由動態系統模型的數學公式求解值結果一致。這說明低于傳播臨界值時病毒將會逐漸滅亡，高于傳播臨界值時病毒將會生存并傳播的判定條件是正確的。
4. 3 低于臨界值時病毒的指數衰退
圖4顯示了系統模型在處于臨界值之下（s<1）時病毒以指數的形式衰退。
如圖4所示，在四種不同的網絡中，在刻度值s<1情況下取不同s值，已感染節點個數都是隨時間以指數形式減少的。
5 結束語
本文研究病毒傳播的規律，提出一個通用的動態系統網絡數學模型，確定了模型的傳播界定值，通過仿真證明了有效精確性。傳播臨界值的取值由圖的最大特征值λ1決定，λ1值越大，圖中節點易感性就越高，當滿足β/δ＜1/λ1時病毒就會徹底滅亡。由于模型中節點只有已感染或者易感染兩種狀態，不存在免疫節點，一個被治愈的節點會馬上變成易感節點，這樣就很難控制病毒的傳播。未來的一個研究方向是臨界值條件下，發現更好的節點免疫方法，最大限度地控制病毒的傳播。
參考文獻：
[1]AIELLO W， CHUNG Fan， LU Lin-yuan. A random graph model for massive graphs[J].STOC，2000，6(1):171-180.
[2]ALBERT R， JEONG H， BARABASI A-L. Diameter of the World Wide Web[J].Nature，1999，401(6749):130-131.
[3]ALBERT R， BARABASI A-L. Topology of evolving networks:local events and universality[J].Phys Rev Lett，2000，85(24):5234-5237.
[4]RAVASZ E， BARABASI A-L.Hierarchical organization in complex networks[J].Phys Rev E，2003，67(2):026112.
[5]GOLDSTEIN M L， MORRIS S A， YEN G G. Problems with fitting to the power-law distribution[J].Eur Phys J B，2004，41(2):255-258.
[6]ZHOU T， WANG B H. Catastrophes in scale-free networks[J].Chinese Phys Lett，2005，22(5):1072-1075.
[7]CONDON P. R FC3580， IEEE 802.1x remote authentication dial in user service(RADIUS)usage guidelines[S]. 2003.
[8]DONGEN M van.Graph clustering by flow simulation[D]. Netherlands: University of Utrecht，2000.
[9]TANGMUNARUNKIT H，GOVINDAN R， JAMIN S， et al. Network topologies，power laws，and hierarchy[J]. ACM SIGCOMM Computer Communication Review，2002，32(1):76.
