孫連軍 趙文正 山東信息職業(yè)技術(shù)學院，山東 濰坊 261041

動態(tài)概率包標記算法分析及改進

孫連軍 趙文正 山東信息職業(yè)技術(shù)學院，山東 濰坊 261041

IP追蹤技術(shù)是防御拒絕服務攻擊的一個研究熱點。本文對IP追蹤中的動態(tài)概率包標記算法進行了介紹和分析，在總結(jié)其優(yōu)點的同時也發(fā)現(xiàn)其存在不足。針對動態(tài)概率包標記算法使得距離攻擊者最近的邊界路由器的標記負載太大的不足提出了一個可行性改進方案，經(jīng)對比分析效果明顯。

IP追蹤；包標記算法；動態(tài)概率包標記算法

引言

拒絕服務攻擊一直以來就是網(wǎng)絡安全領(lǐng)域中非常嚴峻的問題， IP追蹤技術(shù)是防御拒絕服務攻擊技術(shù)研究中的一個熱點，又稱為IP 回溯（IP traceback）技術(shù)，即通過對攻擊路徑的逆向還原確定攻擊者的正確位置。不言而喻，在攻擊的發(fā)起端或愈靠近發(fā)起端的位置實施對攻擊行為的制止是最為有效的。所以對IP追蹤技術(shù)的研究得到了業(yè)內(nèi)人士的廣泛關(guān)注。IP追蹤技術(shù)有很多種，如：入口過濾，洪泛淹沒，ICMP標記等。目前研究的主要方向之一是基于Savage[1]等提出的一種被稱為概率包標記（Probabilistic Packet Marking，PPM）思想的數(shù)據(jù)包采樣標記技術(shù)。 Jenshiuh L i u[2]等提出的動態(tài)概率包標記算法（Dynamic Probabilistic Packet Marking，DPPM）被認為是目前最優(yōu)秀的方案之一，本文對其進行了全面的分析，并提出建設(shè)性改進意見。

1.動態(tài)包標記算法的引入

Savage等人創(chuàng)新性地提出了包標記算法的思想，為IP追蹤問題的研究開辟了一個嶄新的方向。包標記算法的思想是：在路由器轉(zhuǎn)發(fā)數(shù)據(jù)包的過程中，路由器以一定的概率將其地址信息標記到數(shù)據(jù)包中，受害者會收到大量來自于攻擊者的數(shù)據(jù)包。當受害者收到這些數(shù)據(jù)包并從中獲得足夠的路徑信息時，即可重構(gòu)出攻擊性數(shù)據(jù)包所經(jīng)過的路徑。該方案具有開創(chuàng)性的意義，也具有管理開銷小、不需ISP（網(wǎng)絡服務提供商）參與、不增加網(wǎng)絡流量，同時對單個攻擊源的定位非常準確等優(yōu)點。但是也存在很多缺陷，由于路由器以固定概率標記數(shù)據(jù)包，距離受害者較遠的路由器的標記信息會被后繼路由器的標記覆蓋，這樣受害者要收集到足夠信息需要的數(shù)據(jù)包數(shù)會隨著攻擊路徑長度的增大而大量增加，耗用時間更長，同時不確定性因素增加，導致誤報率和漏報率提高。

假定一攻擊路徑：S=（A，R1，R2，……Rd，V），其中A表示攻擊者，V表示受害者，攻擊路徑長度d表示攻擊路徑上的路由器數(shù)。若路由器以固定概率P 標記數(shù)據(jù)包，攻擊規(guī)模即攻擊者發(fā)出的數(shù)據(jù)包數(shù)設(shè)為N。那么，我們可以得出以下結(jié)論：因為受害者要至少收到一個來自距離攻擊者最近的路由器標記的數(shù)據(jù)包，即：

NP(1-P)(d-1)=1 （1）

可以得出重夠攻擊路徑所需數(shù)據(jù)包的期望值為：

lnd/P(1-P)(d-1)（2）

俄羅斯專家表示，歐盟《機器人民事法律規(guī)則》里專設(shè)了“機器人憲章”，規(guī)定了機器人設(shè)計和研發(fā)過程中必須遵守的基本倫理原則，制定了機器人工程師道德行為守則，以及設(shè)計師的“許可”制度和用戶“許可”制度。這些都是俄羅斯在立法時需要參照的范本。

從公式2中我們可以看出，隨著攻擊路徑長度的增加，重夠攻擊路徑所需的攻擊包的數(shù)目會承指數(shù)級急劇增長。而要降低該值就要減小標記數(shù)據(jù)包的概率，如此一來將增加不確定性因素（如攻擊者的偽造信息等）的影響從而降低重構(gòu)路徑的準確性和時間效率。為了尋求一種更為可靠，效率更高的方法來彌補PPM的不足，Jenshiuh Liu提出了采用動態(tài)的標記概率的動態(tài)概率包標記算法。

2.動態(tài)概率包標記算法的介紹與分析

動態(tài)概率包標記算法不再采用固定不變的概率采樣數(shù)據(jù)包進行標記，而是根據(jù)攻擊包所經(jīng)過的路由器跳數(shù)即距離攻擊者的距離來動態(tài)確定標記概率的值。并且距離攻擊者越近，路由器的標記概率越大。并隨著與攻擊者距離的增大而逐漸減小。

動態(tài)概率包標記算法的理論根據(jù)是：假設(shè)從攻擊者到受害者的距離為d（即攻擊者到受害者之間經(jīng)過d個路由器），從攻擊者到受害者之間的路由器依次為R1，R2，……Rd。

設(shè)pi為路由器Ri的標記概率

包只在第一個路由器處被標記的概率為p1(1-p2)(1-p3)…(1-pd-1)(1-pd)，

包只在第二個路由器處被標記的概率為 p2(1-p3)(1-p4)…(1-pd-1)(1-pd),

包只在第三個路由器處被標記的概率為p3(1-p4)(1-p5)…(1-pd-1)(1-pd)，

……

包只在第d-2個路由器處被標記的概率為pd-2(1-pd-1)(1-pd)，

包只在第d-1個路由器處被標記的概率為pd-1(1-pd)，

包只在第d個路由器處被標記的概率為pd，

如果每個數(shù)據(jù)包最終被哪個路由器標記的概率都是相等的（為1/d）則由coupon collector問題[3]可知，重夠所需的數(shù)據(jù)包數(shù)最少。那么pd=1/d，并有以上各式可以推導得出：

pd=1/d，pd-1=1/(d-1)，pd-2=1/(d-2),……，p2=1/2，p1=1

由coupon collector 理論可知，當取這樣的變概率1/i（i∈[1，d]）時受害端重夠攻擊路徑所需的包的數(shù)目最少，所需的數(shù)據(jù)包平均值為d(1+1/2+…+1/d)，其期望值為d lnd 。這是理論上的最小值。在實際實現(xiàn)時的主要困難就是i值的確定。因為現(xiàn)在普遍的網(wǎng)絡路由協(xié)議是基于目的地的，當路由器傳送數(shù)據(jù)包時，它會在路由表中查找下一個最靠近目的地的路由器，這樣就可以以最短的路徑到達目的地。但同時也增加了數(shù)據(jù)包經(jīng)過路由器的不確定性，所以i值也要適時確定。

Jenshiuh Liu提出的思想是：利用IP報文頭部的T T L域的信息來確定當前的i值。他們統(tǒng)計了目前存在的不同操作系統(tǒng)和協(xié)議的T T L的初始值是這樣一個集合{32，64，126，255}。所以可以根據(jù)當前的TTL值和路徑長度不會大于25的結(jié)論[4]判斷其初始值，從而計算出i值。如當前TTL為49那么其初始值只能為64，那么可以計算出i值為64-49=15。

從以上說明中可知，動態(tài)概率包標記算法路徑重構(gòu)所需的數(shù)據(jù)包數(shù)為d lnd。

因為所需包數(shù)最少，這樣重夠時間也最短。另外因為TTL初始值是由操作系統(tǒng)和協(xié)議決定的，不會被攻擊者篡改，提高了標記信息的準確性。

雖然動態(tài)概率包標記算法有諸多優(yōu)勢，但也存在不足。因為路由器標記數(shù)據(jù)包的概率為1/i（i∈[1，d]），所以在靠近攻擊者端，尤其是邊界路由器的標記概率為100%。邊界路由器要對所有轉(zhuǎn)發(fā)的數(shù)據(jù)包進行標記，這導致路由器的負擔過重。如果該處網(wǎng)絡流量太大，會導致網(wǎng)絡涌塞甚至路由器服務癱瘓。為了彌補D P P M的不足，本文提出以下改進方案。

3.動態(tài)包標記算法的改進

為了減小邊界路由器的負擔，我們提出以下改進措施。

邊界路由器上的標記概率定為50%，而在邊界路由器的下一條路由器上執(zhí)行標記算法時，首先判斷是否已被標記，從而避免覆蓋邊界路由器的標記信息。如圖1所示，實際上就是對經(jīng)過邊界路由器的數(shù)據(jù)包進行了分流，當然“分流”指的是對標記負載的分擔。這樣從標記結(jié)果和時間效率上并沒有折損，但卻使邊界路由器的標記負擔減少了50%。具體算法如下：

對于當前路由器對經(jīng)過的數(shù)據(jù)包

先計算數(shù)據(jù)包從源端到當前路由器經(jīng)過的跳數(shù)i

若i=1時，路由器標記概率p=1/2

執(zhí)行標記操作對數(shù)據(jù)包進行標記

若i=2時， 路由器標記概率p=1/2

判斷數(shù)據(jù)包有否被標記，

若標記過則直接轉(zhuǎn)發(fā)；

若沒有被標記則安p=1/2執(zhí)行標記操作

i大于2時，路由器標記概率p=1/i執(zhí)行標記操作

根據(jù)我們分析，改進后的算法使邊界路由器的標記負載減小了50%，但是其作為發(fā)現(xiàn)攻擊的第一個效應點的作用絲毫未減，下面我們在同樣的攻擊環(huán)境下對各算法中路由器的標記負載進行了比較。設(shè)攻擊路徑長度為25，攻擊者發(fā)出的數(shù)據(jù)包數(shù)為100，000，PPM算法的標記的標記概率為0.35。那么三種方案中各節(jié)點路由器的標記負載如圖2所示。

4.總結(jié)

本文介紹了ip追蹤技術(shù)研究的主要方向之一：包標記算法，并對一優(yōu)秀算法——動態(tài)概率包標記算法進行了說明分析。動態(tài)概率包標記算法大大減少了重夠路徑所需要的攻擊包的數(shù)目，提高了ip追蹤的時間效率同時也大大提高了追蹤的準確性。我們通過分析還發(fā)現(xiàn)其存在不足之處，即在距離攻擊者最近的邊界路由器的標記負載太大。我們給出了一個改進的方案，從三種算法的對比圖中可以看出我們的算法的效果是相當明顯的。

[1]Stefan Savage, David Wetherall, Anna Karlin and Tom Anderson. Practical Network Support for IP Traceback. Department of Computer Science and Engineering. University of Washington Seattle, WA, USA , 2000

[2] Jenshiuh Liu,Zhi-jian Lee,Yeh_Ching Chung. Dynamic probabilistic packet marking for efficient IP traceback. Department of Information Engineering and Computer Science,Feng-Chia University,Taichung 407,Taiwan,ROC,Departmen of Computer Science,National Tsing Hua University,Hsingchu 300,Taiwan,ROC. 2006.6

[3] W. Theilmann, K. Rothermel, Dynamic distance maps of the Internet, in: Proceedings of the 2000IEEE INFOCOM Conference, March 2000.

[4] Sariel Har-Peled The Occupancy and Coupon Collector problems, November 598shp -Randomized Algorithms. 2005

Analyses And Amelioration To The Dynamic Probabilistic Packet Marking Algorithm

Sun Lianjun Zhao Wenzheng (Shandong College Of Information Technology, Shandong Weifang 261041)

The IP traceback approach is a very effective method to identify DoS attackers. The dynamic probabilistic packet marking algorithm is introduced and analyzed. As its excellent performance knowing we find it some shortage. A improved algorithm is proposed to solve the problem that the routers nearest to the attackers have a heavy load on marking packets. And the improvement is proved to be in effect.

TP393

A

10.3969/j.issn.1001-8972.2011.13.042

孫連軍，男，副教授，研究方向：計算機動畫設(shè)計，計算機通信技術(shù)。