基于AS路徑識(shí)別包標(biāo)記算法范文

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

摘要：本文提出了一種新的基于自治系統(tǒng)（AS）路徑識(shí)別的包標(biāo)記算法。它通過邊界網(wǎng)關(guān)協(xié)議（BGP）路由器在其轉(zhuǎn)發(fā)的數(shù)據(jù)包中標(biāo)記當(dāng)前AS的編號(hào)，受害者不僅可根據(jù)數(shù)據(jù)包中的標(biāo)記信息重構(gòu)出攻擊包所經(jīng)過的AS路徑，追蹤到攻擊源所在的AS，還可以根據(jù)標(biāo)記信息將擁有那些攻擊路徑的數(shù)據(jù)包過濾掉，從而能有效地緩解攻擊流量對(duì)受害者的影響。該算法解決了傳統(tǒng)標(biāo)記算法中計(jì)算量大、誤報(bào)率高等缺點(diǎn)，同時(shí)無(wú)須攻擊路徑中每個(gè)路由器都參與標(biāo)記，極大地減少了路由器的開銷。

關(guān)鍵詞：自治系統(tǒng)包標(biāo)記網(wǎng)絡(luò)安全

0引言

當(dāng)今網(wǎng)絡(luò)攻擊中DDoS攻擊是最為普遍、最為有效的攻擊手段，它具有易實(shí)施、難防范和追蹤的特點(diǎn)，一直是Internet安全的一個(gè)嚴(yán)重威脅。針對(duì)這些特點(diǎn)，近年來(lái)該領(lǐng)域的研究人員提出了多種追蹤攻擊源方法，主要方法有：數(shù)據(jù)包標(biāo)記、日志記錄、連接測(cè)試、覆蓋網(wǎng)絡(luò)等。

其中數(shù)據(jù)包標(biāo)記中的普通路徑識(shí)別方法（PathIdentification，簡(jiǎn)稱PI）由于標(biāo)記空間有限，它使用路由器IP地址的2位信息摘要來(lái)構(gòu)建每個(gè)包的路徑信息，導(dǎo)致相同的路徑信息代表不同的路徑（即誤報(bào)率很高）；而建立在普通路徑識(shí)別方法基礎(chǔ)之上的鏈路識(shí)別方法雖然采用Link-ID來(lái)代替IP地址，但由于每個(gè)Link-ID的編號(hào)大小和數(shù)據(jù)包經(jīng)過的Link-ID數(shù)目未知，Link-ID域有時(shí)要進(jìn)行哈希處理，同樣會(huì)導(dǎo)致相同的路徑信息代表不同的路徑。

針對(duì)上述兩種路徑識(shí)別包標(biāo)記方法的不足，本文提出了一種新的基于AS路徑識(shí)別的包標(biāo)記算法。

1基于AS路徑識(shí)別的包標(biāo)記算法

1.1算法基本思想當(dāng)數(shù)據(jù)包到達(dá)自治系統(tǒng)的BGP路由器時(shí)，它先檢查該包是否是來(lái)自其它的BGP路由器或其它的AS，如果不是的話，路由器標(biāo)記它的信息作為該包的初始路由器信息，如果是的話，路由器檢查該包的目的地址，如果目的地址在當(dāng)前自治系統(tǒng)中，路由器標(biāo)記它的信息作為該包的結(jié)束路由器信息；如果目的地址在其它的AS中，BGP路由器用它所在的自治系統(tǒng)的ASN來(lái)標(biāo)記數(shù)據(jù)包，也就是說(shuō)，BGP路由器只對(duì)離開本AS去往其它AS的路由器的數(shù)據(jù)包才使用它所在的自治系統(tǒng)的ASN進(jìn)行標(biāo)記。

1.2算法編碼該算法的編碼方案需要34位用于標(biāo)記。為了充分利用IP包頭中可用的空間，本方案除使用IP包頭16位ID域之外，還通過重載偏移域和服務(wù)類型字段來(lái)獲得更多的標(biāo)記空間。初始路由器標(biāo)識(shí)和結(jié)束路由器標(biāo)識(shí)共16位剛好放在數(shù)據(jù)包頭ID域中。其中，AS標(biāo)識(shí)域又可細(xì)分成5個(gè)部分，每個(gè)部分存放16位AS編號(hào)的3位散列值，它的前4個(gè)部分放在偏移域中，最后一部分放在服務(wù)類型字段的3至5位，跳數(shù)域存放在服務(wù)類型字段的后3位，與AS標(biāo)識(shí)域的最后一部分緊鄰。

由于受害者所在自治系統(tǒng)的BGP路由器不參與AS標(biāo)識(shí)域的標(biāo)記，因此該算法至多有5個(gè)BGP路由器參與AS標(biāo)識(shí)域的標(biāo)記。跳數(shù)域的值隨著每次BGP路由器標(biāo)記AS標(biāo)識(shí)而逐步加1，它作為AS標(biāo)識(shí)域的索引來(lái)確定3位標(biāo)記在AS標(biāo)識(shí)域中的位置。

1.3算法實(shí)現(xiàn)舉例說(shuō)明：AS1中的攻擊者想對(duì)AS4中的受害者發(fā)起DoS攻擊。當(dāng)數(shù)據(jù)包到達(dá)AS1中的BGP路由器A時(shí)，路由器A檢測(cè)出該數(shù)據(jù)包是來(lái)自當(dāng)前自治系統(tǒng)，但沒被初始化，于是路由器A在數(shù)據(jù)包包頭初始路由器標(biāo)識(shí)域中寫上它的IP地址8位哈希值，作為初始路由信息，同時(shí)將跳數(shù)域的值置0。然后根據(jù)數(shù)據(jù)包的目的地址找到下一跳路由信息（路由器B），發(fā)現(xiàn)不在當(dāng)前自治系統(tǒng)中，于是遞增跳數(shù)域的值（遞增后的值為1），并將路由器A所在自治系統(tǒng)的編號(hào)的3位哈希值填寫在與跳數(shù)域的值相對(duì)應(yīng)的ASID域中，最后再將數(shù)據(jù)包轉(zhuǎn)發(fā)給AS2中的BGP路由器B，至此路由器A對(duì)數(shù)據(jù)包的操作完畢。

路由器B發(fā)現(xiàn)數(shù)據(jù)包是來(lái)自其它的自治系統(tǒng)，并且下一跳路由信息也在當(dāng)前自治系統(tǒng)AS2中，它不做任何標(biāo)記就把數(shù)據(jù)包轉(zhuǎn)發(fā)給路由器C2。

路由器C2發(fā)現(xiàn)數(shù)據(jù)包是來(lái)自其它的BGP路由器，然后根據(jù)數(shù)據(jù)包的目的地址找到下一跳路由信息（路由器D），發(fā)現(xiàn)不在當(dāng)前自治系統(tǒng)AS2中，于是遞增跳數(shù)域的值（遞增后的值為2），并將路由器C2所在自治系統(tǒng)的編號(hào)的3位哈希值填寫在與跳數(shù)域的值相對(duì)應(yīng)的ASID域中，最后再將數(shù)據(jù)包轉(zhuǎn)發(fā)給AS4中的BGP路由器D，至此路由器C2對(duì)數(shù)據(jù)包的操作完畢。

路由器D發(fā)現(xiàn)數(shù)據(jù)包是來(lái)自其它的自治系統(tǒng)，并且目的地址在當(dāng)前自治系統(tǒng)AS4中，于是路由器D在數(shù)據(jù)包包頭結(jié)束路由器標(biāo)識(shí)域中寫上它的IP地址8位哈希值，作為結(jié)束路由信息。至此該數(shù)據(jù)包標(biāo)記過程完畢。

受害者根據(jù)標(biāo)記信息對(duì)數(shù)據(jù)包進(jìn)行過濾。過濾時(shí)，我們采用門限過濾的思想，即允許受害者以提高假陽(yáng)性比例為代價(jià)來(lái)減少假陰性比例。門限過濾的真正目的是在能夠接受大量合法用戶數(shù)據(jù)包的前提下，允許接受少量的攻擊包。這個(gè)門限是由受害者選擇的一個(gè)值ti（0≤i<231），假設(shè)ai為帶有標(biāo)記i的攻擊包的數(shù)目，ui為帶有標(biāo)記i的用戶數(shù)據(jù)包數(shù)目。如果攻擊包的數(shù)目與總的數(shù)據(jù)包數(shù)目的比例滿足，受害者就丟棄擁有i標(biāo)記的所有數(shù)據(jù)包。例如，門限值t3等于0.25，這表明只要標(biāo)記為3的攻擊流量不超過所有標(biāo)記為3的流量的25%，就允許受害者接受所有標(biāo)記為3的數(shù)據(jù)包。

2理論分析

2.1假陽(yáng)性理論上，在路徑長(zhǎng)度為P的A個(gè)攻擊者發(fā)起攻擊的假陽(yáng)性數(shù)目為：

其中h為AS編號(hào)哈希的位數(shù)，N為路徑長(zhǎng)度為P的可疑攻擊源自治系統(tǒng)數(shù)目。當(dāng)h=4時(shí)，路徑長(zhǎng)度為4的150個(gè)攻擊者發(fā)起攻擊，產(chǎn)生的假陽(yáng)性數(shù)目為0.00228622*N，這數(shù)目相當(dāng)小，幾乎可以忽略不計(jì)。

2.2重構(gòu)AS路徑所需數(shù)據(jù)包數(shù)目在路徑重構(gòu)過程中，受害者使用AS拓?fù)鋱D和被標(biāo)記的攻擊數(shù)據(jù)包來(lái)重構(gòu)攻擊路徑。由于該算法采用的是確定包標(biāo)記算法，每個(gè)數(shù)據(jù)包中都存儲(chǔ)了完整的路徑信息，無(wú)需進(jìn)行信息重組，因而只需幾個(gè)數(shù)據(jù)包就可以重構(gòu)出該數(shù)據(jù)包經(jīng)過的AS路徑。

2.3路由器開銷在傳統(tǒng)的IP追蹤策略中，需要攻擊路徑中的所有路由器參與標(biāo)記，而該算法只部署在BGP路由器上，只需數(shù)據(jù)包經(jīng)過路徑中的BGP路由器參與標(biāo)記，這就避免了攻擊路徑中所有路由器參與。據(jù)統(tǒng)計(jì)，互聯(lián)網(wǎng)中數(shù)據(jù)包從源端到目的端所經(jīng)過的路由器平均數(shù)目大約為17個(gè)，而數(shù)據(jù)包經(jīng)過的自治系統(tǒng)平均數(shù)目大約為3.假設(shè)數(shù)據(jù)包在每個(gè)自治系統(tǒng)中經(jīng)過兩個(gè)BGP路由器，路由器的負(fù)擔(dān)就可以減少大約60%。

3結(jié)論

由于文中所提出的算法通過重載IP包頭偏移域和服務(wù)類型來(lái)獲得更多的標(biāo)記空間，解決了普通路徑識(shí)別方法標(biāo)記空間不足的問題，同時(shí)它使用ASID來(lái)代替基于鏈路識(shí)別的包標(biāo)記算法中的Link-ID，不僅能夠更有效地抵御DDoS攻擊，而且結(jié)合Internet中的AS拓?fù)鋱D還可以追蹤到攻擊源所在的自治系統(tǒng)。

參考文獻(xiàn)：

[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