基于Counting Bloom Filter的DNS異常檢測

胡蓓蓓，彭艷兵，程光

HU Beibei1,PENG Yanbing2,CHENG Guang3

1.武漢郵電科學研究院，武漢430074

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

3.東南大學計算機科學與工程系，南京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）是標識計算機電子方位的“GPS”，它將域名和IP地址相互映射成一個分布式數據庫。一次DNS查詢的失敗（DNS query failure，以下簡稱DNS failure）通常意味著無法在數據庫中找到所查域名對應的資源記錄。出現(xiàn)DNS failure可能是由DNS配置不當或域名輸入錯誤引起，但前者發(fā)生的機率非常小，后者產生的數據量非常小。相關事件與研究表明一些網絡異常活動會導致大量DNS failure的出現(xiàn)：

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

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

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

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

2 準備工作

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

（1）提取純凈的DNS failure報文

借助網絡數據包分析工具wireshark對DNS樣本數據進行觀察，發(fā)現(xiàn)DNS failure報文的三條特征：

①DNS服務器的回復為Server Failure。在該類DNS響應報文中，標志字段中的rcode子字段值為2。

②DNS服務器的回復為No Such Name。在該類DNS響應報文中，標志字段中的rcode子字段值為3。

③域名被劫持至電信114廣告服務器。在該類DNS響應報文中，返回的資源數據內容為114服務器IP地址（a.b.c.d）。

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

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

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

表12 4種惡意應用的每小時DNS failure數

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

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

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

圖1 某主干網信道上的DNS failure變化曲線

為NDF異常的判斷標準，其中i為DNS failure數據的瞬時強度，高出這一標準的概率僅為0.022 8。

依據異常標準對DNS數據進行檢測和還原，可知道發(fā)生異常的DNS failure的有效信息，從而能夠跟蹤和識別僵尸網絡等引起NDF的網絡行為。

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

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

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

3.1 hash聚類

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

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

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

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

圖2 域名的聚類過程

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

圖3 IP地址的聚類過程

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

3.2 源串還原

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

（1）字符語義；

（2）若短串ab的hits值為N，短串bc若與ab同源，那么它的hits值至少為N；

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

3.3 還原算法

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

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

3.4 算法復雜度對比

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

表2 復雜度對比

對表2的幾點說明：

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

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

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

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

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

4 實驗與結果分析

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

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

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

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

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

表5 異常域名

表6 異?？蛻舳薎P

5 結論

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

[1] 丁森林，吳軍，毛偉.利用熵檢測DNS異常[J].計算機系統(tǒ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)網流測量[M].南京：東南大學出版社，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].電子學報，2006，34（5）：822-827.

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