基于馬爾可夫鏈的網絡蠕蟲傳播模型

周翰遜，郭薇，劉建，賈大宇

(1. 遼寧大學 信息學院，遼寧 沈陽 100036；2. 沈陽航空航天大學 計算機學院，遼寧 沈陽 110136；3. 東北大學 信息科學與工程學院，遼寧 沈陽 110819)

1 引言

自從 1988年 Morris蠕蟲[1]爆發(fā)以來，網絡蠕蟲就在不斷地威脅著網絡的安全。然而，直到2001年code red蠕蟲事件爆發(fā)后[2]，人們才開始關注蠕蟲這個領域。這是由于直到 21世紀初，網絡才與人們的經濟和生活緊密的聯(lián)系起來，因此蠕蟲對于網絡造成的危害就是對于人們的經濟生活造成的危害。為了能夠提供好的蠕蟲抑制方法，人們利用蠕蟲的傳播模型來揭示蠕蟲的傳播規(guī)律，并且指導人們抑制蠕蟲。

理想的蠕蟲傳播模型能夠充分反映蠕蟲的傳播過程，預測蠕蟲可能帶來的威脅，指導人們設計蠕蟲的防御檢測方法[3～6]。文獻[7]利用傳染病學的經典 SEM 模型對網絡蠕蟲進行了建模，然而該模型不能夠反映蠕蟲后期的傳播規(guī)律。鄒長春等[8]通過考慮蠕蟲在傳播的后期人們對其防治的 2個因素，在KM模型的基礎上得到了兩因素模型，該模型可以反映蠕蟲傳播后期的規(guī)律。文獻[9]提出了刻畫采用隨機掃描策略網絡蠕蟲的傳播模型AAWP(analytical active worm propagation)。Yu 等[10]對于可以改變掃描率的網絡蠕蟲進行了建模。在拓撲蠕蟲的建模方面，馮朝勝等[11]提出了 P2P網絡中被動型蠕蟲的傳播模型。孫鑫等[12]從社會工程學的角度研究社交網絡蠕蟲的傳播機制，通過量化影響用戶行為的若干因素，提出了微觀節(jié)點上的基于用戶安全意識的行為博弈模型。文獻[13]通過博弈模型表明多種蠕蟲檢測方法的整合才能有效地檢測故意降低傳播速度來降低被檢測的概率的網絡蠕蟲。張偉等[14]針對云安全體系環(huán)境，基于經典SIR模型提出了一種新的病毒傳播模型，該模型重點分析了網絡中云安全的部署程度和信息收集能力對蠕蟲傳播模型的影響。Jennifer等[15]對于在藍牙網絡環(huán)境下網絡蠕蟲的傳播過程進行了建模。雖然文獻[16]利用馬爾可夫模型對于網絡蠕蟲進行了建模，然而并沒有考慮到網絡蠕蟲主機的移去狀態(tài)，也沒有對于模型的穩(wěn)定性等性質進行數學證明。文獻[17]利用 G-W 分支過程對于網絡蠕蟲傳播模型進行了建模，然而在數學模型中也沒有考慮到網絡蠕蟲主機移去的可能性，只是在仿真實驗中加入了該因素。

但是，目前人們建立的網絡蠕蟲傳播模型大多是對于某一特殊蠕蟲的建模，使用確定性模型的平均場方法簡化問題并用微分方程描述病毒傳播的平均趨勢，不考慮概率事件，此類模型無法表述傳播過程中的概率事件[14]，此外，確定性模型忽視了個體之間的交互行為。本文研究網絡蠕蟲的隨機模型，分析蠕蟲病毒在大量主機上傳播時表現出來的特征，由于基于馬爾可夫鏈對于網絡蠕蟲的傳播過程進行建模，可以考慮網絡蠕蟲傳播過程中的概率事件，因此對于網絡蠕蟲的傳播刻畫的更貼近其真實傳播情況。

2 模型結構

模型假設除感病特征外，主機間沒有差異,蠕蟲傳播時采用具有代表性的隨機掃描策略。為了對網絡蠕蟲進行建模，將涉及的主機劃分成 3類，分別為易感狀態(tài)、感染狀態(tài)和移去狀態(tài)。處于易感狀態(tài)的主機沒有被蠕蟲感染，但是具有蠕蟲可以感染主機的漏洞；處于感染狀態(tài)的主機是由于網絡蠕蟲通過感染易感狀態(tài)的主機將其轉化為感染狀態(tài)的主機。移去狀態(tài)：處于易感狀態(tài)的主機是處于感染狀態(tài)的主機經過殺毒軟件或者人工的操作將蠕蟲進行刪除，從而轉化為移去狀態(tài)的主機。表1列出了下文模型中出現的主要參數符號及說明。

表1 模型參數

2.1 基于馬爾可夫鏈的網絡蠕蟲傳播模型

在蠕蟲的傳播過程中，由于網絡蠕蟲的擴散速度以及具有可以感染的漏洞主機數目的不同等因素，每個時間點網絡蠕蟲的傳播是隨機的，因此在時間t上的每個時間點，網絡蠕蟲感染主機的數目I(t)是一個隨機變量，其具有的狀態(tài)為：0，1，2，…，N，其中，N為網絡蠕蟲的漏洞主機數目。離散的隨機變量I(t)，t∈[0，∞ )，取值于狀態(tài)空間S={0，1，2，…，N}，相關的概率函數P(t)=(P0(t)，…，Pn(t))T。

其中，i=0，1，2，…，N并且t=0，Δt，2Δt，…，馬爾可夫過程需要滿足如下條件：t1，t2，…，tn，tn+1，及任意的狀態(tài)i1，i2，i3，…，in，in+1∈S，均有：P{I(tn+1)=in+1|I(t1)=i1，I(t2)=i2，…，I(tn)=in}=P{I(tn+1)=in+1|I(tn)=in}，則稱此隨機過程為馬爾可夫鏈。也就是說，該隨機過程tn+1時刻的狀態(tài)僅取決于tn時刻的狀態(tài)，由于網絡蠕蟲tn+1時刻的傳播數目僅與tn時刻的傳播數目有關，因此網絡蠕蟲的傳播過程符合馬爾可夫鏈的傳播條件，因此即為馬爾可夫鏈。

下面討論其一步轉移概率矩陣。假設在足夠小的時間Δt里，網絡蠕蟲只能增加一個感染主機，減少一個感染主機或者保持不變，如下

由于在足夠小的時間Δt里，轉移概率被認為是無窮小的轉移概率o(△t)，因此o(△t)在定義式子那么根據傳染病模型的原理，可以得到

由式(7)可知，π0，…，πN存在且均為一個常量，因此，該馬爾可夫鏈的極限分布以及平穩(wěn)分布均存在，又由于因此，網絡蠕蟲的馬爾可夫鏈模型是正常返的。

2.2 滅絕概率

隨著網絡蠕蟲的不斷傳播，此種群究竟是不斷壯大，還是規(guī)模保持不變或者最終走向滅亡是一個值得研究的問題。由于蠕蟲的滅絕可以凈化網絡環(huán)境，減小網絡蠕蟲對于網絡的破壞，因此研究網絡蠕蟲的滅絕概率就成了一個重要問題。下面給出網絡蠕蟲傳播初期滅絕的充要條件。

性質 1在蠕蟲傳播的初期，網絡蠕蟲的傳播不會滅絕的充要條件是β＞γ。

證明由于網絡蠕蟲在傳播過程中是否會滅絕，當且僅當它在t時刻的數學期望不大于1[18]。因此，下面來推導網絡蠕蟲在t時刻的傳播數目的數學期望。

蠕蟲傳播過程中的滅絕條件為IF(t)≤1，即ie(β-γ)t≤1，因此lni(β-γ)t≤0，又由于t≥0，lni＞0，因此只有β≤γ的時候，IF(t)≤1。也就是說，網絡蠕蟲的傳播才會終止。因此，在蠕蟲傳播的初期，網絡蠕蟲的傳播不會滅絕的充要條件是β＞γ，因此性質得到證明。

雖然該性質只是證明了在蠕蟲傳播初期網絡蠕蟲不會滅絕的條件，但是在網絡蠕蟲的中后期，由于網絡蠕蟲的傳播受到漏洞主機的數目越來越少，2個蠕蟲感染一臺主機的概率越來越大，傳播速度一定會低于傳播的初期，因此該性質給出了在網絡蠕蟲傳播的中后期不會滅絕的上限條件。具體證明請參閱2.3節(jié)。

2.3 蠕蟲傳播的規(guī)模

由2.2節(jié)可知，在網絡蠕蟲傳播的初期，網絡蠕蟲的傳播規(guī)模為式(9)，但是在網絡蠕蟲傳播的中后期，就不能用式(9)來進行推算了，下面來推導E{I(t)}的解析解。

根據2.2節(jié)可知

3 仿真驗證及分析

為了進一步揭示網絡蠕蟲的傳播規(guī)律，模擬隨機掃描蠕蟲的傳播策略編寫了一個模擬器仿真驗證了傳播模型， 對于每項試驗進行了1 000次的仿真實驗，通過發(fā)生的頻率與實驗次數的比值計算其概率，并且得到了該模型的傳播圖像，如圖1所示。圖像的橫軸為感染主機的數目，縱軸代表相應蠕蟲感染主機數目的感染概率。下面對于模型的參數進行詳細討論。

3.1 傳播參數

圖1是關于傳播參數β和γ的討論。其中圖1(a)和圖 1(b)分別為β=γ以及γ=2β。在這 2組數據下，網絡蠕蟲的傳播主機數目的相應概率均為 0。同時測試了其他參數組合，得到了類似的結論，由于篇幅所限，這里就不加敘述。也就是說，當β≤γ的時候，網絡蠕蟲就會滅絕。這也證明了在2.2節(jié)對于滅絕概率的討論。圖1(c)和圖1(e)分別為β=1和γc=10γe，圖1(d)和圖1(f)分別是圖1(c)和圖1(e)的累積概率圖，即概率分布函數。可以看到在圖1(c)中，網絡蠕蟲數目為5 000的時候的概率為峰值0.04，在圖1(d)中，可以看到網絡蠕蟲傳播小于7 000的概率為1；在圖1(d)中，網絡蠕蟲在8 000的概率為峰值0.085，在圖1(d)中，可以看到網絡蠕蟲傳播小于9 200的概率為1。也就是說，當網絡蠕蟲的傳播速度比移除網絡蠕蟲的速度越快，那么網絡蠕蟲的傳播數目較大的概率就越大。但是，即使是概率的峰值也不過只有0.04或者0.085，因此，網絡蠕蟲傳播的隨機性很大。但是，從圖像中又可以看到在圖 1(c)中網絡蠕蟲的傳播值在[2 000，7 300]之間概率大于0，其他值等于0；在圖1(d)中網絡蠕蟲的傳播值在[6 200，9 200]之間概率大于0，其他值等于0。因此，網絡蠕蟲在傳播過程中，只能知道在某個區(qū)間的傳播可能性較大，而無法確切的指出其傳播的值。因此，定義該區(qū)間為傳播區(qū)間，傳播區(qū)間指出了網絡蠕蟲在傳播過程中可能的感染狀態(tài)。

圖1 傳播參數

3.2 時間參數

圖2是在傳播時間分別為750、1 000和2 000個單位時間時，網絡蠕蟲的傳播圖像。當時間點不同時，網絡蠕蟲的傳播區(qū)間也會發(fā)生變化，因此將網絡蠕蟲的傳播區(qū)間定義為三元組WP(t， min，max)。

其中，t為時間，min為傳播區(qū)間的最小值，max為傳播區(qū)間的最大值。

因此，若WP(2 000， 2 000， 7 000)表明網絡蠕蟲在時間為2 000時，網絡蠕蟲的傳播值在[2 000， 7 000]之間概率大于 0，其他值等于 0。從圖中我們不難得出另外 2 個傳播區(qū)間P(750，0，6 000)，P(1 000， 0， 7 500)。從實驗結果不難發(fā)現，隨著網絡蠕蟲傳播時間的增加，網絡蠕蟲感染較大主機的數目的概率也會不斷增大。

圖2 時間參數

3.3 漏洞主機

圖3(a)、圖3(b)是漏洞主機為12 000時，網絡蠕蟲的傳播概率圖以及相應的概率分布函數。圖3(c)、圖3(d)是漏洞主機為15 000時，網絡蠕蟲的傳播概率圖以及相應的概率分布函數。從圖中不難發(fā)現，當漏洞主機為12 000時，其傳播區(qū)間為WP(2 000，8 000，11 000)；當漏洞主機為 15 000 時，其傳播區(qū)間為WP(2 000，10 000，14 000)。在圖 3(a)中，網絡蠕蟲數目為95 000的時候的概率為峰值0.078，在圖3(b)中，網絡蠕蟲傳播小于11 000的概率為1；在圖3(c)中，網絡蠕蟲在12 000的概率為峰值0.07，在圖3(d)中，可以看到網絡蠕蟲傳播小于14 000的概率為 1。即使是概率的峰值也不過只有 0.07或者0.078，因此，網絡蠕蟲傳播的隨機性還是很大。因此，隨著網絡蠕蟲漏洞主機數目的增加，網絡蠕蟲感染較大主機的數目的概率也會不斷增大。

圖3 漏洞主機的影響

3.4 模型比較

圖4(a)為本文提出的基于馬爾可夫鏈的網絡蠕蟲傳播模型與文獻[17]提出的基于G-W分支過程的網絡蠕蟲傳播模型(N=10 000)的對比，圖4(b)為本文模型與文獻[16]提出的未考慮主機移除率的馬爾可夫鏈的網絡蠕蟲模型(N=10 000)的對比。本文提出的傳播模型其傳播區(qū)間為WP(2 000， 2 000，7 000)，基于G-W分支過程的網絡蠕蟲傳播模型的傳播區(qū)間為WP(2 000， 80 000， 10 000)，未考慮主機移除率的馬爾可夫鏈蠕蟲模型的傳播區(qū)間為WP(2 000， 70 000， 95 000)。這主要是由于基于 G-W分支過程的網絡蠕蟲傳播模型以及文獻[16]的傳播模型并沒有考慮到網絡蠕蟲主機的移除的可能性，因此存在幾乎感染全部漏洞主機的可能性。此外，本文的網絡蠕蟲模型傳播概率的峰值為0.04；G-W分支過程的網絡蠕蟲傳播模型傳播概率的峰值為0.125；未考慮主機移除率的馬爾可夫鏈模型的傳播概率的峰值為0.093。3個模型都表明即使是概率峰值也不大，因此網絡蠕蟲的傳播具有較強的隨機性。

4 結束語

本文提出了網絡蠕蟲的隨機傳播模型。首先，基于馬爾可夫鏈對于網絡蠕蟲進行了建模，并且討論了模型的極限分布以及平穩(wěn)分布的存在性。然后，討論了網絡蠕蟲在傳播初期滅絕的充要條件以及在傳播后期滅絕的必要條件。最后，討論了網絡蠕蟲的傳播規(guī)模。仿真實驗對于模型進行了驗證。由于本文研究網絡蠕蟲傳播的隨機特性，分析蠕蟲病毒在大量主機上傳播時表現出來的特征，可以考慮網絡蠕蟲傳播過程中的概率事件，因此對于網絡蠕蟲的傳播刻畫得更貼近其真實傳播情況。

圖4 模型對比

[1] SPAFFORD E H. The Internet Worm Program： an Analysis[R].Technical Report， CSD-TR-823， West Lafayette： Department of Computer Science， Purdue University， 1988. 1-29.

[2] MOORE D， SHANNON C， BROWN J. Code-Red： a case study on the spread and victims of an Internet worm[A]. Proceedings of the Second ACM SIGCOMM Workshop on Internet Measurement[C]. 2002.273-284.

[3] 劉玉嶺， 馮登國， 吳麗輝等. 基于靜態(tài)貝葉斯博弈的蠕蟲攻防策略績效評估[J]. 軟件學報， 2012， 23(3)： 712-723.LIU Y L， FENG D G， WU L H，et al. Performance evaluation of worm attack and defense strategies based on static Bayesian game[J]. Journal of Software， 2012，23(3)：712-723.

[4] 汪潔， 王建新， 劉緒崇. 基于近鄰關系特征的多態(tài)蠕蟲防御方法[J].通信學報， 2011，32(8)： 150-158.WANG J， WANG J X， LIU X C. Novel approach based on neighborhood relation signature against polymorphic internet worms[J]. Journal on Communications，2011，32(8)：150-158.

[5] 洪征， 吳禮發(fā). 基于陽性選擇的蠕蟲檢測系統(tǒng)[J]. 軟件學報，2010，21(4)： 816-826.HONG Z，WU L F. Worm detection system based on positive selection[J]. Journal of Software， 2010， 21(4)：816-826.

[6] 唐勇， 諸葛建偉， 陳曙暉等. 蠕蟲正則表達式特征自動提取技術研究[J]. 通信學報， 2013， 34(3)：141-147.TANG Y， ZHUGE J W， CHEN S H，et al. Automatic generating regular expression signatures for real network worms[J]. Journal on Communications， 2013， 34(3)： 141-147.

[7] STANIFORD S， PAXSON V， WEAVER N. How to own the Internet in your spare time[A]. Proc of the 11th Usenix Security Symp[C]. San Francisco， 2002.

[8] ZOU C C， GONG W， TOWSLEY D. Code Red worm propagation modeling and analysis[A]. Proc of the 9th ACM Symp. on Computer and Communication Security[C]. Washington， 2002. 138-147.

[9] CHEN Z， GAO L， KWIAT K. Modeling the spread of active worms[A]. IEEE INFOCOM 2003[C]. 2003.1890-1900.

[10] YU W， WANG X， PRASAD C， XUAN D， ZHAO W. Modeling and detection of Camouflaging worm[J]. IEEE Transaction on Dependable and Secure Computing， 2011， 8(4)： 377-390.

[11] 馮朝勝， 秦志光， 袁丁等. P2P 網絡中被動型蠕蟲傳播與免疫建模[J]. 電子學報， 2013， 41(5)：884-889.FENG C S， QIN Z G， YUAN D，et al. Modeling propagation and immunization of passive worms in peer-to-peer networks[J]. Acta Electronica Sinica，2013，41(5)：884-889.

[12] 孫鑫， 劉衍珩， 朱建啟等. 社交網絡蠕蟲仿真建模研究[J]. 計算機學報， 2011， 34(7)： 1252-1261.SUN X， LIU Y H， ZHU J Q，et al. Research on simulation and modeling of social network worm propagation[J].Chinese Journal of Computers，2011，34(7)：1252-1261.

[13] YU W， ZHANG N， FU X W，et al. Self-disciplinary worms and countermeasures：modeling and analysis[J]. IEEE Transactions on Parallel and Distributed Systems， 2010， 21(10)： 1501-1514.

[14] 張偉， 王汝傳， 李鵬. 基于云安全環(huán)境的蠕蟲傳播模型[J]. 通信學報， 2012， 33(4)：17-24.ZHANG W， WANG R C， LI P. Worm propagation modeling in cloud security[J].Journal on Communications， 2012， 33(4)：17-24.

[15] JENNIFER T. Jackson and sadie creese， virus propagation in heterogeneous bluetooth networks with human behaviors[J]. IEEE Transactions on Dependable and Secure Computing， 2012，9(6)：930-943.

[16] 劉烴， 鄭慶華， 管曉宏等. 基于隨機實驗的蠕蟲傳播預測研究[J].通信學報， 2007， 28(12)：72-77.LIU J， ZHENG Q H， GUAN X H，et al. Research of worm-propagation prediction based on stochastic experiment[J].Journal on Communications， 2007， 28(12)：72-77.

[17] SARAH S， NESS B S， SAURABH B. Modeling and automated containment of worms[J]. IEEE Transactions on Dependable and Secure Computing， 2008， 5(2)： 528-537.

[18] ROSS S. Stochastic Processes[M]. John Wiley & Sons， 1996.