基于自适应包标记的RDDoS攻击溯源技术研究*

孙 鹏，吴 庆

(中国人民解放军72671部队，山东省，济南市，邮编：250022)

基于自适应包标记的RDDoS攻击溯源技术研究*

孙 鹏，吴 庆

(中国人民解放军72671部队，山东省，济南市，邮编：250022)

针对RDDoS攻击溯源问题，在包标记技术的基础上，提出了一种自适应的标记算法。通过动态调整标记概率，较好地解决了算法收敛速度和路由器负载问题，并针对传统包标记算法只能对DDoS攻击进行溯源的问题，设计了一种反射标记算法，使包标记技术能应用于RDDoS攻击溯源，最后对算法进行了理论分析及模拟研究，通过与经典包标记算法和动态包标记算法进行对比，验证了其良好的性能。

RDDoS；包标记；溯源

0 引 言

根据所需信息和追踪方法的不同，DDoS攻击溯源技术大致可以分为包标记方法、基于ICMP的追踪方法、路由日志法、链路测试法等，其中包标记是研究比较多的技术，为广大的研究者所青睐。该技术由Burch和Cheswick[1]首先提出，而后Savage等人对算法进行改进，研究提出一种概率包标记方法(Probabilistic Packet Marking，PPM)[2]，使用路由器概率的对经过的数据包记入标识信息，并对下级节点进行转发，处于终点位置的受害者接收到这些标记包后完成攻击路径的重构。Jenshiuh等人在概率包标记的基础上提出一种动态概率包标记算法(Dynamic Probabilistic Packet Marking，DPPM)[3]，用于解决远端路由器标记的数据包数量过少的问题。包标记算法根据标记信息的不同分为节点采样标记(Node Sampling)和边采样标记(Edge Sampling)。因为节点采样标记只能针对单一攻击源的DoS进行溯源，故目前研究焦点主要在于边采样标记算法，其中最具代表性的是Savage等人研究提出的分片标记算法(Fragment Marking Scheme，FMS)和Song等人研究提出的高级包标记算法(Advanced Marking Scheme，AMS)[4]，他们采用异或计算的方法将IP分段标记信息压缩存放，使得同一标记区域内含有相邻两个路由器IP地址信息，节省了标记字段所需的空间。

基于包标记的溯源算法具有较好的优越性，但各算法均无法对反射型分布式拒绝服务攻击(Reflected Distributed Denial of Service，RDDoS)攻击进行溯源，且给路由器带来了很多额外的负担。针对这些问题，本文提出了一种基于自适应包标记的RDDoS攻击溯源技术，设计了一种反射标记算法，使经典的包标记算法可以对DDoS攻击进行溯源。同时在动态概率包标记算法的基础上，设计了覆盖标记与不覆盖标记混合的自适应标记算法，减少了标记包数量，降低了路由器负载。

1 基于自适应包标记的RDDoS攻击溯源算法

1.1 算法总体设计

本文设计的针对RDDoS攻击的溯源算法由三部分组成：一是自适应标记算法，主要应用于路由器节点上，对自身转发和产生的数据包以一定概率标记上本节点的IP地址信息，而后向下级节点传递；二是反射标记算法，主要运行于反射节点，即网络中的DNS服务器等可能被当作攻击反射器的主机，用于解决RDDoS攻击中标记信息的存储和延续；三是路径重构算法，由受害者主机运行，用于统计和分析最终到达受害者的攻击包，完成标记信息重组和攻击路径重构，确定和找出攻击源。各算法运行的位置如图1所示。

图1 RDDoS攻击溯源算法运行位置示意

1.2 自适应标记算法

在DPPM算法中，路由器对所有数据包以一定的概率重复标记，对路由器造成了额外负担，为解决这个问题，本文提出一种自适应标记算法，路由器自主确定标记概率，并选择是否覆盖数据包旧有标记，在路径长度到达一个定值之前，数据包上携带的已有标记不被后续路由器覆盖，在超出这个长度之后再使用覆盖标记的方法，并在算法上保证每个路由器标记的数据包等概率的到达受害终端。

(1)标记概率的计算

假定(A，R1，R2，…，Rd，V)是攻击中的其中一条路径，A是攻击节点，V是受害节点，R1，…，Rd是网络中的路由器，d是由攻击节点路由到受害节点的跳数。假定路由器Ri以概率pi标记，受害者接收到由Ri标记的数据包的概率为qi，在不覆盖标记的条件下，为使重构时所需的数据包的数量最少，需要受害者收到每个路由器标记数据包的概率都相等，且都为1/d。

即：q1=q2= … =qd= 1/d

即：p1= (1-p1)p2= (1-p1)(1-p2)p3= … = (1-p1)(1-p2)…(1-pd-1)pd= 1/d

推导得：

p1=1/d,p2=1/(d-1),pi=1/(d-i+1),… ,pd=1

路由器标记数据包时并不清楚是否发生了攻击，也不会知道是发生了DDoS攻击还是RDDoS攻击，更不知道攻击路径的长度d，而仅仅是计算概率和执行标记动作。在DDoS情况下，最大路径长度一般不大于32，路由器的标记概率直接采用pi=1/(d-i+1)，在RDDOS情况下，最大路径长度超出32的部分我们以Pi=1/i进行覆盖标记，即：

(2)标记信息的存放

标记信息的存放类似压缩边分段采样算法(Compressed Edge Fragment Sampling)，利用IP包头中未使用的位置来记录标识追踪信息。IP报头中的RF位保留未用，可以用作标志位，同时在现有TCP/IP协议的实现中，未做强制使用的位空间还有服务类型(8位)和认证域(16位)，所有可供利用的空间计有25位。

图2 标志位在IP报头中的存储

图中的标志位中，distance域(6位)表示产生标志的路由器离攻击者的跳数，hash域(7位)用于记录由边计算出的hash值，edge域(8位)用于存储路由器节点或者由两个路由器构成的一条边的信息，offset域(2位)表示节点/边被分割成的4段中哪一段IP信息，flag域(2位)用于区分数据包是否载有标记和是否曾被边界路由器标记。Flag域被初始化为00，表示未做任何标记；flag被赋值01，表示数据包被边界路由器之外的路由器标记；flag被赋值10，表示该数据包被边界路由器标记。

(3)标记算法的具体实现

自适应标记算法根据攻击路径长度设定两个标记阶段：一是当路径长度不超过32时，路由器对转发的数据包不重复标记；二是路径长度大于32时，路由器采用覆盖标记算法。整个标记过程为：

1) 路由器进行标记概率计算。首先根据距离域d计算产生标记概率p，并计算出一个处于(0,1]范围的随机数u，当0

2)当flag=00时，表明该数据包不曾被做过标记，从路由器IP的4个分段中随机选择一段标记在edge域，并将offset置为相应的偏移量；计算该路由器32位IP地址的7位hash值(为减少hash冲突，可适当增加hash位数，IP包头中的部分未使用位可提供存储)，结果存入hash域；若路由器是边界路由器，置flag域为10，若不是则置为01；将距离域d置为0。

3) 若flag!=0且d=0，表示相邻的上游路由器已标记过该数据包，根据offset段的值取出edge值与路由器对应IP地址段相异或，将结果记录到edge域并将距离域d加1。

4)若flag!=0且d> 31，可以进行覆盖标记，从路由器IP的4个分段中选择一段标记在edge域，并将offset置为相应的偏移量；将该路由器32位IP地址hash成7位，存储到hash域；将flag域和距离域d分别置为01和0。

5) 当u>p时，若flag!=0且d=0，根据offset段的值取出edge值与路由器对应IP地址段相异或，将结果记录到edge域并将距离域d加1；若flag!=0且d!=0，将距离域d增加1；若flag=0不做任何操作，直接转发数据包。

1.3 反射标记算法设计

(1)反射器存储结构

反射器中的存储结构基于Bloom Filter进行设计，保留了存储高效和查找快速的优点(文献[5]中详细分析了Bloom Filter结构的效率及错误率)，并进行功能改进使之能应用于包标记的存储。结构中包含了一个位数组和一组链表，使用k个hash函数对元素进行hash运算，将运算结果用作链表索引。链表由一组PACKET标记节点组成，每个标记节点由mark、count和下一元素指针组成，记录曾出现过的标记。数据结构如图3所示。

图3 反射器存储结构

其中mark用于存储标记数据包中携带的标记信息，count用于记录多少个携带这种标记的数据包到达了反射器，记录数值的目的是为了在合适的时机删除此PACKET记录，收回占用的存储空间。

(2)反射器标记算法

反射器标记算法由存储标记和复制标记两部分组成，存储标记是指将路由器标记的数据包的摘要和标记存入反射器存储区域，复制标记是从反射器存储区域提取标记，并复制到回应包头部的相应区域。流程如图4所示。

图4 反射器存储及复制算法流程

(3)路径重构算法

当受害端收集到足够的标记数据包后，由数据包头部提取出标记，对各标记重新分组和统计数量，最后重构出攻击路径。算法如下：

1) 受害端提取出数据包头部的标记信息；

2) 按距离域对标记信息分组，同一组中放置距离域相等的标记；

3) 对距离域相等的组中的标记按hash函数进行分组，hash值相等的归为一组；

4) hash值相等的组中按offset值再次分组，共分为4组；

5) 从这4组offset中各取一个IP段，按偏移量标识的次序重新组成完整IP地址；

6) 重复5，直到找出所有这种组合；

7) 按距离值从小到大依次从不同距离域分组中拿出IP地址，先是用距离值最小的IP地址去异或次小的IP，得到的结果再去异或距离值再小一点的，重复完成所有距离值的IP地址。

8) 异或得到的各值就是攻击路径上的各路由器IP，按距离的由小到大依次排列这些集合中的IP地址，结果序列即为由攻击端到受害端的攻击路径。如果攻击是多源的反射型分布式拒绝服务攻击，可计算出多条攻击路径。

2 性能分析

2.1 兼容性分析

兼容性是指对网络协议的改造与当前网络协议是否兼容。自适应标记算法重载了IP报文头部的identification(16位)、tos(8位)和rf(1位)三个区域，identification域用于处理网络层的分段，现在的网络应用一般都有MTU自动发现功能以减少分段的发生，实际网络应用中分段发生的概率只有不到0.25%[6]，对identification域的占用不会影响绝大多数的网络应用；tos域表示服务类型，在RFC791中规定了tos域的意义，后来RFC1394对tos域定义了新的意义，再后来RFC2745规定tos域被用作QoS服务，TOS域的使用一直没有统一严格的规定，可以用来作为标记区域；rf位在IP报头中用作保留位。对这三个区域的重载对现行IP协议不会产生太大影响，有着良好的兼容性。

2.2 收敛性分析

PPM算法中，假设攻击路径长度为d，路由器的标记概率为p，最远的路由器产生的标记成功跟随数据包到达攻击端的概率为：q=p(1-p)d-1，由Coupon Collector Problem问题求解[7]，可知PPM算法构建出完整攻击路径需要的数据包数量的数学期望：

其中k为每个IP地址分片数量，当d=32，p=0.04时，需要1 700个数据包才能重构出完整路径。

DPPM算法中，每个路由器标记数据包成功到达受害端的概率相同，为1/d，重构完整路径需要数据包数量的数学期望为：

EDPPM(x)

当d=32，k=4时，DPPM算法需要620个数据包来重构完整路径。

本文提出的自适应包标记算法中，当距离值d小于32时，因为我们设定路径长度是32，故新算法重构完整路径需要数据包数量的数学期望要大于DPPM，当d等于32时，新算法的收敛性与DPPM相同，当d大于32时，新算法收敛性与DPPM持平，都趋于理想值。由此得出结论，EDPPM(x)≤E新(x)

2.3 路由器负载分析

在所有使用包标记进行攻击源追踪的方案中，都会对路由器造成一定额外负担，主要体现在对大量数据包做标记上面。PPM算法存在弱收敛的问题，路径的重构需要大量携有路由器标识的数据包，整体来看所有路由器负载都很重；在DPPM算法中，路由器根据距离值动态计算标记概率，离攻击端越近，标记越频繁，并且全程攻击链路的下游路由器都可能覆盖上游路由器的标记，额外增加了标记负担；本文的新标记算法在32跳之前路由器不覆盖标记，免除了PPM和DPPM中的额外标记负担，因而整体标记负载优于PPM和DPPM算法。

3 模拟实验

3.1 收敛性实验

考虑到需要对比不同路径长度下重构用到的数据包数量，本文采用线性拓扑结构进行模拟实验。如图5所示，线性结构每次使用不同的结点数量，并在做APPM算法实验时设定其中一个结点做为反射器，比较无反射器时PPM算法、APPM算法和有反射器时新算法重构完整路径用到的数据包数量。

图5 线性结构

从节点数为5开始实验，在每个相同的结点数上对PPM、DPPM和新算法各做8组，至结点数为63为止，每组8次取得的结果中去掉最大值和最小值后取平均，得到路径长度与攻击包数的关系曲线如图6所示。

图6 各算法在不同路径长度下重构所需数据包的数量

由实验结果知，路径长度不超过32时，新算法表现优于PPM算法，稍逊于DPPM算法；在路径长度超出32跳之后，新算法性能与DPPM算法持平，优于PPM算法。

3.2 路由器负载实验

为了定量计算各标记算法对路由器造成的额外负担，对比出各算法在路由器负载中的性能表现，我们统计各算法在完成路径重构时，所有路由器做出标记动作的总次数。具体实现是在数据包中加入一个mark_count变量，路由器对数据包做出一次标记，mark_count值就加一，所有的mark_count值在受害端汇总得出最终结果。如图7所示。

图7 各算法路由器标记总次数对比

由图可知，相比PPM和DPPM算法，新算法在标记数据包的数量上要少很多，证明了新算法的减轻路由器负载上比PPM和DPPM算法有明显的优势。

4 结 语

本文针对RDDoS攻击提出一种基于包标记算法的追踪方案，该方案根据路径长度采用自适应标记策略，增强了收敛性并减小了路由器负载，同时在反射器上采用Bloom Filter原理建立了一种标记信息存储结构，降低了存储消耗并加快了存取速度。该方案同时适用于DDoS和RDDoS攻击溯源，具有普遍适用性。在攻击者控制了网络中某个路由器，并对该路由器标记信息进行篡改时，如何能检测出标记信息的伪造是后续需要进一步研究的。本文以已检测到攻击作为前提条件，在后续工作中将考虑引入实际的检测技术，实现检测与追踪联动。

[1] Burch H,Cheswick B. Tracing Anonymous Packets to their Approximate Source[C]. Proceedings of the 14th Conference on Systems Administration, 2000 LISA XIV, New Orleans, Louisiana, USA, 2000.

[2] Stefan Savage, David Wetherall, Anna Karlin, et al. Network Support for IP Traceback[J]. IEEE/ACM Transon Networking, 2001, 9(3):226-237.

[3] Liu Jenshiuh，Zhi Jianlee，Chung Yehching. Dynamic Probabilistic Packet Marking for Efficient IP Traceback[J].Computer Networks, 2007, 51:866-882.

[4] Song D, Perring A. Advanced and Authenticated Marking Schemes for IP traceback[C]. Anchorage, Proceedings of IEEE INFOCOM, Alaska USA, 2001, 2: 878-886.

[5] Broder A, Mitzenmacher M. Network Applications of Bloom Filters: A survey[J]. Internet Mathematics, 2005,1(4):485-509.

[6] Stoica I,Zhang H. Providing Guaranteed Services Without Per Flow Management. In:Proceedings of the 1999 ACM SIGCOMM Conference,pages 8l-94,Boston,MA,Aug.1999.

[7] 郝尧, 陈周国, 蒲石等. 多源网络攻击追踪溯源技术研究[J]. 通信技术, 2013, 46(12):77-81. HAO Yao, CHEN Zhou-guo, PU Shi,et al. Research On the Tracing Technology of Multi-source Network Attack[J]. Communications Technology,2013,46(12):77-81.

RDDoS Attack Source-Tracing Technology based on Self-Adaptive Packet-Marking

SUN Peng， WU Qing

(Unit 72671 of PLA, Jinan Shandong 250022, China)

Aiming at the source tracing of RDDoS attack, a self-adaptive algorithm based on package-marking technology is proposed. By dynamically adjusting marking probability, convergence speed of the algorithm and payload of the router are fairly solved. Traditional packet-marking algorithm can only trace the source of DDoS attacks, and in light of this, a reflective marker algorithm is proposed and designed, thus enabling the package-marking technique to be applied in the source tracing of RDDoS attack.

RDDoS; package-marking; source tracing

date:2015-01-10；Revised date：2015-03-19

文献标志码：A 文章编号：1002-0802(2015)04-0478-06

孙 鹏(1972—)，男，博士，高级工程师，主要研究方向为计算机网络安全；

吴 庆(1984—)，男，硕士，工程师，主要研究方向为计算机网络安全。

10.3969/j.issn.1002-0802.2015.04.019

2015-01-10；

2015-03-19