基于Huffman编码的包标记算法研究

李明珍，覃运初，唐凤仙

(河池学院 计算机与信息工程学院，广西 宜州 546300)

0 引言

随着网络技术的发展与推广应用，网络日益渗透到社会的各个领域，给人们带来方便的同时，也引发了一系列网络安全问题，其中以DDoS攻击问题最为突出。

DDoS攻击的实质，是指攻击者利用傀儡机发送大规模无用的数据来占用网络带宽或主机资源，当无用的数据占用完所有网络资源时，造成网络瘫痪，即用户正常的网络服务请求无法得到满足。有效遏制DDoS攻击的关键在于攻击源的定位，确定攻击者IP地址。确定攻击者IP地址后，在边界路由器设置包过滤规则，过滤拥有攻击者IP地址的数据包，从而有效抵抗DDoS攻击。

IP追踪技术，是一种攻击源定位技术，旨在通过提取IP地址信息定位攻击源。在IP追踪技术中，包标记算法［1］具有易操作、管理代价小、不需要ISP合作等优点，是研究的热点。文献［2］对IP追踪技术进行综述，对比分析了各种包标记算法的优缺点，指出选择“标识”字段(16 bit)作为标记区域，以一定概率标记数据包，标记的信息很有限，重构攻击路径时所需数据包个数随路径长度的增长呈指数增长——最弱节点问题;文献［3－4］针对包标记最弱节点问题，提出动态概率包标记算法，有效解决了最弱节点问题，但是也增加了路由器标记概率计算的复杂度;文献［5］描述了IPv4数据报首部的路由选项字段功能，该字段可以记录路径，但空间有限，只有40 Byte，不能够记录完整的路径;文献［2，6］提到的节点附加与文献［5］中的路由选项思想类似，但是会导致不必要的分包;文献［7］提出基于Huffman编码的包标记算法，该算法记录的是链路号而不是IP地址，减少标记内容，但要求路由器保持一份链路信息表。

本文结合文献［2，6－9］的算法思想，提出一种增加标记空间、减少编码长度和增加算法适用范围的改进算法。

1 相关知识

1.1 IPv4数据报格式

图1 IPv4数据报格式［10］

图2 IPv4选项格式［10］

1.2 IPv6数据报格式

图3 IPv6数据报格式［11］

1.3 Huffman编码

Huffman编码，是一种无损数据压缩方法，根据字符出现的频率来构造平均长度最短的码字。本文根据数据报到达一条链路的频率的高低来对其编号，频率越高编号越小，如此，得到的编码最短。

图4 IPv6扩展首部格式［11］

2 算法改进

2.1 算法思想

本文提出在IPv4下选择“选项”字段作为标记区域，采用Huffman编码标记链路号;利用IPv6的隧道模式，在IPv4到IPv6网络切换时增加一个复制操作，将标记信息转存到IPv6的hop－by－hop扩展首部，改进算法适用于IPv4和IPv6网络，且只需一个标记包即可完成攻击路径重构。

2.2 标记内容

改进算法要求每一个路由器维持一个链路表，如图5所示。链路表记录与当前路由器直接相连的链路号和上一跳路由器IP地址，链路的编号按照数据到达频率的高低来编号，频率越高编号越小，链路编码也越短。

与路由器相连的链路数≤4［12］，链路号编码最大为4，编码长度为3 bit;数据包传输过程中经过的跳数≤16［12］，故标记一条攻击路径的编码长度≤64 bit(1 bit+3 bit*16+5 bit=54 bit，取 64 bit，字节对齐)。

其中，分界符1 bit，用来区分两个链路号;距离d与链路号一一对应，表示当前链路与攻击者的距离。如图6所示。

图6 标记格式

2.3 标记区域

IPv4下选择“选项”字段作为标记区域;IPv6下选择扩展首部“hop－by－hop”字段作为标记字段;将链路号依次标记到选项里，同时修改距离值，每经过一个路由器距离值增加1。

2.4 隧道技术

IPv4协议和IPv6协议数据报格式差别较大，针对IPv4和IPv6协议并存的网络，采用隧道技术(封装)解决不同网络协议标记区域不同的问题。IPv4网络传输到IPv6，使用IPv6首部封装IPv4数据报，同时检测选项字段是否有标记信息，如果有的话增加一个复制操作，把标记信息标记到扩展首部hop－by－hop，没有标记信息的话不作任何操作;反之，则用IPv4首部封装IPv6数据报，将标记信息标记到选项字段或不做任何操作。以IPv4到IPv6网络标记信息的复制为例，复制操作代码如下:

改进的算法适用于IPv4和IPv6环境，提高了算法的兼容性。

2.5 路径重构

当受害者检测到攻击时，提取标记包中的标记信息，结合路由器中的链路表来重构攻击路径。具体步骤如下:

1)distance=d时，开始进行攻击路径反向回溯，与链路号相关的路由器即受害者最近的路由器为Rd;

2)distance=d－1时，结合标记信息中的链路号、距离和链路表找出对应的路由器Rd－1;

……

d)distance=1时，找出最后一个路由器R1，即离攻击者最近的路由器。按序排列好的路径{Rd→Rd－1→……→R1}就是攻击路径。

3 实验结果分析

3.1 算法分析

本文改进的算法具有标记信息量大、兼容性高和路径重构所需数据包数量少的优点。

与文献［2－3］相比，路径重构时所需标记包的数量大大减少，只需要一个即可完成路径的重构;与文献［7－8］相比，选择的标记区域空间足够满足需求，无须转存到路由器的缓存中，降低路由器的处理开销，并且改进算法兼容性高，适用于IPv4和IPv6网络环境。

3.2 实验结果分析

包标记算法的性能评价指标主要是从标记算法的复杂度和重构攻击路径所需标记包的数量来衡量。本文改进的算法，在标记时采用直接赋值的方式，计算复杂度为O(1);路径重构只需要一个标记包。

实验在Linux系统+NS2仿真软件下进行，跳数取值范围为［1，30］，对PPM算法和ADPPM算法路径重构所需数据包进行对比分析。实验结果如图7所示。

4 总结

算法分析和实验结果表明，本文提出的改进算法在算法复杂度和路径重构效率上有了较大改进，兼容性也大大提高。不足的是要求每一个路由器保持一个链路表，增加了路由器的开销。此外，虽然标记的信息不足8 byte，但还是增加数据包的长度，有可能造成分片，增加算法复杂度。算法存在的问题，是今后研究的重点。

图7 路径重构所需标记包数量与跳数的关系

［1］H Burch，B Cheswick，Tracing anonymous packets to their approximate source［C］//Proceeding of the 2000 USENIX LISA Conference.New Orleans，USA，December，2000:319 －327.

［2］Savage S，Wetherall D，Karlin A，et a1.Practical network support for IP traceback［C］//Proceedings of the 2000 ACM SIGCOMM Conference.New York，USA:ACM Press，2000:295－306.

［3］Peng T，Lecki C，Ramamohanroa K.Adjusted probabilistic packet marking for IP traceback［C］//Proceedings of Networking 2002 Pisa，Italy:IFIP Press，2002:697 －708.

［4］Song Dawn，Perrig A.Advanced and authenticated marking schemes for IP traceback［C］//Proc of IEEE INFOCOM 2001.Alaska，USA:IEEE Press，2001:878 －886.

［5］Postel J.IP OPTION NUMBERS［EB/OL］.［2015－01－08］http://www.iana.org/assignments/ip－parameters/ip－parameters.xhxhtml，2013－05－28.

［6］蒋华，李明珍，王鑫.一种基于概率包标记的PPM算法改进方案［J］.山东大学学报(理学版)，2011，46(9):85－88.

［7］Choi K H，Dai H K.A marking scheme using Huffman codes for IP traceback［C］//Proc of the 7th International Symposium on Parallel Architectures，Algorithm and Networks Hong kong，China，2004:421 －428.

［8］胡清钟，张斌.IPv6下基于Huffman编码的路径回溯算法研究［J］.计算机工程与科学，2013，35(5):51－55.

［9］李明珍，蒋华，王鑫.基于扩展首部hop－by－hop的IPv6包标记算法研究［J］.计算机应用研究，2012，29(6):2313－2316.

［10］Postel J.Internet Protocol(IPv4)［EB/OL］.［2015－01－08］http://datatracker.ietf.org/doc/rfc791/，2013－03－02.

［11］Deering S，Hinden R Internet Protocol(IPv6)［EB/OL］.［2015 －01 －08］http://www.ietf.org/rfc/rfc2460.txt，1998 －12.

［12］Palmer C R，Siganos G，Faloutsos M，et a1.The connectivity and fault tolerance of the Internet topology［C］//Proceeding of the 2001 Workshop on Network Related Data Management，Santa Barbara，2001.