基于AS路徑識別包標記算法范文

本站小編為你精心準備了基于AS路徑識別包標記算法參考范文，愿這些范文能點燃您思維的火花，激發您的寫作靈感。歡迎深入閱讀并收藏。

摘要：本文提出了一種新的基于自治系統（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