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

李明珍，覃運初，唐鳳仙

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

0 引言

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

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

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

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

1 相關知識

1.1 IPv4數據報格式

圖1 IPv4數據報格式［10］

圖2 IPv4選項格式［10］

1.2 IPv6數據報格式

圖3 IPv6數據報格式［11］

1.3 Huffman編碼

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

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

2 算法改進

2.1 算法思想

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

2.2 標記內容

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

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

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

圖6 標記格式

2.3 標記區域

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

2.4 隧道技術

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

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

2.5 路徑重構

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

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

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

……

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

3 實驗結果分析

3.1 算法分析

本文改進的算法具有標記信息量大、兼容性高和路徑重構所需數據包數量少的優點。

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

3.2 實驗結果分析

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

實驗在Linux系統+NS2仿真軟件下進行，跳數取值范圍為［1，30］，對PPM算法和ADPPM算法路徑重構所需數據包進行對比分析。實驗結果如圖7所示。

4 總結

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

圖7 路徑重構所需標記包數量與跳數的關系

［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－hop的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，Faloutsos 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.