基于追蹤部署的著色包標(biāo)記算法的研究

 收稿日期：2008-01-14；

修回日期：2008-03-25

基金項(xiàng)目：國防基礎(chǔ)研究基金資助項(xiàng)目（A1420061266）



作者簡介：劉淵(1967-)，男，教授，碩導(dǎo)，主要研究方向?yàn)榫W(wǎng)絡(luò)安全及網(wǎng)絡(luò)信息系統(tǒng)；

陳彥（1984-），男，江蘇揚(yáng)州人，碩士，主要研究方向?yàn)榫W(wǎng)絡(luò)安全（cy1984817@163.com）；

李秀珍（1982-），男，江蘇徐州人，碩士，主要研究方向?yàn)榫W(wǎng)絡(luò)安全.

（江南大學(xué) 信息工程學(xué)院 江蘇 無錫 214122）

摘要：

基于追蹤部署的相關(guān)理論和著色包標(biāo)記算法，針對當(dāng)前危害很大的分布式拒絕服務(wù)攻擊，提出一種基于追蹤部署的IP回溯算法。該算法是以貪心算法為基礎(chǔ)，利用K-剪枝算法在網(wǎng)絡(luò)拓?fù)鋱D中找出一些關(guān)鍵的路由器，利用這些路由器也就是只讓tracers對過往的數(shù)據(jù)包按照著色包標(biāo)記算法進(jìn)行標(biāo)記，這樣不但減少了重構(gòu)路徑所需的數(shù)據(jù)包數(shù)，降低了路徑誤報(bào)率，提高了追蹤到攻擊者的速度，而且大大減輕了路由器標(biāo)記的負(fù)擔(dān)，從而能夠迅速準(zhǔn)確地找到攻擊源。

關(guān)鍵詞：追蹤部署； 分布式拒絕服務(wù)攻擊； 貪心算法； K-剪枝算法； 著色包標(biāo)記算法

中圖分類號：TP393

文獻(xiàn)標(biāo)志碼：A

文章編號：1001-3695(2008)10-3102-03

Research on coloring packetmarking algorithm based on tracers placement

LIU Yuan CHEN Yan LI Xiu-zhen

(College of Information Engineering Jiangnan University Wuxi Jiangsu 214122 China)

Abstract:

Based on the theory of tracers placement and coloring packetmarking algorithmthis paper proposedan IP traceback algorithm based on tracers placement against DDoS. The algorithm was based on the greedy algorithm using K-Diameter-Cut algorithm in the network topology map to identify some key routers. Using these routers also tracers to mark the packets according with coloring packetmarking algorithm not only could reduce the number of packets needed for path reconstruction and number of 1 positives speed the tracing to attacker but also greatly reduced the burden on the router marker.Therefore it can locate the attack origins rapidly and accurately.

Key words：tracers placement; distributed denial of service(DDoS); greedy algorithm; K-Diameter-Cut algorithm; coloring packetmarking algorithm

拒絕服務(wù)攻擊（DoS、DDoS）已經(jīng)成為Internet 的嚴(yán)重威脅，造成了極大的經(jīng)濟(jì)損失，難以防范。這類攻擊實(shí)施簡單、攻擊流量大、隱蔽性強(qiáng)。可利用的安全性低而資源豐富的網(wǎng)絡(luò)主機(jī)越來越多，因此，如何快速、有效地找出攻擊源，并及時(shí)采用相應(yīng)的防御措施，就成了DDoS攻擊防御研究中的關(guān)鍵課題。

1相關(guān)工作

為了解決追蹤攻擊源的問題，提出了很多方案，如入口過濾（ingress filter）[1，2]、輸入調(diào)試（input debugging）[1，3]、有限洪泛（controlled flooding）[4]、日志記錄（logging）[5]、ICMP 追蹤報(bào)文（ICMP traceback message）[6]和包標(biāo)記（packetmarking）[1，4]等。但是包標(biāo)記是目前最為有效的追蹤方法，它通過向包中添加標(biāo)記使其攜帶路徑信息，因此具有許多其他方法所不具備的優(yōu)點(diǎn)。例如不需要ISP的配合，避免了調(diào)試中高昂的管理開銷；不會產(chǎn)生巨大的網(wǎng)絡(luò)流量，給網(wǎng)絡(luò)路由器帶來過大的負(fù)載，而且還支持事后追蹤等。最早由Savage等人[1]進(jìn)行了深入研究的概率包標(biāo)記方案就是為了追蹤攻擊者或傀儡機(jī)而提出的。Savage方案的最大問題在于追蹤所需數(shù)據(jù)包數(shù)量隨攻擊路徑長度急劇增加。Wang等人[7]提出一種追蹤部署策略來防御DDoS攻擊，解決了怎樣在一個網(wǎng)絡(luò)拓?fù)鋱D中部署tracers以追蹤到攻擊者，但其中沒有提到具體的包標(biāo)記策略和重構(gòu)路徑的收斂速度。M.Muthuprasanna等人[8]提出一種著色包標(biāo)記算法，雖然減輕了路由器標(biāo)記數(shù)據(jù)包的負(fù)擔(dān)，減少了重構(gòu)路徑時(shí)所需的數(shù)據(jù)包數(shù)，能夠比較有效地重構(gòu)出攻擊路徑，但是求出的攻擊路徑的誤報(bào)率仍比較高。本文借鑒他們的思想，利用各自的優(yōu)點(diǎn)，提出了一種基于追蹤部署的著色包標(biāo)記算法，通過模擬路由環(huán)境下的實(shí)驗(yàn)，取得了較好的效果。

2網(wǎng)絡(luò)模型和定義

網(wǎng)絡(luò)模型可以抽象成無向圖G=(V，E)。其中：V表示點(diǎn)的集合；E表示邊的集合。由（V1，V2），(V2，V3)，…，(Vn-1，Vn)這些邊構(gòu)成一條路徑。V1和Vn分別叫做起點(diǎn)和終點(diǎn)，V1到Vn的路徑長度為n-1。在G中如果任意兩個節(jié)點(diǎn)都存在一條路徑，就稱此圖是連通的。定義G中u和v兩點(diǎn)的距離為圖中存在于u和v中所有路徑中最短的，否則記d(u，v)=∞。如果刪除圖中的一個點(diǎn)圖不再連通，那么這個點(diǎn)稱為割點(diǎn)。割點(diǎn)集就是使圖不連通所要刪除的最少點(diǎn)數(shù)的集合，記為k(G)。如果一個點(diǎn)的集合能夠覆蓋圖G中的所有邊，那么就稱此集合為G的點(diǎn)覆蓋。最少的點(diǎn)覆蓋集合記為β(G)。離心率e(v)定義為圖中離v最長的距離。半徑r(G)為最小的離心率，直徑d(G)為最大的離心率。

3Tracers的部署算法

K-剪枝問題是指在圖G中設(shè)法找到最少的節(jié)點(diǎn)數(shù)，使得刪除它們后的圖的每一個連通子圖的直徑比k小，那么為了尋找出這些節(jié)點(diǎn)，文獻(xiàn)提出了用貪心算法解決K-剪枝問題，從而解決了怎樣在網(wǎng)絡(luò)拓?fù)鋱D中布置最少的tracers，通過實(shí)驗(yàn)得出結(jié)論隨著k值的增大，所需的tracers越少，那么對于不同規(guī)模的網(wǎng)絡(luò)模型取不同的k值，基本上是如果網(wǎng)絡(luò)規(guī)模越大越復(fù)雜，那么所取的k值越小，也就是所需的traces越多。圖1、2給出了k=3時(shí)按照此剪枝算法求得的三個子圖，每個子圖中的節(jié)點(diǎn)都是tracers，圖3給出了最終要刪除的標(biāo)號為7和10的節(jié)點(diǎn)。根據(jù)文獻(xiàn)的基本思想，布置的tracers所在的子圖中至少有一個tracer在攻擊路徑上。那么怎樣收集最少數(shù)據(jù)包重構(gòu)出攻擊路徑找到所有的tracers，這就是本文要解決的問題。下面簡述一下文獻(xiàn)[7]的基本算法思想。

3.1貪心算法

a)S=。

b)if G= break;

else在G中選取一個度數(shù)最小的節(jié)點(diǎn)v。

c)把v加到集合S中，刪除v和它所有的相鄰節(jié)點(diǎn)，重復(fù)步驟b)。

3.2K-剪枝算法

a)if k=1 then用貪心算法求出每個獨(dú)立的集合S，輸出T=V-S；

else繼續(xù)下面的步驟：

b)算出每對節(jié)點(diǎn)的離心率e(v)。

c)找出G的中心，從中任取一個點(diǎn)c。

d)如果k為奇數(shù)，找出所有離c點(diǎn)距離小于等于(k-1)/2的所有節(jié)點(diǎn)集合W={v|d(v，c)≤(k-1) and v∈V}。

e)如果k為偶數(shù)，繼續(xù)下面的步驟：

(a)找出所有離c點(diǎn)距離小于等于(k－1)/2的所有節(jié)點(diǎn)集合W={v|d(v，c)≤(k-1)」 and v∈V}；

(b)計(jì)算出Y={v|d(v，c)= (k-1)」+1 and v∈V}；

(c)選取任一節(jié)點(diǎn)vy∈Y ，移出vy；

(d)if d(GW∪{vy})

(e)如果Y不為空，重復(fù)步驟(c)和(d)。

f)從G中獲得G通過不斷縮短子圖Gw直到只剩一個節(jié)點(diǎn)vw。

g)把vw的所有相鄰節(jié)點(diǎn)并入T中(T初始化為空)。為了獲得G′，在G中刪除節(jié)點(diǎn)vw及其所有的相鄰節(jié)點(diǎn)。

h)對于G′的每一個部分Gi，如果d(Gi)≥k，不斷對Gi重復(fù)步驟b)~h)。

4基于追蹤部署的著色包標(biāo)記算法

4.1著色問題

4.1.1圖的點(diǎn)著色問題

圖的點(diǎn)著色問題指的是在圖G中，對每個節(jié)點(diǎn)v用最少的顏色數(shù)對其進(jìn)行著色，使得任意兩個相鄰節(jié)點(diǎn)的顏色不相同。

4.1.2Tracers著色問題

根據(jù)上述有關(guān)圖的著色問題，結(jié)合上面追蹤部署算法所得到的tracers，本文自行設(shè)計(jì)出一種著色方案。敘述如下：在圖G中，根據(jù)上述追蹤部署算法求出所有的tracers，用最少的顏色數(shù)對tracer著色，使得任意兩個相鄰tracer的顏色不相同。根據(jù)文獻(xiàn)，設(shè)一個圖G中最大度數(shù)節(jié)點(diǎn)的度數(shù)為Δ，對一個圖完全著色所需要的顏色數(shù)最少為Δ+1，最多為Δ2+1，如圖4、5所示。

把每一個tracer看成一個節(jié)點(diǎn)，用貪心算法對其進(jìn)行著色，具體步驟如下：

Input:G=(TRACERS，E)

Output:A coloring c:TRACER→1，2，3，…

for i=|TRACERS|;i>0;i-- do

tracert(yī)racer with least degree in subgraph of unlabled vertices

assign label I to tracer

set c(tracer)0

end for

for j=largest-label;j>0;j-- do

μ

for all tracers such that (u，tracer)∈E do μμ∪c(tracer)

for all w such that (w，tracer)∈E do μμ∪c(w)

end for

end for

c(u)least colorμ

end for

4.2著色包標(biāo)記算法

在文獻(xiàn)[8]中，針對節(jié)點(diǎn)度數(shù)特別大的網(wǎng)絡(luò)拓?fù)鋱D又提出了一種基于邏輯著色圖的包標(biāo)記方法，因?yàn)楸疚耐ㄟ^追蹤部署算法已經(jīng)將度數(shù)特別大的節(jié)點(diǎn)基本除去，所以避免了上述因某節(jié)點(diǎn)度數(shù)過大而影響追蹤效果的問題。下面詳細(xì)介紹一下改進(jìn)的著色包標(biāo)記算法。

著色包標(biāo)記算法主要是通過將路由器簡單的顏色信息代替路由器IP信息按照一定的概率標(biāo)記到數(shù)據(jù)包的IPv4包頭中，這樣就減輕了路由器的標(biāo)記負(fù)擔(dān)。上面說到由于采用了追蹤部署的算法，不用考慮2-tier的結(jié)構(gòu)問題，那么也就不用在包頭用1 bit的空間去存放tier域。本文對此提出改進(jìn)，采用了K-剪枝算法將一些無關(guān)緊要的路由器去除掉了，只讓tracers對數(shù)據(jù)包進(jìn)行標(biāo)記，把對tracers著色后得到的顏色信息標(biāo)記到數(shù)據(jù)包的包頭中，當(dāng)受害者重構(gòu)攻擊路徑時(shí)，避免了受害者重構(gòu)出很多重復(fù)的路徑信息，大大降低了誤報(bào)率，提高了重構(gòu)路徑的收斂速度，使得受害者僅通過比較少的數(shù)據(jù)包就可以重構(gòu)出攻擊路徑，從而能夠迅速準(zhǔn)確地找到攻擊源。考慮到有相同的顏色會影響到路徑的重構(gòu)，所以在包頭中設(shè)置了random ID這個域用于區(qū)分不同的節(jié)點(diǎn)。具體的包頭結(jié)構(gòu)設(shè)置如圖6所示。根據(jù)相關(guān)文獻(xiàn)中的研究結(jié)果，標(biāo)記的概率取1/d(d為路由器到受害者的距離，以跳數(shù)計(jì)算)時(shí)，所需的數(shù)據(jù)包數(shù)量最少。下面結(jié)合本文中的tracer給出具體的證明過程。

5收斂性分析

根據(jù)文獻(xiàn)[9]的定理，利用概率中的加法原理算出公式的結(jié)果如下：

定理在攻擊路徑中一共有n個不同的tracer，記為{Tm}(m=1，2，…，n)，qm是受害者收到的Tm標(biāo)記數(shù)據(jù)包的概率，N是受害者收到的被每個tracer至少標(biāo)記了一次所需要的數(shù)據(jù)包數(shù)量，它的數(shù)學(xué)期望



E[N]=∫ ∞ 0{1-∏nm=1(1-e-qmt)}dt=

∑mi=11/qi-∑1≤i＜j≤m1/(qi+

qj)+∑1≤i＜j＜k≤m1/(qi+qj+qk)-…

(-1)m-1/(q1+q2+…+qm)

證明因?yàn)閝m表示了Tm標(biāo)記數(shù)據(jù)包的概率，現(xiàn)在用qn+1表示數(shù)據(jù)包不被任何一個tracer標(biāo)記的概率，所以有∑n+1m=1qm=1，為了算出集中攻擊時(shí)間的數(shù)學(xué)期望E[N]，本文先引進(jìn)一些輔助的泊松過程{C(t)，t≥0}，此過程用來描述m型事件也就是收到被Tm標(biāo)記的數(shù)據(jù)包發(fā)生的等待時(shí)間記為{Cm(t)，t≥0}。n+1型事件也就是一個tracer都沒有標(biāo)記過。它們是獨(dú)立的泊松過程，有各自的速度。現(xiàn)在用ξm描述第一個m型事件發(fā)生的時(shí)間Cm(t)，ξ=max1≤m≤nξm用來表示等待所有類型事件發(fā)生的時(shí)間。根據(jù)泊松過程相關(guān)定理，ξm是一個獨(dú)立的指數(shù)隨機(jī)變量，泊松流為qm，所以有

Pr(ξ

∏nm=1Pr(ξm

∏nm=1(1-e-qmt)

E[ξ]=∫ ∞ 0{1-∏nm=1(1-e-qmt)}dt=

∫ ∞ 0{1-(1-e-q1t)(1-e-q2t)…(1-e-qmt)}dt

令Pi=e-qit，根據(jù)n個事件的加法定理，將上式

原式=∫ ∞ 0{1-(1-∑mi=1Pi+∑1≤i＜j≤mPiPj-∑1≤i＜j＜k≤mPiPjPk+

(-1)mP1P2…Pm)}dt=

∫ ∞ 0{∑mi=1Pi-∑1≤i＜j≤mPiPj+

∑1≤i＜j＜k≤mPiPjPk-…(-1)m-1P1P2…Pm}dt=∑mi=11/qi-

∑1≤i＜j≤m1/(qi+qj)+∑1≤i＜j＜k≤m1/(qi+qj+qk)-…(-1)m-1/

(q1+q2+…+qm)

下面就是要證明E[ξ]=E[N]。

首先看到ξ實(shí)際上就是收到數(shù)據(jù)包數(shù)N的時(shí)間。ξ=∑Nk=1τk，τk就是事件k到達(dá)的間隔時(shí)間，泊松過程C(t)根據(jù)事件到達(dá)的數(shù)量描述了它，所以τk也是一個獨(dú)立的指數(shù)變量。這時(shí)泊松流為1，N和τk相互獨(dú)立，所以得到

E[ξ]=E[E[ξ|N]]=E[E[∑NK=1τK|N]]=E[N.E[τk]]=E[N]

由概率q1=q2=…=qm=1/d代入上式得

原式=d(C1d-C2d/2+C3d/3-…-(-1)m-1Cdd/d)=

d(1+1/2+1/3+…+1/d)=d(ln(d)+O(l))

所以此算法有較好的收斂性。

6實(shí)驗(yàn)結(jié)果

通過實(shí)驗(yàn)比較了本文方法和M.Muthuprasanna[8]等人的著色包標(biāo)記算法，由于受害者收集到的數(shù)據(jù)包只含有tracer的信息，那么只要通過這些tracer就能重構(gòu)出攻擊路徑，所以比著色包標(biāo)記算法所需的數(shù)據(jù)包數(shù)減少很多。對于不同的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)即節(jié)點(diǎn)的平均度數(shù)不一樣，以及對于相同的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，根據(jù)K-剪枝算法選取k值的不同，所布置的tracers的數(shù)量也是不一樣的，著色數(shù)也就不一樣，如表1、2所示，這樣所需的數(shù)據(jù)包數(shù)也是不一樣的。本文根據(jù)不同的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，對比誤報(bào)率的情況，選取平均度數(shù)D=4和D=6兩種情況進(jìn)行實(shí)驗(yàn)，相對于著色包標(biāo)記，誤報(bào)率有明顯的降低，如圖7所示；對比數(shù)據(jù)包數(shù)，在度數(shù)相同的情況下，選取k值分別等于3、5、7，在攻擊路徑長度不超過30的情況下，與著色包標(biāo)記進(jìn)行比較，分別得出結(jié)果，在相同路徑長度和相同度數(shù)的情況下，k越大，所需要的數(shù)據(jù)包數(shù)越少，如圖8、9所示。對比兩個圖可以看出在k=3，k=5時(shí)，D=6比D=4時(shí)所需的數(shù)據(jù)包數(shù)要多，而k=7時(shí)卻相反，D=6時(shí)反而更少。所以本文的算法對于大型而特別復(fù)雜的網(wǎng)絡(luò)結(jié)構(gòu)效果更明顯。

7結(jié)束語

本文的主要思想是以文獻(xiàn)[7]的算法思想為基礎(chǔ)，通過著色包標(biāo)記[8]算法只讓tracer對數(shù)據(jù)包進(jìn)行標(biāo)記，在受害端收集所有的tracers信息，因而這時(shí)候的數(shù)據(jù)包數(shù)是最少的，重構(gòu)路徑的誤報(bào)率也大大降低；通過著色包標(biāo)記算法標(biāo)記數(shù)據(jù)包，大大減輕了路由器標(biāo)記的負(fù)擔(dān)；而通過只對追蹤部署的tracer進(jìn)行著色標(biāo)記，減少了重構(gòu)路徑所需的數(shù)據(jù)包數(shù)，提高了追蹤到攻擊者的速度，從而能迅速而準(zhǔn)確地找到攻擊源。

參考文獻(xiàn)：

[1]SAVAGE S WETHERALL D KARLIN A et al. Practical network support for IP traceback[C]//Proc of ACM SIGCOMM. 2000:295-306.

[2]FERGUSON P SENIE D. RFC 2827 Network ingress filtering:defeating denial of service attacks which employ IP source address spoofing[S]. 2000.

[3]TATSUYA B SHIGEYUKI M. Tracing network attacks to their sources[J]. IEEE Internet Computing 2002，6(2):20-26.

[4]BURCH H CHESWICH B. Tracing anonymous packets to their approximate source[C]//Proc of USENIX LISA. New Orleans:[s.n.] 2000:313-321.

[5]HASSAN A. IP traceback: a new denial-of-service deterrent[J]. IEEE Security Privacy 2003，1(3):24-31.

[6]BELLOVIN S，LEECH M，TAYLOR T.ICMP traceback messages draft-ietf-itrace-02.txt[R].[S.l.]: IETF 2001.

[7]WANG Chun-hsin YU Chang-wu LIANG Chiu-kuo et al. Tracers placement for IP traceback against DDoS attacks[C]//Proc of International Conference on Wireless Communications and Mobile Computing. New York: ACM Press 2006:355-360.

[8]MUTHUPRASANNA M MANIMARAN G. Coloring the Internet:IP traceback[C]//Proc of the 12th International Conference on Parallel and Distributed Systems. Washington DC: IEEE Computer Society 2006:589-598.

[9]MA Miao. Tabu marking scheme for IP traceback[C]//Proc of the 19th IEEE International Parallel and Distributed Processing Sympo-sium. Washington DC: IEEE Computer Society 2005:292-300.