摘 要：提出了可避免數據包重復標記的可變概率分片標記算法。通過模擬試驗對比該提出的算法和基本包標記算法，結果表明該方法能夠消除對數據包的重復標記問題，并顯著地減少反向追蹤攻擊源所需數據包的數目，提高了對攻擊源定位的追蹤的準確性和實時性。
關鍵詞：重復標記；可變概率；傳輸距離
DoS是Denial of Service的簡稱，即拒絕服務。造成DoS的攻擊行為被稱為DoS攻擊，其目的是通過消耗遠程計算機網絡資源來使Internet站點拒絕提供給合法用戶的服務。這種類型的攻擊實施簡單、防御困難、危害極大，攻擊者的IP地址常常是經過偽裝的。針對此類攻擊的特點，研究者提出了很多解決方法，例如包標記、日志記錄、連接測試、ICMP追蹤、覆蓋網絡等。本文提出了可避免數據包重復標記的可變概率分片標記算法，減少路徑重構時所需的數據包數目以及運算時間，提高了對攻擊源定位的追蹤的準確性和實時性。
1 相關研究工作
由Savage等人提出的概率包標記算法BPPM，具有許多其他方法所不具有的優點：(1)無需與ISP相互合作，避免了調試中高額的管理費用；(2)無需增加巨大的網絡流量，可以跟蹤多種攻擊形式；(3)在攻擊停止后很久，仍然可以被用來分析登錄過程并制作用于跟蹤的數據包。(4)網絡路由器負載小。之后在BPPM的基礎上不斷產生出新的改進算法，例如自適應概率包標記、高級包標記和帶認證的包標記，以期減少路徑重構時所需的數據包，重構攻擊路徑時的誤報率，計算復雜度（時間復雜度）。
概率包標記的思想[1]是路由器以固定的概率p標記數據包，將路徑信息加入到IP頭中的16 bit識別域（ID）中，表示為（start，end，distance）。在路由器處產生一個[0,1]之間的隨機數，如果這個隨機數小于p，路由器將自己的IP填入到start，同時將distance賦值為0；否則將自己的IP地址填入到end中；如果路由器以概率1-p不對包標記，則將distance值加1。受害者從這些數據包中提出路徑信息，重構出攻擊路徑。
假設每個路由器標記數據包的概率為p，受害者從距離d（節點與受害者間路由器的個數）的路由器收集到被標記的數據包的概率為p（1-p）1-d。該函數是距離d的嚴格單調遞減函數，距離攻擊者越遠的路由器的樣本越難被采集到，因此算法的時間主要集中在接收最遠路由器提供樣本的時間上。例如，當d=20、P=1/2時，受害者要收集到此路由器上的樣本必須要收到平均1 048 576個數據包。
它最主要的缺點是隨著路徑的增長，所需要數據包的數量成指數增長，并且存在數據包的重復標記問題，距離攻擊者近的被標記的數據包可能被下邊的路由器標記，從而掩蓋曾經被標記過的信息，這就不可能很快地重構路徑防御攻擊。
2 改進的包標記算法NRVPPM
本論文提出一種改進的包標記算法，在包頭中增加標記位flags來避免數據包的重復標記問題，并且使用等概率p=1/di，使受害者主機可等概率地收集到攻擊路徑中路由器標記的數據包。
2.1標記概率
2.2標記格式
為了節省標記存儲空間，不給用戶帶來過多的影響，算法使用IPv4中的16位標識符字段（Identifer）[1]、1位閑置的標志位（Flags）、13位片位移字段（據統計目前少于0.25%的數據包需要分片）[3]，以及一般很少使用的8位TOS（Type-of-Sevice），總共38位來存儲包標記信息。標記格式如表1所示。
把32位的start路由器的IP地址和32位end路由器地址分為4塊。在start和end子域以等概率放置IP地址的4個8 位的片段，并相應地設置偏移offset子域值。
(1)flgs：如果flags=0，則表示數據包沒有被標記過；flags=1，則start子域已被標記過；flags=2，則start、end子域均被標記過。flgs的初始位被置為0。
(2)start和end：用來存儲邊的信息。
(3)distance： 用5位的distance來記錄數據包開始發送的路由器開始經過的跳數。distance的初始值被置為0。
(4)offest：用2位來記錄start和end的4個偏移。
(5)hash：hash(IP)取其后13位。
2.3 標記過程
把32位的start路由器的IP地址和32位end路由器地址分為4塊，在start和end子域以等概率放置IP地址的4個8 bit的片段，并相應地設置偏移offset子域值。路由器以概率p=1/d對數據包w進行標記。在路由器Ri 處，讓x為[0,1]之間的隨機數，y為[0,3]之間的隨機數，如果x<p，(a)當flags=0時，則把路由器Ri 的IP地址的第y個分片放入start域，distance域置為0；(b)當flags=1時，則表明start域已經標記過，把路由器Ri 的IP地址的第w.offset個分片放入end域，flags的值加1。如果flags=2，則表明數據包w的start、end域均已經標記過，直接將distance的值加1，轉發數據包。
標記算法[4]為：
2.4 重構過程
攻擊路徑重構的目標是建立一棵包含所有攻擊路徑拓撲信息的樹T, 重構的第一步是建立一個只包含根節點V的樹T。第二步根據每個節點與受害主機V的距離，把采樣到的邊插入到樹的結構之中，離各個攻擊源最近的路由器就是樹的各個葉子，最后檢查整棵樹，刪去與節點的距離d不等于distance的節點。該算法參考了參考文獻[4]。
重構算法為：
Algorithm 2. Reconstruction procedure at v
let T be a tree with root v
let an edge of T be a tuple (start,end,count)
let E be a two dimension array of the tuples
for each packet w
replace the fragment at offset w.offset of
E[w.distance][w.hash].start with w.start
Replace the fragment at offset w.offset of
E[W.distance][w.hash].end with w.end
increment E[w.distance][w.hash].count
end for
3 仿真試驗
為了測試本文方案的性能，通過模擬實驗比較了2種方案在路徑重構時所需要的數據包的數目，實驗數據利用CAIDA[5](Cooperrative Association for Internet Data Analysis)提供的跟蹤路由數據庫進行仿真攻擊試驗，如圖1所示，選取的攻擊路徑長度為1~30，每個長度進行1 000次試驗取平均值。
圖1橫坐標為路徑長度，縱坐標為重構路徑時所需的數據包數目。從圖1可以看出，在重構路徑時，本方案重組攻擊路徑所需的攻擊數據包的數量隨著攻擊路徑長度的增加而增加，但增加的速度卻隨著路徑長度的增加逐漸減小，與傳統的標記方法相比，傳輸路徑越長，本方案所需的數據包的個數就越具有優勢。因為需要的數據包數量比基本包標記少得多，計算量也會大大減少。所以本方案只需要少量數據包就可以在短時間內重構出攻擊路徑。
追蹤攻擊源是打擊網絡犯罪的必經階段，它不僅是查找攻擊者的重要手段，而且對提供網絡犯罪的證據也具有非常重要的作用，所以攻擊源追蹤技術引起了越來越多的重視。本文提出的算法能夠消除對數據包的重復標記問題，并顯著地減少反向追蹤攻擊源所需數據包的數目，提高了對攻擊源定位的追蹤準確性和實時性。但是要追蹤到真正的攻擊者，還有許多亟待解決的問題。例如攻擊源追蹤只能得到可疑攻擊路徑的集合、只能是近似的回溯、以及如何減少錯誤路徑還需要進一步的研究。
參考文獻
[1] SAVAGE S, WETHERALL D,KARLIN A, et al. Network support for IPtraceback[J]. ACM/IEEE Transactions on Networking,2001,9(3):226-237.
[2] 胡汗平，王凌斐，郭文軒，等.一次性可變概率分片標記及其壓縮標記[J].華中科技大學學報：(自然科學版)，2007，35(3):15-18.
[3] RICHARD S W，著.TCP/IP詳解—卷1：協議[M].范建華，胥光輝，張清，等譯.北京：機械工業出版社.2000.
[4] 梁豐，趙建新，DAVID Y.通過自適應隨機數據包標記實現實 時IP回溯[J].軟件學報，2003，14(05)：1000-9825.
[5] DAVID M. CAIDA cooperrative association for internet data analysis[EB/OL].http://www.caida.org.2004.