閆 巧，寧土文

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

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

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

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

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

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

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

當(dāng)引入1個二維矩陣進(jìn)行邊采樣時

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

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

其中，B為A的逆矩陣.

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

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

為降低重構(gòu)算法復(fù)雜度，并減少標(biāo)記的總位數(shù)，需選擇一個合適的矩陣A.下面討論A的制約條件.首先，A必須是可逆矩陣，如此才能使式(1)通過 rT=A－1·ρ，ρ=(ρi，ρi+1)T求得采樣邊(ri，ri+1).而標(biāo)記進(jìn)每1個數(shù)據(jù)包中的是式(3)中的［c00c01］和ρd或式(4)的［c01c11］和ρd+1.而在固定矩陣A后標(biāo)記進(jìn)每個數(shù)據(jù)包的是A的行標(biāo)和列標(biāo).行標(biāo)和列標(biāo)都只有兩種情況，且列標(biāo)可用距離信息表示，因此只需1 bit表示行標(biāo).然而，ρi(或ρi+1)也要被標(biāo)記進(jìn)數(shù)據(jù)包中，ρi=c00ri+c01ri+1和ρi+1=c10ri+c11ri+1.其中，［c00c01］和［c01c11］為A的行向量.若ρi(或ρi+1)的數(shù)值很大，則所需標(biāo)記位就很多，因此要使ρi(或ρi+1)盡量的小.根據(jù)以上原則，本研究選擇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)是要標(biāo)記進(jìn)數(shù)據(jù)包中的.所以ρi(或ρi+1)值越小，占用的標(biāo)記位就越少.

引入8 bit的攻擊路徑檢驗，以區(qū)分DDoS多攻擊源下產(chǎn)生的多條攻擊路徑中的邊采樣.由此可知，當(dāng)攻擊路徑數(shù)為m時，其重構(gòu)路徑的邊采樣的誤報率PE=m/(28).然后，參考DPPM的自適應(yīng)概率標(biāo)記方法［7］，采用自適應(yīng)概率對采樣邊進(jìn)行標(biāo)記，可降低重構(gòu)路徑所需數(shù)據(jù)包數(shù).

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

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

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

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

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

1.1 基于矩陣邊采樣的IP追蹤方案的標(biāo)記

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

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

圖2 位預(yù)算與標(biāo)記Fig.2 Bit budget and marking

標(biāo)記算法在每個路由器中都是一樣的.首先，將路由器地址R分成4片，每片8 bit保存在whichs［i］(i∈{1，2，3})中.然后，保存1 個8 bit的路徑檢驗 XORpath=whichs［0］= ⊕whichs［2］ ⊕whichs［3］，并保存1個二維單位矩陣MAT.對每個經(jīng)過路由器的數(shù)據(jù)進(jìn)行包標(biāo)記.首先算出標(biāo)記概率p為從 ［0 1］中取1個隨機(jī)數(shù)x，若x＜p，則對數(shù)據(jù)包進(jìn)行標(biāo)記.其中，b是從{0，1，2，3}中隨機(jī)選取的1個整數(shù)，而a是從{0，1}中隨機(jī)取1個整數(shù).然后，令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追蹤方案的重構(gòu)

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

圖3 MES標(biāo)記算法偽代碼Fig.3 Marking algorithm of MES schema

重構(gòu)算法在受害終端進(jìn)行，首先需將數(shù)據(jù)包的標(biāo)記信息保存下來，然后將相鄰路由的線性累加變換成為分片，再將分片轉(zhuǎn)換成為邊信息，最后將邊信息組合成為攻擊路徑.

2 性能分析

2.1 重構(gòu)路徑所需要的數(shù)據(jù)包數(shù)

重構(gòu)路徑所需數(shù)據(jù)包數(shù)目是評價概率包標(biāo)記算法的重要性能指標(biāo)之一，反映了概率包標(biāo)記算法的效率.

假設(shè)一條攻擊路徑長度為d，由傳統(tǒng)PPM知，受害者重構(gòu)一條長度為d的攻擊路徑所需要的數(shù)據(jù)包數(shù)量N的期望值［5］為

傳統(tǒng)PPM的邊分片數(shù)為8，所以其重構(gòu)路徑所需數(shù)據(jù)包數(shù)約為

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

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

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

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

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

圖4 重構(gòu)路徑所需數(shù)據(jù)包數(shù)Fig.4 The number of packets required during reconstruction

2.2 重構(gòu)路徑算法復(fù)雜度

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

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

2.3 重構(gòu)路徑誤報率

由傳統(tǒng)的PPM算法可知，PPM重構(gòu)是逐邊往回追蹤，其每個邊采樣的誤報率［5］為

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

圖5 重構(gòu)路徑誤報率Fig.5 False alarm rate during reconstruction

結(jié) 語

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

/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ìn)的壓縮邊分段采樣算法［J］.西安電子科技大學(xué)學(xué)報:自然科學(xué)版，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追蹤的分片標(biāo)記方法［J］.計算機(jī)工程與應(yīng)用，2010，46(1):4-7.

［9］ Dean D，F(xiàn)ranklin 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的概率包標(biāo)記仿真平臺的實現(xiàn) ［J］.計算機(jī)工程，2011，37(S395):135-138.