基于改进决策树算法的DNS流量异常动态检测

沈广东

(泉州信息工程学院，福建 泉州 362000)

决策树算法实质上属于一种贪心算法，通常由多叉树或二叉树来描述。在决策树中，每一非叶子节点都可以形容某种划分规则[1]，而叶子节点均用来描述类别。通常情况下，决策树算法采用自顶向下方式，从根节点开始按照划分规则生成完整的决策树。在决策树算法中，通常包含两个部分，分别为决策树生成与修剪，而决策树修剪通常是指对已构建好的决策树进行优化，以降低决策树过度拟合问题。

域名系统(Donmain Name System，DNS)属于互联网核心部分，通常用于提供互联网域名服务，在网络中其能够实现IP地址与域名之间的映射[2]，对于网络来说，DNS流量的安全性十分关键，若DNS遭受到攻击，则会导致网站出现虚假副本，使网络受到大量威胁[3]，因此，及时对DNS数据进行分析，获取其中的异常流量，能够有效维护网络安全。

有较多学者对DNS的异常检测进行了研究，秦辉东等[4]研究基于多特征的DNS异常检测方法，但该方法在异常密度较高的情况下，检测结果不够精准；展鹏等[5]研究基于特征符号表示的网络异常流量检测方法，但该方法所获取的流量异常特征不够明显。为此，本文研究基于改进决策树算法的网络DNS流量异常动态检测方法，通过对决策树算法的改进，实现动态监测DNS异常流量。

1 网络DNS流量异常动态检测

1.1 网络DNS流量异常现象分析

网络中异常DNS流量通常是指恶意网站URL，若用户不经意间连接到这些URL时，会导致隐私数据泄露，且会在后台下载恶意代码，使得恶意攻击者访问用户隐私内容。本文针对网络DNS流量异常现象进行研究，相较于传统恶意代码，DNS流量异常现象出现时，攻击者通常会访问用户服务器[6-7]，以获取控制命令，从而使恶意攻击者执行恶意命令，因此，DNS异常流量现象属于受害者主机与攻击者之间的信息交互，即攻击者需要向受害者主机发送命令，当主机接收后才能够完成相应攻击[8]，而攻击命令通常在命令控制信道中出现，因此，检测DNS异常流量可以及时发现域名被查询的情况，可以帮助用户及时切断攻击者的服务器连接，保障网络命令控制信道安全。

1.2 网络DNS流量异常特征选择

特征选择与特征提取不同，特征提取是获取网络DNS流量异常特征，而特征选择则是对特征的筛选，实质上是选出具有代表异常的小范围流量[9-10]。

传统的网络DNS流量特征选择算法有蚁群算法、遗传算法等，但这些算法所选出的特征并不完全，因此，本文利用新型的邻域粗糙集算法选择网络DNS流量异常特征。

在邻域粗糙集算法中具有以下定义：

(1)假设Y为随机获取的样本集，此时设条件、决策属性集分别为K、B，并通过D描述K的邻域，则设计邻域决策系统为。

(2)在中，样本集Y被集合B处理为n个等价类，并表示为a,b,…,n。K的约简属性为∀W⊆K，则可通过公式(1)定义B的邻域粗糙集下近似。

Z={Z·a,Z·b,L,Z·n}

(1)

公式(1)中，L表示邻域范围，Z表示其邻域下近似值，同时可通过公式(2)定义B的邻域粗糙集上近似。

Q={Q·a,Q·b,L,Q·n}

(2)

公式(2)中，Q表示其邻域上近似值。由公式(1)与公式(2)可以获知，粗糙集理论的边界域W，如公式(3)所示。

(3)

(3)在邻域决策系统中，定义如式(4)所示。

(4)

公式(4)中，B依赖K的程度由J表示。

(4)在邻域决策系统中，∀i∈W⊆D，假设J>Q，则表示属性i的存在具有必要性，若无法成立，则属性i的存在不具有必要性。

(5)在邻域决策系统中，若W⊆D可以实现：J=Q、∀i∈W，J

(6)在邻域决策系统中，假设W⊆D，i∈D-W可以满足，则可通过公式(5)定义i在W中的重要度V。

(5)

在上述过程中，本文通过邻域粗糙集算法理论，设计一种邻域决策系统。并通过如下步骤完成网络DNS流量异常特征选择：

向决策系统中输入条件特征集S，计算S的邻域依赖度，同时从中随机挑选特征s，计算s与其邻域的距离函数，若S中全部特征均计算完毕，则删掉具有改变最小距离函数的特征，删除该特征后输出特征选择结果。

1.3 基于C4.5决策树算法的网络DNS流量异常动态检测

决策树算法能够从无规则实例集中分析出分类规则。由于C4.5算法具有较高的计算效率，因此，本文选择C4.5算法进行网络DNS流量异常动态检测。

在决策树算法中，最主要的部分就是对内部节点分支的选择，不同的划分情况得到的决策树效果也存在较大区别，C4.5算法主要采用信息熵理论，将信息增益最高属性设为分类属性。在上述网络DNS流量异常特征选择步骤获取的特征集S中，假设S的理想划分为S={s1,s2,…,sn}，则可通过公式(6)表示信息增益率。

R(S,β)=HG(S,β)/HS(S,β)

(6)

公式(6)中，β表示引入测试条件；当S被β划分后得到的信息增益由HG(S,β)表示；β产生的分割信息熵由HS(S,β)表示。

C4.5算法通过信息增益率获取节点的分枝，但在确定分枝的过程中，由于划分产生的分割信息较小，会导致增益结果不够精准。为此，采用最短距离划分方法设计决策树，假设两个划分间的距离为Mantaras范式距离，则将与理想划分距离最近的属性作为测试条件。

(7)

公式(7)中，S对S′的条件熵为H(S′|S)；S′对S的条件熵为H(S|S′)；同时，H(S,S′)为S对S′的联合熵。

由于训练时容易出现过度拟合现象，因此，还需要对C4.5算法进行改进，使检测过程更加精准。

1.4 基于改进决策树算法的网络DNS流量异常动态检测

C4.5算法属于在ID3算法的基础上进行优化。但由于C4.5算法在属性X只存在一个值时，分裂信息值会接近于0，导致分裂信息的倒数接近无穷大，会使分类结果存在异常。

本文对C4.5算法进行改进，构成BL4DT算法，向C4.5算法中添加平衡变量，之后再对信息增益率进行计算。

对于网络DNS流量异常动态检测问题，在上述网络DNS流量异常特征选择步骤获取的特征集S中，目标函数为Ci(i=1,2,3,…,m)，其中包含m个不同的特征属性，且目标函数服从分布P=(p1,p2,p3,…,pm)，此时，可通过公式(8)计算S的熵。

(8)

公式(8)中，熵是指S的不确定性，由此可以得到验证，如式(9)所示。

0≤E(S)≤log2m

(9)

设由网络DNS流量异常特征构成的样本集合为S={A1,A2,…,Am}，其中具备m个属性特征，则训练样本集为|S|，全部训练样本均被调整为n个各自独立的类Ci(i=1,2,3,…,n)，其中每个类相应的样本数表示为|Ci|，此时，针对S内的属性Ai进行分析，其对应的信息增益G(S,Ai)如公式(10)所示。

G(S,Ai)=E(S)-E(S,Ai)

(10)

公式(10)中，Ai的值空间表示为values(Ai)，当Ai的值为v时其子样本集为Sv，且在此时Sv={s∈S|A(s)=v}。

对于C4.5算法在计算时存在的分裂信息度量sp，主要通过公式(11)实现计算。

(11)

根据上述分析，此时可以获取BL4DT算法对信息增益率的计算过程，如公式(12)所示。

(12)

当完成改进信息增益率计算后，为使计算结果更加精准，引入平衡变量，若A的信息增益率最大时，向其中引入平衡变量，并通过公式(13)表示平衡因子α计算方式。

(13)

公式(13)中，数据集N被调整为m个各种类型的特征属性Ci(i=1,2,3,…,m)；在属性A中，共具备n个不同值，其中A获取的第i类记录里在Cj中的样本数由xij描述，当引入平衡变量后，包含m个值的属性A信息增益可通过公式(14)计算。

(14)

假设S被属性A分解为n个部分，即{S1,S2,…,Sn}，则属性A取值为Ai时，在S中包含正例Pi个、反例ni个，通过I(pi,ni)描述的Si信息，此时，可通过公式(15)描述属性A的信息熵。

(15)

其中，I(pi,ni)通过式(16)计算：

(16)

按照极限公式理论，若x→0，则ln(1+x)≈x，按照这一标准，对上述公式进行简化，简化结果如公式(17)所示。

(17)

信息增益率可以作为网络DNS正常流量与异常流量的分割属性，其具有较强的判别能力，可以使动态检测效果更佳完美。通过以下步骤表示改进后的决策树(BL4DL)算法的网络DNS流量异常动态检测过程：

输入：属性集合A以及样本集S。

(1)构建节点T。

(2)假设训练样本为空，则无法完成建树，返回至步骤(1)再次创建。

(3)假设属性集合A为空，则返回步骤(1)将节点T设为单节树，并向节点T赋予样本集S内出现最密切的类。

(4)若全部训练样本都存在于相同类(Class)中，则返回步骤(1)，将T设为叶节点，并向T赋予S中的类。

(5)从A中挑选信息增益率最大的属性Ai。

(6)将节点T标记为属性Ai。

(7)针对每个Ai中的实际值c，通过节点T生长出Ai=c分支。

(8)将S中Ai=c的训练样本集合设为S′。

(9)若S′为空，则产生叶子节点，并向S′赋予训练样本中含量最大的类，若S′不为空，则引入BL4DT(S′,{A-Ai})作为返回节点。

输出：一颗判定树，即网络DNS流量异常动态检测的结果。

2 实验分析

从企业网络中搜集DNS流量，该网络通过隧道协议传输，因此，DNS流量更加清晰，适合标记异常状态，通过人工方式标记DNS流量异常，并通过本文方法对此进行检测，验证方法有效性。

分析应用本文方法后，能否对不同网络DNS流量特征异常现象实现选择，分析结果如表1所示。

表1 网络DNS流量特征异常现象特征选择

根据表1可知，应用本文方法，能够有效实现多种网络DNS流量特征异常时的选择，可以为DNS流量异常动态监测提供可靠帮助。

分析应用本文方法检测到网络中某日DNS流量的平均异常比，并与实际流量异常情况进行对比，对比结果如图1所示。

图1 网络DNS流量平均异常比

根据图1可知，在不同时间下，网络DNS流量的平均异常比均有所不同，在4h与8h之间平均异常比相对较高，而20h～24h之间平局异常比略低，通过本文方法的检测结果可以看出，检测到的平均异常比与实际异常比十分接近，说明本文方法能够精确实现网络DNS流量异常智能检测。

不同的网络DNS流量异常密度会使异常动态检测的检测率发生变化，本文选取三种异常密度进行分析，分析不同异常密度下，本文方法的ROC曲线变化，分析结果如图2所示。

图2 本文方法ROC曲线变化

根据图2ROC曲线可以看出，当虚警率不断增加，本文方法在不同异常密度下的检测率也随之上升，其中，异常密度越大，检测率相对较低，但是在应用本文方法下，最大异常密度30%的最低检测率也保持在55%以上，说明应用本文方法，可在较大异常密度下实现流量异常检测。

在网络未出现时延时，流量保持500KB左右，当网络出现不同程度的时延，网络DNS流量则出现异常，随着时延的变化流量处于200KB～1000KB之间波动，分析应用本文方法前后，对DNS流量状态的检测情况，检测结果如图3所示。

图3 网络DNS流量检测情况

根据图3可知，应用本文方法前，当网络出现时延时，流量已处于大范围波动，但对流量异常情况并未明细检测，检测得到的流量变化仅处于400～600KB之间，而应用本文方法后，流量发生异常变化时，本文方法能够清晰检测到流量的状态波动。由此可知，本文方法能够较好地实现网络DNS流量异常检测。

3 结论

本文研究基于改进决策树算法的网络DNS流量异常动态检测方法，选择网络DNS流量异常特征，并通过决策树算法对该流量异常特征进行检测，由于决策树算法存在一定缺陷，因此，对该算法进行改进，使网络DNS流量异常动态检测更加完善。在此基础上，可将该方法应用至较多领域，同时，未来也可继续对该方法进行优化，使网络DNS流量异常情况能够得到处理。