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

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

张金伟张国锋

张金伟1张国锋2（1.安徽理工大学计算机科学与工程学院；2.淮南矿业集团瓦斯利用分公司）

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

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

0引言

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

其中数据包标记中的普通路径识别方法（PathIdentification，简称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]MagoniD,PansiotJ.“Analysisoftheautonomoussystemnetworktopology”,ACMComputerCommunicationReview,v.31n.3,July2001.

[2]FayedM,KrapivskyP,ByersJ,eta1.“Onthesizedistributionofautonomoussystems”,TechnicalReport.BostonUniversity,Jan'2003.

[3]B.Zhang,R.Liu,D.MasseyandL.Zhang.“CollectingtheinternetAS-leveltopology”,SIGCOMMComputerCommunicationsReview,35(1):5361,2005.

[4]JaeChungandMarkClaypool.“NSbyExample”,WPIWORCESTERPOLYTECHNICINSTITUTEComputerScience,2002.