基于变点计算的源端DDoS攻击检测方法

王佳佳

（泰州职业技术学院信息工程学院，江苏泰州225300）

DDoS（Distributed Denial of Service） 攻击是利用足够数目的傀儡机产生数量巨大的攻击包对一个或多个目标实施DoS攻击，耗尽受害端的资源，最终使得受害端丧失提供正常网络服务的能力。DDoS攻击是目前网络安全最严重的威胁之一，是对网络可用性的严峻挑战。如何准确尽快地检测出DDoS攻击，是当前研究的重点。

本文提出了一种基于源端网络并适合所有类型DDoS攻击检测的算法，根据攻击发生时出入流量的不对称特性，利用Bloom Filter结构检测出攻击。该方法具有准确性高，能够在线实时检测，更适合大流量背景，并且易于追溯攻击源等特点。本文方法主要采用了两种技术：1）Bloom Filter数据结构，该结构使用静态固定存储空间和静态存储方法，能够用较少的空间存储大量的数据包信息，采用简单加减计算避免了复杂Hash函数的选择，不仅进一步节约了网络资源而且提高了准确度；2）CUSUM检测方法，CUSUM方法的特点是能够尽快反映出攻击发生时数据包特征的变化情况。本文方法不仅具有准确性好、检测迅速、消耗的计算资源少等特点，而且能够区分正常的网络拥塞与攻击，同时适用于所有的DDoS攻击检测。

1 研究现状

所谓源端DDoS攻击检测指的是将检测算法布置在发出攻击数据包的主机所处网络的边界路由器上。将DDoS攻击检测系统部署在源端，可以使得攻击数据流在进入网络之前被阻止，将攻击对网络的威胁降到最低，是最为理想的一种方法[1]。目前针对源端检测已经有很多的解决方案。文献[2]提出了数据包过滤的方法，即将恶意数据包从网络中区分出来，然后在网络层安装过滤工具，将恶意数据包在到达目标网段之前删除。但该方法不能正确检测出所有DDoS攻击数据包，而且检测消耗的资源较大。文献[3]假设DDoS攻击发生时僵尸主机都在使用带宽的上限发送数据包，不能对其他请求及时回应，因此提出了通过向网络中发送广播数据包，没有应答的即为攻击机的方法。但攻击发生时网络中本身存在的数据包就已经很多，此举无异于雪上加霜。

本文提出的方法只需要对不同来源的数据包做简单计算即可检测是否发生攻击，不会对网络性能产生较大影响。采用DDoS攻击的基本特征，能够检测出所有类型的DDoS攻击。检测方法简单使得本文方法可以部署在任意网络出口设备中（即局域网和广域网相连接的设备，如路由器等）。

2 DDoS攻击特征分析

文献[4]等从不同角度分析了DDoS攻击的特点，并给出了不同的分类标准。

攻击的形式多种多样，但各种DDoS攻击在发生时都具有以下若干特征：（1）网络流量的目的地址过于集中；（2） 网络中出现大量涌向受害端的攻击数据包；（3）攻击数据包很快使得受害端网络拥塞甚至拒绝服务；（4）网络中的攻击数据包会持续一段时间。

从以上描述可知，DDoS的特征就是攻击发生时会出现数量巨大的攻击数据包使得受害端拒绝服务[5]。因此从网络中攻击数据包的数量变化进行分析，就可能识别出各种DDoS攻击。

3 基于Bloom Filter的信息提取

Bloom Filter在1970年由布隆提出，是由一些二进制向量和随机函数组成的数据结构。它的存储空间和插入查询时间都是常数，不会随着存储元素个数的增加而变化。Bloom Filter是基于一行初始值为0的m位比特（b1，b2，…，bm），再使用k个相互独立的hash函数，每个hash函数的返回值在1到m之间，被击中的比特位设置值为1。在DDoS攻击发生时，数据流量较大，应用Bloom Filter则具有明显优势[6]。

本文算法基于Bloom Filter的数据结构，并作了一定的改进，三级向量、多比特位，增大了应用范围；采用简单加减计算避免了复杂Hash函数的选择，不仅进一步节约了网络资源而且提高了准确度。DDoS攻击发生时，网络中会出现大量的异常攻击数据包，这势必使网络中数据包数量相关的统计特性相比正常情况发生特定的变化。因此，通过合适的算法定能检测出攻击的存在。首先说明如何计算网络中出现异常数据包的次数，路由器上每个端口处理的数据包都会分成inbound和outbound两个方向，每个端口对应于Bloom Filter中的一个计数器。我们改进了Bloom Filter结构，使得一个网络设备端口对应于三级向量Ti、To和Ts（如图1所示）。改进后的结构能够方便的统计出设备各个端口数据包的流量。

图1 算法中使用的Bloom Filter结构

由于网络数据包的数量不能仅用单个0或者1表达，本文将单个比特位进行了扩展，一定程度上增大了存储空间，但这和攻击发生时进行测试所需要的数据存储空间相比是很小的。

首先初始化Bloom Filter，使得Ti、To和Ts等一维m位向量的初始值均为0。Ti用来保存经过路由器的入数据包的数量，To用来保存经过路由器的出数据包的数量。Ti、To中的值均为大于等于0的正整数，如果Ti中的计数器为0，则说明没有数据包从该接口进入网络设备，如果To中的计数器为0，则说明没有数据包从该接口被转发出去。然后将Bloom Filter计算值加入到对应行的比特位当中，计算并存储Ts值。

当数据包到来时，基于Bloom Filter的信息提取算法描述如下：

（1）分析该数据包所在的接口，并在Bloom Filter结构中找到对应的列Cj（1<=j<=m）；

（2） 分析该数据包的接口方向，如果是入数据包则Ti对应的计数器Cj增加1；如果是出数据包则To对应的计数器Cj增加1；

（3） 计算并重置向量Ts中计数器Cj的值。Ts中计数器Cj的值等于Ti中计数器Cj的值和To中计数器Cj的值差值的绝对值。

网络中tcp占据绝大部分流量[7]。在正常情况下，三次握手是能够成功的，即网络设备各个接口出入方向的数据包数量差异是限制在一定范围内的。此外还有少量不需应答的udp数据包，在正常的网络行为模式下，udp数据包受应用软件生成数据的速率、传输带宽、源端和终端主机性能的限制，传输速度要远远低于攻击发生时数据包的传输速度。通过网络日常行为模式的收集，调整阈值，阶段性重置计数器可以消除此类影响。因此，TS中m个计数器的和可以限制在阈值范围内。即使在正常网络发生拥塞时，用户正常刷新网络数据的速度仍然要远低于使用DDoS攻击工具的速度，因此TS中的m个计数器的和仍然可以限制在阈值范围内。当DDoS攻击发生时，网络中会不断出现大量不能完成三次握手只能进行单向传输的数据包，因此TS中向量计数器的累加和会迅速超出阈值，即发生了异常。

4 基于CUSUM的DDoS攻击检测方法

观察网络数据包统计分布的微小变化很难。如果使用CUSUM算法则简单很多。CUSUM最早用于连续分析技术，通常用于检测变化序列，是目前已知最优的变点算法之一。原始的CUSUM序列算法描述如下：CUSUM（i=Qi-k）+CUSUMi-1。其中Qi为统计序列。由于网络中数据流量不能用简单的高斯或其他线性模型来描述，因此本文采用无参数的CUSUM算法，无参数的CUSUM算法不受具体参数值的影响，并且计算量较小，应用在DDoS攻击检测当中较为理想。具体公式如下：

本文采用TS中各计数器值的累加结果作为检测统计序列Qi，正常情况下，这是一个接近零的序列。我们再构造一个新的随机序列假设E（Q）i=α，则参数k是常数，且满足α

正常情况下，Zi序列是负值且相对稳定。在发生DDoS攻击的情况下，随着攻击包的产生，TS中部分计数器的值会大幅增加，经过本文第3节对数据的处理，Zi序列会迅速提升为一个正的数值。为了使得本文算法更加稳定可靠，同时避免拥塞引起的误判，本文每隔一定时间t会对Bloom Filter中的数值进行重置，一段时间（>）t之后可以得到一个根据时间间隔t变化的序列{Zi，i=1，2，3…}，其中 Zi= （Qi-k） +Zi-1。

因此本文CUSUM算法的计算结果有正值和负值之分。如果结果是负值，表明当前网络处于正常工作状态；如果结果是正值且以很快速度不断增大，表明当前网络可能已经受到DDoS攻击。

攻击发生时，算法结果会迅速提升为正值，但提升到什么程度才能认为发生DDoS攻击呢？阈值N的设置就尤为重要了，通过一段时间内在正常情况下实际网络数据包数量变化的统计可以找出合适的阈值。如果Yi没有超过N则返回结果为0，认为网络仍然处于正常状态，一旦Yi超过N则返回结果为1，认为发生了攻击，公式如下：

5 实验结果及分析

本文检测采用的攻击场景测试集是DARPA提供的数据集。m值的选取依赖于局域网直接和外网相连的网络设备接口数量，m值太小则不利于网络的可扩展性，m值太大则浪费存储空间。目前，一台路由器接口数量一般不超过20个，为了实现向上兼容，本文选取参数m的数值为100。采样间隔如果太小，则容易影响设备性能，采样间隔如果太大，则容易漏掉一部分攻击包。因此实验中，采样间隔设置为200个数据包，每一级的向量组均设置为m=100位。正常情况下，CUSUM算法检测序列随时间没有特别明显的变化，本文实验使用的正常数据包来源于当时实际网络转发的数据（包括tcp包和udp包）。通过Bloom Filter计数器对实际网络转发数据的计算，得出正常情况下Qi的最大值为20，同时考虑到现有设备的容错能力，本文选取攻击检测阈值N=20。

图2 本文算法检测结果

图2 则显示了本文算法在攻击检测的过程中能够尽快发现攻击。横坐标表示本文算法检测的数据包的数量，纵坐标表示CUSUM算法的计算值。正常状态下，CUSUM计算值都在正常范围内（例如负值）。但是当检测到约420000个数据包时，CUSUM检测值突然变为较大的正值且超过了阈值，说明此时发生了攻击。

6 结语

在检测DDoS攻击的过程中，很多源端检测方法往往不能检测出所有类型的攻击。本文提出了一种有效的可以部署在源端的DDoS攻击检测方法，可以在只出现少量攻击数据包的情况下准确发现所有类型的DDoS攻击，适用于源端检测，也为监控攻击数据包的来源以及通知受害端进行防御赢得了宝贵的时间。另外，在攻击流量较小时进行检测及监控，对网络的性能也不会有太大的影响，为阻止后续攻击提供了方便，具有一定的现实意义。

现有的DDoS攻击检测算法一般在检测成功之后仍然无法将攻击数据流直接过滤，因此，结合DDoS攻击检测的研究还需进一步做好过滤攻击包的工作，以更好的阻止DDoS攻击。

[1]严芬,王佳佳,陈轶群,等．一种轻量级的 SYN Flooding攻击检测方法[J].计算机科学,2008,35（9）：72-75．

[2]X.Liu,X.Yang,and Y.Lu.To filter or authorize:network-layer DoSdefense against multimillion-node botnets[C].Seattle Washington USA,2008.

[3]M Walfish,M Vutukuru,H Balakrishan,D Karger,S Shenker.DDoSdefense by offense[C].SIGCOMM,2006.

[4]CHANGRKC.Defendingagainst flooding-based distributed denial-of-service attacks：Atutoria1[J].IEEE Communications Magazine，2002，40（10）：42—51.

[5]J Jung,B Krishnamurthy,M Rabinovich.Flash Crowds and Denial of Service Attacks:Characterization and Implications for CDNs and Web Sites[C].Honolulu,Hawaii,USA,2002.

[6]严芬,王佳佳,殷新春,等．一种基于 Hurst参数的 SYN Flooding攻击实时检测方法[J].计算机科学,2008,35(12)：109-113，162.

[7]张艺濒,张志斌,赵咏,等.TCP与UDP网络流量对比分析研究[J].计算机应用研究，2010，27（6）：2192-2197.