基于低秩分解的網絡異常檢測綜述

李曉燦 謝 鯤 張大方 謝高崗

1(湖南大學信息科學與工程學院 長沙 410082) 2(中國科學院計算機網絡信息中心 北京 100190)

互聯網已經成為社會基礎設施，但面臨嚴重的安全挑戰[1]，如拒絕服務攻擊[2-3]、蠕蟲病毒[4]、僵尸網絡[5-6]等.例如，2016年Twitter與Spotify的大型數據中心，因遭受了持續的拒絕服務攻擊而關閉網站[8]；2017 WannaCry勒索[7]病毒感染了政府、能源、醫院、學校、工廠等多個領域.隨著新技術的不斷應用，互聯網變得越來越復雜，攻擊手段越來越先進，如何快速精準地檢測定位這些異常行為，避免造成更多的損失與危害，變得尤為重要.

1 研究背景

對于網絡異常，不少文獻有各自的定義：Thottan等人[9]將網絡異常描述為一種偏離正常網絡行為的事件；Barnett[10]將異常數據集定義為 “與數據集中其余部分出現不一致的觀測子集”；Chandola等人[11]認為異常數據的行為模式不符合既定的正常行為；根據Lakhina等人[12]所述，網絡異常表現為在網絡流量層面上出現不同尋常且明顯的變化，這種變化通常可以跨越多個網絡鏈接；Hoque等人[13]將異常定義為“相較于明確定義的正常行為數據，那些更不符合規定的、更令人關注的行為數據”；Hawkins[14]對異常的定義是“異常是遠離其他觀測數據而疑為不同機制產生的觀測數據”.通過上述定義發現，異常檢測本質就是檢測和發現數據中不符合期望行為的異常數據模式.研究人員在設計異常檢測算法前通常需要判斷所需檢測異常的種類，通常可分為3類[15-16]：

1) 單點異常(point anomalies).單點異常[11,15]即與全局數據的行為模型不同的單點數據.異常數據在數據集中單個出現，不產生聚集.例如某一局域網中，存在某一網絡節點發生擁塞，導致其丟包率遠遠高于其余網絡節點，那么該網絡節點即為單點異常.單點異常作為最簡單的一種異常種類，通常只需要簡單的聚類、分類算法即可進行有效檢測.網絡中U2R，R2L等攻擊[17-18]通?？梢暈閱吸c異常.

2) 集體異常(collective anomalies).集體異常[19-20]通常由多個對象組合構成，即單獨觀測某一獨立個體可能并不存在異常，但是這些個體同時出現則構成一種異常.集體異常通常是由若干個單點組成，例如，拒絕服務攻擊通常由攻擊者控制大量傀儡機向服務器發送請求來搶占服務器資源，使服務器無法響應正常請求，達到攻擊服務器的目的.

3) 上下文異常(contextual anomalies).上下文異常[21]通常被定義為：當數據點的值與同一上下文環境中的其他數據點明顯不同時，該數據點被認為是上下文異常值.值得注意的是，同一個值發生在不同的上下文環境中，可能不會被認為是離群值.當我們討論日志異常檢測任務時，“上下文”通常表示為日志文件所示上下文；而當我們討論時間序列異常檢測任務時，“上下文”則表示時間.因此，在網絡異常檢測中，日志異常、時序數據異常通常可視為上下文異常.

1.1 相關綜述工作

異常檢測一直以來都是一個備受關注的問題，不少異常檢測的綜述論文從不同角度對現有的異常檢測方法進行了總結與分析.文獻[22]將神經網絡異常檢測方法劃分為特征提取方法、正常數據表征方法、異常分值學習方法，并詳細介紹了這些方法解決的異常檢測問題中存在的挑戰.文獻[23]對時序數據檢測方法進行了綜述，并將這些方法根據變量的不同分類為單變量異常檢測與多變量檢測.文獻[24]則將網絡異常檢測方法劃分為基于距離的方法、基于密度的方法、基于軟閾值的方法.而文獻[25-26]與文獻[27]則分別對基于機器學習以及數據挖掘的異常檢測方法進行了綜述，并將它們根據具體實現算法的不同進行了歸類，如聚類分析、支持向量機、決策樹、貝葉斯網絡等.

盡管文獻[22-27]提出一系列的異常檢測綜述對現有的大部分異常檢測方法進行了歸類與整理，但它們大多是基于某一具體的異常檢測方法進行分類與總結.近期隨著稀疏表征技術的快速發展，得益于該技術較強的數據特征提取能力，基于低秩分解技術的異常檢測方法也越來越受到重視，因此，本文將對基于低秩分解的異常檢測方法進行綜述以及分類.

1.2 異常檢測方法原理以及分類

異常檢測的基本思想是通過算法將異常和正常區分出來，從距離、密度、概率統計這3個不同的角度來區分正常數據和異常數據.異常檢測算法可以分為3類，如表1所示：

Table 1 Classification Table of Traditional Anomaly Detection Methods表1 傳統異常檢測方法分類表

基于距離的異常檢測方法[28-32]是基于數據對象之間的距離計算來定義異常，具有清晰的幾何解釋.這類方法[31]于1998年被提出，通過計算比較數據與近鄰數據集合的距離來檢測異常數據，是最常用的異常檢測方法之一.其基本思想是正常數據點與其近鄰數據相近，而異常數據點則更遠[32].這類方法通常不需要數據標簽，適用于無監督異常檢測場景.其缺點主要包括計算復雜度高、異常距離閾值難以確定等.

基于密度的網絡異常檢測方法[33-36]，首先需要估算輸入空間的密度分布，然后將在低密度空間區域的數據對象定義為異常數據.基于局部離群因子(local outlier factor, LOF)作為一個經典算法[33,36]，通常為每一個數據賦值一個代表其鄰域密度的LOF值，當LOF值越大，則表示其鄰域密度越低，越有可能是異常數據.這類方法同樣不需要數據標簽，適用于無監督異常檢測場景.其缺點主要包括計算復雜度高、LOF閾值定義困難等.

基于概率統計的異常檢測方法[37-41]，最早由Barnett等人[41]提出，首先假設數據集服從某種分布(如正態分布、泊松分布及二項式分布等)或概率模型，然后通過判斷各數據點是否符合該分布/模型來實現異常檢測.例如，假設數據集服從一元正態分布，當數據點與均值差距大于3倍方差時，則認為該數據點為異常數據.這類方法基于數據分布能夠快速有效地找出異常數據，同時又能表示數據所包含的信息特征.其缺點主要包括可解釋性差、數據分布/模型難以確定、隨著數據特征維度的增加其異常檢測精度將降低等.

大量研究基于數據挖掘、機器學習、深度學習等技術實現異常檢測過程，由于數據挖掘與機器學習算法存在交叉與重疊，本文將異常檢測過程的實現方法分為2類，如表2所示：

Table 2 Implementation Methods and Specific Algorithms of Anomaly Detection Algorithms表2 異常檢測算法的實現方法與具體算法

盡管經過多年異常檢測方法的研究，很多檢測方法都實現了不錯的異常檢測效果.然而，大部分研究都是通過分析獨立的時序數據(例如，單鏈路流量數據[37]、關鍵性能指標(key performance indicator, KPI)數據[69-70]、日志/記錄[71-73]、數據包[74]、簡單網絡管理協議(simple network management protocol, SNMP)數據[1,75]等)來實現異常檢測.這些研究方法卻存在一些不可避免的缺陷[76]：

1) 通常需要學習網絡攻擊的先驗知識(prior knowledge)[77]或分析正常用戶的行為模式，因此，難以檢測新型異常、模仿正常用戶行為模式的攻擊.

2) 僅利用了網絡數據內部的時間相關性，而忽略了空間相關性，而許多異常行為常影響網絡中多條鏈路或路徑，并不會在單鏈路或路徑上明顯呈現，這就使得檢測并不準確.

3) 通常利用閾值判斷檢測數據是否為異常，卻無法定位異常發生的具體位置，這就使得算法在網絡管理的應用中存在局限性.

為了解決上述3個缺陷，Lakhina等人[12,78]提出使用流量矩陣作為數據源，并使用一種主成分分析(principal component analysis, PCA)[79]實現了基于低秩分解的全網(network wide)異常檢測模型.該模型利用網絡數據所蘊含的低秩性特征，通過從網絡監測數據分離低秩正常數據和異常數據，實現全網異常檢測.

基于低秩分解的全網異常檢測模型不僅利用多條鏈路流量數據中的時間相關性(temporal corre-lation)，而且同時整合了空間相關性(spatial corre-lation)，將高維的網絡流量數據矩陣映射到正常子空間與異常子空間，然后在異常子空間中檢測凸顯的異常行為模式.該模型作為一種無監督異常檢測模型，不需要學習任何網絡攻擊/異常的先驗知識以及網絡正常行為模式，同時充分利用了網絡數據中的時間-空間相關性.另外，通過分離所得異常數據通常能夠實現對網絡異常的定位.因此，該模型能夠很好地解決傳統異常檢測方法中存在的一系列局限性問題.

盡管，基于低秩分解的全網異常檢測模型相較于傳統的異常檢測方法具有一定的優勢性，卻依然存在不少挑戰.

1) 基于低秩分解的全網異常檢測模型關鍵在于從監測數據中提取正常數據，然而，異常數據通常嚴重影響正常數據的低秩性，進而影響正常數據的提取.因此，如何準確提取正常數據，并在進行正常數據提取過程中對異常數據進行有效約束，以減少異常數據對正常數據提取的影響，從而保證異常檢測精度，這成為一項挑戰.

2) 基于低秩分解的全網異常檢測模型通常需要使用低秩分解技術(如矩陣/張量分解)，然而，低秩分解過程通常是迭代執行過程，需要高昂的計算代價.這就降低了該模型的可拓展性，同時使其無法滿足在線網絡異常檢測的要求.因此，如何降低該模型的計算代價成為另一項挑戰.

為了更清晰地介紹各類基于低秩分解的全網異常檢測模型，本文首先在矩陣模型下對各類異常檢測方法，根據其對異常數據約束方法的不同進行分類，并介紹各類模型在計算代價以及求解方式上的變種與改進.然后，以同樣的方法對張量模型下的異常檢測方法進行了分類與總結.

2 基于低秩分解的異常檢測模型原理

2.1 網絡監測數據矩陣

為了研究基于低秩分解的全網異常檢測技術，通常可以將同一個網絡中所有源節點(origin)和目的節點(destination)對之間的性能數據(例如流量、吞吐量、時延等)建模成一個矩陣.如圖1所示，矩陣中的行代表源節點-目的節點對(OD對),而矩陣中的列代表時間(time)，矩陣中元素則代表對應時刻下OD對之間監測的網絡性能數據.根據所選擇的網絡節點類型的不同，可以定義為不同粒度的矩陣，例如鏈路級、路由級、PoP(point of presence)級流量矩陣[80-81].

Fig. 1 Network monitoring data matrix圖1 網絡監測數據矩陣

2.2 網絡數據的低秩性分析

基于低秩分解的網絡異常檢測算法實現的前提條件是將正常網絡性能數據建模為低秩數據，因此，本節將首先給出網絡測量數據的低秩性驗證.

用戶的網絡行為通常具有時間穩定性以及空間相關性.文獻[82]闡述并證明了網絡性能數據的時間相關性、空間相關性、天周期性等特征.如圖2所示，圖2(a)表示相鄰時刻之間的網絡性能數據之差的累計概率分布，圖2(b)表示不同OD對中的網絡性能數據的相關系數，圖2(c)表示相鄰天之間的網絡性能數據之差的累計概率分布.

通過分析圖2(a)發現，網絡性能數據在相鄰時刻之間十分相似.圖2(c)則顯示相鄰天之間的網絡數據十分相似.因此，網絡性能數據通常具有較強的時間穩定性，這就使得網絡性能數據在時間維度(例如圖1中的時間)具有低秩性的特點.同樣地，通過分析圖2(b)發現不同OD對之間的網絡數據向量具有較強的相關性，因此，網絡數據同樣具有較強的空間相關性，從而使得網絡數據在空間維度(例如圖1中的源節點-目的節點對)具有低秩性的特點.

Fig. 2 The temporal correlation, spatial correlation, and day periodic of network data圖2 網絡數據的時間相關性、空間相關性、天周期性

為了進一步驗證網絡數據的低秩性，我們將網絡性能數據按照圖1所示建模為矩陣X，并對X進行奇異值分解(singular value decomposition, SVD)，得到[X]=UΣVT.其中，Σ為對角矩陣，Σ=diag(σ1,σ2,…,σR,0,…,0)，該矩陣的對角線上元素通常為從大到小排列的結果.那么，矩陣X的秩則為矩陣Σ中非零元素的個數.值得注意的是，在實際的應用中，由于網絡的監測數據為連續數據存在一定的測量噪音，因此，監測數據通常并不滿足嚴格意義的低秩.根據主成分分析算法的定義，奇異值越大，其所代表的主成分越重要，其前k個奇異值所占比重幾乎等于所有奇異值之和時，則可以認為這個矩陣為近似低秩矩陣，并滿足低秩性的特點.因此，通常利用指標來判斷是否為近似低秩矩陣.

圖3表示Abilene和GEANT數據集的低秩性驗證結果.通過分析可以發現，少數幾個奇異值基本占據了所有奇異值的比重，因此，得以驗證網絡性能數據具有低秩性特征.

Fig. 3 The diagram of low rank of network data圖3 網絡數據的低秩性示意圖

Fig. 4 Network anomaly detection based on low-rank decomposition圖4 基于低秩分解的網絡異常檢測方法

文獻[83]同樣在開源網絡流量數據集Abilene與GEANT上開展了實驗，并驗證了網絡數據的低秩性.另外，大量研究[82-87]利用網絡數據的低秩性來填充網絡缺失數據.而基于低秩分解的網絡異常檢測方法則通常利用網絡性能數據的低秩性以及低秩分解技術，將高維的網絡性能數據映射到正常子空間與異常子空間，其中正常子空間即為低秩子空間.

3 基于矩陣模型的異常檢測方法

由于網絡性能數據中具有第2節中分析的低秩性特征，因此，基于低秩分解的數據分離模型[88]提出利用網絡數據內部的低秩性特征，結合低秩分解技術將監測所得原始數據分離成為正常數據與異常數據.如圖4所示，矩陣X為網絡監測數據矩陣，利用低秩分解技術可以將其分解為正常數據矩陣M與異常數據矩陣E.根據2.2節分析，正常數據具有低秩性的特點，網絡攻擊代價高的問題以及網絡設備故障的稀疏性問題使得異常數據通常具有稀疏性的特點.因此，異常數據矩陣E通常為稀疏矩陣，通過基于低秩分解的數據分離模型獲得稀疏異常數據矩陣E后，即可對網絡數據中是否存在異常進行判定，同時根據矩陣中非零元素所處位置可進行異常定位.

為了實現圖4所示的數據分離，基于低秩分解的異常檢測模型通常將優化目標函數表示為：

(1)

其中,X為原始的網絡監測數據，M為正常數據矩陣，E為稀疏異常數據矩陣，rank(M)≤R表示正常數據的低秩約束，而ρ(E)表示異常數據約束條件.由于基于低秩分解的異常檢測模型關鍵在于從監測數據中提取正常數據，然而，異常數據通常嚴重影響正常數據的低秩性，進而影響正常數據的提取，并最終影響異常檢測的精度.因此，如何準確地提取正常數據并有效約束異常數據，成為異常檢測的關鍵一環.

本節將分類介紹各類異常檢測方法，如表3所示.根據正常數據的提取方法與異常數據約束條件的不同，將基于低秩分解的異常檢測方法分為基于PCA的異常檢測方法、基于魯棒的主成分分析方法(robust principal component analysis, RPCA)的異常檢測方法、基于直接矩陣分解的異常檢測方法，以及其他異常檢測方法.然后介紹各類方法在計算代價以及求解方式上的優化與改進.

Table 3 Classification of Anomaly Detection Methods Based on Low-Rank Decomposition Under Matrix Model表3 矩陣模型下基于低秩分解的異常檢測方法分類

3.1 基于PCA的異常檢測方法

Lakhina等人[12,78]提出將網絡流量數據建模為矩陣，并使用PCA算法來實現全網異常檢測.該算法利用低秩分解技術，將正常數據M從原始監測數據X中提取出來，如圖4所示.

為了實現正常數據的提取，通常對原始監測數據使用PCA[79]求解式(2)來獲得網絡監測數據的低秩子空間(UR(UR)T)，并將原始數據投影至低秩子空間，得到正常數據：M=UR(UR)TX.

(2)

為了求解式(2)，研究[12,78]首先計算數據矩陣X的協方差矩陣Cov(X)，然后通過奇異值分解方法得到協方差矩陣的奇異值{σ1,σ2,…,σn}與特征矩陣U，并選擇R個最大的奇異值所對應的特征向量(主成分)構成特征矩陣UR，最后將原始數據矩陣X投影到特征矩陣所構成的空間P=UR(UR)T上，從而得到正常數據M.

通過PCA完成正常數據的提取后，為了實現異常檢測，基于PCA的異常檢測方法又可以細分為基于子空間殘差分析的異常檢測方法與基于主成分方向變化的異常檢測方法兩大類，接下來講具體介紹這2類方法.

3.1.1 基于子空間殘差分析的異常檢測方法

基于子空間殘差分析的異常檢測方法[12,78,89-90]，在獲得低秩的正常數據M后，為了能夠準確檢測并定位異常，直接計算原始數據與正常數據之間的殘差子空間(X-M)，并對殘差子空間進行閾值判斷.當殘差大于閾值時，則定義該位置為異常數據，否則為正常數據.

下面將介紹2種閾值設計方案[12,78]，首先定義殘差子空間中各位置的平方預測誤差(squared prediction error,SPE)為

SPE=(xij-mij)2,

(3)

其中,xij與mij分別表示原始監測矩陣與正常數據陣中第i行、第j列的元素值.

基于Q統計量的方法，定義閾值為

(4)

(5)

其中0≤α≤1是歷史數據的相對權重，亦稱為平滑指數.

(6)

另一方面，由于基于殘差分析的異常檢測方法需要獲得正常子空間的前提是對原始數據進行低秩分解，而這一過程計算代價非常高.文獻[91-92]為了讓這一類方法更適用于大規模網絡的異常檢測任務，提出了一種分布式的主成分分析方法，將原本的中心化異常檢測轉變為分布式異常檢測.這種方法為每一個網絡監測節點設置一個監測過濾窗口，當且僅當該監測節點中新來臨的數據不屬于該監測過濾窗口內，才將該數據向中心節點上傳于更新.而中心節點則根據各監測節點上傳的數據進行參數更新，而不是通過精確的全局數據進行更新，并在更新后將結果下發到各個監測節點.這就使得計算代價大大降低，同時實現了分布式的異常檢測.

基于子空間殘差分析的異常檢測方法通常針對全網所有時刻的性能數據進行設計，并通過將原始數據分為正常子空間與異常子空間進行異常檢測.在異常子空間內，我們可以判斷是否存在異常數據，同時可以通過異?？臻g定位異常數據所在具體時刻與位置，如圖4所示，稀疏矩陣E中第2行第4列的元素，表示第2個OD對在第4個時刻發生了異常.因此這些方法適合部署于網絡數據中心的離線異常檢測與定位任務中.

3.1.2 基于主成分方向變化的異常檢測方法

基于主成分方向變化分析的異常檢測方法[95-96]不同于3.1.1節的殘差分析方法，這一類方法并不需要計算原始數據與正常數據之間的殘差，而僅需對比前后2時刻下PCA所求主成分的變化來檢測異常.

Fig. 5 Diagram of anomaly detection method based on principal component direction change analysis[95]圖5 基于主成分方向變化分析的異常檢測方法[95]

PCA作為一種降維方法，通常以最小化各個數據樣本到主成分之間的距離之和為目的，進行優化求解.以圖5為例，降維后的主成分方向表示為圖5(a)中左側圖的實線箭頭所示的新坐標軸，而原始坐標軸則代表原始空間.圖5中的小圓圈則表示歷史數據樣例，當新的數據樣例到來時，將在不同程度上影響主成分的方向，尤其是當新來的數據為異常數據(方塊)時，由于新數據嚴重偏離正常數據，通常會使得主成分的方向將發生巨大的偏移(如圖5(a)的右側圖所示)；反之，當新來的數據為正常數據(圓圈)時，主成分的方向則并不會發生較大偏移(如圖5(b)右側圖所示).正是利用PCA的這一特性，基于主成分方向變化的異常檢測方法通常適用于判別新來臨的數據是否為異常數據.

由于傳統的PCA通常處理向量類型數據，在實際網絡的異常檢測任務中，網絡數據往往建模成為矩陣模型，傳統的PCA需要將矩陣模型向量化，以便檢查當前時刻是否存在異常.文獻[97]提出，蘊含在數據內部的空間相關性將因為向量化過程出現丟失，因此，文獻[97]提出使用雙向2維PCA來計算網絡數據矩陣的主成分，并利用所求主成分來進行異常檢測.

首先，將歷史的網絡數據通過雙向2維PCA，計算得到矩陣行列2個空間的歷史主成分uhistory，vhistory.如圖6所示，通過雙向2維主成分分析方法，原始數據從3維降到2維與1維.時刻t下的主成分由u1(t),u2(t)與v1(t)組成，其中u1(t),u2(t)為行空間主成分，v1(t)為列空間主成分；而時刻t+1的主成分由u1(t+1),u2(t+1)與v1(t+1)組成.

Fig. 6 Diagram of anomaly detection method based on two-dimensional principal component direction change analysis圖6 2維主成分方向變化分析的異常檢測方法

為了計算主成分方向的偏移，將行列2個空間的主成分進行拼接，然后通過式(7)計算前后2個時刻的主成分方向之間的夾角來定義其偏移量的大小.

(7)

其中,Mt=[Ut,Vt]，Mt+1=[Ut+1,Vt+1]，Vec()為矩陣向量化.最后，通過歷史數據的預訓練或者專家經驗來設定閾值，并與Cosine進行比較，以判斷數據是否為異?；蚴欠翊嬖诋惓?

盡管文獻[95-96]所提方法可以準確地檢測到一些偏離正常模式較大的異常數據，但隨著歷史數據的不斷積累，新來臨的異常數據對主成分方向的影響將越來越小.為了維持新來臨數據對主成分方向的影響，文獻[95,97]提出一種數據過采樣(over-sampling)的方法，將新來臨的數據復制α×T遍，并更新主成分unew.其中，α為過采樣倍數，一般設置α=0.1，T為歷史時刻數.另外，這一方法在計算主成分時需要利用奇異值分解或者特征值分解的方法，通常需要高昂的計算代價.為了實現在線網絡異常檢測，文獻[95,97-100]提出了增量更新的過程，這些更新方法不需要重復地進行主成分計算，不需要保存歷史數據，而僅需利用新來臨數據直接更新主成分方向.

基于主成分方向變化的異常檢測方法通常利用歷史時刻的網絡性能數據訓練主成分，并對新時刻的網絡性能數據進行實時分析，通?？梢耘袛鄶祿楫惓祿?，而無法對異常數據所在位置與時刻進行定位，因此適合部署于網絡數據中心或小型網絡設備的在線異常檢測與告警任務中.

3.2 基于RPCA的異常檢測方法

基于PCA的異常檢測方法，在異常檢測過程并沒有對異常數據進行約束，而僅使用Frobenius范數約束所得剩余殘差來表征異常數據的分布.Frobenius范數為數據內部各項元素的絕對值平方的總和，即約束數據內部的數值大小，當異常數據符合較小的高斯分布時，異常檢測效果可以得到保證.然而，當異常數據中存在較大值(尖銳)時，會在不經意間污染主成分分析的正常子空間(即網絡性能數據的低秩性特征)，從而扭曲正常的定義[101]，并最終影響異常檢測的精度.

為了解決該問題，并保證異常檢測的精度，需要對異常數據進行有效約束.由于網絡異常數據具有稀疏性的特點，因此，通常使用L0范數來約束異常數據的分布:

(8)

然而，針對L0范數與rank()的約束求解過程比較困難，為此，基于RPCA的異常檢測方法[88,102-106]提出對L0范數與rank()問題進行松弛化處理，使用核范數代替rank()約束來提取正常數據，并使用L0范數的最優凸近似(L1范數)來約束異常數據:

(9)

其中，L1范數表示數據內部的每個元素絕對值之和，這就使得異常檢測方法可以在異常數據中存在較大值時，保證網絡異常檢測的精度.

大量文獻提出求解式(9)的方法.例如，基于標準內點法(standard interior point methods)[107]被率先提出來求解該問題，但是由于該方法需要非常高的計算代價，因此并不適合用于大規模矩陣處理；為了讓算法更具可擴展性，文獻[108]提出了奇異值閾值算法(singular value thresholding, SVT)來處理核范數約束問題；文獻[109]所提的迭代閾值方法(iterative thresholding, IT)能夠實現可擴展性更高的優化方案，但其收斂速度相對緩慢；文獻[110]提出了包括加速近端梯度方法(accelerated proximal gradient, APG)與梯度上升方法(gradient-ascent)，然而這2種算法在實際應用中依然出現了收斂緩慢的問題；文獻[111]提出2種增廣拉格朗日方法，其中一種為精確增廣拉格朗日(exact augmented Lagrange multipliers)能夠實現Q-linear的收斂速度，另一種非精確增廣拉格朗日(inexact augmented Lagrange multipliers)方法收斂速度與精確增廣拉格朗日方法相似，卻在低秩分解問題上實現了計算代價的優化，相較于加速近端梯度方法能夠提高近5倍的計算速度，然而這2種方法將低秩約束問題與稀疏異常約束問題合并在一起進行優化，而沒有將它們作為可分離的2個子問題進行考慮，依然存在缺陷.

為此，文獻[112-114]提出了一種交替方向乘子法(alternating direction method of multipliers, ADMM),通過中間變量將2個子問題進行分離求解，從而獲得更好的異常檢測效果.通過引入中間變量Z將式(10)轉化為

(10)

其中中間變量Z為乘子的線性約束，β>0為違反線性約束的懲罰參數，〈·,·〉為標準的內積函數.

最后，各個參數更新為：

(11)

(12)

Zk+1=Zk-β(X-Mk+1-Ek+1),

(13)

經過對式(9)的研究，不少變種方法被應用于數據分離，并取得了不錯的效果.例如，文獻[115]提出了一種固定秩的方法，將低秩矩陣的秩固定為r，并提出優化目標函數：

(14)

而文獻[116]提出了一種增量秩的方法來改進式(14)的固定秩的方法，這種方法通過逐步增加秩的大小來進行啟發式學習，以學習到最優秩，從而實現更高的異常檢測精度.

文獻[117]提出了一種歸納方法：

(15)

其中矩陣P為低秩投影矩陣，這一優化問題則可通過非精確的增廣拉格朗日方法[111]進行求解.

文獻[118]提出了使用2維PCA(2D-PCA)來實現異常檢測，該方法使用2維PCA替代奇異值分解方法，以實現更多信息的提取從而提高異常檢測精度：

(16)

另外，由于網絡數據是以流數據的形式源源不斷到來的，為了能夠實現實時的網絡異常檢測，文獻[119-124]提出了增量更新的方法，這些方法僅需利用新來臨的數據更新優化方法中的對應參數，而不需要利用整體數據進行重復計算.這些方法一方面降低了優化算法的計算代價，另一方面降低算法對存儲空間的需求，可以使得基于魯棒的主成分分析方法的異常檢測算法更適用于簡單網絡設備以及在線網絡異常檢測過程.

基于RPCA的異常檢測方法通常針對所有時刻的全網性能數據進行設計，并利用數據分離的方法實現異常檢測，因此適合部署于網絡數據中心的離線異常檢測與定位任務中.其中文獻[119-124]所提的改進方案，由于在計算復雜度上進行了有效改進，因此同樣適合部署于在線異常檢測與定位任務中.

3.3 基于直接矩陣分解的異常檢測方法

盡管基于RPCA的異常檢測方法被證明對于尖銳的異常數據更具魯棒性，卻利用凸松弛技術來實現對原始約束問題的求解，這就使得異常檢測精度仍然較低.原始約束問題為：

(17)

為了直接求解式(17)的原始問題，文獻[125]提出了基于直接矩陣分解的異常檢測方法，該方法使用塊坐標下降(block coordinate descent)方法來求解，將原始問題的求解過程轉化為迭代求解2個子問題.

低秩估計子問題：

(18)

異常檢測子問題：

(19)

異常檢測子問題求解過程為：首先計算原始矩陣X與低秩估計子問題的解M之間的殘差S；然后將殘差矩陣S中的元素進行降序排序，保留前e個元素，其余位置的元素都置為0，最終得到稀疏異常矩陣E.

文獻[126-128]提出一種輕量級的矩陣分解方法，該方法通過實驗分析發現基于L0范數的異常檢測方法在實際應用過程中呈現一種“異常位置快速收斂”的性質.這種性質使得稀疏異常矩陣E的非零元素所在位置能夠快速確定下來，在迭代過程很少發生改變，甚至不改變，而唯一發生變化的是，稀疏異常矩陣中非零元素的大小.正是利用這一性質，所提輕量級的矩陣分解方法可以通過重用上一輪迭代的低秩估計結果，從而降低算法計算代價，以適應更大規模的數據處理.

基于直接矩陣分解的異常檢測方法與基于RPCA的異常檢測方法類似，利用數據分離的方法實現異常檢測，因此適合部署于網絡數據中心的離線異常檢測與定位任務中.

3.4 其他異常檢測方法

除了3.1～3.3節所述的3種不同約束的異常檢測方法，少數研究提出了一些特殊范數約束[125-126,128-130]，這些范數約束在不同角度上加強了對異常數據部分的約束，從而提高異常檢測算法的精度.

文獻[130]提出了card范數來約束異常數據的稀疏性：

(20)

其中，card范數本質上與L0范數一致，該范數通過保留異常矩陣中最大的ε個元素來實現稀疏性約束.

Fig. 7 Structured anomaly model圖7 結構化異常模型

在實際網絡中，在數據遭到持續污染的情況下會造成矩陣行中多個元素被污染，如圖7所示.當第5個位置的數據遭受持續不斷的污染時，第5行中所有元素都為異常數據，為了解決這種結構化異常的問題，文獻[125-126,128]提出了一種L2,0范數來約束異常數據.

(21)

而為了求解這種約束問題，首先計算原始矩陣X與低秩估計子問題的解M之間的殘差S，然后對殘差矩陣S的每一行求和，并將每一行的和進行排序，保留最大的ε行，其余行則歸0.

如文獻[131]所述，文獻[88]所提的L1范數與核范數并不是嚴格的(tight)約束，這就使得所求解并不一定是可信解.為此提出了另外的非凸松弛范數(如式(22)所示)，使用Schatten-p范數來代替核范數約束，使用lq范數來代替L1范數約束，以此加強對正常數據的低秩約束以及異常數據的稀疏約束.

(22)

式(22)同樣可以被表達為：

(23)

其中σi(M)表示矩陣M的第i奇異值.該優化問題則通過近端迭代重加權算法(proximal iteratively reweighted algorithm, PIRA)進行求解.

其他異常檢測方法利用數據分離的方法實現異常檢測，因此同樣適合部署于網絡數據中心的離線異常檢測與定位任務中.另外，由于對異常數據的不同約束，文獻[125-126,128]所提出的使用L2,0范數來約束異常數據的方案，可用于結構化的異常檢測與定位任務中.

4 基于張量模型的異常檢測方法

盡管第3節所述的異常檢測方法取得了不錯的效果，最近一些研究[82]卻表明網絡監測數據建模成為矩陣的表征形式，丟失了蘊含在數據內部的高階結構化信息，難以表征多模式數據的多維本質.而張量模型作為矩陣模型向多維的擴展，可以表征多模式數據的多維本質，張量模型不再局限于數據內比較簡單的2維線性關系，而是將多維放到一起綜合考慮，探索多因子、多成分、多線性關系，具有重要的學術價值和應用前景.其已經開始被應用到計量化學、信號處理、機器學習、計算機視覺、認知科學等科學領域[132-135].因此，一部分研究為了充分挖掘網絡性能數據內部蘊含的高階結構化特征，提出將網絡監測數據建模成為張量模型.

為了能夠更簡單、清晰地表達，本文將使用3維張量作為例子進行描述，在實際應用中，張量模型的維度可以大于等于3維.如圖8(a)所示，3維張量為長方體的模型，其3個維度分別表示源節點、目的節點、時間，其中元素表示對應時刻下OD對之間監測的網絡性能數據；在一些研究中3維張量模型則表現為圖8(b)的形式，其3個維度分別表示為節點-目的節點對、天、時間，其中元素則表示為某一OD對在某天的某一時刻下監測的網絡性能數據.

Fig. 8 Network monitoring data tensor圖8 網絡監測數據張量

正是利用張量模型，大量研究[136-137]通過將基于矩陣模型的算法拓展至張量模型X′，從而實現了更高的異常檢測精度.接下來，本節將根據對異常數據的不同約束條件，分類介紹各種異常檢測方法并總結分析.

與矩陣模型下的PCA異常檢測方法類似，文獻[138]的方法更適合部署于網絡數據中心的離線異常檢測與定位任務中.

Fig. 9 Origin-destination-subjects tensor model圖9 源節點-目的節點-對象張量模型

Fig. 10 HOOI tensor decomposition model圖10 HOOI張量分解模型

通過分析不同時刻下因子矩陣的變化來判斷該時刻是否存在異常，由于不同時刻下的網絡接入節點個數不一定相同，使得因子矩陣U1,U2的規模在不同時刻下也不同，也就不能直接使用歐氏距離進行變化的測量，而是使用Grassmann距離[141]來計算：

(24)

其中,ζ為各因子矩陣行數的最小值，而θk(Ui(t),Ui(t+1))則表示因子矩陣Ui(t),Ui(t+1)的Grassmann距離.最后，通過判斷該距離是否大于閾值μd+2σd來確定是否為異常，當距離大于該閾值時該時刻下存在異常數據，否則為正常數據.其中

由于文獻[140]是基于因子矩陣的差異來實現異常檢測，而非數據分離，且HOOI方法的計算復雜度較高.因此該方案更適合部署于網絡數據中心的離線異常檢測與告警任務中.

相似地，文獻[140]將網絡監測數據建模成如圖11所示的2個張量模型，其中一個為網絡流數據構成，另一個為網絡拓撲數據構成，張量模型的3個維度分別為源節點、目的節點和時間.

Fig. 11 Network flow tensor model and topological tensor model圖11 網絡流張量模型與拓撲張量模型

(25)

其中,μ為均值，Cov(X)為協方差矩陣.

同樣地，與矩陣模型下基于RPCA的異常檢測方法類似，文獻[102,142]將數據建模成為高階張量模型X′,并同樣使用核范數與L1范數約束正常數據與異常數據，從而得到優化問題：

(26)

為了求解式(26)的問題，同樣采用了增廣拉格朗日的方法引入中間變量進行求解.不同的是為了求解張量模型的核范數約束問題，文獻[143]首先將張量模型按照各個維度展開，并針對各個維度展開下的矩陣進行奇異值分解，從而得到各自的低秩估計.而文獻[102,144]則同樣使用ADMM方法進行求解，不同的是,它們結合T-SVD[145]算法進行式(26)的更新.

文獻[140,146]同樣提出將數據建模成為張量模型，卻分別利用CP分解方法和Tucker分解方法來求解張量模型的核范數約束問題，并使用軟閾值方法，在更新異常數據張量E時，將張量中小于閾值的元素歸為0，以實現稀疏化約束.

與矩陣模型下基于直接矩陣分解方法的異常檢測方法類似，文獻[147]將網絡流量數據建模為張量X′(如圖8(b)所示)，并提出基于L0范數約束的張量恢復算法(式(27)所示)，通過學習網絡數據中的高階結構化信息，從而實現更高精度的異常檢測.

(27)

其中rank(M′)≤rank(r1,r2,r3)表示該張量在3個不同維度下所形成展開矩陣的秩約束，而E′為L0范數約束的稀疏異常張量.同樣地，利用塊坐標下降方法將該問題轉化為低秩估計子問題與異常檢測子問題.不同的是，文獻[147]為了快速求解式(27)的多元秩約束的低秩估計子問題以滿足大規模網絡數據處理的需求，提出了一種連續截斷的張量分解方法.

文獻[147]所提方法使用數據分離的方法實現異常檢測，然而張量分解算法的計算復雜度通常較高.因此，這一類方法更適合部署于網絡數據中心的離線異常檢測與定位任務中.

盡管文獻[147]所提方法能夠加速異常檢測過程，卻仍然無法滿足在線的網絡異常檢測任務.為此，文獻[76]提出了一種在線網絡異常檢測模型，如圖12所示.首先將網絡流量數據建模成為張量模型，然后定義一個滑動窗口，當新時刻數據來臨時，刪除窗口內最老的數據，從而保證數據量的同時維持數據的有效性.

Fig. 12 Online network anomaly detection model圖12 在線網絡異常檢測模型

在新數據來臨時，為了能夠及時檢測并報告異常的位置，文獻[76]提出了一種基于CP分解重用的技術，僅需存儲少數小規模中間變量，便能夠利用新來臨數據更新低秩估計子問題中所求解.根據文獻[76]所述，該方法能夠實現與文獻[147]相似的檢測精度，卻能夠滿足在線網絡異常檢測的計算速度要求.

盡管文獻[76]所提方案使用數據分離的方法實現異常檢測，但是得益于其模型的設計與計算復雜度的大幅度降低，該方法適合部署于網絡數據中心的在線異常檢測與定位任務中.

根據文獻[148]所述，盡管張量模型能夠充分網絡數據中的高階結構化信息，卻僅考慮了數據內部的線性特征(低秩)，而忽略了可能出現的非線性特征.對于網絡數據，源節點域、目的節點域和時間域之間除了線性相關性外，還存在一些非線性鄰近信息[84-85,148].例如，同一網絡拓撲在某個特定時間(即辦公時間、休息時間)應具有相似的流量數據，因此網絡性能數據應包含時間鄰近信息.而根據節點扮演的角色，網絡中的節點可以分為多種不同的類別，例如正常的終端用戶和功能強大的服務器.相同類別的節點可能具有相似的網絡訪問模式，并產生相似的流量負載，從而導致流量數據具有源節點鄰近性和目的節點鄰近性.因此，文獻[148]提出了一種基于流形學習的方法來將這種非線性特征融入異常檢測問題中，并提出優化目標函數：

(28)

其中Otime,Oori,Odes分別表示與時間鄰近度、源節點鄰近度和目的節點鄰近度相對應的約束.這3個鄰近度分別表示為

(29)

(30)

(31)

其中A,B,C為CP分解中因子矩陣，而La,Lb,Lc分別是時間鄰居圖、源節點鄰居圖、目的節點鄰居圖的拉普拉斯矩陣.

5 方法比較

網絡空間安全已經成為國家安全的重要組成部分，異常檢測成為網絡管理的重要部分之一.而數據挖掘、機器學習、深度學習等領域的快速發展為網絡異常檢測提供了堅實的理論依據.基于低秩分解的網絡異常檢測作為一種無監督的異常檢測方法，吸引了越來越多的學者們進行深入研究.然而，不同的方法由于約束條件的不同和優化求解方式的不同，達到異常檢測精度與計算速度也不同.本節將對基于低秩分解的網絡異常檢測方法進行了總結以及優缺點的分析，如表4所示：

Table 4 Classification, Summary, Advantages and Disadvantages of Anomaly Detection Methods Based on Low-Rank Decomposition表4 基于低秩分解的異常檢測方法分類、總結、優缺點分析

6 挑戰與展望

近年來，盡管基于低秩分解的網絡異常檢測受到了越來越多學者的關注，各種新的研究方法與成果不斷涌現，但當前的異常檢測研究還處于學術研究的階段，基于低秩分解的網絡異常檢測仍然面臨著諸多挑戰.例如，異常檢測方法對于網絡特性與領域知識的融合問題，異常檢測算法與模型的適應性問題，以及異常檢測的后續任務研究問題.這些挑戰將推動這一研究方向往更深入的方向不斷發展.總的來說，未來的研究方向將主要包括3個方面：

1) 網絡特性與領域知識的融合問題.現有基于低秩分解的異常檢測模型通常僅約束了正常網絡數據的低秩性與異常數據的稀疏性等特點，缺乏對實際網絡環境中存在的特征約束，例如網絡連通性約束、網絡帶寬約束、網絡流量約束.而這些網絡特有的約束通常能夠幫助網絡管理中心判斷數據的正常與否，以及協助網絡數據輪廓、特征、模型的構造.另外，網絡異常檢測模型可以分析與利用的計算機網絡領域知識越來越豐富，例如網絡拓撲信息、網絡設備信息等.

然而，網絡特性與領域知識通常并不能表示為歐氏空間數據，難以融入現有的方法.因此，如何設計算法模型，將計算機網絡特性與領域知識融入基于低秩分解的異常檢測模型中，并提出對應的求解方法，以提高異常檢測精度是未來的研究方向之一.

2) 異常檢測算法與模型的適應性問題.現有的算法與模型在數據與設備上存在一系列適應性問題.例如，基于低秩分解的異常檢測方法通常建立在數據的完整性上，當數據存在大量缺失時，其異常檢測的精度會遭到較大的影響.一方面，完整的網絡數據采集代價較大，另一方面，數據在傳輸過程中往往會存在不可避免的丟失，所以網絡數據通常會存在缺失的問題.而對存在缺失的網絡數據環境進行異常檢測充滿了挑戰.因此，如何設計算法在數據缺失的情況下準確分離正常數據與異常數據，從而保證異常檢測精度，將會是未來的研究方向之一.

另外，在實際網絡中，網絡設備的存儲代價與計算代價有限，現有的基于低秩分解的異常檢測算法大多針對網絡監控中心設計，需要較高的計算以及存儲能力.因此，如何將現有算法模型進行壓縮，而不損失其異常檢測精度，以保證簡單網絡設備能夠進行分布式的異常檢測，減少對網絡監控中心的依賴，將會是未來的研究方向之一.

3) 基于異常檢測的預測分析與根因分析問題.現有的網絡異常檢測方法通過分析測量到的網絡數據來實現，卻無法對網絡異常進行有效預測.在網絡管理中，如何對網絡異常進行預測，并根據預測結果進行事先診斷與預防十分重要.因此，如何通過對歷史異常數據的分析，來預測未來發生異常的位置以及時間，是未來的研究方向之一.

另外，在實際的網絡管理場景中，通過基于低秩分解的網絡異常檢測方法可以分離得到稀疏異常數據.盡管可以通過稀疏異常數據進行異常定位與檢測，卻無法進行進一步的異常根因溯源以及有效進行恢復與管理.因此，如何通過分析發生異常的種類、分布以及時間來確定發生異常的根因，是未來的研究方向之一.

作者貢獻聲明：李曉燦負責論文的撰寫與修改；謝鯤負責論文結構設計與指導，以及論文部分章節的修改；張大方負責各方法的整理與校對，以及論文修訂；謝高崗負責部分章節內容的撰寫與修改.