基于追蹤部署的著色包標記算法的研究
2008-12-31 00:00:00劉淵陳彥李秀珍
計算機應用研究 2008年10期
收稿日期：2008-01-14；
修回日期：2008-03-25
基金項目：國防基礎研究基金資助項目（A1420061266）
作者簡介：劉淵(1967-)，男，教授，碩導，主要研究方向為網絡安全及網絡信息系統；
陳彥（1984-），男，江蘇揚州人，碩士，主要研究方向為網絡安全（cy1984817@163.com）；
李秀珍（1982-），男，江蘇徐州人，碩士，主要研究方向為網絡安全.
（江南大學 信息工程學院 江蘇 無錫 214122）
摘要：
基于追蹤部署的相關理論和著色包標記算法，針對當前危害很大的分布式拒絕服務攻擊，提出一種基于追蹤部署的IP回溯算法。該算法是以貪心算法為基礎，利用K-剪枝算法在網絡拓撲圖中找出一些關鍵的路由器，利用這些路由器也就是只讓tracers對過往的數據包按照著色包標記算法進行標記，這樣不但減少了重構路徑所需的數據包數，降低了路徑誤報率，提高了追蹤到攻擊者的速度，而且大大減輕了路由器標記的負擔，從而能夠迅速準確地找到攻擊源。
關鍵詞：追蹤部署； 分布式拒絕服務攻擊； 貪心算法； K-剪枝算法； 著色包標記算法
中圖分類號：TP393
文獻標志碼：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
拒絕服務攻擊（DoS、DDoS）已經成為Internet 的嚴重威脅，造成了極大的經濟損失，難以防范。這類攻擊實施簡單、攻擊流量大、隱蔽性強。可利用的安全性低而資源豐富的網絡主機越來越多，因此，如何快速、有效地找出攻擊源，并及時采用相應的防御措施，就成了DDoS攻擊防御研究中的關鍵課題。
1相關工作
為了解決追蹤攻擊源的問題，提出了很多方案，如入口過濾（ingress filter）[1，2]、輸入調試（input debugging）[1，3]、有限洪泛（controlled flooding）[4]、日志記錄（logging）[5]、ICMP 追蹤報文（ICMP traceback message）[6]和包標記（packetmarking）[1，4]等。但是包標記是目前最為有效的追蹤方法，它通過向包中添加標記使其攜帶路徑信息，因此具有許多其他方法所不具備的優點。例如不需要ISP的配合，避免了調試中高昂的管理開銷；不會產生巨大的網絡流量，給網絡路由器帶來過大的負載，而且還支持事后追蹤等。最早由Savage等人[1]進行了深入研究的概率包標記方案就是為了追蹤攻擊者或傀儡機而提出的。Savage方案的最大問題在于追蹤所需數據包數量隨攻擊路徑長度急劇增加。Wang等人[7]提出一種追蹤部署策略來防御DDoS攻擊，解決了怎樣在一個網絡拓撲圖中部署tracers以追蹤到攻擊者，但其中沒有提到具體的包標記策略和重構路徑的收斂速度。M.Muthuprasanna等人[8]提出一種著色包標記算法，雖然減輕了路由器標記數據包的負擔，減少了重構路徑時所需的數據包數，能夠比較有效地重構出攻擊路徑，但是求出的攻擊路徑的誤報率仍比較高。本文借鑒他們的思想，利用各自的優點，提出了一種基于追蹤部署的著色包標記算法，通過模擬路由環境下的實驗，取得了較好的效果。
2網絡模型和定義
網絡模型可以抽象成無向圖G=(V，E)。其中：V表示點的集合；E表示邊的集合。由（V1，V2），(V2，V3)，…，(Vn-1，Vn)這些邊構成一條路徑。V1和Vn分別叫做起點和終點，V1到Vn的路徑長度為n-1。在G中如果任意兩個節點都存在一條路徑，就稱此圖是連通的。定義G中u和v兩點的距離為圖中存在于u和v中所有路徑中最短的，否則記d(u，v)=∞。如果刪除圖中的一個點圖不再連通，那么這個點稱為割點。割點集就是使圖不連通所要刪除的最少點數的集合，記為k(G)。如果一個點的集合能夠覆蓋圖G中的所有邊，那么就稱此集合為G的點覆蓋。最少的點覆蓋集合記為β(G)。離心率e(v)定義為圖中離v最長的距離。半徑r(G)為最小的離心率，直徑d(G)為最大的離心率。
3Tracers的部署算法
K-剪枝問題是指在圖G中設法找到最少的節點數，使得刪除它們后的圖的每一個連通子圖的直徑比k小，那么為了尋找出這些節點，文獻提出了用貪心算法解決K-剪枝問題，從而解決了怎樣在網絡拓撲圖中布置最少的tracers，通過實驗得出結論隨著k值的增大，所需的tracers越少，那么對于不同規模的網絡模型取不同的k值，基本上是如果網絡規模越大越復雜，那么所取的k值越小，也就是所需的traces越多。圖1、2給出了k=3時按照此剪枝算法求得的三個子圖，每個子圖中的節點都是tracers，圖3給出了最終要刪除的標號為7和10的節點。根據文獻的基本思想，布置的tracers所在的子圖中至少有一個tracer在攻擊路徑上。那么怎樣收集最少數據包重構出攻擊路徑找到所有的tracers，這就是本文要解決的問題。下面簡述一下文獻[7]的基本算法思想。
3.1貪心算法
a)S=。
b)if G= break;
else在G中選取一個度數最小的節點v。
c)把v加到集合S中，刪除v和它所有的相鄰節點，重復步驟b)。
3.2K-剪枝算法
a)if k=1 then用貪心算法求出每個獨立的集合S，輸出T=V-S；
else繼續下面的步驟：
b)算出每對節點的離心率e(v)。
c)找出G的中心，從中任取一個點c。
d)如果k為奇數，找出所有離c點距離小于等于(k-1)/2的所有節點集合W={v|d(v，c)≤(k-1) and v∈V}。
e)如果k為偶數，繼續下面的步驟：
(a)找出所有離c點距離小于等于(k－1)/2的所有節點集合W={v|d(v，c)≤(k-1)」 and v∈V}；
(b)計算出Y={v|d(v，c)= (k-1)」+1 and v∈V}；
(c)選取任一節點vy∈Y ，移出vy；
(d)if d(GW∪{vy}) (e)如果Y不為空，重復步驟(c)和(d)。 f)從G中獲得G通過不斷縮短子圖Gw直到只剩一個節點vw。 g)把vw的所有相鄰節點并入T中(T初始化為空)。為了獲得G′，在G中刪除節點vw及其所有的相鄰節點。 h)對于G′的每一個部分Gi，如果d(Gi)≥k，不斷對Gi重復步驟b)~h)。 4基于追蹤部署的著色包標記算法 4.1著色問題 4.1.1圖的點著色問題 圖的點著色問題指的是在圖G中，對每個節點v用最少的顏色數對其進行著色，使得任意兩個相鄰節點的顏色不相同。 4.1.2Tracers著色問題 根據上述有關圖的著色問題，結合上面追蹤部署算法所得到的tracers，本文自行設計出一種著色方案。敘述如下：在圖G中，根據上述追蹤部署算法求出所有的tracers，用最少的顏色數對tracer著色，使得任意兩個相鄰tracer的顏色不相同。根據文獻，設一個圖G中最大度數節點的度數為Δ，對一個圖完全著色所需要的顏色數最少為Δ+1，最多為Δ2+1，如圖4、5所示。 把每一個tracer看成一個節點，用貪心算法對其進行著色，具體步驟如下： Input:G=(TRACERS，E) Output:A coloring c:TRACER→1，2，3，… for i=|TRACERS|;i>0;i-- do tracertracer 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著色包標記算法 在文獻[8]中，針對節點度數特別大的網絡拓撲圖又提出了一種基于邏輯著色圖的包標記方法，因為本文通過追蹤部署算法已經將度數特別大的節點基本除去，所以避免了上述因某節點度數過大而影響追蹤效果的問題。下面詳細介紹一下改進的著色包標記算法。 著色包標記算法主要是通過將路由器簡單的顏色信息代替路由器IP信息按照一定的概率標記到數據包的IPv4包頭中，這樣就減輕了路由器的標記負擔。上面說到由于采用了追蹤部署的算法，不用考慮2-tier的結構問題，那么也就不用在包頭用1 bit的空間去存放tier域。本文對此提出改進，采用了K-剪枝算法將一些無關緊要的路由器去除掉了，只讓tracers對數據包進行標記，把對tracers著色后得到的顏色信息標記到數據包的包頭中，當受害者重構攻擊路徑時，避免了受害者重構出很多重復的路徑信息，大大降低了誤報率，提高了重構路徑的收斂速度，使得受害者僅通過比較少的數據包就可以重構出攻擊路徑，從而能夠迅速準確地找到攻擊源。考慮到有相同的顏色會影響到路徑的重構，所以在包頭中設置了random ID這個域用于區分不同的節點。具體的包頭結構設置如圖6所示。根據相關文獻中的研究結果，標記的概率取1/d(d為路由器到受害者的距離，以跳數計算)時，所需的數據包數量最少。下面結合本文中的tracer給出具體的證明過程。 5收斂性分析 根據文獻[9]的定理，利用概率中的加法原理算出公式的結果如下： 定理在攻擊路徑中一共有n個不同的tracer，記為{Tm}(m=1，2，…，n)，qm是受害者收到的Tm標記數據包的概率，N是受害者收到的被每個tracer至少標記了一次所需要的數據包數量，它的數學期望 E[N]=∫ ∞ 0{1-∏nm=1(1-e-qmt)}dt= ∑mi=11/qi-∑1≤i＜j≤m1/(qi+ qj)+∑1≤i＜j＜k≤m1/(qi+qj+qk)-… (-1)m-1/(q1+q2+…+qm) 證明因為qm表示了Tm標記數據包的概率，現在用qn+1表示數據包不被任何一個tracer標記的概率，所以有∑n+1m=1qm=1，為了算出集中攻擊時間的數學期望E[N]，本文先引進一些輔助的泊松過程{C(t)，t≥0}，此過程用來描述m型事件也就是收到被Tm標記的數據包發生的等待時間記為{Cm(t)，t≥0}。n+1型事件也就是一個tracer都沒有標記過。它們是獨立的泊松過程，有各自的速度。現在用ξm描述第一個m型事件發生的時間Cm(t)，ξ=max1≤m≤nξm用來表示等待所有類型事件發生的時間。根據泊松過程相關定理，ξm是一個獨立的指數隨機變量，泊松流為qm，所以有 Pr(ξ ∏nm=1Pr(ξm ∏nm=1(1-e-qmt) E[ξ]=∫ ∞ 0{1-∏nm=1(1-e-qmt)}dt= ∫ ∞ 0{1-(1-e-q1t)(1-e-q2t)…(1-e-qmt)}dt 令Pi=e-qit，根據n個事件的加法定理，將上式 原式=∫ ∞ 0{1-(1-∑mi=1Pi+∑1≤i＜j≤mPiPj-∑1≤i＜j＜k≤mPiPjPk+ (-1)mP1P2…Pm)}dt= ∫ ∞ 0{∑mi=1Pi-∑1≤i＜j≤mPiPj+ ∑1≤i＜j＜k≤mPiPjPk-…(-1)m-1P1P2…Pm}dt=∑mi=11/qi- ∑1≤i＜j≤m1/(qi+qj)+∑1≤i＜j＜k≤m1/(qi+qj+qk)-…(-1)m-1/ (q1+q2+…+qm) 下面就是要證明E[ξ]=E[N]。 首先看到ξ實際上就是收到數據包數N的時間。ξ=∑Nk=1τk，τk就是事件k到達的間隔時間，泊松過程C(t)根據事件到達的數量描述了它，所以τk也是一個獨立的指數變量。這時泊松流為1，N和τk相互獨立，所以得到 E[ξ]=E[E[ξ|N]]=E[E[∑NK=1τK|N]]=E[N.E[τk]]=E[N] 由概率q1=q2=…=qm=1/d代入上式得 原式=d(C1d-C2d/2+C3d/3-…-(-1)m-1Cdd/d)= d(1+1/2+1/3+…+1/d)=d(ln(d)+O(l)) 所以此算法有較好的收斂性。 6實驗結果 通過實驗比較了本文方法和M.Muthuprasanna[8]等人的著色包標記算法，由于受害者收集到的數據包只含有tracer的信息，那么只要通過這些tracer就能重構出攻擊路徑，所以比著色包標記算法所需的數據包數減少很多。對于不同的網絡拓撲結構即節點的平均度數不一樣，以及對于相同的網絡拓撲結構，根據K-剪枝算法選取k值的不同，所布置的tracers的數量也是不一樣的，著色數也就不一樣，如表1、2所示，這樣所需的數據包數也是不一樣的。本文根據不同的網絡拓撲結構，對比誤報率的情況，選取平均度數D=4和D=6兩種情況進行實驗，相對于著色包標記，誤報率有明顯的降低，如圖7所示；對比數據包數，在度數相同的情況下，選取k值分別等于3、5、7，在攻擊路徑長度不超過30的情況下，與著色包標記進行比較，分別得出結果，在相同路徑長度和相同度數的情況下，k越大，所需要的數據包數越少，如圖8、9所示。對比兩個圖可以看出在k=3，k=5時，D=6比D=4時所需的數據包數要多，而k=7時卻相反，D=6時反而更少。所以本文的算法對于大型而特別復雜的網絡結構效果更明顯。 7結束語 本文的主要思想是以文獻[7]的算法思想為基礎，通過著色包標記[8]算法只讓tracer對數據包進行標記，在受害端收集所有的tracers信息，因而這時候的數據包數是最少的，重構路徑的誤報率也大大降低；通過著色包標記算法標記數據包，大大減輕了路由器標記的負擔；而通過只對追蹤部署的tracer進行著色標記，減少了重構路徑所需的數據包數，提高了追蹤到攻擊者的速度，從而能迅速而準確地找到攻擊源。 參考文獻： [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.
