基于自適應包標記的RDDoS攻擊溯源技術研究*

2015-06-23 13:55:22孫鵬，吳慶

通信技術 2015年4期

孫鵬，吳慶

(中國人民解放軍72671部隊，山東省，濟南市，郵編：250022)

孫鵬，吳慶

(中國人民解放軍72671部隊，山東省，濟南市，郵編：250022)

針對RDDoS攻擊溯源問題，在包標記技術的基礎上，提出了一種自適應的標記算法。通過動態調整標記概率，較好地解決了算法收斂速度和路由器負載問題，并針對傳統包標記算法只能對DDoS攻擊進行溯源的問題，設計了一種反射標記算法，使包標記技術能應用于RDDoS攻擊溯源，最后對算法進行了理論分析及模擬研究，通過與經典包標記算法和動態包標記算法進行對比，驗證了其良好的性能。

RDDoS；包標記；溯源

0 引言

根據所需信息和追蹤方法的不同，DDoS攻擊溯源技術大致可以分為包標記方法、基于ICMP的追蹤方法、路由日志法、鏈路測試法等，其中包標記是研究比較多的技術，為廣大的研究者所青睞。該技術由Burch和Cheswick[1]首先提出，而后Savage等人對算法進行改進，研究提出一種概率包標記方法(Probabilistic Packet Marking，PPM)[2]，使用路由器概率的對經過的數據包記入標識信息，并對下級節點進行轉發，處于終點位置的受害者接收到這些標記包后完成攻擊路徑的重構。Jenshiuh等人在概率包標記的基礎上提出一種動態概率包標記算法(Dynamic Probabilistic Packet Marking，DPPM)[3]，用于解決遠端路由器標記的數據包數量過少的問題。包標記算法根據標記信息的不同分為節點采樣標記(Node Sampling)和邊采樣標記(Edge Sampling)。因為節點采樣標記只能針對單一攻擊源的DoS進行溯源，故目前研究焦點主要在于邊采樣標記算法，其中最具代表性的是Savage等人研究提出的分片標記算法(Fragment Marking Scheme，FMS)和Song等人研究提出的高級包標記算法(Advanced Marking Scheme，AMS)[4]，他們采用異或計算的方法將IP分段標記信息壓縮存放，使得同一標記區域內含有相鄰兩個路由器IP地址信息，節省了標記字段所需的空間。

基于包標記的溯源算法具有較好的優越性，但各算法均無法對反射型分布式拒絕服務攻擊(Reflected Distributed Denial of Service，RDDoS)攻擊進行溯源，且給路由器帶來了很多額外的負擔。針對這些問題，本文提出了一種基于自適應包標記的RDDoS攻擊溯源技術，設計了一種反射標記算法，使經典的包標記算法可以對DDoS攻擊進行溯源。同時在動態概率包標記算法的基礎上，設計了覆蓋標記與不覆蓋標記混合的自適應標記算法，減少了標記包數量，降低了路由器負載。

1 基于自適應包標記的RDDoS攻擊溯源算法

1.1 算法總體設計

本文設計的針對RDDoS攻擊的溯源算法由三部分組成：一是自適應標記算法，主要應用于路由器節點上，對自身轉發和產生的數據包以一定概率標記上本節點的IP地址信息，而后向下級節點傳遞；二是反射標記算法，主要運行于反射節點，即網絡中的DNS服務器等可能被當作攻擊反射器的主機，用于解決RDDoS攻擊中標記信息的存儲和延續；三是路徑重構算法，由受害者主機運行，用于統計和分析最終到達受害者的攻擊包，完成標記信息重組和攻擊路徑重構，確定和找出攻擊源。各算法運行的位置如圖1所示。

圖1 RDDoS攻擊溯源算法運行位置示意

1.2 自適應標記算法

在DPPM算法中，路由器對所有數據包以一定的概率重復標記，對路由器造成了額外負擔，為解決這個問題，本文提出一種自適應標記算法，路由器自主確定標記概率，并選擇是否覆蓋數據包舊有標記，在路徑長度到達一個定值之前，數據包上攜帶的已有標記不被后續路由器覆蓋，在超出這個長度之后再使用覆蓋標記的方法，并在算法上保證每個路由器標記的數據包等概率的到達受害終端。

(1)標記概率的計算

假定(A，R1，R2，…，Rd，V)是攻擊中的其中一條路徑，A是攻擊節點，V是受害節點，R1，…，Rd是網絡中的路由器，d是由攻擊節點路由到受害節點的跳數。假定路由器Ri以概率pi標記，受害者接收到由Ri標記的數據包的概率為qi，在不覆蓋標記的條件下，為使重構時所需的數據包的數量最少，需要受害者收到每個路由器標記數據包的概率都相等，且都為1/d。

即：q1=q2= … =qd= 1/d

即：p1= (1-p1)p2= (1-p1)(1-p2)p3= … = (1-p1)(1-p2)…(1-pd-1)pd= 1/d

推導得：

p1=1/d,p2=1/(d-1),pi=1/(d-i+1),… ,pd=1

路由器標記數據包時并不清楚是否發生了攻擊，也不會知道是發生了DDoS攻擊還是RDDoS攻擊，更不知道攻擊路徑的長度d，而僅僅是計算概率和執行標記動作。在DDoS情況下，最大路徑長度一般不大于32，路由器的標記概率直接采用pi=1/(d-i+1)，在RDDOS情況下，最大路徑長度超出32的部分我們以Pi=1/i進行覆蓋標記，即：

(2)標記信息的存放

標記信息的存放類似壓縮邊分段采樣算法(Compressed Edge Fragment Sampling)，利用IP包頭中未使用的位置來記錄標識追蹤信息。IP報頭中的RF位保留未用，可以用作標志位，同時在現有TCP/IP協議的實現中，未做強制使用的位空間還有服務類型(8位)和認證域(16位)，所有可供利用的空間計有25位。

圖2 標志位在IP報頭中的存儲

圖中的標志位中，distance域(6位)表示產生標志的路由器離攻擊者的跳數，hash域(7位)用于記錄由邊計算出的hash值，edge域(8位)用于存儲路由器節點或者由兩個路由器構成的一條邊的信息，offset域(2位)表示節點/邊被分割成的4段中哪一段IP信息，flag域(2位)用于區分數據包是否載有標記和是否曾被邊界路由器標記。Flag域被初始化為00，表示未做任何標記；flag被賦值01，表示數據包被邊界路由器之外的路由器標記；flag被賦值10，表示該數據包被邊界路由器標記。

(3)標記算法的具體實現

自適應標記算法根據攻擊路徑長度設定兩個標記階段：一是當路徑長度不超過32時，路由器對轉發的數據包不重復標記；二是路徑長度大于32時，路由器采用覆蓋標記算法。整個標記過程為：

1) 路由器進行標記概率計算。首先根據距離域d計算產生標記概率p，并計算出一個處于(0,1]范圍的隨機數u，當0

2)當flag=00時，表明該數據包不曾被做過標記，從路由器IP的4個分段中隨機選擇一段標記在edge域，并將offset置為相應的偏移量；計算該路由器32位IP地址的7位hash值(為減少hash沖突，可適當增加hash位數，IP包頭中的部分未使用位可提供存儲)，結果存入hash域；若路由器是邊界路由器，置flag域為10，若不是則置為01；將距離域d置為0。

3) 若flag!=0且d=0，表示相鄰的上游路由器已標記過該數據包，根據offset段的值取出edge值與路由器對應IP地址段相異或，將結果記錄到edge域并將距離域d加1。

4)若flag!=0且d> 31，可以進行覆蓋標記，從路由器IP的4個分段中選擇一段標記在edge域，并將offset置為相應的偏移量；將該路由器32位IP地址hash成7位，存儲到hash域；將flag域和距離域d分別置為01和0。

5) 當u>p時，若flag!=0且d=0，根據offset段的值取出edge值與路由器對應IP地址段相異或，將結果記錄到edge域并將距離域d加1；若flag!=0且d!=0，將距離域d增加1；若flag=0不做任何操作，直接轉發數據包。

1.3 反射標記算法設計

(1)反射器存儲結構

反射器中的存儲結構基于Bloom Filter進行設計，保留了存儲高效和查找快速的優點(文獻[5]中詳細分析了Bloom Filter結構的效率及錯誤率)，并進行功能改進使之能應用于包標記的存儲。結構中包含了一個位數組和一組鏈表，使用k個hash函數對元素進行hash運算，將運算結果用作鏈表索引。鏈表由一組PACKET標記節點組成，每個標記節點由mark、count和下一元素指針組成，記錄曾出現過的標記。數據結構如圖3所示。

圖3 反射器存儲結構

其中mark用于存儲標記數據包中攜帶的標記信息，count用于記錄多少個攜帶這種標記的數據包到達了反射器，記錄數值的目的是為了在合適的時機刪除此PACKET記錄，收回占用的存儲空間。

(2)反射器標記算法

反射器標記算法由存儲標記和復制標記兩部分組成，存儲標記是指將路由器標記的數據包的摘要和標記存入反射器存儲區域，復制標記是從反射器存儲區域提取標記，并復制到回應包頭部的相應區域。流程如圖4所示。

圖4 反射器存儲及復制算法流程

(3)路徑重構算法

當受害端收集到足夠的標記數據包后，由數據包頭部提取出標記，對各標記重新分組和統計數量，最后重構出攻擊路徑。算法如下：

1) 受害端提取出數據包頭部的標記信息；

2) 按距離域對標記信息分組，同一組中放置距離域相等的標記；

3) 對距離域相等的組中的標記按hash函數進行分組，hash值相等的歸為一組；

4) hash值相等的組中按offset值再次分組，共分為4組；

5) 從這4組offset中各取一個IP段，按偏移量標識的次序重新組成完整IP地址；

6) 重復5，直到找出所有這種組合；

7) 按距離值從小到大依次從不同距離域分組中拿出IP地址，先是用距離值最小的IP地址去異或次小的IP，得到的結果再去異或距離值再小一點的，重復完成所有距離值的IP地址。

8) 異或得到的各值就是攻擊路徑上的各路由器IP，按距離的由小到大依次排列這些集合中的IP地址，結果序列即為由攻擊端到受害端的攻擊路徑。如果攻擊是多源的反射型分布式拒絕服務攻擊，可計算出多條攻擊路徑。

2 性能分析

2.1 兼容性分析

兼容性是指對網絡協議的改造與當前網絡協議是否兼容。自適應標記算法重載了IP報文頭部的identification(16位)、tos(8位)和rf(1位)三個區域，identification域用于處理網絡層的分段，現在的網絡應用一般都有MTU自動發現功能以減少分段的發生，實際網絡應用中分段發生的概率只有不到0.25%[6]，對identification域的占用不會影響絕大多數的網絡應用；tos域表示服務類型，在RFC791中規定了tos域的意義，后來RFC1394對tos域定義了新的意義，再后來RFC2745規定tos域被用作QoS服務，TOS域的使用一直沒有統一嚴格的規定，可以用來作為標記區域；rf位在IP報頭中用作保留位。對這三個區域的重載對現行IP協議不會產生太大影響，有著良好的兼容性。

2.2 收斂性分析

PPM算法中，假設攻擊路徑長度為d，路由器的標記概率為p，最遠的路由器產生的標記成功跟隨數據包到達攻擊端的概率為：q=p(1-p)d-1，由Coupon Collector Problem問題求解[7]，可知PPM算法構建出完整攻擊路徑需要的數據包數量的數學期望：

其中k為每個IP地址分片數量，當d=32，p=0.04時，需要1 700個數據包才能重構出完整路徑。

DPPM算法中，每個路由器標記數據包成功到達受害端的概率相同，為1/d，重構完整路徑需要數據包數量的數學期望為：

EDPPM(x)

當d=32，k=4時，DPPM算法需要620個數據包來重構完整路徑。

本文提出的自適應包標記算法中，當距離值d小于32時，因為我們設定路徑長度是32，故新算法重構完整路徑需要數據包數量的數學期望要大于DPPM，當d等于32時，新算法的收斂性與DPPM相同，當d大于32時，新算法收斂性與DPPM持平，都趨于理想值。由此得出結論，EDPPM(x)≤E新(x)

2.3 路由器負載分析

在所有使用包標記進行攻擊源追蹤的方案中，都會對路由器造成一定額外負擔，主要體現在對大量數據包做標記上面。PPM算法存在弱收斂的問題，路徑的重構需要大量攜有路由器標識的數據包，整體來看所有路由器負載都很重；在DPPM算法中，路由器根據距離值動態計算標記概率，離攻擊端越近，標記越頻繁，并且全程攻擊鏈路的下游路由器都可能覆蓋上游路由器的標記，額外增加了標記負擔；本文的新標記算法在32跳之前路由器不覆蓋標記，免除了PPM和DPPM中的額外標記負擔，因而整體標記負載優于PPM和DPPM算法。

3 模擬實驗

3.1 收斂性實驗

考慮到需要對比不同路徑長度下重構用到的數據包數量，本文采用線性拓撲結構進行模擬實驗。如圖5所示，線性結構每次使用不同的結點數量，并在做APPM算法實驗時設定其中一個結點做為反射器，比較無反射器時PPM算法、APPM算法和有反射器時新算法重構完整路徑用到的數據包數量。

圖5 線性結構

從節點數為5開始實驗，在每個相同的結點數上對PPM、DPPM和新算法各做8組，至結點數為63為止，每組8次取得的結果中去掉最大值和最小值后取平均，得到路徑長度與攻擊包數的關系曲線如圖6所示。

圖6 各算法在不同路徑長度下重構所需數據包的數量

由實驗結果知，路徑長度不超過32時，新算法表現優于PPM算法，稍遜于DPPM算法；在路徑長度超出32跳之后，新算法性能與DPPM算法持平，優于PPM算法。

3.2 路由器負載實驗

為了定量計算各標記算法對路由器造成的額外負擔，對比出各算法在路由器負載中的性能表現，我們統計各算法在完成路徑重構時，所有路由器做出標記動作的總次數。具體實現是在數據包中加入一個mark_count變量，路由器對數據包做出一次標記，mark_count值就加一，所有的mark_count值在受害端匯總得出最終結果。如圖7所示。

圖7 各算法路由器標記總次數對比

由圖可知，相比PPM和DPPM算法，新算法在標記數據包的數量上要少很多，證明了新算法的減輕路由器負載上比PPM和DPPM算法有明顯的優勢。

4 結語

本文針對RDDoS攻擊提出一種基于包標記算法的追蹤方案，該方案根據路徑長度采用自適應標記策略，增強了收斂性并減小了路由器負載，同時在反射器上采用Bloom Filter原理建立了一種標記信息存儲結構，降低了存儲消耗并加快了存取速度。該方案同時適用于DDoS和RDDoS攻擊溯源，具有普遍適用性。在攻擊者控制了網絡中某個路由器，并對該路由器標記信息進行篡改時，如何能檢測出標記信息的偽造是后續需要進一步研究的。本文以已檢測到攻擊作為前提條件，在后續工作中將考慮引入實際的檢測技術，實現檢測與追蹤聯動。

[1] Burch H,Cheswick B. Tracing Anonymous Packets to their Approximate Source[C]. Proceedings of the 14th Conference on Systems Administration, 2000 LISA XIV, New Orleans, Louisiana, USA, 2000.

[2] Stefan Savage, David Wetherall, Anna Karlin, et al. Network Support for IP Traceback[J]. IEEE/ACM Transon Networking, 2001, 9(3):226-237.

[3] Liu Jenshiuh，Zhi Jianlee，Chung Yehching. Dynamic Probabilistic Packet Marking for Efficient IP Traceback[J].Computer Networks, 2007, 51:866-882.

[4] Song D, Perring A. Advanced and Authenticated Marking Schemes for IP traceback[C]. Anchorage, Proceedings of IEEE INFOCOM, Alaska USA, 2001, 2: 878-886.

[5] Broder A, Mitzenmacher M. Network Applications of Bloom Filters: A survey[J]. Internet Mathematics, 2005,1(4):485-509.

[6] Stoica I,Zhang H. Providing Guaranteed Services Without Per Flow Management. In:Proceedings of the 1999 ACM SIGCOMM Conference,pages 8l-94,Boston,MA,Aug.1999.

[7] 郝堯, 陳周國, 蒲石等. 多源網絡攻擊追蹤溯源技術研究[J]. 通信技術, 2013, 46(12):77-81. HAO Yao, CHEN Zhou-guo, PU Shi,et al. Research On the Tracing Technology of Multi-source Network Attack[J]. Communications Technology,2013,46(12):77-81.

RDDoS Attack Source-Tracing Technology based on Self-Adaptive Packet-Marking

SUN Peng， WU Qing

(Unit 72671 of PLA, Jinan Shandong 250022, China)

Aiming at the source tracing of RDDoS attack, a self-adaptive algorithm based on package-marking technology is proposed. By dynamically adjusting marking probability, convergence speed of the algorithm and payload of the router are fairly solved. Traditional packet-marking algorithm can only trace the source of DDoS attacks, and in light of this, a reflective marker algorithm is proposed and designed, thus enabling the package-marking technique to be applied in the source tracing of RDDoS attack.

RDDoS; package-marking; source tracing

date:2015-01-10；Revised date：2015-03-19

文獻標志碼：A 文章編號：1002-0802(2015)04-0478-06