基于昵称检测和ID3决策树算法的僵尸网络检测方法

尹璐 09S030141

一、相关背景

近年来，僵尸网络的活跃得到了国内外安全业界的高度重视。 简单地说， 僵尸网络就

1

是攻击者利用互联网秘密建立的可以集中控制的计算机群。僵尸网络具有四个属性：恶意性、非配合性、可控性和联合性。

僵尸网络主要由4个部分组成：

<1> 控制者：整个僵尸网络的所有人，指挥整个网络的行为。 <2> 僵尸终端：网络中背控制的主机

<3> 僵尸程序：用于控制僵尸终端的恶意程序

<4> 控制命令信道：网络中用来传播控制命令的途径，目前主要有IRC2、HTTP和P2P。 虽然P2P和HTTP僵尸网络逐渐盛行，但由于IRC僵尸网络简单、灵活、易控等优点， IRC僵尸网络仍然是攻击者手中的重要手段。 目前已有的IRC僵尸网络检测算法或者需要先验知识， 或者不能达到轻量实时处理，都不能满足大规模网络的需要3。

本文主要对僵尸网络的终端昵称特征进行检测，同时结合决策树的算法对检测结果进行分析，判断被检测网络是否是僵尸网络。 二、昵称检测算法

与一般的网络聊天中昵称的随机性不同，僵尸网络终端的昵称往往具有一定的命名规律，这样比较便于控制者对僵尸终端的传播和控制。所以我们主要对IRC客户端的昵称进行检测，对具有比较相似的昵称的终端重点分析。在这里我们主要采用3个属性来描述昵称的特征：公共子串比率、组成距离和结构相似性。 3.1 公共子串比率

我们将字符串X和字符串Y的公共子串比率（LCS_rate）定义为

LCS_rate（X,Y）=

2 |LCSofX&Y|

|X| |Y|

在实际出现的僵尸网络昵称中，通过固定的字符串加上变化的数字字符前缀后缀作为僵

尸昵称是很常见的。公共子串比率反映了两个昵称是否包含 长公共子串， 显然如果两个昵称具有高公共子串比率， 则说明两个昵称具备高内容相似性， 那么这两个昵称为僵尸昵称的概率较高。 3.2 组成距离

一个昵称由若干字母、数字和特殊字符组成。同一个IRC频道下的昵称的各个组成部分的内容可能不同， 但各个组成部分的长度基本相同。 于是将昵称表示为四元向量（昵称长度、字母长度、数字长度、特殊字符长度）。这里使用欧几里德距离来刻画两个昵称向量相似性，实际验证发现，需要突出特殊字符长度和数字串长度对昵称组成距离的作用。这里我们定义字符串X和字符串Y的组成距离Dis(X,Y)为Dis(X,Y)=

(LT(X) LT(Y)) (LL(X) LL(Y)) (LN(X) LN(Y)) (LS(X) LS(Y))

max{min{LN(X),LN(Y)},1} max{min{LS(X),LS(Y)},1}

2

2

2

2

其中LT(X)为字符串X的总长度记， LL(X)为字母长度记， LN(X)为数字长度记， LS(X)为特殊字符长度记。

3.3 结构相似性

这里我们忽略昵称中的具体内容，首先对昵称字符串进行标准化映射f： A,x {a~z,A~Z}

f(x)= B,x {0~9}

C,其他

我们将映射后的字符串成为标准字符串。例如字符串USA|00|XP|719的标准字符串为AAACBBCAACBBB。去掉重复后的缩减标准字符串为ACBCACB。然后我们定义字符串X和字符串Y的结构相似性RN_Dice(X,Y) RN_Dice(X,Y)=

2 |2grams(RN(X)) 2grams(RN(Y))||2grams(RN(X))| |2grams(RN(X))|

三、决策树思想

决策树（decision tree）是一个树结构（可以是二叉树或非二叉树）。其每个非叶节点表示一个特征属性上的测试，每个分支代表这个特征属性在某个值域上的输出，而每个叶节点存放一个类别。使用决策树进行决策的过程就是从根节点开始，测试待分类项中相应的特征属性，并按照其值选择输出分支，直到到达叶子节点，将叶子节点存放的类别作为决策结果。

构造决策树的关键步骤是分裂属性。所谓分裂属性就是在某个节点处按照某一特征属性的不同划分构造不同的分支，其目标是让各个分裂子集尽可能地“纯”。尽可能“纯”就是尽量让一个分裂子集中待分类项属于同一类别。

构造决策树的关键性内容是进行属性选择度量，属性选择度量是一种选择分裂准则，是将给定的类标记的训练集合的数据划分D“最好”地分成个体类的启发式方法，它决定了拓扑结构及分裂点的选择。

四、在僵尸网络检测中的应用

在这里我们采用ID3算法来构造决策树，而决策树的分裂属性就是公共子串比率、组成距离和结构相似性。所以ID3算法的核心思想就是以信息增益度量属性选择，选择分裂后信息增益最大的属性进行分裂。设D为用类别对数据集进行的划分，其中的一个分裂属性为A，这里我们先定义几个概念：

m

4

熵info(D)=

i 1

pilog2(pi) pi表示第i个类别再整个数据集中出现的概率。

v

A对D划分的期望信息infoA(D)=

j 1

|Dj|

(Dj) |D|

信息增益为二者差值gain(A)=info(D)- infoA(D)

ID3算法就是在每次需要分裂时，计算每个属性的增益率，然后选择增益率最大的属性进行分裂。我们假设数据集包含10个僵尸网络昵称

子串比率、组成距离、结构相似性和是否是僵尸网络，假面计算各属性信息增益。

info(D)=-0.7log20.7-0.3log20.3=0.7*0.51+0.3*1.74=0.879 infoL(D)=

0.3*(

03log

2

3

33

log

3

2

3

) 0.4*(

14

log

1

2

4

34

log

3

2

4

) 0.3*(

13

log

1

2

3

23

log

2

2

3

)

0 0.326 0.277 0.603

gain(L)=0.879-0.603=0.276

同理得gain(R)=0.033和gain(S)=0.553。属性S具有最大信息增益，所以第一次分裂选择S为分裂属性，分裂后的结果如下：

在第一步分裂的基础上，递归使用该方法计算子节点的分裂属性，就可以构造出整个决策树。

这样，我们通过对已知的网络数据的学习，可以得出一个昵称是否是僵尸网络的大致概率，然后我们对开放网络环境进行检测，对检测到的昵称进行属性计算，根据计算的结果数值，结合构造好的决策树，来判断该昵称是否是一个僵尸网络。 1

杜跃进，崔翔. 僵尸网络及其启发. 中国数据通信, 2005, 7( 5) : 9 13 2

Oikarinen J, Reed D. Internet relay chat protocol. Request for Comment s ( RFC) 1459, IE TF, May, 1993 3

王威，方滨兴，崔翔. 基于终端行为特征的IRC僵尸网络检测. 计算机学报2009.10 4

张洋. 算法杂货铺-分类算法之决策树.

http://www.77cn.com.cn/leoo2sk/archive/2010/09/19/decision-tree.html