胡蓓蓓，彭艷兵，程光

HU Beibei1,PENG Yanbing2,CHENG Guang3

1.武漢郵電科學(xué)研究院，武漢430074

2.烽火通信科技股份有限公司，南京210019

3.東南大學(xué)計(jì)算機(jī)科學(xué)與工程系，南京211189

1.Wuhan Research Institute of Posts and Telecommunications,Wuhan 430074,China

2.Fiberhome Communication Technologies Co.Ltd,Nanjing 210019,China

3.Department of Computer Science and Engineering,Southeast University,Nanjing 211189,China

1 引言

域名系統(tǒng)（DNS）是標(biāo)識計(jì)算機(jī)電子方位的“GPS”，它將域名和IP地址相互映射成一個(gè)分布式數(shù)據(jù)庫。一次DNS查詢的失?。―NS query failure，以下簡稱DNS failure）通常意味著無法在數(shù)據(jù)庫中找到所查域名對應(yīng)的資源記錄。出現(xiàn)DNS failure可能是由DNS配置不當(dāng)或域名輸入錯(cuò)誤引起，但前者發(fā)生的機(jī)率非常小，后者產(chǎn)生的數(shù)據(jù)量非常小。相關(guān)事件與研究表明一些網(wǎng)絡(luò)異?；顒訒?dǎo)致大量DNS failure的出現(xiàn)：

2009年5月18日域名托管商DNSPod的一臺承擔(dān)著暴風(fēng)影音等十萬個(gè)域名解析工作的服務(wù)器因遭到攻擊而失效離線，19日數(shù)量巨大的重復(fù)的baofeng.com查詢在得不到響應(yīng)的情況下轉(zhuǎn)向各省遞歸服務(wù)器，19日晚這些服務(wù)器陸續(xù)因超負(fù)荷而崩潰，引發(fā)大規(guī)模網(wǎng)絡(luò)癱瘓[1]。

Yadav S[2]、Jiang N[3]等學(xué)者研究發(fā)現(xiàn)僵尸網(wǎng)絡(luò)等異?；顒邮荄NS failure的主要來源。考慮到采用domainflux技術(shù)的僵尸主機(jī)會對特殊算法生成的域名進(jìn)行逐一訪問而有大量DNS failure出現(xiàn)，前者借助域名的熵值計(jì)算和訪問的時(shí)間相關(guān)性來分離網(wǎng)絡(luò)流量中的惡意域名與合法域名，實(shí)驗(yàn)表明該方法對Conficker僵尸網(wǎng)絡(luò)具有較好的檢測效果；后者為區(qū)別不同類別的failure模式，使用三維非負(fù)矩陣聚類，成功檢測到未知僵尸網(wǎng)絡(luò)的存在。

大部分DNS異常檢測的過程里需要保存和處理一定的域名、IP、訪問時(shí)間、報(bào)文長度等DNS流特征，以研究具體的異常細(xì)節(jié)。考慮到目前大部分主干網(wǎng)絡(luò)已經(jīng)升級到OC-48（2.5 Gb/s）和OC-192（10 Gb/s）[4]，上述研究方法并不適用于計(jì)算資源（CPU、內(nèi)存、硬盤等）有限的高速大規(guī)模的網(wǎng)絡(luò)環(huán)境中。

因此，本文以DNS failure中的域名和客戶端IP為檢測對象、以發(fā)現(xiàn)惡意活動為檢測目標(biāo)，提出了一種僅需很小資源開銷的基于Counting Bloom Filter的檢測方法。如何改進(jìn)Counting Bloom Filter，以較低的資源開銷實(shí)現(xiàn)高效的DNS異常檢測是本文的主要研究內(nèi)容。

2 準(zhǔn)備工作

鑒于惡意程序DNS查詢的動機(jī)、時(shí)間、頻率由事先編程的代碼內(nèi)容設(shè)定，它的DNS failure流量與合法用戶的隨機(jī)DNS failure存在著明顯的區(qū)別。為了讓惡意DNS failure從DNS數(shù)據(jù)流中“脫穎而出”，首先需要做好兩項(xiàng)準(zhǔn)備工作：

（1）提取純凈的DNS failure報(bào)文

借助網(wǎng)絡(luò)數(shù)據(jù)包分析工具wireshark對DNS樣本數(shù)據(jù)進(jìn)行觀察，發(fā)現(xiàn)DNS failure報(bào)文的三條特征：

①DNS服務(wù)器的回復(fù)為Server Failure。在該類DNS響應(yīng)報(bào)文中，標(biāo)志字段中的rcode子字段值為2。

②DNS服務(wù)器的回復(fù)為No Such Name。在該類DNS響應(yīng)報(bào)文中，標(biāo)志字段中的rcode子字段值為3。

③域名被劫持至電信114廣告服務(wù)器。在該類DNS響應(yīng)報(bào)文中，返回的資源數(shù)據(jù)內(nèi)容為114服務(wù)器IP地址（a.b.c.d）。

（2）描述惡意DNS failure的流量特征

Zhu Z.S.等人為了解不同應(yīng)用產(chǎn)生的不同的failure流量，進(jìn)行了一組對比實(shí)驗(yàn)：惡意應(yīng)用組中被執(zhí)行的程序有基于HTTP、IRC及P2P三種協(xié)議的僵尸程序以及蠕蟲等；網(wǎng)絡(luò)爬蟲及視頻網(wǎng)站等良性應(yīng)用被置于正常組。觀察發(fā)現(xiàn)24種惡意程序中有3/4表現(xiàn)出活躍的DNS failure現(xiàn)象，相對于正常應(yīng)用有更高的DNS failure頻度[5]。如表1所示。

由此，定義單位時(shí)間內(nèi)DNS failure大規(guī)模的發(fā)生為大規(guī)模失敗DNS查詢異常（Numerous DNS Failures，NDF）。為將良性的DNS failure流量與惡性的DNS合理區(qū)分開，如何界定NDF異常是亟需解決的問題，通過設(shè)定NDF異常判斷標(biāo)準(zhǔn)，使最終被檢測的數(shù)據(jù)盡可能多地覆蓋異常內(nèi)容、盡可能少地包含正常內(nèi)容。

表12 4種惡意應(yīng)用的每小時(shí)DNS failure數(shù)

對于網(wǎng)絡(luò)中數(shù)據(jù)流的到達(dá)，學(xué)術(shù)界已經(jīng)基本形成了共識，認(rèn)為其是服從Poisson分布的，DNS流亦如此。而對于DNS failure的到達(dá)，目前還沒有相關(guān)結(jié)論。由于每一次DNS查詢都是獨(dú)立的用戶行為，并且最終結(jié)果只有DNS success和DNS failure兩種可能性，設(shè)DNS failure發(fā)生的概率為p，以X表示n個(gè)時(shí)間粒度內(nèi)的DNS查詢中DNS failure發(fā)生的次數(shù)，則X服從二項(xiàng)分布X～b(n，p)。當(dāng)測量時(shí)間足夠長，即n值足夠大時(shí)，X可以很好地近似為正態(tài)分布。

為有效分析大規(guī)模網(wǎng)絡(luò)環(huán)境中DNS failure流到達(dá)的分布特征，采用某主干網(wǎng)邊界采集器上的數(shù)據(jù)為研究對象，考察其2012年5月19日10：00至20：00時(shí)間范圍內(nèi)DNS failure報(bào)文數(shù)量隨著時(shí)間變化的分布狀況，以5 min為單位時(shí)間粒度，對報(bào)文進(jìn)行計(jì)數(shù)，計(jì)數(shù)結(jié)果如圖1所示。圖1中橫軸是以時(shí)間刻度為單位的時(shí)間軸；縱軸是DNS failure數(shù)據(jù)的瞬時(shí)強(qiáng)度，即單位時(shí)間粒度內(nèi)到達(dá)的DNS failure報(bào)文的數(shù)目。如圖所示，正常訪問的DNS failure數(shù)量很少，而且DNS failure的爆發(fā)在短時(shí)間內(nèi)發(fā)生。

根據(jù)6σ原理，當(dāng)隨機(jī)事件的發(fā)生服從正態(tài)分布時(shí)，其正態(tài)總體幾乎總?cè)≈涤趨^(qū)間(μ-3σ，μ+3σ)內(nèi)，在此區(qū)間之外的取值概率為0.002 6，通常認(rèn)為這種情況在一次實(shí)驗(yàn)中幾乎不可能發(fā)生。上文中已說明DNS failure的發(fā)生可近似為正態(tài)分布，在保證正常DNS failure盡可能地落入正常區(qū)間的前提下定義：

圖1 某主干網(wǎng)信道上的DNS failure變化曲線

為NDF異常的判斷標(biāo)準(zhǔn)，其中i為DNS failure數(shù)據(jù)的瞬時(shí)強(qiáng)度，高出這一標(biāo)準(zhǔn)的概率僅為0.022 8。

依據(jù)異常標(biāo)準(zhǔn)對DNS數(shù)據(jù)進(jìn)行檢測和還原，可知道發(fā)生異常的DNS failure的有效信息，從而能夠跟蹤和識別僵尸網(wǎng)絡(luò)等引起NDF的網(wǎng)絡(luò)行為。

圖1中期望Ε為211.542，標(biāo)準(zhǔn)差σ為468.855。A點(diǎn)高于Ε+2σ線，發(fā)生了NDF異常，下面將重點(diǎn)描述如何進(jìn)行異常檢測獲得發(fā)生異常的場景信息（A點(diǎn)主要異常的域名，客戶端IP）。

3 基于Counting Bloom Filter的DNS異常檢測

本章將圍繞帶語義特征的可逆哈希函數(shù)展開，利用該函數(shù)將檢測中聚類與還原兩個(gè)重要環(huán)節(jié)緊密聯(lián)系在一起。其中，key到value的映射過程用于聚類；其逆運(yùn)算將用于還原。

3.1 hash聚類

hash函數(shù)作為一種簡單的聚類方法，使不同類別的數(shù)據(jù)按照hash函數(shù)給定的規(guī)則聚集到不同的hash值上，該hash值即成為具有某個(gè)特性的流的聚類標(biāo)簽。這個(gè)以短標(biāo)簽替代長標(biāo)簽的過程，將原始數(shù)據(jù)的長流映射到很短的哈希串所在空間里，極大地減縮了存儲代價(jià)和遍歷查找等計(jì)算時(shí)間。Bloom Filter作為普通hash函數(shù)的變形，選用多個(gè)hash函數(shù)提高h(yuǎn)ash檢驗(yàn)的精度。Counting Bloom Filter則將Bloom Filter位數(shù)組的每一位擴(kuò)展為計(jì)數(shù)器，以支持聚類過程中對某類元素的個(gè)數(shù)統(tǒng)計(jì)。

標(biāo)準(zhǔn)Counting Bloom Filter（Bloom Filter）的hash聚類有兩個(gè)局限：一是所有的聚類對象被多個(gè)hash函數(shù)映射到同一哈?？臻g中，不可避免的內(nèi)部沖突影響聚類結(jié)果的準(zhǔn)確性；二是對映射結(jié)果均勻分布（為減小不同對象間的沖突）的期望，不僅加大了hash函數(shù)的選取難度，也不利于hash串的逆向還原。為了能在顯著降低普通Counting Bloom Filter錯(cuò)誤肯定率（False Positive Rate，F(xiàn)PR）的前提下還原h(huán)ash串，本文擴(kuò)展了Counting Bloom Filter的應(yīng)用。

首先為每個(gè)hash函數(shù)準(zhǔn)備獨(dú)立的存儲空間，這樣雖然不能消除多個(gè)不同源串被哈希至同一位置的外部沖突，但杜絕了不同hash函數(shù)映射結(jié)果相同的內(nèi)部沖突；其次選用一些直接取源串中的部分重疊比特的hash函數(shù)，不僅非常簡單，對源串的還原也有很大的益處。這里就此兩點(diǎn)進(jìn)行細(xì)述：

DNS域名長度應(yīng)在255個(gè)字符范圍之內(nèi)，如何在有限的空間內(nèi)標(biāo)識一個(gè)唯一的域名，這在域名聚類前必須要考慮。實(shí)踐表明，取域名前13個(gè)不包括“.”的字符（若域名本身長度不足，可小于13），能很好地兼顧聚類結(jié)果的精度及存儲開銷。如將“ftp.cn.playsafe.com.tw”中的ftpcnplaysafe作為源串，用12個(gè)獨(dú)立的hash函數(shù)分別依次按字符重疊取出不同的兩個(gè)字符（ft，tp，pc，…，af，fe）的比特串；對于拆解后的多對短串，以第一個(gè)字符對應(yīng)的二進(jìn)制數(shù)為高8位，第二個(gè)字符對應(yīng)的比特值為低8位，經(jīng)過按位與運(yùn)算得到索引，并在索引對應(yīng)的哈?？臻g中計(jì)算該短串在數(shù)據(jù)流中的出現(xiàn)次數(shù)（hits）。圖2給出了域名的聚類過程。

圖2 域名的聚類過程

而對于IP地址，三個(gè)hash函數(shù)直接映射IP地址的高16 bit、中間16 bit以及低16 bit，具體聚類步驟如圖3所示。

圖3 IP地址的聚類過程

不同的hash索引對應(yīng)著不同短串的出現(xiàn)次數(shù)，通過對域名和IP的hash聚類，不同源串中相同的短串自然地聚集在了一起；多個(gè)哈?？臻g的并行映射使得FPR減小了許多；但因域名字符的種類限制，以及IPv4地址的特定范圍，使得哈希后的值集中于哈?？臻g的某一區(qū)間。對于此類使用獨(dú)立哈希空間、非均勻Counting Bloom Filter的FPR及誤差分析，文獻(xiàn)[6]有詳細(xì)報(bào)道，此處不再贅述。

3.2 源串還原

上節(jié)中精心挑選的hash函數(shù)，讓還原過程變得非常簡單。如果能夠確定兩個(gè)hash串出自同一個(gè)源串，那么就可以通過字符拼接來最大可能地恢復(fù)源串的全貌。根據(jù)上節(jié)的分析，這里提出三條同源性判斷的依據(jù)：

（1）字符語義；

（2）若短串a(chǎn)b的hits值為N，短串bc若與ab同源，那么它的hits值至少為N；

（3）hash短串的hits值大于或等于其源串的出現(xiàn)次數(shù)。

3.3 還原算法

考慮到檢測時(shí)間內(nèi)的某點(diǎn)發(fā)生NDF異常由該點(diǎn)對應(yīng)時(shí)間內(nèi)的少數(shù)高頻度異常DNS訪問貢獻(xiàn)，因此只需對各哈?？臻gTopN的短串進(jìn)行同源性判斷，再通過拼接復(fù)原即可得到異常域名和IP的具體信息。

基于以上分析，本文給出域名源串還原算法（IP地址的還原算法與此類似，不同之處在于IP地址的前綴聚類可用于蠕蟲擴(kuò)散、路由循環(huán)等異常的檢測，相關(guān)分析可見文獻(xiàn)[7]）：

3.4 算法復(fù)雜度對比

以異常客戶端IP地址的檢測為例，將改進(jìn)的Counting Bloom Filter算法與單哈希（32 bit）、單哈希+鏈表以及map三種常規(guī)實(shí)現(xiàn)“算法”進(jìn)行比較，如表2。

表2 復(fù)雜度對比

對表2的幾點(diǎn)說明：

（1）Counting Bloom Filter算法的主要計(jì)算是排序獲得Top N，而借助于比較進(jìn)行的排序在最壞情況下能達(dá)到的最好時(shí)間復(fù)雜度為O(N lbN)。對hash空間的訪問開銷為O(1)，在對IP進(jìn)行檢測的過程中，直接映射IP其中的16 bit，設(shè)映射空間的大小為M，則M=216。該算法的空間復(fù)雜度為O(M+N)，時(shí)間復(fù)雜度為O(M+N lbN)，由于N遠(yuǎn)小于M，所以兩者均近似為O(M)。

（2）單哈希算法預(yù)先分配固定大小的哈希數(shù)組，映射空間內(nèi)可以是對IP地址的計(jì)數(shù)或存放完整的IP地址（32 bit），前者不便于可逆還原，后者占用4 GB的存儲空間。對hash空間的訪問為O(1)；若直接存儲IP地址，則映射空間的大小M′是上一條中M的兩倍。

（3）單哈希與鏈表的組合，是由鏈表存儲原始的IP地址，而哈希表中存放指向鏈表的指針。M″是對鏈表訪問所花費(fèi)的開銷，空間復(fù)雜度由指針本身的存儲空間Mp以及平均每個(gè)鏈表所占用的空間Mlist決定，n是數(shù)據(jù)流中的IP數(shù)。

（4）C++的STL默認(rèn)使用樹結(jié)構(gòu)來實(shí)現(xiàn)map，在一次樹查找中，最壞情況下的復(fù)雜度為O(lbn)，另外還需考慮查找過程中一些函數(shù)的調(diào)用。空間上，主要是存儲n個(gè)IP地址值和map容器自身的開銷Mmap。

當(dāng)這些方法應(yīng)用于高速大規(guī)模網(wǎng)絡(luò)環(huán)境中（即n非常大時(shí)），改進(jìn)的Counting Bloom Filter算法的優(yōu)勢會非常明顯，尤其在異常域名的檢測上。

4 實(shí)驗(yàn)與結(jié)果分析

本節(jié)對基于Counting Bloom Filter的檢測方法進(jìn)行了實(shí)現(xiàn)，實(shí)驗(yàn)所用的數(shù)據(jù)取自某主干網(wǎng)5月19日10：00至20：00共10個(gè)小時(shí)的DNS數(shù)據(jù)，具體DNS failure的變化曲線如圖1所示。下面通過表格說明圖1中的A點(diǎn)（12：20—12：25）異常的檢測過程（為節(jié)省篇幅，表3和表4僅列出Counting Bloom Filter空間的Top 5，實(shí)際實(shí)驗(yàn)時(shí)取Top 10）。

表3 域名的Counting Bloom Filter空間Top 5

表4 客戶端IP的Counting Bloom Filter空間Top 5

參考同源性判斷的三條依據(jù)，拼接表3和表4中的短串，得到異常域名和客戶端IP的列表，如表5、6。

根據(jù)第2章E為211.542，σ為468.855可知此次檢測中NDF的判斷標(biāo)準(zhǔn)E+2σ=1 149.251。在表5與表6中，域名“ftp.cn.playsafe.com.tw”和“ftp.playsafe.com.tw”以及客戶端IP“a.42.53.56”的瞬時(shí)強(qiáng)度（hits值）均符合這一標(biāo)準(zhǔn)。關(guān)聯(lián)三者可進(jìn)一步看出A點(diǎn)的爆發(fā)異常的主要原因是IP地址a.42.53.56對域名ftp.cn.playsafe.com.tw和ftp.playsafe.com.tw的爆發(fā)訪問。

表5 異常域名

表6 異?？蛻舳薎P

5 結(jié)論

本文以DNS failure為切入點(diǎn)，提出了一種基于Counting Bloom Filter的DNS異常檢測方法——在選取多個(gè)有獨(dú)立空間和語義特征的哈希函數(shù)保障不同的hash代表的語義間不會產(chǎn)生沖突之后，根據(jù)同源判斷和Top N的結(jié)果拼接出頻度上異常的域名和IP源串。借助該方法，能夠快速從真實(shí)的高速大規(guī)模主干網(wǎng)數(shù)據(jù)中發(fā)現(xiàn)異常DNS行為，確診這些異常的具體類型將是下一步的研究方向。

[1] 丁森林，吳軍，毛偉.利用熵檢測DNS異常[J].計(jì)算機(jī)系統(tǒng)應(yīng)用，2010，19（12）：195-198.

[2] Yadav S，Reddy N.Winning with DNS failures：strategies forfasterbotnetdetection[C]//SecurityandPrivacyin Communication Networks，2011.

[3] Jiang N，Gao J，Lin Y，et al.Identifying suspicious activities through DNS failure graph analysis[C]//IEEE International Conference on Computer Communications，2011.

[4] 程光，龔儉.互聯(lián)網(wǎng)流測量[M].南京：東南大學(xué)出版社，2008.

[5] Zhu Z S，Yegneswaran V，Chen Y.Using failure informationanalysistodetectenterprisezombies[C]//Security and Privacy in Communication Networks，2009.

[6] 彭艷兵，龔儉，劉衛(wèi)江，等.Bloom Filter哈希空間的元素還原[J].電子學(xué)報(bào)，2006，34（5）：822-827.

[7] 龔儉，彭艷兵，楊望，等.基于Bloom Filter的大規(guī)模異常TCP連接參數(shù)再現(xiàn)方法[J].軟件學(xué)報(bào)，2006，17（3）：434-444.