基于AS路径识别的包标记算法

摘要：本文提出了一种新的基于自治系统（as）路径识别的包标记算法。它通过边界网关协议（bgp）路由器在其转发的数据包中标记当前as的编号，受害者不仅可根据数据包中的标记信息重构出攻击包所经过的as路径，追踪到攻击源所在的as，还可以根据标记信息将拥有那些攻击路径的数据包过滤掉，从而能有效地缓解攻击流量对受害者的影响。该算法解决了传统标记算法中计算量大、误报率高等缺点，同时无须攻击路径中每个路由器都参与标记，极大地减少了路由器的开销。

关键词：自治系统 包标记 网络安全

0 引言

当今网络攻击中ddos攻击是最为普遍、最为有效的攻击手段，它具有易实施、难防范和追踪的特点，一直是internet安全的一个严重威胁。针对这些特点，近年来该领域的研究人员提出了多种追踪攻击源方法，主要方法有：数据包标记、日志记录、连接测试、覆盖网络等。

其中数据包标记中的普通路径识别方法（path identification，简称pi）由于标记空间有限，它使用路由器ip地址的2位信息摘要来构建每个包的路径信息，导致相同的路径信息代表不同的路径（即误报率很高）；而建立在普通路径识别方法基础之上的链路识别方法虽然采用link-id来代替ip地址，但由于每个link-id的编号大小和数据包经过的link-id数目未知，link-id域有时要进行哈希处理，同样会导致相同的路径信息代表不同的路径。

针对上述两种路径识别包标记方法的不足，本文提出了一种新的基于as路径识别的包标记算法。

1 基于as路径识别的包标记算法

1.1 算法基本思想 当数据包到达自治系统的bgp路由器时，它先检查该包是否是来自其它的bgp路由器或其它的as，如果不是的话，路由器标记它的信息作为该包的初始路由器信息，如果是的话，路由器检查该包的目的地址，如果目的地址在当前自治系统中，路由器标记它的信息作为该包的结束路由器信息；如果目的地址在其它的as中，bgp路由器用它所在的自治系统的asn来标记数据包，也就是说，bgp路由器只对离开本as去往其它as的路由器的数据包才使用它所在的自治系统的asn进行标记。

1.2 算法编码 该算法的编码方案需要34位用于标记。为了充分利用ip包头中可用的空间，本方案除使用ip包头16位id域之外，还通过重载偏移域和服务类型字段来获得更多的标记空间。初始路由器标识和结束路由器标识共16位刚好放在数据包头id域中。其中，as标识域又可细分成5个部分，每个部分存放16位as编号的3位散列值，它的前4个部分放在偏移域中，最后一部分放在服务类型字段的3至5位，跳数域存放在服务类型字段的后3位，与as标识域的最后一部分紧邻。

由于受害者所在自治系统的bgp路由器不参与as标识域的标记，因此该算法至多有5个bgp路由器参与as标识域的标记。跳数域的值随着每次bgp路由器标记as标识而逐步加1，它作为as标识域的索引来确定3位标记在as标识域中的位置。

1.3 算法实现 举例说明：as1中的攻击者想对as4中的受害者发起dos攻击。当数据包到达as1中的bgp路由器a时，路由器a检测出该数据包是来自当前自治系统，但没被初始化，于是路由器a在数据包包头初始路由器标识域中写上它的ip地址8位哈希值，作为初始路由信息，同时将跳数域的值置0。然后根据数据包的目的地址找到下一跳路由信息（路由器b），发现不在当前自治系统中，于是递增跳数域的值（递增后的值为1），并将路由器a所在自治系统的编号的3位哈希值填写在与跳数域的值相对应的asid域中，最后再将数据包转发给as2中的bgp路由器b，至此路由器a对数据包的操作完毕。

路由器b发现数据包是来自其它的自治系统，并且下一跳路由信息也在当前自治系统as2中，它不做任何标记就把数据包转发给路由器c2。

路由器c2发现数据包是来自其它的bgp路由器，然后根据数据包的目的地址找到下一跳路由信息（路由器d），发现不在当前自治系统as2中，于是递增跳数域的值（递增后的值为2），并将路由器c2所在自治系统的编号的3位哈希值填写在与跳数域的值相对应的asid域中，最后再将数据包转发给as4中的bgp路由器d，至此路由器c2对数据包的操作完毕。

路由器d发现数据包是来自其它的自治系统，并且目的地址在当前自治系统as4中，于是路由器d在数据包包头结束路由器标识域中写上它的ip地址8位哈希值，作为结束路由信息。至此该数据包标记过程完毕。

受害者根据标记信息对数据包进行过滤。过滤时，我们采用门限过滤的思想，即允许受害者以提高假阳性比例为代价来减少假阴性比例。门限过滤的真正目的是在能够接受大量合法用户数据包的前提下，允许接受少量的攻击包。这个门限是由受害者选择的一个值ti（0≤i<231），假设ai为带有标记i的攻击包的数目，ui为带有标记i的用户数据包数目。如果攻击包的数目与总的数据包数目的比例满足 ，受害者就丢弃拥有i标记的所有数据包。例如，门限值t3等于0.25，这表明只要标记为3的攻击流量不超过所有标记为3的流量的25%，就允许受害者接受所有标记为3的数据包。

2 理论分析

2.1 假阳性 理论上，在路径长度为p的a个攻击者发起攻击的假阳性数目为：

其中h为as编号哈希的位数，n为路径长度为p的可疑攻击源自治系统数目。当h=4时，路径长度为4的150个攻击者发起攻击，产生的假阳性数目为0.00228622*n，这数目相当小，几乎可以忽略不计。

2.2 重构as路径所需数据包数目 在路径重构过程中，受害者使用as拓扑图和被标记的攻击数据包来重构攻击路径。由于该算法采用的是确定包标记算法，每个数据包中都存储了完整的路径信息，无需进行信息重组，因而只需几个数据包就可以重构出该数据包经过的as路径。

2.3 路由器开销 在传统的ip追踪策略中，需要攻击路径中的所有路由器参与标记，而该算法只部署在bgp路由器上，只需数据包经过路径中的bgp路由器参与标记，这就避免了攻击路径中所有路由器参与。据统计，互联网中数据包从源端到目的端所经过的路由器平均数目大约为17个，而数据包经过的自治系统平均数目大约为3. 假设数据包在每个自治系统中经过两个bgp路由器，路由器的负担就可以减少大约60%。

3 结论

由于文中所提出的算法通过重载ip包头偏移域和服务类型来获得更多的标记空间，解决了普通路径识别方法标记空间不足的问题，同时它使用asid来代替基于链路识别的包标记算法中的link-id，不仅能够更有效地抵御ddos攻击，而且结合internet中的as拓扑图还可以追踪到攻击源所在的自治系统。

参考文献：

[1]magoni d,pansiot j.“analysis of the autonomous system network topology”,acm computer communication review,v.31 n.3,july 2001.

[2]fayed m,krapivsky p,byers j,eta1. “on the size distribution of autonomous systems”,technical report.boston university,jan' 2003.

[3]b.zhang,r.liu,d.massey and l.zhang.“collecting the internet as-level topology”, sigcomm computer communications review, 35(1):53 61,2005.

[4]jae chung and mark claypool.“ns by example”,wpi worcester polytechnic institute computer science, 2002.