NMF-NAD：基于NMF的全網(wǎng)絡(luò)流量異常檢測(cè)方法

魏祥麟，陳鳴，張國(guó)敏，黃建軍

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

1 引言

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

網(wǎng)絡(luò)流量異常是指網(wǎng)絡(luò)流量不尋常地和顯著地變化，并且可能涵蓋多條鏈路或者路徑[1]。檢測(cè)流量異常面臨的主要難點(diǎn)在于：第一，因特網(wǎng)流量的高波動(dòng)和長(zhǎng)相關(guān)性會(huì)使異常流量淹沒(méi)于正常的流量之中；第二，流量異常模式非常分散并且經(jīng)常出現(xiàn)新型異常流量；第三，網(wǎng)絡(luò)流量巨大，分布式收集和處理很困難；第四，異常檢測(cè)的實(shí)用化要求做到早期檢測(cè)，對(duì)時(shí)效性要求較高。

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

本文的內(nèi)容安排如下：第2節(jié)綜述相關(guān)工作；第3節(jié)研究NMF-NAD算法；第4節(jié)通過(guò)實(shí)驗(yàn)驗(yàn)證了NMF-NAD算法的有效性；第5節(jié)是結(jié)束語(yǔ)。

2 相關(guān)工作

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

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

錢葉魁等從時(shí)空特性出發(fā)，提出了基于多尺度PCA(MSPCA, multiscale PCA)[12]的方法。該方法在進(jìn)行PCA方法之前加入了小波去噪的過(guò)程，意在去除數(shù)據(jù)中的噪聲（由于測(cè)量數(shù)據(jù)的錯(cuò)誤或不準(zhǔn)確導(dǎo)致）并使得數(shù)據(jù)平滑，然后使用PCA方法分離正常和異常子空間，最后使用Q統(tǒng)計(jì)量計(jì)算閾值或者指數(shù)滑動(dòng)平均控制圖來(lái)檢測(cè)網(wǎng)絡(luò)異常?？梢钥闯鯩SPCA方法與PCA方法的最主要區(qū)別在于其加入了小波去噪過(guò)程，而這會(huì)減輕大的異常對(duì)于正常子空間的影響，從而有可能提高檢測(cè)精度；第二，MSPCA方法考慮了采用指數(shù)滑動(dòng)平均控制圖來(lái)設(shè)定檢測(cè)閾值。

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

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

本節(jié)首先定義了流量矩陣模型；然后介紹了NMF的基本思想，并分析了其與PCA的主要區(qū)別；最后提出了基于 NMF的全網(wǎng)絡(luò)異常檢測(cè)算法NMF-NAD，并分析了該算法的復(fù)雜度。

3.1 流量矩陣和非負(fù)矩陣分解

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

對(duì)于流量矩陣X=[X1,X2,…,Xp]，其中，Xi是第i個(gè)網(wǎng)絡(luò)位置的測(cè)量值列向量，Xi∈Rd，d是測(cè)量周期的數(shù)量。NMF的目標(biāo)是將X分解為2個(gè)矩陣U∈Rd×r和V∈Rr×p，X≈UV，并滿足如下目標(biāo)函數(shù)：

定義了代價(jià)函數(shù)之后，那么式(2)可以重寫為如下帶有約束的非線性最優(yōu)化問(wèn)題：

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

求L對(duì)于U和V的偏導(dǎo)如式(5)所示：

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

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

3.2 基于NMF的全網(wǎng)絡(luò)流量異常檢測(cè)

基于 NMF的全網(wǎng)絡(luò)流量異常檢測(cè)主要分為 3步：構(gòu)建正常子空間、獲取殘余矩陣以及異常凸顯與檢測(cè)。

3.2.1 構(gòu)建正常子空間

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

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

3.2.2 獲取殘余矩陣

構(gòu)建了r維子空間以后，就可以利用這r個(gè)基向量對(duì)流量矩陣進(jìn)行重構(gòu)，得到矩陣，并且將看作是流量矩陣中的噪聲和異常部分，稱為殘余矩陣。每個(gè)測(cè)量周期在殘余矩陣中對(duì)應(yīng)的行是異常時(shí)刻凸顯的基礎(chǔ)，稱為這個(gè)測(cè)量周期對(duì)應(yīng)的殘余流量。

3.2.3 凸顯與檢測(cè)異常

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

如果在每個(gè)測(cè)量周期采取均值、標(biāo)準(zhǔn)差或者極差作為統(tǒng)計(jì)信息，則發(fā)生網(wǎng)絡(luò)異常的測(cè)量周期與正常的測(cè)量周期在中對(duì)應(yīng)的向量的值之間的差別就表現(xiàn)為二者統(tǒng)計(jì)信息之間的差別。該差別可用Shewhart控制圖[17]很好地捕捉到。為了描述清晰，將每個(gè)測(cè)量周期稱為一個(gè)采樣點(diǎn)，將發(fā)生異常的測(cè)量周期稱作異常采樣點(diǎn)，而將未發(fā)生異常的測(cè)量周期稱為正常采樣點(diǎn)。

Shewhart控制圖的理論依據(jù)是中心極限定理[17]，它假定研究對(duì)象服從正態(tài)分布，利用樣本數(shù)據(jù)檢驗(yàn)總體的均值μ和標(biāo)準(zhǔn)差σ是否發(fā)生顯著變化來(lái)設(shè)定控制限，并以控制限為標(biāo)準(zhǔn)來(lái)判斷某個(gè)采樣點(diǎn)是否發(fā)生異?；虺隹刂啤１疚倪x擇的是均值-極差控制圖(

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

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

3.3 NMF-NAD算法描述

3.3.1 NMF-NAD算法

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

算法1 NMF-NAD

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

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

3.3.2 復(fù)雜性分析

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

4 算法評(píng)價(jià)與分析

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

4.1 模擬實(shí)驗(yàn)及其分析

4.1.1 模擬實(shí)驗(yàn)方法

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

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

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

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

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

4.1.2 檢測(cè)結(jié)果

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

對(duì)于PCA方法，采用的是Q統(tǒng)計(jì)量的方法進(jìn)行檢測(cè)。

圖2 3種方法的異常凸顯對(duì)比

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

圖3 MSPCA方法的檢測(cè)結(jié)果

圖4 NMF-NAD方法的檢測(cè)結(jié)果

由圖3和圖4可以看出，MSPCA和NMF-NAD不同程度地檢測(cè)出了PCA無(wú)法檢測(cè)的連續(xù)異常點(diǎn)。與NMF-NAD方法相比，MSPCA方法具有更高的誤報(bào)率，如在它第200個(gè)采樣點(diǎn)周圍的異常點(diǎn)都是由于誤報(bào)形成的。

具體的檢測(cè)結(jié)果如表1所示。可見(jiàn)NMF-NAD方法在三者中間檢測(cè)率最高，同時(shí)誤判率也較低。

表1 異常檢測(cè)結(jié)果

4.1.3 參數(shù)影響的討論

在NMF-NAD方法中，選取的r的數(shù)量和迭代周期k不僅會(huì)影響NMF-NAD方法的復(fù)雜性，也會(huì)影響方法的檢測(cè)效果。表2給出了在r取不同值時(shí)的檢測(cè)結(jié)果。由表2可以看出，r取值為2時(shí)檢測(cè)效果最佳。r的取值與數(shù)據(jù)集的特性有關(guān)，在不同的數(shù)據(jù)集上取值會(huì)有所不同。

表2r取值不同時(shí)的檢測(cè)結(jié)果

另外，考察了子空間的維數(shù)r=2時(shí)，迭代輪數(shù)k對(duì)于檢測(cè)效果的影響。實(shí)驗(yàn)結(jié)果如圖5所示?？梢?jiàn)，當(dāng)k取值為50時(shí)就可以達(dá)到穩(wěn)定的檢測(cè)效果。

圖5k取值不同時(shí)的NMF-NAD檢測(cè)效果對(duì)比

4.2 對(duì)因特網(wǎng)實(shí)測(cè)數(shù)據(jù)的分析

4.2.1 數(shù)據(jù)集、實(shí)驗(yàn)方法以及測(cè)度

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

表3 Abilene流量矩陣

為了保證對(duì)比的公平，采用文獻(xiàn)[20]最新提出的實(shí)驗(yàn)方法。對(duì)于每一種檢測(cè)方法和每一個(gè)的數(shù)據(jù)集，具體過(guò)程如下。

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

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

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

第4步：根據(jù)BAS、IAS和DAS計(jì)算檢測(cè)率和保持率。

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

另外，在異常注入過(guò)程中，需要避免與現(xiàn)有異常的重合。

4.2.2 實(shí)驗(yàn)結(jié)果

取子空間維數(shù)r=2，并且迭代輪數(shù)為50輪，3種方法的異常凸顯結(jié)果如圖6和圖7所示。圖6和圖7分別給出了針對(duì)Dataset1和Dataset2的異常時(shí)刻凸顯結(jié)果，其中，y軸是各種方法的殘余矩陣的2范數(shù)值?？梢钥闯?，NMF-NAD方法更好地凸顯出了發(fā)生異常的那些采樣點(diǎn)，MSPCA方法次之，而PCA方法無(wú)法較好地凸顯出異常的采樣點(diǎn)。

圖6 Dataset1數(shù)據(jù)集異常凸顯結(jié)果

圖7 Dataset2數(shù)據(jù)集異常凸顯結(jié)果

運(yùn)行 50次后取均值，最終的檢測(cè)結(jié)果分別如表4和表5所示。可見(jiàn)NMF-NAD方法在實(shí)測(cè)數(shù)據(jù)環(huán)境下，取得了高于PCA和MSPCA方法的檢測(cè)率，并且較好地檢測(cè)出了原有的異常點(diǎn)。

表4 3種檢測(cè)方法對(duì)Dataset1的檢測(cè)結(jié)果

表5 3種檢測(cè)方法Dataset 2的檢測(cè)結(jié)果

5 結(jié)束語(yǔ)

本文提出了一種基于非負(fù)子空間的全網(wǎng)絡(luò)異常檢測(cè)方法 NMF-NAD，理論分析表明該算法與PCA類方法相比，在檢測(cè)連續(xù)突發(fā)的情況下具有更好的性能。模擬實(shí)驗(yàn)數(shù)據(jù)以及因特網(wǎng)實(shí)測(cè)數(shù)據(jù)的分析表明，NMF-NAD算法具有更好的檢測(cè)性能，優(yōu)于PCA以及MSPCA方法。目前提出的NMF-NAD方法屬于批處理的檢測(cè)方法，下一步要對(duì)其進(jìn)行改進(jìn)，提出在線的、存儲(chǔ)開(kāi)銷更低的檢測(cè)方法，并考慮對(duì)發(fā)生異常的網(wǎng)絡(luò)流進(jìn)行定位。

[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 異常檢測(cè)器的攻擊和防御機(jī)制[J]. 電子學(xué)報(bào), 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] 王兆軍, 鄒長(zhǎng)亮, 李忠華. 統(tǒng)計(jì)質(zhì)量控制圖理論與方法[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.