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

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

1 引言

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

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

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

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

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

為了提高異常檢測系統(tǒng)的檢測精度，研究者開始通過對流量數(shù)據(jù)的分布特征進行監(jiān)控來檢測異常，采用熵對分布特征進行度量?；陟氐漠惓z測系統(tǒng)的主要思想是：一旦有異常流量發(fā)生時，總體流量在各個維度上的分布應(yīng)該會發(fā)生變化，通過熵值的變化能夠檢測出該異常。文獻[12]通過流量特征上的熵值把流量分為異常和正常2類分量來進行異常檢測；文獻[13]首次提出在高速IP網(wǎng)絡(luò)上利用熵值來檢測蠕蟲和流量異常；文獻[14]通過比較當(dāng)前分布和基準(zhǔn)分布的差異來進行異常檢測，且基于最大熵原理，提出了一種靈活計算基準(zhǔn)分布的方法；文獻[15]通過把分布的特征分為2類：數(shù)據(jù)分組頭特征和行為特征，發(fā)現(xiàn)它們熵值序列之間的相關(guān)性，提出了在實現(xiàn)基于熵的異常檢測系統(tǒng)時需要注意的若干問題。但是上述算法的空間和時間復(fù)雜度較高，通常時間復(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)上進行異常檢測。首先把骨干網(wǎng)上海量流量數(shù)據(jù)通過 Hash映射隨機投影到Filter-ary-Sketch數(shù)據(jù)結(jié)構(gòu)中，再通過熵值的變化來檢測異常，通過不同維度熵值變化情況來判斷異常類型。檢測到異常后，通過 Filter-ary-Sketch中各個桶內(nèi)統(tǒng)計量差值的變化情況來定位異常點，最后通過Bloom Filter中存儲的源IP信息進行惡意流量阻斷。

本文主要貢獻：

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ò)流量各維度熵值進行高效并行計算，解決以往基于熵的異常檢測不能進行實時異常檢測和不適應(yīng)高速骨干網(wǎng)的問題。

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

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

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

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

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

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

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

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

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

散列函數(shù)是隨機投影技術(shù)的核心，它把高維度的流量數(shù)據(jù)向低緯度空間進行隨機投影，是一種典型的壓縮映射。散列函數(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ù)簇隨機取一個函數(shù)，具有性質(zhì)：?x,y∈A，且 x≠y，則 P(f(x)=f(y))≤1/|B|。

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

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

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

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

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

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

2.3 基于熵的異常檢測算法

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

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

對S的準(zhǔn)確估算并不一定能夠獲得一個誤差足夠小的熵估計值，在實際的計算過程中，如果H值很小，S值趨向于它的最大值時，計算S值時一個很小的誤差可能導(dǎo)致H值出現(xiàn)無法接受的誤差，定義為通過計算獲得的熵估計值，即下面的定理保證通過對S的估計值來估算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ù)雜度分析：該算法具有很好的并行性，各個維度上沒有任何數(shù)據(jù)依賴，可以直接分配到不同的處理器上執(zhí)行，在此只分析每個維度的算法復(fù)雜度。熵值計算過程的時間復(fù)雜為O(ploy(M))，其中M為Filter-ary-Sketch數(shù)據(jù)結(jié)構(gòu)中每個維度的散列數(shù)組長度，檢測過程的時間復(fù)雜度也為O(ploy(M))。熵值計算算法在常數(shù)時間內(nèi)可以完成，不隨著網(wǎng)絡(luò)流量的增加而增加，當(dāng)然這樣也帶來了一定誤差，當(dāng)網(wǎng)絡(luò)流量增大時散列函數(shù)桶內(nèi)的碰撞概率增大，在某些維度上檢測精度可能會降低，但在其他維度上則不會受影響，可以通過增加檢測維度的方法來提高檢測精度。算法中δ的選擇決定了算法漏報率和誤報率水平，可以通過機器學(xué)習(xí)等方法獲得合適的δ值。

3 異常檢測流程

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

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

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

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

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

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

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

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

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

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

3.2 異常檢測流程

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

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

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

3.3 惡意流量阻斷

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

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

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

3) 對惡意IP的流量進行阻斷。

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

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

4 實驗與結(jié)果分析

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

4.1 效率對比實驗

CAIDA發(fā)布的DDoS attack 2007數(shù)據(jù)集為發(fā)生在2007年8月4日的一次大規(guī)模DDoS攻擊流量數(shù)據(jù)，主要消耗被攻擊主機的計算資源和網(wǎng)絡(luò)帶寬。實驗1主要使用DDoS攻擊開始的前10min數(shù)據(jù)進行實驗，分析所提異常檢測方法在時間和空間上特性。因為數(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個IP分組劇增到每分鐘8×105個IP分組?？傮w流量上，數(shù)據(jù)分組峰值達到每秒2.2×104，假設(shè)每個數(shù)據(jù)分組在數(shù)據(jù)鏈路層大小為100byte，則該骨干網(wǎng)的流量達到174Mbit/s，通過實驗已經(jīng)證明所提方法在采樣率為10%時，依然有較好的檢測精度，所以該方法能夠在吉比特每秒級別的網(wǎng)絡(luò)上進行異常檢測，當(dāng)然，本文所有實驗都通過C語言實現(xiàn)，下一步將通過硬件平臺實現(xiàn)，有望進一步改善性能。

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

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

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

圖3 計算時間對比

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

圖4 存儲開銷對比

4.2 精度對比實驗

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

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

表1 Trace文件流量特征

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

圖5 熵值曲線

圖6 異常IP流量

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

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

5 結(jié)束語

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

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

[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)芬, 陳軼群, 黃皓. 使用補償非參數(shù)CUSUM方法檢測DDoS攻擊[J]. 通信學(xué)報. 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é)報,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/.