基于矩陣邊采樣的IP追蹤

閆 巧，寧土文

1)深圳大學計算機與軟件學院，深圳518060;2)深圳大學信息工程學院，深圳518060

拒絕服務攻擊 (denial of service attack，DoS)和分布式拒絕服務攻擊 (distributed denial of service attack，DDoS)消耗被攻擊主機的網絡資源，使得正常用戶無法響應網絡請求.由于攻擊容易實施，但難以防范，更不容易查找攻擊源，因此引起了研究者的廣泛重視.IP追蹤技術 (Internet protocol traceback)［1］借助路由器獲得攻擊路徑，反向追蹤到攻擊源，是確定DoS和DDoS攻擊源的有效方法.

根據IP追蹤的主動被動性，現有的IP追蹤技術可分為被動式IP追蹤和主動式IP追蹤兩大類.被動式IP追蹤，即檢測到攻擊后才開始引發追蹤過程，這種追蹤只能在攻擊流保持活動時進行追蹤，一旦攻擊結束，就無法確定IP源，早期的方法包括輸入調試［2］和控制洪泛［3］.主動式 IP追蹤指當攻擊發生時，可根據實時監測的結果重構攻擊路徑，這種追蹤在攻擊結束后仍能確定真實的IP源地址，主要方法包括:基于網際控制信息協議(Internet control message protocol，ICMP) 的 追蹤［4］、數據包標記 (packet marking)追蹤［5-10］和日記分析追蹤［11-12］等.其中，數據包標記追蹤是研究最多的IP追蹤技術，它可分為概率包標記 (probabilistic packet marking，PPM)和確定性包標記(deterministic packet marking，DPM).PPM 方案［5］是一種針對DoS或DDoS的有效IP源追蹤技術.它易于實現，僅使用IP包本身信息，不會產生額外流量，也不會被防火墻或安全策略堵塞，且不需來自互聯網服務提供商 (Internet server provider，ISP)的相互合作，因此備受業界關注［6］.但PPM同時亦面臨著存在最弱鏈、難收斂、重構算法復雜度過高和重構路徑誤報率過高等問題［5］.動態概率包標記 (dynamic probabilistic packet marking，DPPM)方案［7］采用自適應概率對數據包進行標記，使受害終端接收到攻擊路徑上的每個采樣邊的概率相等，從而不存在最弱鏈和難收斂問題，且重構路徑時所需數據包數較少.然而，DPPM仍存在重構路徑算法復雜度過高和重構路徑誤報率過多等問題［7］.

PPM算法的邊采樣是通過增加1個32 bit哈希然后分片，再由相鄰路由器之間的異或來實現的.因此，PPM重構時可使用窮舉法，再用哈希關系檢測采樣邊［5］.當分片為8時，PPM重構算法復雜度為O(m8)，邊采樣的誤報率PE=1－(1－1/232)m8.其中，m為攻擊路徑數.當m=20時，PE≈1.可見，PPM在攻擊路徑上使用相鄰路由之間的異或來進行邊采樣，而PPM在重構時使用了窮舉法，導致PPM重構攻擊路徑時復雜度和誤報率過高.針對PPM的缺陷，本研究改進了邊采樣方法，用1個二維矩陣對相鄰路由進行邊采樣，降低了重構算法的復雜度，通過引入8 bit的多路徑檢驗，降低重構路徑誤報率.又因采用了自適應概率對數據包標記，使受害終端接收到的攻擊路徑上每個采樣邊的概率相等，減少了重構路徑所需數據包.

1 基于矩陣邊采樣的IP追蹤

DoS的攻擊路徑如圖1［8］.由圖1可見，整條攻擊路徑上有d個路由，由于IP包頭中可標記的位數有限，不可能把d個路由的地址全部標記在1個數據包中，所以采用邊采樣，即將相鄰路由之間的邊信息標記進IP包頭中，然后在收集到所有的邊信息后重構整條攻擊路徑.

圖1 DoS攻擊路徑示意圖Fig.1 DoS attack path diagram

當引入1個二維矩陣進行邊采樣時

其中，ri和ri+1分別是DoS攻擊路徑上的第i個和第i+1個路由地址;ρi和ρi+1分別是ri和ri+1的線性累加;c00，c01，c10和 c11是隨機數.

若A可逆，則可在重構時通過rT=A－1·ρ，且ρ=(ρd，ρd+1)T求得采樣邊(ri，ri+1)，即

其中，B為A的逆矩陣.

所以在標記數據包時，要把二維矩陣A和ρ=(ρi，ρi+1)T標記進去，而在每個數據包中只標記式(3)的［c00c01］和ρi，或式(4)的［c10c11］和ρi+1.

為降低重構算法復雜度，使A矩陣固定，那么在重構時就不用計算A的逆矩陣.A固定后，就可用A的行標和列標來索引A中的每1個cij(i，j∈{0，1}).由于A的列標與攻擊路徑上的距離信息相關，因此只需用1 bit來索引A的行標.

為降低重構算法復雜度，并減少標記的總位數，需選擇一個合適的矩陣A.下面討論A的制約條件.首先，A必須是可逆矩陣，如此才能使式(1)通過 rT=A－1·ρ，ρ=(ρi，ρi+1)T求得采樣邊(ri，ri+1).而標記進每1個數據包中的是式(3)中的［c00c01］和ρd或式(4)的［c01c11］和ρd+1.而在固定矩陣A后標記進每個數據包的是A的行標和列標.行標和列標都只有兩種情況，且列標可用距離信息表示，因此只需1 bit表示行標.然而，ρi(或ρi+1)也要被標記進數據包中，ρi=c00ri+c01ri+1和ρi+1=c10ri+c11ri+1.其中，［c00c01］和［c01c11］為A的行向量.若ρi(或ρi+1)的數值很大，則所需標記位就很多，因此要使ρi(或ρi+1)盡量的小.根據以上原則，本研究選擇A為二維單位矩陣，這是因為:首先，二維單位矩陣是可逆矩陣，且其可逆矩陣也為二維單位矩陣;其次，由ρi=c00ri+c01ri+1和ρi+1=c10ri+c11ri+1.其中，［c00c01］和［c10c11］為A的行向量.由此可知，在沒有信息壓縮的情況下，A為單位矩陣，那么［c00c01］(或［c10c11］)就只有1個元素是1，此時ρi=c00ri+c01ri+1(或ρi+1=c10ri+c11ri+1)的值最小，這是因為ρi(或ρi+1)是要標記進數據包中的.所以ρi(或ρi+1)值越小，占用的標記位就越少.

引入8 bit的攻擊路徑檢驗，以區分DDoS多攻擊源下產生的多條攻擊路徑中的邊采樣.由此可知，當攻擊路徑數為m時，其重構路徑的邊采樣的誤報率PE=m/(28).然后，參考DPPM的自適應概率標記方法［7］，采用自適應概率對采樣邊進行標記，可降低重構路徑所需數據包數.

如圖1，假設DoS攻擊路徑上有d個路由，每個邊采樣的標記概率為p(i)(i∈{1，2，…，d})，由PPM算法可知，在受害終端檢測到的相鄰路由采樣邊標記信息的概率為 pL(i)，其中i∈ {1，2，…，d}，則有

若是PPM算法，則相鄰路由邊采樣的標記概率相同，即 p(i)=p(i∈ {1，2，…，d})［5］.此時，在終端檢測到的各采樣邊的概率為

由 pL(i)(i∈{1，2，…，d})可知，pL(1)的概率最小，是最弱鏈.要避免出現最弱鏈，須使pL(1)=pL(2)=… =pL(d)=1/d，由式(5)解得pL(i)(i∈ {1，2，…，d})為 p(i)=1/i，i∈ {1，2，…，d}).將其代入式(5)，得

對僑民的贊美和愛戴在節慶時刻得到集中展示，也是對他們貢獻的回報形式。在節慶中，僑民收獲的無形權力體現為人氣和聲譽——作為“皇后”“公主”的人氣和作為海外僑民作出貢獻的聲譽，來自四面八方的艷羨和敬重在節慶時刻達到極致。僑民的皇后加冕已經形成一種鄉村禮儀規范，維系著僑民與本地留守人員之間的關系。參與其中的僑民和本地留守人員默認維護著這一套鄉村禮儀規范，成為節慶大群體的成員。不認同該“規則”的人也有權選擇不參與這一套禮儀規范。

因此第一個路由的標記概率為1，第二個路由的標記概率為1/2，第d個路由的標記概率為1/d.IP包中的生存時間 (time to live，TTL)值每經過一個路由就減1，因此，設初始化TTL=32，則可用1/(32－TTL)代表每一個路由器上的標記概率.從而使每個路由標記的數據包到達受害終端的概率相等.因此，本研究提出基于矩陣邊采樣的IP追蹤 (IP traceback with matrix edge sampling)方案，即MES方案.

1.1 基于矩陣邊采樣的IP追蹤方案的標記

由上述基于矩陣邊采樣的IP追蹤思想可知，邊標記的過程如式 (1)，將A固定為二維單位矩陣后，只需標記其行標和列標 (與距離信息相關).然后，將每個路由地址分成4片，每片8 bit，引入1個8 bit的攻擊路徑檢驗用以區分DDoS多攻擊源下產生的多條攻擊路徑中的邊采樣.為使重構時需要的數據包數更小，本研究采用自適應概率標記數據包.

如圖2，用1 bit的firstc表示A的行標，用5 bit的distance表示距離信息，同時距離信息與A的列標相關，用log24=2 bit的offset表示分片信息，用8 bit的 sumedge表示采樣邊累加，用8 bit的path表示路徑檢驗，所需標記位共24 bit.因此，可采用IP包頭中的16 bit的IP標識域［5］和8 bit的服務類型 (type of service，TOS)域［9-10］進行標記，恰好24 bit.圖3是標記算法偽代碼.

圖2 位預算與標記Fig.2 Bit budget and marking

標記算法在每個路由器中都是一樣的.首先，將路由器地址R分成4片，每片8 bit保存在whichs［i］(i∈{1，2，3})中.然后，保存1 個8 bit的路徑檢驗 XORpath=whichs［0］= ⊕whichs［2］ ⊕whichs［3］，并保存1個二維單位矩陣MAT.對每個經過路由器的數據進行包標記.首先算出標記概率p為從 ［0 1］中取1個隨機數x，若x＜p，則對數據包進行標記.其中，b是從{0，1，2，3}中隨機選取的1個整數，而a是從{0，1}中隨機取1個整數.然后，令w.sumedge=whichs［b］* MAT［a］［0］，w.distance=0，w.offset=b，w.firstc=a，w.path=XORpath;否則，即x≥p，那么先檢查w.distance是否為0，若是，則令 w.sumedge=whichs［w.offset］ * MAT［w.firstc］ ［1］ +w.sumedge，w.path=w.path⊕XORpath.w.distance都要增1.

1.2 基于矩陣邊采樣的IP追蹤方案的重構

由上述基于矩陣邊采樣的IP追蹤思想可知，MES邊采樣標記對應式(1)，而重構對應式(2)，其中A是關鍵.又因矩陣A為二維單位矩陣，所以其逆矩陣B也為二維單位矩陣.因此，只需要將不同路徑和不同距離的邊信息收集齊后，即可按照式(2)進行邊重構.邊重構完成后就進行多路徑重構.

圖3 MES標記算法偽代碼Fig.3 Marking algorithm of MES schema

重構算法在受害終端進行，首先需將數據包的標記信息保存下來，然后將相鄰路由的線性累加變換成為分片，再將分片轉換成為邊信息，最后將邊信息組合成為攻擊路徑.

2 性能分析

2.1 重構路徑所需要的數據包數

重構路徑所需數據包數目是評價概率包標記算法的重要性能指標之一，反映了概率包標記算法的效率.

假設一條攻擊路徑長度為d，由傳統PPM知，受害者重構一條長度為d的攻擊路徑所需要的數據包數量N的期望值［5］為

傳統PPM的邊分片數為8，所以其重構路徑所需數據包數約為

基于矩陣邊采樣的IP追蹤，即MES方案 (IP traceback with matrix edge sampling，MES)，采用自適應概率標記數據包.路由器標記數據包的概率為1/dA，這里dA是路由器距離攻擊者的跳數，可確保每個路由器標記過的數據包到達受害者的概率都為1/d，這里d為攻擊路徑長度波.如DPPM的重構路徑所需數據包數［7］為

其中，k為分片數;d為攻擊路徑長度.由于基于矩陣邊采樣的IP追蹤采用的是用1個二維單位矩陣對相鄰路由邊進行采樣，而該二維矩陣的兩個行向量是獨立標記進數據包中的，因此需采集到兩個不同的數據包，才能對采樣邊進行重構.假設平均采集X次才能采集到兩個不同的數據包，且采集到的各個數據包的概率都為0.5，則

即平均要采集3次才能采集到兩個概率相等的數據包.所以，該重構路徑所需數據包量為

由MES方案可知，k=4，即

NS2(Network Simulator version 2)環境［13］下仿真結果如圖4.由圖4可見，仿真結果與理論分析一致.

圖4 重構路徑所需數據包數Fig.4 The number of packets required during reconstruction

2.2 重構路徑算法復雜度

假設攻擊路徑上有d個路由，m條獨立的攻擊路徑，由PPM和DPPM的重構算法可知，重構攻擊路徑需進行8md次異或和dm8次哈希運算，即算法復雜度為O(8md+m8d).由于d＜32，所以PPM和DPPM的重構路徑算法復雜度為O(m8)［5-7］.

由基于矩陣邊采樣的IP追蹤重構算法可知，因新方案分片數為4，而重構出相鄰路由邊采樣的運算如式 (2)為4次乘法，若DDoS攻擊路徑上有d個路由，m條獨立的攻擊路徑，則其需進行4×4×d×m次乘法.其中，d是小于32的常數.因此，重構算法復雜度為O(m).由此可知，基于矩陣邊采樣的IP追蹤的重構算法復雜度比PPM和DPPM都要低很多.

2.3 重構路徑誤報率

由傳統的PPM算法可知，PPM重構是逐邊往回追蹤，其每個邊采樣的誤報率［5］為

其中，m為攻擊路徑數.基于矩陣邊采樣的IP追蹤，即MES方案，引入了8 bit的多路徑檢驗，若有m條攻擊路徑，則其邊采樣誤報率PE(MES)=m/28.PPM、DPPM和MES的重構路徑邊采樣的誤報率統計如圖5.由圖5可見，當攻擊路徑m=20時，PE(PPM)≈1，而PE(MES)=20/28=0.078 125，這表明MES方案比PPM方案保持了更低的誤報率.

圖5 重構路徑誤報率Fig.5 False alarm rate during reconstruction

結 語

本研究提出一種邊采樣概率包標記方案，即MES方案.通過引入二維單位矩陣對相鄰路由節點進行邊采樣，降低了重構路徑的算法復雜度，引入8 bit的多攻擊路徑檢驗，降低了重構路徑的誤報率，采用自適應概率對數據包進行標記，從而降低重構路徑所需要的數據包數.理論分析和NS2仿真結果表明，MES方案在防御DDoS攻擊中的表現比其他概率包標記方案更佳.

/References:

［1］ Belenky A，Ansari N.On IP traceback［J］.IEEE Communications Magazine，2003，41(7):142-153.

［2］ Stone R.Center track:an IP overlay network for tracking Dos floods［C］//Proceedings of 2000 USENIX Security Symposium.Denver(USA)，2000:199-212.

［3］ Burch H，Cheswick B.Tracing anonymous packets to their approximate source［C］//Proceedings of 2000 USENIX LISA Conference.Seattle(USA)，2000:319-327.

［4］ Sung M，Xu J，Li J，et al.Large-scale IP traceback in high-speed internet:practical techniques and informationtheoretic foundation ［J］.IEEE/ACM Transactions on Networking，2008，16(6):1253-1266.

［5］ Savage S，Wetherall D，Karlin A，et al.Network support for IP traceback ［J］.IEEE/ACM Transactions on Networking，2001，9(3):226-237.

［6］ YAN Qiao，XIA Shu-tao，WU Jian-ping.Improved compressed edge fragment sampling algorithm ［J］.Journal of Xidian University:Nature Science，2006，33(5):824-828.(in Chinese)閆 巧，夏樹濤，吳建平.改進的壓縮邊分段采樣算法［J］.西安電子科技大學學報:自然科學版，2006，33(5):824-828.

［7］ LIU Jenshiuh，LEE Zhi-Jian，CHUNG Yeh-Ching.Dynamic probabilistic packet marking for efficient IP traceback ［J］.The International Journal of Computer and Telecommunications Networking，2007，51(3):866-882.

［8］ LU Jun-jie，LIU Li.New fragment marking algorithm for IP traceback ［J］.Computer Engineering and Applications，2010，46(13):4-7.(in Chinese)呂俊杰，劉 麗.一種新的IP追蹤的分片標記方法［J］.計算機工程與應用，2010，46(1):4-7.

［9］ Dean D，Franklin M，Stubblefield A.An algebraic approach to IP traceback［J］.ACM Transactions on Information and System Security，2002，5(2):119-137.

［10］ Pegah Sattari，Minas Gjoka，Athina Markopoulou.A Network coding approach to IP traceback［C］//IEEE International Symposium on Network Coding(NetCod).Toronto:［s.l.］，2010:1-6.

［11］ Snoeren A C，Partridge C，Luis A，et al.Hash-based IP traceback［C］//Proceedings of the ACM SIGCOMM 2001 Conference on Applications，Technologies，Architectures，and Protocols for Computer Communication.New York:ACM，2001:3-14.

［12］ Snoeren A C，Partridge C，Luis A，et al.Single-packet IP traceback［J］.IEEE/ACM Transactions on Networking，2002，10(6):721-734.

［13］ YAN Qiao，Ning Tu-wen.Implementation of simulation platform for probabilistic packet marking based on NS2［J］.Computer Engineering，2011，37(S395):135-138.(in Chinese)閆 巧，寧土文.基于NS2的概率包標記仿真平臺的實現 ［J］.計算機工程，2011，37(S395):135-138.