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

錢葉魁 陳 鳴

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

1 引言

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

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

本文正是以此作為研究目標，提出一種基于奇異值分解更新的多元在線異常檢測算法(MOADASVDU)。主要創新點包括以下兩個方面：(1)利用奇異值分解的更新算法，提出了一種全網絡異常的在線檢測算法MOADA-SVDU，并對該算法的復雜度進行了分析；(2)通過分析因特網實測的流量矩陣數據集及模擬試驗，證實了MOADA-SVDU算法的有效性。

2 MOADA-SVDU算法

本節首先描述能夠刻畫網絡流量完整視圖的流量矩陣模型，然后利用奇異值分解更新的方法以增量的方式建立能夠刻畫網絡流量變化規律的常態模型，由此提出一種增量的多元在線異常檢測算法MOADA-SVDU，最后對該算法的存儲開銷和時間復雜度進行理論分析。

2.1 流量矩陣模型

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

2.2 MOADA-SVDU算法

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

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

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

因此

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

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

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

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

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

表1 MOADA-SVDU算法

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

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

3 算法評價

為評價MOADA-SVDU算法的檢測性能，本文采用了兩種方法：對因特網實測數據的分析以及對模擬試驗數據的分析，并在同等條件下與PCA算法進行比較。

3.1 因特網實測數據的分析

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

(2)檢測結果 選擇表2中4種不同流量測度的數據集：Dataset1，Dataset2，Dataset4和Dataset5，分別畫出輸入向量2-范數的平方、PCA算法計算獲得的殘余向量2-范數的平方以及MOADA-SVDU算法計算獲得的殘余向量2-范數的平方，如圖1(a)-1(d)所示。可以看出，MOADA-SVDU算法不僅實現了網絡流量異常的在線檢測，而且在大部分情況下都具有與PCA算法類似的檢測性能。

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

表2 Abilene流量矩陣

圖1 PCA和MOADA-SVDU算法對實測數據的檢測結果

圖2 不同的流量矩陣對應的Q統計量

3.2 模擬試驗數據的分析

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

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

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

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

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

圖3 異常的合成步驟

表3 異常類型及其特征

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

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

表4 異常參數及其取值

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

4 結束語

圖4 PCA, MOADA-SVDU和KRLS算法對模擬試驗數據的檢測結果

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

本文提出了一種基于奇異值分解更新的多元在線異常檢測算法MOADA-SVDU，Abilene實測的流量矩陣數據和模擬試驗數據分析表明該算法不僅實現了網絡流量的在線檢測，而且取得了與批處理算法PCA類似的檢測性能，完全能夠滿足網絡管理員在線有效地檢測網絡異常的需要。近期的研究表明PCA異常檢測器自身也會遭受方差注入攻擊[12]，且流量矩陣可能出現丟失元素值的情況[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]. 通信學報, 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用戶瀏覽行為的統計異常檢測[J].軟件學報, 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.