胡清鐘，張 斌

（桂林電子科技大學(xué)網(wǎng)絡(luò)中心，廣西 桂林541004）

1 引言

Internet的快速發(fā)展和廣泛應(yīng)用給人們帶來(lái)很大的便利，同時(shí)也滋生了一些不安全因素，威脅著網(wǎng)絡(luò)安全。在所有的威脅中，DDoS攻擊最為嚴(yán)重，為有效遏制DDoS攻擊，必須從源頭上防治。

IP回溯（IP traceback）是一種主動(dòng)防御技術(shù)，旨在追蹤DDoS攻擊源，已有的方案有入口過(guò)濾［1］、輸 入 測(cè) 試［2］、路 由 日 志 法［2，3］、ICMP 追 蹤法［4］和包標(biāo)記［5］等，其中，包標(biāo)記以其網(wǎng)絡(luò)開(kāi)銷、路由器開(kāi)銷和管理開(kāi)銷小成為研究的熱點(diǎn)。文獻(xiàn)［5］提出PPM算法，將IP地址分片標(biāo)記在標(biāo)記區(qū)域，但攻擊路徑達(dá)到16跳以上時(shí)，重構(gòu)路徑所需的數(shù)據(jù)包過(guò)多，達(dá)1 600多個(gè)；文獻(xiàn)［6］采用哈希函數(shù)的編碼方式，可以標(biāo)記一個(gè)完整的IP地址，大大減少了路徑重構(gòu)所需數(shù)據(jù)包的數(shù)量，但前提是必須知道網(wǎng)絡(luò)的拓?fù)鋱D；為進(jìn)一步減少路徑重構(gòu)時(shí)所需的數(shù)據(jù)包，文獻(xiàn)［7，8］提出分別適用于IPv4、IPv6網(wǎng)絡(luò)的單包追蹤方案：源路徑隔離引擎（SPIE），通過(guò)路由器存儲(chǔ)轉(zhuǎn)發(fā)的每一個(gè)數(shù)據(jù)包的哈希摘要，實(shí)現(xiàn)一個(gè)數(shù)據(jù)包即可重構(gòu)出攻擊路徑，但該方案的路由器計(jì)算開(kāi)銷、處理開(kāi)銷和存儲(chǔ)開(kāi)銷過(guò)大。就SPIE方案路由器開(kāi)銷過(guò)大的問(wèn)題，文獻(xiàn)［9，10］分別提出一種IPv4下基于Huffman編碼的IP回溯方案，兩種方案亦實(shí)現(xiàn)了單包追蹤攻擊源，且路由器的計(jì)算開(kāi)銷、處理開(kāi)銷和存儲(chǔ)開(kāi)銷降低；不足的是，只給出標(biāo)記方案，沒(méi)有指明具體的標(biāo)記區(qū)域，當(dāng)標(biāo)記區(qū)域空間不足時(shí)，需將標(biāo)記包相關(guān)信息存儲(chǔ)在路由器上，耗費(fèi)一定的路由器存儲(chǔ)空間。

隨著IPv6的推廣使用，IPv6下的包標(biāo)記技術(shù)研究也相繼展開(kāi)，文獻(xiàn)［11］提出選擇 Hop－by－Hop選項(xiàng)作為標(biāo)記區(qū)域，但因由離攻擊者最近的邊界路由器標(biāo)記所有經(jīng)過(guò)的數(shù)據(jù)包，路由器負(fù)擔(dān)過(guò)大；文獻(xiàn)［12］提出采用自適應(yīng)概率對(duì)數(shù)據(jù)包進(jìn)行采樣，將相鄰兩個(gè)路由器的邊地址標(biāo)記到Hop－by－Hop選項(xiàng)，綜合性能較好，不足的是需額外空間存儲(chǔ)標(biāo)記信息，傳輸時(shí)會(huì)占用一定的網(wǎng)絡(luò)帶寬。本文結(jié)合文獻(xiàn)［11，12］中的方案，對(duì)文獻(xiàn)［9，10］中的方案進(jìn)行改進(jìn)，以使其適應(yīng)于IPv6網(wǎng)絡(luò)，該算法明確指出選擇Hop－by－Hop選項(xiàng)作為標(biāo)記區(qū)域，標(biāo)記信息全部存儲(chǔ)在標(biāo)記區(qū)域，不需要因存儲(chǔ)空間不足而將標(biāo)記信息轉(zhuǎn)存在路由器上。

2 相關(guān)背景

2.1 Huffman編碼

Huffman編碼主要用于對(duì)數(shù)據(jù)的無(wú)損壓縮，本質(zhì)上是根據(jù)字符出現(xiàn)的概率來(lái)構(gòu)造Huffman樹(shù)，出現(xiàn)頻率越高越靠近根節(jié)點(diǎn)，其編碼長(zhǎng)度也越短，從而找出最佳編碼（最短編碼）。本文中鏈路發(fā)送數(shù)據(jù)包的頻率與字符出現(xiàn)的概率類似，可根據(jù)數(shù)據(jù)包發(fā)送頻率來(lái)構(gòu)造Huffman樹(shù)，從而得到最短編碼，以減少標(biāo)記信息占用的空間。

2.2 鏈路表

每一個(gè)路由器都維持一個(gè)鏈路表［9］（Link Table），用來(lái)實(shí)現(xiàn)鏈路號(hào)和端口IP地址的準(zhǔn)確映射，以供路徑重構(gòu)時(shí)查詢。該鏈路表有統(tǒng)一的結(jié)構(gòu)，如表1所示。

本文對(duì)文獻(xiàn)［9］中的鏈路表進(jìn)行改進(jìn)，增加一個(gè)鏈路號(hào)屬性，記錄鏈路的Huffman編碼，路徑回溯時(shí)，根據(jù)鏈路號(hào)直接查找出相應(yīng)的路由器，降低查找的時(shí)間復(fù)雜度。保留發(fā)送數(shù)據(jù)包的頻率屬性，用于當(dāng)路由器相鄰節(jié)點(diǎn)發(fā)生變化時(shí)重新計(jì)算Huffman編碼，保持鏈路表的實(shí)時(shí)性。

3 基于Huffman編碼的標(biāo)記算法

本文提出的基于Huffman編碼的改進(jìn)標(biāo)記算法，選擇IPv6報(bào)頭擴(kuò)展首部的Hop－by－Hop選項(xiàng)作為標(biāo)記字段，標(biāo)記的信息全部存儲(chǔ)在該字段，不需要轉(zhuǎn)存在中間節(jié)點(diǎn)；同時(shí)，修改路徑MTU（PMTU）發(fā)現(xiàn)算法，以修正路徑傳輸最大單元，避免由于標(biāo)記帶來(lái)的包分片。標(biāo)記算法標(biāo)記的不是當(dāng)前路由器的信息，而是與接收數(shù)據(jù)包的端口相連的上一跳路由器相關(guān)的鏈路號(hào)，該鏈路號(hào)采用Huffman編碼。每一個(gè)路由器維護(hù)一個(gè)鏈路表，鏈路表記錄了與當(dāng)前路由器相連的所有相鄰節(jié)點(diǎn)，每一條鏈路用一個(gè)采用Huffman編碼的鏈路號(hào)來(lái)表示。

3.1 標(biāo)記區(qū)域的選擇

IPv6報(bào)頭［12］包括基本報(bào)頭和擴(kuò)展首部?jī)刹糠?。IPv6基本報(bào)頭包括版本、通信類別、流標(biāo)簽等八個(gè)字段，如表2所示。與IPv4報(bào)頭相比，IPv6報(bào)頭簡(jiǎn)化了很多，使得在通信過(guò)程中對(duì)數(shù)據(jù)包的處理更快，同時(shí)也給我們的標(biāo)記帶來(lái)了困難，八個(gè)字段已明確定義功能，不能用于標(biāo)記字段。IPv6擴(kuò)展首部封裝可選的網(wǎng)絡(luò)層信息，位于IPv6首部和上層協(xié)議之間，格式如表3所示，已定義的擴(kuò)展首部有 Hop－by－Hop Options、Routing、Fragment、Destination Options、Authentication和Encapsulating Security Payload。這六個(gè)擴(kuò)展首部是可選的，如果多個(gè)擴(kuò)展首部在IP報(bào)頭中出現(xiàn)，則按以上順序排列，每一個(gè)擴(kuò)展首部由Next Header來(lái)標(biāo)識(shí)。特別地，Hop－by－Hop Options緊隨IPv6基本首部，且途中每個(gè)路由器必須對(duì)Hop－by－Hop Options進(jìn)行檢查。根據(jù)IPv6的特點(diǎn)，本文選擇Hop－by－Hop Options作為標(biāo)記區(qū)域，取64bit的大小。

Table 2 Header format of IPv6表2 IPv6報(bào)頭格式

Table 1 Link table表1 鏈路表

Table 3 Extension header format of IPv6表3 IPv6擴(kuò)展首部格式

3.2 標(biāo)記格式

因本文標(biāo)記信息可以全部標(biāo)記在標(biāo)記區(qū)域，而不需要轉(zhuǎn)存在路由器上，故本文標(biāo)記信息的格式在文獻(xiàn)［9，10］的基礎(chǔ)上稍作改動(dòng)，用de（delimiter）字段取代sf作為分界符，ls字段保持不變；同時(shí)，增加一個(gè)distance字段，每標(biāo)記一個(gè)鏈路號(hào)，distance增加1，記錄攻擊者與受害者相隔的跳數(shù)，作為路徑重構(gòu)時(shí)判斷重構(gòu)過(guò)程是否結(jié)束的依據(jù)，具體格式如表4所示。

其中，高位de用0來(lái)代替，填充在有效標(biāo)記信息流之前。每一個(gè)路由器有3.15個(gè)鄰接點(diǎn)［13］（此處取4），相應(yīng)的鏈路有4個(gè)，3bits編碼鏈路號(hào)即可。數(shù)據(jù)包傳輸過(guò)程中經(jīng)過(guò)的跳數(shù)不超過(guò)16跳［14］，distance取5bits；而每個(gè)鏈路號(hào)3bits，鏈路號(hào)之間接連存儲(chǔ)，ls的位數(shù)為：3bits×16＝48bits。標(biāo)記區(qū)域3個(gè)字段的總長(zhǎng)度為：1＋48＋5＝54bits，IPv6規(guī)定按8bytes對(duì)齊，故取64bits（8bytes），多出的11bits分配給ls。

3.3 標(biāo)記信息編碼

數(shù)據(jù)包中標(biāo)記的信息是一個(gè)與上一跳路由器轉(zhuǎn)發(fā)鏈路相關(guān)的鏈路號(hào)，該鏈路是轉(zhuǎn)發(fā)當(dāng)前數(shù)據(jù)包的鏈路，鏈路號(hào)根據(jù)接口轉(zhuǎn)發(fā)數(shù)據(jù)包的頻率構(gòu)造的Huffman樹(shù)而生成的Huffman編碼。采用Huffman編碼，間接提高標(biāo)記信息量。

3.4 PMTU發(fā)現(xiàn)算法修改

為避免數(shù)據(jù)包在傳輸中被分片，網(wǎng)絡(luò)協(xié)議規(guī)定最大傳輸單元 MTU（Maximum Transmission U－nit），本文改進(jìn)的算法修改報(bào)頭格式，增加一個(gè)8bytes的標(biāo)記區(qū)域，導(dǎo)致整個(gè)數(shù)據(jù)包長(zhǎng)度增加8bytes，可能使發(fā)送數(shù)據(jù)包時(shí)數(shù)據(jù)包長(zhǎng)度計(jì)算不準(zhǔn)確而超過(guò)MTU，從而導(dǎo)致包分片，給路由器增加負(fù)擔(dān)。盡管IPv6支持分片，但不建議分片。

為不增加額外的開(kāi)銷，不影響正常的數(shù)據(jù)傳輸，對(duì)PMTU（Path MTU）發(fā)現(xiàn)算法作出修改，以適應(yīng)路徑的MTU。數(shù)據(jù)包增加的總長(zhǎng)度為8byte，對(duì)MTU進(jìn)行重新計(jì)算，代碼如下：

MTU＝max（PMTU，1280）－8bytes；

for every packet p

if p.size＞M

fp［i］＝Fragment（p，M）；

send（fp［i］）；

else

send（p）；

4 路徑重構(gòu)

受害者檢測(cè)到攻擊時(shí)，根據(jù)標(biāo)記包里的標(biāo)記信息進(jìn)行路徑重構(gòu)。本文提出的算法中，一個(gè)標(biāo)記包標(biāo)記路徑上所有的路徑信息，故一個(gè)標(biāo)記包即可重構(gòu)出攻擊路徑。具體的重構(gòu)過(guò)程如下：

（1）從distance＝1開(kāi)始，進(jìn)行反向路徑回溯，ls字段中最后的一個(gè)3位組即受害者上跳鏈路號(hào)，結(jié)合路由器保存的鏈路表找出相應(yīng)的路由器R1，并添加到集合P中（代表攻擊路徑中的各個(gè)路由器的集合）；

（2）distance＝2時(shí)，利用ls字段中倒數(shù)第二個(gè)3位組，對(duì)比鏈路表找出相應(yīng)的路由器R2，并添加到集合P；

（3）如此，直到distance等于標(biāo)記字段distance中的值（用d來(lái)表示），即distance＝d時(shí)攻擊路徑的重構(gòu)結(jié)束，此時(shí)對(duì)應(yīng)的路由器為Rd。得到的集合P ＝ ｛R1，R2，…，Rd｝，包含攻擊路徑上的所有路由器，按序排列就可以得到攻擊路徑：R1→R2→…→Rd。

5 實(shí)驗(yàn)結(jié)果分析

5.1 算法分析

本文改進(jìn)的算法與文獻(xiàn)［5，6］中的算法相比，有絕對(duì)優(yōu)勢(shì)，只需要一個(gè)標(biāo)記包即可重構(gòu)出攻擊路徑，路徑重構(gòu)所需標(biāo)記包大幅降低；與文獻(xiàn)［7，8］中的算法相比，路由器無(wú)需計(jì)算和存儲(chǔ)數(shù)據(jù)包的哈希摘要信息，計(jì)算開(kāi)銷和存儲(chǔ)開(kāi)銷大大減少。

與文獻(xiàn)［9，10］中的算法相比，本文改進(jìn)的算法有三個(gè)方面的優(yōu)點(diǎn)。（1）一個(gè)標(biāo)記包標(biāo)記所有的路徑信息，不需要轉(zhuǎn)存在中間節(jié)點(diǎn)，節(jié)省中間節(jié)點(diǎn)的存儲(chǔ)空間和CPU的處理負(fù)擔(dān)，整個(gè)算法減少轉(zhuǎn)存這一步驟，算法復(fù)雜度降低；（2）PMTU發(fā)現(xiàn)算法的修改保證PMTU數(shù)值的準(zhǔn)確性，標(biāo)記算法沒(méi)給PMTU造成任何偏差，避免了因標(biāo)記信息的增加而造成數(shù)據(jù)包分片；（3）利用標(biāo)記格式中的distance記錄數(shù)據(jù)包經(jīng)過(guò)的跳數(shù)，作為路徑重構(gòu)是否結(jié)束的標(biāo)準(zhǔn)，簡(jiǎn)單易行。

5.2 實(shí)驗(yàn)結(jié)果與分析

本文實(shí)驗(yàn)仿真平臺(tái)是Linux系統(tǒng)下的NS－2軟件，在該環(huán)境下分別實(shí)現(xiàn)了IPv4下PPM算法、ADPPM算法和IPv6下本文改進(jìn)的算法（d＝1，2，…，30）。圖1顯示了三種算法在重構(gòu)路徑時(shí)所需標(biāo)記包的數(shù)量，說(shuō)明本文改進(jìn)的算法有明顯的優(yōu)勢(shì)，所需標(biāo)記包大大減少。

Figure 1 Required marking package圖1 所需標(biāo)記包比較

Huffman平均編碼長(zhǎng)度與節(jié)點(diǎn)度的平均值成比例，表5顯示了編碼長(zhǎng)度隨節(jié)點(diǎn)度從2增加到6的變化情況。圖2顯示了Huffman平均編碼長(zhǎng)度和節(jié)點(diǎn)度的平均值與鏈路發(fā)送數(shù)據(jù)包頻率（相同與不同）之間的關(guān)系?？傮w來(lái)說(shuō)，Huffman編碼長(zhǎng)度≤3bits。

Table 5 Huffman code average length with different node degree表5 節(jié)點(diǎn)度平均值為2，3，4，5，6的Huffman平均編碼長(zhǎng)度

Figure 2 Relationship between code length and node degree change圖2 編碼長(zhǎng)度與節(jié)點(diǎn)度的變化關(guān)系

6 結(jié)束語(yǔ)

本文提出的算法利用一個(gè)標(biāo)記包重構(gòu)出一條攻擊路徑，降低了路徑重構(gòu)所需的標(biāo)記包的數(shù)量，算法簡(jiǎn)單，易實(shí)現(xiàn)。不足的是，路由器要對(duì)所有的數(shù)據(jù)包進(jìn)行標(biāo)記，路由器的處理負(fù)擔(dān)過(guò)重；該算法只能應(yīng)用于IPv6網(wǎng)絡(luò)，不能適用于整個(gè)網(wǎng)絡(luò)環(huán)境。以后研究的重點(diǎn)是，如何對(duì)數(shù)據(jù)包進(jìn)行概率標(biāo)記以降低路由器標(biāo)記負(fù)擔(dān)，以及如何使基于Huffman編碼的包標(biāo)記算法適用于現(xiàn)有的整個(gè)網(wǎng)絡(luò)系統(tǒng)（包括IPv4和IPv6網(wǎng)絡(luò)）。

［1］ Fergusonand P，Senie D.Network ingress filtering：Defeating denial－of－service attacks which employ IP source address spoofing［S］.RFC 2827，2000.

［2］ Stone R.CenterTrack：An IP overlay network for tracking DDoS floods［C］∥Proc of 2000USENIX Security Symposium，2000：199－212.

［3］ Sager G.Security fun with OCxmon and cflowd［C］∥Proc of the Internet 2Working Group，1998：1.

［4］ Bellovin S M.ICMP traceback messages［EB／OL］.［2000－11－26］.http：／／www.research.att.com／～smb／papers／draftbellovin－itrace－00.txt.

［5］ Savage S，Wetherall D，Karlin A，et al.Practical network support for IP traceback［C］∥Proc of 2000ACM SIGCOMM Conference，2000：295－306.

［6］ Song D，Perrig A.Advanced and authenticated marking schemes for IP traceback［C］∥Proc of IEEE INFOCOM’01，2001：878－886.

［7］ Snoeren A C，et al.Single－packet IP traceback［J］.IEEE Transactions on Networking，2002，10（6）：721－734.

［8］ Strayer T W，Jones C E，Tchakountio F，et al.SPIE－IPv6：Single IPv6packet traceback［C］∥Proc of the 29th Annual IEEE International Conference on Local Computer Net－works，2004：118－125.

［9］ Choi K H，Dai H K.A marking scheme using Huffman codes for IP traceback［C］∥Proc of the 7th International Symposium on Parallel Architectures，Algorithm and Networks，2004：421－428.

［10］ Luo Li－li，Xie Dong－qing，Zhan Yong－jun，et al.The new IP traceback scheme based on Huffman codes［J］.Research on Application of Computer，2007，24（10）：125－127.（in Chinese）

［11］ Obaid Choong S，Seon Hong C.On IPv6traceback［C］∥Proc of ICACT’06，2006：2139－2143.

［12］ Yang Jun，Wang Zhen－xing，Guo Hao－ran.IPv6attack source traceback scheme based on extension header probabilistic marking［J］.Research on Application of Computer，2010，27（6）：2335－2337.（in Chinese）

［13］ Deering S，Hinden R.Internet protocol，Version 6（IPv6）specification［S］.RFC 2460，1998.

［14］ Palmer C R，Siganos G，F(xiàn)aloutsos M，et al.The connectivity and fault－tolerance of the Internet topology［C］∥Proc of 2001Workshop on Network－Related Data Management，2001：1.

［15］ Theilmann W，Rothermel K.Dynamic distance maps of the Internet［C］∥Proc of the 19th Annual Conference of IEEE Communications and Computer Societies，2000：275－285.

附中文參考文獻(xiàn)：

［10］ 羅莉莉，謝冬青，占勇軍，等.新的基于Huffman編碼的追蹤方案［J］.計(jì)算機(jī)應(yīng)用研究，2007，24（10）：125－127.

［12］ 楊俊，王振興，郭浩然.基于擴(kuò)展頭隨機(jī)標(biāo)記的IPv6攻擊源追蹤方案［J］.計(jì)算機(jī)應(yīng)用研究，2010，27（6）：2335－2337.