基于低秩分解的網(wǎng)絡(luò)異常檢測綜述

李曉燦 謝 鯤 張大方 謝高崗

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

互聯(lián)網(wǎng)已經(jīng)成為社會基礎(chǔ)設(shè)施，但面臨嚴(yán)重的安全挑戰(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é)校、工廠等多個(gè)領(lǐng)域.隨著新技術(shù)的不斷應(yīng)用，互聯(lián)網(wǎng)變得越來越復(fù)雜，攻擊手段越來越先進(jìn)，如何快速精準(zhǔn)地檢測定位這些異常行為，避免造成更多的損失與危害，變得尤為重要.

1 研究背景

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

盡管經(jīng)過多年異常檢測方法的研究，很多檢測方法都實(shí)現(xiàn)了不錯(cuò)的異常檢測效果.然而，大部分研究都是通過分析獨(dú)立的時(shí)序數(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]等)來實(shí)現(xiàn)異常檢測.這些研究方法卻存在一些不可避免的缺陷[76]：

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

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

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

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

基于低秩分解的全網(wǎng)異常檢測模型不僅利用多條鏈路流量數(shù)據(jù)中的時(shí)間相關(guān)性(temporal corre-lation)，而且同時(shí)整合了空間相關(guān)性(spatial corre-lation)，將高維的網(wǎng)絡(luò)流量數(shù)據(jù)矩陣映射到正常子空間與異常子空間，然后在異常子空間中檢測凸顯的異常行為模式.該模型作為一種無監(jiān)督異常檢測模型，不需要學(xué)習(xí)任何網(wǎng)絡(luò)攻擊/異常的先驗(yàn)知識以及網(wǎng)絡(luò)正常行為模式，同時(shí)充分利用了網(wǎng)絡(luò)數(shù)據(jù)中的時(shí)間-空間相關(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ù)通常嚴(yán)重影響正常數(shù)據(jù)的低秩性，進(jìn)而影響正常數(shù)據(jù)的提取.因此，如何準(zhǔn)確提取正常數(shù)據(jù)，并在進(jìn)行正常數(shù)據(jù)提取過程中對異常數(shù)據(jù)進(jìn)行有效約束，以減少異常數(shù)據(jù)對正常數(shù)據(jù)提取的影響，從而保證異常檢測精度，這成為一項(xiàng)挑戰(zhàn).

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

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

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

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

為了研究基于低秩分解的全網(wǎng)異常檢測技術(shù)，通?？梢詫⑼粋€(gè)網(wǎng)絡(luò)中所有源節(jié)點(diǎn)(origin)和目的節(jié)點(diǎn)(destination)對之間的性能數(shù)據(jù)(例如流量、吞吐量、時(shí)延等)建模成一個(gè)矩陣.如圖1所示，矩陣中的行代表源節(jié)點(diǎn)-目的節(jié)點(diǎn)對(OD對),而矩陣中的列代表時(shí)間(time)，矩陣中元素則代表對應(yīng)時(shí)刻下OD對之間監(jiān)測的網(wǎng)絡(luò)性能數(shù)據(jù).根據(jù)所選擇的網(wǎng)絡(luò)節(jié)點(diǎn)類型的不同，可以定義為不同粒度的矩陣，例如鏈路級、路由級、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ò)異常檢測算法實(shí)現(xiàn)的前提條件是將正常網(wǎng)絡(luò)性能數(shù)據(jù)建模為低秩數(shù)據(jù)，因此，本節(jié)將首先給出網(wǎng)絡(luò)測量數(shù)據(jù)的低秩性驗(yàn)證.

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

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

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

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

圖3表示Abilene和GEANT數(shù)據(jù)集的低秩性驗(yàn)證結(jié)果.通過分析可以發(fā)現(xiàn)，少數(shù)幾個(gè)奇異值基本占據(jù)了所有奇異值的比重，因此，得以驗(yàn)證網(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ò)異常檢測方法

文獻(xiàn)[83]同樣在開源網(wǎng)絡(luò)流量數(shù)據(jù)集Abilene與GEANT上開展了實(shí)驗(yàn)，并驗(yàn)證了網(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ù)具有低秩性的特點(diǎn)，網(wǎng)絡(luò)攻擊代價(jià)高的問題以及網(wǎng)絡(luò)設(shè)備故障的稀疏性問題使得異常數(shù)據(jù)通常具有稀疏性的特點(diǎn).因此，異常數(shù)據(jù)矩陣E通常為稀疏矩陣，通過基于低秩分解的數(shù)據(jù)分離模型獲得稀疏異常數(shù)據(jù)矩陣E后，即可對網(wǎng)絡(luò)數(shù)據(jù)中是否存在異常進(jìn)行判定，同時(shí)根據(jù)矩陣中非零元素所處位置可進(jìn)行異常定位.

為了實(shí)現(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ù)通常嚴(yán)重影響正常數(shù)據(jù)的低秩性，進(jìn)而影響正常數(shù)據(jù)的提取，并最終影響異常檢測的精度.因此，如何準(zhǔn)確地提取正常數(shù)據(jù)并有效約束異常數(shù)據(jù)，成為異常檢測的關(guān)鍵一環(huán).

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

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算法來實(shí)現(xiàn)全網(wǎng)異常檢測.該算法利用低秩分解技術(shù)，將正常數(shù)據(jù)M從原始監(jiān)測數(shù)據(jù)X中提取出來，如圖4所示.

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

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

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

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

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

SPE=(xij-mij)2,

(3)

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

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

(4)

(5)

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

(6)

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

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

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

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

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

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

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

首先，將歷史的網(wǎng)絡(luò)數(shù)據(jù)通過雙向2維PCA，計(jì)算得到矩陣行列2個(gè)空間的歷史主成分uhistory，vhistory.如圖6所示，通過雙向2維主成分分析方法，原始數(shù)據(jù)從3維降到2維與1維.時(shí)刻t下的主成分由u1(t),u2(t)與v1(t)組成，其中u1(t),u2(t)為行空間主成分，v1(t)為列空間主成分；而時(shí)刻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維主成分方向變化分析的異常檢測方法

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

(7)

其中,Mt=[Ut,Vt]，Mt+1=[Ut+1,Vt+1]，Vec()為矩陣向量化.最后，通過歷史數(shù)據(jù)的預(yù)訓(xùn)練或者專家經(jīng)驗(yàn)來設(shè)定閾值，并與Cosine進(jìn)行比較，以判斷數(shù)據(jù)是否為異常或是否存在異常.

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

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

3.2 基于RPCA的異常檢測方法

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

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

(8)

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

(9)

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

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

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

(10)

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

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

(11)

(12)

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

(13)

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

(14)

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

文獻(xiàn)[117]提出了一種歸納方法：

(15)

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

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

(16)

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

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

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

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

(17)

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

低秩估計(jì)子問題：

(18)

異常檢測子問題：

(19)

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

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

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

3.4 其他異常檢測方法

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

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

(20)

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

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

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

(21)

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

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

(22)

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

(23)

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

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

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

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

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

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

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

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

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

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

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

(24)

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

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

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

Fig. 11 Network flow tensor model and topological tensor model圖11 網(wǎng)絡(luò)流張量模型與拓?fù)鋸埩磕Ｐ?/p>

(25)

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

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

(26)

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

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

與矩陣模型下基于直接矩陣分解方法的異常檢測方法類似，文獻(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)化信息，從而實(shí)現(xiàn)更高精度的異常檢測.

(27)

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

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

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

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

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

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

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

(28)

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

(29)

(30)

(31)

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

5 方法比較

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

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

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)將推動(dòng)這一研究方向往更深入的方向不斷發(fā)展.總的來說，未來的研究方向?qū)⒅饕?個(gè)方面：

1) 網(wǎng)絡(luò)特性與領(lǐng)域知識的融合問題.現(xiàn)有基于低秩分解的異常檢測模型通常僅約束了正常網(wǎng)絡(luò)數(shù)據(jù)的低秩性與異常數(shù)據(jù)的稀疏性等特點(diǎn)，缺乏對實(shí)際網(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ò)異常檢測模型可以分析與利用的計(jì)算機(jī)網(wǎng)絡(luò)領(lǐng)域知識越來越豐富，例如網(wǎng)絡(luò)拓?fù)湫畔ⅰ⒕W(wǎng)絡(luò)設(shè)備信息等.

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

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

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

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

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

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