作者：饑餓加菲貓（QQ120474） 
      iojhgfti@hotmail.com 

摘要: 針對互聯(lián)網(wǎng)上日益猖獗的拒絕服務(wù)攻擊（DoS），分析了傳統(tǒng)的隨機數(shù)據(jù)包標記算法的性能缺陷，提出一種新的基于散列消息鑒別碼的返回跟蹤算法HPPM，通過分析其性能指標，說明該算法提高了返回跟蹤DoS攻擊的效率和準確性。 
感謝幫過我的幾個高手袁哥[nsfocus], sunwear[E.S.T] , isno[xfocus] , scz[nsfocus] 
1．引言 
    拒絕服務(wù)攻擊，簡稱DoS(Denial-of-Service)，是一種常見的黑客攻擊行為。這種攻擊行為通過發(fā)送帶有虛假源地址的數(shù)據(jù)包請求，使網(wǎng)絡(luò)服務(wù)器充斥大量等待回復(fù)的信息,消耗網(wǎng)絡(luò)帶寬或系統(tǒng)資源,使網(wǎng)絡(luò)或系統(tǒng)服務(wù)負載過重，服務(wù)質(zhì)量下降，直至癱瘓而停止正常的服務(wù)。有時,黑客為了提高攻擊的效果,往往會聯(lián)合多個攻擊站點向受害者發(fā)動進攻。由于DoS攻擊易于實施、難于防御，而且很難返回跟蹤攻擊源，使之成為一個嚴重侵擾網(wǎng)絡(luò)服務(wù)提供商、政府機關(guān)和金融證券等機構(gòu)正常運作的安全問題。 
2．IP返回跟蹤相關(guān)技術(shù) 
為了徹底消除DoS攻擊，必須追根溯源，找到真正的攻擊機器或攻擊者。這種方法被稱為IP返回追蹤技術(shù)（IP Traceback）。由于DoS攻擊者在發(fā)送攻擊數(shù)據(jù)包時往往會偽造源地址，使得IP返回追蹤的難度很大。常用的IP返回追蹤方法有：入口過濾（Ingress Filtering）、連接測試（Link Testing）、ICMP追蹤[7]、登錄分析（Logging）、源路徑隔離引擎（SPIE）、IPSec追蹤，以及隨機數(shù)據(jù)包標記追蹤（PPM）[2]。各種追蹤技術(shù)之間的性能比較，如表1所示。 
    管理負擔     網(wǎng)絡(luò)負擔     路由器負擔     分布式能力     事后追蹤能力     預(yù)防/反應(yīng) 
進入過濾     中等     低     中等     N/A     N/A     預(yù)防 
輸入調(diào)試     高     低     高     好     差     反應(yīng) 
控制流     低     高     低     差     差     反應(yīng) 
登陸分析     高     低     高     極好     極好     反應(yīng) 
ICMP追蹤     低     低     低     好     極好     反應(yīng) 
數(shù)據(jù)包標記     低     低     低     好     極好     反應(yīng) 
表1 幾種IP返回追蹤技術(shù)的性能比較[2] 
3．HPPM IP返回跟蹤算法 
    3.1     PPM算法（Probabilistic Packet Marking） 
隨機數(shù)據(jù)包標記算法PPM的主要原理如下：路由器以一定的概率p（通常是1/25）[2]，用其IP地址或IP地址的一部分隨機標記經(jīng)過它的數(shù)據(jù)包。當發(fā)生DoS攻擊時，受害者根據(jù)其收到的攻擊數(shù)據(jù)包中的標記信息，重建攻擊路徑。使用PPM算法，路由器負擔較小，采用標記邊壓縮和分片技術(shù)大大降低了額外的網(wǎng)絡(luò)流量。而且，該方法可以在攻擊結(jié)束以后對攻擊源進行追蹤。PPM對單源DoS攻擊，有較好的追蹤效果。 
但是，由于其自身缺陷，PPM算法無法很好地返回跟蹤DDoS攻擊（Distributed–Denial–of–Service）。首先，由于路由器以概率p隨機標記數(shù)據(jù)包，就給攻擊者以可乘之機，將偽造的標記信息寫入攻擊數(shù)據(jù)包的報頭中（一般是Identifier字段），只要該數(shù)據(jù)包一直不被其經(jīng)過的路由器標記，直至目標主機，就能在攻擊路徑中偽造一條邊路徑，阻止受害者跟蹤真正的攻擊源。其次，為了節(jié)省存儲空間，減小網(wǎng)絡(luò)負擔，PPM采用了邊標記壓縮和分片存儲技術(shù)。但是，分片存儲可能導(dǎo)致受害者將本不屬于同一數(shù)據(jù)包的分片組合在一起，從而生成錯誤的邊路徑。而標記的邊壓縮方法主要依據(jù)(a○+b)○+b=a(a、b分別是攻擊路徑上相鄰兩個路由器的IP地址)，將顯著加劇這一效果，進一步生成錯誤的攻擊路徑。當發(fā)生DDoS攻擊時，由于同一距離存在多個攻擊者，而產(chǎn)生爆炸效果，影響將更加嚴重[2]。 
3.2     HPPM算法 
針對PPM算法的上述缺陷，我們提出了一種基于散列消息鑒別碼HMAC的數(shù)據(jù)包標記算法HPPM，并采用新的標記重疊分片策略，以提高IP返回跟蹤DoS攻擊（特別是DDoS攻擊）的性能。 
在該算法中，路由器Ri以概率p隨機對經(jīng)過它的數(shù)據(jù)包進行標記，標記信息包括Ri的IP地址和下一跳路由器Rj的IP地址，總共64位。為了節(jié)省標記存儲空間，不給用戶帶來過多影響，算法使用IPv4首部中的16位標識符字段（Identifier），1位閑置的標志位（Flags）[1]和13位片位移字段（據(jù)統(tǒng)計，目前少于0.25%的數(shù)據(jù)包需要分片[2]），以及一般很少使用的8位TOS字段（Type-of-Service）[1],總共38位，來存儲標記分片信息。64位標記信息被分成k＝8片，每片占用8位，分片偏移值占log2k＝3位，Ri到目標主機的距離值占5位（25－1＝31跳，適用于目前絕大多數(shù)網(wǎng)絡(luò)[2]），用于驗證的HMAC值占22位。 
散列消息鑒別碼，簡稱HMAC，是一種基于消息鑒別碼MAC（Message Authentication Code）的鑒別機制。使用HMAC時,消息通訊的雙方，通過驗證消息中加入的鑒別密鑰K來鑒別消息的真?zhèn)危籋MAC還引人了一個散列函數(shù)H，對消息進行加密，進一步確保消息鑒別的安全性和有效性。HMAC的具體計算方法如下： 
HMAC(M,K) = H(K○+opad, H(K○+ipad, M )) 
其中，ipad = 字0x36重復(fù)B次，opad = 字0x5C重復(fù)B次，M = 待加密的消息字符串，B = 消息字符串的字長。關(guān)于HMAC更詳細的內(nèi)容，請參考文獻RFC 2104[6]。 
在HPPM算法中，我們采用一次性口令機制OTP（One-Time Password）[4][5]，先讓每個路由器Ri生成一組私有密鑰序列{Kij}（j=0、1、2……）。這組私有密鑰序列通過單向散列函數(shù)f生成，并具有以下規(guī)則：Kij-1 =f(Kij)。由于函數(shù)f是單向的，所以由最新的密鑰Kij可以依次推出在它以前生成的所有Kij-1、Kij-2……Ki0，但根據(jù)已有的密鑰卻推不出下一個密鑰，這就確保了他人無法偽造Ri的密鑰。路由器Ri每經(jīng)過一段固定的時間間隔，就根據(jù)上述方法更換一次私有密鑰Ki，然后將剛剛停止使用的密鑰通過可靠的方式發(fā)布出去。當數(shù)據(jù)包P通過Ri時，Ri 使用HMAC函數(shù)H和當前私有密鑰Ki，對Ri 的IP地址和P的目的地址進行加密，即：H(M,Ki),其中，M = IP(Ri)+IP(destination)。具體的標記步驟如下： 
Marking procedure at router Ri: 
let m be the marking massage ip(Ri) + ip(Rj) 
let k be the number of fragments in m 
let H be the HMAC function 
let Ki be the private key of Ri at current time interval    
for each packet w 
let x be a random number from [0..1) 
if x < p then 
let hmac be the HMAC value of IP(Ri)+IP(w.destination) 
    hmac := H( IP(Ri)+IP(w.destination), Ki) 
let o be a random integer from [0..k-1] 
let f be the fragment of m at offset o 
write f into w.frag 
write 0 into w.distance 
write o into w.offset 
write hmac into w.hmac 
else 
increment w.distance 
以下將討論受害者重建攻擊路徑的過程。當受到DoS攻擊時，受害者開始收集標記分片，并記錄其到達時間。我們假設(shè)攻擊者發(fā)送大量的攻擊數(shù)據(jù)包，那么受害者就能收集到足夠多的標記分片，然后根據(jù)分片的偏移值，將具有相同攻擊距離d和hmac值的分片重組，生成邊路徑，進而生成整個攻擊路徑。由于攻擊者可能偽造標記數(shù)據(jù)包，干擾返回跟蹤過程，因此需要對生成的邊路徑鑒別真?zhèn)巍＞唧w鑒別方法是：受害者與路由器Ri（服務(wù)提供商）聯(lián)系，取得Ri最新的私有密鑰K，然后根據(jù)K和數(shù)據(jù)包P到達時間（需要考慮延時），使用相同散列函數(shù)f計算出Ri標記P時使用的私有密鑰Ki；再根據(jù)Ri和自身的IP地址，以及Ki，計算出HMAC值與標記數(shù)據(jù)包中的HMAC值進行比較，一致則說明該邊路徑有效，否則將其丟棄。重建攻擊路徑的具體過程如下： 
Path reconstruction procedure at victim v: 
let FragTbl be a table of tuples (frag, offset, distance, hmac, time) 
let G be a tree with root v 
let edges in G be tuples (start,end,distance,hmac,time) 
let maxd := 0 
let last := v 
for each packet w from attacker 
let rectime be the time when v receives the packet w 
FragTbl.Insert(w.frag,w.offset,w.distance,w.hmac,rectime) 
if w.distance > maxd then 
maxd := w.distance 
for d := 0 to maxd 
for all ordered combinations of fragments having the same hmac value at distance d 
construct edge z( IP(Ri), IP(Rj), w.distance, w.hmac, rectime) 
// Start of HMAC authentication 
let K be the private key of Ri at current time interval 
let Ki be the private key of Ri at the time interval when Ri marked the packet w 
let f be the function to get Ki according to K and rectime 
Ki := f(K, rectime) 
if w.hmac = H(IP(Ri)+IP(v), Ki) 
insert edge z( IP(Ri), IP(Rj), w.distance) into G 
        // End of HMAC authentication 
remove any edge (x,y,d,hmac,time) with d ≠ distance from x to v in G 
extract path (Ri..Rj ) by enumerating acyclic paths in G 
4．HPPM算法性能分析 
4.1     攻擊收斂包數(shù) 
根據(jù)[2]，受害者收到距離為d的路徑上最遠處路由器發(fā)來的標記數(shù)據(jù)包的概率是：p(1-p)d-1。保守假設(shè)受害者收到該路徑上任一路由器發(fā)來標記數(shù)據(jù)包的概率都與最遠距離d處相同，并且相互獨立，因此受害者收到的任一數(shù)據(jù)包被該數(shù)據(jù)包途經(jīng)路徑上某些路由器標記過的概率，將具有期望值：1/dp(1-p)d-1。 
根據(jù)coupon-collector問題[8]，受害者收到的從距離為d的路徑上發(fā)來的數(shù)據(jù)包中，包括所有d個路由器中每個路由器發(fā)出的至少一個標記數(shù)據(jù)包，所需要接收的數(shù)據(jù)包數(shù)，具有以下期望值：1＋d/(d-1)+d/(d-2)+……+d/2+d = d(ln(d)+O(1))?？紤]到每個標記數(shù)據(jù)包被分成k片，總共有kd片，則上述值為kd(ln(kd)+O(1))。因此，重建距離為d（包含d個路由器）的攻擊路徑所需要的數(shù)據(jù)包數(shù)N，具有期望值： 
E(N)<kd(ln(kd)+O(1)) 
1/dp(1-p)d-1≈k 
ln(kd)/p(1-p)d-1 
因此，該算法攻擊收斂包數(shù)與PPM邊標記算法相同[2]。 
4.2     健壯性 
    在PPM算法[2]中，對于輸出長度為h的散列隨機函數(shù)，受害者接受任一候選邊路徑的概率是1/2h。假設(shè)有m個攻擊者，則在一定距離d處，最壞情況下將有m個獨立的路由器。因此，在距離受害者d處，本不在實際攻擊路徑中的任意候選邊路徑被受害者接受（即：產(chǎn)生了正誤差[3]）的最大概率將是：1-(1-1/2h)n（其中n=mk）[2]。因為，最壞情況下，距離d處將有mk個標記分片。當k值或m值很大時，這一概率也將變得很大。而HPPM算法使用的HMAC鑒別機制，可以十分有效地鑒別攻擊者偽造的邊路徑，將偽造的邊路徑從候選邊路徑中過濾掉，從而充分減小了算法產(chǎn)生的正誤差，提高了返回跟蹤的準確性。 
4.3     路由器負擔 
由于采用HMAC和一次性口令機制來加密攻擊數(shù)據(jù)包中的邊標記，因此中間路由器無須承擔PPM算法中每個路由器對其IP地址和已有邊標記進行的異或運算(a○+b)○+b。而HMAC的計算過程簡單，擴展性也很好，當發(fā)現(xiàn)或需要運算速度更快或更安全的散列函數(shù)時，幾乎不用修改，就可以很容易地實現(xiàn)底層散列函數(shù)的替換，參閱文獻[6]。為了使數(shù)據(jù)包標記過程更加安全，路由器需要周期性更換其用于加密邊標記的私有密鑰。這個周期需要進行適當選擇，周期太短將給路由器帶來額外負擔，且不利于與受害者的同步，周期太長又影響算法安全性，可以考慮把10秒作為其數(shù)量級[3]。 
4.4     受害者負擔 
由于使用了一次性口令機制，受害者需要獲取上游路由器加密邊標記時使用的私有密鑰。一種可行的方法是，上游路由器將最新密鑰通過可信渠道發(fā)布（如：發(fā)布在網(wǎng)站上），受害者鑒別邊標記真?zhèn)螘r，只需下載該路由器的最新密鑰，根據(jù)最新密鑰就能推算出該路由器以前加密邊標記時使用的所有密鑰。這一過程可以在常數(shù)時間內(nèi)完成。 
4.5     算法局限性 
HPPM算法，要求受害者掌握網(wǎng)絡(luò)拓撲結(jié)構(gòu)，具有其上游路由器的地圖，這在一定程度上限制了算法的發(fā)展。受害者與中間路由器關(guān)于密鑰的同步過程還需要進一步考慮。 
5．總結(jié)及未來工作 
本文描述了一種新的基于散列消息鑒別碼HMAC的隨機數(shù)據(jù)包標記算法HPPM，該算法用于返回跟蹤DoS攻擊的攻擊源，能夠充分減小由于攻擊者偽造數(shù)據(jù)包標記而帶來的誤差，提高了返回跟蹤的安全性和準確性。然而，該算法還有不完善的地方，比如：與大多數(shù)返回跟蹤算法一樣，HPPM算法是一種反應(yīng)型跟蹤算法，即：只有確實發(fā)生了攻擊，才能進行跟蹤。并且，該算法實際上無法跟蹤到真正的攻擊源，只能返回跟蹤到最接近攻擊源的邊界路由器。這些問題都有待進一步研究。 

參考文獻 
[1] W.Richard Stevens著，范建華 胥光輝 張濤 等譯，謝希仁校，《TCP/IP詳解——卷1：協(xié)議》[M]，第1版，北京：機械工業(yè)出版社，2000年4月，第24－27、111－112頁. 
[2] S.Savage, D.Wetherall, A.Karlin and T.Anderson. Practical network support for IP traceback[C]. In ACM SIGCOMM, Stockholm, Sweden, 2000, 295-306. 
[3] D.X.Song and A.Perrig. Advanced and authenticated marking schemes for IP traceback[C]. In IEEE INFOCOMM, April 2001. 
[4] N.Haller, The S/KEY One-Time Password System[Z], Internet RFC 1760, February 1995. 
[5] N.Haller, A One-Time Password System[Z], Internet RFC 2289, February 1998. 
[6] H.Krawczyk, M.Bellare, and R.Canetti, HMAC: Keyed-Hashing for Message Authentication[Z], Internet RFC 2104, February 1997. 
[7] S.M.Bellovin. ICMP Traceback Messages[Z]. Internet Draft:draft-bellovin-itrace-00.txt.March 2000. 
[8] W.Feller. An Introduction to Probability Theory and Its Applications[M]. 2nd edition, volume 1. Wiley and Sons. 1966. 
[9] K.Park, H.Lee. On the Effectiveness of Probabilistic Packet Marking for IP Traceback under Denial
 of Service Attack[C]. In IEEE INFOCOM, 2001.