粒子群算法追踪DDoS攻击源技术研究

李爱华,肖金凤,邱　朋

(沈阳理工大学 信息科学与工程学院，沈阳 110159)



粒子群算法追踪DDoS攻击源技术研究

李爱华,肖金凤,邱朋

(沈阳理工大学 信息科学与工程学院，沈阳 110159)

摘要：研究DDoS攻击源追踪技术，采用粒子群算法对概率包标记提出改进策略，设计攻击源追踪实现方案。通过在NS2仿真平台上测试，对仿真结果进行比较分析，仿真实现了基于粒子群算法对DDoS攻击源的追踪，满足攻击路径重构的快速、准确的性能要求。

关键词：攻击源追踪；DDoS；粒子群算法；网络仿真

随着互联网应用的不断深入，DDoS攻击成为当前网络安全领域最具威胁问题之一。在攻击源追踪技术的发展过程中，先后出现了多种技术，包括链路测试技术、路由日志、ICMP回溯、包标记和一些新方法[1-2]。闫巧、靳娜等人在研究各种溯源方案的基础上，提出了基于数据包标记的改进方案[3-4]。随着各种溯源方案的提出，如何解决IP溯源技术的追踪有效性、收敛速度、路由负载问题，仍是今后研究工作的重点。本文采用粒子群算法改进数据包策略，有效改进包标记效率，提高追踪速度，减轻路由负载，准确重构攻击路径。

1DDoS攻击概述

1.1DDoS攻击原理

DDoS(Distributed Denial of Service)分布式拒绝服务[1]，是在原有的DoS攻击基础上出现的一种新的攻击手段，DDoS攻击利用一些受控主机同时向目标受害主机发起DoS攻击，虚假的服务请求数量急剧增加，从而占用网络带宽，致使目标主机系统崩溃或资源耗尽而无法进行服务。这样洪水般的攻击破坏力极大且令人难以防范。

1.2DDoS攻击类型

DDoS攻击类型主要有两种：一种是带宽消耗型，另一种是资源耗尽型[2]。

带宽消耗型主要有UDP攻击和Smurf攻击。UDP攻击是通过发送带有虚假返回地址的UDP数据包。Smurf攻击是通过向网络中的广播地址发送大量的ICMP回应请求消息，并且把受害主机的IP地址伪造为源IP地址，这两种攻击都能占用网络带宽，造成网络阻塞而影响正常网络服务。

资源耗尽型攻击主要是SYN攻击。SYN攻击利用TCP的三次握手协议原理，向受害者发送大量的包含虚假返回地址的SYN数据包，受害者无法识别虚假地址，正常发送ACK报文，造成了大量的TCP半连接，从而耗尽系统资源。

2DDoS攻击中IP溯源问题描述

IP溯源技术[3]，是指准确定位攻击者源头并且重构攻击路径的一种技术。IP溯源的主要技术有两类，一类是反应式追踪，另一类是主动式追踪。

2.1反应式追踪回溯技术

反应式追踪又意为被动式追踪。主要有链路测试技术，是指在攻击进行的过程中通过人工测试路由器间的链路来确定攻击流的来源。链路测试技术因DDoS攻击的受控主机往往分散在多个网络中而难以被应用。

2.2主动式追踪回溯技术

主动式追踪主要方法有路由日志、ICMP回溯、包标记和一些新方法。路由日志策略是根据数据挖掘技术利用路由器的日志功能将路由器所转发的数据包的信息存储在路由器上找出数据包在网络中的传输的路径。ICMP回溯是指用户通过接收到ICMP回溯消息来分析出数据包生成时间、来源和权限的路径信息，重构出攻击路径。

包标记技术是指根据一定算法将追踪数据标记到经过路由器的数据包的IP报头的一些字段，受害者通过分析标记数据实现攻击路径重构。本文主要针对包标记算法进行改进，采用粒子群算法有效提高标记效率，减轻路由器负载。

2.3各种追踪方法的比较

表 1　各种追踪方法比较

如表1对综上的几种溯源方法进行了比较[4]，还需解决的问题有：

1)追踪速度问题。追踪速度的好坏影响后续防御工作的进展，是衡量追踪系统的一个重要的指标。

2)路由器的负载问题。路由器负载越低，对路由器数据转发工作的影响就越小，是衡量算法优劣的一个重要指标。

3基于粒子群算法的IP溯源技术研究

针对上述问题，本文提出解决方案，基于包标记算法进行改进，采用粒子群算法，提高包标记效率，减轻路由负载，有效进行IP回溯。

3.1粒子群算法分析

粒子群算法(Particle Swarm Optimization)，简称PSO[5]，通过研究鸟类捕食行为，采用群体间的合作机制来全局搜索最优解，算法简单易懂且需要设定参数较少，是1995年R.Eberhart博士和J.Kennedy博士发明的一种智能优化算法。

算法定义：在D维搜索空间中一个由m个粒子组成的群体以一定速度飞行，每个粒子由以下三个D维向量组成：

当前位置：Xi=(xi1,xi2,…,xiD);

历史最优位置：Yi=(yi1,yi2,…,yiD);

速度：Vi=(vi1,vi2…,viD)。

对于每一个粒子在搜索过程中都要考虑历史最优点和群体内其他粒子的历史最优点，在此基础上变化位置，其第d维(1≤d≤D),标准粒子群算法有如下等式：

vid=w·vid+c1·rand()·(yid-xid)+c2·rand()·(ygd-xid)

(1)

xid=xid+vid

(2)

式中：w为惯性权重，可以起到平衡算法全局搜索和局部搜索能力的作用；c1和c2通常等于2，这两个常数可以使粒子具有自我学习能力，向自身的历史最优点以及群体内的全局最优点靠近；随机函数rand()的取值范围为[0,1]。

对于离散空间，J.Kennedy和R.Eberhart于1997年通过对标准PSO算法改进了一个离散二进制PSO算法，速度更新公式没有变，但没有原始PSO的粒子位置更新公式。为了表示速度的值是二进制位取1的概率，速度的值被映射到区间[0,1]，映射的方法一般采用sigmoid函数：

(3)

这里表示位置取1的概率，粒子通过式(4)改变它的位置。

(4)

3.2基于粒子群算法的DDoS追踪

粒子群算法的特性是搜索全局最优粒子，那么在包标记过程中就可以利用这个特性来选择最有可能是DDoS攻击发送的数据包进行标记，从而提高包标记效率,有效减轻路由器负载,提高追踪效率。

3.2.1包标记算法描述

概率包标记技术(PPM)[6-7]是包标记技术的一种，是指路由器以一定概率将部分路径信息标记到经过路由器的数据包，受害主机通过分析一定数量的有标记信息的数据包重构完整的攻击路径。确定最佳的标记概率对路径重构的准确性起到至关重要的作用。基本PPM算法如下：

Marking procedure at router R:

For each Packet B and n be a random number from[0,1]

Ifn

Writer IPRinto B

3.2.2基于粒子群算法对概率包标记策略的改进

基于上述粒子群算法对概率包标记策略进行改进，利用离散粒子群算法的位变量取1的概率产生包标记概率，从而通过多次迭代，受害主机收到足够数量的有标记信息的数据包后，可通过分析数据包信息重构完整的攻击路径。

(1)设计DDOS网络攻击模型

假设DDoS网络攻击模型如图1所示。

图1　DDoS攻击网络模型

攻击者由R3、R5、R6发送攻击流给一台服务器，并伪造源IP地址进行攻击，使受害者无法提供给正常用户A等的合法请求服务。

(2)设计标记空间。文中标记信息的存放采取压缩边采样[8-9]的设计，将标记信息存放于IP报文的头部。在IPv4报头中可利用空间有服务类型(8位)、认证域(16位)和RF(1位)，共25位。其中：6位用来标记路由器到攻击者的距离；8位用来标记路由器的一个点或者一条边的信息；7位用来标记边的头结点的7位hash值；2位用来标记数据包标记痕迹；2位用来存储点或边的哪一段IP地址信息。

(3)确定标记概率。首先初始化粒子位置，利用矩阵进行二进制编码，设矩阵维数为6，则初始矩阵为

每个二进制位利用速度变化公式(1)产生速度，速度再根据式(3)转换成概率，也就是位变量取1值的机会，粒子再通过式(4)改变位置。

定义Vmax=6,那么s(vid)的值将在0.9975和0.0025之间，也就是包标记概率p的取值。

(4)重构攻击路径。粒子群算法可以通过多次迭代，得到最优粒子路径，最理想的矩阵赋值如下：

重构攻击路径有R3→R5→R6，追踪到距离攻击者最近的路由器3。

4仿真测试

对基于粒子群算法的DDoS攻击追踪过程进行仿真测试，分析其在追踪速度和路由负载等方面的性能。

4.1NS2仿真过程

NS2(Network Simulator Version 2)是一种具有开放源代码、丰富网络模拟功能和强大扩展功能的可供研究各种网络技术的网络模拟软件。

仿真环境：win7+Cygwin；软件版本ns-allinone-2.35；编程语言C++、Otcl。

为了验证仿真结果的有效性,仿真实验分为两种情况。实验一 ：仿真最简单的网络攻击模型。仿真模拟的网络拓扑图如图2所示。

图2　实验一网络拓扑图

实验二：仿真存在虚假源地址的攻击模型。仿真模拟的网络拓扑图如图3所示。

图3　实验二网络拓扑图

仿真过程：首先完成包标记空间的设计，修改 s-allinone-2.35 s-2.35common目录下的packet.h文件。然后记录标记过程，修改 s-2.35 race目录下的trace.h,trace.cc文件，标记工作的实现主要在DequeTrace类中的recv()函数中完成。接着实现路径重构，本实验agent采用TcpAgent类，在ns-2.35 cp目录下找到tcp.h,tcp.cc文件，重构过程主要在TcpAgent类的recv()函数中添加重构功能。本实验的application选定FTP，编写Otcl脚本即可直接使用。修改完成后重新编译NS2，根据测试网络编写运行脚本,绑定测试节点、设定网络攻击参数，最后运行脚本文件进行调用。

4.2仿真结果及性能分析

在两种仿真拓扑结构下，分别采用传统的PPM算法和改进后的粒子群算法，仿真结果记录在文件out.tr中。

4.2.1收敛速度

在传统的PPM算法中，假设l为传输路径长度，路由器以固定概率p0标记，离他最远的路由器标记的数据包到达受害主机的概率为

q=p0(1-p0)l-1

(5)

根据数学期望公式：

(6)

式中k为每个IP地址信息被分为k片。当l=32,p0=0.04时，重构路径大概需要1700个数据包。

文中根据sigmoid函数得到的标记概率p0取得平均值0.5远大于0.04，根据收敛时间的计算公式：

(7)

可知其收敛速度明显优于PPM算法。

4.2.2路由器负载

通过测试路由器的处理开销来评价路由器负载，标记次数越多，则说明处理开销越大，路由负担越重。结合粒子群理论研究，迭代次数一般不会超过32次，即可找到最优粒子。根据仿真实验数据也可以看出，收到标记过的包也在传统算法的基础上有所减少，如表2和表3所示。

表2　实验一中传统概率包标记算法和粒子

表3　实验二中传统概率包标记算法和粒子群算法

5结束语

针对DDoS攻击的溯源技术，基于粒子群算法，研究了如何提高包标记效率，有效重构DDoS攻击路径，准确定位攻击源，在追踪过程中改善速度问题和路由器负载问题。通过NS2进行了仿真测试，结果显示，基于粒子群算法的DDoS攻击溯源技术，具有高效、准确、有效减轻路由器负载的优势，对今后的研究有一定参考价值。

由于本文提出的基于粒子群算法的DDoS攻击溯源方案，只是停留在虚拟网络环境中，且现有理论研究较少，如何在实际网络中有效的实现还需要进一步的研究。

参考文献：

[1]张永铮,肖军,云晓春.DDoS攻击检测和控制方法[J].软件学报,2012,23(8):2058-2072.

[2]陈栋.DDoS防御方法分析[J].哈尔滨师范大学自然科学学报,2014,30(4):56-59.

[3]闫巧,雷琼钰.IP追踪新进展[J].小型微型计算机系统,2012,33(9):2027-2032.

[4]靳娜.DDoS攻击下的数据包标记优化方案的研究[D].成都:电子科技大学,2013.

[5]徐玉杰.粒子群算法的改进及应用[D].南京:南京师范大学,2013.

[6]杨俊,王振兴,郭浩然.基于扩展头随机标记的IPv6攻击源追踪方案[J].计算机应用研究,2010,27(6):2335-2337.

[7]周萍,高仲合.一种新的DDoS攻击检测算法[J].通信技术,2014,47(9):1080-1083.

[8]Xiao-jing Wang,Xiao-yin Wang.Topology-assisted deterministic packet marking for IP traceback[J].The Journal of China Universities of Posts and Telecommunications,2010,17(2):116-121.

[9]Ankunda R Kiremire,Matthias R Brust,Vir V Phoha.Using network motifs to investigate the influence of network topology on PPM-based IP traceback schemes[J].Computer Networks,2014,72(29):14-32.

(责任编辑：马金发)

Study of DDoS Attack Traceback Based on Particle Swarm Optimization

LI Aihua,XIAO Jinfeng,QIU Peng

(Shenyang Ligong University,Shenyang 110159,China)

Abstract：By researching the traceback technology of DDoS,the particle swarm optimization(PSO) is applied to improve the strategy of probabilistic packet marking,and design implementation of traceback.By testing on NS2 simulation platform,and the comparison analysis of the simulation results,it was shown that simulation successfully implemented DDoS attack traceback,and the proposed solution satisfies the performance requirements of speed and accuracy.

Key words：technology of traceback;DDoS；PSO；network simulation

中图分类号：TP393

文献标志码：A

文章编号：1003-1251(2016)02-0039-05

作者简介：李爱华(1996—)，女，副教授，研究方向：网络服务质量与网络安全。

收稿日期：2015-04-17