吳蓉暉，吳 嵐

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

IP追蹤中的包標(biāo)記算法＊

吳蓉暉?，吳 嵐

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

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

IP追蹤；網(wǎng)絡(luò)安全；包標(biāo)記；拒絕服務(wù)攻擊；分布式拒絕服務(wù)攻擊

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

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

1 概率包標(biāo)記

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

在IP報文的格式中，包頭的Identification域是用來識別在一個分段數(shù)據(jù)包的重組時的不同分段的，而在Internet中，只有大約不到0.25%［11］的包會分段傳輸，也即Identification域基本是不被采用的，故用于包標(biāo)記算法標(biāo)記路徑信息所需的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 計算量

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

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

1.2 誤報數(shù)

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

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

2 改進算法

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

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

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

3 仿真分析

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

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

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

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

4 結(jié) 論

本文通過對PPM算法的分析，將原先的IP地址與其hash值按位穿插改為拼接，并且對其重構(gòu)過程也作了相應(yīng)修改，極大地減少了受害者重構(gòu)路徑的計算量并有效減少了誤報.仿真實驗結(jié)果表明，采用拼接的方法明顯降低了PPM的收斂時間以及需要數(shù)據(jù)包的個數(shù)，從而能夠更快、更準確地追蹤到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，F(xiàn)RANKLIN 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，F(xiàn)ebruary，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］ 趙隴，吳辰文.基于動態(tài)概率包標(biāo)記的IP追蹤技術(shù)研究［J］.計算機技術(shù)與發(fā)展，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］ 高大鵬，於時才，閆文芝.復(fù)合包標(biāo)記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］徐勁松.一種改進的路由包標(biāo)記追蹤方案［J］.計算機應(yīng)用，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

國家自然科學(xué)基金資助項目（60803130）

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

?通訊聯(lián)系人，E-mail：wrh＠hnu.cn