IP追蹤中的包標記算法＊

吳蓉暉，吳 嵐

（湖南大學信息科學與工程學院，湖南長沙 410082）

IP追蹤中的包標記算法＊

吳蓉暉?，吳 嵐

（湖南大學信息科學與工程學院，湖南長沙 410082）

針對基本包標記算法效率低的問題，提出了一種改進算法.通過優化傳統的路徑信息編碼方式，對其標記過程和重構過程作了相應的修改，使受害者可以更快地重構出攻擊路徑.仿真實驗結果表明：該算法能夠有效地減少組合次數，提高追蹤效率，并且大大降低了誤報率.在實際的拒絕服務攻擊中能夠使受害者更快更準確地追蹤到攻擊者，從而減少損失.

IP追蹤；網絡安全；包標記；拒絕服務攻擊；分布式拒絕服務攻擊

計算機網絡對人們的生活、工作、學習方式等很多方面產生了深遠的影響，網絡安全越來越受到重視，其中分布式拒絕服務攻擊（Distributed Denial of Service，DDoS）由于具有易實施、難防范、追蹤困難等特點，成為了互聯網最難解決的安全問題之一.網絡追蹤作為對付拒絕服務攻擊的重要手段，也得到了國際同行的重視.國內外的許多學者都對此提出了多種追蹤方案，其中包標記以其追蹤效率高，收斂時間短等優勢成為了研究熱點.其中最具代表性的有Savage等［1］提出的概率包標記算法（Probabilistic Packet Marking，PPM），其無論在路由器開銷還是TCP／IP兼容方面都具有突出的優勢，概率包標記也稱為基本包標記.基本包標記在拒絕服務攻擊下的攻擊者追蹤方面是一個開創性的工作，具有重要意義.

Park等［2］分析了基本包標記在攻擊者偽造IP地址時追蹤的不確定性.文獻［3］通過實驗演示了基本包標記在進行攻擊路徑的重構時具有計算量大、誤報率高等缺點，并提出了2個方案，分別稱為高級包標記（Advanced Packet Marking，APM）和帶認證的包標記（Authenticated Packet Marking），這2種方法在重構攻擊路徑時，需要網絡的拓撲信息.Dean等［4］提出的基于代數編碼的包標記也是在基本包標記的基礎上進行研究的，其動機來源于基本包標記的組合爆炸和誤報率高的缺點.文獻［5］提出了基于路由器編碼的自適應包標記.文獻［6－7］都各自提出一種動態概率包標記方法（DPPM）.文獻［8］將一種改進的壓縮邊分段采樣算法（Compressed Edge Fragment Sampling，CEFS）為基礎與可變概率標記相結合，提出一種復合式標記方法PCEFS.文獻［9］采用的因特網快速追蹤算法，只需1 bit就可以記錄節點的跳數關系，大大節約了標記空間.文獻［10］利用中國余數定理的唯一性來標記IP分塊的特征，有效避免了hash碰撞的發生，具有一定的創新性.本文在PPM基礎上提出了一種新的標記方法，其在誤報率、收斂時間、計算量等方面均比基本包標記優越，具有很強的可執行性.

1 概率包標記

為了快速追蹤到攻擊者，最好的方法是將路由器地址信息全部標記到數據包中，當受害者收到這些包后，就可以直接得到路徑信息.但是，由于MTU（最大傳輸單元）的限制，這種做法明顯行不通.因此只能在數據包中標記部分路徑信息.文獻［1］采用的方法是將IP與其32 bit的hash值（作為校驗碼）以比特為單位間隔穿插得到64 bit.然后將此64 bit分為8塊，每塊8 bit，并將其分別編號為0，1，…，7（即偏移offset），如圖1所示.當向數據包嵌入路由信息時，將距離和8個分塊之一以及相應的偏移嵌入到該數據包的標記域.為了在接收方能得到準確的距離信息，在對包進行標記時需將距離域置為0，如果緊接著下一個的路由器不標記該包，則其將距離增加l，并把自己的與偏移對應的塊與數據包中的塊異或重新填入.在Internet中，數據包所經過的路徑一般不超過30［5］，因此，用5 bit就可以存放距離信息.所以標記域需要5＋8＋3共計16 bit的空間.基本包標記中邊信息的重組如圖2所示.

在IP報文的格式中，包頭的Identification域是用來識別在一個分段數據包的重組時的不同分段的，而在Internet中，只有大約不到0.25%［11］的包會分段傳輸，也即Identification域基本是不被采用的，故用于包標記算法標記路徑信息所需的16 bit的空間可以存放在Identification域中.

圖1 IP地址與校驗碼按bit穿插，然后分組Fig.1 The hash is interleave with the address then group into 8 fragments

圖2 邊信息重組圖Fig.2 Reconstructing a candidate edge

1.1 計算量

概率包標記算法在路徑重構時，需要檢查每種組合是否為合法的IP，即通過計算該組合的hash值是否與其攜帶的hash值相等，而在此過程中，每一次的hash計算是最大的開銷，故可以用計算hash的次數來衡量該路徑重構過程的計算量，而hash次數與每一種組合是一一對應的，因此只需計算出總共有多少種組合就可以大約估計出整個過程的計算量.

若在實際攻擊樹中有k個節點到受害者的距離為d＋1（距離域的值為d），則對于相同的d和相同的偏移，會有多個不同的分塊.假設偏移為0，1，…，7的互不相同的分塊數量為k0，k1，…，k7，則需檢查組合.假設最遠的攻擊者距離受害者為L＋1，則整個重構過程的計算量為

1.2 誤報數

若一個路由器在重構出的攻擊路徑上，而不在實際的攻擊路徑上，則稱此為一個誤報.在前面的條件下，有k個節點到受害者距離為d＋1，故任意8個隨機塊的組合通過hash檢測的概率為2－32k，即在種組合中只有k種組合會得到合法的節點，而其余種組合中通過檢測的數量平均為：

由式（1）可知，如果ki不小于16，則平均誤報數大于k.

2 改進算法

通過對概率包標記算法標記過程的分析，發現路由器是將IP地址（32 bit）與其hash值（32 bit）按位穿插得到64位，將其分為8 bit塊，每一塊均攜帶IP值與hash值，這樣，在路徑重構時需要將所有分塊全部進行重組，再逐一hash，故工作量非常大.因此，將按位穿插改為拼接，即將hash值直接添加到IP值的后面，如圖3所示，仍然是64位分為8 bit塊，這樣，偏移為0～3塊攜帶的為IP地址信息，而偏移為4～7分塊攜帶的是hash信息.在最后的路徑重構時，只需偏移為0～3的塊參與組合即可，極大地減少了組合次數.

圖3 將IP地址的hash值直接附加到IP后面Fig.3 The hash add behind the IP address

具體步驟為：將hash（IP）添加到IP后面，得到64位，分為8 bit塊，共8塊，路由器隨機抽取一塊添加到標記域當中.當受害者收到足夠的數據包時，將數據包按距離域與偏移域的值分為若干個集合，當距離值相等時，只需組合前4個集合（offset為0，1，2，3）中的數據，得到個集合，然后檢查這些集合中哪些構成合法的IP地址.檢查方法：對一個組合的32 bitIP地址求其hash（IP），然后按順序分成4塊8 bit的塊，然后檢查后4個集合（offset為4，5，6，7）中是否都分別包含了這4個塊，如果包含，則認為這一組合為一個合法的IP.改進后的算法描述如下：

3 仿真分析

為了模擬大規模DDoS攻擊，且能夠方便地改變實驗配置以進行多組不同的實驗，故采用普遍使用的NS-2仿真軟件進行模擬測試.

NS-2不支持PPM算法，為了構建DDoS攻擊和PPM算法模擬平臺，必須對NS-2進行擴展.將NS－2的IP包頭修改，添加一個16位的字段表示IP數據包頭中的Identification字段，利用該字段填寫包標記信息，并在Classifer類中添加需要實現仿真的各種算法.本實驗過程是將基本包標記、高級包標記以及拼接算法進行性能分析，添加的成員分別為PPMAlgorithm， APMAlgorithm和Conn Algorithm.在仿真過程中，為實現典型的PPM算法，節點上綁定UDP，使用CBR對象生成流量，并且按照不同需求部署攻擊流量和正常流量的比例.對于改進的PPM方法，可以通過腳本修改相應的參數，從而可靈活地在相同環境下針對不同的PPM方法模擬大規模DDoS攻擊和反向追蹤執行效果.

根據Gnuplot NS-2仿真過程記錄data文件，輸出的實驗數據如圖4所示.由圖4可知，相對PPM，拼接算法無論在重構速度還是包需求量方面均有較大優勢；即使相對于性能較好的APM，新算法也表現出了較好的性能.文獻［5］的作者采用了一種自適應包標記算法，將文獻［5］中的數據與實驗得出的結果比較分析可知，雖然前者在路由器未被攻占的條件下性能較好，但在路由器參與偽造的情況下，新算法表現出了較大的優勢.再與文獻［12］比較，攻擊路徑長度在2～25個內，新算法在包數量上明顯比前者低，而在收斂時間上，其處在百數量級，而文獻［13］中的數據已經上千.

圖4 PPM，APM以及改進算法的重構時間和所需包數對比Fig.4 The contrast of the reconstruction time and the number of the packet between PPM，APM and the new algorithm

4 結 論

本文通過對PPM算法的分析，將原先的IP地址與其hash值按位穿插改為拼接，并且對其重構過程也作了相應修改，極大地減少了受害者重構路徑的計算量并有效減少了誤報.仿真實驗結果表明，采用拼接的方法明顯降低了PPM的收斂時間以及需要數據包的個數，從而能夠更快、更準確地追蹤到DDoS攻擊者.

［1］ SAVAGE S，WETHERALL D，KARLIN A，etal.Practical network support for IP traceback［C］／／Proceedings of the 2000 ACM SIGCOMM Conference.Stockholm，Sweden：ACM Press，August，2000：295－306.

［2］ PARK K，LEE H.On the effectiveness of probabilistic packet marking for IP traceback under denial of service attack［C］／／Proceedings of IEEE INFOCOM’01.Anchorage，Alaska：IEEE Computer and Communications Societies，April，2001：338－347.

［3］ DAWN X S，PERRIG A.Advanced and authenticated marking schemes for IP traceback［C］／／Proceedings of IEEE INFOCOM.Alaska：IEEE Computer and Communications Societies，2001，2：878－886.

［4］ DEAN D，FRANKLIN M，STUBBLEFIELD A.An algebraic approach to IP traceback［C］／／Network and Distributed System Security Symposium Conference Proceedings，NDSS’01.San Diego，California：IEEE Computer Society Press，February，2001.

［5］ LI De-quan，SU Pu-rui，WEI Dong-mei，etal.Router numbering based adaptive packet marking［J］.Journal of Software，2007，18（10）：2652－2661.

［6］ 趙隴，吳辰文.基于動態概率包標記的IP追蹤技術研究［J］.計算機技術與發展，2008（12）：217－219.

ZHAO Long，WU Chen-wen.IP tracing technology research based on dynamic probabilistic packet marking［J］.Computer Technology and Development，2008（12）：217－219.（In Chinese）

［7］ FENG Bo，GUO Fan，YU Min.Dynamic probabilistic packet marking based on PPM［C］／／2009 Second Pacific-Asia Conference on Web Mining and Web-based Application.Wuhan，China：IEEE Computer Society Press，June，2009：289－292.

［8］ 高大鵬，於時才，閆文芝.復合包標記IP追蹤算法研究［J］.計算機工程，2009（10）：115－117.

GAO Da-peng，YU Shi-cai，YAN Wen-zhi.Research on composed packet marking for ip traceback algorithm［J］.Computer Engineering，2009（10）：115－117.（In Chinese）

［9］ YEAR A，PERRIG A，SONG D.FIT：fast internet traceback［C］／／Proceedings of 24th Annual Joint Conference of the IEEE Computer and Communication Societies：INFOCOMM 2005.Washington，DC：IEEE Computer and Communications Societies，2005：1395－1406.

［10］徐勁松.一種改進的路由包標記追蹤方案［J］.計算機應用，2009（5）：1316－1320.

XU Jin-song.Improved router packet marking tracking scheme［J］.Journal of Computer Applications，2009（5）：1316－1320.（In Chinese）

［11］STOICA I，ZHANG H.Providing guaranteed services without per flow management［C］／／Proceedings of the 1999 ACM SIGCOMM Conference.Boston，Massachusetts：MCM Press，Aug，1999：81－94.

［12］ZHOU Zai-hong，XIE Dong－qing，JIAO Bing-wang.A maekawa set based marking scheme［J］.Information Technology Journal，2009，8（4）：504－512.

Research on the Packet Marking Algorithm for IP Trackback

WU Rong-hui?，WU Lan

（College of Information Science and Engineering，Hunan Univ，Changsha，Hunan 410082，China）

To solve the problem of low efficiency of probabilistic packet marking，an improved algorithm was proposed.This new algorithm optimizes the encoding of path information and modifies the marking and reconstruction process，so that victims can quickly reconstruct the attack path.Simulation results have shown that the new algorithm can effectively reduce combination frequency，improve tracking efficiency and greatly reduce the false positives rate.In the actual denial of service attack，victims can track the attacker faster and more accurately，thus minimizing the damage.

IP traceback；network security；packet marking；Denial of Service（DoS）；Distributed Denial of Service（DDoS）

TP393

A

1674-2974（2011）06-0075-04＊

2010-12-03

國家自然科學基金資助項目（60803130）

吳蓉暉（1967－），女，河南太康人，湖南大學副教授

?通訊聯系人，E-mail：wrh＠hnu.cn