動態(tài)概率包標(biāo)記算法分析及改進(jìn)

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

動態(tài)概率包標(biāo)記算法分析及改進(jìn)

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

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

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

引言

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

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

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

假定一攻擊路徑：S=（A，R1，R2，……Rd，V），其中A表示攻擊者，V表示受害者，攻擊路徑長度d表示攻擊路徑上的路由器數(shù)。若路由器以固定概率P 標(biāo)記數(shù)據(jù)包，攻擊規(guī)模即攻擊者發(fā)出的數(shù)據(jù)包數(shù)設(shè)為N。那么，我們可以得出以下結(jié)論：因為受害者要至少收到一個來自距離攻擊者最近的路由器標(biāo)記的數(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ù)級急劇增長。而要降低該值就要減小標(biāo)記數(shù)據(jù)包的概率，如此一來將增加不確定性因素（如攻擊者的偽造信息等）的影響從而降低重構(gòu)路徑的準(zhǔn)確性和時間效率。為了尋求一種更為可靠，效率更高的方法來彌補PPM的不足，Jenshiuh Liu提出了采用動態(tài)的標(biāo)記概率的動態(tài)概率包標(biāo)記算法。

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

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

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

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

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

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

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

……

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

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

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

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

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

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

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

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

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

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

3.動態(tài)包標(biāo)記算法的改進(jìn)

為了減小邊界路由器的負(fù)擔(dān)，我們提出以下改進(jìn)措施。

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

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

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

若i=1時，路由器標(biāo)記概率p=1/2

執(zhí)行標(biāo)記操作對數(shù)據(jù)包進(jìn)行標(biāo)記

若i=2時， 路由器標(biāo)記概率p=1/2

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

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

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

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

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

4.總結(jié)

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

[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ù)。