一種準確快速定位的節點包標記算法
2008-12-31 00:00:00劉淵李秀珍陳彥
計算機應用研究 2008年12期
（1．江南大學 信息工程學院， 江蘇 無錫214122； 2．南京理工大學計算機學院，南京 210093）
摘 要：
目前對于拒絕服務攻擊 (DoS)和分布式拒絕服務攻擊(DDoS)，概率包標記(PPM)和高級包標記方案(AMS)是有效的IP追蹤技術，但其存在很大的誤報率，不能快速追蹤到攻擊者。在AMS的基礎上改進了包標記方法，合理假設在一個自治系統中，采用節點標記方法，經理論分析能降低誤報率；經實驗驗證用較少的數據包就可以快速準確地定位到攻擊者。
關鍵詞：分布式拒絕服務攻擊; 概率包標記; 高級包標記; 節點包標記; IP追蹤
中圖分類號：TP309 文獻標志碼：A
文章編號：10013695(2008)12373902
Kind of accurate and fast location node packet marking schemes
LIU Yuan1，2，LI Xiuzhen1， CHEN Yan 1
(1.College of Information Engineering， Southern Yangtze University， Wuxi Jiangsu 214122， China; 2.School of Computer， Nanjing University of Science Technology， Nanjing 210093， China)
Abstract:Probabilistic packet marking and advanced marking schemes are effective technique for IP traceback. However， they use the edge sampling method which exists the large 1 positive rate and can’t fast trace the attacker. Based on reasonable hypothesis， in a large autonomous system， this paper improved AMS with node sampling， which could reduce the 1 positive rate by theoretical analysis， could quickly and accurately locate the attacker by experimental verification.
Key words：DDoS; probabilistic packetmarking(PPM); advanced marking schemes(AMS);node sampling;IP traceback
隨著網絡技術的發展，IP追蹤成為防范DoS和DDoS攻擊的主要手段。概率包標記[1](PPM)作為一種有效的DDoS攻擊追蹤技術，無須互聯網提供商（ISP）的支持，可以減少管理開銷；但它也存在一些缺點，如重復的包標記導致標記概率的不平衡引發最弱鏈的問題，并存在較大的誤報數等。高級包標記[2]（AMS）采用了hash函數算法，比PPM降低了誤報數，但是在重構路徑的過程中要知道上游完整的網絡拓撲信息。而且PPM和AMS均假設路徑中的所有路由器都具備標記功能并可追蹤標記，這增大了設備開銷，降低了工程的可操作性，因此合理的假設應該是在一個自治系統中完全部署。本文的包標記方法是假設在一個自治域系統中，經過分析受害者無須知道完整的網絡上游拓撲信息，利用較少的數據包就可以快速定位到攻擊者。
1 包標記
1. 1 AMS
數據包在途中經分段（fragment）處理的情況是很少出現的（不超過0.25%[3]），因此IP頭中的識別號域（identification field）也很少使用。Song等人提出了高級包標記，把路徑信息嵌入到識別號域中。標記的方法是把16 bit的identification field分為5 bit的distance字段和11 bit的edge字段，如圖1所示。當路由器以概率q標記數據包時，將路由器的IP地址h(Ri )寫入到edge字段中，distance值賦為0；如果distance值為0，說明它被前一個路由器標記過，將edge字段的值異或h(Ri)，并用異或后的值來重新填入edge字段。如果路由器不標記數據包，就只將distance的值加1。這樣edge字段包含兩個相鄰路由器的異或結果。因為aba＝b，可以從受害端開始，一個hop連著一個hop重構出攻擊路徑中的全部路由器。這樣數據包中的標記信息實際上是兩個相鄰路由器之間的邊（或連接）的信息。
在該方案中假設路徑中的路由器都支持標記追蹤，即完全部署，且采用邊標記。在完全部署時，構成一條邊的兩個節點是相鄰的；但是在非完全部署時，一條邊的兩個節點之間可能有多個沒有標記功能的路由器，這樣采用邊采樣的AMS方案中距離信息對標記的路由器計數就不是真實的距離，會產生很大的誤報數。方案中，路由器向數據包標記的信息是路由器IP 地址的hash值，而hash 函數是單向的，這就使得受害者必須知道上游網絡的拓撲信息。由于攻擊者可能來自于Internet 上的任何地方，而且網絡的上游拓撲信息也是變化的，這就意味著受害者幾乎要預先知道整個Internet 的拓撲信息，這在實際中非常困難。從理論上講，上游網絡的拓撲信息對任何人都可得到，用戶可較輕易地利用 tracert 命令或CAIDA 的skitter[4]或者其他類似工具得到。但，普通用戶一般不具有大量的存儲空間用于存放拓撲信息。當然，ISP 可以為普通用戶提供拓撲信息，ISP 甚至可以在其用戶遭到 DoS和DDoS攻擊時為其提供追蹤服務，但這對ISP 又提出了更高的要求。下面對原方案進行改進，使得受害者不完全需要知道上游網絡拓撲信息就能快速定位到攻擊者。
1. 2 新的包標記方案
新的包標記方案是假設在自治域系統中（AS），有一個ISP運營的網絡稱為自治系統，一個自治系統有惟一的16 bit的自治系統編號（AS number）。新的包標記方法如圖2所示。
在以往的包標記方案中，identification標記的是路由器IP地址信息，新方案標記的是16 bit的AS number，這樣在IP追蹤時可以快速判定是在哪個自治系統中。用文獻[5]中計算距離的方法，標志位RF表示為1 bit的距離域，RF用來存儲TTL值的低位第六位的值。識別號identification是用于分段數據包的重組，當identification作為標記IP地址信息時，后面的fragment offset也就沒有意義了。把32 bit的 IP地址信息經過hash函數h(#8226;)轉換為13 bit的地址信息摘要標記在fragment offset域。當路由器以概率q(q=0.04)標記包時，將AS number寫進identification域，DF置為1（數據包不分片），MF位置為0（數據包后面沒有包，該包為最后包）， TTL的低位數起第六位1 bit的數存儲在1 bit的RF域，常量C的值賦予TTL[4…0]。將IP地址13 bit的信息摘要寫進offset域，若路由器不標記就不作任何操作。由文獻[5]知，TTL[5…0]表示的是TTL的后六位數，TTL[5]表示的是TTL的第六位數，TTL[4…0]表示的是TTL的后五位數；C是常量，取值為22（文獻[5]中通過實驗說明取值22是最優的）；p.RF|c表示的是p.RF中一位數與TTL的后五位數連接為六位數。每經過一個路由器TTL就自動減1。距離的計算方法為：
d=(p.RF|c-TTL[5…0])mod 64
即數據包被最后一個路由器標記時的p.RF|c值與當前的TTL差的模64。 具體算法如下：
for each packet p
let r be a random number from(0，1)
if (r<=q) OR( p.RF|c-TTL[5…0] mod 64)>32 then
p.idenfication:=AS number
p.DF:=1
p.MF:=0
m:=h(ip);
p.offset=m
p.RF:=TTL[5]
TTL[4…0]:=C;
else TTL:=TTL-1
定位攻擊者：路徑重構中本文的主要目標是找到攻擊者。在受害者處收到m個數據包，按不同的AS number號組成n個集合Ii(i≤i≤n)。m個距離d值按不同的距離值分為m′個不同的d值。
距離值為di和對應的13 bit IP地址信息h(ri) {di，h(ri)}值組成集合Ii，如圖3所示。對于Ii集合，依據距離值由小到大的順序，當距離d值最大時，即數據包被第一個路由器標記，距離攻擊者最近的一個路由器。通過ISP的支持，由13 bit IP的信息摘要可以計算出IP地址信息，根據對應的AS number號即可定位到攻擊者。
2 性能分析
1)誤報數 高級包標記方法沒有對IP地址進行分段，而是通過hash函數產生11 bit的輸出，它的誤報數來自攻擊者其hash沖突的情況。由文獻[2]中計算誤報數的計算方法，設Sd表示攻擊圖中離受害端距離為d的路由器集合;ty表示在Sd-1中元素y的入度； |ψd|表示受害端接收到的distance=d的邊段數目。11 bit的hash相同的概率是1/211，距離distance=d的節點數是|ψd|，每個節點的入度是ty，所以距離為d+1處的誤報數E=ty×|ψd|/211 ；新方案中的誤報數 E= ty×|ψd|/213。新方案的誤報數是高級包標記的25%，降低了誤報數。
2)重構路徑的工作量 令M 表示在因特網中與同一個路由器直接連接的上游路由器的平均數量。在高級包標記中，如果在距離d 處有k個節點，在距離k+1處有 k′個節點，則受害者平均至少需作7k′+kM次hash運算。在新方案中依據最大的距離d值定位到攻擊者時只需作一次hash運算，這樣降低了計算工作量。由于標記了自治系統號，每個自治系統號是惟一的，ISP只要提供一個自治系統中的網絡拓撲信息就可以快速定位到攻擊者。高級包標記在重構路徑時需要獲得上游完整的網絡拓撲信息，而且網絡拓撲信息也是變化的，這會增加誤報數，也會為ISP帶來困難。
3)距離值的計算 高級包標記中的距離值采用的是0/1遞增的計算方法，在非完全部署時距離值是不準確的，這會增加誤報數。新的標記方案是用文獻[5]中TTL值計算距離的方法，且在一個自治域大系統中路由器是完全部署的，這樣得到的距離值是真實的，可降低誤報數。
4)路由器標記數據包工作量 高級包標記和新方案中，路由器對數據包的標記都用到了hash 函數，但由于hash 的輸入固定，路由器可將這些hash 值預先運算后儲存起來，而不必在每次標記數據包時重新計算。因此，可以認為hash 運算對標記的運算量沒有顯著的影響。
3 模擬實驗
為了測試改進方案的性能，在一個大自治域系統中進行了模擬實驗，數據來源是CAIDA[6]（Cooperative Association for Internet Data Analysis）提供的跟蹤路由仿真實驗。選取的攻擊路徑長度d=1，2，3，…，30，對每一個路徑長度d，發送的數據包是100，150，200，…，直到能定位到攻擊者，對每個路徑長度d經過多次實驗得到能定位到攻擊者的平均數據包量。實驗中取q=0.04，實驗結果如圖4所示。經計算得到本文的算法定位到攻擊者需要的平均數據包數量約是高級包標記的42%。故在自治系統中利用本文算法，受害者需要很少的數據包就可以快速準確地定位到攻擊者。
4 結束語
目前的PPM和AMS攻擊追蹤方案均在假設路由器具有標記、回溯追蹤功能基礎上的，不能廣泛用于實際網絡中。本文是在AMS方案的基礎上對原有的假設合理地改為在一個自治域系統中路由器的完全部署，由AMS標記的邊采樣改為節點采樣。經過理論分析新的包標記方案能降低誤報數，經實驗驗證需要較少的數據包就可以快速準確地定位到攻擊者。但是本文算法是假設在一個自治域系統中，對于整個Internet網絡應用還有待研究。
參考文獻：[1]SAVAGE S， WETHERALL D， KARLIN A， et al. Practical network support for IP traceback[C]//Proc of ACM SIGCOMM Conference. New York: ACM， 2000:295306.
[2]SONG D X， PERRIG A. Advanced and authenticated marking schemes for IP traceback[C]//Proc of the 20th Annual Joint Conferenceon IEEE Computer and Communications Societies. Los Alamitos: IEEE Computer Society， 2001:878886.
[3]STOICA I， ZHANG Hui. Providing guaranteed services without per flow management[C]//Proc of ACM SIGCOMM Conference. New York: ACM，1999:8194.
[4]Cooperative Association for Internet Data Analysis (CAIDA). The skitter project[EB/OL].(20050305). http://www.caida.org/tools/measurement/skitter/.
[5]YAAR A， PERRIG A， SONG D. FIT: fast Internet traceback[C]//Proc of IEEE INFOCOM. Miami， FL:[s.n.]， 2005:13951406.
[6]Cooperative Association for Internet Data Analysis[EB/OL].http://www.caida.org.
