基于Filter-ary-Sketch數(shù)據(jù)結(jié)構(gòu)的骨干網(wǎng)異常檢測研究

鄭黎明，鄒鵬，韓偉紅，李愛平，賈焰

(1. 國防科學(xué)技術(shù)大學(xué) 計(jì)算機(jī)學(xué)院，湖南 長沙 410073；2. 裝備指揮技術(shù)學(xué)院，北京 100029)

1 引言

隨著互聯(lián)網(wǎng)技術(shù)的不斷發(fā)展以及各類網(wǎng)絡(luò)應(yīng)用爆炸式增長，計(jì)算機(jī)網(wǎng)絡(luò)已經(jīng)成為影響我國政治、經(jīng)濟(jì)、軍事、文化的一個(gè)重要因素。但與此同時(shí)網(wǎng)絡(luò)安全問題卻日趨嚴(yán)峻，流量異常和網(wǎng)絡(luò)攻擊變得日益頻繁，如DDoS、蠕蟲爆發(fā)、大規(guī)模端口掃描等。為了盡早發(fā)現(xiàn)大規(guī)模網(wǎng)絡(luò)安全事件，需要在骨干網(wǎng)上進(jìn)行異常檢測并對惡意流量進(jìn)行阻斷，這樣才能把惡意流量造成的危害降到最低。但是已有的網(wǎng)絡(luò)異常檢測系統(tǒng)存在諸多問題，不能滿足高速骨干網(wǎng)上異常檢測的要求，總得來說有以下幾點(diǎn)。

1) 已有入侵檢測系統(tǒng)通常是面向主機(jī)或者面向局域網(wǎng)的，不能適應(yīng)大規(guī)模高速網(wǎng)絡(luò)環(huán)境，但是在蠕蟲快速傳播的早期對其進(jìn)行檢測，或者遭受DDoS攻擊時(shí)盡可能靠近源地址檢測又尤為重要?，F(xiàn)有骨干網(wǎng)的實(shí)時(shí)海量流量數(shù)據(jù)使得已有的各類異常檢測系統(tǒng)很難適應(yīng)，以10Gbit/s的骨干網(wǎng)為例，報(bào)文以每秒百萬的速率到達(dá)，假設(shè)每個(gè)報(bào)文40byte，報(bào)文達(dá)到的時(shí)間間隔僅為32ns。

2) 已有入侵檢測工具如Snort、Bro等都采用特征匹配的方法，需要對每個(gè)數(shù)據(jù)分組的內(nèi)容和特征樣本進(jìn)行匹配，隨著網(wǎng)絡(luò)中惡意代碼數(shù)量的增加，特征庫越來越大，異常檢測性能隨著特征樣本數(shù)量的增加急劇下降，同時(shí)它還無法檢測未知特征攻擊。

3) 為了應(yīng)對挑戰(zhàn)，研究者提出了多種流量異常檢測方法，如基于統(tǒng)計(jì)、機(jī)器學(xué)習(xí)和數(shù)據(jù)挖掘的方法等。按照數(shù)據(jù)來源的聚集層次，可以分為2類：基于全部(或者符合一定條件的子流量)流量值的方法和基于 Flow級(jí)別的方法?；诳傮w流量值的方法雖然需要的存儲(chǔ)開銷和計(jì)算資源都較少，但是容易造成檢測精度不高，無法定位異常，不能提供異常的詳細(xì)信息，更重要的是只針對某種特定攻擊檢測效果比較好，而對其他類型的攻擊則存在假陽性或者假陰性概率比較高的問題。如在路由器上基于變點(diǎn)檢測(CPM)技術(shù)[1]或者基于 CUSUM 算法的SYN防洪攻擊檢測系統(tǒng)[2]，它們針對整體流量中的SYN-FIN或者 SYN-SYN/ACK數(shù)據(jù)分組對的統(tǒng)計(jì)行為進(jìn)行異常檢測?；?Flow的方法檢測精度較高，能定位異常，給管理者提供異常的詳細(xì)視圖，但存儲(chǔ)開銷和計(jì)算消耗較大，很難直接適用于大規(guī)模高速骨干網(wǎng)絡(luò)。例如基于 Flow流統(tǒng)計(jì)的異常檢測方法[3]，需要保存每個(gè) Flow流的狀態(tài)信息，而Flow流由五元組構(gòu)成，保存每個(gè)Flow流信息需要2104bit的存儲(chǔ)開銷，無法滿足骨干網(wǎng)上異常檢測要求。特別當(dāng)面對利用大規(guī)模僵尸網(wǎng)絡(luò)發(fā)起的 DDoS攻擊時(shí)，基于 Flow流統(tǒng)計(jì)的異常檢測系統(tǒng)將出現(xiàn)內(nèi)存溢出問題。

異常檢測因能檢測“zero day”攻擊且適用于高速網(wǎng)絡(luò)而獲得了廣泛的應(yīng)用，主要思想是通過歷史流量得到一個(gè)正常的流量模型，然后通過檢測在短期內(nèi)不符合此模型的行為來發(fā)現(xiàn)異常。但是現(xiàn)有的高速骨干網(wǎng)通常每秒到達(dá)的 IP分組以百萬計(jì)，在IPv4網(wǎng)絡(luò)環(huán)境下單個(gè)維度的地址空間達(dá) 232，用已有算法直接處理骨干網(wǎng)上流量數(shù)據(jù)來檢測異常是不可行的，通?？梢圆捎媒稻S的方法來減少需要處理的數(shù)據(jù)量。目前對流量數(shù)據(jù)進(jìn)行降維的方法主要有：采樣、聚集、主成分分析法 PCA(principal component analysis)和sketch(概要數(shù)據(jù)結(jié)構(gòu))。文獻(xiàn)[4]指出采樣是一個(gè)有損的信息處理過程，會(huì)丟棄重要信息，它研究采樣對各類檢測算法的影響，實(shí)驗(yàn)證明通過采樣后的數(shù)據(jù)進(jìn)行異常檢測將會(huì)導(dǎo)致異常檢測算法誤差增大；對網(wǎng)絡(luò)流量進(jìn)行聚集可能導(dǎo)致惡意流量聚集后呈現(xiàn)正常流量的行為特征，而正常流量聚集后呈現(xiàn)異常流量行為特征[5]；PCA是一種坐標(biāo)變化方法，它將給定數(shù)據(jù)點(diǎn)映射到一些新的坐標(biāo)軸，這些新的坐標(biāo)軸就成為主成分，文獻(xiàn)[6]提出了利用 PCA進(jìn)行流量異常檢測，不過算法相對復(fù)雜度高，只能進(jìn)行事后異常分析，不能滿足骨干網(wǎng)上異常檢測要求。Sketch數(shù)據(jù)結(jié)構(gòu)來源于數(shù)據(jù)流研究領(lǐng)域，是對大流量一次經(jīng)過的數(shù)據(jù)進(jìn)行快速查詢，即在數(shù)據(jù)流上維持一個(gè)實(shí)時(shí)更新的摘要數(shù)據(jù)，在一定精度保證下快速回答用戶的查詢請求[7]。Sketch 是一種高效的概要數(shù)據(jù)結(jié)構(gòu)，它占用的內(nèi)存資源少，甚至可以移植到SRAM中，計(jì)算和更新的復(fù)雜性也小，通常能夠達(dá)到O (ploy(logn0))(n0為不同數(shù)據(jù)標(biāo)識(shí)的數(shù)目)，且在理論上有精度保證，能夠滿足大規(guī)模網(wǎng)絡(luò)條件下實(shí)時(shí)流量數(shù)據(jù)處理的要求。Sketch數(shù)據(jù)結(jié)構(gòu)已經(jīng)廣泛應(yīng)用于網(wǎng)絡(luò)安全領(lǐng)域，文獻(xiàn)[8]利用 Hash函數(shù)建立了 Count-min概要數(shù)據(jù)結(jié)構(gòu)；Krishnamurthy 等人在文獻(xiàn)[9]中提出k-ary sketch概要數(shù)據(jù)結(jié)構(gòu)，應(yīng)用于變點(diǎn)檢測，并提出一種啟發(fā)式方法自動(dòng)設(shè)置sketch的參數(shù)；在文獻(xiàn)[9]的基礎(chǔ)上，Schweller 等人在文獻(xiàn)[10]中采用 IP 地址分塊 hash和IP擾亂2種方法來解決sketch 可溯源性問題；最近Dewaele 等人在sketch 的基礎(chǔ)上應(yīng)用非高斯邊緣分布(non Gaussian marginal distribution)的多時(shí)間尺度特性進(jìn)行異常檢測，可以檢測多種攻擊，包括檢測低強(qiáng)度持續(xù)時(shí)間長的攻擊和持續(xù)時(shí)間短的端口掃描攻擊[11]。在眾多的概要數(shù)據(jù)結(jié)構(gòu)中，k-ary sketch概要數(shù)據(jù)具有最優(yōu)的時(shí)間和空間約束，能夠有效地應(yīng)用于異常檢測。但是概要數(shù)據(jù)結(jié)構(gòu)的異常檢測方法不能提供攻擊者的詳細(xì)信息，雖然文獻(xiàn)[10,19]提出了相關(guān)算法，能夠逆向還原出源IP地址，但是相關(guān)算法復(fù)雜度高，計(jì)算量較大，而且現(xiàn)在攻擊普遍采用IP欺騙技術(shù)，還原出源IP作用并不明顯。

為了提高異常檢測系統(tǒng)的檢測精度，研究者開始通過對流量數(shù)據(jù)的分布特征進(jìn)行監(jiān)控來檢測異常，采用熵對分布特征進(jìn)行度量?；陟氐漠惓z測系統(tǒng)的主要思想是：一旦有異常流量發(fā)生時(shí)，總體流量在各個(gè)維度上的分布應(yīng)該會(huì)發(fā)生變化，通過熵值的變化能夠檢測出該異常。文獻(xiàn)[12]通過流量特征上的熵值把流量分為異常和正常2類分量來進(jìn)行異常檢測；文獻(xiàn)[13]首次提出在高速IP網(wǎng)絡(luò)上利用熵值來檢測蠕蟲和流量異常；文獻(xiàn)[14]通過比較當(dāng)前分布和基準(zhǔn)分布的差異來進(jìn)行異常檢測，且基于最大熵原理，提出了一種靈活計(jì)算基準(zhǔn)分布的方法；文獻(xiàn)[15]通過把分布的特征分為2類：數(shù)據(jù)分組頭特征和行為特征，發(fā)現(xiàn)它們熵值序列之間的相關(guān)性，提出了在實(shí)現(xiàn)基于熵的異常檢測系統(tǒng)時(shí)需要注意的若干問題。但是上述算法的空間和時(shí)間復(fù)雜度較高，通常時(shí)間復(fù)雜度為O(ploy(n0))，空間復(fù)雜度也為O (ploy(n0))，只適應(yīng)于事后異常分析或者低速網(wǎng)絡(luò)環(huán)境下的異常檢測，不能滿足骨干網(wǎng)上異常檢測要求。

本文引入數(shù)據(jù)流中概要數(shù)據(jù)結(jié)構(gòu)的思想，提出Filter-ary-Sketch數(shù)據(jù)結(jié)構(gòu)，在該數(shù)據(jù)結(jié)構(gòu)上采用基于熵的異常檢測算法在骨干網(wǎng)上進(jìn)行異常檢測。首先把骨干網(wǎng)上海量流量數(shù)據(jù)通過 Hash映射隨機(jī)投影到Filter-ary-Sketch數(shù)據(jù)結(jié)構(gòu)中，再通過熵值的變化來檢測異常，通過不同維度熵值變化情況來判斷異常類型。檢測到異常后，通過 Filter-ary-Sketch中各個(gè)桶內(nèi)統(tǒng)計(jì)量差值的變化情況來定位異常點(diǎn)，最后通過Bloom Filter中存儲(chǔ)的源IP信息進(jìn)行惡意流量阻斷。

本文主要貢獻(xiàn)：

1) 在 k-ary概要數(shù)據(jù)結(jié)構(gòu)的基礎(chǔ)上，提出了Filter-ary-Sketch概要數(shù)據(jù)結(jié)構(gòu)，解決了以往異常檢測后不能直接定位異常流量的問題。

2) 在 Filter-ary-Sketch數(shù)據(jù)結(jié)構(gòu)上對網(wǎng)絡(luò)流量各維度熵值進(jìn)行高效并行計(jì)算，解決以往基于熵的異常檢測不能進(jìn)行實(shí)時(shí)異常檢測和不適應(yīng)高速骨干網(wǎng)的問題。

3) 針對已有異常檢測方法進(jìn)行惡意流量阻斷成本高的問題，本文在Filter-ary-Sketch數(shù)據(jù)結(jié)構(gòu)中放置Bloom Filter存儲(chǔ)源IP信息，利用隨機(jī)Hash函數(shù)的特點(diǎn)識(shí)別惡意源IP。

第2節(jié)對異常檢測中的關(guān)鍵數(shù)據(jù)結(jié)構(gòu)和算法進(jìn)行描述，第3節(jié)對異常檢測流程進(jìn)行詳細(xì)描述，第4節(jié)使用真實(shí)數(shù)據(jù)驗(yàn)證本文所提檢測方法的有效性，第5節(jié)為結(jié)束語。

2 數(shù)據(jù)模型與算法

2.1 多維十字轉(zhuǎn)門模型

數(shù)據(jù)流描述模型有多種，如時(shí)間序列模型、緩沖寄存器模型、十字轉(zhuǎn)門模型等。所提方法需要在多個(gè)維度上進(jìn)行隨機(jī)散列投影，且需要實(shí)時(shí)更新到達(dá)IP分組的數(shù)目，所以在十字轉(zhuǎn)門模型的基礎(chǔ)上進(jìn)行多維擴(kuò)展，提出多維十字轉(zhuǎn)門模型。網(wǎng)絡(luò)流量數(shù)據(jù)具有多個(gè)不同的維度，假設(shè)維度數(shù)為 d，則每個(gè)數(shù)據(jù)項(xiàng)可描述為Xi=[xi,1,xi,2,…,xi,d],Dom(xj), 0≤j ≤d表示各個(gè)維度的取值空間，流量數(shù)據(jù)在不同維度的取值空間上具有不同的分布。文獻(xiàn)[15]研究了多個(gè)不同維度上熵值時(shí)間序列之間相關(guān)性，通過骨干網(wǎng)上實(shí)際采集的流量數(shù)據(jù)，分析了不同維度上熵值時(shí)間序列兩兩之間的相關(guān)性，對熵值異常檢測中維度選擇提出了一些建議，本文針對骨干網(wǎng)上異常檢測的需求，借鑒文獻(xiàn)[15]的結(jié)論，選擇源IP、目的Port和IP數(shù)據(jù)分組長度3個(gè)相關(guān)性較少的維度作為熵值異常檢測的特征維度。下面對多維十字轉(zhuǎn)門模型進(jìn)行定義。

定義1 多維十字轉(zhuǎn)門模型：L=a0,a1,…為數(shù)據(jù)項(xiàng)逐個(gè)連續(xù)到達(dá)的輸入流，其中每個(gè)數(shù)據(jù)項(xiàng) ai=(SIPi, Dporti,Plengthi,ui)，SIPi, Dporti,Plengthi為該數(shù)據(jù)項(xiàng)各維度上的標(biāo)識(shí)，為了闡述方便定義identityi=σ[SIPi,Dporti,Plengthi]，表示當(dāng)前討論投影維度上的標(biāo)識(shí)。ui表示該數(shù)據(jù)項(xiàng)的特征值，[N]k= σk[Dom(SIP),Dom(Dport),Dom(Plength)]={0,1,…, nk-1}為流數(shù)據(jù)模型當(dāng)前投影維度的取值空間。U[identityi]表示對所有標(biāo)識(shí)為 identityi數(shù)據(jù)項(xiàng)的統(tǒng)計(jì)量，當(dāng)一個(gè)數(shù)據(jù)項(xiàng)到達(dá)時(shí)，更新其標(biāo)識(shí)所對應(yīng)的統(tǒng)計(jì)量，即U[identityi]+= ui。

在骨干網(wǎng)異常檢查應(yīng)用場景下，多維十字轉(zhuǎn)門模型中每個(gè)數(shù)據(jù)項(xiàng)可取IP數(shù)據(jù)分組數(shù)目或字節(jié)數(shù)，本文采用了IP數(shù)據(jù)分組長度作為分析維度，數(shù)據(jù)項(xiàng)記錄IP數(shù)據(jù)分組數(shù)目，特征值統(tǒng)一定義為IP分組的數(shù)目，在每個(gè)數(shù)據(jù)項(xiàng)到達(dá)時(shí)ui=1，所提方法主要通過計(jì)算各個(gè)維度上 IP數(shù)據(jù)分組數(shù)目的分布變化情況來檢測異常。

2.2 Filter-ary-Sketch數(shù)據(jù)結(jié)構(gòu)

骨干網(wǎng)上異常檢測過程中對流量數(shù)據(jù)的處理具有以下特點(diǎn)：①流量數(shù)據(jù)海量、無限、快速到達(dá)；②需要連續(xù)跟蹤處理結(jié)果；③因數(shù)據(jù)量大，數(shù)據(jù)一經(jīng)處理，大部分情況不再存儲(chǔ)；④實(shí)時(shí)性要求比較高；⑤僅要求獲得近似結(jié)果。針對上述特點(diǎn)，本文提出了Filter-ary-Sketch數(shù)據(jù)結(jié)構(gòu)，其包括3個(gè)部分：Hash函數(shù)、Filter-ary-Sketch數(shù)據(jù)結(jié)構(gòu)、Filter-ary-Sketch數(shù)據(jù)結(jié)構(gòu)上定義的操作。

散列函數(shù)是隨機(jī)投影技術(shù)的核心，它把高維度的流量數(shù)據(jù)向低緯度空間進(jìn)行隨機(jī)投影，是一種典型的壓縮映射。散列函數(shù)的取值空間通常遠(yuǎn)小于輸入空間，不同的輸入可能會(huì)散列成相同的輸出，也不可能從散列函數(shù)值來唯一確定輸入值，即散列函數(shù)存在碰撞問題和不可逆性。為了讓所提方法具有普遍適用性，同時(shí)把碰撞的概率控制在一定范圍之內(nèi)，本文選擇通用散列函數(shù)。

定義2[19]通用散列函數(shù)簇(universal散列classes)：G是從A映射到B的一系列函數(shù)，如果G滿足?x,y∈A，且x≠y，則x, y在G的所有函數(shù)下碰撞的次數(shù)C≤G B，則稱G為通用散列函數(shù)簇。從通用散列函數(shù)簇隨機(jī)取一個(gè)函數(shù)，具有性質(zhì)：?x,y∈A，且 x≠y，則 P(f(x)=f(y))≤1/|B|。

通用散列函數(shù)具有很好的性質(zhì)，能夠把沖突概率控制在一定范圍內(nèi)，也可以保證數(shù)據(jù)項(xiàng)標(biāo)識(shí)均勻分布，選擇通用散列函數(shù)簇中獨(dú)立的h個(gè)散列函數(shù)，只要h足夠大就能保證Filter-ary-Sketch數(shù)據(jù)結(jié)構(gòu)上定義的算法誤差足夠小。本文所提異常檢測方法不需要對單個(gè)Key值對應(yīng)的統(tǒng)計(jì)量進(jìn)行精確估計(jì)，只需要確保經(jīng)過散列后的函數(shù)值滿足均勻性分布即可，所以采用文獻(xiàn)[19]中提出的通用散列函數(shù)簇，即

其中，p是大于identity空間[N]k元素個(gè)數(shù)的素?cái)?shù)，δi為素?cái)?shù)空間[p]中任意元素，k表示通用散列函數(shù)級(jí)別，因本文所提方法不需要文獻(xiàn)[9,10]中對單個(gè)散列桶內(nèi)統(tǒng)計(jì)量進(jìn)行精度估計(jì)，為了較少計(jì)算復(fù)雜度，k取值2。

Filter-ary-Sketch數(shù)據(jù)結(jié)構(gòu)在單個(gè)維度上用一個(gè)h行M列的二維數(shù)組來存儲(chǔ)統(tǒng)計(jì)量，對應(yīng)h×M個(gè)計(jì)數(shù)器。數(shù)組的每一行對應(yīng)一個(gè)散列函數(shù)，每行中的M個(gè)計(jì)數(shù)器表示散列函數(shù)的M個(gè)桶，每個(gè)計(jì)數(shù)器記錄散列到此桶的數(shù)據(jù)流元素的特征值統(tǒng)計(jì)量，其中 Mi[0]用于存儲(chǔ)熵值計(jì)算的結(jié)果。所提方法需要在多個(gè)維度上進(jìn)行熵值計(jì)算，同樣也需要在各個(gè)維度上構(gòu)建Filter-ary-Sketch概要數(shù)據(jù)結(jié)構(gòu)，整個(gè)概要數(shù)據(jù)結(jié)構(gòu)的結(jié)構(gòu)如圖1所示。

為了在異常檢測后能夠?qū)阂饬髁窟M(jìn)行阻斷，在每個(gè)散列函數(shù)輸出桶位置對應(yīng)一個(gè) Bloom Filter數(shù)據(jù)結(jié)構(gòu)，存儲(chǔ)散列到該桶內(nèi)的源IP地址。Bloom Filter是一種空間效率很高的隨機(jī)數(shù)據(jù)結(jié)構(gòu)，它利用位數(shù)組很簡潔地表示一個(gè)集合，并能快速判斷一個(gè)元素是否屬于這個(gè)集合。通過Bloom Filter數(shù)據(jù)結(jié)構(gòu)存儲(chǔ)投影到該桶的源IP地址，當(dāng)有異常發(fā)生時(shí)，首先尋找異常點(diǎn)對應(yīng)的散列函數(shù)存儲(chǔ)桶，對新到達(dá)的IP數(shù)據(jù)分組提取源IP地址，在異常桶位置對應(yīng)的Bloom Filter上進(jìn)行查詢，然后根據(jù)多個(gè)Bloom Filter上的查詢結(jié)果綜合判斷是否屬于惡意 IP，從而實(shí)現(xiàn)惡意流量阻斷。Bloom Filter具體的工作原理參看文獻(xiàn)[18]，在此不再贅述。

圖1 Filter-ary-Sketch數(shù)據(jù)結(jié)構(gòu)

在 Filter-ary-Sketch數(shù)據(jù)結(jié)構(gòu)上定義了更新(update)操作、熵值計(jì)算(calculate-entropy)操作、異常點(diǎn)定位(detect-locate)3類操作，詳細(xì)的操作流程將在第3部分詳細(xì)闡述。

2.3 基于熵的異常檢測算法

在每個(gè)時(shí)間周期完成數(shù)據(jù)記錄后，需要在Filter-ary-Sketch數(shù)據(jù)結(jié)構(gòu)上計(jì)算該時(shí)間周期內(nèi)流量數(shù)據(jù)在各個(gè)維度上的熵值，然后把當(dāng)前時(shí)刻的熵值和前一時(shí)刻的熵值進(jìn)行對比，如果熵值的差超過一定范圍則認(rèn)為在該維度上出現(xiàn)了異常。首先給出熵異常檢測算法的相關(guān)概念。

數(shù)據(jù)項(xiàng)出現(xiàn)的次數(shù)定義為mi，其中i∈[n]，例如目的端口為i的IP數(shù)據(jù)分組的數(shù)目；當(dāng)前時(shí)間周期內(nèi)數(shù)據(jù)流中數(shù)據(jù)項(xiàng)的總數(shù)定義為 m，則。在每個(gè)時(shí)間周期內(nèi)，并不是所有的 n個(gè)標(biāo)識(shí)都有相應(yīng)的數(shù)據(jù)項(xiàng)出現(xiàn)。定義 aj∈[n] 為當(dāng)前時(shí)間周期內(nèi)數(shù)據(jù)流上的第j個(gè)數(shù)據(jù)項(xiàng)，n0為當(dāng)前時(shí)間周期內(nèi)出現(xiàn)的不同數(shù)據(jù)項(xiàng)的數(shù)目，熵定義為。熵是對到達(dá)的數(shù)據(jù)流隨機(jī)性的度量，當(dāng)所有到達(dá)的數(shù)據(jù)項(xiàng)相同時(shí)熵取最小值0，當(dāng)所有到達(dá)的數(shù)據(jù)項(xiàng)都不同時(shí)熵取最大值logm，為了描述地簡潔，本文所有對數(shù)統(tǒng)一默認(rèn)以2為底數(shù)，且0log0=0。為了在各個(gè)時(shí)間周期上和不同維度上對比熵值，需要對熵值進(jìn)行歸一化處理，定義標(biāo)準(zhǔn)熵為，熵值計(jì)算過程可描述為

對S的準(zhǔn)確估算并不一定能夠獲得一個(gè)誤差足夠小的熵估計(jì)值，在實(shí)際的計(jì)算過程中，如果H值很小，S值趨向于它的最大值時(shí)，計(jì)算S值時(shí)一個(gè)很小的誤差可能導(dǎo)致H值出現(xiàn)無法接受的誤差，定義為通過計(jì)算獲得的熵估計(jì)值，即下面的定理保證通過對S的估計(jì)值來估算H值是合理的。

下面給出 Filter-ary-Sketch數(shù)據(jù)結(jié)構(gòu)上基于熵的異常檢測算法：

算法1 異常檢測算法

1) for each dimensionality dk

2) for each row in Sketch ri

Detect processing

6) for each dimensionality dk

7) for each row in Sketch ri

9) A larmk←add

11) A larmk←cut

12) Type_reveal( A larm1, Alarm2, … ,A larmd)

算法復(fù)雜度分析：該算法具有很好的并行性，各個(gè)維度上沒有任何數(shù)據(jù)依賴，可以直接分配到不同的處理器上執(zhí)行，在此只分析每個(gè)維度的算法復(fù)雜度。熵值計(jì)算過程的時(shí)間復(fù)雜為O(ploy(M))，其中M為Filter-ary-Sketch數(shù)據(jù)結(jié)構(gòu)中每個(gè)維度的散列數(shù)組長度，檢測過程的時(shí)間復(fù)雜度也為O(ploy(M))。熵值計(jì)算算法在常數(shù)時(shí)間內(nèi)可以完成，不隨著網(wǎng)絡(luò)流量的增加而增加，當(dāng)然這樣也帶來了一定誤差，當(dāng)網(wǎng)絡(luò)流量增大時(shí)散列函數(shù)桶內(nèi)的碰撞概率增大，在某些維度上檢測精度可能會(huì)降低，但在其他維度上則不會(huì)受影響，可以通過增加檢測維度的方法來提高檢測精度。算法中δ的選擇決定了算法漏報(bào)率和誤報(bào)率水平，可以通過機(jī)器學(xué)習(xí)等方法獲得合適的δ值。

3 異常檢測流程

異常檢測的流程可分為3個(gè)部分：利用Filter-ary-Sketch數(shù)據(jù)結(jié)構(gòu)進(jìn)行數(shù)據(jù)記錄、異常檢測和惡意流量阻斷。

3.1 數(shù)據(jù)記錄

為了后期進(jìn)行異常點(diǎn)定位，該系統(tǒng)需要2個(gè)同樣的Filter-ary-Sketch數(shù)據(jù)結(jié)構(gòu)，分別記錄當(dāng)前時(shí)刻和前一時(shí)間的流量信息，同時(shí)需要在當(dāng)前時(shí)刻Filter-ary-Sketch數(shù)據(jù)結(jié)構(gòu)散列桶位置存放Bloom Filter，利用它記錄投影到該位置的源IP地址，Bloom Filter隨著當(dāng)前時(shí)刻的Filter-ary-Sketch數(shù)據(jù)結(jié)構(gòu)一起更新。在異常檢測階段利用2個(gè)Filter-ary-Sketch數(shù)據(jù)結(jié)構(gòu)中記錄的值差異進(jìn)行異常檢測，在惡意流量阻斷階段根據(jù)各個(gè)散列桶當(dāng)前時(shí)刻值和前一時(shí)刻值的差異來定位異常，并根據(jù)異常點(diǎn)位置的Bloom Filter記錄的源IP地址信息進(jìn)行惡意流量阻斷。

初始狀態(tài)時(shí)，F(xiàn)ilter-ary-Sketch數(shù)據(jù)結(jié)構(gòu)中每個(gè)散列桶初始值為0，每個(gè)散列桶對應(yīng)的Bloom Filter每位都初始化為0。在每個(gè)時(shí)間周期內(nèi)，用每個(gè)新到達(dá)的數(shù)據(jù)項(xiàng)更新Filter-ary-Sketch數(shù)據(jù)結(jié)構(gòu)，具體過程如下。

1) 當(dāng)一個(gè)數(shù)據(jù)項(xiàng)(＜SIPi, Dporti, Plengthi＞,ui)到達(dá)時(shí)，首先投影到各個(gè)不同維度，在各個(gè)維度上計(jì)算hd個(gè)散列函數(shù)值，得到Md個(gè)計(jì)數(shù)器中的對應(yīng)項(xiàng)，hashk( identityi)∈｛1,…,Md｝,k∈{1,…,hd}。

2) 對每個(gè)hashk( identityi)標(biāo)識(shí)的計(jì)數(shù)器統(tǒng)計(jì)值進(jìn)行更新，即：T[ k][ hashk( identityi)]+=ui，其中k∈｛1,…,hd｝。

3) 用該數(shù)據(jù)項(xiàng)的SIPi更新對應(yīng)散列函數(shù)桶位置的Bloom Filter。

4) 當(dāng)時(shí)間周期結(jié)束時(shí)，計(jì)算Filter-ary-Sketch中各個(gè)維度每行的值，并存儲(chǔ)到T[ k][0]。

5) 把該Filter-ary-Sketch標(biāo)識(shí)為當(dāng)前記錄Sketch，另一Filter-ary-Sketch標(biāo)識(shí)為最近記錄Sketch，轉(zhuǎn)異常檢測流程。

算法需要對采集到的每個(gè)數(shù)據(jù)項(xiàng)進(jìn)行處理，所提方法對每個(gè)數(shù)據(jù)項(xiàng)的處理過程分為3個(gè)階段，投影、更新Sketch數(shù)據(jù)結(jié)構(gòu)和更新Bloom Filter。投影的計(jì)算復(fù)雜度為O(ploy(D))，其中D為需要投影的維度，更新Sketch數(shù)據(jù)結(jié)構(gòu)的時(shí)間復(fù)雜度為O(c+ploy(h))，其中c為散列函數(shù)計(jì)算時(shí)間，h為Sketch數(shù)據(jù)結(jié)構(gòu)的行數(shù)，而更新Bloom Filter的時(shí)間復(fù)雜度也為常數(shù)[18]。綜上，對每個(gè)數(shù)據(jù)項(xiàng)可以在常數(shù)時(shí)間內(nèi)處理完成，并不隨著網(wǎng)絡(luò)流量數(shù)據(jù)的增加而增加，當(dāng)然更新過程總體的時(shí)間復(fù)雜度為O(m)，其中m為到達(dá)數(shù)據(jù)分組的數(shù)目，隨著流量數(shù)據(jù)的增加成線性增長，但是可以采用采樣的方式降低計(jì)算復(fù)雜度，通過文獻(xiàn)[4]的方法進(jìn)行實(shí)驗(yàn)，當(dāng)網(wǎng)絡(luò)流量數(shù)據(jù)中每秒到達(dá)的數(shù)據(jù)項(xiàng)個(gè)數(shù)在106量級(jí)時(shí)，所提方法采樣率為10%時(shí)依然能夠獲得很好的檢測精度。

3.2 異常檢測流程

在每個(gè)時(shí)間周期完成數(shù)據(jù)記錄過程后，需要根據(jù)計(jì)算得到該時(shí)間周期內(nèi)流量數(shù)據(jù)在各個(gè)維度上的值和最近一次時(shí)間周期內(nèi)值的對比來進(jìn)行異常檢測，具體檢測過程如下所述。

2) 根據(jù)各個(gè)維度上異常情況判斷異常是否真的發(fā)生，如果發(fā)生判斷事件類型。其中通過多個(gè)維度異常檢測結(jié)果進(jìn)行異常判斷可采用多種方法，如基于規(guī)則的方法、投票的方法、聚類方法等，在本文實(shí)驗(yàn)中采用簡單的投票方法，多維綜合檢測將在下一步工作中進(jìn)行研究。

4) 取Cij對應(yīng)的Bloom Filter，轉(zhuǎn)惡意流量阻斷流程。

3.3 惡意流量阻斷

在檢測到異常后，首先需要根據(jù)Filter-ary-Sketch數(shù)據(jù)結(jié)構(gòu)內(nèi)每個(gè)散列桶位置當(dāng)前時(shí)刻值和最近時(shí)刻值的差異定位異常點(diǎn)，利用異常點(diǎn)位置對應(yīng)的Bloom Filter內(nèi)存儲(chǔ)的源IP地址進(jìn)行惡意流量阻斷。具體的流程如下。

1) 對下一時(shí)刻到達(dá)的數(shù)據(jù)分組，取出源IP地址，分別在各個(gè)Bloom Filter上進(jìn)行查詢判斷。

2) 如果在每個(gè)Bloom Filter上判斷都成功，則該IP是惡意流量IP，即該IP屬于。

3) 對惡意IP的流量進(jìn)行阻斷。

由于Bloom Filter本身存在假陽性問題，惡意流量阻斷同樣也存在誤差，下面分析惡意流量阻斷的精度。

惡意流量阻斷誤差主要來源于2個(gè)方面，Bloom Filter帶來的假陽性錯(cuò)誤和Sketch隨機(jī)投影帶來的誤差。按照Bloom Filter理論，設(shè)集合S=｛x1, x2,…,xn｝,為了表示這樣一個(gè)n個(gè)元素的集合，Bloom Filter使用k個(gè)相互獨(dú)立的散列函數(shù)，它們分別將集合中的每個(gè)元素映射到{1,2,…,m}的范圍中，則該Bloom Filter的誤差f=(1-e-knm)k，那么一個(gè)不屬于惡意IP的IP地址在所有異常點(diǎn)對應(yīng)的Bloom Filter都出現(xiàn)假陽性錯(cuò)誤概率為(1-e-kn/m)h·k，其中h是Sketch數(shù)據(jù)結(jié)構(gòu)中散列函數(shù)的個(gè)數(shù)。在Filter-ary-Sketch的構(gòu)建過程中知道，每個(gè)散列桶對應(yīng)的元素個(gè)數(shù)Ai均值為a/Md，其中a為數(shù)據(jù)流每個(gè)時(shí)間周期內(nèi)數(shù)據(jù)項(xiàng)個(gè)數(shù)的平均值，Md為某個(gè)維度散列桶的個(gè)數(shù)，當(dāng)前維度的Sketch數(shù)據(jù)結(jié)構(gòu)有hd個(gè)獨(dú)立散列函數(shù)，那么一個(gè)不屬于惡意IP地址的源IP同時(shí)出現(xiàn)在Hh個(gè)異常點(diǎn)的概率為(1/Md)hd。綜上，只要合理地選擇Sketch數(shù)據(jù)結(jié)構(gòu)中散列函數(shù)的個(gè)數(shù)h、Bloom Filter中散列函數(shù)數(shù)目以及數(shù)據(jù)位數(shù)m就可以控制2個(gè)方面的誤差，把惡意流量阻斷系統(tǒng)的精度控制在可接受的范圍內(nèi)。

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

為了驗(yàn)證所提檢測方法的有效性和合理性，并與文獻(xiàn)[10]和文獻(xiàn)[20]的方法進(jìn)行對比，設(shè)計(jì)了2個(gè)實(shí)驗(yàn)。實(shí)驗(yàn)1采用的是CAIDA組織發(fā)布的2007年互聯(lián)網(wǎng)中實(shí)際爆發(fā)的一次大規(guī)模DDoS攻擊數(shù)據(jù)[21]，主要從檢測時(shí)間和所需存儲(chǔ)空間2方面進(jìn)行對比試驗(yàn)。實(shí)驗(yàn)2采用NLANR PMA組在Internet 2實(shí)驗(yàn)網(wǎng)上采集的一段含有異常事件的流量數(shù)據(jù)，主要從檢測精度方面進(jìn)行對比試驗(yàn)。

4.1 效率對比實(shí)驗(yàn)

CAIDA發(fā)布的DDoS attack 2007數(shù)據(jù)集為發(fā)生在2007年8月4日的一次大規(guī)模DDoS攻擊流量數(shù)據(jù)，主要消耗被攻擊主機(jī)的計(jì)算資源和網(wǎng)絡(luò)帶寬。實(shí)驗(yàn)1主要使用DDoS攻擊開始的前10min數(shù)據(jù)進(jìn)行實(shí)驗(yàn)，分析所提異常檢測方法在時(shí)間和空間上特性。因?yàn)閿?shù)據(jù)集不包含正常的網(wǎng)絡(luò)流量，采用WIDE組織[22]在穿越太平洋的骨干鏈路上采集的流量數(shù)據(jù)作為正常流量，數(shù)據(jù)分組含2005年1月7日13:00到13:10分的流量。具體的流量信息如圖2所示，DDoS攻擊發(fā)生于第6min附近，目的IP71.126.222.64的流量由每分鐘4 000個(gè)IP分組劇增到每分鐘8×105個(gè)IP分組?？傮w流量上，數(shù)據(jù)分組峰值達(dá)到每秒2.2×104，假設(shè)每個(gè)數(shù)據(jù)分組在數(shù)據(jù)鏈路層大小為100byte，則該骨干網(wǎng)的流量達(dá)到174Mbit/s，通過實(shí)驗(yàn)已經(jīng)證明所提方法在采樣率為10%時(shí)，依然有較好的檢測精度，所以該方法能夠在吉比特每秒級(jí)別的網(wǎng)絡(luò)上進(jìn)行異常檢測，當(dāng)然，本文所有實(shí)驗(yàn)都通過C語言實(shí)現(xiàn)，下一步將通過硬件平臺(tái)實(shí)現(xiàn)，有望進(jìn)一步改善性能。

圖2 網(wǎng)絡(luò)流量

在試驗(yàn)中除了實(shí)現(xiàn)本文所提檢測方法外，還實(shí)現(xiàn)了文獻(xiàn)[10,20]所提方法，分別在該數(shù)據(jù)集上進(jìn)行異常檢測。本文所提方法具有很好的并行性，在異常檢測時(shí)，以3個(gè)維度上最長的計(jì)算時(shí)間作為總的檢測計(jì)算時(shí)間。Filter-ary-Sketch數(shù)據(jù)結(jié)構(gòu)的參數(shù)h和M采用和文獻(xiàn)[20]中一樣的設(shè)置，每個(gè)維度h取值8，源IP維度的M值取1 024，端口維和IP數(shù)據(jù)分組長度維M取值256；檢測算法的閾值取值0.1 logmm，其中0.1是對H歸一化后的閾值；檢測的時(shí)間周期為2min。

檢測方法的計(jì)算時(shí)間對比：3個(gè)方法都是基于概要數(shù)據(jù)結(jié)構(gòu)的檢測方法，主要對比每個(gè)周期數(shù)據(jù)記錄和檢測異常2部分時(shí)間，圖3是3個(gè)方法各個(gè)時(shí)間周期上計(jì)算時(shí)間的對比，IP traceability是文獻(xiàn)[20]所提方法，Sketch是文獻(xiàn)[10]所提方法，從圖中看出所提方法比文獻(xiàn)[10]的方法耗時(shí)多，但明顯優(yōu)于文獻(xiàn)[20]的方法。比文獻(xiàn)[10]的方法耗時(shí)多是因?yàn)槲墨I(xiàn)[10]所提方法不具備IP還原或惡意流量阻斷功能，而優(yōu)于文獻(xiàn)[20]主要是因?yàn)椋孩俨捎昧嘶陟刂档漠惓z測，不需要計(jì)算誤差Sketch結(jié)構(gòu)；②采用了Bloom Filter結(jié)構(gòu)記錄源IP地址，更新源IP集可以在常數(shù)時(shí)間內(nèi)完成。

圖3 計(jì)算時(shí)間對比

所需存儲(chǔ)空間對比：因?yàn)槲墨I(xiàn)[10]不具備惡意流量定位和阻斷功能，所需空間僅為Sketch存儲(chǔ)空間，在這里主要和文獻(xiàn)[20]的方法進(jìn)行對比。圖4為3種方法在數(shù)據(jù)集上所需要的存儲(chǔ)開銷對比，從圖中看出，本文所提方法優(yōu)于文獻(xiàn)[20]的方法，主要是因?yàn)椴捎肂loom Filter結(jié)構(gòu)記錄源IP地址，但同時(shí)也帶來了一定的誤差。

圖4 存儲(chǔ)開銷對比

4.2 精度對比實(shí)驗(yàn)

精度對比實(shí)驗(yàn)(實(shí)驗(yàn)2)數(shù)據(jù)采用NLANR PMA組在Internet2 實(shí)驗(yàn)網(wǎng)上獲取的真實(shí)網(wǎng)絡(luò)流量trace數(shù)據(jù)。為了和文獻(xiàn)[10,20]工作進(jìn)行對比，選取IPLS-KSCY 數(shù)據(jù)，該數(shù)據(jù)為美國Indianapolis 到Kansas City 的OC192 鏈路數(shù)據(jù)，時(shí)間為2004年8月19日，每個(gè)數(shù)據(jù)文件持續(xù)時(shí)間長度為10min，本文選擇下午2點(diǎn)的6個(gè)trace文件順序連接成一個(gè)小時(shí)。6個(gè)Trace文件的主要特性見表1。

參數(shù)選擇：該異常檢測方法涉及到的參數(shù)主要有：檢測的維度D、選擇源IP、目的端口和數(shù)據(jù)分組長度3個(gè)維度；Filter-ary-Sketch數(shù)據(jù)結(jié)構(gòu)參數(shù)h和M也按照文獻(xiàn)[20]所提供的設(shè)置方式設(shè)置，每個(gè)維度h取值8，源IP維度的M值取1 024，端口維和數(shù)據(jù)分組長度維取值256；檢測算法的閾值取值0.1m log(m)，其中0.1是對熵值H歸一化后的閾值；為了提高檢測精度，檢測的滑動(dòng)窗口時(shí)間長度取值2min。Bloom Filter中依據(jù)c=(1-e-knm)k進(jìn)行參數(shù)設(shè)置，其中c=0.05為假陽性概率，k=8為散列的數(shù)量，n是Filter里keys的數(shù)量，m是Filter的位長，從實(shí)際數(shù)據(jù)統(tǒng)計(jì)情況來看，n=100，所以計(jì)算得出m=688。

表1 Trace文件流量特征

實(shí)驗(yàn)結(jié)果：為了能與其他基于熵值的算法進(jìn)行比較，通過計(jì)算得到值換算成熵值，圖6為3個(gè)維度上熵值曲線，其中目的端口維和源IP維度的熵值曲線有較強(qiáng)的相關(guān)性，而包長度維的熵值對該時(shí)段內(nèi)的異常并不太敏感，不過依然可以為異常檢測提供有效的輔助信息。圖5中出現(xiàn)了4個(gè)異常點(diǎn)，分別在14:14-14:18, 14:26-14:30, 14:42-14:44, 14:44-14:56時(shí)間段。通過對流量的詳細(xì)分析，發(fā)現(xiàn)在這幾個(gè)時(shí)間點(diǎn)上都出現(xiàn)了流量異常，如在14:42-14:44時(shí)間段，目的IP為10.1.130.153的IP數(shù)據(jù)分組從20多萬突然增加到140多萬個(gè)，這種流量的突然變遷代表了網(wǎng)絡(luò)中出現(xiàn)了異常情況，根據(jù)3個(gè)維度上熵值的變化情況可以初步判定造成這樣異常的原因可能是針對該目的IP的 DDoS攻擊或者突發(fā)訪問。在其他3個(gè)時(shí)間點(diǎn)上也同樣出現(xiàn)了一些目的IP流量上發(fā)生較大突變的情況，圖6給出了幾個(gè)目的IP上流量的異常變化情況。

圖5 熵值曲線

圖6 異常IP流量

該方法能檢測到文獻(xiàn)[10]所提方法檢測到的4個(gè)異常點(diǎn)，文獻(xiàn)[20]所提方法還能檢測到一些其他的異常點(diǎn)，不過會(huì)帶來很高的誤報(bào)率。在對文獻(xiàn)[20]方法檢測到的其他異常點(diǎn)進(jìn)行分析的過程中發(fā)現(xiàn)，其他異常點(diǎn)發(fā)生時(shí)網(wǎng)絡(luò)中各個(gè)主機(jī)流量并沒有出現(xiàn)大的突變，所以本文所提方法在誤報(bào)率和漏報(bào)率上是一個(gè)較好的折中。在惡意流量阻斷方面，本文所提方法錯(cuò)誤阻斷率小于 3%，如在 14:42-14:44時(shí)間段，目的IP為 10.1.130.153的數(shù)據(jù)分組阻斷方面，通過 Bloom Filter的記錄和查詢操作后，所有的源IP都能被成功過濾，只有小量的源IP被錯(cuò)誤阻斷，該部分IP只占全部阻斷IP的2%，雖然文獻(xiàn)[20]所提方法比本文方法的惡意 IP定位準(zhǔn)確度高，但是以高的存儲(chǔ)開銷和高的計(jì)算時(shí)間為代價(jià)。

基于Filter-ary-Sketch的檢測方法的優(yōu)點(diǎn)如下：①當(dāng)網(wǎng)絡(luò)流量在整體上看不出異常時(shí)，F(xiàn)ilter-ary-Sketch中的某個(gè)維度上的計(jì)數(shù)器可能表現(xiàn)異常。它在空間復(fù)雜度上和時(shí)間復(fù)雜度上都遠(yuǎn)遠(yuǎn)優(yōu)于基于per flow 的檢測，特別在當(dāng)前高速骨干鏈路上基于per flow的檢測方法基本上無法適應(yīng)的情況下，該方法能夠滿足檢測的要求。②基于Filter-ary-Sketch的異常檢測能夠檢測隱藏于大量背景流量下的異常，優(yōu)于基于整體流量特征的檢測(把整個(gè)網(wǎng)絡(luò)流量看成一個(gè)時(shí)間序列，采用時(shí)間序列相關(guān)方法進(jìn)行異常檢測)。③基于 Filter-ary-Sketch的異常檢測能檢測只在特定維度上呈現(xiàn)異常行為的異常，且能夠根據(jù)各個(gè)維度熵值的不同變化提供詳細(xì)異常信息。

5 結(jié)束語

為了解決高速骨干網(wǎng)上異常檢測面臨的問題，本文首先提出 Filter-ary-Sketch數(shù)據(jù)結(jié)構(gòu)存儲(chǔ)骨干網(wǎng)上流量信息，然后在該概要數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)上采用改進(jìn)的基于熵的異常檢測算法，在多個(gè)維度上進(jìn)行基于熵的異常檢測，增加檢測精度，且根據(jù)多個(gè)維度上熵值的計(jì)算結(jié)果判斷大規(guī)模網(wǎng)絡(luò)安全事件類型，最后根據(jù)Filter-ary-Sketch中Bloom Filter記錄的源IP地址有效地進(jìn)行惡意流量阻斷。通過實(shí)驗(yàn)驗(yàn)證了該異常檢測方法在一定的精度條件要求下時(shí)間復(fù)雜度和空間復(fù)雜度相對其他算法更低。

但是本文提出的在 Filter-ary-Sketch數(shù)據(jù)結(jié)構(gòu)上基于熵的異常檢測算法并沒有理論上的精度保證，在基于熵的異常檢測維度選擇以及多維度整合方面也需要進(jìn)一步的理論和實(shí)驗(yàn)證明，這些都將是下一步工作的重點(diǎn)。

[1] WANG H N, ZHANG D L, SHIN K G. Change-point monitoring for the detection of DoS attacks[J]. IEEE Transactions on Dependable and Secure Computing, 2004, 1(4):193-208.

[2] 嚴(yán)芬, 陳軼群, 黃皓. 使用補(bǔ)償非參數(shù)CUSUM方法檢測DDoS攻擊[J]. 通信學(xué)報(bào). 2008, 29(6):126-132.YAN F, CHEN Y Q, HUANG H. Detecting DDoS attack based on compensation non-parameter CUSUM algorithm[J]. Journal on Conmmunications, 2008,29(6): 126-132.

[3] JUNG J, PAXSON V, BERGER A W. Fast portscan detection using sequential hypothesis testing[A]. Proceedings of the IEEE Symposium on Security and Privacy[C]. 2004.

[4] MAI J N, CHUAH C N, SRIDHARAN A. Is sampled data sufficient for anomaly detection[A]. Proceedings of the 6th ACM SIGCOMM conference on Internet measurement[C]. 2006.

[5] KOMPELLA R R, SINGH S, VARGHESE G. On scalable attack detection in the network[A]. Proceedings of the 4th ACM SIGCOMM Conference on Internet Measurement[C]. 2004.

[6] LAKHINA A, CROVELLA M, DIOT C. Mining anomalies using traffic feature distributions[A]. SIGCOMM[C]. 2005.

[7] MUTHUKRISHNAN S. Data stream: algorithms and applications[A].Proceedings of the 14th annual ACM-SIAM Symposium on Discrete Algorithms[C]. 2003.

[8] CORMODE G, MUTHUKRISHNAN S. An improved data stream summary: the count-min sketch and its applications[J]. Journal of Algorithms,2005,55(1).

[9] KRISHNAMURTHY B, SEN S, ZHANG Y. Sketch-based change detection: methods, evaluation, and applications[A]. Proceedings of the 3th ACM SIGCOMM conference on Internet measurement[C]. 2003.

[10] SCHWELLER R, LI Z C, CHEN Y. Reverse hashing for high-speed network monitoring: algorithm, evaluation, and applications[A]. IEEE Infocom[C]. 2006.

[11] DEWAELE G, FUKUDA K, BORGNAT P. Extracting hidden anomalies using sketch and non gaussian multiresolution statistical detection procedures[A]. Proceedings of the 2007 workshop on Large scale attack defense[C]. 2007.

[12] XU K, ZHANG Z L, Supratik bhattacharyya. profiling internet backbone traffic: behavior models and applications[A]. ACM Sigcomm[C]. 2005.

[13] WAGNER A, PLATTNER B. Entropy based worm and anomaly detection in fast IP networks[A]. Proceedings of the 14th IEEE Internatinal Workshops on Enabling Technologies: Infrastructure for Collaborative Enterprise[C]. 2005.

[14] GU Y, MCCALLUM A, TOWSLEY D. Detecting anomalies in network traffic using maximum entropy estimation[A]. Proceedings of the 5th ACM Sigcomm Conference on Internet Measurement[C].2005.

[15] NYCHIS G, SEKAR V, ANDERSEN D G. An empirical evaluation of entropy-based traffic anomaly detection[A]. Proceedings of the 8th ACM SIGCOMM Conference on Internet Measurement[C]. 2008.

[16] LI X, BIAN F, CROVELLA M. Detection and identification of network anomalies using sketch subspaces[A]. Proceedings of the 6th ACM Sigcomm Conference on Internet Measurement[C]. 2006.

[17] ZHAO H Q, LALL A, OGIHARA M. A data streaming algorithm for estimating entropies of OD flows[A]. Proceedings of the 7th ACM Sigcomm Conference on Internet Measurement[C]. 2007.

[18] BRODER A, MITZENMACHER M. Network applications of bloom filters: a survey[J]. Internet Mathematics, 2004, 1(4):485-509.

[19] WEGMAN M, CARTER J. New hash functions and their use in authentication and set equality[J]. Journal of Computer and System Sciences, 1981,22(3):265-279

[20] 羅娜, 李愛平, 吳泉源. 基于概要數(shù)據(jù)結(jié)構(gòu)可溯源的異常檢測方法[J]. 軟件學(xué)報(bào),2009,20(10):2899-2906.LUO N, LI A P, WU Q Y. Sketch-based anomalies detection with IP address traceability[J]. Journal of Software. 2009,20(10):2899-2906.

[21] The cooperative association for internet data analysis(CAIDA)[EB/OL]. http://www.caida.org/data.

[22] Measurement and analysis on the WIDE Internet (MAWI) working group traffic archive[EB/OL]. http://mawi.wide.ad.jp/mawi/.