基于元胞退火算法的僵尸网络传播特征研究

赵攀，江宇波，邱玲

（四川理工学院计算机学院，四川自贡643000）

基于元胞退火算法的僵尸网络传播特征研究

赵攀，江宇波，邱玲

（四川理工学院计算机学院，四川自贡643000）

为了有效研究僵尸网络传播过程中的特征变化，基于元胞退火算法提出了一种新的刻画方法BDCA。该方法通过定义了僵尸网络中普通节点、易感染节点和感染节点之间的转化关系，建立平衡条件下的最优目标函数，并利用元胞退火算法求出最优解。最后，利用NS2进行仿真实验，深入分析了影响BDCA算法的关键因素，同时通过对比其它算法之间的性能状况。结果表明，该算法具有较好的适应性。

僵尸网络；感染；特征；元胞退火算法

引言

近年来，僵尸网络（Botnet）成为计算机网络安全的重要威胁，它是一种通过传播僵尸程序控制主机，并由一对多的命令与控制信道所组成的网络［1_3］。这种一对多的控制关系使攻击者以极低代价实现控制大量资源的目的，并可以轻易发动诸如垃圾邮件和分布式拒绝服务等攻击，造成数据窃取和服务器瘫痪等危害。它是从传统恶意代码形态和后门工具演化而来的。

僵尸网络主要由僵尸程序和僵尸网络控制器构成，作为僵尸网络核心的控制机制主要采用的协议有IRC、P2P和HTTP［4_7］。而目前针对僵尸网络的检测方法主要有三种：蜜罐技术、流量分析技术和终端信息的检测技术。蜜罐是防御者部署在网络中用以引诱攻击者上钩的陷阱主机，其前提必须让蜜罐绝对隐蔽地加入到僵尸网络中，并且需要保证蜜罐不会被攻击者反检测；流量分析技术则是检测人员通过网络分析软件，对异常流量进行检测；而基于终端信息的检测技术，主要利用僵尸终端的一些重要信息进行反馈和分析。柴胜等［S］通过详细分析P2P僵尸网络的网络特征和生命周期，提出了一种新的基于改进的SPRINT决策树和相似度函数的在线综合检测方法。臧天宁等［9］针对僵尸网络之间潜在具有的隐藏关系，提取了内部通信的主机通信量、数据流数量、数据分组负载等特征，建立了僵尸网络之间的相似度评价模型。王劲松等人［10］首先从僵尸网络的传播、攻击以及命令与控制等方面介绍了僵尸网络工作机制的发展，然后从监测、工作机制分析、特征分析、检测和主动遏制对僵尸网络防御方面的研究进行总结和分析，并对防御方法的局限、僵尸网络的发展趋势进行了讨论。陈端兵［11］通过挖掘网络中的关键节点和社区结构，建立了一种基于社会网络分析的P2P僵尸网络反制策略，有效控制僵尸网络病毒的传播。钱权［12］在详细分析两种典型的结构化P2P协议Chord和Kademlia的基础上，结合双因子免疫机制、主机在线率等因素建立了结构化P2P僵尸网络的传播模型，深入研究了这两种典型的结构化P2P网络中僵尸的传播原理。

针对上述问题，本文首先给出了僵尸网络中各类节点之间的转化关系，并建立符合僵尸网络传播的数学模型，同时利用元胞退火算法对上述模型进行求解，获得平衡关系下的最优解。最后，通过NS2进行仿真实验，深入研究了影响该方法的关键因素。

1 僵尸网络特征

假设初始时刻，某网络G中存在的N个节点均未被僵尸程序感染。在每个单位时间内节点的变化率为ΔN，那么经过时间步长t后，网络G中的节点数量为N（t）=N+∑tΔN（t）。将这些节点划分为普通节点、易感节点和感染节点。三类节点之间的转化关系为：普通节点被僵尸程序植入后以概率α变成易感节点，易感节点在被入侵后以概率β变化成感染节点，而感染节点和易感节点在清除掉僵尸程序后分别以概率γ和δ恢复为普通节点。这四类转化关系的概率计算公式：

式（1）采用节点度和平均概率α计算普通节点i向易感染节点转化的概率αi，其中Di表示易感染节点i的度，表示网络中所有节点的度，这两者比例越大其感染可能性将变大，这说明网络中如果某个普通节点的相邻节点越多，那么它受到感染的几率将增大。

2 目标函数

由上述的三类节点之间的转化关系，进行数学描述。假设在某时刻t网络中的总节点数为N（t），普通节点数量为A（t），易感节点数量为B（t），感染节点数量为C（t），并且易感节点数量与总节点数量正相关。在单位时间内某感染节点i能探测到的节点数等于其度数节点i能探测到的易感节点数可表示为，那么单位时间内感染节点i能够感染的易感节点数为。为了获得比较安全的网络环境，感染节点和易感节点的数量应该趋于0。对此，本文建立如下目标函数：

约束条件为：

其中，式（6）描述了单位时间内易感节点转化为普通节点或者感染节点的变化率，式（7）描述了感染节点转化为普通节点的变化率，式（S）描述了在单位时间内普通节点转化为易感节点以及感染节点和易感节点转化为普通节点的变化率。

3 算法描述

对于上述建立的数学模型，是一个非线性最优问题。而元胞自动机是一种时间和空间离散、状态有限的多维系统，多应用于非线性空间。所以，本文利用元胞退火算法（Botnet Detecting algorithm based on Cellular Annealing，BDCA）对模型进行求解。

定义Moore型元胞结构（图1），中心黑色圆圈代表当前元胞，与周围S个元胞相邻。中心元胞下一时刻状态将选择周围S个元胞和自身状态中的最优值。这里将中心元胞视作抗体，其适应度z（x）状态值如下：

根据元胞适应度、变异概率p和交叉概率q，定义交叉和变异过程中所采用的元胞演化规则：

图1元胞结构示意图

（1）在当前时刻，令中心元胞i和临域元胞j的适应度分别为z（i）和z（j），其差Δz=z（i）-z（j），判断交叉概率p与rand（）之间的关系，若p≤rand（），保持当前元胞状态；否则当前元胞执行变异操作，根据式（S）产生新的子抗体r1：

其中，rand（）为0到1之间的随机数；

（2）判断交叉概率q与rand（）之间的关系，如果q≤rand（），保持当前元胞状态；否则根据式（9）对抗体i和j执行交叉操作，获得子抗体i1和j1：

（3）在下一时刻更新所有元胞状态：

本文结合元胞退火算法给出上述数学模型的求解算法（Botnet Detecting algorithm based on Cellular Annea_ ling，BDCA）。具体描述如下：

（1）在开始时刻T，初始化网络拓扑结构，随机生成网络节点数目N，以及普通节点、易感染节点和感染节点初始所占比例，并确定种群规模R、抗体群规模为M、初始温度t0、变异概率p和交叉概率q、迭代次数m等参数。

（2）这里将每个节点视作抗体，根据式（12）计算抗体群中每个抗体i的适应度值，用来表示抗体与抗原之间的匹配程度。

（3）按照式（16）对第i个抗体进行克隆操作，获得规模为M1的新抗体群η：

其中，“=”表示向下取整，θ表示克隆系数。

（4）根据元胞演化规则对新抗体群η1中抗体r执行变异操作，并产生新的子抗体r1以及临时抗体群η2，同时将r1作为当前最优解。

（5）根据元胞演化规则对临时抗体群η2的抗体r1和r2随机执行交叉操作，获得子抗体r3和r4，以及新的抗体群η3。

判断当前温度t是否为零，如果不为零，则令i+1，t=t（N-i）/n，跳转到步骤（3）；否则表示退火过程完成，此时得到的抗体群η3即为下一时刻最优的目标函数F（k），跳转到步骤（7）。

（7）令m=m+1，判断当前循环是否结束，如果是则跳转到步骤（2），继续预测下一时刻最优的目标函数F（k），否则跳转到步骤（S）。

（S）输出当前的最优解，即为稳定状态下感染节点和易感染节点的最小值。

（9）算法结束。

4 仿真实验

为了验证上述算法的有效性，这里利用NS2进行仿真实验。在NS2中首先建立如图2所示的网络拓扑图。

图2仿真拓扑图

设置其参数：节点数目为150个，链路容量为15 MbPs，各节点缓存大小为256 Packets，延时10 ms，数据包大小为512 Byte。同时，令种群规模R=200，抗体群规模为M=20、初始温度t0=1、变异概率p=0.04，交叉概率q=0.5，最大迭代次数m=200。在表1中列出了文献［16］所采集的不同网络流量属性信息，这里将本文提出的BDCA算法与文献［16］提出的BDCFA（Botnet Detectingmethod based on Clustering Flow Attributes）算法进行比较分析。假设初始时刻不存在僵尸程序，在t= 10时僵尸程序出现，有一个节点被感染，此时没有恢复的节点。首先在节点A、D、E和F处按照表1给出的网页浏览、在线游戏、P2P应用和僵尸网络数据流特征来产生数据源。

图3中显示了这两种算法感染节点数的变化趋势。随着仿真时间的增加，曲线整体先呈现上升趋势，随后降低直至平稳。在开始阶段，感染节点较少，并且连接度较小，僵尸程序的传播能力较低，整个网络的感染节点数增长缓慢。大约在t=30时，网络有相当一部分节点被感染，此时汇聚节点的连接度远高于开始阶段，导致网络中感染节点的连接度迅速增加，并达到最大值（t=50时）。同时，针对僵尸程序的防治措施在网络中开发发挥作用，恢复为普通节点的数量不断增加，感染节点的连接度随之下降，因此僵尸程序的传播能力下降，使感染节点的数量逐渐减少，最后达到一种平衡状态。而在同一仿真时间下，BDCA算法对应曲线的感染节点数较BDCFA算法更低，这说明BDCA算法具有更好的抵抗僵尸程序的能力。

表1不同网络流量属性信息

图3感染节点数对比情况

其次，再对变异概率p和初始温度t0这两个影响BDCA算法性能的关键因素进行研究。图4给出了不同变异概率p下感染节点数的变化趋势。在仿真初期，变异概率p越小对应的感染节点数个数越少，但是在仿真后期仿真曲线发生突变，变异概率p越大对应的感染节点数个数越少。这是由于初期网络中节点被感染的情况较少，而仿真后期，单位面积内的感染节点分布增加，此时增大变异程度越大，查找出感染节点进行恢复的概率就越大，而在前期增大变异程度会过多消耗系统资源。

图5给出了不同初始温度t0下感染节点数的变化趋势。在初期初始温度越小，对应曲线的感染节点数越大；而在仿真后期情况发生了突变，初始温度越大，对应曲线的感染节点数越大。这是因为初期感染僵尸程序的节点较少，如果初始温度越大，系统趋于稳定的速度越快，感染节点恢复效率将增加；当处于仿真后期，感染节点增多，初始温度越大系统寻优过程的开销越大，清除感染节点的几率减小。

图4不同变异概率下感染节点数比较

图5不同初始温度下感染节点数比较

5 结束语

本文针对僵尸网络传播特点提出了一种新的刻画方法BDCA。该方法首先定义了普通节点、易感染节点和感染节点之间的转化关系，并建立了平衡条件下的目标函数和数学模型。同时，结合元胞退火算法，将网络节点集合看作抗体种群，普通节点、易感染节点和感染节点看作不同抗体，对目标函数进行求解。最后，通过NS2进行仿真实验，对比研究了BDCA算法与其它算法之间的性能差异，结果表明该算法具有较好的适应性。在后续研究中，可以考虑结合蜜罐检测和流检测方法对分布式P2P僵尸网络传播特点进行刻画，以此建立完善的评价体系结构。

［1]Zhang Z H，Kadobayashi Y.A holistic perspective on understanding and breaking botnets:challenges and coun_ termeasures［J].Journal of the National Institute of Infor_ mation and Communications Technology，2008，55(2_3):43_59.

［2]Sun Y D，Li D.Overview of botnet［J].Computer Appli_ cations，2006，26(7):1628_1630.

［3]诸葛建伟，韩心慧，周勇林，等.僵尸网络研究［J].软件学报，2008，19(3):702_715.

［4]王天佐，王怀民，刘波，等.僵尸网络中的关键问题［J].计算机学报，2012，35(6):1192_1208.

［5]李润恒，王明华，贾焰.基于通信特征提取和IP聚集的僵尸网络相似性度量模型［J].计算机学报，2010，33(1):45_54.

［6]Holz T，Steiner M，Dahl F，et al.Measurement and mitiga_ tion of peer_to_peer_based botnets:a case study on storm worm［C]//Proceeding of the 1st UsenixWorkshop on Large_Scale Exploits and Emergent Threats，San Fran_ cisco，April 9，2008:1_9.

［7]王海龙，胡宁，龚正虎.Bot_CODA:僵尸网络协同检测体系结构［J].通信学报，2009，30(10A):15_22.

［8]柴胜，胡亮，梁波.一种p2p Botnet在线检测方法研究［J].电子学报，2011，39(4):906_912.

［9]臧天宁，云晓春，张永铮，等.基于通信特征和D_S证据理论分析僵尸网络相似度［J].通信学报，2011，32 (4):66_76.

［10]王劲松，刘帆，张健.基于组特征过滤器的僵尸主机检测方法的研究［J].通信学报，2010，31(2):29_35.

［11]陈端兵，万英，田军伟，等.一种基于社会网络分析的P2P僵尸网络反制策略［J].计算机科学，2009，36 (6):101.

［12]钱权，萧超杰，张瑞.结构化对等网络中P2P僵尸网络传播模型［J].软件学报，2012，23(12):3161_ 3174.

［13]谭虓，刘自山，李凌宇.基于模拟退火遗传算法的IIR数字滤波器参数优化设计［J].四川理工学院学报:自然科学版，2010，24(4):426_430.

［14]崔之熠，王茂芝，刘国涛，等.蚂蚁算法在TSP问题求解的应用［J].四川理工学院学报:自然科学版，2011，24(3):334_337.

［15]鲁宇明，黎明，李凌.一种具有演化规则的元胞遗传算法［J].电子学报，2010，38(7):1603_1607.

［16]苏欣，张大方，罗章琪，等.基于Command and Control通信信道流量属性聚类的僵尸网络检测方法［J].电子与信息学报，2012，34(8):1993_1999.

Study of Botnet Spread Characteristic Based on Cellular Annealing Algorithm

ZHAO Pan，JIANG Yubo，QIU Ling
（School of ComPuter Science，Sichuan University of Science&Engineering，Zigong 643000，China）

In order to research the characteristic changes in Botnet sPread Process effectively，a novel dePicted method BDCA is ProPosed based on cellular annealing algorithm.In thismethod，the transformation relationshiPs between ordinary nodes，suscePtible nodes and infected nodes are defined，and the oPtimal objective function under equilibrium conditions is built.Then，the oPtimal solution is solved by using cellular annealing algorithm.Finally，a simulation exPerimentwith NS2 is conducted to analyse the key factors influencing the BDCA algorithm in dePth.Meanwhile comPared to the Performance of other algorithms，the results show that，BDCA has better adaPtability.

Botnet；infect；characteristic；cellular annealing algorithm

TP393

A

1673_1549(2014)02_0032_05

10.11863/j.suse.2014.02.07

2013_11_11

四川省教育厅重点项目（13ZA011S）；人工智能四川省重点实验室开放基金项目（2012RYY02）；四川理工学院培育项目（2012PY13）

赵攀（1976_），男，四川自贡人，副教授，硕士，主要从事计算机网络通信和数据处理方面的研究，（E_mail）zhaoPanS27@gmail.com