基于流量強度的DDoS攻擊源追蹤快速算法

摘 要:DDoS攻擊以其破壞力大、易實施、難檢測、難追蹤等特點，而成為網絡攻擊中難處理的問題之一。攻擊源追蹤技術是阻斷攻擊源、追蹤相關責任、提供法律證據的必要手段。基于網絡拓撲理論和路由器流量特性原理以及可編程式路由器的體系結構，提出了一種追蹤DDoS攻擊源的分布式快速算法，該算法可以準確、協調、高效地判斷路由器的數據流量值，受害者可以根據流量強度推斷出惡意攻擊數據流的來源，從而快速追溯和定位DDoS攻擊源。

關鍵詞:DDoS攻擊; 攻擊源追蹤; 流量強度; 追蹤算法

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

文章編號:1004-373X(2010)07-0131-04

Fast Algorithm Based on Traffic Intensity for DDoS Attack Source Track

LIU An-li， ZHAO Huai-xun

(Departmant of Communications Engrneering， Engineering College of Armed Police Force， Xi’an 710086， China)

Abstract: DDoS attack whose damage is great to the network， easy to implement， difficult to detect， difficult to track and so on， is one of the intractable problems in network protection. Network attack source track is an essential technology in stopping on-going attacks， prosecuting， and deterring attackers.Based on network topology and traffic principle of routers， a fast distributed algorithm for tracking DDoS attack source is proposed. The algorithm can determine the data traffic values of routers traffic accurately， coordinately and efficiently， the victim can infer the source of malicious data traffic by traffic intensity.Therefore，it can locate the attack origins rapidly and accurately.

Keywords: DDoS attack; attack source track; traffic intensity; track algorithm

0 引 言

互聯網的出現，在帶來溝通便捷化的同時也暴露出很多內在的安全問題，DDoS(Distributed Denial-of-service)攻擊就是其中最普遍的問題之一[1]。近年來，DDoS攻擊的規模、頻率和攻擊強度正在逐年增加。本文提出一種分布式追蹤算法，可以有效地追蹤風暴型DDoS攻擊。該算法基于以下兩點:

首先，網絡中的路由器是一種可編程式的路由體系結構[2，3]，即路由器可以協同采集統計相關數據流并傳輸給受害者。受害者能夠構建攻擊圖譜，通過分析接收到的數據包勾畫攻擊路徑，準確推斷攻擊流的來源、強度和規模。

其次，受害者根據確定的每個網絡中路由器本地數據流量強度，以及在一定的測量時間間隔內獲得來自每個路由器的數據流量，確定存在攻擊的路由器消耗受害者資源的比例大小。

1 相關工作

網絡拓撲圖如圖1所示。

圖1 網絡拓撲圖

首先確定相關的網絡模型。在圖1中，以V為根節點，由路由器和局域網(LAN)組成的有向無環圖(DAG)代表了一個網絡拓撲結構;根節點V代表受害者的網站;Ri是V的上游路由器。所有路由器中流向V的數據流形成DAG圖譜。每個LAN網包含終端(client)，這些終端包括合法終端和攻擊者(attacker)。路由器Ri作為LAN0和LAN1網關，這兩個局域網稱為R1的本地域。路由器負責傳輸從域中產生的數據流以及從域的上游路由器產生的數據流。將模型推至整個網絡，當相應的局域網代表ISP/AS域時，路由器代表ISP或一個AS的邊緣路由器。

定義以下概念:過境流量是從直接上游路由器轉發的數據流，本地域中所產生的數據流量定義為Ri的本地流量，輸出流量是過境流量與本地流量的總和。

如圖1所示，流向V的流量部分來自于LAN5，數據包必須通過路由器R5，R4和R1 才到V，來自于LAN5的流量被認為是路由器R4的過境流量。另一方面，來自于LAN4的客戶也產生流量給V，這個流量作為R4的本地流量考慮。來自與LAN4和LAN5兩股數據流的匯總作為R4的輸出數據流。

假設每個路由器都有一個計數器，記錄累積(忽略反重疊問題)流向V的輸出數據流時，攻擊者的行為定義為大量相互協同的攻擊者在一定的時間內以虛假源地址產生并發送大量的攻擊數據流給受害者，消耗受害者的系統資源。

下面介紹本文的方法[4]，Ci(t)是路由器Ri在t時刻的外部流量計數器的值;U(Ri)是Ri的直接上游路由器。路由器Ri在時刻t的本地流量總和為:

Ni(t) = Ci(t)-∑Rj∈U(Ri)Cj(t)

(1)

在[t1，t2]時間內，通過Ri路由器的本地流量(流量強度)Li(t1，t2)為:

Li(t1，t2)=Ni(t2)-Ni(t1)

(2)

可以通過式(1)來判斷發向受害者的本地流量。通過在監測兩個不同時間點的流量值，路由器可通過式(2)獲得發向受害者的本地流量。

此算法在整個網絡中有一個全球時鐘，并且所有的路由器都能夠對其各自的輸出流量計數器執行同步閱讀的情況下才是正確的，以下所提出的算法，不依賴全球時鐘就可精確測量所有路由器的本地流量，并根據流量強度確定攻擊者位置。

2 流量測量原理

首先用一個例子來說明概念的正確性，圖2描述了兩個路由器Ri和Rj之間的時序圖。圖中Rj是Ri的直接上游路由器，黑方塊表示一個路由器Ri中讀到的輸出數據流量值，將這一瞬間記為ti，k，此處 k∈[1，2]，代表兩次流量讀取。假設圖2是第k次讀取輸出數據流量計數器的值;Cj(tj，k)是在ti，k時刻路由器Rj輸出數據流量計數器的值;Ci(ti，k)是ti，k時刻路由器Ri輸出數據流量的值;Aji塊代表在時刻tj，k之前通過路由器Rj發送給受害者V和時刻ti，k之后通過路由器Ri接收的一系列數據包。相應地，Bji塊表示在時刻tj，k后通過Rj發送給受害者V和在ti，k時刻前接收到的一系列數據包。由此可知，所有Aji中的數據包記錄在Cj(tj，k)中而不是記錄在Ci(ti，k)中;所有Bji中的數據包記錄在Ci(ti，k)中，而不是記錄在Cj(tj，k)中，如果這些數據包記錄錯誤，將導致錯誤的結論。

圖2 本地流量累積值示意圖

在時刻ti，k時Ri的本地流量記為Ni(ti，k)，它介于ti，k時刻收到的輸出流量和過境數據流量traffic(Ri/ti，k)之間:

Ni(ti，k)=Ci(ti，k)-traffic(Ri/ti，k)

Ri在時刻ti，k時的過境流量來自于Ri的所有直接上游路由器的輸出流量，首先，在ti，k時刻數據包Aji中沒有收到來自于Ri的數據，但是在 tj，k時刻收到了來自于Rj的數據包，需要在Cj(tj，k)中減掉流量負載，另外，在ti，k時刻Bji中的數據包記錄有來自于Ri的，但是在tj，k時刻沒有來自于Rj的，于是，需要在Cj(tj，k)中增加流量負載。因此，來自于路由器Ri的正確的本地流量值如下:

Ni(ti，k)=Ci(ti，k)-∑Rj∈U(Ri)(Cj(tj，k)-Aji+Bji)

基于以上流量計算原理，提出一種分布式快速算法[5] ，用來準確測量Aji和Bji的值。

3 分布式快速追蹤算法

3.1 算法定義和功能

快速算法由三部分組成:指令;路由器或受害者V狀態;信道狀態。

(1) 指令:指令是一個特殊的頭項分組，最初由V發送給其所有相鄰路由器，功能是讓所有參與其中的路由器記錄它們的局部狀態并推導出相應的信道狀態。

(2) 本地狀態:每一個參與的路由器Ri和受害者V都有自己的本地狀態。對于Ri，在時刻t的本地狀態是輸出流量值Ci(t)，受害者V的本地狀態指的是在時刻t收到的數據包的累積值，也就是說從各參與路由器的域中發往V的累積流量TV(t)，在時間間隔[t1，t2]內發送到受害者V的輸入流量可表示為:

IV(t1，t2)=TV(t2)-TV(t1)

(3)

(3) 信道狀態:指的是相應的路由器在記錄它自己的本地狀態之后，并在路由器沿著鏈路收到指令之前，接收到數據包的數量，本算法假設數據包的傳輸遵照FIFO原理，兩個相鄰的路由器通過同一個通信鏈路或在同一局域網內，由于信道狀態的衡量是從上游路由器轉發的數據包數量，因此路由器不必檢查傳入數據包的源地址，本算法只關注數據包從哪個上游路由器而來。因為當數據包通過路由設備時，數據包地址通常要被路由設備的硬件地址所改變。若攻擊者偽造兩級數據包源地址對本算法無影響。

定義以下標記:定義Ri和Rj是兩個相鄰的通過單向連接的路由器，鏈路為Linkij和Linkji，Ri記錄它的本地狀態的時刻為ti，k，在Ri記錄它的本地狀態之后的時刻tji，k 收到來自于Linkji的一個指令(如果在Ri記錄它的本地狀態之前指令已經到達，則時刻為ti，k)，記Hji(ti，k，tji，k)作為Linkji的信道狀態，此狀態就是在tji，k之前，ti，k 之后Rj從Ri收到的數據包的數量，下面的偽代碼顯示了快速算法的輪廓。

3.2 追蹤快速算法

追蹤快速算法:

(1) 算法初始化

受害者V記錄在時刻t的數據流量值Tv(t)

for(每個鏈路LinkVk連接V到它的相鄰路由器Rk)

{V沿著鏈路LinkVk發送指令并開始記錄從鏈路LinkVk收到的數據包的數量｝

(2) 指令發送和接收規則

for 受害者V

if(V在t'時刻收到來自于Linkkv的一個指令)

{V停下來去記錄來自于Linkkv的數據包的數量并將其存儲為通道狀態值Hkv(t，t');}

for 每一個路徑中的路由器 Ri

if(Ri收到來自于Linkji的一個指令并且Ri沒有記錄它的本地狀態)

{ Ri記錄在時刻t的輸出流量值為Ci(t);

Ri設置信道狀態 Hji(ti，k，tji，k) = 0;

For(每一個鏈路Linkik連接Ri到它的鄰接路由器Rk)

{Ri沿著Linkik發送一個指令;

Ri開始記錄除鏈路Linkji外來自于鏈路Linkki的數據包數量;}

If(Ri在tji，k時刻收到來自于Linkji的一個標記并且Ri并沒有記錄它自己的本地狀態)

{Ri停下來去記錄來自于Linkji的數據包數量記錄為Hji(ti，k，tji，k);}

(3) 算法終止規則

for 每個拓撲網絡中參與的路由器Ri

If(Ri已經記錄本地狀態并完成對所有輸入連接的信道狀態記錄)

{Ri發送相關數據(包括它的本地狀態和所有信道狀態值)給受害者V;

Ri結束;}

for 受害者V

If (V已經記錄完本身輸入流量并且對所有的輸入鏈接完成所有的通道狀態記錄，并收到來自于所有的參與路由器的快速數據)

{V結束;｝

快速算法開始調用是當受害者V意識到受到DDoS攻擊時，也就是V發現它的輸入流量超過其承受閾值時。首先，V沿著它的輸出鏈路發送指令給它的鄰接路由器，這些路由器按照上面的偽代碼再發送指令給他們的鄰接路由器，最終，所有參與的路由器都收到了指令，所有的路由器之間協調地發送和接收指令。為分析算法，給出以下引理。

引理 對于任何兩個相鄰的通過Linkji相連的路由器Ri和Rj，快速算法確保Bji=0，并且Aji就是鏈路Linkji的信道狀態，即測量值Hji(ti，k，tji，k)=Aji。

可證得路由器Ri的本地流量累積值為:



Ni(ti，k) = Ci(ti，k)-∑Rj∈U(Ri)[Cj(tj，k)-Hji(ti，k，tji，k)]

(4)

4 算法分析

假設所有路由器都有它自己的本地域，攻擊者的位置在如圖3所示的路由器R3和R4的域中。

圖3 攻擊拓撲圖

圖4為DDoS攻擊追蹤算法進程圖[4]，黑色矩形代表某時刻路由器里記錄其輸出的流量計數器的值，記時刻為ti，k;k代表快速算法的k次觸發，k∈[1，2]。對于受害者V，黑色矩形代表在某時刻V記錄的輸入數據包數量，記時刻為tk，這里k∈[1，2]。為簡單說明，假設所有路由器輸出的流量計數器初始值和累計受害者站點V的輸入流量初始值為零，陰影三角形代表一個路由器或受害者V停止讀取信道狀態時刻，記時刻為tji，k(這里的j表示是來自于Linkji的指令)。圖中白色圈代表一系列正常數據包(如圖中na，nb等);黑色圈代表來自攻擊者的惡意數據包(如圖中的ma，mb等)。

圖4 DDoS攻擊追蹤算法進程時序圖

基于圖4所示數值，可用式(4)來計算路由器或受害者兩個時間點間的累積本地流量，之后用式(2)來獲得每個路由器本地流量的強度，從而判斷攻擊源所在域。本算法的重要特性是只記錄快速算法的兩個時間點之間的數據包。

由圖4可知，數據包na和mb在路由器參與回溯算法之前就被發送了，因此不會被記錄，從而可以得到結論:如果一個對路由器Ri的攻擊者在快速算法的兩個時間ti，1，ti，2之間發送了大量的惡意數據包，就會被追蹤算法所偵測到。

5 結 語

在無全局時鐘的條件下提出了能夠正確監測記錄路由器流量并定位攻擊源位置的DDoS追蹤算法，該算法對在偵測時間范圍外發送的攻擊包還無法進行偵測定位，這將是下一步研究的重點。

參考文獻

[1]CERT Coordination Center.Denial of service attacks[EB/OL]. http: //www. cert. org/tech_tips/denial_of_service. html.

[2]TAYLOR DE， LOCKWOOD J W， SPROULL T S， et al. Scalable IP lookup for programmable routers[C]. New York: IEEE Infocom.， 2002.

[3]QIE X， BAVIER A， PETERSON L， et al. Scheduling computations on a software-based router[C]. Cambridge: ACM SIGMETRICS， 2001.

[4]WONG T Y， LAW K T， LUI J C S， et al. An efficient distributed algorithm to identify and traceback DDoS[J]. Tra-ffic The Computer Journal， 2002， 49: 605-611.

[5]CHANDY K M， LAMPORTL. Distributed apshots:determining global states of distributed systems[C]. [S.l.]: ACM Trans.Comput.Syst.， 1985.

[6]田開琳，李明.一種可靠檢測低速率DDoS攻擊的異常檢測系統[J].現代電子技術，2009，32(7):68-71.