基于IP地址重拼接的DDOS攻击源追踪算法
开篇：润墨网以专业的文秘视角，为您筛选了一篇基于IP地址重拼接的DDOS攻击源追踪算法范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！
摘 要： 为了提高对分布式拒绝服务(DDoS)攻击源反向追踪的效率和准确度，提出了一个新算法。此算法不同于AMS(Advanced Marking Schemes)算法，是利用IP地址拼接技术，重定义IP数据包头部分字段，利用一种新的路由器地址编码格式，使得一个数据包携带更多路由地址信息，提高重构路径的效率，大幅降低误报率。相对于AMS算法,新算法明显提高了IP反向追踪的性能，降低了误报率。
关键词： DDOS攻击； 地址拼接； 追踪算法； IP数据包
中图分类号：TP393.08 文献标志码：A 文章编号：1006-8228(2012)05-35-02
DDOS attack source tracing algorithm based on the IP address re-stitching
Zhao Jie
（Department of Information Technology and Management , Zhejiang Police Vocational Academy, Hangzhou, Zhejiang 310018, China）
Abstract： To improve the distributed denial of service (DDoS) attack source traceback efficiency and accuracy, proposed a new algorithm that compared to AMS (Advanced Marking Schemes) algorithm, using the IP address of stitching techniques, re-define the IP data header part of the field, using a new router address coding format, making the route a packet to carry more address information to improve the efficiency of reconstruction of the path, dramatically reducing the false alarm rate. Relative to the AMS algorithm, the new algorithm significantly improves the performance of IP traceback, reduce false alarm rate.
Key words： DDOS； address stitching； tracking algorithm； IP packets
0 引言
当前各类网络安全威胁中，拒绝服务攻击（DOS）和分布式拒绝服务攻击（DDOS）因其危害大、难以彻底防范、攻击来源难确定等成为网络攻击者最常采用的方法。为了隐藏其真实来源，它们利用伪装IP地址进行攻击，这是IP反向追踪困难的主要原因。但是，尽管IP数据包头地址是伪造的，然而数据包从源头到目的地所经过的路由器等网络转发设备还是会记录下攻击路径，利用这点我们可以重构攻击路径找到攻击源[1]。
1 数据包标记追踪算法
1.1 基本数据包标记算法[2]
Burch等提出，将路由信息全部插入数据包中，当受害者收到这些数据包时，从中即可获得相关路径信息，便可重构出攻击路径。但向数据包中插入过多的路由信息，会导致数据包长度超过路径的最大传输单元，造成数据包不必要的分段。
1.2 高级数据包标记（AMS）算法
AMS的主要思想是，将IP数据包头中标记域分为：distance域、flagID域和edge域，每个路由器以固定概率p决定是否标记数据包，把两个路由器地址信息“异或”后的Hash值插入数据包头标识域来减少存储空间。在重构路径中，AMS算法利用了“异或”的数学特性即aba=b，从最后一个路由节点开始逐跳求出路由器地址信息，从而构造出整个攻击路径。
由于反向地址追踪的准确性和高效率是由每个数据包所携带的路由信息所决定的，如果数据包头能够携带更多信息，则能大幅降低重构路径算法的收敛时间和误报率。
2 IP地址拼接的包追踪算法
高级数据包标记虽然比基本数据包标记误报率有所降低，但是仍然不理想，这是由数据包头标记的格式所决定的[3]。本文提出一种新标记算法，通过改变IP数据包头中标记域编码格式，达到减少重构路径误报数量的目的。
2.1 算法思路
利用RF位在当前网络应用中未被使用特点，对IP数据包头中标识域（16bit）和RF位（1bit）的编码格式进行重定义，如图1所示。用20bit对路由器进行编码，并分为4个分片。当路由器决定标记一个数据包时，从4个分片中随机等概率将1个分片写入标记域block1中，偏移域offset则置为相应分片号。考虑到网络数据包从源到目的地址所经过节点数量不会超过32跳，将固定值32写入distance域，同时将block2置0。下游节点路由设备收到数据包，则执行以下动作：
⑴ 接到数据包后检查block1域，如果block1域通过验证，则该路由器从自己的20bit中取出对应分片写入block2中。
⑵ 如果block1和block2都通过验证，则不执行任何动作。
图1 IP数据包头编码变化
算法描述如下：
for each incoming packet w
let x be a random number from[0...1)
if x
{ choose a int number j from [0…4]
w.block1 fragment[j];
w.offset j;
w.distance 32;
w.block2 0; }
if x≥p
if block1 through authenticate
{ if block2 through authenticate
do nothing;
else w.block2fragment[w.offset]; }
在最大限度保留IP数据包头原有标记含义的基础上，对数据包头中标识域存储格式进行重定义，并借用RF位与标识域进行拼接，就可达到减少重构路径误报数量的目的。
2.2 攻击路径重构过程
被攻击者收到标记包时，利用固定值32与当前distance字段的差值可得到距离值d，并在获得上游拓扑结构图GM后，以被攻击者为根节点进行广度优先遍历。首先，把收到数据包依据不同距离值组成集合δ[d];当d=0时列出所有与它相邻节点和与之匹配路由器IP地址，并将这些节点插入S0中；逐跳向上匹配，直到d达到最大距离值；最终，被攻击主机将得到整个攻击路径{Sd}0≤d≤max。
3 包标记误报率分析
3.1 高级包标记的误报[4-6]
对于高级包标记，设被攻击者得到的距离为d+1，偏移位j的不同8bit的hash值分别为kj，j=0…7。由于一个随机8bit数属于kj个值的概率为2-8，在Q-K个路由器中，任一通过检验的概率为2-64∏7，因此，在被攻击者d+1处，高级包标记的误报平均为：
3.2 地址拼接算法的误报
设被攻击者到d+1处偏移位0,1,2,3的不同分块有Ni个，i=0,1,2,3。则在重构过程中，对于个分块，共有-K种组合。当-K个组合中有一个通过校验就构成误报。每个路由器信息用20bit编码地址信息，用4个状态表示偏移位信息，所以误报通过的概率为2-80Q。地址拼接算法的误报平均数：
3.3 误报率分析
通过对高级包标记算法和地址拼接算法误报率的分析，我们可以得到高级包标记和新算法的误报比值为：
误报率比值=
利用误报比值公式我们可以得知，当Kj≥125时，误报数比值会非线性增加，如图2所示，由此我们可以知道新算法更能适应大规模分布式拒绝服务攻击。
图2 距离d处模拟DDOS攻击曲线图
4 结束语
基于地址拼接的ip包追踪算法充分利用了IP包头容量空间，在最大限度不破坏IP包头原有定义的基础上，借用了Identifler域和RF域的存储空间，所设计的一种路由器编码格式使得一个数据包能携带更多的路由地址信息。采用IP地址拼接的标记算法，在路由路径重构过程中能降低运算量并且大幅降低误报率。
参考文献：
[1] 赵德山.曹斌.多Agent的ddos源地址追踪方法研究[J].计算机工程
与设计,2010.31(8).
[2] 王燕.网络攻击追踪技术性能分析[J].计算机应用与软件,2011.28(3).
[3] 王浩.网络DDOS攻击犯罪及其源地址追踪的研究[D].云南大学,
2009.
[4] 董玲.陈一民,朱正江.DoS攻击的研究与源地址追踪[J].计算机工程
与科学,2004.26(3).
[5] 杨德山.张璐璐.基于IP地址分段的DDoS路由追踪技术[J].合肥工
业大学学报（自然科学版）,2008.31(7).
[6] 张震,康有政,崔林立.网络攻击追踪方法的技术分析与实现模型[J].
中国公共安全(学术版),2007.1.