新的基于Ｈｕｆｆｍａｎ編碼的追蹤方案

摘要:面對DDoS攻擊，研究人員提出了各種IP追蹤技術(shù)尋找攻擊包的真實源IP地址，但是目前的追蹤方案存在著標記過程中的空間問題#65380;追蹤源是否準確及追蹤所需包的數(shù)量等問題#65377;提出一種新的基于Huffman編碼的追蹤方案，可以節(jié)省大量的存儲空間，提高空間效率，而且當遭遇DoS(拒絕服務(wù)攻擊)和DDoS的攻擊時能迅速作出反應(yīng)，僅僅收到一個攻擊包即可重構(gòu)出攻擊路徑，找到準確的攻擊源， 將攻擊帶來的危害和損失減小到最低程度#65377;

關(guān)鍵詞:分布式拒絕服務(wù)攻擊;攻擊源追蹤;哈夫曼編碼

中圖分類號:TP393.08文獻標志碼:A

文章編號:1001-3695(2007)10-0125-03

0引言

2001年，Savage[1]#65380;Ferguson[2]等人提出了一種ingress filter追蹤方案#65377;該方案對于追蹤到發(fā)動攻擊的真實源地址很方便，其主要局限是它要求路由器有足夠的能力檢查每個包的源地址，并有足夠的能力判別是合法地址還是非法地址#65377;2002年，Baba[3]提出hopbyhop tracing方案#65377;該方案的主要局限是整個工作必須在攻擊進行的過程中完成，且需要ISP之間的協(xié)作，因此可能追蹤尚未完成，而攻擊已經(jīng)結(jié)束#65377;文獻[1]中的Logging方案的優(yōu)點是在攻擊發(fā)生后很長時間仍然可以追蹤，但是大量消耗系統(tǒng)資源，而且有效的數(shù)據(jù)挖掘技術(shù)本身也是個難題#65377;文獻[1，3]也提到ICMP traceback方案，它是在包發(fā)送的過程中，由路由器小概率(如1/20 000)采樣所轉(zhuǎn)發(fā)的包，并生成一個特殊的ICMP追蹤消息，發(fā)往包的目的地址;受害主機根據(jù)收到的大量這類包信息重構(gòu)報文轉(zhuǎn)發(fā)路徑，并追蹤到攻擊主機#65377;該方案的缺點是增加了網(wǎng)絡(luò)流量#65377;

Packet marking算法在眾多的追蹤算法中是一種比較有成效的方法，此算法通過在路由器處標記數(shù)據(jù)包實現(xiàn)在受害者處重構(gòu)攻擊路徑#65377;所有數(shù)據(jù)包標記技術(shù)分為兩個部分，即在路由器處標記數(shù)據(jù)包和在受害者處實現(xiàn)重構(gòu)攻擊路徑#65377;根據(jù)對數(shù)據(jù)包標記的性質(zhì)不同分為概率包標記和確定性包標記#65377;Savage[1]#65380;Song[4]#65380;Park[5]提出在網(wǎng)絡(luò)傳輸?shù)臄?shù)據(jù)包中概率標記經(jīng)過的每一個路由器的信息，路徑信息隨包一起到達目的地，而確定性包標記[1]則對經(jīng)過的每一個數(shù)據(jù)包都進行確定性的標記#65377;

目前提出的各種追蹤方案中，還存在一個很嚴重的問題:若在包中保留所有路徑上的路由器信息，則存在空間問題導致的重新分段及相互影響問題;其次是目的主機的處理負擔太重#65377;本文針對空間不足問題提出一個新的追蹤方案，它與目前的所有追蹤方案相比，可以明顯地節(jié)省空間，也沒有分段問題的產(chǎn)生#65377;當有攻擊發(fā)生時，只需一個數(shù)據(jù)包即可重構(gòu)出攻擊路徑，及時準確地確定攻擊源，將攻擊帶來的危害和損失減小到最低程度#65377;

1Huffman編碼思想

在給出Huffman編碼思想之前，本文先給出路徑和路徑長度的概念#65377;從樹中一個節(jié)點到另一個節(jié)點之間的分支構(gòu)成這兩個節(jié)點之間的路徑，路徑上的分支數(shù)目稱為路徑長度，樹的路徑長度是從樹根到每一個節(jié)點的路徑長度之和#65377;若將上述概念推廣到一般情況，考慮帶權(quán)的節(jié)點，樹的帶權(quán)路徑長度通常記做WPL=nk=lwklk#65377;假設(shè)有n個權(quán)值{w1，w2，…，wn}，構(gòu)造一棵有n個葉子節(jié)點的二叉樹，每個葉子節(jié)點帶權(quán)為wi，則其中帶權(quán)路徑長度WPL最小的二叉樹稱為Huffman樹#65377;構(gòu)造Huffman樹的算法見文獻[6]#65377;如圖1所示，給出了一個Huffman樹的實例#65377;

在這組權(quán)值下，每個字母的期望代碼長度為[(1×120)+(3×121)+(4×32)+(5×24)+(6×9)]/306≈2.57#65377;對于這八個字母，固定長度編碼每個字母需要log 8=3位，而Huffman編碼只需要2.57位#65377;因此對于這組字母，Huffman編碼預(yù)計可以節(jié)省大約12%的空間，如果頻率變化范圍很大的話可以節(jié)省更多的空間#65377;

2新的Huffman編碼追蹤方案

2.1標記過程

Huffman編碼方案與以往的追蹤方案不同的是，當包經(jīng)過某一個路由器時，它不是標記當前路由器的IP地址，而是標記該路由器的上游路由器的信息(即該包經(jīng)過的上一個路由器的信息)#65377;

本文采用32 bit作為標記域，考慮到一般情況下攻擊路徑不會超過32跳，一條攻擊路徑上保存三次ls(link sequence)信息到路由器存儲器足夠了，所以2 bit作為sf(saved flag)#65377;為了確保能存儲最大信息量，要將ls設(shè)置得盡量大，30 bit全部分配給ls，如圖2所示#65377;

本文用bit 1作為每個路由器標記的分隔符，每個有效bit流信息前都加上0，從左往右逐漸添加，當ls空間不夠時，將hash(p)+(sf，ls)保存到路由器的當前存儲器中，sf增加1，ls置為0x10(清零)#65377;

假定路由器R的上游有五個路由器，分別為R0#65380;R1#65380;R2#65380;R3#65380;R4，它們發(fā)送包到R的相對頻率分別為30#65380;40#65380;50#65380;60#65380;200，則 R0#65380;R1#65380;R2#65380;R3#65380;R4構(gòu)成的Huffman樹如圖3所示#65377;

當R4將包轉(zhuǎn)發(fā)給R時，如果ls空間夠用，則標記域中增加的信息為(101);否則保存當前信息hash(p) +(sf，ls)到路由器的當前存儲器，清空ls，然后直接將sf增1，表明標記域已經(jīng)存儲，在空的ls中寫信息101#65377;為了避免轉(zhuǎn)發(fā)包的過程中出現(xiàn)包中數(shù)據(jù)的某一位或者某幾位被修改，本文提出這樣的解決方案:當sf不為00時，路由器保存舊包的hash值;同時也保存新包的hash值，然后將ls置為0x10，保持sf不變#65377;

2.2追蹤過程

追蹤過程從離受害者最近的路由器開始，當受害者收到離它最近的路由器發(fā)送的包時，它通過查看ls中的內(nèi)容，可以確定上游路由器的Huffman編碼，通過查找鏈路表中與之對應(yīng)的信息可以確定路由器的IP，鏈路表如圖4所示#65377;當ls為1(只有分隔符)，sf不為01#65380;10，或者11時，表示當前路由器存儲了hash(p)+(sf，ls)，從存儲器中取出ls，重復上述過程，繼續(xù)向前追蹤知道ls變成1，sf變?yōu)?0#65377;具體的標記和追蹤算法描述見2.3節(jié)#65377;

路由器R的上游路由器數(shù)量R1向R發(fā)包的相對頻率R2向R發(fā)包的相對頻率…R1的IP 地址R2的IP 地址…

2.3算法描述 

2.3.1包標記算法

首先通過鏈路表確定上游路由器的Huffman編碼:

If (sf==1 and packet p(old_ p) transformed into a different packet (new_ p))

Then store MD(new_ p):MD(old_ p)(sf， ls)

ls = 0x10

Count the leading 0s(space_ right) in ls to know how many bits are available in ls;

If (space_ right< length (codeword))

Then store MD (p):(sf， ls)

sf = sf+1;

ls = 0x10;

Append codeword to ls;

2.3.2包追蹤算法

Starting at the closest router (current router) with which the victim is directly connected;

While (1) {

Print current router;

Construct Huffman tree with the link table of current router;

Decode one Huffman codeword from the left of ls by using the tree;

Find the router that the decoded codeword represents;

If (ls==0x10 and sf!=00) 

then retrieve MD(p):MD(pre_p)(sf，ls)or MD(p):(sf，ls)

reset sf，ls with retrieved values

If (ls==0x10 and sf==00)

then break 

set current router with the found router;

sf=sf-1;

}

3實驗結(jié)果及其分析

幾乎所有的路徑長度均小于32跳并且路徑的平均長度大多集中在16跳左右[7]，路由器R的上游路由器的數(shù)量通常介于3和4[8]#65377;因此32 bit作為標記域，考慮相對頻率不等的情況下， 路由器R的上游路由器數(shù)量為3，跳數(shù)為16時，所占ls的平均長度為23.11，如圖5(a)所示#65377;標記域存儲過的概率為0.002，如圖6(a)所示#65377;而相對頻率相等且都為255，其他條件都相同的情況下，所占ls平均長度為24.95，較之23.11要稍大一些，如圖5(b)所示#65377;標記域被存儲的概率為0.001，如圖6(b)所示#65377;從圖6(b)還可以看到，當跳數(shù)為21#65380;路由器R的上游路由器數(shù)量為3時，所占ls的平均長度超過了30 bit，所以標記域必須存儲到路由存儲器中#65377;因此在32跳中，標記域被存儲在路由器的概率為2.34%#65377;

從圖7鏈接數(shù)量與Huffman編碼之間的關(guān)系可以看出， 頻率差值不等情況下所需的平均Huffman編碼長度比頻率差值相等情況下小，隨著頻率差值的增加這種差距越明顯#65377;

4結(jié)束語 

與目前已有的很多方案一樣，該方案也可以實現(xiàn)攻擊時和攻擊后的追蹤#65377;目前的概率包標記方案[1，4]需要成百上千個攻擊包才可重構(gòu)攻擊路徑，而該方案一個很大的特點是只需一個包(無論是攻擊包還是合法的包)就能重構(gòu)DoS和DDoS攻擊路徑，因為不同的攻擊路徑有不同的ls，而不同的序列流能夠解密不同的攻擊路徑;與ingress filter#65380;logging#65380;packet marking等方案相比，該方案需要的存儲空間更少這也是本方案最成功的地方#65377;存儲標記域增加了路由器的開銷是該方案與其他方案相比存在的不足之處，不過從實驗結(jié)果來看此開銷還是很小的#65377;進一步的研究方向是將該方案運用到IPv6中去，并且盡量將路由器的開銷減少到最低程度#65377;

參考文獻:

[1]SAVAGE S，WETHERALL D，KARLIN A.Practical network support for IPtraceback[C]//Proc of the ACM SIGCOMMConference.New York: ACM Press，2000:295-306.

[2]FERGUSON P，SENIE D.RFC 2827， Network ingress filtering:defeating denial of service attacks which employ IP source address spoofing[S].2000.

[3]BABA T.Tracing network attack to their sources [J].IEEE Internet Computing，2002，6(2):20-26.

[4]SONE D X，ADRIAN P.Advanced and authenticated marking schemes for IP traceback[C]//Proc of IEEE INFOCOM’01.Anchorage， Alaska: IEEE Press， 2001:878-886.

[5]PAPK K，LEE H.On the effectiveness of probabilistic packet marking for IP traceback under denial of service attack[C]//Proc of IEEE INFOCOM.Anchorge:IEEE，2001:338-347.

[6]嚴蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu):C語言版[M].北京:清華大學出版社，1997:144146.

[7]STONE R. Center track:an IP overlay network for tracking DoS floods[C]//Proc of the 9th Usenix Security Symp.Usenix Assoc:[s.n.]，2000:199-212.

[8]STRAYER T.SPIEIPv6: single IPv6 packet traceback，local computer networks[C]//Proc of the 29th Aunual IEEE International Conference.Boston: IEEE Standards Office，2004:118125.

[9]BURCH H，CHESWICK B.Tracing anonymous packets to their approximate source[C]//Proc of the 14th Conf Systems Administration.[S.l.]:Usenix Assoc，2000:319-327.

“本文中所涉及到的圖表、注解、公式等內(nèi)容請以PDF格式閱讀原文”