（1.北京理工大学计算机科学与技术学院，北京 100081；
2. 北京理工大学计算机网络攻防对抗技术实验室，北京 100081）

摘 要：鉴于无标度网络的健壮性和小世界特性是蠕虫网络的理想特征,借助于复杂网络理论,提出了一个基于随机游走的蠕虫网络演化模型。该模型依据主机性能和网络的带宽采取择优的方式从蠕虫网络中选择合适的节点与新感染的主机建立连接。理论分析和模拟实验表明：所建立蠕虫网络具有无标度网络的性质。
关键词：计算机科学技术基础学科；蠕虫；随机游走；无标度；平均场理论
中图分类号：TP309.08        文献标识码：A

Research on Worm Network Evolution Based on Random Walkers
CHEN Jun-hua, HU Chang -zhen
( 1. School of Computer Science and Technology, Beijing Institute of Technology, Beijing 100081;
2. Lab for Computer Network Defense Technology, Beijing Institute of Technology, Beijing 100081 )

Abstract: Robustness and small-world property of scale-free network are the desirable features in worm network., a worm evolution model is proposed based on random walkers by the complex network theory. According to host capability and network bandwidth, the model builds a valid connection between a new infected host and the suitable nodes selected from worm network using preferential attachment. Theoretical analysis and simulation experiments show that such network exhibits a power-law distribution of node degree.
Key words: basic disciplines of computer science and technology; worm; random walkers; scale-free; mean-field theory

０引言

    近年来，复杂网络成为迅速发展的一门新兴学科，大量复杂网络的研究成果发表在《Physical Review Letters》、《Physical Review E》和《Physica A 》等物理类期刊以及《Nature》和《Science》等综合性期刊上 ，从一个侧面反映出复杂网络已成为物理界的一个新的研究热点,其理论基础是统计物理学。复杂网络最重要的两个基本特征是：小世界特性和健壮性，这也是蠕虫传播的理想特征，因为如果蠕虫网络具有小世界特性，那么蠕虫编写者向任意一台蠕虫主机发布控制命令，都能迅速传递到所有蠕虫主机；如果蠕虫网络具有健壮性，则可以避免随机发生的蠕虫节点死机或者被杀毒修复导致整个蠕虫网络的断裂。学科的交叉使我们对蠕虫网络拓扑的演化有了一个全新的认识,它不仅让我们认识到了蠕虫网络规模的增长,而且还能正确地反映出网络的许多几何性质：蠕虫网络可以通过添加新的节点而网络规模主动向外延伸,在选择节点的下一个邻居节点时,新感染蠕虫的主机依据主机性能和网络带宽择优选择与蠕虫网络的节点建立连接，这样演化成的网络拓扑更接近真实的网络,增强网络的可靠性、高效性，有利于对蠕虫传播。因此，本文借助于对复杂网络理论的研究方法,利用蠕虫传播过程来研究蠕虫网络演化机制。

1 模型基本定义

    定义1 节点 感染蠕虫的主机是蠕虫网络的节点。
    定义2 父节点 在蠕虫传播过程中,如果蠕虫通过节点v₁攻击节点v₂并自我复制, 则节点v₁被称为节点v₂的父节点。
    定义3 节点度 一个节点所拥有邻居节点(连接)的数量被称为该节点的度数。
    定义4 吸引力(Attraction)，节点间建立连接的能力，由主机性能(Host Capability)和网络带宽(Bandwidth)指标确定，它是蠕虫传播的基础。节点i的吸引力定义为A(i)=w₁ A_c, (i)+w₂ A_b(i)，其中w₁和w₂分别是节点主机性能吸引力A_c,和网络带宽吸引力A_b的权值，其中 w₁,w₂∈(0,1]。
    定义5 度分布 在t 时刻从蠕虫网络中随机地选择一个节点，它有度数为k的概率记为 , 称为t 时步网络的度分布，这里k₂(t)为节点i 在第t 时步的度数。

2 网络演化算法 

    蠕虫网络演化的基本思想是基于随机游走^[4]的策略，依据主机吸引力而不是节点的度择优的方式，将新感染的主机与网络中节点相连, 节点吸引力越高被选择的概率越大。主要算法描述如下：
    (1) 蠕虫编写者找到m₀台存在漏洞的主机作为蠕虫网络的初始节点、相互连接;
    (2) 通过所控制的m₀台主机发布蠕虫;
    (3) 蠕虫感染主机v后，以它的父节点作为游走的起点;
    (4) 游走的每一步，游走者游走到当前节点i 的邻居节点j 的概率II(j)取决于当前节点的吸引力A_j，即 (k_i 表示节点i 的度)，随后节点i 被标记，直到m个节点(m≤m₀ ) 被标记。
    (5) 主机v 与所标记的m个节点建立连接;
    (6) 循环执行(3) ～ (5) 步，将新感染的节点扩充进蠕虫网络。

(责任编辑：adminadmin2008)