动态概率包标记算法分析及改进

孙连军 赵文正 山东信息职业技术学院，山东 潍坊 261041

动态概率包标记算法分析及改进

孙连军 赵文正 山东信息职业技术学院，山东 潍坊 261041

IP追踪技术是防御拒绝服务攻击的一个研究热点。本文对IP追踪中的动态概率包标记算法进行了介绍和分析，在总结其优点的同时也发现其存在不足。针对动态概率包标记算法使得距离攻击者最近的边界路由器的标记负载太大的不足提出了一个可行性改进方案，经对比分析效果明显。

IP追踪；包标记算法；动态概率包标记算法

引言

拒绝服务攻击一直以来就是网络安全领域中非常严峻的问题， IP追踪技术是防御拒绝服务攻击技术研究中的一个热点，又称为IP 回溯（IP traceback）技术，即通过对攻击路径的逆向还原确定攻击者的正确位置。不言而喻，在攻击的发起端或愈靠近发起端的位置实施对攻击行为的制止是最为有效的。所以对IP追踪技术的研究得到了业内人士的广泛关注。IP追踪技术有很多种，如：入口过滤，洪泛淹没，ICMP标记等。目前研究的主要方向之一是基于Savage[1]等提出的一种被称为概率包标记（Probabilistic Packet Marking，PPM）思想的数据包采样标记技术。 Jenshiuh L i u[2]等提出的动态概率包标记算法（Dynamic Probabilistic Packet Marking，DPPM）被认为是目前最优秀的方案之一，本文对其进行了全面的分析，并提出建设性改进意见。

1.动态包标记算法的引入

Savage等人创新性地提出了包标记算法的思想，为IP追踪问题的研究开辟了一个崭新的方向。包标记算法的思想是：在路由器转发数据包的过程中，路由器以一定的概率将其地址信息标记到数据包中，受害者会收到大量来自于攻击者的数据包。当受害者收到这些数据包并从中获得足够的路径信息时，即可重构出攻击性数据包所经过的路径。该方案具有开创性的意义，也具有管理开销小、不需ISP（网络服务提供商）参与、不增加网络流量，同时对单个攻击源的定位非常准确等优点。但是也存在很多缺陷，由于路由器以固定概率标记数据包，距离受害者较远的路由器的标记信息会被后继路由器的标记覆盖，这样受害者要收集到足够信息需要的数据包数会随着攻击路径长度的增大而大量增加，耗用时间更长，同时不确定性因素增加，导致误报率和漏报率提高。

假定一攻击路径：S=（A，R1，R2，……Rd，V），其中A表示攻击者，V表示受害者，攻击路径长度d表示攻击路径上的路由器数。若路由器以固定概率P 标记数据包，攻击规模即攻击者发出的数据包数设为N。那么，我们可以得出以下结论：因为受害者要至少收到一个来自距离攻击者最近的路由器标记的数据包，即：

NP(1-P)(d-1)=1 （1）

可以得出重够攻击路径所需数据包的期望值为：

lnd/P(1-P)(d-1)（2）

俄罗斯专家表示，欧盟《机器人民事法律规则》里专设了“机器人宪章”，规定了机器人设计和研发过程中必须遵守的基本伦理原则，制定了机器人工程师道德行为守则，以及设计师的“许可”制度和用户“许可”制度。这些都是俄罗斯在立法时需要参照的范本。

从公式2中我们可以看出，随着攻击路径长度的增加，重够攻击路径所需的攻击包的数目会承指数级急剧增长。而要降低该值就要减小标记数据包的概率，如此一来将增加不确定性因素（如攻击者的伪造信息等）的影响从而降低重构路径的准确性和时间效率。为了寻求一种更为可靠，效率更高的方法来弥补PPM的不足，Jenshiuh Liu提出了采用动态的标记概率的动态概率包标记算法。

2.动态概率包标记算法的介绍与分析

动态概率包标记算法不再采用固定不变的概率采样数据包进行标记，而是根据攻击包所经过的路由器跳数即距离攻击者的距离来动态确定标记概率的值。并且距离攻击者越近，路由器的标记概率越大。并随着与攻击者距离的增大而逐渐减小。

动态概率包标记算法的理论根据是：假设从攻击者到受害者的距离为d（即攻击者到受害者之间经过d个路由器），从攻击者到受害者之间的路由器依次为R1，R2，……Rd。

设pi为路由器Ri的标记概率

包只在第一个路由器处被标记的概率为p1(1-p2)(1-p3)…(1-pd-1)(1-pd)，

包只在第二个路由器处被标记的概率为 p2(1-p3)(1-p4)…(1-pd-1)(1-pd),

包只在第三个路由器处被标记的概率为p3(1-p4)(1-p5)…(1-pd-1)(1-pd)，

……

包只在第d-2个路由器处被标记的概率为pd-2(1-pd-1)(1-pd)，

包只在第d-1个路由器处被标记的概率为pd-1(1-pd)，

包只在第d个路由器处被标记的概率为pd，

如果每个数据包最终被哪个路由器标记的概率都是相等的（为1/d）则由coupon collector问题[3]可知，重够所需的数据包数最少。那么pd=1/d，并有以上各式可以推导得出：

pd=1/d，pd-1=1/(d-1)，pd-2=1/(d-2),……，p2=1/2，p1=1

由coupon collector 理论可知，当取这样的变概率1/i（i∈[1，d]）时受害端重够攻击路径所需的包的数目最少，所需的数据包平均值为d(1+1/2+…+1/d)，其期望值为d lnd 。这是理论上的最小值。在实际实现时的主要困难就是i值的确定。因为现在普遍的网络路由协议是基于目的地的，当路由器传送数据包时，它会在路由表中查找下一个最靠近目的地的路由器，这样就可以以最短的路径到达目的地。但同时也增加了数据包经过路由器的不确定性，所以i值也要适时确定。

Jenshiuh Liu提出的思想是：利用IP报文头部的T T L域的信息来确定当前的i值。他们统计了目前存在的不同操作系统和协议的T T L的初始值是这样一个集合{32，64，126，255}。所以可以根据当前的TTL值和路径长度不会大于25的结论[4]判断其初始值，从而计算出i值。如当前TTL为49那么其初始值只能为64，那么可以计算出i值为64-49=15。

从以上说明中可知，动态概率包标记算法路径重构所需的数据包数为d lnd。

因为所需包数最少，这样重够时间也最短。另外因为TTL初始值是由操作系统和协议决定的，不会被攻击者篡改，提高了标记信息的准确性。

虽然动态概率包标记算法有诸多优势，但也存在不足。因为路由器标记数据包的概率为1/i（i∈[1，d]），所以在靠近攻击者端，尤其是边界路由器的标记概率为100%。边界路由器要对所有转发的数据包进行标记，这导致路由器的负担过重。如果该处网络流量太大，会导致网络涌塞甚至路由器服务瘫痪。为了弥补D P P M的不足，本文提出以下改进方案。

3.动态包标记算法的改进

为了减小边界路由器的负担，我们提出以下改进措施。

边界路由器上的标记概率定为50%，而在边界路由器的下一条路由器上执行标记算法时，首先判断是否已被标记，从而避免覆盖边界路由器的标记信息。如图1所示，实际上就是对经过边界路由器的数据包进行了分流，当然“分流”指的是对标记负载的分担。这样从标记结果和时间效率上并没有折损，但却使边界路由器的标记负担减少了50%。具体算法如下：

对于当前路由器对经过的数据包

先计算数据包从源端到当前路由器经过的跳数i

若i=1时，路由器标记概率p=1/2

执行标记操作对数据包进行标记

若i=2时， 路由器标记概率p=1/2

判断数据包有否被标记，

若标记过则直接转发；

若没有被标记则安p=1/2执行标记操作

i大于2时，路由器标记概率p=1/i执行标记操作

根据我们分析，改进后的算法使边界路由器的标记负载减小了50%，但是其作为发现攻击的第一个效应点的作用丝毫未减，下面我们在同样的攻击环境下对各算法中路由器的标记负载进行了比较。设攻击路径长度为25，攻击者发出的数据包数为100，000，PPM算法的标记的标记概率为0.35。那么三种方案中各节点路由器的标记负载如图2所示。

4.总结

本文介绍了ip追踪技术研究的主要方向之一：包标记算法，并对一优秀算法——动态概率包标记算法进行了说明分析。动态概率包标记算法大大减少了重够路径所需要的攻击包的数目，提高了ip追踪的时间效率同时也大大提高了追踪的准确性。我们通过分析还发现其存在不足之处，即在距离攻击者最近的边界路由器的标记负载太大。我们给出了一个改进的方案，从三种算法的对比图中可以看出我们的算法的效果是相当明显的。

[1]Stefan Savage, David Wetherall, Anna Karlin and Tom Anderson. Practical Network Support for IP Traceback. Department of Computer Science and Engineering. University of Washington Seattle, WA, USA , 2000

[2] Jenshiuh Liu,Zhi-jian Lee,Yeh_Ching Chung. Dynamic probabilistic packet marking for efficient IP traceback. Department of Information Engineering and Computer Science,Feng-Chia University,Taichung 407,Taiwan,ROC,Departmen of Computer Science,National Tsing Hua University,Hsingchu 300,Taiwan,ROC. 2006.6

[3] W. Theilmann, K. Rothermel, Dynamic distance maps of the Internet, in: Proceedings of the 2000IEEE INFOCOM Conference, March 2000.

[4] Sariel Har-Peled The Occupancy and Coupon Collector problems, November 598shp -Randomized Algorithms. 2005

Analyses And Amelioration To The Dynamic Probabilistic Packet Marking Algorithm

Sun Lianjun Zhao Wenzheng (Shandong College Of Information Technology, Shandong Weifang 261041)

The IP traceback approach is a very effective method to identify DoS attackers. The dynamic probabilistic packet marking algorithm is introduced and analyzed. As its excellent performance knowing we find it some shortage. A improved algorithm is proposed to solve the problem that the routers nearest to the attackers have a heavy load on marking packets. And the improvement is proved to be in effect.

TP393

A

10.3969/j.issn.1001-8972.2011.13.042

孙连军，男，副教授，研究方向：计算机动画设计，计算机通信技术。