ODA-IPNMF：一種在線全網絡流量異常檢測方法

柏 駿，夏靖波1，吳吉祥3，鹿傳國4

（1.空軍工程大學信息與導航學院，710077西安；2.95852部隊，572600海南東方；3.空軍大連通信士官學校，116600遼寧大連；4.95806部隊，100076北京）

ODA-IPNMF：一種在線全網絡流量異常檢測方法

柏 駿1，2，夏靖波1，吳吉祥3，鹿傳國4

（1.空軍工程大學信息與導航學院，710077西安；2.95852部隊，572600海南東方；3.空軍大連通信士官學校，116600遼寧大連；4.95806部隊，100076北京）

為實時、高效地檢測網絡流量異常，提出一種基于增量投影非負矩陣分解（IPNMF）的全網絡流量異常檢測方法（ODA-IPNMF）.提出一種增量投影非負矩陣算法，該算法不僅具有與PCA相同的表達形式，還能以增量的方式構建正常子空間和異常子空間，進而利用Shewhart控制圖實現全網絡流量異常的在線檢測.理論分析表明，該方法計算開銷遠小于NMF-NAD，具有更高的實用價值；模擬網絡數據以及實測網絡數據實驗表明，基于NMF異常檢測方法（NMF-NAD和ODAIPNMF）的檢測性能優于PCA方法；本文所提ODA-IPNMF與NMF-NAD網絡異常檢測效果相當，且可在線檢測網絡異常.

網絡異常檢測；流量矩陣；增量投影非負矩陣分解；在線檢測

隨著互聯網技術的迅猛發展，各類網絡異常活動如影隨形，網絡安全成為各方關注的焦點.異常檢測對于維護網絡安全、高效、可靠運行具有重要意義，是網絡安全領域的研究熱點［1-9］.

從全網的視角實時檢測網絡異常對于維護網絡穩定運行極為重要.文獻［3-4］提出基于流量矩陣子空間映射的全網絡異常檢測方法，該方法利用流量矩陣的空間相關性和時間相關性，從全網絡的視角檢測異常行為.文獻［5］指出基于PCA異常檢測方法對于主成分數量、檢測閾值等參數的選取非常敏感，而且連續的或者足夠大的網絡異常可能毒害正常子空間，并致使誤報率增加.文獻［6］利用奇異值分解（SVD）實現PCA的在線更新，進而實現全網絡的多元在線異常檢測.文獻［7］先利用小波去除數據中的噪聲，以減輕大的異常對于正常子空間的毒害，再使用PCA將流量矩陣映射到正常和異常子空間.文獻［8］亦做了類似的工作，將PCA和小波分析結合起來以提高流量異常檢測的精度.針對基于PCA的異常檢測方法難以解釋矩陣分解過程中出現的負值以及無法連續檢測異常的問題，文獻［9］提出利用非負矩陣分解檢測網絡異常，將原始流量矩陣與重構矩陣的差視為噪聲和異常，并通過Shewhart控制圖捕捉網絡異常，但該文獻并未對方法的合理性做出解釋，并且只能離線檢測網絡異常.

本文采用與PCA表達形式相同的投影非負矩陣分解算法（PNMF）作為檢測工具，提出了一種基于IPNMF的在線全網絡流量異常檢測方法（ODA-IPNMF）.將PNMF引入到基于流量矩陣的全網絡異常檢測中，并提出了一種增量投影矩陣分解算法——IPNMF；提出一種基于IPNMF的全網絡異常檢測方法，該方法以增量的方式對流量矩陣進行投影，構建正常子空間和異常子空間，可實時檢測網絡異常.

1 流量矩陣及PNMF算法

1.1 流量矩陣

流量矩陣TM（traffic matrix）是全網絡流量概覽，可全面、準確地描述網絡流量特征（流量大小、字節數、IP地址、端口等）的分布情況［10］.矩陣中的元素代表網絡中某一時刻（時間間隔）源節點與目的節點之間（OD對）的流量，可表示為一個d×p的矩陣X.其中，d為測量的周期數；p為n個網絡節點的OD對數，有p=n×n（或p=n× （n-1））.Xij為在第i個測量周期時第j個OD對的流量特征數據的測量值.根據選擇的網絡節點類型不同，可以分為鏈路級、路由級和PoP（point of presence）級流量矩陣.本文以PoP級流量矩陣作為研究對象.

1.2 PNMF算法

為應對高維數據“維度詛咒”問題，多采用矩陣分解來分析實際問題中的高維數據，如PCA、ICA、SVD、VQ等.然而上述方法分解的矩陣元素可能出現負數往往無法得到合理的解釋，因此，文獻［11］的非負矩陣分解應運而生.

對任意給定的非負矩陣X∈Rd×p+進行分解，試圖尋找最優解W和H使得

并通過迭代使得二者之間的近似誤差最小，用歐式距離衡量，有

PNMF［12］是一個改進的NMF算法，它試圖尋找一個非負的投影矩陣使得

式中的投影矩陣可進一步表示為

PNMF算法為求得最佳W，定義了如下優化問題:

對X求偏導，有

令

帶入上式，得到

進而得到更新方程:

較其他NMF算法，PNMF更適用于流量矩陣的網絡異常在線檢測.首先，PNMF與與基于PCA的異常檢測算法［3］具有相同的表達形式，可將流量矩陣向正常子空間和異常子空間上進行投影；其次，通過PNMF不僅可得到非負的稀疏矩陣，而且只需考慮更少的參數，就能產生更稀疏的矩陣，便于在線流量異常檢測；而且，PNMF在不斷迭代的過程中，可將正常與異常子空間的差異最大化，具備更佳的檢測效果.

2 ODA-IPNMF算法

采用子空間分析方法［3］檢測流量異常的前提是分離正常子空間和異常子空間，并對異常子空間進行分析以檢測網絡是否出現異常.上述PNMF算法只能對流量矩陣進行離線的批量處理，無法以增量的方式分離正常、異常子空間.因此，為克服PNMF只能進行離線數據處理的不足，提出一種增量投影非負矩陣分解算法（IPNMF）.

增量計算是一個不斷利用前面處理結果進行后續增量運算的過程.那么增量過程的關鍵就是如何利用已得到的計算結果.文獻［13］指出，增量非負矩陣分解過程中，基向量代表了之前數據的所有信息.基于此，將新增樣本數據D（t）添加到上一時刻的基向量W（t-1）中作為IPNMF算法的新的輸入向量X（t），記為X（t）=［W（t-1），D（t）］；然后將X（t）代入式（9）和式（10）中，不斷迭代直至收斂.在迭代過程中，主要的計算是式（9）中的矩陣乘法，為減少運算量，令

下面給出IPNMF算法的偽代碼:

基于以上分析，本文采用子空間分析方法，利用IPNMF將流量矩陣映射到正常子空間和異常子空間中，然后利用Shewhart控制圖捕捉異常子空間中的流量異常.該方法步驟如下:

3）異常流量捕獲.為了對殘余矩陣進行分析，本文引入殘余流量向量中所有元素的平方和（SSE）來衡量殘余向量的大小，并利用Shewhart控制圖來捕捉異常子空間中的流量異常.

利用上述的IPNMF增量算法思想實現全網絡流量異常的在線檢測——ODA-IPNMF，算法描述如下:

ODA-IPNMF方法的計算開銷主要在于增量數據D（t）的IPNMF分解和基于Shewhart的異常檢測.增量數據D（t）的IPNMF的時間復雜性為O（pr（r+s）k），其中p為OD對數，r是基矩陣維數，s為增量數據維數，k為迭代次數.而基于Shewhart的異常檢測的時間復雜性僅與增量數據維數s相關，為O（s），遠小于前者.因此，ODAIPNMF方法的時間復雜性為O（pr（r+s）k），相比于文獻［9］的O（pdrk），其中（r+s）?d，那么所提方法的運算效率有明顯提高.

3 實驗分析及評價

為對所提ODA-IPNMF算法性能進行分析、評價，本文基于Matlab實驗平臺，以檢測率和誤檢率作為評價指標，采用模擬實驗分析與因特網實測數據分析相結合的方式來比較異常檢測算法的檢測性能.

3.1 模擬數據實驗及其分析

3.1.1 模擬數據生成

首先產生近似周期性的正常成分、高斯噪聲成分和異常成分［14］，再按適當的比例人工合成網絡流量.具體步驟:1）通過將3種不同周期、隨機初始相位的正弦波疊加來模擬OD流，進而構成基準流量矩陣，圖1（a）；2）在OD流上加入零均值的高斯噪聲，得到不含異常的基準流量矩陣，見圖1（b）；3）以一定規則注入各類典型異常，見圖1（c）.采用間隔為5 min，共模擬一個星期的網絡流量，最終生成包含2 016個測量周期、121條網絡流的流量矩陣X.

圖1 模擬網絡流量數據合成

本文所提方法是從流量大小的角度去檢測異常，故在此考慮4種最常見的、引起流量劇烈變化的典型異常:阿爾法（alpha）異常、（分布式）拒絕服務攻擊（DoS，DDoS）、突發流（flash crowd）、入口/出口移動（ingress/egress shift）異常，并利用持續時間、流量變化大小、源-目的數以及形狀函數等4個參數來描述.上述異常的具體行為特征參見文獻［6］.

網絡異常注入過程如下:從第250個測量周期到第500個測量周期，每50個測量周期注入一次持續30 min（6個測量周期）阿爾法攻擊；從第750個測量周期到第1 000個測量周期，每50個測量周期注入一次持續時間為30 min（6個測量周期）DDoS攻擊；從第1 250測量周期到1 500測量周期，每50個測量周期注入一次突發流；在第1 900測量周期到1 950測量周期內注入一次入口/出口移動異常.

3.1.2 IPNMF算法性能分析及參數選取

為比較本文所提IPNMF算法與PNMF算法的收斂性以及矩陣還原性，在固定基矩陣維數r= 3的條件下，利用上述兩種算法對模擬實驗數據重復10次，得到的實驗結果見表1.

表1 IPNMF算法與PNMF算法性能比較結果

從表1中看出IPNMF算法對收斂性的明顯改善，矩陣分解過程中的迭代次數以及收斂時間都大幅減少.一方面原因是IPNMF算法的時間復雜性低于PNMF算法；另一方面則是IPNMF算法所需存儲的最大矩陣規模為m×（r+s），遠小于后者的m×（n+s），節省了大量存儲資源.此外，兩種投影非負矩陣分解算法的d值相差無幾，因此二者具有相當的矩陣還原性.

非負矩陣分解算法的一個非常重要的參數是基矩陣維數r.為確定基矩陣維數，本文設置最大迭代次數為500，另r從2遞增至20，以尋求最優的矩陣還原性.實驗重復10次，實驗結果見圖2.

圖2 基矩陣維數r與算法性能的關系

3.1.3 ODA-IPNMF算法性能分析與比較

將本文所提ODA-IPNMF與MOADA-SVD方法［6］和NMF-NAD方法［9］進行比較.MOADA-SVD是基于奇異值分解的在線網絡異常檢測方法，采用Q統計量的方法檢測異常；NMF-NAD是基于NMF的離線網絡異常檢測方法，采用Shewhart控制圖的方法進行異常檢測.上述3種算法異常時刻凸顯的結果見圖3.

圖3 3種方法的異常凸顯對比

由圖3可發現，相較于MOADA-SVD方法，基于NMF的異常檢測方法（NMF-NAD和ODAIPNMF）對網絡異常更為敏感，其異常/正常流量的幅值比明顯大于前者，更易被檢測，且誤檢率更低.究其原因，MOADA-SVD仍是基于PCA算法，它力求尋找均方誤差最小意義下的最優線性映射投影，卻忽略了正常流量與異常流量的屬性差異，導致可能包含的重要信息丟失；而NMF在不斷迭代的過程中將這種差異最大化，因而具有更佳的異常檢測效果.

在圖4中，利用Shewhart對ODA-IPNMF與NMF-NAD的檢測結果進行比較，其中R為流量變化范圍，在［LCL，UCL］區間內即為正常.結合圖3（b）和圖3（c），可以看出，上述兩種方法對全網絡異常的凸顯幾乎是一樣的，唯一不同在于第1 900到1 950測量周期的入口/出口移動異常檢測結果，NMF-NAD方法表現出連續異常，而本文算法表現為突發異常.究其原因，本文方法采用增量分解算法，以6個測量周期進行矩陣分解，殘余矩陣中的連續流量信息容易被忽略，導致連續異常未能被充分檢測.此外，ODA-IPNMF算法以增量的方式實時檢測網絡異常，每次需處理的數據僅與時間間隔t有關，數據量遠遠小于一次性分解全流量矩陣，所占用的存儲空間以及計算資源要遠遠小于NMF-NAD算法，因而實際應用價值更高.

重復上述實驗過程10次，3種算法的檢測結果見表2.通過比較發現，NMF-NAD和 ODAIPNMF方法無論是檢測率還是誤檢率都相差無幾，且明顯優于 MOADA-SVD方法，而后者與文獻［3］的結果吻合.實驗表明，NMF具備更優異的異常檢測能力.

圖4 基于Shewchart的異常檢測結果

表2 異常檢測結果 %

3.2 實測數據實驗及其分析

3.2.1 實測數據集Abilene

為驗證、評價上述方法在實際網絡中異常檢測的效果及性能，本文采用來自于Abilene網絡的流量矩陣數據，其描述如表3所示.上述數據集自身便含有網絡異常，發現并確定異常是檢測的關鍵.

表3 Abilene流量矩陣

3.2.2 ODA-IPNMF算法實驗分析

按照上述實驗流程對Abilene流量矩陣數據進行異常檢測.其中Dataset1的3種方法的異常凸顯結果見圖5.

圖5 Dataset1數據集異常凸顯結果

實測網絡數據的異常檢測結果很好地驗證了模擬數據的實驗結論.MOADA-SVD方法僅發現了3處網絡異常，而其他兩種方法則發現了包括上述異常在內的5至6處異常，表明基于NMF的異常檢測方法（NMF-NAD和ODA-IPNMF）在異常檢測性能上優于基于PCA的檢測方法；本文提出的基于增量NMF的在線異常檢測算法ODA-IPNMF與NMF-NAD相比，在異常檢測性能上是相當的，但對于不同的異常表現出一些差異.

4 結 語

實驗與分析表明基于NMF的異常子空間投影方法較基于PCA的方法更利于網絡流量矩陣異常檢測.然而現有基于NMF的異常檢測方法只能處理離線數據，無法對網絡流量進行在線檢測.針對這一不足，本文給出了一種增量非負矩陣分解算法，并將其應用于網絡異常檢測中，并利用Shewart控制圖分析殘余流量，提出了一種基于IPNMF的在線全網絡流量異常檢測方法.該方法以增量的方式實時檢測網絡異常，所占用的存儲空間以及計算資源要遠遠小于NMF-NAD算法.通過模擬數據以及實測網絡數據實驗表明本文所提方法具備良好的全網絡異常流量檢測效果.

［1］BHUYAN M H，BHATTACHARYYA D K，KALITA J K.Network anomaly detection:methods，systems and tools［J］.Communications Surveys&Tutorials，IEEE，2014，16（1）:303-336.

［2］HUANG S Y，HUANG Y N.Network traffic anomaly detection based on growing hierarchical SOM［C］//2013 43rd Annual IEEE/IFIP International Conference on Dependable Systems and Networks（DSN）.Budapest: ［s.n.］，2013:1-2.

［3］LAKHINA A，CROVELLA M，DIOT C.Diagnosing network-wide traffic anomalies［C］//ACM SIGCOMM Computer Communication Review，［S.l.］:ACM，2004，34（4）:219-230.

［4］LAKHINA A，CROVELLA M，DIOT C.Mining anomalies using traffic feature distributions［C］//ACM SIGCOMM Computer Communication Review，［S.l.］: ACM，2005，35（4）:217-228.

［5］RINGBERG H，SOULE A，REXFORD J，et al.Sensitivity of PCA for traffic anomaly detection［C］// ACM SIGMETRICS Performance Evaluation Review，［S.l.］:ACM，2007，35（1）:109-120.

［6］錢葉魁，陳鳴.基于奇異值分解更新的多元在線異常檢測方法［J］.電子與信息學報，2010，32（10）: 2404-2409.

［7］錢葉魁，陳鳴，葉立新，等.基于多尺度主成分分析的全網絡異常檢測方法［J］.軟件學報，2012，23 （2）:361-377.

［8］NOVAKOV S，LUNG C H，LAMBADARIS I，et al.Studies in applying PCA and wavelet algorithms for network traffic anomaly detection ［C］//High Performance Switching and Routing（HPSR），2013 IEEE 14th International Conference on，［S.l.］:IEEE，2013:185-190.

［9］魏祥麟，陳鳴，張國敏.NMF-NAD:基于NMF的全網絡流量異常檢測方法［J］.通信學報，2012，33 （4）:54-61.

［10］VARDI Y M.Network tomography:estimating sourcedestination traffic intensities from link data［J］.Journal of theAmerican StatisticalAssociation， 1996， 91 （433）:365-377.

［11］LEE D D，SEUNG H S.Learning the parts of objects by non-negative matrix factorization［J］.Nature，1999，401:788-791.

［12］YANG Z，OJA E.Linear and nonlinear projective nonnegative matrix factorization［J］.IEEE Transaction on Neural Networks，2010，21（5）:734-749.

［13］DONOHO D，STODEEN V.When does non-negative matrix factorization give a correct decomposition into parts？ ［C］//Advances in Neural Information Processing Systems，2004:1141-1148.

［14］LAKHINA A，PAPAGIANNAKI K，CROVELLA M，et al.Structural analysis of network traffic flows［C］// SIGMETRICS，New York，NY，USA:［s.n.］，2004: 156-167.

（編輯 苗秀芝）

ODA-IPNMF:An Online Anomaly Detection Algorithm

BAI Jun1，2，XIA Jingbo1，WU Jixiang3，LU Chuanguo4
（1.Institute of Information and Navigation，AFEU，710077 Xi'an，Shanxi，China；2.Unit 95852，572600，Dongfang，Hainan，China；3.Air Force Dalian Communications Noncommissioned Officers School，116600，Dalian，Liaoning，China；4.Unit 95806，100076 Beijing，China）

An online anomaly detection algorithm based on incremental projective non-negative matrix factorization is proposed to detect the network anomaly real-timely and efficiently.Firstly，an incremental projective non-negative matrix factorization is given，which has the same expression with PCA，and is able to construct normal and abnormal subspace to detect network-wide anomalies online by Shewhart control chart.Theoretic analysis indicates that，the proposed algorithm computation is far smaller than NMF-NAD.In addition，traffic matrix datasets analyzing for internet and simulation results show that the network anomalies detection algorithms based on NMF（such as NMF-NAD and ODA-IPNMF）performs better than that based on PCA，and the proposed ODA-IPNMF has comparable network anomaly detection by NMF-NAD，which the ability to detect the network anomaly online.

network anomalies detection； traffic matrix； incrementalprojective non-negative matrix factorization；online detection

TP393

A

0367-6234（2015）05-0104-06

10.11918/j.issn.0367-6234.2015.05.018

2014-06-19.

國家自然科學基金（61272486）；陜西省科技計劃自然基金重點項目（2012JZ8005）.

柏 駿（1985—），男，博士研究生；

夏靖波（1963—），男，教授，博士生導師.

柏 駿，peking1985-2005@163.com.