NMF-NAD：基于NMF的全網絡流量異常檢測方法

魏祥麟，陳鳴，張國敏，黃建軍

(解放軍理工大學 指揮自動化學院，江蘇 南京210007)

1 引言

因特網已經成為人類生活的重要基礎設施，而因網絡設備誤配置、網絡故障、網絡安全事件（如分布式拒絕服務攻擊、蠕蟲傳播等）以及不尋常的用戶行為等導致的網絡異常事件時有發生，嚴重地干擾了網絡的正常運行。然而，在高速且持續變化的鏈路上準確地檢測出網絡流量異常，進而維護網絡的平穩運行，是因特網服務提供者(ISP)面臨的難題，也是網絡研究的熱點問題之一。

網絡流量異常是指網絡流量不尋常地和顯著地變化，并且可能涵蓋多條鏈路或者路徑[1]。檢測流量異常面臨的主要難點在于：第一，因特網流量的高波動和長相關性會使異常流量淹沒于正常的流量之中；第二，流量異常模式非常分散并且經常出現新型異常流量；第三，網絡流量巨大，分布式收集和處理很困難；第四，異常檢測的實用化要求做到早期檢測，對時效性要求較高。

很多異常行為(如 DDoS攻擊以及蠕蟲傳播等等)的全局特性使得傳統的單鏈路方法[2～4]失效，為此，Lakhina等人[1,5]首次采用基于主成分分析(PCA,principal component analysis)的子空間方法進行全網絡(network-wide)異常檢測，并取得了較好的效果。流量矩陣經過 PCA投影后，得到由一組正交基組成的正常子空間，可以看作是流量的某種固有變化模式，而每條鏈路或者路徑的流量則是這組基向量按照某個系數向量的疊加，這形成了 PCA異常檢測的基礎。然而，PCA存在以下問題。第一，系數向量中時常出現負值，而網絡流量不可能為負，使得這個分解過程的含義難以解釋。第二，PCA追求全局誤差最小的特性使其容易將連續異常學習為正常流量模式并投影到正常子空間，從而無法有效檢測連續突發異常的情況[6,7]。第三，PCA處理復雜度較高。為此，提出了基于非負矩陣分解(NMF, non-negative matrix factorization)的全網絡流量異常檢測方法 NMF-NAD (NMF based network wide traffic anomalies detection method)。NMF-NAD首先采用非負子空間方法提取流量矩陣中的主要時變模式，并用這些時變模式構成流量正常子空間，并以非負的系數向量對原始流量矩陣進行重構，得到重構矩陣和殘余矩陣，然后應用Shewhart控制圖基于殘余矩陣進行異常點檢測。本文首次將NMF應用于全網絡流量異常檢測領域，并取得了良好的檢測效果。

本文的內容安排如下：第2節綜述相關工作；第3節研究NMF-NAD算法；第4節通過實驗驗證了NMF-NAD算法的有效性；第5節是結束語。

2 相關工作

在全網絡異常檢測方面，主要采用多元統計分析的方法，這類方法可以檢測覆蓋多條鏈路的流量異常，成為近年來網絡研究的熱點。當前基于多元統計分析的方法主要包括基于 PCA的方法和核密度估計的方法。Lakhina等人證實了流量矩陣具有的低維特性以及不同流之間的空間相關性，首次提出了基于PCA的異常檢測算法[1,5]，將流量矩陣形成的原始空間分離為正常和異常子空間，并使用Q統計量計算閾值以檢測網絡異常；而且，實測數據分析表明該方法對于較大的流量異常具有較好的檢測性能。

但是，近年來的研究[8,9]，以及實際的實驗表明，PCA方法還存在2個主要的問題。第一，PCA方法的檢測效果對于其選擇的主成分數量以及檢測閾值非常敏感。一些基于PCA的方法需要人工設定選擇的主成分數量才可以取得較好的檢測效果，而不同的主成分選擇會導致檢測精度差別達到3倍或者更多。檢測閾值更是直接決定了檢測率的大小，小的閾值可以達到較高的檢測率，但同時也會帶來較高的誤報率；而大的閾值則會在降低誤報率的同時降低檢測精度。第二，大的或者連續的異常可以毒害PCA的正常子空間。足夠大的異常可以顯著地污染PCA的正常子空間，使得正常子空間的定義出現偏差，導致增加誤報率；連續的異常則可以使得 PCA將其歸入正常子空間中，將其當作流量的正常模式，從而降低檢測率，這 2個因素也是用來毒害 PCA以降低其檢測精度的重要方法[10,11]。

錢葉魁等從時空特性出發，提出了基于多尺度PCA(MSPCA, multiscale PCA)[12]的方法。該方法在進行PCA方法之前加入了小波去噪的過程，意在去除數據中的噪聲（由于測量數據的錯誤或不準確導致）并使得數據平滑，然后使用PCA方法分離正常和異常子空間，最后使用Q統計量計算閾值或者指數滑動平均控制圖來檢測網絡異常。可以看出MSPCA方法與PCA方法的最主要區別在于其加入了小波去噪過程，而這會減輕大的異常對于正常子空間的影響，從而有可能提高檢測精度；第二，MSPCA方法考慮了采用指數滑動平均控制圖來設定檢測閾值。

文獻[13]提出了基于統計用戶行為距離的異常檢測方法。為了減小 PCA算法檢測的復雜性，文獻[14]提出了分布式實現 PCA檢測的方法。Tarem等人在文獻[7]指出 PCA方法在檢測連續異常時性能較差，并提出了基于核密度估計的檢測方法，但這種方法的參數較多，實際檢測時需要大量的人工干預。本文方法與已有方法的最大不同在于：在檢測連續突發異常時擁有更好的性能，并且分解過程具有更好的可解釋性。

3 流量矩陣建模及NMF-NAD算法

本節首先定義了流量矩陣模型；然后介紹了NMF的基本思想，并分析了其與PCA的主要區別；最后提出了基于 NMF的全網絡異常檢測算法NMF-NAD，并分析了該算法的復雜度。

3.1 流量矩陣和非負矩陣分解

全網絡異常檢測是基于在多個網絡位置經多個測量周期統計得到的流量特征數據進行的[8]。這里的網絡位置可以是鏈路、路由器以及匯聚點等等。流量特征則可以是分組數、流數、字節數以及源IP地址熵等各種流量統計信息。為了便于研究，定義流量矩陣X為一個dp×的矩陣，其中，d是測量周期的數量，而p是網絡位置的數量[8]。Xij表示在第i個測量周期時第j個網絡位置流量特征數據的測量值。

對于流量矩陣X=[X1,X2,…,Xp]，其中，Xi是第i個網絡位置的測量值列向量，Xi∈Rd，d是測量周期的數量。NMF的目標是將X分解為2個矩陣U∈Rd×r和V∈Rr×p，X≈UV，并滿足如下目標函數：

定義了代價函數之后，那么式(2)可以重寫為如下帶有約束的非線性最優化問題：

式(3)是一個帶約束的非線性規劃問題，而約束條件就是V非負，可以使用Lagrange multiplier方法求解。令U=[uij]，V=[vij]。令αij，βij分別是對應限制條件uij≥0 和vij≥0 的 Lagrange乘子，并令矩陣α=[αij],β=[βij]。那么拉格朗日函數L就如式(4)所示：

求L對于U和V的偏導如式(5)所示：

利用 Kuhn-Tucker條件αijuij=0，βijvij=0，得到式(6)：

從而得到式(7)所示的更新方程：

3.2 基于NMF的全網絡流量異常檢測

基于 NMF的全網絡流量異常檢測主要分為 3步：構建正常子空間、獲取殘余矩陣以及異常凸顯與檢測。

3.2.1 構建正常子空間

對于原始流量矩陣X，第i個網絡位置的測量值向量可以看作位于d維實空間的一個點。由于具有低維特性，因此流量矩陣可以用一個r（r＜＜d）維子空間表示，而這個r維子空間則可以通過NMF構建。更具體地說，對X進行NMF之后，得到的U=[U1,U2,…,Ur]的每一列都構成了r維子空間的一個基向量，其中每一維基向量都捕獲了流量隨時間變化的一種時變模式。而V=[V1,V2,…,Vp]則是矩陣X中每一列在這個r維子空間的系數向量。類似于文獻[15]中的概念，稱該r維子空間為正常子空間。

基于NMF的正常子空間構建過程與基于PCA的基向量提取過程[15,16]有 2點不同。第一，由于NMF是帶約束條件的最優化問題且目標函數是非凸函數，因此采用梯度下降的優化方法只能得到局部最優解，與 PCA追求的全局誤差最小化相比，局部最優的結果使得連續突發異常現象能夠較好地凸顯出來；第二，NMF抽取的基向量和系數具有非負的特點，這使得各個基向量之間的內積均大于零，因此基向量之間不完全正交，這與“網絡流量的變化是多種流量變化模式的加性組合”這一事實相吻合。而 PCA的系數向量中存在負值，這使得網絡流量可能是多個時變模式的負的疊加，可解釋性較差。

3.2.2 獲取殘余矩陣

構建了r維子空間以后，就可以利用這r個基向量對流量矩陣進行重構，得到矩陣，并且將看作是流量矩陣中的噪聲和異常部分，稱為殘余矩陣。每個測量周期在殘余矩陣中對應的行是異常時刻凸顯的基礎，稱為這個測量周期對應的殘余流量。

3.2.3 凸顯與檢測異常

對于第i個測量周期的測量值經過NMF之后，可以記作其中，分別表示矩陣的第i行，并且分別是Xi中的正常和異常(殘余)流量的成分。如果在第i個測量周期發生了網絡異常，則Xi將有更多的流量落入中，使得其在中的值大于那些未發生網絡異常的測量周期的值，使發生網絡異常的測量周期和正常測量周期在中對應的向量的值存在較大的差別。

如果在每個測量周期采取均值、標準差或者極差作為統計信息，則發生網絡異常的測量周期與正常的測量周期在中對應的向量的值之間的差別就表現為二者統計信息之間的差別。該差別可用Shewhart控制圖[17]很好地捕捉到。為了描述清晰，將每個測量周期稱為一個采樣點，將發生異常的測量周期稱作異常采樣點，而將未發生異常的測量周期稱為正常采樣點。

Shewhart控制圖的理論依據是中心極限定理[17]，它假定研究對象服從正態分布，利用樣本數據檢驗總體的均值μ和標準差σ是否發生顯著變化來設定控制限，并以控制限為標準來判斷某個采樣點是否發生異常或超出控制。本文選擇的是均值-極差控制圖(

假定d個樣本獨立服從正態分布N(μ,σ2)，并且每個采樣點有p個采樣值。在第i個采樣點，其極差為Ri，而R是d個采樣點極差的均值，

當μ和σ都已知時，以概率 1-α落在區間中。在實際應用中，μ1-α/2通常取為3，也就是生產中的3σ控制線。根據中心極限定理，即使樣本偏離正態假設，Shewhart控制圖的結果仍然近似可用。對于均值和方差，采用樣本進行估計，則控制圖的控制界限可以寫作式(8)～式(10)：

3.3 NMF-NAD算法描述

3.3.1 NMF-NAD算法

基于上述討論，提出一種基于 NMF的全網絡異常檢測算法 NMF-NAD。該算法包含以下基本步驟：1) 對原始流量矩陣X進行非負矩陣分解，得到重構矩陣，如算法1中的第1到第2步所示；2) 計算得到誤差矩陣，如算法 1中的第 3步所示；3) 使用 Shewhart控制圖檢測發生異常的測量周期，如算法1中的第4到第9步所示。

算法1 NMF-NAD

輸入：X//原始流量矩陣

輸出：ATS(anomalies time period set) //發生異常的測量周期的集合

3.3.2 復雜性分析

NMF-NAD算法的時間復雜性主要包括2個部分：NMF分解和根據閾值進行的異常檢測。NMF分解的復雜性為O(pdkr)，其中，k是迭代的輪數，r是子空間的維數，d是測量周期的數量，p是網絡位置的數量。而基于閾值的判斷部分復雜度為O(d)，因此 NMF-NAD算法的時間復雜性為O(pdkr)。相比之下，PCA方法的復雜度為O(dp2)[15]。k與r在實際計算中取值均較小，因此一般地，NMF-NAD的實際處理復雜度低于 PCA方法的處理復雜度。

4 算法評價與分析

NMF-NAD作為一種新的子空間方法，為了考察其性能，將其與 2種典型的子空間方法 PCA[16]以及MSPCA[12]進行了對比。為了對這3種方法進行綜合的對比并分析NMF-NAD方法的敏感性，首先進行了模擬實驗，在人工生成的數據注入具有不同參數的異常，然后對3種方法的檢測結果進行了對比。為了進一步地驗證NMF-NAD方法在實際流量數據中的檢測效果，又采用最新提出的實驗方法基于因特網實測數據進行了實驗。為了評價異常檢測算法的檢測性能，采用了2個測度：檢測率和誤報率。檢測率定義為所有異常測量周期中被檢測出來的比例；誤報率定義為正常流量周期中被判定為異常的比例。

4.1 模擬實驗及其分析

4.1.1 模擬實驗方法

網絡流量通常由3種成分構成[18]：近似周期性的正常成分、高斯噪聲成分和異常成分。產生這 3種成分并按適當比例人工合成流量矩陣中每條網絡流(即X的一列)。具體步驟如下：利用多種不同周期的流量(比如周期為7天、5天、3天、24h、12h、6h、3h和1.5h的周期流)疊加來模擬周期性的網絡流量[16]，并構造基準流量矩陣，如圖1(a)所示；在基準流量矩陣上疊加上零均值的高斯噪聲，獲得不含異常的流量矩陣，如圖1(b)所示；再以一定的規則加入各種典型異常，如圖1(c)所示，其中，虛線圈中是異常注入的采樣點。用這種方法生成121條網絡流并組成流量矩陣X，其中，每條流包含2 010個測量周期。

圖1 合成一條異常流的步驟

在此考慮了 4種典型的流量異常[19]：阿爾法(alpha)異常、（分布式）拒絕服務攻擊(DoS, DDoS)、閃擁(flash crowd)和入口/出口移動(ingress/egress shift)異常。阿爾法異常是指點到點之間不尋常的高速字節傳輸；（分布式）拒絕服務攻擊是指單源或多源對單個目的地的洪泛攻擊；閃擁是指大量客戶同時訪問某一站點，比如某個Web服務器或視頻網站等；入口/出口移動則是BGP策略變化引起流量出口點的變化。

一般可以使用4個參數來描述這4種網絡流量異常[19]：持續時間、流量變化大小、源-目的數以及形狀函數。各種異常通常具有不同的持續時間，例如拒絕服務攻擊通常持續5～30min，阿爾法和閃擁異常可能持續任意時間，而入口/出口移動異常通常持續很多天，直到發生下次 BGP策略變化。當網絡異常出現時，可以用2種方式模擬流量大小的變化：一是通過為基準流量矩陣中部分網絡流乘上一個乘法因子，二是通過為基準流量矩陣中部分網絡流加上一個常數項。源-目的數是指異常所涉及的網絡流的數目，拒絕服務攻擊或阿爾法事件一般涉及到單個源和單個目的地；入口/出口移動異常則通常涉及到2個源點和2個目的地；而閃擁則會涉及到多個源和單個目的。形狀參數是用來模擬各種異常的變化行為，如阿爾法異常通常表現為流量大小的急劇上升，拒絕服務攻擊通常表現為流量大小的逐漸上升，閃擁事件通常表現為流量大小的迅速上升，然后又逐漸減少，而入口/出口移動表現為流量大小的階躍變化，這些行為可以用不同的形狀函數(比如斜坡、指數和臺階函數等)及其組合來表征。

在實驗中，采樣點之間間隔為5min，異常注入過程如下：從第300個采樣點到第800個采樣點期間，每隔50個采樣點注入一次阿爾法攻擊，并且阿爾法攻擊持續30min(持續6個采樣點)；從第1 000個到第1 500個采樣點里，每隔50個采樣點注入一次分布式拒絕服務攻擊或者閃擁攻擊，攻擊持續時間為30min(持續6個采樣點)；從第1 700到第1 800個采樣點期間，持續注入入口/出口移動的異常(持續100個采樣點)，將某條網絡流的一定比例的流量遷移到另外一個網絡流對上。

4.1.2 檢測結果

3種算法異常時刻凸顯的結果如圖2所示，其中，豎軸為各種檢測方法得到的每個測量周期對應的殘余流量向量中所有元素的平方和 (SSE, square sum of the elements of the residual traffic)。

對于PCA方法，采用的是Q統計量的方法進行檢測。

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

對于 MSPCA以及 NMF-NAD方法，采用了Shewhart控制圖進行異常檢測。檢測的具體過程如3.2.3節所述，是基于誤差矩陣進行的。結果分別如圖3和圖4所示。

圖3 MSPCA方法的檢測結果

圖4 NMF-NAD方法的檢測結果

由圖3和圖4可以看出，MSPCA和NMF-NAD不同程度地檢測出了PCA無法檢測的連續異常點。與NMF-NAD方法相比，MSPCA方法具有更高的誤報率，如在它第200個采樣點周圍的異常點都是由于誤報形成的。

具體的檢測結果如表1所示。可見NMF-NAD方法在三者中間檢測率最高，同時誤判率也較低。

表1 異常檢測結果

4.1.3 參數影響的討論

在NMF-NAD方法中，選取的r的數量和迭代周期k不僅會影響NMF-NAD方法的復雜性，也會影響方法的檢測效果。表2給出了在r取不同值時的檢測結果。由表2可以看出，r取值為2時檢測效果最佳。r的取值與數據集的特性有關，在不同的數據集上取值會有所不同。

表2r取值不同時的檢測結果

另外，考察了子空間的維數r=2時，迭代輪數k對于檢測效果的影響。實驗結果如圖5所示。可見，當k取值為50時就可以達到穩定的檢測效果。

圖5k取值不同時的NMF-NAD檢測效果對比

4.2 對因特網實測數據的分析

4.2.1 數據集、實驗方法以及測度

為了評價NMF-NAD算法在真實流量數據集上的檢測性能，采用了從Abilene實測得到的流量矩陣數據集[1,2,6,18]，數據集的具體描述如表 3所示。Dataset1與Dataset2采自不同的時期且有不同粒度，可以用來考量檢測方法的適用性。

表3 Abilene流量矩陣

為了保證對比的公平，采用文獻[20]最新提出的實驗方法。對于每一種檢測方法和每一個的數據集，具體過程如下。

第1步：對數據集應用檢測方法得到初始異常集合(BAS, base anomaies set)，其數量為|BAS|=NBAS，其中，| |表示集合的勢。

第2步：向數據集注入4種異常，并記為注入異常集合(IAS, injected anomalies set)，其數量為|IAS|=NIAS。

第3步：對注入異常后的數據集再次應用檢測方法，得到檢測異常集合(DAS, detected anomalies set)，并且異常的數量為|DAS|=NDAS，其中，屬于BAS的異常的數量為N1，屬于IAS的數量為N2。

第4步：根據BAS、IAS和DAS計算檢測率和保持率。

其中，檢測率(TPR, true positive ratio)以及保持率(KPR, keep positive ratio)定義如式(12)所示：

另外，在異常注入過程中，需要避免與現有異常的重合。

4.2.2 實驗結果

取子空間維數r=2，并且迭代輪數為50輪，3種方法的異常凸顯結果如圖6和圖7所示。圖6和圖7分別給出了針對Dataset1和Dataset2的異常時刻凸顯結果，其中，y軸是各種方法的殘余矩陣的2范數值。可以看出，NMF-NAD方法更好地凸顯出了發生異常的那些采樣點，MSPCA方法次之，而PCA方法無法較好地凸顯出異常的采樣點。

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

圖7 Dataset2數據集異常凸顯結果

運行 50次后取均值，最終的檢測結果分別如表4和表5所示。可見NMF-NAD方法在實測數據環境下，取得了高于PCA和MSPCA方法的檢測率，并且較好地檢測出了原有的異常點。

表4 3種檢測方法對Dataset1的檢測結果

表5 3種檢測方法Dataset 2的檢測結果

5 結束語

本文提出了一種基于非負子空間的全網絡異常檢測方法 NMF-NAD，理論分析表明該算法與PCA類方法相比，在檢測連續突發的情況下具有更好的性能。模擬實驗數據以及因特網實測數據的分析表明，NMF-NAD算法具有更好的檢測性能，優于PCA以及MSPCA方法。目前提出的NMF-NAD方法屬于批處理的檢測方法，下一步要對其進行改進，提出在線的、存儲開銷更低的檢測方法，并考慮對發生異常的網絡流進行定位。

[1] LAKHINA A, CROVELLA M, DIOT C. Characterization of network-wide anomalies in traffic flows[A]. IMC[C]. 2004. 201-206.

[2] LOGG C, COTTRELL L, NAVRATIL J. Experiences in traceroute and available bandwidth change analysis[A]. SIGCOMM Workshop[C]. 2004. 247-252.

[3] BRUTLAG J D. Aberrant behavior detection in time series for network monitoring[A]. USENIX[C]. New Orleans, Louisiana, USA,2000. 139-146.

[4] MA J, PERKINS S. Online novelty detection on temporal sequences[A]. SIGKDD[C]. Washington, DC, USA, 2003.613-618.

[5] LAKHINA A, CROVELLA M, DIOT C. Mining anomalies using traffic feature distributions[A]. SIGCOMM[C]. Philadelphia, Pennsylvania, USA, 2005. 217-228.

[6] AHMED T, COATES M, LAKHINA A. Multivariate online anomaly detection using kernel recursive least squares[A]. INFOCOM[C]. Anchorage, Alaska, USA, 2007. 625-633.

[7] AHMED T. Online anomaly detection using KDE[A]. GlobeCom[C].Honolulu, Hawaii, USA, 2009. 1-8.

[8] REINGBERG H, SOULE A, REXFORD J,et al. Sensitivity of PCA for traffic anomaly detection[A]. ACM Sigmetrics[C]. 2007. 109-120.

[9] BRAUKHOFF D, SALAMATIAN K, MAY M. Applying PCA for traffic anomaly detection: problems and solutions[A]. IEEE INFOCOMM[C]. 2009. 2866-2870.

[10] RUBINSTEIN B I P, NELSON B, HUANG L,et al. ANTIDOTE:understanding and defending against poisoning of anomaly detectors[A]. ACM IMC[C]. 2009.1-14.

[11] 錢葉魁, 陳鳴. 面向 PCA 異常檢測器的攻擊和防御機制[J]. 電子學報, 2011, 39(3):543-548.QIAN Y K, CHEN M. Poison attack and defense strategies on PCA-based anomaly detector[J]. Acta Electronica Sinica, 2011, 39(3):543-548.

[12] BAKSHI B. Multiscale PCA with application to multivariate statistical process monitoring[J]. AIChE Journal,1998,44(7): 1596-1610.

[13] SENGAR H, WANG X, WANG H,et al. Online detecting of network traffic anomalies using behavioral distance[A]. IWQoS[C]. Charleston,South Carolina, 2009. 1-9.

[14] LIU Y, ZHANG L, GUAN Y. Sketch-based streaming PCA algorithm for network-wide traffic anomaly detection[A]. ICDCS[C]. Genoa, Italy, 2010. 807-816.

[15] XU W, LIU X, GONG Y. Document clustering based on non-negative matrix factorization[A]. ACM SIGIR[C]. Toronto, Canada, 2003.267-273.

[16] LAKHINA A, CROVELLA M, DIOT C. Diagnosing network-wide traffic anomalies[A]. SIGCOMM[C]. Portland, OR, USA, 2004. 219-230.

[17] 王兆軍, 鄒長亮, 李忠華. 統計質量控制圖理論與方法[EB/OL].http://www.202.113.29.3/～zjwang/publications/books/spc.pdf.WANG Z J, ZOU C L, LI Z H. The theory and methods of statistical quality control charts[EB/OL]. http://www.202.113.29.3/～zjwang/publications/ books/ spc.pdf.

[18] LAKHINA A, PAPAGIANNAKI K, CROVELLA M,et al. Structural analysis of network traffic flows[A]. SIGMETRICS[C]. New York,NY, USA, 2004.61-72.

[19] SOULE A, SALAMATIAN K E, TAFT N. Combining filtering and statistical methods for anomaly detection[A]. IMC[C]. Berkeley, CA,USA, 2005. 1-14.

[20] NYALKALKAR K, SINHA S, BAILEY M,et al. A comparative study of two network-based anomaly detection methods[A]. INFOCOM[C]. Shanghai, China, 2011. 176-180.