李曉燦 謝 鯤 張大方 謝高崗

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

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

1 研究背景

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

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

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

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

1.1 相關(guān)綜述工作

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

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

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

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

Table 1 Classification Table of Traditional Anomaly Detection Methods表1 傳統(tǒng)異常檢測方法分類表

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

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

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

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

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

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

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

2) 僅利用了網(wǎng)絡(luò)數(shù)據(jù)內(nèi)部的時間相關(guān)性，而忽略了空間相關(guān)性，而許多異常行為常影響網(wǎng)絡(luò)中多條鏈路或路徑，并不會在單鏈路或路徑上明顯呈現(xiàn)，這就使得檢測并不準確.

3) 通常利用閾值判斷檢測數(shù)據(jù)是否為異常，卻無法定位異常發(fā)生的具體位置，這就使得算法在網(wǎng)絡(luò)管理的應(yīng)用中存在局限性.

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

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

盡管，基于低秩分解的全網(wǎng)異常檢測模型相較于傳統(tǒng)的異常檢測方法具有一定的優(yōu)勢性，卻依然存在不少挑戰(zhàn).

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

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

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

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

2.1 網(wǎng)絡(luò)監(jiān)測數(shù)據(jù)矩陣

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

Fig. 1 Network monitoring data matrix圖1 網(wǎng)絡(luò)監(jiān)測數(shù)據(jù)矩陣

2.2 網(wǎng)絡(luò)數(shù)據(jù)的低秩性分析

基于低秩分解的網(wǎng)絡(luò)異常檢測算法實現(xiàn)的前提條件是將正常網(wǎng)絡(luò)性能數(shù)據(jù)建模為低秩數(shù)據(jù)，因此，本節(jié)將首先給出網(wǎng)絡(luò)測量數(shù)據(jù)的低秩性驗證.

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

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

Fig. 2 The temporal correlation, spatial correlation, and day periodic of network data圖2 網(wǎng)絡(luò)數(shù)據(jù)的時間相關(guān)性、空間相關(guān)性、天周期性

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

圖3表示Abilene和GEANT數(shù)據(jù)集的低秩性驗證結(jié)果.通過分析可以發(fā)現(xiàn)，少數(shù)幾個奇異值基本占據(jù)了所有奇異值的比重，因此，得以驗證網(wǎng)絡(luò)性能數(shù)據(jù)具有低秩性特征.

Fig. 3 The diagram of low rank of network data圖3 網(wǎng)絡(luò)數(shù)據(jù)的低秩性示意圖

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

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

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

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

為了實現(xiàn)圖4所示的數(shù)據(jù)分離，基于低秩分解的異常檢測模型通常將優(yōu)化目標(biāo)函數(shù)表示為：

(1)

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

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

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

3.1 基于PCA的異常檢測方法

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

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

(2)

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

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

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

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

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

SPE=(xij-mij)2,

(3)

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

基于Q統(tǒng)計量的方法，定義閾值為

(4)

(5)

其中0≤α≤1是歷史數(shù)據(jù)的相對權(quán)重，亦稱為平滑指數(shù).

(6)

另一方面，由于基于殘差分析的異常檢測方法需要獲得正常子空間的前提是對原始數(shù)據(jù)進行低秩分解，而這一過程計算代價非常高.文獻[91-92]為了讓這一類方法更適用于大規(guī)模網(wǎng)絡(luò)的異常檢測任務(wù)，提出了一種分布式的主成分分析方法，將原本的中心化異常檢測轉(zhuǎn)變?yōu)榉植际疆惓z測.這種方法為每一個網(wǎng)絡(luò)監(jiān)測節(jié)點設(shè)置一個監(jiān)測過濾窗口，當(dāng)且僅當(dāng)該監(jiān)測節(jié)點中新來臨的數(shù)據(jù)不屬于該監(jiān)測過濾窗口內(nèi)，才將該數(shù)據(jù)向中心節(jié)點上傳于更新.而中心節(jié)點則根據(jù)各監(jiān)測節(jié)點上傳的數(shù)據(jù)進行參數(shù)更新，而不是通過精確的全局數(shù)據(jù)進行更新，并在更新后將結(jié)果下發(fā)到各個監(jiān)測節(jié)點.這就使得計算代價大大降低，同時實現(xiàn)了分布式的異常檢測.

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

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

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

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

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

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

首先，將歷史的網(wǎng)絡(luò)數(shù)據(jù)通過雙向2維PCA，計算得到矩陣行列2個空間的歷史主成分uhistory，vhistory.如圖6所示，通過雙向2維主成分分析方法，原始數(shù)據(jù)從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()為矩陣向量化.最后，通過歷史數(shù)據(jù)的預(yù)訓(xùn)練或者專家經(jīng)驗來設(shè)定閾值，并與Cosine進行比較，以判斷數(shù)據(jù)是否為異?；蚴欠翊嬖诋惓?

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

基于主成分方向變化的異常檢測方法通常利用歷史時刻的網(wǎng)絡(luò)性能數(shù)據(jù)訓(xùn)練主成分，并對新時刻的網(wǎng)絡(luò)性能數(shù)據(jù)進行實時分析，通常可以判斷數(shù)據(jù)為異常數(shù)據(jù)，而無法對異常數(shù)據(jù)所在位置與時刻進行定位，因此適合部署于網(wǎng)絡(luò)數(shù)據(jù)中心或小型網(wǎng)絡(luò)設(shè)備的在線異常檢測與告警任務(wù)中.

3.2 基于RPCA的異常檢測方法

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

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

(8)

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

(9)

其中，L1范數(shù)表示數(shù)據(jù)內(nèi)部的每個元素絕對值之和，這就使得異常檢測方法可以在異常數(shù)據(jù)中存在較大值時，保證網(wǎng)絡(luò)異常檢測的精度.

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

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

(10)

其中中間變量Z為乘子的線性約束，β>0為違反線性約束的懲罰參數(shù)，〈·,·〉為標(biāo)準的內(nèi)積函數(shù).

最后，各個參數(shù)更新為：

(11)

(12)

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

(13)

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

(14)

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

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

(15)

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

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

(16)

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

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

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

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

(17)

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

低秩估計子問題：

(18)

異常檢測子問題：

(19)

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

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

基于直接矩陣分解的異常檢測方法與基于RPCA的異常檢測方法類似，利用數(shù)據(jù)分離的方法實現(xiàn)異常檢測，因此適合部署于網(wǎng)絡(luò)數(shù)據(jù)中心的離線異常檢測與定位任務(wù)中.

3.4 其他異常檢測方法

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

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

(20)

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

Fig. 7 Structured anomaly model圖7 結(jié)構(gòu)化異常模型

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

(21)

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

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

(22)

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

(23)

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

其他異常檢測方法利用數(shù)據(jù)分離的方法實現(xiàn)異常檢測，因此同樣適合部署于網(wǎng)絡(luò)數(shù)據(jù)中心的離線異常檢測與定位任務(wù)中.另外，由于對異常數(shù)據(jù)的不同約束，文獻[125-126,128]所提出的使用L2,0范數(shù)來約束異常數(shù)據(jù)的方案，可用于結(jié)構(gòu)化的異常檢測與定位任務(wù)中.

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

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

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

Fig. 8 Network monitoring data tensor圖8 網(wǎng)絡(luò)監(jiān)測數(shù)據(jù)張量

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

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

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

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

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

(24)

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

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

相似地，文獻[140]將網(wǎng)絡(luò)監(jiān)測數(shù)據(jù)建模成如圖11所示的2個張量模型，其中一個為網(wǎng)絡(luò)流數(shù)據(jù)構(gòu)成，另一個為網(wǎng)絡(luò)拓撲數(shù)據(jù)構(gòu)成，張量模型的3個維度分別為源節(jié)點、目的節(jié)點和時間.

Fig. 11 Network flow tensor model and topological tensor model圖11 網(wǎng)絡(luò)流張量模型與拓撲張量模型

(25)

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

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

(26)

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

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

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

(27)

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

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

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

Fig. 12 Online network anomaly detection model圖12 在線網(wǎng)絡(luò)異常檢測模型

在新數(shù)據(jù)來臨時，為了能夠及時檢測并報告異常的位置，文獻[76]提出了一種基于CP分解重用的技術(shù)，僅需存儲少數(shù)小規(guī)模中間變量，便能夠利用新來臨數(shù)據(jù)更新低秩估計子問題中所求解.根據(jù)文獻[76]所述，該方法能夠?qū)崿F(xiàn)與文獻[147]相似的檢測精度，卻能夠滿足在線網(wǎng)絡(luò)異常檢測的計算速度要求.

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

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

(28)

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

(29)

(30)

(31)

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

5 方法比較

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

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

6 挑戰(zhàn)與展望

近年來，盡管基于低秩分解的網(wǎng)絡(luò)異常檢測受到了越來越多學(xué)者的關(guān)注，各種新的研究方法與成果不斷涌現(xiàn)，但當(dāng)前的異常檢測研究還處于學(xué)術(shù)研究的階段，基于低秩分解的網(wǎng)絡(luò)異常檢測仍然面臨著諸多挑戰(zhàn).例如，異常檢測方法對于網(wǎng)絡(luò)特性與領(lǐng)域知識的融合問題，異常檢測算法與模型的適應(yīng)性問題，以及異常檢測的后續(xù)任務(wù)研究問題.這些挑戰(zhàn)將推動這一研究方向往更深入的方向不斷發(fā)展.總的來說，未來的研究方向?qū)⒅饕?個方面：

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

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

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

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

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

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

作者貢獻聲明：李曉燦負責(zé)論文的撰寫與修改；謝鯤負責(zé)論文結(jié)構(gòu)設(shè)計與指導(dǎo)，以及論文部分章節(jié)的修改；張大方負責(zé)各方法的整理與校對，以及論文修訂；謝高崗負責(zé)部分章節(jié)內(nèi)容的撰寫與修改.