一種多層次的追蹤器部署策略

摘 要:結合K-剪枝算法，提出了一種多層次追蹤器部署策略，在第一層的追蹤器部署時選擇較大的k值進行剪枝，以較小的改造代價部署相對較少的追蹤器，來進行關鍵追蹤，在第二層通過二次剪枝，以部署剪枝域內追蹤器，對無法通過第一層次節點進行追蹤的攻擊進行再次追蹤，確定攻擊來源。該方案能夠以較低的網絡改造代價以及網絡性能代價完成準確追蹤。理論分析以及仿真結果驗證了該方案的正確性和有效性。

關鍵詞:分布式拒絕服務攻擊; 追蹤器; 數據包標記; 剪枝

中圖分類號:TP393.08 文獻標志碼:A

文章編號:1001-3695(2010)03-1039-03

doi:10.3969/j.issn.1001-3695.2010.03.064

Multi-layer tracer deployment scheme

XU Jin-songa，b

(a.Tongda College， b.College of Computer Science， Nanjing University of Posts Telecommunications， Nanjing210003， China)

Abstract:This paper proposed a multi-layer tracer deployment schemewith the K-diameter algorithm. In the scheme， chosen a larger k-could to value diameter tracer deployment at the first layer. As a result， needed less cost to deploy comparatively few tracers for the sake of conducting the pivotal tracing. The second diameter at the second layer was to deploy tracers in the area of diameter. Could confirmed the source of attack thus by tracing again the attacks which couldn’t be traced at the first layer node. The scheme could trace accurately with lower costs of network transformation and network performance. The theoretical analyses and the simulations verified the scheme is correct and valid.

Key words:distributed denial of service attacks (DDoS); tracer; packet marking(PM); diameter

0 引言

分布式拒絕服務攻擊(denial of service attacks/distributed denial of service attacks， DoS/DDoS)的攻擊者能夠輕易偽造源IP地址，使得對該攻擊所進行的源地址追蹤成為DoS/DDoS防御中一個難以解決的問題。如何找出真正的攻擊者，即IP追蹤(IP traceback)問題，成為當前Internet安全領域一個比較活躍的課題。

數據包標記(packet marking，PM)是目前引起最廣泛關注的追蹤技術，它是指路徑上的路由器節點對轉發的數據包加上本站的地址標記，通過從收到的攻擊包中收集和分析這些標記，受害主機可以復原出該數據包的傳輸路徑。這種方法的前提是網絡中的所有路由器都可以支持數據包標記的算法(本文中將這些路由器稱為追蹤器(tracer))。實際上，在2005年5月所收集到的路由器數目高達192 244個[1]，在實際的網絡中不可能花費巨大的資金和時間成本將這些路由器全部更換為追蹤器。因此，需要一種有效的方法指導實際網絡中追蹤器的部署問題。

1 相關研究

目前，針對DoS/DDoS攻擊源追蹤方案的研究中都是利用路由器來進行追蹤。文獻[2]在邊界路由器上實現確定包標記(deterministic packet marking，DPM)方法，可能由于攻擊產生于骨干網而不經過追蹤器而難以追蹤。由Savage等人[3]提出的概率包標記(probabilistic packet marking，PPM)方法，專注與如何降低重組攻擊路徑所需收集的數據報的數量以及降低誤報等方面:文獻[4]根據路由器統計信息降低數據報被重新標記的概率;文獻[5]使用TTL信息加速數據報重構路徑并減少重構路徑發生錯誤;文獻[6]提出使用概率模型的方法降低重構路徑所需數據報數量;文獻[7]使用著色的方法降低需要的編碼數量，并提出了2-tier的追蹤架構。這些方法雖然允許部署部分追蹤器，但是即使在部署的節點超過總節點數一半的情況下，也可能因為攻擊包沒有經過任何一個追蹤器而很難有效追蹤到攻擊來源。

為了解決追蹤器的部署問題，Wang等人[8]提出了一種追蹤部署的策略來防御DDoS攻擊，使用K-剪枝算法滿足在部分網絡節點部署追蹤器的情況下，保證一個IP數據包傳遞路徑超過k跳時，必定經過一個路由器。文獻[9]更是基于這種算法與著色包標記算法的基礎上作了一些改進，以降低重構路徑的數據包數和誤報率。

然而在這種算法中，無法檢測到攻擊的概率仍然存在，并與k值的選取相關。追蹤器的數量隨著k值變大而減少，會使得無法檢測到攻擊行為的概率上升。而且k值越大，則刪除追蹤器節點后的連通子圖中的節點數也越大，配合使用其他檢測方法需要的代價也就越大。本文正是基于這樣的考慮，提出了一種分層次的追蹤器部署方案，以較低的代價標記數據包進行追蹤，并保證追蹤器的部署能夠有效追蹤到攻擊行為。

2 策略描述

在Wang等人提出的追蹤器部署策略中，當攻擊者到受害者(victim)之間的路徑沒有經過任何一個部署了追蹤器的路由器的概率仍然存在，這里將一個被追蹤器包圍的連通子域稱為剪枝域(diameter area)。這個域包含的節點數目與k值的選取相關，也與K-剪枝算法的特點相關。為了對發生在剪枝域中的攻擊行為進行追蹤，可以針對節點數過多的域再部署一些追蹤器。由于K-剪枝算法求出的部署方案已經被證明是一個NP完全問題[8]，直觀的做法就是在這些剪枝域內再進行一次更小k值的K-剪枝以部署內部的追蹤器。

2.1 IP數據報頭編碼方案

由于數據包在途中經分段(fragment)處理的情況是很少出現的(不超過0.25%)，IP頭中的標志號(identification)域也很少使用，于是Savage等人建議將路徑信息寫入到16 bit的標志號域中。文獻[3]指出服務類型(type of services， TOS)域也可以用來作為路由標記使用。在分段包標記算法(fragment marking scheme， FMS)[3]、高級包標記算法(advanced marking scheme， AMS)[10]以及一些改進方案中，都有一個距離(distance)域，用來表示標記數據包的路由器與受害者之間的距離。文獻[5]建議使用生存時間(time to live， TTL)域代替distance域，以節省更多的空間存儲路由器的信息。路徑重構時，受害者對具有相同距離信息的標記嘗試可能的組合[3]。

使用1 bit的TOS域來作為標記編號(偏移值)。加上identification域與TTL域，整個利用的IP數據包頭中的長度為25 bit。具體編碼格式如圖1所示。

它們的分布和作用如下:

a)標記(MID:marking identification，0≤MID≤1)。1 bit，用于記錄IP信息所屬的范圍。

b)路由器IP地址信息(IP fragment)。16 bit，用于記錄路由器IP標記的信息。

c)路由器與受害者的路由距離(distance)。8 bit，直接使用TTL值來標志距離。

當路由器決定對數據包進行標記時，首先查找路由器的轉發表，根據數據報從哪一個網絡接口進入路由器，將變數i(0≤i≤1)寫入MID位。當數據報來自于鄰接的路由器時，標記為1;當數據報來自于本地時，標記為0，距離則用TTL來代替。假設路由器知道數據報的目的距離為d，只要將d值的兩倍寫入TTL即可。若之后的路由器都沒有再對該數據報進行標記，則都會對TTL減去1。當被標記的數據報抵達受害者時，TTL的值正好顯示受害者與標記路由器的距離信息。

2.2 網絡模型和定義

為了描述追蹤器部署算法以及追蹤的方法，定義如下:

定義1 記網絡G=(V，E)是一個全連通的無向圖。其中:V為頂點(vertex)或節點(node)的集合;E為邊(edge)的集合。

定義2 記d(u，v)是圖形G中從u到v的最短路徑長度;否則d(u，v)=∞。

定義3 記頂點集合V′V為割點集，則G-V′將不再連通。

定義4 記頂點v與u的最長距離e(v)=max{d(u，v)，u∈V}為圖形G中頂點v的離心率(eccentricity)。

定義5 記圖形G的半徑為γ(G)=min(e(v));反之記diam(G)=max(e(v))為其直徑。

定義6 若圖形G中存在頂點v有e(v)=γ(G)，則記該頂點v為圖形G的中心點c;記中心點的集合為C。

定義7 若圖形G中刪除邊e并將e連接的兩個頂點合并為一個新頂點，則稱為圖形收縮(contracted)。若圖形G對所有可以收縮的邊進行收縮，所得到的圖形成為收縮子圖。

定義8 若圖形G中頂點子集SV，且v∈S兩兩互不相鄰，則稱S為獨立集。

定義9 記頂點v的度數(degree)為d(v)，指與頂點v相關聯的邊的條數。

定義10 記頂點v相鄰頂點的集合為P(v)={u∈V|d(v，u)=1}。

定義11 記用K-剪枝算法分割出的剪枝域(diameter area)為Gd，記算法得出的割點集為T，記剪枝域連通子圖的節點數為numG。

2.3 多層次的追蹤器部署算法

多層次的追蹤器部署算法的目的是為了在圖G中設法找出最少的節點數來部署追蹤器，使得網絡滿足無論攻擊者來自于網絡何方，攻擊數據報都會經過一個追蹤器，或者保證攻擊源經過的第一個追蹤器一定在k跳之內。首先使用K-剪枝算法對網絡拓撲圖進行分割，第一次分割后產生數個剪枝域，如果這些剪枝域中節點的數目超過設定的值σ，則對該剪枝域再用K-剪枝算法進行分割，其中兩次選取的k值第一次可以較大，第二次選取的k值要比第一次選取的k值小。算法偽代碼描述如下:

/*多層次的追蹤器部署，輸入拓撲圖，輸出一個多層次的追蹤器部署節點集T*/

/*以i作為層次的標記*/

i←0Gi←G

validate1 : /*選自一個合適的k值并進行剪枝*/

/*輸入全連通的無向拓撲圖，輸出本層追蹤器部署節點集Ti*/

Ti←ifk=1then

/*當k=1時，使用貪心算法求出獨立集S*/

/*輸出該層的部署節點集Ti*/

S←

validate2 :ifGi≠then

for wholeVsearchvwhend(v)=min d(u)，u∈V Gi←Gi-P(v)∪{v}S←S+{v}

goto validate2

else break

Ti←V-S

returnTi

else /*當k≠1時，進行剪枝*/

validate3:C← for wholeVcounte(v)，v∈V

ife(v)=γ(G)thenC←C+{v}

selectc∈C/*任選一個中心點*/

ifk mod 2=1thenW←{v∈V|d(v，c)≤(k-1)/2}

else W←{v∈V|d(v，c)≤(k-1)/2」}Y←{v∈V|d(v，c)≤(k-1)/2」+1}

validate4:ifY≠then

selectvy∈Y/*任選一個頂點*/

Y←Y-{vy}ifdiam(GW∪{vy})

goto validate4

elsebreak

contractGWto a pointvwgetG*/*G*是收縮后的連通圖*/

Ti←Ti+{u∈V|d(u，vw)=1}G′←G*-Ti-{vw}/*G′是刪除中心點以及追蹤器的子圖集合*/

for each subplotGsG′/*對每一個子圖進行剪枝*/

ifdiam(Gs)≥kthen

goto validate3

elsebreakreturnTi

G′′←Gi-Ti/*刪除追蹤器形成剪枝域集合*/

i←i+1 for each diameter subplotG′i/*針對每一個剪枝域的節點數進行運算*/

ifnumG′i>σ，G′iG′′thenGi←G′i

goto validate1

elsebreak

該算法與文獻[10]提出的算法最大的不同是可以在上一層次的追蹤器部署時選擇較大的k值進行剪枝，有效降低了追蹤器部署的數量。網絡拓撲被第一層的追蹤器T0劃分為數個剪枝域。平時第一層的追蹤器只要以極低的概率對經過的數據報進行標記，當受害者發現攻擊行為時，才要求下層的追蹤器進行追蹤。k=3時第一層剪枝的范例如圖2所示。

3 數據報來源追蹤

3.1 來源追蹤算法

當受害者發現有攻擊行為時，會對來源的數據報進行分析。數據報所標記的信息包含追蹤器的地址以及MID值。當MID值為0時，表示數據報來自于追蹤器的本地網絡。這時只要配合使用其他工具就可以對攻擊源進行定位。當MID值為1時，表示數據報可能來自于其他路由器。一般情況下，可以保證該數據報應該是在路由器鄰接的剪枝域。雖然標記方法是以概率的方式標記數據報，事實上被標記過的數據報可以通過一定的方法避免被再次標記。假設數據報是按照最短路徑的順序進行傳遞，基于路由器知道數據報的目的距離。當被標記過的數據報經過另一個追蹤器時，該追蹤器可以通過2d-TTL的值判定該值是否在其他追蹤器距離的范圍內。如果落在該距離范圍內，則表示該數據報已經過其他追蹤器。

再回到圖2，追蹤器N進行數據報標記前，會先判斷數據報的來源。如果是本地網絡，則標記MID值為0，并進行地址與距離的標記動作。假如數據包是從interface1、interface2、interface3上過來，首先根據目的地址的距離d與收到數據報的TTL值，求出f(d)=2d-TTL。由于追蹤器N知道鄰接追蹤器I、G、M、R的距離Th={2，3，4}，只要判定f(d)是否落在Th之內，就可以判定出數據報是否被標記過，也就是說已經過其他追蹤器，否則數據報來自于鄰接的剪枝域內。當受害者判定攻擊者來自于剪枝域內，就會發起下一層的追蹤器進行追蹤。如果下一層沒有部署追蹤器時，就需要對剪枝域進行線性查找，直到找到攻擊源為止。追蹤算法的偽代碼如下:

/*受害者檢測到攻擊并發起追蹤*/

i←0

validate:ifMID=0thenfind attack source

elsei←i+1/*call the tracer awake PM ofilevel*/

ifTi=then

find attack source by liner search

elsePM with highly probability byilevel tracer

goto validate

當受害者收到攻擊數據報后，會使用概率包標記的一般方法先重構路徑，以找到距離最遠的追蹤器，并認為該攻擊數據報來自于該追蹤器或該追蹤器相鄰的剪枝域內。追蹤器根據數據報發送的網絡接口判斷是來自于追蹤器本地網絡還是剪枝域。如果來自本地網絡，直接找到攻擊源;如果來自于剪枝域(該域由網絡接口直接判斷)，首先查找下層有沒有部署追蹤器。如果沒有部署，則有必要作線性查找;否則通知下一層的追蹤器以較高的概率標記數據報，以查找攻擊源。這里有一種特殊的情況存在，就是攻擊源與受害者都落在同一個剪枝域內，這時候受害者需要通知本剪枝域鄰接的追蹤器發起本域內的追蹤。

3.2 追蹤成本分析

系統進行追蹤的成本主要體現在攻擊發生后進行搜索產生的數據成本。

當數據報直接來自于追蹤器，在本方案中無須進行其他工作，可以直接找到攻擊源，因此認為無須定義追蹤成本。當攻擊者落在剪枝域中，若是單層剪枝或剪枝域內沒有部署此層的追蹤器，則搜索成本定義為:對剪枝域內網絡節點作線性搜索的數量;當此層有追蹤器存在，額外的追蹤成本需要定義為:攻擊者所在的剪枝域鄰接路由器與受害者的距離(通知成本)及該剪枝域的直徑長度(廣播成本)。

4 系統仿真

為了測試該方案的性能，實驗數據采用了從CAIDA[1]獲得的真實因特網數據。實驗中取平均度數D=4和D=6兩種情況分別對需要部署的追蹤器數量與單層結構的追蹤器部署進行比較。實驗中剪枝參數分別選為K=3，K1=5，K2=3，σ=0，K1=5，K2=3，σ=20，K1=7，K2=3，σ=0，K1=7，K2=3，σ=20來比較它們所需要部署的追蹤器數量以及查找的成本。圖3為需要部署的追蹤器數量的比較。

圖3顯示，使用單層追蹤部署方案，設定剪枝值k=3和多層部署時與多層追蹤部署方案中設定剪枝值k1=7，k2=3，σ=20所需要部署的追蹤器數目并沒有太大

差距。但是值得注意的是，在多層部署方式下，由于平時只有第一層節點在進行標記動作，對于網絡的效率影響較小，系統成本比較低。圖4是各種部署方案下追蹤器響應追蹤時追蹤成本的比較。

從圖4看出，多層架構的追蹤器部署方案在響應查找時會有通知以及廣播成本存在。但是由于部署的方案在平時不作追蹤時需要動作的追蹤器較少，也對系統性能造成的影響較小。

5 結束語

本文提出了一種使用多層次的方式對網絡中的攻擊源追蹤進行部署的方案。理論分析與實驗結果表明，改進后的方案可以使網絡以較小的改造代價部署相對較少的追蹤器來進行攻擊源的追蹤。在以后的工作中，如何設計一個較好的追蹤算法以配合該部署方案進行追蹤仍然是一個重點，并且在標記方案上，除了需要設計一個完善的標記方法外，如何有效壓縮標記信息的大小也需要仔細斟酌。

參考文獻:

[1]CAIDA. Skitter[EB/OL].http://www.caida.org/tools/measurement/skitter/router_topology/.

[2]BELENKY A， ANSARI N.IP traceback with deterministic packet marking[J].Communications Letters， 2003， 7(4):162-164.

[3]SAVAGE S， WETHERALL D，KARLIN A， et al.Network support for IP traceback[J].ACM/IEEE Trans on Networking，2001， 9(3) :226-237.

[4]SOZAKI H， ATA S，OKA I， et al. Performance improvement on probabilistic packet marking by using history caching[C]//Proc of the 6th Asia-Pacific Symposium on Information and Telecommunication Technologies.2005:381-386.

[5]YAAR A， PERRIG A，SONG D. FIT: fast Internet traceback[C]//Proc of the 24th Annual Joint Conference of the IEEE Computer and Communications Societies. 2005:1395-1406.

[6]LIU Wu， DUAN Hai-xin， LI Xing.Improved marking model ERPPM tracing back to DDoS attacker[C]//Proc of the 3rd International Conference on Information Technology and Applications.2005:759-762.

[7]MUTHUPRASANNA M，MANIMARAN G，ALICHERRY M，et al. Coloring the Internet: IP traceback[C]//Proc of the 12th International Conference on Parallel and Distributed Systems.2006:12-15.

[8]WANG C H， YU C W， YU K M et al. Tracers placement for IP traceback against DDoS attacks[C]//Proc of International Conference on Communications and Mobile Computing.2006.

[9]劉淵， 陳彥， 李秀珍.基于追蹤部署的著色包標記算法的研究[J].計算機應用研究，2008， 25(10):3102-3104.

[10]SONG D X， PERRIG A.Advanced and authenticated marking schemes for IP traceback[C]//Proc of the 20th Annual Joint Conference of Computer and Communition Societies.2001:878-886.