IP追踪中的包标记算法＊

吴蓉晖，吴 岚

（湖南大学信息科学与工程学院，湖南长沙 410082）

IP追踪中的包标记算法＊

吴蓉晖†，吴 岚

（湖南大学信息科学与工程学院，湖南长沙 410082）

针对基本包标记算法效率低的问题，提出了一种改进算法.通过优化传统的路径信息编码方式，对其标记过程和重构过程作了相应的修改，使受害者可以更快地重构出攻击路径.仿真实验结果表明：该算法能够有效地减少组合次数，提高追踪效率，并且大大降低了误报率.在实际的拒绝服务攻击中能够使受害者更快更准确地追踪到攻击者，从而减少损失.

IP追踪；网络安全；包标记；拒绝服务攻击；分布式拒绝服务攻击

计算机网络对人们的生活、工作、学习方式等很多方面产生了深远的影响，网络安全越来越受到重视，其中分布式拒绝服务攻击（Distributed Denial of Service，DDoS）由于具有易实施、难防范、追踪困难等特点，成为了互联网最难解决的安全问题之一.网络追踪作为对付拒绝服务攻击的重要手段，也得到了国际同行的重视.国内外的许多学者都对此提出了多种追踪方案，其中包标记以其追踪效率高，收敛时间短等优势成为了研究热点.其中最具代表性的有Savage等［1］提出的概率包标记算法（Probabilistic Packet Marking，PPM），其无论在路由器开销还是TCP／IP兼容方面都具有突出的优势，概率包标记也称为基本包标记.基本包标记在拒绝服务攻击下的攻击者追踪方面是一个开创性的工作，具有重要意义.

Park等［2］分析了基本包标记在攻击者伪造IP地址时追踪的不确定性.文献［3］通过实验演示了基本包标记在进行攻击路径的重构时具有计算量大、误报率高等缺点，并提出了2个方案，分别称为高级包标记（Advanced Packet Marking，APM）和带认证的包标记（Authenticated Packet Marking），这2种方法在重构攻击路径时，需要网络的拓扑信息.Dean等［4］提出的基于代数编码的包标记也是在基本包标记的基础上进行研究的，其动机来源于基本包标记的组合爆炸和误报率高的缺点.文献［5］提出了基于路由器编码的自适应包标记.文献［6－7］都各自提出一种动态概率包标记方法（DPPM）.文献［8］将一种改进的压缩边分段采样算法（Compressed Edge Fragment Sampling，CEFS）为基础与可变概率标记相结合，提出一种复合式标记方法PCEFS.文献［9］采用的因特网快速追踪算法，只需1 bit就可以记录节点的跳数关系，大大节约了标记空间.文献［10］利用中国余数定理的唯一性来标记IP分块的特征，有效避免了hash碰撞的发生，具有一定的创新性.本文在PPM基础上提出了一种新的标记方法，其在误报率、收敛时间、计算量等方面均比基本包标记优越，具有很强的可执行性.

1 概率包标记

为了快速追踪到攻击者，最好的方法是将路由器地址信息全部标记到数据包中，当受害者收到这些包后，就可以直接得到路径信息.但是，由于MTU（最大传输单元）的限制，这种做法明显行不通.因此只能在数据包中标记部分路径信息.文献［1］采用的方法是将IP与其32 bit的hash值（作为校验码）以比特为单位间隔穿插得到64 bit.然后将此64 bit分为8块，每块8 bit，并将其分别编号为0，1，…，7（即偏移offset），如图1所示.当向数据包嵌入路由信息时，将距离和8个分块之一以及相应的偏移嵌入到该数据包的标记域.为了在接收方能得到准确的距离信息，在对包进行标记时需将距离域置为0，如果紧接着下一个的路由器不标记该包，则其将距离增加l，并把自己的与偏移对应的块与数据包中的块异或重新填入.在Internet中，数据包所经过的路径一般不超过30［5］，因此，用5 bit就可以存放距离信息.所以标记域需要5＋8＋3共计16 bit的空间.基本包标记中边信息的重组如图2所示.

在IP报文的格式中，包头的Identification域是用来识别在一个分段数据包的重组时的不同分段的，而在Internet中，只有大约不到0.25%［11］的包会分段传输，也即Identification域基本是不被采用的，故用于包标记算法标记路径信息所需的16 bit的空间可以存放在Identification域中.

图1 IP地址与校验码按bit穿插，然后分组Fig.1 The hash is interleave with the address then group into 8 fragments

图2 边信息重组图Fig.2 Reconstructing a candidate edge

1.1 计算量

概率包标记算法在路径重构时，需要检查每种组合是否为合法的IP，即通过计算该组合的hash值是否与其携带的hash值相等，而在此过程中，每一次的hash计算是最大的开销，故可以用计算hash的次数来衡量该路径重构过程的计算量，而hash次数与每一种组合是一一对应的，因此只需计算出总共有多少种组合就可以大约估计出整个过程的计算量.

若在实际攻击树中有k个节点到受害者的距离为d＋1（距离域的值为d），则对于相同的d和相同的偏移，会有多个不同的分块.假设偏移为0，1，…，7的互不相同的分块数量为k0，k1，…，k7，则需检查组合.假设最远的攻击者距离受害者为L＋1，则整个重构过程的计算量为

1.2 误报数

若一个路由器在重构出的攻击路径上，而不在实际的攻击路径上，则称此为一个误报.在前面的条件下，有k个节点到受害者距离为d＋1，故任意8个随机块的组合通过hash检测的概率为2－32k，即在种组合中只有k种组合会得到合法的节点，而其余种组合中通过检测的数量平均为：

由式（1）可知，如果ki不小于16，则平均误报数大于k.

2 改进算法

通过对概率包标记算法标记过程的分析，发现路由器是将IP地址（32 bit）与其hash值（32 bit）按位穿插得到64位，将其分为8 bit块，每一块均携带IP值与hash值，这样，在路径重构时需要将所有分块全部进行重组，再逐一hash，故工作量非常大.因此，将按位穿插改为拼接，即将hash值直接添加到IP值的后面，如图3所示，仍然是64位分为8 bit块，这样，偏移为0～3块携带的为IP地址信息，而偏移为4～7分块携带的是hash信息.在最后的路径重构时，只需偏移为0～3的块参与组合即可，极大地减少了组合次数.

图3 将IP地址的hash值直接附加到IP后面Fig.3 The hash add behind the IP address

具体步骤为：将hash（IP）添加到IP后面，得到64位，分为8 bit块，共8块，路由器随机抽取一块添加到标记域当中.当受害者收到足够的数据包时，将数据包按距离域与偏移域的值分为若干个集合，当距离值相等时，只需组合前4个集合（offset为0，1，2，3）中的数据，得到个集合，然后检查这些集合中哪些构成合法的IP地址.检查方法：对一个组合的32 bitIP地址求其hash（IP），然后按顺序分成4块8 bit的块，然后检查后4个集合（offset为4，5，6，7）中是否都分别包含了这4个块，如果包含，则认为这一组合为一个合法的IP.改进后的算法描述如下：

3 仿真分析

为了模拟大规模DDoS攻击，且能够方便地改变实验配置以进行多组不同的实验，故采用普遍使用的NS-2仿真软件进行模拟测试.

NS-2不支持PPM算法，为了构建DDoS攻击和PPM算法模拟平台，必须对NS-2进行扩展.将NS－2的IP包头修改，添加一个16位的字段表示IP数据包头中的Identification字段，利用该字段填写包标记信息，并在Classifer类中添加需要实现仿真的各种算法.本实验过程是将基本包标记、高级包标记以及拼接算法进行性能分析，添加的成员分别为PPMAlgorithm， APMAlgorithm和Conn Algorithm.在仿真过程中，为实现典型的PPM算法，节点上绑定UDP，使用CBR对象生成流量，并且按照不同需求部署攻击流量和正常流量的比例.对于改进的PPM方法，可以通过脚本修改相应的参数，从而可灵活地在相同环境下针对不同的PPM方法模拟大规模DDoS攻击和反向追踪执行效果.

根据Gnuplot NS-2仿真过程记录data文件，输出的实验数据如图4所示.由图4可知，相对PPM，拼接算法无论在重构速度还是包需求量方面均有较大优势；即使相对于性能较好的APM，新算法也表现出了较好的性能.文献［5］的作者采用了一种自适应包标记算法，将文献［5］中的数据与实验得出的结果比较分析可知，虽然前者在路由器未被攻占的条件下性能较好，但在路由器参与伪造的情况下，新算法表现出了较大的优势.再与文献［12］比较，攻击路径长度在2～25个内，新算法在包数量上明显比前者低，而在收敛时间上，其处在百数量级，而文献［13］中的数据已经上千.

图4 PPM，APM以及改进算法的重构时间和所需包数对比Fig.4 The contrast of the reconstruction time and the number of the packet between PPM，APM and the new algorithm

4 结 论

本文通过对PPM算法的分析，将原先的IP地址与其hash值按位穿插改为拼接，并且对其重构过程也作了相应修改，极大地减少了受害者重构路径的计算量并有效减少了误报.仿真实验结果表明，采用拼接的方法明显降低了PPM的收敛时间以及需要数据包的个数，从而能够更快、更准确地追踪到DDoS攻击者.

［1］ SAVAGE S，WETHERALL D，KARLIN A，etal.Practical network support for IP traceback［C］／／Proceedings of the 2000 ACM SIGCOMM Conference.Stockholm，Sweden：ACM Press，August，2000：295－306.

［2］ PARK K，LEE H.On the effectiveness of probabilistic packet marking for IP traceback under denial of service attack［C］／／Proceedings of IEEE INFOCOM’01.Anchorage，Alaska：IEEE Computer and Communications Societies，April，2001：338－347.

［3］ DAWN X S，PERRIG A.Advanced and authenticated marking schemes for IP traceback［C］／／Proceedings of IEEE INFOCOM.Alaska：IEEE Computer and Communications Societies，2001，2：878－886.

［4］ DEAN D，FRANKLIN M，STUBBLEFIELD A.An algebraic approach to IP traceback［C］／／Network and Distributed System Security Symposium Conference Proceedings，NDSS’01.San Diego，California：IEEE Computer Society Press，February，2001.

［5］ LI De-quan，SU Pu-rui，WEI Dong-mei，etal.Router numbering based adaptive packet marking［J］.Journal of Software，2007，18（10）：2652－2661.

［6］ 赵陇，吴辰文.基于动态概率包标记的IP追踪技术研究［J］.计算机技术与发展，2008（12）：217－219.

ZHAO Long，WU Chen-wen.IP tracing technology research based on dynamic probabilistic packet marking［J］.Computer Technology and Development，2008（12）：217－219.（In Chinese）

［7］ FENG Bo，GUO Fan，YU Min.Dynamic probabilistic packet marking based on PPM［C］／／2009 Second Pacific-Asia Conference on Web Mining and Web-based Application.Wuhan，China：IEEE Computer Society Press，June，2009：289－292.

［8］ 高大鹏，於时才，闫文芝.复合包标记IP追踪算法研究［J］.计算机工程，2009（10）：115－117.

GAO Da-peng，YU Shi-cai，YAN Wen-zhi.Research on composed packet marking for ip traceback algorithm［J］.Computer Engineering，2009（10）：115－117.（In Chinese）

［9］ YEAR A，PERRIG A，SONG D.FIT：fast internet traceback［C］／／Proceedings of 24th Annual Joint Conference of the IEEE Computer and Communication Societies：INFOCOMM 2005.Washington，DC：IEEE Computer and Communications Societies，2005：1395－1406.

［10］徐劲松.一种改进的路由包标记追踪方案［J］.计算机应用，2009（5）：1316－1320.

XU Jin-song.Improved router packet marking tracking scheme［J］.Journal of Computer Applications，2009（5）：1316－1320.（In Chinese）

［11］STOICA I，ZHANG H.Providing guaranteed services without per flow management［C］／／Proceedings of the 1999 ACM SIGCOMM Conference.Boston，Massachusetts：MCM Press，Aug，1999：81－94.

［12］ZHOU Zai-hong，XIE Dong－qing，JIAO Bing-wang.A maekawa set based marking scheme［J］.Information Technology Journal，2009，8（4）：504－512.

Research on the Packet Marking Algorithm for IP Trackback

WU Rong-hui†，WU Lan

（College of Information Science and Engineering，Hunan Univ，Changsha，Hunan 410082，China）

To solve the problem of low efficiency of probabilistic packet marking，an improved algorithm was proposed.This new algorithm optimizes the encoding of path information and modifies the marking and reconstruction process，so that victims can quickly reconstruct the attack path.Simulation results have shown that the new algorithm can effectively reduce combination frequency，improve tracking efficiency and greatly reduce the false positives rate.In the actual denial of service attack，victims can track the attacker faster and more accurately，thus minimizing the damage.

IP traceback；network security；packet marking；Denial of Service（DoS）；Distributed Denial of Service（DDoS）

TP393

A

1674-2974（2011）06-0075-04＊

2010-12-03

国家自然科学基金资助项目（60803130）

吴蓉晖（1967－），女，河南太康人，湖南大学副教授

†通讯联系人，E-mail：wrh＠hnu.cn