基于复杂网络的计算机病毒求源问题研究∗

贾志娟 杨艳艳 郭 娜

（郑州师范学院 郑州 450044）

基于复杂网络的计算机病毒求源问题研究∗

贾志娟 杨艳艳 郭 娜

（郑州师范学院 郑州 450044）

当前计算机病毒方向的研究主要是在病毒传播特性方面，对病毒求源问题鲜有人提出，而计算机病毒求源问题能够为人们还原其传播过程并为快速控制病源提供帮助，因此，文章主要针对病毒求源问题建模，通过观察网络各个节点状态，实现对病毒源头的定位。首先，依据实际网络连接情况，建立一个复杂网络病毒求源模型；其次，利用网络时序状态矩阵模拟由计算机病毒传播而引起的网络节点状态变化情况，并通过分析，给出一个网络状态转换过程，该过程就是病毒传播路径的逆过程，初始状态病毒节点即为病源；最后，文章通过仿真实验，验证上述模型的正确性和有效性，为以后计算机病毒求源问题研究和控制病毒传播提供依据。

复杂网络；计算机病毒；求源问题；传播路径

1 引言

随着网络技术的快速发展，计算机网络已成为人们社会生活中不可缺少的一部分，人们可以利用网络进行信息交流、办公、娱乐等各种社会活动。然而，网络也为计算机病毒的传播提供了新的平台。计算机病毒在网络上的传播已给互联网造成了巨大的威胁，成为网络上最大的安全隐患［1～3］。因此，分析计算机病毒的网络传播特性和病源特征，并提出有效的防御策略已成为当前网络信息安全领域的一个首要任务。

目前，人们在计算机病毒防治方面进行了大量的研究工作，提出了许多防病毒、反病毒、查病毒的策略和技术。例如，顾海俊、蒋国平、夏玲玲等利用稳态分析理论推导计算机网络中病毒的传播临界值，同时利用蒙特卡罗方法分析均匀网络和非均匀网络的病毒传播临界值，获知病毒传播临界值更加接近真实蒙特卡罗值，并且与免疫丧失率无关［4］。Mishra B K，Saini D等在文献［5］中列举出计算机病毒不同情况下的传播数学模型。王维、张鹏涛、谭营、何新贵等提出了一种基于人工免疫的利用计算机病毒代码相关性的计算机病毒特征提取方法，提高对病毒的识别能力［6］。胡庆成，尹龑燊等主要研究网络中最具影响力的传播节点，提出KSC（K-shell and community centrality）指标模型，此模型不但考虑了节点的内部属性，而且还综合考虑了节点的外部属性，使得寻找到的节点精度高［7］。陈旭辉、李尘、柯铭等从网络中节点在病毒免疫过程中存在差异性和非近邻传播特性对病毒传播的影响出发，提出一类新的具有个体差异性和非近邻传播特性的SIRS模型［8］。但是，以上技术都没有涉及计算机病毒传播源头，并且没有考虑到从病毒源头切断其传播路径，从而来控制计算机病毒。

本文利用复杂网络模拟实际生活中计算机病毒传播模式，并探索出控制和根除计算机病毒源头的最优策略。研究学者对大量实际网络做了实证性研究，发现实际网络具有小世界特性和无标度特性［9～11］，因此，选择复杂网络给实际网络建模，比其他模型能够相对准确地刻画网络结构特征。首先依据现实世界中网络节点连接情况，建立一个复杂网络病毒求源模型；其次，利用网络时序状态矩阵模拟由计算机病毒传播而引起的网络节点状态变化情况，提出一个网络状态转换过程，从而求出网络中计算机病毒源头，有效防治计算机病毒传播。

2 计算机病毒求源问题建模

1）计算机病毒传播网络图

本文利用复杂网络对网络中的计算机病毒传播进行建模，在该模型中，计算机病毒的传播过程就是一个随时间变化的节点状态转换矩阵。这里令实际网络为一无向图，描述为G(V，E)，其中V为网络中节点的集合，代表网络中各种设备集合，即网络节点V={v1，v2，…，vn}；E 为网络中边的集合，代表网络中设备之间的连接情况，若设备节点之间直接相连，则其之间存在一条无向边，即(vi，vj)∈E。图1为计算机病毒求源问题网络模型。

计算机间物理连接是计算机病毒传播的必要条件，本文用连接矩阵En×n描述网络的连接情况，

图1 计算机病毒传播网络模型

对于计算机网络中任一感染节点，存在多条从计算机病源节点传递至本身节点的路径，在此定义从计算机病源到当前被病毒感染节点的路径是一条病毒传播路径。例如在图1中，从计算机病源d到被感染节点 f之间存在多条传播路径，即d-b-f，d-c-f，d-b-c-f，d-c-b-f，d-b-g-f，d-c-j-k-f。根据计算机病毒在网络中的传播路径，找出网络中计算机病源。

2）病毒感染状态向量

利用SIR模型［12～13］研究计算机病毒在网络中的传播特性。在图G中查找病毒源，节点主要有三种状态：（1）易感染S态，表示该节点没有被计算机病毒感染，但是有可能会被计算机病毒感染；（2）感染状态I态，表示该节点已被计算机病毒感染，并且能够传播计算机病毒到其他节点；（3）免疫状态R态，表示该节点上的计算机病毒已被查毒程序移除，不会再感染同一种计算机病毒，且不会传播计算机病毒，也称为移除状态。假设易感染节点被感染的概率为β，感染节点病毒清楚的概率为γ，SIR病毒传播模型表示如图2所示。

图2 SIR病毒传播模型

通过以上分析，网络节点V={v1，v2，…，vn}在 t时刻网络计算机病毒感染状态向量表示为St={s1，s2，…，sn}T，其中 si=0 表示网络中的第 i台计算机未被病毒感染；si=1表示网络中的第i台计算机已被病毒感染。这里，网络中S态，R态定义为未被感染状态。

3）免疫状态向量

本文采用免疫状态向量存储网络中已经被杀过毒的计算机节点，假设只要某一节点的计算机病毒被清除之后，该节点就会具有免疫性质，不会感染上同一种计算机病毒。令Kt表示t时刻网络中各个节点的病毒免疫情况，K={k1，k2，…，kn}，其中，ki=0表示网络中的第i台计算机的病毒已被清除且具备免疫功能，也说明该节点曾感染过计算机病毒；ki=1表示网络中的第i台计算机的病毒不具备免疫功能。

4）网络时序状态矩阵

本文将计算机病毒在时刻t到t+1间网络的传播状态表示为网络时序状态矩阵，表示为Un×n，刻画了计算机病毒在网络中的传播情况和传播方向，uij表示从时刻t到时刻t+1间计算机节点vi是否感染了计算机节点vj，若uij取值为0，表示计算机节点vi未感染计算机节点vj；uij取值为1，表示计算机节点vi已感染计算机节点vj，其中，

5）计算机病毒传播过程

在计算机病毒传播网络图基础上，定义了网络时序状态矩阵和病毒感染状态向量后，可以用公式模拟计算机病毒传播过程。首先，利用式（1）计算时刻t+1网络内所有计算机的感染状态向量St+1；其次，利用式（2）计算t时刻网络中计算机节点附加病毒免疫特性，具有免疫特性的节点不会被再次感染计算机病毒，符号“·”表示对向量St，Kt相对应元素做与运算。

假设网络初始状态的病毒感染状态为S0，且能够获得不同时刻的病毒转换过程，从而可以计算出网络时序状态矩阵。将病毒传播时间段等分为x个时间段，则网络时序状态矩阵，可表示为U1，U2，…，Ux，当前时刻该网络内计算机病毒感染状态过程如下：

在式（3）每一步计算中，需利用式（2）对病毒感染状态向量做病毒免疫特性附加计算，进而迭代传播。

3 计算机病毒求源过程

通过上述分析，已经获知网络中病毒传播过程及表示方法，而病毒求源过程就是病毒传播过程的逆过程，因此，计算机病毒求源问题就是对式（3）求解的过程，最后得到S0的值，即网络节点的初始状态，其中状态值为1的节点就是病源。式（4）是病毒求源过程，需注意的是，病源并不唯一，也许有多个病源。

同样，该公式计算中，需要利用式（5）对病毒感染状态向量做病毒免疫特性清除计算，进而迭代求源。具体步骤如下：首先，对当前时刻免疫状态向量Kt各元素取反，其次，与病毒感染状态向量St相对应元素进行或运算，所得结果向量即为清除节点免疫特性后的病毒感染情况，符号“|”表示对向量St，Kt'相对应元素做或运算。

4 仿真实验

本文构建具有20个设备节点的局域网，抓取局域网中所有连接的数据包。因为病毒数据包一定在该网络中传播，所以我们抓取所有流经局域网内的数据包必包含病毒数据包。本文将抓取到的所有数据包通过解析数据包连接信息，获知病毒数据包的具体传播路径，构造网络时序状态矩阵，并记录病毒数据包传播过程中的节点免疫信息，构造免疫状态向量，从而构建一个完整的病毒传播状态转换过程。

实验要求每隔3个小时采集一次数据包，因为抓取数据包的周期过长，可能会搜集不到足够有价值的信息，并且选择VBS脚本病毒，使得对网络中计算机的危害尽可能的小。

为了抓取网络数据包以及感染计算机情况，主要有以下五个步骤：1）抓取流经该网络的所有数据包；2）对抓取数据包的连接信息进行解析，并导入数据库；3）依据连接信息建立网络连接矩阵；4）计算获得不同时间段的节点免疫信息和网络时序状态矩阵；5）依据网络时序状态矩阵定位该网络的计算机病毒。

在实验过程中，需在不同时刻记录一个病毒源传播情况统计信息。

图3模拟了一个病毒源的传播过程，其中实线节点表示已感染节点，虚线节点表示该节点已进行了清毒措施，并且在后来也没有被感染。

图3 一个病毒源的传播过程

表1 一个病毒求源情况表

表1中，t0～t6时间点是实验采集数据的时刻，而t0是在网络中植入计算机病毒的时刻。可以看出，网络中b节点是子网中的唯一毒源，r，x，e节点分别在第t4，t3，t5时刻进行了清毒措施。试验中t0时刻，感染计算机病毒的节点即为病源节点，因此，可以获知，该网络的计算机病源是b节点。

5 结语

本文基于复杂网络给出了网络中计算机病毒求源过程，病毒求源过程可以看成病毒传播过程的逆过程，认为病毒传播路径的初始点即为病源。通过抓取网络内病毒数据包的传播信息，创建计算机病毒求源模型，即创建网络时序状态矩阵和免疫状态向量，结合实际网络情况反复求解网络时序状态矩阵的逆运算，直到获得网络初始状态的病毒感染状态向量，初始状态病毒感染节点就为病毒源。文章对模型进行了仿真实验，实验证明该理论模型的正确性和有效性，为以后计算机病毒求源问题研究和控制病毒传播提供依据。

但是该模型对网络中病毒的传播路径刻画相对简单，并没有考虑到网络节点数目、病毒变异等因素对病毒传播的影响，只是对病毒求源问题做了初步的描述，因此，综合考虑计算机病毒传播特性，改进病毒求源模型，使其更加符合实际，是我们进一步要做的工作。

［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］顾海俊，蒋国平，夏玲玲.基于状态概率转移的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］胡庆成，尹龑燊，马鹏斐，等.一种新的网络传播中最有影响力的节点发现方法［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，FENG Suqin.Improved SIR model of computer virus propagation in the network［J］.Journal of Computer Applications，2011，31（7）：1891-1893.

［11］胡明生，贾志娟，雷利利.基于复杂网络的灾害关联建模 与 分 析［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］张道祥，李迅.非连续免疫策略对计算机病毒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］胡明生，贾遂民，陈巧灵，等.基于常数输入的蠕虫传播模型及其分析［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日

国家自然科学基金项目“基于复杂网络的传染病溯源方法研究”（编号：U1304614）。

贾志娟，女，博士，教授，研究方向：数据挖掘、复杂网络。杨艳艳，女，硕士，讲师，研究方向：数据挖掘。郭娜，女，助教，研究方向：软件工程。