動態概率包標記算法分析及改進

孫連軍 趙文正 山東信息職業技術學院，山東 濰坊 261041

動態概率包標記算法分析及改進

孫連軍 趙文正 山東信息職業技術學院，山東 濰坊 261041

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

IP追蹤；包標記算法；動態概率包標記算法

引言

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

1.動態包標記算法的引入

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

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

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

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

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

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

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

2.動態概率包標記算法的介紹與分析

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

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

設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，

如果每個數據包最終被哪個路由器標記的概率都是相等的（為1/d）則由coupon collector問題[3]可知，重夠所需的數據包數最少。那么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]）時受害端重夠攻擊路徑所需的包的數目最少，所需的數據包平均值為d(1+1/2+…+1/d)，其期望值為d lnd 。這是理論上的最小值。在實際實現時的主要困難就是i值的確定。因為現在普遍的網絡路由協議是基于目的地的，當路由器傳送數據包時，它會在路由表中查找下一個最靠近目的地的路由器，這樣就可以以最短的路徑到達目的地。但同時也增加了數據包經過路由器的不確定性，所以i值也要適時確定。

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

從以上說明中可知，動態概率包標記算法路徑重構所需的數據包數為d lnd。

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

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

3.動態包標記算法的改進

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

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

對于當前路由器對經過的數據包

先計算數據包從源端到當前路由器經過的跳數i

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

執行標記操作對數據包進行標記

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

判斷數據包有否被標記，

若標記過則直接轉發；

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

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

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

4.總結

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

[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

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