病毒在無標度網絡上的傳播及控制仿真研究

摘要：網絡病毒的爆發給計算機用戶帶來巨大的損失，同時互聯網被認為是無標度網絡，因此研究病毒在無標度網絡上的傳播及控制很有意義。通過構建一個BA無標度網絡模型，對病毒的傳播行為及影響因素進行了仿真分析。研究表明，采取恰當的策略可以有效地控制、預防病毒傳播。

關鍵詞：網絡病毒； 無標度網絡； 冪律

中圖分類號：TP309文獻標志碼：A

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

0引言

1999年Faloutsos等人^[1]發現，互聯網表現出很強的冪律分布特點，節點的度(某節點的度是指與該節點相連的節點數目，或者說與該節點關聯的邊的數目)有很大的波動性^[1，2]。目前為止主要從兩種不同的角度來描繪互聯網的結構^[1，3]。無論將互聯網中的路由器定義為節點，路由器之間的通信鏈路定義為連接節點的邊，還是將互聯網中的子域定義為節點，域間連接定義為連接節點的邊， 互聯網節點的度都在雙對數坐標圖中呈現明顯的線性分布。盡管隨著時間的推移，系統中的節點和邊在不斷增加，但網絡拓撲結構特性卻不會發生很大的變化。

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

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

2病毒傳播仿真

病毒在無尺度網絡上的傳播受到很多因素影響。其中初始感染節點位置、免疫策略、節點的抗病毒能力對病毒傳播的影響尤為顯著。因此在這里主要考慮與仿真初始感染節點位置、免疫策略、節點的抗病毒能力這三種因素對病毒傳播的影響。初始時刻網絡中的節點均處于易感染狀態，病毒從其產生源出發，沿網絡連接向四周傳播。

2．1初始感染節點位置對病毒傳播的影響

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

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

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

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

由圖3可以看出，不采取任何免疫策略，病毒用六個單位時間感染了99．2%的節點；用七個單位時間感染了所有的節點；采取隨機免疫策略，病毒傳播用六個單位時間感染了95．9%的節點，也是用七個單位時間感染了所有的節點；采取選擇免疫策略，病毒傳播花費13個單位時間感染了90．2%的節點，最終也是感染了90．2%的節點。可見，采取隨機免疫策略，傳播時間未發生明顯地變化，傳播速度略微減小；采取選擇免疫策略，傳播時間延長近一倍，傳播速度顯著降低。

2．3節點的抗病毒能力對病毒傳播的影響

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

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

2．4病毒傳播預防控制仿真

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

圖5中當節點的平均抗病毒能力為40%時，病毒的傳播范圍被控制在43．59%；當節點的平均抗病毒能力為50%時，病毒的傳播范圍被控制在21．75%；當節點的平均抗病毒能力為60%時，病毒的傳播范圍被控制在3．63%。圖6中當節點的平均抗病毒能力為40%時，病毒的傳播范圍被控制在20．10%；當節點的平均抗病毒能力為50%時，病毒的傳播范圍被控制在1．70%；當節點的平均抗病毒能力為60%時，病毒的傳播范圍被控制在0．47%。可見，在合理的范圍內提高免疫節點的百分比，增強節點的抗病毒能力，可以有效地預防和控制病毒傳播的范圍。

3結束語

互聯網表現出很強的冪律分布特點，本文通過構建一個無標度仿真網絡，研究了病毒在該網絡上的傳播行為及其影響因素。仿真實驗表明，避免度較大的節點，尤其是集散節點成為病毒源；合理地選擇免疫節點，提高每個節點的抗病毒能力，可以最大程度地預防和控制病毒的傳播。這對于防范計算機病毒在互聯網上的傳播，具有很重要的現實意義。

參考文獻：

[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]汪小帆，李翔，陳關榮.復雜網絡理論及其應用[M].北京:清華大學出版社，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.

“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文”