基于Filter-ary-Sketch數據結構的骨干網異常檢測研究

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

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

1 引言

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

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

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

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

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

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

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

本文主要貢獻：

1) 在 k-ary概要數據結構的基礎上，提出了Filter-ary-Sketch概要數據結構，解決了以往異常檢測后不能直接定位異常流量的問題。

2) 在 Filter-ary-Sketch數據結構上對網絡流量各維度熵值進行高效并行計算，解決以往基于熵的異常檢測不能進行實時異常檢測和不適應高速骨干網的問題。

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

第2節對異常檢測中的關鍵數據結構和算法進行描述，第3節對異常檢測流程進行詳細描述，第4節使用真實數據驗證本文所提檢測方法的有效性，第5節為結束語。

2 數據模型與算法

2.1 多維十字轉門模型

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

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

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

2.2 Filter-ary-Sketch數據結構

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

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

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

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

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

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

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

圖1 Filter-ary-Sketch數據結構

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

2.3 基于熵的異常檢測算法

在每個時間周期完成數據記錄后，需要在Filter-ary-Sketch數據結構上計算該時間周期內流量數據在各個維度上的熵值，然后把當前時刻的熵值和前一時刻的熵值進行對比，如果熵值的差超過一定范圍則認為在該維度上出現了異常。首先給出熵異常檢測算法的相關概念。

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

對S的準確估算并不一定能夠獲得一個誤差足夠小的熵估計值，在實際的計算過程中，如果H值很小，S值趨向于它的最大值時，計算S值時一個很小的誤差可能導致H值出現無法接受的誤差，定義為通過計算獲得的熵估計值，即下面的定理保證通過對S的估計值來估算H值是合理的。

下面給出 Filter-ary-Sketch數據結構上基于熵的異常檢測算法：

算法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)

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

3 異常檢測流程

異常檢測的流程可分為3個部分：利用Filter-ary-Sketch數據結構進行數據記錄、異常檢測和惡意流量阻斷。

3.1 數據記錄

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

初始狀態時，Filter-ary-Sketch數據結構中每個散列桶初始值為0，每個散列桶對應的Bloom Filter每位都初始化為0。在每個時間周期內，用每個新到達的數據項更新Filter-ary-Sketch數據結構，具體過程如下。

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

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

3) 用該數據項的SIPi更新對應散列函數桶位置的Bloom Filter。

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

5) 把該Filter-ary-Sketch標識為當前記錄Sketch，另一Filter-ary-Sketch標識為最近記錄Sketch，轉異常檢測流程。

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

3.2 異常檢測流程

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

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

4) 取Cij對應的Bloom Filter，轉惡意流量阻斷流程。

3.3 惡意流量阻斷

在檢測到異常后，首先需要根據Filter-ary-Sketch數據結構內每個散列桶位置當前時刻值和最近時刻值的差異定位異常點，利用異常點位置對應的Bloom Filter內存儲的源IP地址進行惡意流量阻斷。具體的流程如下。

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

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

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

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

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

4 實驗與結果分析

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

4.1 效率對比實驗

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

圖2 網絡流量

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

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

圖3 計算時間對比

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

圖4 存儲開銷對比

4.2 精度對比實驗

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

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

表1 Trace文件流量特征

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

圖5 熵值曲線

圖6 異常IP流量

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

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

5 結束語

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

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

[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] 嚴芬, 陳軼群, 黃皓. 使用補償非參數CUSUM方法檢測DDoS攻擊[J]. 通信學報. 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] 羅娜, 李愛平, 吳泉源. 基于概要數據結構可溯源的異常檢測方法[J]. 軟件學報,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/.