病毒在無標(biāo)度網(wǎng)絡(luò)上的傳播及控制仿真研究

摘要：網(wǎng)絡(luò)病毒的爆發(fā)給計(jì)算機(jī)用戶帶來巨大的損失，同時(shí)互聯(lián)網(wǎng)被認(rèn)為是無標(biāo)度網(wǎng)絡(luò)，因此研究病毒在無標(biāo)度網(wǎng)絡(luò)上的傳播及控制很有意義。通過構(gòu)建一個(gè)BA無標(biāo)度網(wǎng)絡(luò)模型，對(duì)病毒的傳播行為及影響因素進(jìn)行了仿真分析。研究表明，采取恰當(dāng)?shù)牟呗钥梢杂行У乜刂?、預(yù)防病毒傳播。

關(guān)鍵詞：網(wǎng)絡(luò)病毒； 無標(biāo)度網(wǎng)絡(luò)； 冪律

中圖分類號(hào)：TP309文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1001-3695(2007)12-0177-02

0引言

1999年Faloutsos等人^[1]發(fā)現(xiàn)，互聯(lián)網(wǎng)表現(xiàn)出很強(qiáng)的冪律分布特點(diǎn)，節(jié)點(diǎn)的度(某節(jié)點(diǎn)的度是指與該節(jié)點(diǎn)相連的節(jié)點(diǎn)數(shù)目，或者說與該節(jié)點(diǎn)關(guān)聯(lián)的邊的數(shù)目)有很大的波動(dòng)性^[1，2]。目前為止主要從兩種不同的角度來描繪互聯(lián)網(wǎng)的結(jié)構(gòu)^[1，3]。無論將互聯(lián)網(wǎng)中的路由器定義為節(jié)點(diǎn)，路由器之間的通信鏈路定義為連接節(jié)點(diǎn)的邊，還是將互聯(lián)網(wǎng)中的子域定義為節(jié)點(diǎn)，域間連接定義為連接節(jié)點(diǎn)的邊， 互聯(lián)網(wǎng)節(jié)點(diǎn)的度都在雙對(duì)數(shù)坐標(biāo)圖中呈現(xiàn)明顯的線性分布。盡管隨著時(shí)間的推移，系統(tǒng)中的節(jié)點(diǎn)和邊在不斷增加，但網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)特性卻不會(huì)發(fā)生很大的變化。

冪律分布也稱為無標(biāo)度分布，具有冪律分布的網(wǎng)絡(luò)也稱為無標(biāo)度網(wǎng)絡(luò)^[4]。本文研究病毒在無標(biāo)度網(wǎng)絡(luò)上的傳播及其控制，通過仿真得到了一些有意義的結(jié)論。

本文利用如上所述的無標(biāo)度網(wǎng)絡(luò)生成算法生成一個(gè)具有1 000個(gè)節(jié)點(diǎn)，平均度為4的無標(biāo)度網(wǎng)絡(luò)。其度分布如圖1所示。在圖1中，節(jié)點(diǎn)度大于平均度4的節(jié)點(diǎn)占節(jié)點(diǎn)總數(shù)的19．0%，不妨定義這類節(jié)點(diǎn)為A類節(jié)點(diǎn)。顯然在A類節(jié)點(diǎn)中，包含了在無標(biāo)度網(wǎng)絡(luò)中被稱為集散節(jié)點(diǎn)的節(jié)點(diǎn)。節(jié)點(diǎn)度小于等于平均度4的節(jié)點(diǎn)占節(jié)點(diǎn)總數(shù)的81．0%，不妨定義這類節(jié)點(diǎn)為B類節(jié)點(diǎn)。由圖1可直觀地看見該仿真網(wǎng)絡(luò)的度分布服從冪律分布。

2病毒傳播仿真

病毒在無尺度網(wǎng)絡(luò)上的傳播受到很多因素影響。其中初始感染節(jié)點(diǎn)位置、免疫策略、節(jié)點(diǎn)的抗病毒能力對(duì)病毒傳播的影響尤為顯著。因此在這里主要考慮與仿真初始感染節(jié)點(diǎn)位置、免疫策略、節(jié)點(diǎn)的抗病毒能力這三種因素對(duì)病毒傳播的影響。初始時(shí)刻網(wǎng)絡(luò)中的節(jié)點(diǎn)均處于易感染狀態(tài)，病毒從其產(chǎn)生源出發(fā)，沿網(wǎng)絡(luò)連接向四周傳播。

2．1初始感染節(jié)點(diǎn)位置對(duì)病毒傳播的影響

在這里，討論病毒源為A類節(jié)點(diǎn)和B類節(jié)點(diǎn)兩種情況下病毒傳播仿真，如圖2所示。

由圖2可以看到，網(wǎng)絡(luò)病毒在無標(biāo)度網(wǎng)絡(luò)上的傳播與初始感染節(jié)點(diǎn)的位置關(guān)系密切。當(dāng)初始感染節(jié)點(diǎn)為節(jié)點(diǎn)度較小的B類節(jié)點(diǎn)時(shí)，傳播時(shí)間是七個(gè)單位時(shí)間；當(dāng)初始感染節(jié)點(diǎn)為度較大的類A節(jié)點(diǎn)時(shí)，平均傳播速度增加約一倍，傳播時(shí)間減少了近一半，約為四個(gè)單位時(shí)間。因此，可以說，防止度較大的節(jié)點(diǎn)成為病毒源是防止病毒快速傳播的第一步，尤其是防止集散節(jié)點(diǎn)成為病毒源，可以有效地延緩病毒的擴(kuò)散，為進(jìn)一步采取措施控制、消滅病毒大面積的傳播贏得時(shí)間。

2．2不同的免疫策略對(duì)病毒傳播的影響

免疫是抑制計(jì)算機(jī)病毒的一種重要方法。免疫節(jié)點(diǎn)是指當(dāng)病毒傳播到該節(jié)點(diǎn)時(shí)，該節(jié)點(diǎn)既不會(huì)被病毒感染，也不會(huì)將病毒向其他節(jié)點(diǎn)傳播。對(duì)網(wǎng)絡(luò)節(jié)點(diǎn)進(jìn)行免疫，既可以防止被免疫的節(jié)點(diǎn)感染病毒，又可以隔斷病毒通過該節(jié)點(diǎn)感染其他節(jié)點(diǎn)。所以，可以看做是從網(wǎng)絡(luò)中刪除該節(jié)點(diǎn)。較好的免疫策略應(yīng)該是在對(duì)較少的節(jié)點(diǎn)進(jìn)行免疫的情況下，能夠最大程度地延緩病毒的傳播，為消滅病毒贏得時(shí)間。目前，主要有隨機(jī)免疫和選擇免疫兩種免疫策略^[6]。隨機(jī)免疫不考慮節(jié)點(diǎn)間的差別，對(duì)所有的節(jié)點(diǎn)平等對(duì)待，進(jìn)行免疫時(shí)隨機(jī)地選擇節(jié)點(diǎn)，沒有優(yōu)先順序。選擇免疫多為根據(jù)某一標(biāo)準(zhǔn)有選擇地取一類節(jié)點(diǎn)進(jìn)行免疫，以達(dá)到最好的免疫效果。下面筆者對(duì)病毒傳播過程中，對(duì)不采取任何免疫策略、隨機(jī)免疫策略和選擇免疫策略三種情況進(jìn)行仿真分析，仿真結(jié)果如圖3所示。這里選擇免疫原則是度大的節(jié)點(diǎn)優(yōu)先進(jìn)行免疫。在兩種免疫策略下分別選擇3%的節(jié)點(diǎn)進(jìn)行免疫。

由圖3可以看出，不采取任何免疫策略，病毒用六個(gè)單位時(shí)間感染了99．2%的節(jié)點(diǎn)；用七個(gè)單位時(shí)間感染了所有的節(jié)點(diǎn)；采取隨機(jī)免疫策略，病毒傳播用六個(gè)單位時(shí)間感染了95．9%的節(jié)點(diǎn)，也是用七個(gè)單位時(shí)間感染了所有的節(jié)點(diǎn)；采取選擇免疫策略，病毒傳播花費(fèi)13個(gè)單位時(shí)間感染了90．2%的節(jié)點(diǎn)，最終也是感染了90．2%的節(jié)點(diǎn)?？梢姡扇‰S機(jī)免疫策略，傳播時(shí)間未發(fā)生明顯地變化，傳播速度略微減小；采取選擇免疫策略，傳播時(shí)間延長近一倍，傳播速度顯著降低。

2．3節(jié)點(diǎn)的抗病毒能力對(duì)病毒傳播的影響

在這里不妨以電子郵件病毒傳播為例說明節(jié)點(diǎn)的抗病毒能力對(duì)病毒傳播的影響。在電子郵件病毒傳播過程中，用戶總在定期地檢查他們的電子郵件。當(dāng)一位用戶檢查信箱并且遇到帶病毒附件的郵件時(shí)，他有可能丟棄這封信(如果對(duì)這封信表示懷疑或者反病毒軟件檢測(cè)出該信帶有病毒) ，也有可能打開這封信的附件。而打開概率則由用戶關(guān)于電子郵件病毒的知識(shí)和意識(shí)所決定。打開概率可以看成節(jié)點(diǎn)的抗病毒能力，打開概率越大，相當(dāng)于該節(jié)點(diǎn)的抗病毒能力越弱；打開概率越小，相當(dāng)于該節(jié)點(diǎn)的抗病毒能力越強(qiáng)。當(dāng)然每個(gè)節(jié)點(diǎn)的抗病毒能力是不同的。這里可看成是平均抗病毒能力。節(jié)點(diǎn)具備不同抗病毒能力對(duì)病毒傳播的影響如圖4所示。

由圖4可以看出，當(dāng)每個(gè)節(jié)點(diǎn)具備60%的抗病毒能力時(shí)，病毒傳播時(shí)間延長一倍，傳播范圍降低至43．3%；當(dāng)每個(gè)節(jié)點(diǎn)具備70%的抗病毒能力時(shí)，病毒傳播時(shí)間延長一倍，傳播范圍降低至8．34%。對(duì)于電子郵件病毒傳播來說，也就是提高用戶的警惕和防病毒能力。當(dāng)用戶打開帶有病毒的附件的平均概率降低到30%時(shí)，可以本質(zhì)性地抑制病毒的廣泛傳播。

2．4病毒傳播預(yù)防控制仿真

病毒在網(wǎng)絡(luò)中傳播時(shí)，筆者對(duì)初始感染節(jié)點(diǎn)位置、免疫策略、節(jié)點(diǎn)的抗病毒能力（用戶的警惕和防病毒能力）對(duì)病毒傳播速度和范圍的影響分別進(jìn)行了仿真分析。從仿真結(jié)果可以看出初始感染節(jié)點(diǎn)位置、免疫策略、節(jié)點(diǎn)的抗病毒能力分別對(duì)病毒傳播的影響。以下綜合分析病毒傳播受這三種因素共同影響的仿真?？紤]到免疫的節(jié)點(diǎn)不可能占有總節(jié)點(diǎn)數(shù)太大的比例，否則會(huì)增加太大的人為工作量；節(jié)點(diǎn)的抗病毒能力也不可能太高，要求所有節(jié)點(diǎn)具有很高的平均抗病毒能力也是不現(xiàn)實(shí)的。因此筆者選取以下各種因素值：病毒源避免是節(jié)點(diǎn)度較大的A類節(jié)點(diǎn)；根據(jù)度大的節(jié)點(diǎn)進(jìn)行優(yōu)先免疫的原則分別選擇2%、4%的節(jié)點(diǎn)進(jìn)行免疫；節(jié)點(diǎn)分別具有40%、50%、60%的抗病毒能力。病毒傳播的仿真圖如圖5、6所示。

圖5中當(dāng)節(jié)點(diǎn)的平均抗病毒能力為40%時(shí)，病毒的傳播范圍被控制在43．59%；當(dāng)節(jié)點(diǎn)的平均抗病毒能力為50%時(shí)，病毒的傳播范圍被控制在21．75%；當(dāng)節(jié)點(diǎn)的平均抗病毒能力為60%時(shí)，病毒的傳播范圍被控制在3．63%。圖6中當(dāng)節(jié)點(diǎn)的平均抗病毒能力為40%時(shí)，病毒的傳播范圍被控制在20．10%；當(dāng)節(jié)點(diǎn)的平均抗病毒能力為50%時(shí)，病毒的傳播范圍被控制在1．70%；當(dāng)節(jié)點(diǎn)的平均抗病毒能力為60%時(shí)，病毒的傳播范圍被控制在0．47%?？梢?，在合理的范圍內(nèi)提高免疫節(jié)點(diǎn)的百分比，增強(qiáng)節(jié)點(diǎn)的抗病毒能力，可以有效地預(yù)防和控制病毒傳播的范圍。

3結(jié)束語

互聯(lián)網(wǎng)表現(xiàn)出很強(qiáng)的冪律分布特點(diǎn)，本文通過構(gòu)建一個(gè)無標(biāo)度仿真網(wǎng)絡(luò)，研究了病毒在該網(wǎng)絡(luò)上的傳播行為及其影響因素。仿真實(shí)驗(yàn)表明，避免度較大的節(jié)點(diǎn)，尤其是集散節(jié)點(diǎn)成為病毒源；合理地選擇免疫節(jié)點(diǎn)，提高每個(gè)節(jié)點(diǎn)的抗病毒能力，可以最大程度地預(yù)防和控制病毒的傳播。這對(duì)于防范計(jì)算機(jī)病毒在互聯(lián)網(wǎng)上的傳播，具有很重要的現(xiàn)實(shí)意義。

參考文獻(xiàn)：

[1]FALOUTSOS M， FALOUTSOS P， FALOUTSOS C. On power－law relationships of the Internet topology[J]. Computer Communication Review， 1999，29(4):251-262.

[2]VZQUEZ A， PASTOR－SATORRAS R， VESPIGNANI A. Large－scale topological and dynamical properties of the Internet[EB/OL].(2002).http://arxiv.org/abs/cond－mat/0112400.

[3]CHEN Guan－rong， FAN Zheng－ping， LI Xiang. Modelling the complex Internet topology[C]//Proc of Complex Dynamics in Communication Networks. Berlin: Springer－Verlag， 2004.

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

[5]BARABASI A L， ALBERT R. Emergence of scaling in random networks[J]. Science， 1999，286(5439):509-512.

[6]PASTOR－SATORRAS R， VESPIGNANI A. Epidemic spreading in scale－free networks[J]. Physical Review Letters， 2001，86:3200-3203.

“本文中所涉及到的圖表、注解、公式等內(nèi)容請(qǐng)以PDF格式閱讀原文”