基于多维伪随机序列的高级包标记策略算法

摘 要：高级包标记策略（AMS）是对分布式拒绝服务（DDoS）攻击进行IP追踪的有效算法，但是，由于使用哈希函数实现边地址的压缩，AMS算法存在复杂度高、保密性差、误报率高等缺陷。为了提高追踪效率，设计了一种基于多维伪随机序列的AMS算法： 一方面，在路由器上，以全硬件实现的边采样矩阵代替原有的哈希函数，完成IP地址的压缩编码； 另一方面，在受害者端，结合边地址压缩码和边的权重计算过程，实现攻击路径图的输出。仿真实验中，基于多维伪随机序列的AMS算法与原始算法性能基本一致，但能有效减少误判的发生和快速判断伪造路径。实验结果表明，所提算法保密性能高，计算速度快，抗攻击能力强。

关键词：

多维伪随机序列；边采样矩阵；高级包标记策略；压缩编码；攻击路径图

中图分类号：TP393.08

文献标志码：A

文章编号：1001-9081（2016）11-3093-05

0 引言

分布式拒绝服务（Distributed Denial of Service，DDoS）攻击[1]是一种分布的、协作的大规模拒绝服务（Denial of Service，DoS）攻击，它主要的攻击目标是大型的站点，比如商业公司、搜索引擎和政府部门的网站等。由于DDoS攻击较容易实施，且难于防范和追踪，已经成为了互联网中最严重的安全威胁之一。在DDoS攻击过程中，犯罪分子为了躲避打击，经常会伪造或通过改变数据包的源IP地址。为了对抗伪造源IP地址这种造成网络不可信的非法行为，IP追踪技术应运而生。

IP追踪技术已经有十多年的研究历史，主流的研究仍然集中在主动式追踪算法上。2000年，Savage等[2]对包标记进行了深入的研究，提出了经典的概率包标记（Probabilistic Packet Marking，PPM）算法。为了检测和防御DDoS攻击，2001年，Song等[3]在Savage的研究基础上，提出了两个改进方案：高级包标记策略（Advanced Marking Scheme，AMS）和带认证的包标记策略。

AMS算法使用哈希函数实现边地址的压缩，但由于哈希碰撞的存在，不同攻击路径上的路由器在路径重构中会被认为存在于同一条攻击路径上，这就导致AMS算法的误报率较高。将边地址压缩和数学编码思想相结合，可以有效减少重构路径所需的数据包数量，降低漏报率和误报率，提高追踪效率。

本文改进了原有的AMS算法，以边采样矩阵代替哈希函数，采用全新的边地址压缩策略，可以将整个标记算法都集成于路由器的硬件电路中，提高抗攻击能力；在受害者端，统计相同标记的重复数，并转化为边的权重值，最终得出可定性和定量分析的攻击路径图。

4 实验设计与性能分析

4.1 评价指标的对比

为了验证基于多维伪随机序列的AMS算法性能，本文以学术界广泛使用的NS2为网络模拟的实验工具。首先，为了便于计算各算法的收敛包数，通过编写OTcl脚本，生成了一条总长度为31的路径，受害者节点标号为0，并分别在节点1、2、…、31处发起攻击，攻击流量为100包/s。受害者处的31个文本文件对应了在不同的距离值下收集到的数据包标记域，文件中的一行记录对应一个数据包的标记域。在各个距离值下：以10行的增量将文件的标记域输入重构算法，如果重构结果正确，则认为成功一次；重复进行1000次实验得到重构成功率Psuc；因为重构算法输入的包数是逐步递增的，可以认为最早满足置信度要求（Psuc≥1-1/c）的数据包数是收敛包数的实验值。实验中的参数设置为：置信度95%，即c=20；标记概率p=0.04；阈值L=4。分别计算了使用经典PPM算法[2]、原始AMS算法[3]和本文算法时收敛包数的理论值和实验值。

由图4可知：无论是从理论值还是从实验值来看，收敛包数最少的均是AMSⅠ，其次是AMSⅡ，经典PPM算法的收敛性能最差。其次，基于多维伪随机序列的AMS算法，在收敛包数上与原始AMS算法一致，保持了较好的性能。

在重构过程中，可能出现误报的情况为：相同距离域的异或值通过哈希检验，被判为节点路由器，事实上并非是攻击路径上对应的路由器。所以，本文根据相同距离域的所有碎片组合对应的异或值，判断是否发生了碰撞，将碰撞次数累加，最终得出误报数。

分析图5可知，AMSⅠ在2000个攻击者时的误报数达到了528个，AMSⅡ随着判决阈值的增大误报数在减少；大致上看来，本文AMS算法和原始AMS算法性能较接近，很多数据点的结果还要优于后者。

4.2 算法输出的攻击图

接着，本文使用文献[14]和文献[15]中的网络拓扑模型，编写OTcl脚本进行DDoS实验仿真。如图6所示，该网络包括：3个攻击节点0、1和2，30个中间路由器和1个受害者节点3，攻击流量为100包/s。

将受害者处收集到的标记信息分别输入对应的攻击路径重构模块，得出攻击路径上的各条边和边的权重，最终输出攻击图。因为在原始AMSⅠ和AMSⅡ中，没有边的权重的计算过程，所以，本文对它们所得攻击图的边赋权值1。

为了模拟路由器被攻陷的情况，分别在原始AMSⅠ和本文AMSⅠ收集到的标记文本中加入了伪造的标记记录：边{4，5}和{5，9}各2个，伪造路径（0 4 5 9 13 19 25 31 3）。

图7显示了由原始AMSⅠ得出的包括4条攻击路径攻击图：攻击路径0（0 4 9 13 19 25 31 3），攻击路径1（1 6 11 13 19 25 31 3），攻击路径2（2 9 13 19 25 31 3），伪造路径（0 4 5 9 13 19 25 31 3）。可见，原始AMSⅠ无法判断伪造的标记信息，会将伪造路径误认为攻击路径输出。

对本文AMSⅠ得出的攻击图（图8）进行定性和定量分析可知：1）各条边的权重对应了这条边被误判的概率，越小则说明误判可能性越小，则这条边的可信度越高；2）判断节点0、1和2为3个末端节点，对应3个攻击点；3）3条攻击路径存在多条重合边，而多个攻击流合并时，权重会减小，如边{9，13}的权重小于边{11，13}的权重；4）边{13，19}、边{19，25}、边{25，31}和边{31，3}的权重大小类似，反映了各个路由器标记数据包的可能性是相互独立的，满足理论分析的前提条件；5）根据式（3）计算攻击路径0的可信度为98.4%，攻击路径1的可信度为98.08%，攻击路径2的可信度为98.77%。6）虚线表示攻击者伪造的边{4，5}和{5，6}，权重均为0.5，计算该条路径的可信度为24.7%，由于可信度较低，判为伪造路径。

图9显示了由原始AMSⅡ得出的包括4条攻击路径的攻击图：攻击路径0，攻击路径1，攻击路径2，误报路径（23 29 31 3）。可见，原始AMSⅡ无法判断哈希碰撞造成的误报，会将误报路径误认为攻击路径输出。

图10显示了由本文AMSⅡ得出的攻击图。对该攻击图进行定性和定量分析可以得出和图8类似的结论，唯一不同的是这里也发生了一次误报：重构过程中将边{30，31}误认为是攻击路径上的边。从对节点31所连接的三条边的可信度分析可知：边{25，31}、边{30，31}和边{31，3}对应的权重分别为0.0013、0.0013和0.0012，三个数值基本一致，并不存在两个攻击流合并导致的边{31，3}权重相应减小的情况，所以，可以判断边{30，31}是误报。

5 结语

基于多维伪随机序列的AMS算法保持了原始算法的优点，收敛包数少，计算代价和误报率低，总结以上实验结果，该算法的高效性体现如下：

1）保密性能高。

经典PPM算法和原始AMS算法存在一个安全隐患：如果攻击者通过病毒、木马注入等方式控制了一个路由器，就可以篡改经过的标记数据包，甚至可以破解路由器中的标记概率分布，迫使受害者即使分析标记信息的重复个数，也无法找出被控制的路由器。针对这个问题，本文AMS算法采用了全新的边地址的压缩编码策略，一个边采样矩阵既是压缩编码的关键，又等同于一种鉴别码。一方面，攻击者无法破解出全硬件实现的边采样矩阵；另一方面，受害者能够根据边采样矩阵对标记包进行鉴别运算。

2）计算速度快。

一般来说，软件实现的算法速度较慢，不能满足数据实时处理的要求，为了达到高速处理的性能要求，采用硬件实现边采样矩阵的构造具有重要的现实意义。另外，随着工艺技术的发展和市场需要，超大规模、高速、低功耗的新型现场可编程门阵列（Field-Programmable Gate Array，FPGA）器件不断推陈出新，可使用FPGA实现边地址的压缩编码。

3）快速判断伪造路径。

当有路由器被攻击者所控制，使得受害者端收集到的数据包中存在伪造的边地址信息时，算法如何对抗这种干扰呢？在以往的算法中，基本上没有任何的抵抗能力，很容易构造出错误的攻击路径。本文AMS算法考虑到了这个问题，统计了标记信息的重复次数，并将其转化为边的权重值，从而计算出每条攻击路径的可信度，有利于快速发现伪造路径。

4）有效降低误判的发生。

边的权重的引入，使本文可以对重构结果进行定性和定量分析，在面对无法避免的误报情况时，通过对比分析连接在同一节点上的不同边的可信度，能有效降低误判的发生。

参考文献：

[1] DOULIGERIS C， MITROKOTSA A. DDoS attacks and defense mechanisms： classification and state-of-the-art[J]. Computer Networks， 2004， 44（5）： 643-666.

[2] SAVAGE S， WETHERALL D， KARLIN A， et al. Practical network support for IP traceback[J]. Journal of Clinical Epidemiology， 2001， 30（4）： 295-306.

[3] SONG D X， PERRIG A. Advanced and authenticated marking schemes for IP traceback[C]// Proceedings of the 20th Annual Joint Conference of the IEEE Computer and Communications Societies. Piscataway， NJ： IEEE， 2001：878-886.

[4] GOODRICH M T. Probabilistic packet marking for large-scale IP traceback[J]. IEEE/ACM Transactions on Networking， 2008， 16（1）： 15-24.

[5] WANG X J， WEI S J. IP traceback based probabilistic packet marking and randomized network coding[C]// Proceedings of the 2nd International Workshop on Computer Science and Engineering. Piscataway， NJ： IEEE， 2009：151-154.

[6] SATTARI P， GJOKA M， MARKOPOULOU A. A network coding approach to IP traceback[C]// Proceedings of the 2010 IEEE International Symposium on Network Coding. Piscataway， NJ： IEEE， 2010：1-6.

[7] 闫巧，宁土文.基于矩阵边采样的IP追踪[J].深圳大学学报（理工版），2012，29（5）：399-404.（YAN Q， NING T W. IP traceback with matrix edge sampling[J]. Journal of Shenzhen University （Science and Engineering）， 2012， 29（5）：399-404.）

[8] DONOHO D L. Compressed sensing[J]. IEEE Transactions on Information Theory， 2006， 52（4）： 1289-1306.

[9] CANDES E J， ROMBERG J， TAO T. Robust uncertainty principles： exact signal reconstruction from highly incomplete frequency information[J]. IEEE Transactions on Information Theory， 2006， 52（2）： 489-509.

[10] GOLD R. Optimal binary sequences for spread spectrum multiplexing[J]. IEEE Transactions on Information Theory， 1967， 13（4）： 619-621.

[11] LI S， GAO F， GE G， et al. Deterministic construction of compressed sensing matrices via algebraic curves[J]. IEEE Transactions on Information Theory， 2012， 58（8）： 5035-5041.

[12] 万哲先.代数和编码[M].3版.北京：高等教育出版社，2007：219-249.（WAN Z X. Algebra and Coding Theory[M]. 3th ed. Beijing： Higher Education Press， 2007： 219-249.）

[13] GOPPA V D. Codes on algebraic curves [J]. Soviet Math Doklady， 1981， 259（6）： 1289-1290.

[14] 蒋玲. IP追踪及攻击源定位技术研究[D].广州：广东工业大学，2011：45-48.（JIANG L. Research on IP traceback technology based on DDoS attack[D]. Guangzhou： Guangdong University of Technology， 2011： 45-48.）

[15] BELLOVIN S， LEECH M， TAYLOR T. ICMP traceback messages[EB/OL].[2013-11-26]. http：///Proceedings/01dec/I-D/draft-ietf-itraee-ol.txt.