基于ME-PGNMF的異常流量檢測方法

,,

(火箭軍工程大學 信息工程系,西安 710025)

0 概述

隨著網絡技術的發展和普及,網絡流量的規模越來越大,類型也越來越多,網絡安全問題日益突出。但不論何種網絡異常都會對網絡流量產生影響,因此,網絡流量異常檢測的研究越來越受到重視。網絡流量異常檢測是指通過對網絡流量歷史活動的觀測建立網絡流量的正常模式,和當前網絡流量活動比較發現異常。其優點是可以發現新的異常,但也存在不少問題。

當前骨干網的網絡活動特點是流量大、流速快、數據維數高,要進行數據檢測,數據的降維處理成為一個必要的過程。文獻[1]采用基于主成分分析(Principal Component Analysis,PCA)的子空間方法,利用PCA對數據降維的能力將流量矩陣分離為正常子空間和異常子空間,通過設置閾值,對大流量的異常取得較好的檢測效果。文獻[2]同時考慮流量的時間和空間相關性,綜合利用小波變換具有的多尺度建模能力和PCA具有的降維能力對正常流量進行建模,實現異常檢測。但PCA方法仍存在較多問題:PCA追求的是全局最優解,導致對局部特征提取不充分,影響檢測精度;系數向量中存在負值,但流量不可能為負,可解釋性差;PCA方法的效果受主成分的選擇和閾值設定的影響很大。鑒于以上問題,文獻[3]將非負矩陣分解(Non-negative Matrix Factorization,NMF) 方法用于異常流量檢測。主要特點是采用非負子空間方法提取流量矩陣中的主要時變模式,構成正常子空間,得到重構矩陣和殘余矩陣,然后應用Q圖進行異常點檢測。該方法有更強的特征提取能力,由于其非負性,可解釋性也更強,實驗表明比PCA方法在檢測精度方面有明顯提高。

傳統的基于統計的網絡流量異常檢測方法多是對流量特性進行分析[4]。文獻[5]總結了基于熵的異常流量檢測的優點:在數據流上有高效的熵值計算算法,且有足夠的精度保證;基于熵的檢測方法提供了一種更細粒度的信息,能夠檢測出更加隱蔽的異常類型;采樣對基于熵的檢測方法精度影響并不明顯;正常情況下熵值相對流量幅值更穩定。

文獻[6]用增量投影非負矩陣分解對NMF方法進行改進,提高了NMF的效率。文獻[7]雖利用了流量的熵值特征,但僅利用流量幅值的熵,流量數據利用不充分。為此,本文提出一種將特征熵和NMF相結合的方法對此類異常流量檢測方法進行改進。

1 多維熵矩陣和PGNMF算法

1.1 多維熵矩陣

信息熵是信息論中用于度量信息量的一個概念,信息熵標志著所含信息量的多少,是對系統不確定性的描述。用信息熵來描述網絡流量的特征,對流量數據預處理,不僅增強了對網絡流量異常的檢測能力,而且方便了流量異常的分類。

基于熵的異常檢測系統的主要思想是:一旦有異常流量發生,總體流量的熵值應該會隨之發生變化,通過熵值的變化能夠檢測出該異常。文獻[8]把流量聚集成網絡流,針對每個流在源/目IP,源/目端口維度上分別計算熵值,然后采用PCA方法進行異常檢測;文獻[9]提出在高速IP網絡上利用熵值來檢測蠕蟲爆發和流量異常,均取得較好的效果。文獻[10]基于最大熵原理,通過比較當前分布和基準分布的差異來進行異常檢測。文獻[11]在多個不同維度上采用熵度量流量數據的分布特征,在每個時間窗口上把不同維度熵值序列排列成檢測向量,提出多窗口關聯檢測算法,既降低了計算復雜度,也提高了檢測效率。以上方法從不同層面都驗證了熵特征在異常流量檢測方面的良好性能。

把采集到的Netflow流量數據當作離散信息源,把數據中的各個屬性看作是一組隨機事件,就可以對它的信息熵進行分析。假設某一時段內目的IP的集合用X表示,i表示有i個不同的目的IP,ni表示第i個目的IP出現的次數:X={ni,i=1,2,…,N}。那么該時段內目的IP(X)的信息熵定義如式(1)所示,本文使用信息熵的指標有源/目的IP、源/目的端口,如下:

(1)

不同指標熵的計算方法可參考式(1)。表1反映的是不同異常對流量各屬性熵值的影響。

為充分利用流量的時間和空間相關性,在多維特征熵的基礎上構建多維熵矩陣。傳統流量矩陣描述一個網絡中所有源節點和目的節點(Origin-Destination, OD)對之間的流量情況,主要反映了目標網絡各OD對之間流量分布情況。主要包括鏈路級、路由級和PoP(Point of Presence)級流量矩陣。單一時刻的流量矩陣表示為一個m行的列向量:(x1,x2,…,xn)T,其中。m表示OD對的數量。不同的列代表不同時刻。則在有m個OD對的網絡中所有n個時刻的流量矩陣如式(2)所示,矩陣Xmn表示第m個OD對在n時刻的流量情況,多維熵矩陣就是將流量指標修改為源/目的IP熵,源/目的端口熵等指標得到四維熵矩陣。

(2)

1.2 PGNMF算法

NMF[12]起源于主成分分析,1999年Lee和Seung在Nature上發表了NMF算法,該算法是在矩陣中所有元素均為非負的條件下對其實現非負分解.具有可解釋性、占用存儲空間少等優點。NMF可以定義為給定一個n×m階非負矩陣Vg和一個正整數r,將矩陣Vg分解為n×r階的矩陣Wg和r×m階的矩陣Hg的乘積,如式(3)所示為得到近似的分解結果,需要定義一個目標函數:

Vm×n≈Wm×r×Hr×n

(3)

(4)

來量化矩陣Vg與矩陣Wg×Hg的逼近程度,如式(4)所示。式(4)需滿足矩陣Wia≥0,Hbj≥0,?i,a,b,j,是一個帶約束的非線性規劃問題。利用迭代的方法求解矩陣Wg和Hg。文獻[3]給出了帶約束條件下用拉格朗日算子解得的矩陣Wg和Hg的更新方程,如下:

(5)

NMF算法可描述如下:

1)初始化矩陣Wia≥0,Hbj≥0,?i,a,b,j。

2)設置基矩陣維數r和最大迭代次數k,更新矩陣Wg和Hg,更新規則為式(5)。

3)循環執行式(5),至算法收斂。

但NMF算法復雜度高,不利于異常流量檢測對實時性的要求,因此,采用投影梯度(Projected Gradient, PG)優化方法降低NMF迭代的復雜度。PGNMF方法具物理意義明確、稀疏性好、以及耗時少等特點,但梯度投影法使用另外的迭代規則。文獻[9]提出的一種梯度投影法,使迭代的復雜度大為降低且更新得到的解收斂。算法基本思想如下:

將式(4)改寫為如下形式:

(6)

(7)

(8)

1)初始化矩陣Wia≥0,Hbj≥0,?i,a,b,j。

2)設置基矩陣維數r和最大迭代次數k,通過迭代條件式(8),利用梯度投影方法求解式(6)、式(7),得到矩陣Wg和Hg的更新關系。

3)重復步驟(2),至算法收斂,得到矩陣Wg和Hg。

2 基于ME-PGNMF異常流量檢測模型

基于ME-PGNMF的異常流量檢測方法主要分為構建多維熵矩陣、獲取殘差矩陣、異常點檢測。如圖1所示為異常流量檢測的基本流程。

圖1 異常流量檢測基本流程

2.1 多維熵矩陣構建

若矩陣Xm×n表示待檢測的目標網絡流量矩陣,則m表示目標網絡的OD對的數量,n表示檢測時間段內的采樣周期數。根據信息熵定義,求出網絡流量在n個周期內源/目的IP、源/目的端口4個屬性的熵值序列,并標準化處理,得到4個大小為m×n的標準化熵矩陣。將4個維度矩陣依次按行相接得到一個4m×n的多維熵矩陣,用矩陣V4m×n表示。矩陣V4m×n的列向量表示某一檢測周期內不同OD對4種屬性熵值的變化,行向量表示某一OD對不同周期某一屬性熵值變化。

2.2 殘差矩陣獲取

若將多維熵矩陣中第i個位置的向量看做是d維空間的點,每一個點的狀態特征用多維熵特征表示。多維熵矩陣可以用r維的子空間表示,滿足條件的r維子空間為多維熵矩陣的特征子空間,而r維子空間可以通過PGNMF算法進行構建。選取子空間維數r和迭代次數k,通過構建r維特征子空間,得到殘差距陣。殘差矩陣的獲取分2個步驟:提取正常成分和獲取殘余成分。

首先提取正常成分,對多維熵矩陣V進行PGNMF算法分解之后可以獲得矩陣W和矩陣H,其中基矩陣Wg=(w1,w2,…,wr)的每一列代表的是r維子空間的基向量,系數矩陣Hg=(h1,h2,…,hn)中的每一列表示的是r維子空間的系數向量,而每一個基向量捕獲的是目標網絡各OD對的一種狀態模式。矩陣Vg≈Wg×Hg代表的是目標網絡的正常狀態成分。

2.3 異常點檢測

得到殘差矩陣后,如果某周期內發生了異常,其對應的殘差向量也會發生明顯變化。本文引入Q統計量來監測殘差向量的變化,Q統計量的時序圖亦稱平方預測誤差(Squared Prediction Error,SPE)圖[14],是多元統計過程控制圖的一種,主要監測輸入多變量的數據結構是否變化,殘差向量中包含源/目的IP、源/目的端口熵4個變量,每個殘差向量代表一個采樣點。

Q統計量在i時刻的值Qi是個標量,用殘余向量中所有元素的平方和(SSE)來衡量,當檢驗水平為α時,控制限Qα可按式(9)計算:

(9)

其中,λj為多維熵矩陣V第j個特征值,cα是正態分布中1-α分位數,α通常取0.001。若Qi

分析以上3個步驟可以發現基于ME-PGNMF的異常流量檢測方法有以下3個關鍵問題:1)PGNMF算法的效果受初始參數r和k影響較大,如何選取合理的參數保證檢測效果。2)r維特征子空間是否能還原出流量的正常狀態模式,從而保證得到的殘余矩陣包含了異常狀態模式。3)用Q統計量對殘余向量進行多元統計過程控制是否能檢測出異常。對于問題1)可通過矩陣還原性來選取參數,問題2)一方面取決于矩陣還原性,同時取決于檢測效果,而問題3主要取決于檢測效果。綜上,在進行實驗設計和分析時要從以上3個問題進行綜合考慮,不僅要分析最終的檢測效果,還要關注過程中的矩陣還原性指標。

3 實測數據實驗及結果分析

3.1 實驗數據與方法

為了驗證分析ME-PGNMF算法在異常流量檢測方面的有效性,實驗實測數據來自Abilene骨干網在2009年3月1日—2009年3月7日一周所采集的流量矩陣數據。該網絡是美國的IP骨干網絡,每個節點對應一個城市,由12個節點組成,共有12×12=144條OD流,所有節點通過配置NetFlow來收集真實OD流。其中,采集間隔為5 min,這樣一周所采集的次數為7×24×60/5=2 016,而OD流的數目為144個,因此,該OD流矩陣為一個144×2016的矩陣。在OD流矩陣的基礎上,計算源/目的IP、源/目的端口4個同樣大小的熵矩陣,標準化處理后,按行相接得到576×2 016的多維熵矩陣。表2所示為本文實驗的具體數據集形式。

但Abilene數據集中并無明顯異常,因此采用人為注入異常流量的方法進行實驗。為方便和PCA、NMF等方法對比,采用和文獻[3]相似的異常注入方式。在實驗中,采樣點之間間隔為5 min,異常注入過程如下:從第300個采樣點到第800個采樣點期間,每隔50個采樣點輪流依次注入一次低速DDOS攻擊和一次DDOS攻擊,并且2種攻擊都持續30 min(持續6個采樣點);從第1 000個～第1 500個采樣點里,每隔50個采樣點注入一次端口掃描,攻擊持續時間為30 min(持續6個采樣點);從第1 700個～第1 900個采樣點期間,持續注入蠕蟲攻擊,包括個感染到爆發的完整過程(持續200個采樣點)。

3.2 參數分析與選擇

非負矩陣分解算法的一個非常重要的參數是基矩陣維數r的選擇,參數r主要影響分解后的矩陣對原矩陣的還原性,是影響最終檢測結果的重要因素。且參數r的選擇受數據集特性影響較大。迭代次數k雖然在足夠大的情況下能確保算法收斂,但k值過大會使算法的復雜性增大。鑒于以上情況以及數據集的相似性,對基于流量矩陣的NMF方法,參數選擇參考文獻[3],對基于流量熵矩陣的PGNMF方法,參數選擇參考文獻[15],本文重點分析基于多維熵矩陣的PGNMF方法的參數選擇。

矩陣的還原性通常用式(10)來衡量:

(10)

為確定基矩陣維數r和合理的迭代次數k,為確保d收斂,首先設置最大的迭代次數k為500,r從2遞增至20,尋求最優矩陣還原性的r。。實驗對象為標準化后的576×2 016的多維熵矩陣,實驗結果如圖2所示。

圖2 矩陣還原性d與維數r的關系

從圖2和圖3可以看出,基矩陣維數r設為12時,矩陣還原性d已基本穩定即d收斂,且此時收斂所需時間t還沒有明顯增加。結合圖4,d收斂時所需的迭代次數k均未超過200,因此,最大迭代次數500未對實驗造成影響。綜合以上結果選取參數r為12,k為200。

圖3 d收斂時,收斂時間t與維數r的關系

圖4 d收斂時,不同維數r與迭代次數k的關系

3.3 實驗結果及分析

對基于NMF的檢測算法選擇合適的基矩陣維數r和迭代次數k后,按表2算法與實驗數據形式得到圖3和表3、表4的實驗結果。圖3中直線代表控制限Qα,α取0.001,圓圈代表殘余向量的Qi。表3檢測率指標參考文獻[16],為檢測到的異常點與注入異常點的比,表4中誤報率為注入異常時段內正常采樣點報為異常的次數與正常采樣點的比。

表3 不同方法對注入異常的檢測率 %

表4 不同方法對注入異常的誤報率 %

通過分析表3和圖5～圖8可以發現對于低速DDOS攻擊,PCA方法檢測效果最差,檢測率接近于0,NMF和PGNMF方法檢測效果也不明顯檢測率不足20%,分析原因主要是此類攻擊并未明顯引起流量變化,而這3種方法都是以流量為基礎。對于端口掃描和普通DDOS攻擊,幾種方法都能不同程度的檢測出來,其中,以ME-PGNMF方法效果最好,原因是該方法既有NMF方法局部特征提取能力強的優勢,又以多維熵為基礎,對異常流量的分辨能力有很大提高。最后,比較對蠕蟲攻擊的檢測可以發現,PCA方法對攻擊最不敏感,在第1 700個采樣點攻擊已出現,圖5直到第1 780個采樣點左右才有檢測到的跡象,圖6和圖7中雖然在第1 700采樣點已能檢測到異常但并不穩定,依然有很多漏報點發生,直至第1 750采樣點才穩定報出異常,只有ME-PGNMF方法最快對蠕蟲攻擊做出反應,且漏報點很少,分析原因,與蠕蟲攻擊在起始階段對流量變化影響不大有關。

圖5 PCA方法異常流量檢測效果

圖6 NMF方法異常流量檢測效果

圖7 PGNMF方法異常流量檢測效果

圖8 ME-PGNMF方法異常流量檢測效果

為準確評價幾種方法對注入異常的檢測效果,分析表4的誤報率可以看出,基于流量的方法對低速DDOS攻擊不敏感,檢測率和誤報率都很低,對其他攻擊流量,ME-PGNMF方法檢測率有明顯提高,誤報率也沒有明顯上升。綜合考慮3種攻擊,ME-PGMF方法檢測率有明顯提高,同時誤報率并無明顯提升。對于蠕蟲攻擊,由于每一個采樣點都注入異常,因此不存在把正常采樣點報為異常點,即誤報問題。

3.4 參數選擇對實驗結果的影響

在3.2節中分析了ME-PGNMF方法中參數選擇對算法的影響,為直觀體現參數r和k對實驗結果的影響,通過設計不同的參數得到圖9～圖10所示的實驗結果。可以看出,實驗結果與參數分析基本一致。r為12,k為120(小于實驗預設值200)都達到了實驗的最佳效果,如果參數變大雖能達到檢測效果,但運算的時間復雜度就會增加。

圖9 k為200時,r與檢測率的關系

圖10 r為12時,k與檢測率的關系

4 結束語

利用熵特征對異常流量的敏感性和PGNMF算法局部特征提取能力強、收斂速度快的特性,本文提出基于多維熵和PGNMF的網絡異常流量檢測方法。實驗結果表明,與基于流量的檢測方法相比,該方法對低流量異常更敏感,有利于發現隱蔽的流低速攻擊,可以在蠕蟲爆發的早期階段及時發現,提高了檢測率。下一步將改進數據輸入形式,通過增量或其他方法,達到在線檢測的目的。

[1] LAKHINA A,CROVELLA M,DIOT C.Mining Anomalies Using Traffic Feature Distributions[J].Conference on Applications,2005,35(4):217-228.

[2] 錢葉魁,陳 鳴,葉立新,等.基于多尺度主成份的全網絡異常檢測方法[J].軟件學報,2012,23(2):361-377.

[3] 魏祥麟,陳 鳴,張國敏.NMF-NAD:基于NMF的全網絡流量異常檢測方法[J].通信學報,2012,33(4):54-61.

[4] 王 浩.針對TCP的低速DDoS解析及防御策略[J].計算機工程,2009,35(13):122-124.

[5] 鄭黎明.大規模通信網絡流量異常檢測與優化[D].長沙:國防科學技術大學,2012.

[6] 柏 駿,夏靖波,吳吉祥,等.ODA-IPNMF:一種在線全網絡流量異常檢測方法[J].哈爾濱工業大學學報,2015,47(5):104-109.

[7] 王曉鴿.基于PGM-NMF的網絡流量異常檢測研究[J].電子科技,2014,27(5):175-178.

[8] ANUKOOLL,MARK C,CHRISTOPHE D.Mining Anomalies Using Traffic Feature Distributions[C]//Proceedings of ACM SIUCOMM’05.New York,USA:ACM Press,2005:217-228.

[9] WAGNER A,PLANNER B.Entropy Based Worm and Anomaly Detection in Fast IP Networks[C]//Proceedings of the 14th IEEE International Workshops on Enabling Technologies:Infrastructure for Collaborative Enterprise.Washington D.C.,USA:IEEE Press,2005:172-177.

[10] YU Gu,ANDREW M,DON T.Detecting Anomalies in Network Traffic Using Maximum Entropy Estimation[C]//Proceedings of the 5th ACM SIUCOMM Conference on Internet Measurement.New York,USA:ACM Press,2005:345-350.

[11] 鄭黎明,鄒 鵬,韓偉紅,等.基于多維嫡值分類的骨干網流量異常檢測研究[J].計算機研究與發展,2012,49(9):1972-1981.

[12] LEE D,SEUNG H S.Learning the Parts of Objects by Non-negative Matrix Factorization[J].Nature,1999,401(6755):788-791.

[13] LINC J.Projected Gradient Methods for Non-negative Matrix Factorization[J].Neural Computation,2007,19(10):2756-2779.

[14] 王兆軍,鄒長亮,李忠華,等.統計質量控制圖理論與方法[M].北京:科學出版社,2013.

[15] 王曉鴿.基于流量矩陣的網絡入侵檢測研究[D].蘭州:蘭州交通大學,2014.

[16] 許 倩,程東年.基于層次聚類的網絡流量異常分類算法[J].計算機工程,2012,38(23):131-136.