摘 要：提出了可避免數(shù)據(jù)包重復(fù)標(biāo)記的可變概率分片標(biāo)記算法。通過模擬試驗(yàn)對(duì)比該提出的算法和基本包標(biāo)記算法，結(jié)果表明該方法能夠消除對(duì)數(shù)據(jù)包的重復(fù)標(biāo)記問題，并顯著地減少反向追蹤攻擊源所需數(shù)據(jù)包的數(shù)目，提高了對(duì)攻擊源定位的追蹤的準(zhǔn)確性和實(shí)時(shí)性。
關(guān)鍵詞：重復(fù)標(biāo)記；可變概率；傳輸距離

　　DoS是Denial of Service的簡(jiǎn)稱，即拒絕服務(wù)。造成DoS的攻擊行為被稱為DoS攻擊，其目的是通過消耗遠(yuǎn)程計(jì)算機(jī)網(wǎng)絡(luò)資源來使Internet站點(diǎn)拒絕提供給合法用戶的服務(wù)。這種類型的攻擊實(shí)施簡(jiǎn)單、防御困難、危害極大，攻擊者的IP地址常常是經(jīng)過偽裝的。針對(duì)此類攻擊的特點(diǎn)，研究者提出了很多解決方法，例如包標(biāo)記、日志記錄、連接測(cè)試、ICMP追蹤、覆蓋網(wǎng)絡(luò)等。本文提出了可避免數(shù)據(jù)包重復(fù)標(biāo)記的可變概率分片標(biāo)記算法，減少路徑重構(gòu)時(shí)所需的數(shù)據(jù)包數(shù)目以及運(yùn)算時(shí)間，提高了對(duì)攻擊源定位的追蹤的準(zhǔn)確性和實(shí)時(shí)性。
1 相關(guān)研究工作
　　由Savage等人提出的概率包標(biāo)記算法BPPM，具有許多其他方法所不具有的優(yōu)點(diǎn)：(1)無需與ISP相互合作，避免了調(diào)試中高額的管理費(fèi)用；(2)無需增加巨大的網(wǎng)絡(luò)流量，可以跟蹤多種攻擊形式；(3)在攻擊停止后很久，仍然可以被用來分析登錄過程并制作用于跟蹤的數(shù)據(jù)包。(4)網(wǎng)絡(luò)路由器負(fù)載小。之后在BPPM的基礎(chǔ)上不斷產(chǎn)生出新的改進(jìn)算法，例如自適應(yīng)概率包標(biāo)記、高級(jí)包標(biāo)記和帶認(rèn)證的包標(biāo)記，以期減少路徑重構(gòu)時(shí)所需的數(shù)據(jù)包，重構(gòu)攻擊路徑時(shí)的誤報(bào)率，計(jì)算復(fù)雜度（時(shí)間復(fù)雜度）。
　　概率包標(biāo)記的思想[1]是路由器以固定的概率p標(biāo)記數(shù)據(jù)包，將路徑信息加入到IP頭中的16 bit識(shí)別域（ID）中，表示為（start，end，distance）。在路由器處產(chǎn)生一個(gè)[0,1]之間的隨機(jī)數(shù)，如果這個(gè)隨機(jī)數(shù)小于p，路由器將自己的IP填入到start，同時(shí)將distance賦值為0；否則將自己的IP地址填入到end中；如果路由器以概率1-p不對(duì)包標(biāo)記，則將distance值加1。受害者從這些數(shù)據(jù)包中提出路徑信息，重構(gòu)出攻擊路徑。
      假設(shè)每個(gè)路由器標(biāo)記數(shù)據(jù)包的概率為p，受害者從距離d（節(jié)點(diǎn)與受害者間路由器的個(gè)數(shù)）的路由器收集到被標(biāo)記的數(shù)據(jù)包的概率為p（1-p）^1-d。該函數(shù)是距離d的嚴(yán)格單調(diào)遞減函數(shù)，距離攻擊者越遠(yuǎn)的路由器的樣本越難被采集到，因此算法的時(shí)間主要集中在接收最遠(yuǎn)路由器提供樣本的時(shí)間上。例如，當(dāng)d=20、P=1/2時(shí)，受害者要收集到此路由器上的樣本必須要收到平均1 048 576個(gè)數(shù)據(jù)包。
　　它最主要的缺點(diǎn)是隨著路徑的增長，所需要數(shù)據(jù)包的數(shù)量成指數(shù)增長，并且存在數(shù)據(jù)包的重復(fù)標(biāo)記問題，距離攻擊者近的被標(biāo)記的數(shù)據(jù)包可能被下邊的路由器標(biāo)記，從而掩蓋曾經(jīng)被標(biāo)記過的信息，這就不可能很快地重構(gòu)路徑防御攻擊。
2 改進(jìn)的包標(biāo)記算法NRVPPM
　　本論文提出一種改進(jìn)的包標(biāo)記算法，在包頭中增加標(biāo)記位flags來避免數(shù)據(jù)包的重復(fù)標(biāo)記問題，并且使用等概率p=1/di，使受害者主機(jī)可等概率地收集到攻擊路徑中路由器標(biāo)記的數(shù)據(jù)包。
2.1標(biāo)記概率

2.2標(biāo)記格式
　　為了節(jié)省標(biāo)記存儲(chǔ)空間，不給用戶帶來過多的影響，算法使用IPv4中的16位標(biāo)識(shí)符字段（Identifer）[1]、1位閑置的標(biāo)志位（Flags）、13位片位移字段（據(jù)統(tǒng)計(jì)目前少于0.25%的數(shù)據(jù)包需要分片）[3]，以及一般很少使用的8位TOS（Type-of-Sevice），總共38位來存儲(chǔ)包標(biāo)記信息。標(biāo)記格式如表1所示。　            

　　把32位的start路由器的IP地址和32位end路由器地址分為4塊。在start和end子域以等概率放置IP地址的4個(gè)8 位的片段，并相應(yīng)地設(shè)置偏移offset子域值。
　　(1)flgs：如果flags=0，則表示數(shù)據(jù)包沒有被標(biāo)記過；flags=1，則start子域已被標(biāo)記過；flags=2，則start、end子域均被標(biāo)記過。flgs的初始位被置為0。
　　(2)start和end：用來存儲(chǔ)邊的信息。
　　(3)distance： 用5位的distance來記錄數(shù)據(jù)包開始發(fā)送的路由器開始經(jīng)過的跳數(shù)。distance的初始值被置為0。
　　(4)offest：用2位來記錄start和end的4個(gè)偏移。
　　(5)hash：hash(IP)取其后13位。
2.3 標(biāo)記過程
　　把32位的start路由器的IP地址和32位end路由器地址分為4塊，在start和end子域以等概率放置IP地址的4個(gè)8 bit的片段，并相應(yīng)地設(shè)置偏移offset子域值。路由器以概率p=1/d對(duì)數(shù)據(jù)包w進(jìn)行標(biāo)記。在路由器Ri 處，讓x為[0,1]之間的隨機(jī)數(shù)，y為[0,3]之間的隨機(jī)數(shù)，如果x<p，(a)當(dāng)flags=0時(shí)，則把路由器Ri 的IP地址的第y個(gè)分片放入start域，distance域置為0；(b)當(dāng)flags=1時(shí)，則表明start域已經(jīng)標(biāo)記過，把路由器Ri 的IP地址的第w.offset個(gè)分片放入end域，flags的值加1。如果flags=2，則表明數(shù)據(jù)包w的start、end域均已經(jīng)標(biāo)記過，直接將distance的值加1，轉(zhuǎn)發(fā)數(shù)據(jù)包。
　　標(biāo)記算法[4]為：
　

2.4 重構(gòu)過程
　　攻擊路徑重構(gòu)的目標(biāo)是建立一棵包含所有攻擊路徑拓?fù)湫畔⒌臉銽, 重構(gòu)的第一步是建立一個(gè)只包含根節(jié)點(diǎn)V的樹T。第二步根據(jù)每個(gè)節(jié)點(diǎn)與受害主機(jī)V的距離，把采樣到的邊插入到樹的結(jié)構(gòu)之中，離各個(gè)攻擊源最近的路由器就是樹的各個(gè)葉子，最后檢查整棵樹，刪去與節(jié)點(diǎn)的距離d不等于distance的節(jié)點(diǎn)。該算法參考了參考文獻(xiàn)[4]。
　　 重構(gòu)算法為：
　　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 仿真試驗(yàn)
　　為了測(cè)試本文方案的性能，通過模擬實(shí)驗(yàn)比較了2種方案在路徑重構(gòu)時(shí)所需要的數(shù)據(jù)包的數(shù)目，實(shí)驗(yàn)數(shù)據(jù)利用CAIDA[5](Cooperrative Association for Internet Data Analysis)提供的跟蹤路由數(shù)據(jù)庫進(jìn)行仿真攻擊試驗(yàn)，如圖1所示，選取的攻擊路徑長度為1~30，每個(gè)長度進(jìn)行1 000次試驗(yàn)取平均值。

　　圖1橫坐標(biāo)為路徑長度，縱坐標(biāo)為重構(gòu)路徑時(shí)所需的數(shù)據(jù)包數(shù)目。從圖1可以看出，在重構(gòu)路徑時(shí)，本方案重組攻擊路徑所需的攻擊數(shù)據(jù)包的數(shù)量隨著攻擊路徑長度的增加而增加，但增加的速度卻隨著路徑長度的增加逐漸減小，與傳統(tǒng)的標(biāo)記方法相比，傳輸路徑越長，本方案所需的數(shù)據(jù)包的個(gè)數(shù)就越具有優(yōu)勢(shì)。因?yàn)樾枰臄?shù)據(jù)包數(shù)量比基本包標(biāo)記少得多，計(jì)算量也會(huì)大大減少。所以本方案只需要少量數(shù)據(jù)包就可以在短時(shí)間內(nèi)重構(gòu)出攻擊路徑。
　　追蹤攻擊源是打擊網(wǎng)絡(luò)犯罪的必經(jīng)階段，它不僅是查找攻擊者的重要手段，而且對(duì)提供網(wǎng)絡(luò)犯罪的證據(jù)也具有非常重要的作用，所以攻擊源追蹤技術(shù)引起了越來越多的重視。本文提出的算法能夠消除對(duì)數(shù)據(jù)包的重復(fù)標(biāo)記問題，并顯著地減少反向追蹤攻擊源所需數(shù)據(jù)包的數(shù)目，提高了對(duì)攻擊源定位的追蹤準(zhǔn)確性和實(shí)時(shí)性。但是要追蹤到真正的攻擊者，還有許多亟待解決的問題。例如攻擊源追蹤只能得到可疑攻擊路徑的集合、只能是近似的回溯、以及如何減少錯(cuò)誤路徑還需要進(jìn)一步的研究。
參考文獻(xiàn)
[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] 胡汗平，王凌斐，郭文軒，等.一次性可變概率分片標(biāo)記及其壓縮標(biāo)記[J].華中科技大學(xué)學(xué)報(bào)：(自然科學(xué)版)，2007，35(3):15-18.
[3] RICHARD S W，著.TCP/IP詳解—卷1：協(xié)議[M].范建華，胥光輝，張清，等譯.北京：機(jī)械工業(yè)出版社.2000.
[4] 梁豐，趙建新，DAVID Y.通過自適應(yīng)隨機(jī)數(shù)據(jù)包標(biāo)記實(shí)現(xiàn)實(shí) 時(shí)IP回溯[J].軟件學(xué)報(bào)，2003，14(05)：1000-9825.
[5] DAVID M. CAIDA cooperrative association for internet data analysis[EB/OL].http://www.caida.org.2004.