基于Huffman編碼的包標記算法研究

李明珍，覃運初，唐鳳仙

(河池學院 計算機與信息工程學院，廣西 宜州 546300)

0 引言

隨著網(wǎng)絡技術(shù)的發(fā)展與推廣應用，網(wǎng)絡日益滲透到社會的各個領域，給人們帶來方便的同時，也引發(fā)了一系列網(wǎng)絡安全問題，其中以DDoS攻擊問題最為突出。

DDoS攻擊的實質(zhì)，是指攻擊者利用傀儡機發(fā)送大規(guī)模無用的數(shù)據(jù)來占用網(wǎng)絡帶寬或主機資源，當無用的數(shù)據(jù)占用完所有網(wǎng)絡資源時，造成網(wǎng)絡癱瘓，即用戶正常的網(wǎng)絡服務請求無法得到滿足。有效遏制DDoS攻擊的關鍵在于攻擊源的定位，確定攻擊者IP地址。確定攻擊者IP地址后，在邊界路由器設置包過濾規(guī)則，過濾擁有攻擊者IP地址的數(shù)據(jù)包，從而有效抵抗DDoS攻擊。

IP追蹤技術(shù)，是一種攻擊源定位技術(shù)，旨在通過提取IP地址信息定位攻擊源。在IP追蹤技術(shù)中，包標記算法［1］具有易操作、管理代價小、不需要ISP合作等優(yōu)點，是研究的熱點。文獻［2］對IP追蹤技術(shù)進行綜述，對比分析了各種包標記算法的優(yōu)缺點，指出選擇“標識”字段(16 bit)作為標記區(qū)域，以一定概率標記數(shù)據(jù)包，標記的信息很有限，重構(gòu)攻擊路徑時所需數(shù)據(jù)包個數(shù)隨路徑長度的增長呈指數(shù)增長——最弱節(jié)點問題;文獻［3－4］針對包標記最弱節(jié)點問題，提出動態(tài)概率包標記算法，有效解決了最弱節(jié)點問題，但是也增加了路由器標記概率計算的復雜度;文獻［5］描述了IPv4數(shù)據(jù)報首部的路由選項字段功能，該字段可以記錄路徑，但空間有限，只有40 Byte，不能夠記錄完整的路徑;文獻［2，6］提到的節(jié)點附加與文獻［5］中的路由選項思想類似，但是會導致不必要的分包;文獻［7］提出基于Huffman編碼的包標記算法，該算法記錄的是鏈路號而不是IP地址，減少標記內(nèi)容，但要求路由器保持一份鏈路信息表。

本文結(jié)合文獻［2，6－9］的算法思想，提出一種增加標記空間、減少編碼長度和增加算法適用范圍的改進算法。

1 相關知識

1.1 IPv4數(shù)據(jù)報格式

圖1 IPv4數(shù)據(jù)報格式［10］

圖2 IPv4選項格式［10］

1.2 IPv6數(shù)據(jù)報格式

圖3 IPv6數(shù)據(jù)報格式［11］

1.3 Huffman編碼

Huffman編碼，是一種無損數(shù)據(jù)壓縮方法，根據(jù)字符出現(xiàn)的頻率來構(gòu)造平均長度最短的碼字。本文根據(jù)數(shù)據(jù)報到達一條鏈路的頻率的高低來對其編號，頻率越高編號越小，如此，得到的編碼最短。

圖4 IPv6擴展首部格式［11］

2 算法改進

2.1 算法思想

本文提出在IPv4下選擇“選項”字段作為標記區(qū)域，采用Huffman編碼標記鏈路號;利用IPv6的隧道模式，在IPv4到IPv6網(wǎng)絡切換時增加一個復制操作，將標記信息轉(zhuǎn)存到IPv6的hop－by－h(huán)op擴展首部，改進算法適用于IPv4和IPv6網(wǎng)絡，且只需一個標記包即可完成攻擊路徑重構(gòu)。

2.2 標記內(nèi)容

改進算法要求每一個路由器維持一個鏈路表，如圖5所示。鏈路表記錄與當前路由器直接相連的鏈路號和上一跳路由器IP地址，鏈路的編號按照數(shù)據(jù)到達頻率的高低來編號，頻率越高編號越小，鏈路編碼也越短。

與路由器相連的鏈路數(shù)≤4［12］，鏈路號編碼最大為4，編碼長度為3 bit;數(shù)據(jù)包傳輸過程中經(jīng)過的跳數(shù)≤16［12］，故標記一條攻擊路徑的編碼長度≤64 bit(1 bit+3 bit*16+5 bit=54 bit，取 64 bit，字節(jié)對齊)。

其中，分界符1 bit，用來區(qū)分兩個鏈路號;距離d與鏈路號一一對應，表示當前鏈路與攻擊者的距離。如圖6所示。

圖6 標記格式

2.3 標記區(qū)域

IPv4下選擇“選項”字段作為標記區(qū)域;IPv6下選擇擴展首部“hop－by－h(huán)op”字段作為標記字段;將鏈路號依次標記到選項里，同時修改距離值，每經(jīng)過一個路由器距離值增加1。

2.4 隧道技術(shù)

IPv4協(xié)議和IPv6協(xié)議數(shù)據(jù)報格式差別較大，針對IPv4和IPv6協(xié)議并存的網(wǎng)絡，采用隧道技術(shù)(封裝)解決不同網(wǎng)絡協(xié)議標記區(qū)域不同的問題。IPv4網(wǎng)絡傳輸?shù)絀Pv6，使用IPv6首部封裝IPv4數(shù)據(jù)報，同時檢測選項字段是否有標記信息，如果有的話增加一個復制操作，把標記信息標記到擴展首部hop－by－h(huán)op，沒有標記信息的話不作任何操作;反之，則用IPv4首部封裝IPv6數(shù)據(jù)報，將標記信息標記到選項字段或不做任何操作。以IPv4到IPv6網(wǎng)絡標記信息的復制為例，復制操作代碼如下:

改進的算法適用于IPv4和IPv6環(huán)境，提高了算法的兼容性。

2.5 路徑重構(gòu)

當受害者檢測到攻擊時，提取標記包中的標記信息，結(jié)合路由器中的鏈路表來重構(gòu)攻擊路徑。具體步驟如下:

1)distance=d時，開始進行攻擊路徑反向回溯，與鏈路號相關的路由器即受害者最近的路由器為Rd;

2)distance=d－1時，結(jié)合標記信息中的鏈路號、距離和鏈路表找出對應的路由器Rd－1;

……

d)distance=1時，找出最后一個路由器R1，即離攻擊者最近的路由器。按序排列好的路徑{Rd→Rd－1→……→R1}就是攻擊路徑。

3 實驗結(jié)果分析

3.1 算法分析

本文改進的算法具有標記信息量大、兼容性高和路徑重構(gòu)所需數(shù)據(jù)包數(shù)量少的優(yōu)點。

與文獻［2－3］相比，路徑重構(gòu)時所需標記包的數(shù)量大大減少，只需要一個即可完成路徑的重構(gòu);與文獻［7－8］相比，選擇的標記區(qū)域空間足夠滿足需求，無須轉(zhuǎn)存到路由器的緩存中，降低路由器的處理開銷，并且改進算法兼容性高，適用于IPv4和IPv6網(wǎng)絡環(huán)境。

3.2 實驗結(jié)果分析

包標記算法的性能評價指標主要是從標記算法的復雜度和重構(gòu)攻擊路徑所需標記包的數(shù)量來衡量。本文改進的算法，在標記時采用直接賦值的方式，計算復雜度為O(1);路徑重構(gòu)只需要一個標記包。

實驗在Linux系統(tǒng)+NS2仿真軟件下進行，跳數(shù)取值范圍為［1，30］，對PPM算法和ADPPM算法路徑重構(gòu)所需數(shù)據(jù)包進行對比分析。實驗結(jié)果如圖7所示。

4 總結(jié)

算法分析和實驗結(jié)果表明，本文提出的改進算法在算法復雜度和路徑重構(gòu)效率上有了較大改進，兼容性也大大提高。不足的是要求每一個路由器保持一個鏈路表，增加了路由器的開銷。此外，雖然標記的信息不足8 byte，但還是增加數(shù)據(jù)包的長度，有可能造成分片，增加算法復雜度。算法存在的問題，是今后研究的重點。

圖7 路徑重構(gòu)所需標記包數(shù)量與跳數(shù)的關系

［1］H Burch，B Cheswick，Tracing anonymous packets to their approximate source［C］//Proceeding of the 2000 USENIX LISA Conference.New Orleans，USA，December，2000:319 －327.

［2］Savage S，Wetherall D，Karlin A，et a1.Practical network support for IP traceback［C］//Proceedings of the 2000 ACM SIGCOMM Conference.New York，USA:ACM Press，2000:295－306.

［3］Peng T，Lecki C，Ramamohanroa K.Adjusted probabilistic packet marking for IP traceback［C］//Proceedings of Networking 2002 Pisa，Italy:IFIP Press，2002:697 －708.

［4］Song Dawn，Perrig A.Advanced and authenticated marking schemes for IP traceback［C］//Proc of IEEE INFOCOM 2001.Alaska，USA:IEEE Press，2001:878 －886.

［5］Postel J.IP OPTION NUMBERS［EB/OL］.［2015－01－08］http://www.iana.org/assignments/ip－parameters/ip－parameters.xhxhtml，2013－05－28.

［6］蔣華，李明珍，王鑫.一種基于概率包標記的PPM算法改進方案［J］.山東大學學報(理學版)，2011，46(9):85－88.

［7］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 Hong kong，China，2004:421 －428.

［8］胡清鐘，張斌.IPv6下基于Huffman編碼的路徑回溯算法研究［J］.計算機工程與科學，2013，35(5):51－55.

［9］李明珍，蔣華，王鑫.基于擴展首部hop－by－h(huán)op的IPv6包標記算法研究［J］.計算機應用研究，2012，29(6):2313－2316.

［10］Postel J.Internet Protocol(IPv4)［EB/OL］.［2015－01－08］http://datatracker.ietf.org/doc/rfc791/，2013－03－02.

［11］Deering S，Hinden R Internet Protocol(IPv6)［EB/OL］.［2015 －01 －08］http://www.ietf.org/rfc/rfc2460.txt，1998 －12.

［12］Palmer C R，Siganos G，F(xiàn)aloutsos M，et a1.The connectivity and fault tolerance of the Internet topology［C］//Proceeding of the 2001 Workshop on Network Related Data Management，Santa Barbara，2001.