賈志娟 楊艷艷 郭 娜

（鄭州師范學院 鄭州 450044）

基于復雜網(wǎng)絡的計算機病毒求源問題研究?

賈志娟 楊艷艷 郭 娜

（鄭州師范學院 鄭州 450044）

當前計算機病毒方向的研究主要是在病毒傳播特性方面，對病毒求源問題鮮有人提出，而計算機病毒求源問題能夠為人們還原其傳播過程并為快速控制病源提供幫助，因此，文章主要針對病毒求源問題建模，通過觀察網(wǎng)絡各個節(jié)點狀態(tài)，實現(xiàn)對病毒源頭的定位。首先，依據(jù)實際網(wǎng)絡連接情況，建立一個復雜網(wǎng)絡病毒求源模型；其次，利用網(wǎng)絡時序狀態(tài)矩陣模擬由計算機病毒傳播而引起的網(wǎng)絡節(jié)點狀態(tài)變化情況，并通過分析，給出一個網(wǎng)絡狀態(tài)轉換過程，該過程就是病毒傳播路徑的逆過程，初始狀態(tài)病毒節(jié)點即為病源；最后，文章通過仿真實驗，驗證上述模型的正確性和有效性，為以后計算機病毒求源問題研究和控制病毒傳播提供依據(jù)。

復雜網(wǎng)絡；計算機病毒；求源問題；傳播路徑

1 引言

隨著網(wǎng)絡技術的快速發(fā)展，計算機網(wǎng)絡已成為人們社會生活中不可缺少的一部分，人們可以利用網(wǎng)絡進行信息交流、辦公、娛樂等各種社會活動。然而，網(wǎng)絡也為計算機病毒的傳播提供了新的平臺。計算機病毒在網(wǎng)絡上的傳播已給互聯(lián)網(wǎng)造成了巨大的威脅，成為網(wǎng)絡上最大的安全隱患［1～3］。因此，分析計算機病毒的網(wǎng)絡傳播特性和病源特征，并提出有效的防御策略已成為當前網(wǎng)絡信息安全領域的一個首要任務。

目前，人們在計算機病毒防治方面進行了大量的研究工作，提出了許多防病毒、反病毒、查病毒的策略和技術。例如，顧?？　⑹Y國平、夏玲玲等利用穩(wěn)態(tài)分析理論推導計算機網(wǎng)絡中病毒的傳播臨界值，同時利用蒙特卡羅方法分析均勻網(wǎng)絡和非均勻網(wǎng)絡的病毒傳播臨界值，獲知病毒傳播臨界值更加接近真實蒙特卡羅值，并且與免疫喪失率無關［4］。Mishra B K，Saini D等在文獻［5］中列舉出計算機病毒不同情況下的傳播數(shù)學模型。王維、張鵬濤、譚營、何新貴等提出了一種基于人工免疫的利用計算機病毒代碼相關性的計算機病毒特征提取方法，提高對病毒的識別能力［6］。胡慶成，尹龑燊等主要研究網(wǎng)絡中最具影響力的傳播節(jié)點，提出KSC（K-shell and community centrality）指標模型，此模型不但考慮了節(jié)點的內部屬性，而且還綜合考慮了節(jié)點的外部屬性，使得尋找到的節(jié)點精度高［7］。陳旭輝、李塵、柯銘等從網(wǎng)絡中節(jié)點在病毒免疫過程中存在差異性和非近鄰傳播特性對病毒傳播的影響出發(fā)，提出一類新的具有個體差異性和非近鄰傳播特性的SIRS模型［8］。但是，以上技術都沒有涉及計算機病毒傳播源頭，并且沒有考慮到從病毒源頭切斷其傳播路徑，從而來控制計算機病毒。

本文利用復雜網(wǎng)絡模擬實際生活中計算機病毒傳播模式，并探索出控制和根除計算機病毒源頭的最優(yōu)策略。研究學者對大量實際網(wǎng)絡做了實證性研究，發(fā)現(xiàn)實際網(wǎng)絡具有小世界特性和無標度特性［9～11］，因此，選擇復雜網(wǎng)絡給實際網(wǎng)絡建模，比其他模型能夠相對準確地刻畫網(wǎng)絡結構特征。首先依據(jù)現(xiàn)實世界中網(wǎng)絡節(jié)點連接情況，建立一個復雜網(wǎng)絡病毒求源模型；其次，利用網(wǎng)絡時序狀態(tài)矩陣模擬由計算機病毒傳播而引起的網(wǎng)絡節(jié)點狀態(tài)變化情況，提出一個網(wǎng)絡狀態(tài)轉換過程，從而求出網(wǎng)絡中計算機病毒源頭，有效防治計算機病毒傳播。

2 計算機病毒求源問題建模

1）計算機病毒傳播網(wǎng)絡圖

本文利用復雜網(wǎng)絡對網(wǎng)絡中的計算機病毒傳播進行建模，在該模型中，計算機病毒的傳播過程就是一個隨時間變化的節(jié)點狀態(tài)轉換矩陣。這里令實際網(wǎng)絡為一無向圖，描述為G(V，E)，其中V為網(wǎng)絡中節(jié)點的集合，代表網(wǎng)絡中各種設備集合，即網(wǎng)絡節(jié)點V={v1，v2，…，vn}；E 為網(wǎng)絡中邊的集合，代表網(wǎng)絡中設備之間的連接情況，若設備節(jié)點之間直接相連，則其之間存在一條無向邊，即(vi，vj)∈E。圖1為計算機病毒求源問題網(wǎng)絡模型。

計算機間物理連接是計算機病毒傳播的必要條件，本文用連接矩陣En×n描述網(wǎng)絡的連接情況，

圖1 計算機病毒傳播網(wǎng)絡模型

對于計算機網(wǎng)絡中任一感染節(jié)點，存在多條從計算機病源節(jié)點傳遞至本身節(jié)點的路徑，在此定義從計算機病源到當前被病毒感染節(jié)點的路徑是一條病毒傳播路徑。例如在圖1中，從計算機病源d到被感染節(jié)點 f之間存在多條傳播路徑，即d-b-f，d-c-f，d-b-c-f，d-c-b-f，d-b-g-f，d-c-j-k-f。根據(jù)計算機病毒在網(wǎng)絡中的傳播路徑，找出網(wǎng)絡中計算機病源。

2）病毒感染狀態(tài)向量

利用SIR模型［12～13］研究計算機病毒在網(wǎng)絡中的傳播特性。在圖G中查找病毒源，節(jié)點主要有三種狀態(tài)：（1）易感染S態(tài)，表示該節(jié)點沒有被計算機病毒感染，但是有可能會被計算機病毒感染；（2）感染狀態(tài)I態(tài)，表示該節(jié)點已被計算機病毒感染，并且能夠傳播計算機病毒到其他節(jié)點；（3）免疫狀態(tài)R態(tài)，表示該節(jié)點上的計算機病毒已被查毒程序移除，不會再感染同一種計算機病毒，且不會傳播計算機病毒，也稱為移除狀態(tài)。假設易感染節(jié)點被感染的概率為β，感染節(jié)點病毒清楚的概率為γ，SIR病毒傳播模型表示如圖2所示。

圖2 SIR病毒傳播模型

通過以上分析，網(wǎng)絡節(jié)點V={v1，v2，…，vn}在 t時刻網(wǎng)絡計算機病毒感染狀態(tài)向量表示為St={s1，s2，…，sn}T，其中 si=0 表示網(wǎng)絡中的第 i臺計算機未被病毒感染；si=1表示網(wǎng)絡中的第i臺計算機已被病毒感染。這里，網(wǎng)絡中S態(tài)，R態(tài)定義為未被感染狀態(tài)。

3）免疫狀態(tài)向量

本文采用免疫狀態(tài)向量存儲網(wǎng)絡中已經(jīng)被殺過毒的計算機節(jié)點，假設只要某一節(jié)點的計算機病毒被清除之后，該節(jié)點就會具有免疫性質，不會感染上同一種計算機病毒。令Kt表示t時刻網(wǎng)絡中各個節(jié)點的病毒免疫情況，K={k1，k2，…，kn}，其中，ki=0表示網(wǎng)絡中的第i臺計算機的病毒已被清除且具備免疫功能，也說明該節(jié)點曾感染過計算機病毒；ki=1表示網(wǎng)絡中的第i臺計算機的病毒不具備免疫功能。

4）網(wǎng)絡時序狀態(tài)矩陣

本文將計算機病毒在時刻t到t+1間網(wǎng)絡的傳播狀態(tài)表示為網(wǎng)絡時序狀態(tài)矩陣，表示為Un×n，刻畫了計算機病毒在網(wǎng)絡中的傳播情況和傳播方向，uij表示從時刻t到時刻t+1間計算機節(jié)點vi是否感染了計算機節(jié)點vj，若uij取值為0，表示計算機節(jié)點vi未感染計算機節(jié)點vj；uij取值為1，表示計算機節(jié)點vi已感染計算機節(jié)點vj，其中，

5）計算機病毒傳播過程

在計算機病毒傳播網(wǎng)絡圖基礎上，定義了網(wǎng)絡時序狀態(tài)矩陣和病毒感染狀態(tài)向量后，可以用公式模擬計算機病毒傳播過程。首先，利用式（1）計算時刻t+1網(wǎng)絡內所有計算機的感染狀態(tài)向量St+1；其次，利用式（2）計算t時刻網(wǎng)絡中計算機節(jié)點附加病毒免疫特性，具有免疫特性的節(jié)點不會被再次感染計算機病毒，符號“·”表示對向量St，Kt相對應元素做與運算。

假設網(wǎng)絡初始狀態(tài)的病毒感染狀態(tài)為S0，且能夠獲得不同時刻的病毒轉換過程，從而可以計算出網(wǎng)絡時序狀態(tài)矩陣。將病毒傳播時間段等分為x個時間段，則網(wǎng)絡時序狀態(tài)矩陣，可表示為U1，U2，…，Ux，當前時刻該網(wǎng)絡內計算機病毒感染狀態(tài)過程如下：

在式（3）每一步計算中，需利用式（2）對病毒感染狀態(tài)向量做病毒免疫特性附加計算，進而迭代傳播。

3 計算機病毒求源過程

通過上述分析，已經(jīng)獲知網(wǎng)絡中病毒傳播過程及表示方法，而病毒求源過程就是病毒傳播過程的逆過程，因此，計算機病毒求源問題就是對式（3）求解的過程，最后得到S0的值，即網(wǎng)絡節(jié)點的初始狀態(tài)，其中狀態(tài)值為1的節(jié)點就是病源。式（4）是病毒求源過程，需注意的是，病源并不唯一，也許有多個病源。

同樣，該公式計算中，需要利用式（5）對病毒感染狀態(tài)向量做病毒免疫特性清除計算，進而迭代求源。具體步驟如下：首先，對當前時刻免疫狀態(tài)向量Kt各元素取反，其次，與病毒感染狀態(tài)向量St相對應元素進行或運算，所得結果向量即為清除節(jié)點免疫特性后的病毒感染情況，符號“|”表示對向量St，Kt'相對應元素做或運算。

4 仿真實驗

本文構建具有20個設備節(jié)點的局域網(wǎng)，抓取局域網(wǎng)中所有連接的數(shù)據(jù)包。因為病毒數(shù)據(jù)包一定在該網(wǎng)絡中傳播，所以我們抓取所有流經(jīng)局域網(wǎng)內的數(shù)據(jù)包必包含病毒數(shù)據(jù)包。本文將抓取到的所有數(shù)據(jù)包通過解析數(shù)據(jù)包連接信息，獲知病毒數(shù)據(jù)包的具體傳播路徑，構造網(wǎng)絡時序狀態(tài)矩陣，并記錄病毒數(shù)據(jù)包傳播過程中的節(jié)點免疫信息，構造免疫狀態(tài)向量，從而構建一個完整的病毒傳播狀態(tài)轉換過程。

實驗要求每隔3個小時采集一次數(shù)據(jù)包，因為抓取數(shù)據(jù)包的周期過長，可能會搜集不到足夠有價值的信息，并且選擇VBS腳本病毒，使得對網(wǎng)絡中計算機的危害盡可能的小。

為了抓取網(wǎng)絡數(shù)據(jù)包以及感染計算機情況，主要有以下五個步驟：1）抓取流經(jīng)該網(wǎng)絡的所有數(shù)據(jù)包；2）對抓取數(shù)據(jù)包的連接信息進行解析，并導入數(shù)據(jù)庫；3）依據(jù)連接信息建立網(wǎng)絡連接矩陣；4）計算獲得不同時間段的節(jié)點免疫信息和網(wǎng)絡時序狀態(tài)矩陣；5）依據(jù)網(wǎng)絡時序狀態(tài)矩陣定位該網(wǎng)絡的計算機病毒。

在實驗過程中，需在不同時刻記錄一個病毒源傳播情況統(tǒng)計信息。

圖3模擬了一個病毒源的傳播過程，其中實線節(jié)點表示已感染節(jié)點，虛線節(jié)點表示該節(jié)點已進行了清毒措施，并且在后來也沒有被感染。

圖3 一個病毒源的傳播過程

表1 一個病毒求源情況表

表1中，t0～t6時間點是實驗采集數(shù)據(jù)的時刻，而t0是在網(wǎng)絡中植入計算機病毒的時刻。可以看出，網(wǎng)絡中b節(jié)點是子網(wǎng)中的唯一毒源，r，x，e節(jié)點分別在第t4，t3，t5時刻進行了清毒措施。試驗中t0時刻，感染計算機病毒的節(jié)點即為病源節(jié)點，因此，可以獲知，該網(wǎng)絡的計算機病源是b節(jié)點。

5 結語

本文基于復雜網(wǎng)絡給出了網(wǎng)絡中計算機病毒求源過程，病毒求源過程可以看成病毒傳播過程的逆過程，認為病毒傳播路徑的初始點即為病源。通過抓取網(wǎng)絡內病毒數(shù)據(jù)包的傳播信息，創(chuàng)建計算機病毒求源模型，即創(chuàng)建網(wǎng)絡時序狀態(tài)矩陣和免疫狀態(tài)向量，結合實際網(wǎng)絡情況反復求解網(wǎng)絡時序狀態(tài)矩陣的逆運算，直到獲得網(wǎng)絡初始狀態(tài)的病毒感染狀態(tài)向量，初始狀態(tài)病毒感染節(jié)點就為病毒源。文章對模型進行了仿真實驗，實驗證明該理論模型的正確性和有效性，為以后計算機病毒求源問題研究和控制病毒傳播提供依據(jù)。

但是該模型對網(wǎng)絡中病毒的傳播路徑刻畫相對簡單，并沒有考慮到網(wǎng)絡節(jié)點數(shù)目、病毒變異等因素對病毒傳播的影響，只是對病毒求源問題做了初步的描述，因此，綜合考慮計算機病毒傳播特性，改進病毒求源模型，使其更加符合實際，是我們進一步要做的工作。

［1］葉曉夢，楊小帆.基于兩階段免疫接種的SIRS計算機病毒傳播模型［J］.計算機應用，2013，33（3）：739-742.YE Xiaomeng，YANG Xiaofan.SIRS model of computer vi?rus propagation based on two-stage immunization［J］.Journal of Computer Applications，2013，33（3）：739-742.

［2］Muroya Y，Enatsu Y，Li H.Global stability of a delayed SIRS computer virus propagation model［J］.International Journal of Computer Mathematics，2014，91（3）：347-367.

［3］Gan C，Yang X，Liu W，et al.Propagation of computer vi?rus both across the Internet and external computers：A complex-network approach［J］.Communications in Non?linear Science&Numerical Simulation，2014，19（8）：2785-2792.

［4］顧?？?，蔣國平，夏玲玲.基于狀態(tài)概率轉移的SIRS病毒傳播模型及其臨界值分析［J］.計算機科學，2016，43（s1）：64-67.GU Haijun，JIANG Guoping，XIA Lingling.SIRS Epidem?ic Model and its Threshold Based on State Transition Prob?ability［J］.Computer Science，2016，43（s1）：64-67.

［5］Mishra B K，Saini D.Mathematical models on computer viruses［J］.Applied Mathematics&Computation，2013，187（2）：929-936.

［6］王維，張鵬濤，譚營，等.一種基于人工免疫和代碼相關性的計算機病毒特征提取方法［J］.計算機學報，2011，34（2）：204-215.WANG Wei，ZHANG Pengtao，TAN Ying，et al.A Feature Extraction Method of Computer Viruses Based on Artifi?cial Immune and Code Relevance［J］.Chinese Journal of Computers，2011，34（2）：204-215.

［7］胡慶成，尹龑燊，馬鵬斐，等.一種新的網(wǎng)絡傳播中最有影響力的節(jié)點發(fā)現(xiàn)方法［J］.物理學報，2013，62（14）：140101-140101.HU Qingcheng，YIN Yanshen，MA Pengfei，et al.A new approach to identify influential spreaders in complex net?works［J］.Acta Physica Sinica，2013，62 （14） ：140101-140101.

［8］陳旭輝，李塵，柯銘.一類具有個體差異性和非近鄰傳播特性的SIRS計算機病毒傳播模型［J］.計算機應用與軟件，2013，30（5）：15-19.CHEN Xuhui，LI Chen，KE Ming.A Model of SIRS Com?puter Virus Spreading with Individual Differences and Non-Nearest Neighbour Propacation［J］.Computer Appli?cations and Software，2013，30（5）：15-19.

［9］Pinto C M A，Machado J A T.Fractional Dynamics of Com?puter Virus Propagation［J］.Mathematical Problems in En?gineering，2014，2014（2-3）：259-305.

［10］馮麗萍，王鴻斌，馮素琴.改進的SIR計算機病毒傳播模型［J］.計算機應用，2011，31（7）：1891-1893.FENG Liping，WANG Hongbin，F(xiàn)ENG Suqin.Improved SIR model of computer virus propagation in the network［J］.Journal of Computer Applications，2011，31（7）：1891-1893.

［11］胡明生，賈志娟，雷利利.基于復雜網(wǎng)絡的災害關聯(lián)建模 與 分 析［J］.計 算 機 應 用 研 究 ，2013，30（8）：2315-2318.HU Mingsheng，JIA Zhijuan，LEI Lili.Modeling and analysis of disasters relationship based on complex net?work［J］.Application Research of Computers，2013，30（8）：2315-2318.

［12］張道祥，李迅.非連續(xù)免疫策略對計算機病毒SIR模型的影響［J］.應用科學學報，2016（3）：329-338.ZHANG Daoxiang，LI Xun.Impact of Discontinuous Im?munity on SIR Computer Virus Model［J］.Journal of Ap?plied Sciences，2016（3）：329-338.

［13］胡明生，賈遂民，陳巧靈，等.基于常數(shù)輸入的蠕蟲傳播模型及其分析［J］.計算機工程與科學，2014，36（8）：1482-1485.HU Mingsheng，JIA Suimin，CHEN Qiaoling，et al.Anal?ysis of the worm propagation model with constant immi?gration［J］.Computer Engineering and Science，2014，36（8）：1482-1485.

Research on the Tracing Source of Computer Virus Based on Complex Network

JIA Zhijuan YANG Yanyan GUO Na
（Zhengzhou Normal University，Zhengzhou 450044）

At present，the research of computer virus is mainly in the aspects of virus spreading，but the source of the virus is rarely raised.The computer virus source problem can help people to restore the communication process and provide help for the rap?id control of disease.Therefore，this paper mainly focuses on the virus to tracing the source problem to model，through the observa?tion network each node status，realizes to the virus source localization.Firstly，according to the actual network connection，this pa?per builds a complex network virus source model；Secondly，the state of the network nodes caused by the propagation of computer vi?rus is simulated by using the state matrix of the network time sequence.Through the analysis，a network state transition process is given，which is the inverse process of the virus transmission path.The initial state of node is the source of virus.Finally，this paper through the simulation experiment，verify the correctness and validity of the model，and provide the basis for the future research and control of virus transmission.

complex network，computer virus，tracing source of virus，spreading path

Class Number TP309

TP309

10.3969/j.issn.1672-9722.2017.12.028

2017年6月13日，

2017年7月22日

國家自然科學基金項目“基于復雜網(wǎng)絡的傳染病溯源方法研究”（編號：U1304614）。

賈志娟，女，博士，教授，研究方向：數(shù)據(jù)挖掘、復雜網(wǎng)絡。楊艷艷，女，碩士，講師，研究方向：數(shù)據(jù)挖掘。郭娜，女，助教，研究方向：軟件工程。