基于奇異值分解更新的多元在線異常檢測方法

錢葉魁 陳 鳴

①(解放軍理工大學(xué)指揮自動(dòng)化學(xué)院 南京 210007)②(解放軍防空兵指揮學(xué)院 鄭州 450052)

1 引言

所謂網(wǎng)絡(luò)異常是指網(wǎng)絡(luò)運(yùn)行偏離正常狀態(tài)的情況。導(dǎo)致網(wǎng)絡(luò)異常的原因很多，包括網(wǎng)絡(luò)設(shè)備誤配置、網(wǎng)絡(luò)故障、網(wǎng)絡(luò)安全事件(分布式拒絕服務(wù)攻擊、蠕蟲傳播等)以及不尋常的用戶行為等。異常檢測對于保證網(wǎng)絡(luò)的正常運(yùn)行具有重要意義，一直是網(wǎng)絡(luò)研究的熱點(diǎn)問題。

Lakhina等人[1,2]提出的基于PCA的異常檢測算法奠定了多元異常檢測的基礎(chǔ)。Jin等人[3]運(yùn)用流量活動(dòng)圖分解的方法對骨干網(wǎng)流量進(jìn)行了分析，揭示了各種網(wǎng)絡(luò)異常行為；Torres等人[4]運(yùn)用流量聚類的分析方法推斷P2P網(wǎng)絡(luò)的異常行為。這些方法都是一種離線的分析方法，無法適用于在線分析和檢測異常的需要。而現(xiàn)有的網(wǎng)絡(luò)異常在線檢測算法[5]大都僅僅關(guān)注單條鏈路的流量異常或單條端到端路徑的性能異常。國內(nèi)有關(guān)網(wǎng)絡(luò)流量異常檢測的文獻(xiàn)很多，但是大多是針對某種特定異常的離線檢測方法[6,7]。因此，網(wǎng)絡(luò)管理員亟需一種既能夠在線地檢測網(wǎng)絡(luò)異常，又能夠取得很好的檢測性能的算法。

本文正是以此作為研究目標(biāo)，提出一種基于奇異值分解更新的多元在線異常檢測算法(MOADASVDU)。主要?jiǎng)?chuàng)新點(diǎn)包括以下兩個(gè)方面：(1)利用奇異值分解的更新算法，提出了一種全網(wǎng)絡(luò)異常的在線檢測算法MOADA-SVDU，并對該算法的復(fù)雜度進(jìn)行了分析；(2)通過分析因特網(wǎng)實(shí)測的流量矩陣數(shù)據(jù)集及模擬試驗(yàn)，證實(shí)了MOADA-SVDU算法的有效性。

2 MOADA-SVDU算法

本節(jié)首先描述能夠刻畫網(wǎng)絡(luò)流量完整視圖的流量矩陣模型，然后利用奇異值分解更新的方法以增量的方式建立能夠刻畫網(wǎng)絡(luò)流量變化規(guī)律的常態(tài)模型，由此提出一種增量的多元在線異常檢測算法MOADA-SVDU，最后對該算法的存儲(chǔ)開銷和時(shí)間復(fù)雜度進(jìn)行理論分析。

2.1 流量矩陣模型

定義1 流量矩陣 假設(shè)某自治系統(tǒng)(Autonomous System, AS)有n個(gè)邊界路由器，以一定的時(shí)間間隔(周期)連續(xù)地被動(dòng)測量任意一對邊界路由器之間的流量，然后將這些測量值排列成一個(gè)p×T的矩陣X，它表示所有這些流量測量值的時(shí)間序列。其中，T表示測量的周期數(shù)，p表示每個(gè)周期內(nèi)測量獲得的流量測量值的個(gè)數(shù)，即p=n×n；第i列表示在第i個(gè)周期內(nèi)流量測量值向量，通常用Xi表示，第j行表示第j個(gè)路由器對之間流量測量值的時(shí)間序列。矩陣X稱為AS的路由級流量矩陣，簡稱為流量矩陣。根據(jù)選擇的流量測度，可以定義基于不同測度的流量矩陣：分組數(shù)矩陣、流數(shù)矩陣、字節(jié)數(shù)矩陣等。

2.2 MOADA-SVDU算法

流量異常檢測的前提是建立網(wǎng)絡(luò)流量的常態(tài)模型，然后根據(jù)這個(gè)常態(tài)模型來分析獲得的測量樣本，從而確定它們是正常的還是異常的。在離線異常檢測中，通常以批處理的方式建立常態(tài)模型，從而確定在這批測量樣本中哪些屬于異常；而在在線異常檢測中，通常要以增量的方式建立常態(tài)模型，每步只處理單個(gè)測量樣本，判斷該測量樣本是否屬于異常，并利用該測量樣本更新常態(tài)模型。

許多規(guī)模較大的AS(如Abilene)通常具有十幾個(gè)邊界路由器。如果將AS所有邊界路由器間的流量測量值看作一個(gè)輸入向量Xi，則該向量Xi是存在于高維空間p?中的一個(gè)多元變量，流量矩陣X可以看作高維空間p?中多元變量的時(shí)間序列其中T表示測量的周期數(shù)。而PCA是處理類似流量矩陣高維數(shù)據(jù)的一種最有效的方法，它能夠通過降低維度的方法實(shí)現(xiàn)最小均方意義下原始數(shù)據(jù)的重構(gòu)。

奇異值分解(Singular Value Decomposition,SVD)是實(shí)現(xiàn)PCA的另一種重要方法。直接對歸一化的輸入向量進(jìn)行SVD如下：

因此

由式(1)-式(4)可以看出：對X的協(xié)方差矩陣C進(jìn)行譜分解得到的特征向量矩陣與直接對X進(jìn)行SVD得到的特征向量矩陣完全相等；而對X的協(xié)方差矩陣C進(jìn)行譜分解得到的特征值矩陣是直接對X進(jìn)行SVD得到的奇異值矩陣Σ的平方，即=2ΛΣ。因此，可以直接對X進(jìn)行SVD，求取協(xié)方差矩陣C對應(yīng)的特征值矩陣和特征向量矩陣，從而實(shí)現(xiàn)PCA。

但是，SVD同樣屬于批處理算法，它要求流量矩陣X必須提前給定。為了以增量的方式計(jì)算特征值矩陣和特征向量矩陣，本文引入一種SVD更新算法[8]。

其中式(5)是對矩陣(I?Uk)B執(zhí)行QR分解；式(6)是對矩陣[Σk,B;0,R]執(zhí)行SVD；式(7)是根據(jù)式(5)，式(6)計(jì)算得到的有關(guān)參數(shù)計(jì)算矩陣[Ap×n,Bp×r]的秩-k近似矩陣。

本文在4.1節(jié)將通過實(shí)測數(shù)據(jù)分析表明MOADA-SVDU算法得到的殘余向量與PCA算法得到的殘余向量基本相同，而且對于同樣的流量測度，相鄰時(shí)期的流量矩陣對應(yīng)的Q統(tǒng)計(jì)量閾值非常接近。因此，可以將前一階段的流量矩陣作為訓(xùn)練集，并在該訓(xùn)練集上執(zhí)行PCA算法以獲得Q統(tǒng)計(jì)量閾值，然后以此作為下一階段MOADA-SVDU算法的異常檢測閾值。

基于以上基本原理，本文提出一種基于奇異值分解更新的多元在線異常檢測算法MOADASVDU，算法流程見表1。

表1 MOADA-SVDU算法

對于在線異常檢測算法來說，存儲(chǔ)開銷和時(shí)間復(fù)雜度是至關(guān)重要的兩個(gè)指標(biāo)。MOADA-SVDU算法可以分為兩個(gè)階段：在初始化階段，需要存儲(chǔ)X1；在增量檢測階段，需要存儲(chǔ)Uk、Σk、Vk以及x。因此，MOADA-SVDU算法總的存儲(chǔ)開銷為p×n+p×k+k×k+n×k+p×1，而PCA算法的存儲(chǔ)開銷為p×T的流量矩陣。由于n?T, k?p，所以MOADA-SVDU算法的存儲(chǔ)開銷遠(yuǎn)小于PCA。

MOADA-SVDU算法在增量檢測階段的計(jì)算瓶頸是式(5)的QR分解和式(6)的SVD，其時(shí)間復(fù)雜度分別為Ο(p)和Ο(p×k)；而PCA算法的計(jì)算瓶頸是對整個(gè)流量矩陣執(zhí)行譜分解，其時(shí)間復(fù)雜度為Ο(T×p2)。顯然，MOADA-SVDU算法的時(shí)間復(fù)雜度遠(yuǎn)低于PCA。

3 算法評價(jià)

為評價(jià)MOADA-SVDU算法的檢測性能，本文采用了兩種方法：對因特網(wǎng)實(shí)測數(shù)據(jù)的分析以及對模擬試驗(yàn)數(shù)據(jù)的分析，并在同等條件下與PCA算法進(jìn)行比較。

3.1 因特網(wǎng)實(shí)測數(shù)據(jù)的分析

(1)數(shù)據(jù)集 利用從Abilene實(shí)測得到的流量矩陣數(shù)據(jù)集[1,2,9]來評價(jià)MOADA-SVDU算法的檢測性能，數(shù)據(jù)集的具體描述見表2。

(2)檢測結(jié)果 選擇表2中4種不同流量測度的數(shù)據(jù)集：Dataset1，Dataset2，Dataset4和Dataset5，分別畫出輸入向量2-范數(shù)的平方、PCA算法計(jì)算獲得的殘余向量2-范數(shù)的平方以及MOADA-SVDU算法計(jì)算獲得的殘余向量2-范數(shù)的平方，如圖1(a)-1(d)所示?？梢钥闯觯琈OADA-SVDU算法不僅實(shí)現(xiàn)了網(wǎng)絡(luò)流量異常的在線檢測，而且在大部分情況下都具有與PCA算法類似的檢測性能。

異常檢測閾值是影響MOADA-SVDU算法檢測性能的重要參數(shù)，為了驗(yàn)證以Q統(tǒng)計(jì)量作為閾值的可行性，計(jì)算并畫出表2中數(shù)據(jù)集Dataset1～Dataset6對應(yīng)的Q統(tǒng)計(jì)量，其中Dataset1～Dataset3對應(yīng)的Q統(tǒng)計(jì)量如圖2(a)所示，Dataset4～Dataset6對應(yīng)的Q統(tǒng)計(jì)量如圖2(b)所示?？梢钥闯?，雖然不同測度的流量矩陣對應(yīng)的Q統(tǒng)計(jì)量差異很大，但相鄰時(shí)期的流量矩陣對應(yīng)的Q統(tǒng)計(jì)量非常接近，這驗(yàn)證了3.2節(jié)中閾值選取方法的可行性。

表2 Abilene流量矩陣

圖1 PCA和MOADA-SVDU算法對實(shí)測數(shù)據(jù)的檢測結(jié)果

圖2 不同的流量矩陣對應(yīng)的Q統(tǒng)計(jì)量

3.2 模擬試驗(yàn)數(shù)據(jù)的分析

(1)模擬方法 考慮到網(wǎng)絡(luò)流量通常由3種成分的流量構(gòu)成[10]：近似周期性的正常成分、高斯噪聲成分和異常成分。因此，我們產(chǎn)生這3種成分來并按照適當(dāng)比例人工合成流量矩陣中每條OD流。具體步驟如下：

第1步 利用3種不同周期的正弦波疊加來模擬正常的OD流，并構(gòu)造基準(zhǔn)流量矩陣。

第2步 在第1步產(chǎn)生的基準(zhǔn)流量矩陣的每條OD流上加入零均值的高斯噪聲，獲得不含異常的基準(zhǔn)流量矩陣。

第3步 在第2步產(chǎn)生的含噪音的基準(zhǔn)流量矩陣中以一定的規(guī)則加入各種典型異常，異常的合成步驟如圖3所示。

由于本文重點(diǎn)關(guān)注流量大小異常的檢測，所以本文模擬4種最常見的流量異常：阿爾法(alpha)異常、(分布式)拒絕服務(wù)攻擊(DoS, DDoS)、閃擁(flash crowd)、入口/出口移動(dòng)(ingress/egress shift)異常。這4種異常的具體特征見表3。

圖3 異常的合成步驟

表3 異常類型及其特征

可以用4個(gè)參數(shù)來描述這4種網(wǎng)絡(luò)流量異常[11]：持續(xù)時(shí)間、流量變化大小、源-目的數(shù)以及形狀函數(shù)。當(dāng)網(wǎng)絡(luò)異常出現(xiàn)時(shí)，可以用兩種方式模擬流量大小的變化：一是通過為基準(zhǔn)流量矩陣中部分OD流乘上一個(gè)乘法因子，二是通過為基準(zhǔn)流量矩陣中部分OD流加上一個(gè)常數(shù)項(xiàng)。源-目的數(shù)是指異常所涉及的OD流的數(shù)目，記號(1,1)表示異常涉及單個(gè)源和單個(gè)目的地，這可能是由于拒絕服務(wù)攻擊或阿爾法事件，(N,1)表示異常涉及N個(gè)源點(diǎn)和1個(gè)目的地，這可能是由于出現(xiàn)了分布式拒絕服務(wù)攻擊或閃擁，(2,2)表示異常涉及2個(gè)源點(diǎn)和2個(gè)目的地，這可能是由于入口/出口移動(dòng)事件引起的。形狀函數(shù)是用來模擬各種異常的變化行為，這些行為可以用不同的形狀函數(shù)及其組合來表征。以上4個(gè)參數(shù)的可能取值見表4。

(2)檢測結(jié)果 采用上述方法模擬4種不同的網(wǎng)絡(luò)異常，來評價(jià)算法的檢測性能。當(dāng)模擬阿爾法事件或拒絕服務(wù)攻擊時(shí)，從第1000時(shí)刻開始產(chǎn)生異常，持續(xù)時(shí)間為4個(gè)周期，將某條OD流的流量大小從增加20%迅速增加至80%。當(dāng)模擬分布式拒絕服務(wù)攻擊或閃擁事件時(shí)，從第1500時(shí)刻開始產(chǎn)生異常，持續(xù)時(shí)間為6個(gè)周期，將5條OD流的流量大小從增加10%迅速增加至50%，然后又逐漸降低至10%。當(dāng)模擬入口/出口移動(dòng)事件時(shí)，從第1700時(shí)刻開始產(chǎn)生異常，持續(xù)時(shí)間為40個(gè)周期，將某條OD流的流量大小減少50%，即為某條OD流的流量大小乘以0.5，且將減少的這部分流量加到另一條OD流上。檢測結(jié)果如圖4(a)所示，MOADA-SVDU算法能夠非常準(zhǔn)確地檢測出這3種人造異常，與PCA算法的檢測結(jié)果幾乎完全相同。KRLS算法[9]的檢測結(jié)果如圖4(b)所示，顯然無法通過設(shè)置某一閾值來檢測異常，其中δt表示投影誤差。因此，MOADA-SVDU算法的檢測性能明顯優(yōu)于KRLS算法。

表4 異常參數(shù)及其取值

下面進(jìn)一步研究MOADA-SVDU算法的敏感性。從第1000時(shí)刻開始產(chǎn)生異常，持續(xù)時(shí)間為10個(gè)周期，將某條OD流的流量大小從5%逐漸增加至50%，檢測結(jié)果如圖5(a)所示，在前4個(gè)周期，由于異常流量較小，所以無法被檢測到，而從第1004-1009時(shí)刻成功檢測到異常，由此可見，異常流量越大，MOADA-SVDU算法的檢測性能越好。在第1500時(shí)刻，將某條OD流的流量大小增加20%，持續(xù)時(shí)間為5個(gè)周期，在第1550時(shí)刻，將某10條OD流的流量大小同時(shí)增加20%，持續(xù)時(shí)間也為5個(gè)周期，檢測結(jié)果如圖5(b)所示，異常分布范圍越廣，算法的檢測性能越好，由此可見MOADA-SVDU算法尤其適合檢測那些局部影響不大但影響范圍較廣的異常，如DDoS攻擊。

4 結(jié)束語

圖4 PCA, MOADA-SVDU和KRLS算法對模擬試驗(yàn)數(shù)據(jù)的檢測結(jié)果

圖5 MOADA-SVDU算法的敏感性分析

本文提出了一種基于奇異值分解更新的多元在線異常檢測算法MOADA-SVDU，Abilene實(shí)測的流量矩陣數(shù)據(jù)和模擬試驗(yàn)數(shù)據(jù)分析表明該算法不僅實(shí)現(xiàn)了網(wǎng)絡(luò)流量的在線檢測，而且取得了與批處理算法PCA類似的檢測性能，完全能夠滿足網(wǎng)絡(luò)管理員在線有效地檢測網(wǎng)絡(luò)異常的需要。近期的研究表明PCA異常檢測器自身也會(huì)遭受方差注入攻擊[12]，且流量矩陣可能出現(xiàn)丟失元素值的情況[13]，因此下一步我們將研究更為魯棒的PCA異常檢測方法。

[1] Lakhina A, Crovella M, and Diot C. Diagnosing network-wide traffic anomalies[C]. SIGCOMM, Portland,Oregon, USA, 2004: 224-235.

[2] Lakhina A, Crovella M, and Diot C. Mining anomalies using traffic feature distributions[C]. SIGCOMM, Philadelphia,Pennsylvania, USA, 2005: 164-175.

[3] Jin Y, Sharafuddin E, and Zhang Z L. Unveiling core network-wide communication patterns through application traffic activity graph decomposition[C]. SIGMETRICS,Seattle, WA, USA, 2009: 86-91.

[4] Torres R, Hajjat M, and Rao S G, et al.. Inferring undesirable behavior from P2P traffic analysis[C]. SIGMETRICS, Seattle,WA, USA, 2009: 156-167.

[5] Logg C, Cottrell L, and Navratil J. Experiences in traceroute and available bandwidth change analysis[C]. SIGCOMM Workshop, Portland, Oregon, USA, 2004: 81-90.

[6] 吳志軍, 張東. 低速率DDoS攻擊的仿真和特征提取[J]. 通信學(xué)報(bào), 2008, 29(1): 71-76.Wu Z J and Zhang D. Attack simulation and signature extraction of low-rate DDoS[J]. Journal on Communications,2008, 29(1): 71-76.

[7] 謝逸, 余順爭. 基于Web用戶瀏覽行為的統(tǒng)計(jì)異常檢測[J].軟件學(xué)報(bào), 2007, 18(4): 967-977.Xie Y and Yu S Z. Anomaly detection based on web users’browsing behaviors[J]. Journal of Software, 2007, 18(4):967-977.

[8] Zhao H, Yuen P C, and Kwok J T. A novel incremental principal component analysis and its application for face recognition[J]. IEEE Transactions on Systems, Man, and Cybernetics-Part B: Cybernetics, 2006, 36(3): 873-886.

[9] Ahmed T, Coates M, and Lakhina A. Multivariate online anomaly detection using kernel recursive least squares[C].INFOCOM, Los Angeles, USA, 2007: 387-396.

[10] Lakhina A, Papagiannaki K, and Crovella M, et al..Structural analysis of network traffic flows[C]. SIGMETRICS,New York, NY, USA, 2004: 156-167.

[11] Soule A, Salamatian K, and Taft N. Combining filtering and statistical methods for anomaly detection[C]. IMC, Boston,USA, 2005: 168-179.

[12] Rubinstein B, Nelson B, and Huang L. Stealthy poisoning attacks on PCA-based anomaly detectors[C]. SIGMETRICS,Seattle, WA, USA, 2009: 168-179.

[13] Zhang Y, Roughan M, and Willinger W, et al..Spatio-temporal compressive sensing and Internet traffic matrices[C]. SIGCOMM, Barcelona, Spain, 2009: 110-121.