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

1、 基于AS路径识别的包标记算法摘要：本文提出了一种新的基于自治系统路径识别的包标记算法。它通过边界网关协议路由器在其转发的数据包中标记当前as的编号，受害者不仅可根据数据包中的标记信息重构出攻击包所经过的as路径，追踪到攻击源所在的as，还可以根据标记信息将拥有那些攻击路径的数据包过滤掉，从而能有效地缓解攻击流量对受害者的影响。该算法解决了传统标记算法中计算量大、误报率高等缺点，同时无须攻击路径中每个路由器都参与标记，极大地减少了路由器的开销。关键词：自治系统 包标记 网络安全 0 引言 当今网络攻击中ddos攻击是最为普遍、最为有效的攻击手段，它具有易实施、难防范和追踪的特点，一直是inte

2、rnet安全的一个严重威胁。针对这些特点，近年来该领域的研究人员提出了多种追踪攻击源方法，主要方法有：数据包标记、日志记录、连接测试、覆盖网络等。 其中数据包标记中的普通路径识别方法由于标记空间有限，它使用路由器ip地址的2位信息摘要来构建每个包的路径信息，导致相同的路径信息代表不同的路径；而建立在普通路径识别方法基础之上的链路识别方法虽然采用link-id来代替ip地址，但由于每个link-id的编号大小和数据包经过的link-id数目未知，link-id域有时要进行哈希处理，同样会导致相同的路径信息代表不同的路径。 针对上述两种路径识别包标记方法的不足，本文提出了一种新的基于as路径识别的

3、包标记算法。lOCalhOST 1 基于as路径识别的包标记算法 算法基本思想 当数据包到达自治系统的bgp路由器时，它先检查该包是否是来自其它的bgp路由器或其它的as，如果不是的话，路由器标记它的信息作为该包的初始路由器信息，如果是的话，路由器检查该包的目的地址，如果目的地址在当前自治系统中，路由器标记它的信息作为该包的结束路由器信息；如果目的地址在其它的as中，bgp路由器用它所在的自治系统的asn来标记数据包，也就是说，bgp路由器只对离开本as去往其它as的路由器的数据包才使用它所在的自治系统的asn进行标记。 算法编码 该算法的编码方案需要34位用于标记。为了充分利用ip包头中可用

4、的空间，本方案除使用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标识域中的位置。 算

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

6、as2中，它不做任何标记就把数据包转发给路由器c2。 路由器c2发现数据包是来自其它的bgp路由器，然后根据数据包的目的地址找到下一跳路由信息，发现不在当前自治系统as2中，于是递增跳数域的值，并将路由器c2所在自治系统的编号的3位哈希值填写在与跳数域的值相对应的asid域中，最后再将数据包转发给as4中的bgp路由器d，至此路由器c2对数据包的操作完毕。 路由器d发现数据包是来自其它的自治系统，并且目的地址在当前自治系统as4中，于是路由器d在数据包包头结束路由器标识域中写上它的ip地址8位哈希值，作为结束路由信息。至此该数据包标记过程完毕。 受害者根据标记信息对数据包进行过滤。过滤时，我们

7、采用门限过滤的思想，即允许受害者以提高假阳性比例为代价来减少假阴性比例。门限过滤的真正目的是在能够接受大量合法用户数据包的前提下，允许接受少量的攻击包。这个门限是由受害者选择的一个值ti，假设ai为带有标记i的攻击包的数目，ui为带有标记i的用户数据包数目。如果攻击包的数目与总的数据包数目的比例满足 ，受害者就丢弃拥有i标记的所有数据包。例如，门限值t3等于，这表明只要标记为3的攻击流量不超过所有标记为3的流量的25%，就允许受害者接受所有标记为3的数据包。 2 理论分析 假阳性 理论上，在路径长度为p的a个攻击者发起攻击的假阳性数目为： 其中h为as编号哈希的位数，n为路径长度为p的可疑攻击

8、源自治系统数目。当h=4时，路径长度为4的150个攻击者发起攻击，产生的假阳性数目为*n，这数目相当小，几乎可以忽略不计。 重构as路径所需数据包数目 在路径重构过程中，受害者使用as拓扑图和被标记的攻击数据包来重构攻击路径。由于该算法采用的是确定包标记算法，每个数据包中都存储了完整的路径信息，无需进行信息重组，因而只需几个数据包就可以重构出该数据包经过的as路径。 路由器开销 在传统的ip追踪策略中，需要攻击路径中的所有路由器参与标记，而该算法只部署在bgp路由器上，只需数据包经过路径中的bgp路由器参与标记，这就避免了攻击路径中所有路由器参与。据统计，互联网中数据包从源端到目的端所经过的路

9、由器平均数目大约为17个，而数据包经过的自治系统平均数目大约为3. 假设数据包在每个自治系统中经过两个bgp路由器，路由器的负担就可以减少大约60%。 3 结论 由于文中所提出的算法通过重载ip包头偏移域和服务类型来获得更多的标记空间，解决了普通路径识别方法标记空间不足的问题，同时它使用asid来代替基于链路识别的包标记算法中的link-id，不仅能够更有效地抵御ddos攻击，而且结合internet中的as拓扑图还可以追踪到攻击源所在的自治系统。参考文献：1magoni d,pansiot j.“analysis of the autonomous system network topology”,acm computer communication review, ,july 2001.2fayed m,krapivsky p,byers j,eta1. “on the size distribution of autonomous systems”,technical university,jan 2003.3, and “collecting the internet as-level topology”, sigcomm