云虛擬機(jī)異常檢測(cè)場(chǎng)景下改進(jìn)的LOF算法

賀寰燁 ，林果園 ，3，顧 浩 ，方夢(mèng)華

1.中國(guó)礦業(yè)大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，江蘇 徐州 221116

2.礦山數(shù)字化教務(wù)部工程研究中心，江蘇 徐州 221116

3.南京大學(xué) 計(jì)算機(jī)軟件新技術(shù)國(guó)家重點(diǎn)實(shí)驗(yàn)室，南京 210023

1 引言

云服務(wù)是一種將物理資源虛擬化并向用戶出售資源的一種服務(wù)模式。目前已有研究發(fā)現(xiàn)，未采用超額預(yù)定策略的大部分云計(jì)算中心的CPU 平均使用率僅為40%[1]。超額預(yù)定策略可以減少云服務(wù)提供商資源空閑而造成的損失，但同時(shí)還存在一定的風(fēng)險(xiǎn)——當(dāng)用戶對(duì)某類資源的使用峰值處于同一時(shí)間段時(shí)，就會(huì)造成資源搶占的情況發(fā)生，這將會(huì)造成云虛擬機(jī)卡頓甚至宕機(jī)等問題，這嚴(yán)重違反了服務(wù)等級(jí)協(xié)議（Service-Level Agreement，SLA）[2]。以CPU 資源超額預(yù)定為例，當(dāng)大量用戶在某個(gè)時(shí)間同時(shí)大量使用CPU 時(shí)，會(huì)發(fā)生對(duì)CPU 資源的搶占。對(duì)于其中某臺(tái)云虛擬機(jī)，不僅在用戶體驗(yàn)上有卡頓，其CPU 負(fù)載也將處于一種較低的水平。通過異常檢測(cè)可以盡早地發(fā)現(xiàn)云平臺(tái)中的各類異常狀況，對(duì)維護(hù)云服務(wù)的穩(wěn)定性、魯棒性與安全性有著重要作用[3-5]。盡管云計(jì)算平臺(tái)采用了相對(duì)集中和專業(yè)的管理，被普遍認(rèn)為具有相對(duì)較高的可用性，但目前沒有任何一種技術(shù)可以保證云服務(wù)不出現(xiàn)故障，而這些故障可能引起部分甚至所有服務(wù)失效[6-9]。當(dāng)云虛擬機(jī)發(fā)生故障時(shí)，通過檢測(cè)云虛擬機(jī)運(yùn)行數(shù)據(jù)來判斷異常是否發(fā)生。

為了減少云虛擬機(jī)故障對(duì)云服務(wù)提供商及用戶造成的損失，近年來云虛擬機(jī)異常檢測(cè)已成為云服務(wù)領(lǐng)域的熱門研究話題。何等人[10]針對(duì)上下文異常檢測(cè)提出了一種聚類中心選取策略，將具有相似上下文的虛擬機(jī)先聚類，然后將不同類別的虛擬機(jī)分別通過異常檢測(cè)模型判斷其中是否發(fā)生異常。Sauvanaud 等人[8]提出了一種異常檢測(cè)系統(tǒng)，他們首先訓(xùn)練機(jī)器模型，然后通過這個(gè)模型來判斷云虛擬機(jī)是否發(fā)生異常，在判斷為異常的同時(shí)還可以提供異常種類。Farshchi 等人[7]分析了云服務(wù)活動(dòng)日志與云服務(wù)虛擬資源之間的關(guān)系，提出了一種基于回歸分析的度量選擇方法，以解決針對(duì)云虛擬機(jī)操作方面的異常識(shí)別。在CPU資源超額預(yù)定所造成異常的例子中，異常云虛擬機(jī)由于得不到足夠的CPU資源，其內(nèi)部CPU使用率處于一種較低水平。而大部分異常檢測(cè)的正常數(shù)據(jù)集由虛擬機(jī)在各個(gè)狀態(tài)下正常運(yùn)行的數(shù)據(jù)所構(gòu)成。而該異常云虛擬機(jī)的CPU數(shù)據(jù)往往處于這部分異常檢測(cè)訓(xùn)練集中的正常數(shù)據(jù)。但通過上下文異常檢測(cè)則可以發(fā)現(xiàn)該數(shù)據(jù)與歷史同期的數(shù)據(jù)不同，從而識(shí)別出異常的發(fā)生。

云服務(wù)中存在多種任務(wù)類型，云虛擬機(jī)的運(yùn)行數(shù)據(jù)與所執(zhí)行的任務(wù)類型有關(guān)，執(zhí)行同類任務(wù)的云虛擬機(jī)的運(yùn)行數(shù)據(jù)是相似的，并且異常云虛擬機(jī)占比較小。前面的例子說明了CPU 資源超額預(yù)定可能存在的異常，而且產(chǎn)生的異常數(shù)據(jù)不僅有宏觀上明顯的異常數(shù)據(jù)，還存在宏觀上近似正常數(shù)據(jù)，而在局部才體現(xiàn)異常的數(shù)據(jù)。LOF 算法適合檢測(cè)這類數(shù)據(jù)。目前已有學(xué)者在云虛擬機(jī)異常檢測(cè)中采用LOF算法。Huang等人[9]在研究虛擬機(jī)在動(dòng)態(tài)遷移過程中是否發(fā)生異常，他們先使用LOF算法判斷遷移數(shù)據(jù)是否為異常，再結(jié)合基于時(shí)間序列的符號(hào)化算法（Symbolic Aggregate Approximation，SAX）算法檢測(cè)這種異常情況是否為誤報(bào)，以此提高算法準(zhǔn)確性。他們雖然提高了檢測(cè)精度，但是花費(fèi)了大量計(jì)算時(shí)間與計(jì)算量。Wang 等人[11]針對(duì)云服務(wù)web 應(yīng)用，先以負(fù)載向量對(duì)提供web服務(wù)的云虛擬機(jī)進(jìn)行分組，采用增量聚類算法對(duì)工作負(fù)載進(jìn)行訓(xùn)練，最后采用LOF算法檢測(cè)工作負(fù)載是否發(fā)生異常。該方法可以提高對(duì)特定負(fù)載的檢測(cè)準(zhǔn)確率。但該方法適用范圍小，只適用于某些云服務(wù)。呂等人[12]首先通過DBSCAN 算法先對(duì)數(shù)據(jù)集進(jìn)行預(yù)處理，排除大量正常數(shù)據(jù)集，然后對(duì)剩余數(shù)據(jù)采用LOF 算法計(jì)算是否有異常點(diǎn)。這種算法改進(jìn)方式通過排除大量正確云虛擬機(jī)來減少算法的時(shí)間花費(fèi)，但是在異常檢測(cè)的過程中，缺少部分虛擬機(jī)會(huì)造成準(zhǔn)確率降低以及誤判率偏高。楊等人[13]將iForest算法、LOF算法與DBSCAN 算法分別通過同類數(shù)據(jù)集進(jìn)行訓(xùn)練，再依據(jù)訓(xùn)練結(jié)果對(duì)三種算法分配權(quán)重，最終通過加權(quán)的結(jié)果綜合實(shí)現(xiàn)對(duì)異常點(diǎn)的檢測(cè)。這種檢測(cè)架構(gòu)雖然提高了檢測(cè)準(zhǔn)確率，但是時(shí)間花費(fèi)與計(jì)算花費(fèi)非常大。

為了解決上述問題，本文提出了一種基于密度空間的局部離群因子算法。該算法將同一時(shí)間內(nèi)執(zhí)行同類任務(wù)虛擬機(jī)的數(shù)據(jù)作為彼此的歷史數(shù)據(jù)，并參考DBSCAN 算法在密度空間中核心云虛擬機(jī)之間的密度相連、密度直達(dá)、密度可達(dá)等性質(zhì)，提出了LOF計(jì)算過程中的判斷規(guī)則，達(dá)到減少對(duì)正常云虛擬機(jī)的計(jì)算量的目的，提高算法的計(jì)算效率。

2 LOFBDS算法

云服務(wù)中某臺(tái)云虛擬機(jī)表示為VMi，全部云虛擬機(jī)集合表示為：VM={VM1,VM2,…,VMi,…,VMn}。任意兩臺(tái)云虛擬機(jī)VMi與VMj之間的距離表示為d(VMi,VMj)= |VMi,VMj|，其中“ |·| ”表示兩個(gè)向量的歐氏距離。以云虛擬機(jī)VMi為例，距離VMi第k遠(yuǎn)云虛擬機(jī)的距離稱為云虛擬機(jī)VMi的第k鄰近距離，表示為：

式（1）中dk(VMi)需滿足以下兩個(gè)條件：

（1）在云虛擬機(jī)VMi周圍至少有不包含該云虛擬機(jī)的k臺(tái)云虛擬機(jī)VMl∈VM，并符合?d(VMi,VMl)≤d(VMi,VMj)。

（2）在云虛擬機(jī)VMi周圍至多有不包括該云虛擬機(jī)的k-1 臺(tái)云虛擬機(jī)VMl∈VM，并符合 ?d(VMi,VMl)＜d(VMi,VMj)。

云虛擬機(jī)VMi的第k鄰近距離之內(nèi)所有云虛擬機(jī)集合稱為VMi的第k鄰域，記為Nk(VMi)。可以得出|Nk(VMi) |≥k。云虛擬機(jī)VMi到云虛擬機(jī)VMj的第k可達(dá)距離表示為：

式（2）表示，若VMj處于VMi的第k鄰域內(nèi)，則VMi到VMj的第k可達(dá)距離為dk(VMi)，否則為VMi到VMj的真實(shí)距離d(VMi,VMj) 。由此可以得出云虛擬機(jī)VMi的局部密度：

式（3）表示，云虛擬機(jī)VMi的局部密度為VMi的第k鄰域內(nèi)的云虛擬機(jī)到云虛擬機(jī)VMi的平均第k可達(dá)距離的倒數(shù)。進(jìn)而可以得出云虛擬機(jī)的局部離群因子：

式（4）表示，云虛擬機(jī)VMi局部離群因子為VMi的第k鄰域內(nèi)的云虛擬機(jī)的局部密度與VMi的局部密度比值之和的均值。如果這個(gè)比值接近1，則表明VMi與其第k鄰域的云虛擬機(jī)的局部密度相似，VMi可能與其第k鄰域的云虛擬機(jī)屬于同一簇；如果這個(gè)比值小于1，則表明VMi的局部密度大于其第k鄰域的云虛擬機(jī)的局部密度，VMi可能為密集點(diǎn)；如果這個(gè)比值大于1，則表明的局部密度小于其第k鄰域的云虛擬機(jī)的局部密度，VMi可能為異常點(diǎn)。

2.1 基于密度空間改進(jìn)LOF

由于異常點(diǎn)是少數(shù)存在的，通過LOF算法對(duì)大量正常點(diǎn)計(jì)算浪費(fèi)了計(jì)算資源。文獻(xiàn)[11]提出的算法只是機(jī)械地組合了DBSCAN 與LOF 算法，并通過剪枝操作刪除正常云虛擬機(jī)，只對(duì)剩余云虛擬機(jī)進(jìn)行異常檢測(cè)，這種檢測(cè)方法由于云虛擬機(jī)數(shù)量減少而造成部分云虛擬機(jī)局部密減少，使得檢測(cè)準(zhǔn)確率降低，誤判率增高。在減少計(jì)算量的前提下，為了保障檢測(cè)準(zhǔn)確率與誤判率，不能直接去除正常云虛擬機(jī)，LOFBDS算法通過引入密度空間中局部核心云虛擬機(jī)概念及相關(guān)性質(zhì)，并增加判斷規(guī)則，實(shí)現(xiàn)對(duì)大部分云虛擬機(jī)的快速判斷。

（1）局部核心云虛擬機(jī)的概念及性質(zhì)

核心云虛擬機(jī)為局部密度大于一定閾值γ的云虛擬機(jī)。但是面對(duì)密度不同的集群，其中的異常云虛擬機(jī)與該虛擬機(jī)所在集群之間的差異也不同，因此無法有統(tǒng)一確定核心云虛擬機(jī)的標(biāo)準(zhǔn)。為此，在核心云虛擬機(jī)的基礎(chǔ)上提出局部核心云虛擬機(jī)。局部核心云虛擬機(jī)為局部密度大于一定閾值γ的云虛擬機(jī)，并且有效范圍為該云虛擬機(jī)的第k鄰域，即局部核心云虛擬機(jī)針對(duì)這臺(tái)云虛擬機(jī)及其第k鄰域內(nèi)的云虛擬機(jī)生效。局部核心云虛擬機(jī)具有以下四點(diǎn)性質(zhì)：

①密度直達(dá)。若云虛擬機(jī)VMj屬于局部核心云虛擬機(jī)VMi的第k鄰域，而且VMj也是一臺(tái)局部核心云虛擬機(jī)，則可以表示VMj由VMi密度直達(dá)。

②密度可達(dá)。對(duì)于任意兩臺(tái)局部核心云虛擬機(jī)VMi與VMj，若存在這樣一條局部核心云虛擬機(jī)序列{vm1,vm2,…,vmm} ，其中vm1=VMi，vmm=VMj，并且vmi+1由vmi密度直達(dá)，則稱VMj由VMi密度可達(dá)。

③密度相連。對(duì)于任意兩臺(tái)局部核心云虛擬機(jī)VMi與VMj，若存在局部核心云虛擬機(jī)VMk使得VMi與VMj均由VMk密度可達(dá)，稱VMi與VMj密度相連。

④范圍延伸。密度相連的局部核心云虛擬機(jī)其第k鄰域都為其有效范圍。

（2）局部核心云虛擬機(jī)的判斷方式

局部核心云虛擬機(jī)是LOFBDS 算法能夠快速檢測(cè)云虛擬機(jī)是否異常的重要部分。LOFBDS 算法在判斷一臺(tái)云虛擬機(jī)是否為局部核心云虛擬機(jī)時(shí)會(huì)有兩種情況，若該虛擬機(jī)處于某臺(tái)局部核心云虛擬機(jī)的第k領(lǐng)域，則通過方式①判斷，其他需要檢測(cè)該云虛擬機(jī)的局部離群因子的情況，通過方式②判斷：

①在某一臺(tái)局部核心云虛擬機(jī)的第k鄰域內(nèi)，并滿足局部密度γ的云虛擬機(jī)。具體情況如下：

若VMi為正常云虛擬機(jī)，VMj為VMi第k鄰域內(nèi)的云虛擬機(jī)。若滿足local_dk(VMj)≥γ，則VMj也為良局部核心云虛擬機(jī)。

若VMi為異常云虛擬機(jī)，VMj為VMi第k鄰域內(nèi)的云虛擬機(jī)。若滿足local_dk(VMj)＜γ，則VMj也為劣局部核心云虛擬機(jī)。

②經(jīng)過計(jì)算局部離群因子的云虛擬機(jī)為局部核心云虛擬機(jī)。若為正常云虛擬機(jī)，則稱其為良局部核心云虛擬機(jī)。若為異常云虛擬機(jī)，則稱其為劣局部核心云虛擬機(jī)。

（3）與局部核心云虛擬機(jī)相關(guān)的密度參數(shù)γ

密度參數(shù)γ是由局部核心云虛擬機(jī)所確定的，該局部核心云虛擬機(jī)是通過計(jì)算局部離群因子而判定的。密度參數(shù)為該局部核心云虛擬機(jī)的局部密度，即local_dk(VMi)=γ。密度參數(shù)是用來判斷該局部核心云虛擬機(jī)第k鄰域內(nèi)的云虛擬機(jī)是否滿足局部核心云虛擬機(jī)的標(biāo)準(zhǔn)。與局部核心云虛擬機(jī)相同，密度參數(shù)γ也是在局部核心云虛擬機(jī)的第k鄰域內(nèi)有效。

2.2 LOFBDS算法判斷規(guī)則

在LOFBDS算法的執(zhí)行過程中，計(jì)算并檢測(cè)某臺(tái)云虛擬機(jī)的局部離群因子后，其第k領(lǐng)域內(nèi)的云虛擬機(jī)可以不需要依次計(jì)算其局部離群因子就能夠快速確定是否為異常云虛擬機(jī)。根據(jù)式（4）可知，云虛擬機(jī)VMi的局部離群因子LOFK(VMi)是根據(jù)該云虛擬機(jī)與其第k領(lǐng)域內(nèi)的其他云虛擬機(jī)的局部密度之比的均值來判定的。那么云虛擬機(jī)VMi的第k鄰域內(nèi)其他云虛擬機(jī)VMj將存在兩種情況：

（1）local_dk(VMi)≤local_dk(VMj)，由此可得出推論1與推論2。

推論1如果一臺(tái)云虛擬機(jī)VMi是正常的，那么它第k鄰域內(nèi)的所有云虛擬機(jī)(VMj∈Nk(VMi))都為正常云虛擬機(jī)。

證明如果一臺(tái)云虛擬機(jī)發(fā)生異常，那么這臺(tái)云虛擬機(jī)與同類云虛擬機(jī)相似度就很低，這臺(tái)云虛擬機(jī)在密度空間的位置將遠(yuǎn)離正常云虛擬機(jī)集合。假定異常云虛擬機(jī)VManomaly為VMi的第k臺(tái)鄰近云虛擬機(jī)，那么總是可以從正常云虛擬機(jī)集合中找到一臺(tái)云虛擬機(jī)VMj，滿足 ?d(VMi,VMj)＜d(VMi,VManomaly)。所以VManomaly不是VMi的第k臺(tái)鄰近云虛擬機(jī)。由此推廣，正常云虛擬機(jī)的第k鄰域內(nèi)不會(huì)有異常云虛擬機(jī)的存在。正常云虛擬機(jī)的第k鄰域內(nèi)的所有云虛擬機(jī)都為正常云虛擬機(jī)。證畢。

推論2如果一臺(tái)云虛擬機(jī)VMi是正常的，那么它第k鄰域(Nk(VMi))內(nèi)局部密度大于等于VMi的云虛擬機(jī)VMj的第k鄰域(Nk(VMj))內(nèi)的云虛擬機(jī)也是正常的。

證明由推論1可知，如果云虛擬機(jī)VMi是正常的，那么VMi為良局部核心云虛擬機(jī)，此時(shí)Nk(VMi)內(nèi)的云虛擬機(jī)都是正常的。假設(shè)存在云虛擬機(jī)VMj，局部密度local_dk(VMj)＞local_dk(VMi)。那么VMj為良局部核心云虛擬機(jī)，Nk(VMj)內(nèi)的云虛擬機(jī)將更加靠近VMj，那么Nk(VMj)內(nèi)的云虛擬機(jī)比Nk(VMi)表現(xiàn)更為正常。根據(jù)推論1得出，VMj的第k鄰域（Nk(VMj)）內(nèi)的云虛擬機(jī)也是正常的。證畢。

（2）local_dk(VMi)＞local_dk(VMj)，由此可得出推論3。

推論3如果一臺(tái)云虛擬機(jī)VMi是異常的，那么它第k鄰域（Nk(VMi)）內(nèi)局部密度小于VMi的云虛擬機(jī)VMj也是異常的。

證明若云虛擬機(jī)VMi為異常云虛擬機(jī)，那么該云虛擬機(jī)將遠(yuǎn)離正常云虛擬機(jī)集合。假設(shè)VMj∈Nk(VMi)，并且local_dk(VMj)＜local_dk(VMi)，說明VMj第k領(lǐng)域內(nèi)的云虛擬機(jī)更加稀疏，則云虛擬機(jī)VMj較VMi更加遠(yuǎn)離正常云虛擬機(jī)集合，并且LOFK(VMj)＜LOFK(VMi)，所以VMj一定是異常云虛擬機(jī)。證畢。

LOFBDS 算法通過優(yōu)化對(duì)大部分云虛擬機(jī)的判斷方式，通過判斷規(guī)則對(duì)不同的云虛擬機(jī)進(jìn)行相對(duì)應(yīng)的判斷過程。LOFBDS 算法的判斷規(guī)則根據(jù)以上3 點(diǎn)推論所得，具體規(guī)則如下：

規(guī)則1對(duì)于非局部核心云虛擬機(jī)第k領(lǐng)域內(nèi)的云虛擬機(jī)，通過檢測(cè)云虛擬機(jī)VMi局部離群因子與閾值ε的關(guān)系判斷其是否為異常。結(jié)果分為以下兩種情況：

（1）LOFK(VMi)≤ε，說明VMi為正常云虛擬機(jī)，同時(shí)記為良局部核心云虛擬機(jī)。

（2）LOFK(VMi)＞ε，說明VMi為異常云虛擬機(jī)，同時(shí)記為劣局部核心云虛擬機(jī)。

規(guī)則2對(duì)局部核心云虛擬機(jī)第k領(lǐng)域內(nèi)的云虛擬機(jī)進(jìn)行判斷：

（1）若VMi為良局部核心云虛擬機(jī)，根據(jù)推論1 可知，Nk(VMi)內(nèi)的云虛擬機(jī)VMj都為正常云虛擬機(jī)，并將滿足local_dk(VMj)≥local_dk(VMi)的云虛擬機(jī)記為良局部核心云虛擬機(jī)。依據(jù)推論2，Nk(VMj)內(nèi)的云虛擬機(jī)也可通過此規(guī)則進(jìn)行進(jìn)一步判斷。

（2）當(dāng)VMi為劣局部核心云虛擬機(jī)，根據(jù)推論3 可知，Nk(VMi)內(nèi)的云虛擬機(jī)VMj滿足local_dk(VMj)≤local_dk(VMi)為異常云虛擬機(jī)，同時(shí)也記為劣局部核心云虛擬機(jī)。Nk(VMj)內(nèi)的云虛擬機(jī)也可通過此規(guī)則進(jìn)行進(jìn)一步判斷。

規(guī)則3對(duì)于無法通過規(guī)則2判斷的云虛擬機(jī)，將其視為非局部核心云虛擬機(jī)第k領(lǐng)域內(nèi)的云虛擬機(jī)，并通過規(guī)則1進(jìn)行判斷。

至此，在檢測(cè)云虛擬機(jī)VMi的狀態(tài)后，可以得出Nk(VMi)之內(nèi)部分云虛擬機(jī)的狀態(tài)，進(jìn)而可以得到這些云虛擬機(jī)第k鄰域內(nèi)部分云虛擬機(jī)的狀態(tài)。以此類推，計(jì)算一次局部離群因子可以判斷多臺(tái)云虛擬機(jī)的狀態(tài)，并且在這個(gè)過程中不需要檢測(cè)這些云虛擬機(jī)的局部離群因子，減少了計(jì)算量。

2.3 LOFBDS算法偽代碼

LOFBDS 算法在檢測(cè)過程中將云虛擬機(jī)分至4 種云虛擬機(jī)集合，分別是還未進(jìn)行檢測(cè)的虛擬機(jī)集合VM′，根據(jù)判斷規(guī)則尚無法直接推斷，還需要進(jìn)一步計(jì)算局部離群因子的待測(cè)云虛擬機(jī)集合wait_VM′，已確認(rèn)為正常云虛擬機(jī)的正常云虛擬機(jī)集合normal_VM以及已確認(rèn)為異常云虛擬機(jī)的異常云虛擬機(jī)集合anormaly_VM。LOFBDS算法偽代碼如算法1所示。

算法1LOFBDS算法偽代碼

輸入：VM，云服務(wù)虛擬機(jī)集合

TASK，云服務(wù)任務(wù)類型集合

ε，局部離群因子閾值

輸出：anormaly_VM，異常云虛擬機(jī)集合

Begin

1.Forjin range（1，m）：

2.Computelocal_dk(VMj)

3.VM′←local_dk(VMj)

4.End for #計(jì)算全體云虛擬機(jī)局部密度

5.While（wait_VM′＞ 0 orVM′＞ 0）：

6.IfwaitVM′==null：

7.VM′→VMi

8.Else：

9.wait_VM′→VMi

10.End if #選擇一臺(tái)云虛擬機(jī)VMi

11.ComputeLOFK(VMi)#計(jì)算VMi的局部離群因子

12.IfLOFK(VMi)＜ε：

13.normal_VM←VMi

14.Forrin range（1，k）：

15.Iflocal_dk(VMr)≥local_dk(VMi)：

16.normal_VM←VMr

17.Else：

18.wait_VM←VMr

19.End if

20.End for

21.Else：

22.anomaly_VM←VMi

23.Forrin range（1，k）：

24.Iflocal_dk(VMr)≤local_dk(VMi)：

25.anormaly_VM←VMr

26.Else：

27.wait_VM←VMr

28.End if

29.End for

30.End if #依據(jù)判斷規(guī)則判斷Nk(VMi)內(nèi)云虛擬機(jī)

31.End while

3 實(shí)驗(yàn)

3.1 實(shí)驗(yàn)環(huán)境

實(shí)驗(yàn)數(shù)據(jù)通過收集實(shí)驗(yàn)云平臺(tái)獲得，該云平臺(tái)基于OpenStack搭建，使用服務(wù)器一臺(tái)，其他主機(jī)10臺(tái)，具體參數(shù)如表1所示。

OpenStack 的控制節(jié)點(diǎn)搭建在戴爾服務(wù)器上，所有物理節(jié)點(diǎn)上配置相同配置的虛擬機(jī)。其中虛擬機(jī)配置CPU算力1 GHz，內(nèi)存2 GB，存儲(chǔ)20 GB，網(wǎng)絡(luò)等采用默認(rèn)配置。虛擬機(jī)部署Ubuntu16.04操作系統(tǒng)。其中服務(wù)器部署90臺(tái)虛擬機(jī)，每臺(tái)聯(lián)想主機(jī)配置14臺(tái)虛擬機(jī)，每臺(tái)宏碁主機(jī)配置8 臺(tái)虛擬機(jī)，總計(jì)200 臺(tái)虛擬機(jī)。實(shí)驗(yàn)室云平臺(tái)網(wǎng)絡(luò)拓?fù)鋱D如圖1所示。

本次實(shí)驗(yàn)通過CPU 利用率來檢測(cè)算法的有效性。虛擬機(jī)安裝實(shí)驗(yàn)室測(cè)試使用的模塊，可以通過浮點(diǎn)計(jì)算模擬CPU 使用，并通過atop 監(jiān)控虛擬機(jī)，收集運(yùn)行數(shù)據(jù)。在對(duì)虛擬機(jī)分配任務(wù)時(shí)，保證每臺(tái)物理機(jī)上均有虛擬機(jī)分配到任務(wù)。

異常通過人為方式注入，云平臺(tái)在執(zhí)行浮點(diǎn)運(yùn)算任務(wù)時(shí)，選取非服務(wù)器的一臺(tái)物理主機(jī)，人為對(duì)多臺(tái)處于待機(jī)狀態(tài)中的虛擬機(jī)增加浮點(diǎn)計(jì)算任務(wù)，以實(shí)現(xiàn)CPU資源的搶占，模擬用戶對(duì)某種資源的使用峰值處于同一時(shí)間段。

實(shí)驗(yàn)結(jié)果通過準(zhǔn)確率、誤判率、檢測(cè)速度來對(duì)比各個(gè)算法之間的優(yōu)劣，其中準(zhǔn)確率、誤判率的計(jì)算公式如下：

式（5）及式（6）中，TP表示正確識(shí)別正常云虛擬機(jī)的數(shù)量，TN表示正確識(shí)別異常云虛擬機(jī)的數(shù)量，F(xiàn)N表示錯(cuò)誤識(shí)別異常云虛擬機(jī)的數(shù)量，ALL表示全部云虛擬機(jī)的數(shù)量。

3.2 實(shí)例分析

某虛擬機(jī)在異常注入后的CPU利用率如圖2所示，該虛擬機(jī)在正常執(zhí)行任務(wù)180 s 時(shí)，對(duì)其所在的宿主機(jī)進(jìn)行異常注入，可以發(fā)現(xiàn)該虛擬機(jī)內(nèi)部檢測(cè)到CPU 利用率突然降低，從98%左右降至60%左右，并且CPU 利用率波動(dòng)增大。

表1 實(shí)驗(yàn)云平臺(tái)物理設(shè)備配置表

圖1 云平臺(tái)網(wǎng)絡(luò)拓?fù)鋱D

圖2 某虛擬機(jī)的CPU利用率

圖3 為一組實(shí)驗(yàn)數(shù)據(jù)經(jīng)過t-SNE（t-distributed Stochastic Neighbor Embedding）算法降維得到的二維可視化圖。其中C1 虛擬機(jī)集群運(yùn)行浮點(diǎn)運(yùn)算，主要使用CPU資源；C2虛擬機(jī)集群執(zhí)行連續(xù)存儲(chǔ)及刪除操作，主要使用磁盤I/O資源。

圖3 虛擬機(jī)數(shù)據(jù)二維可視化圖

如圖3 所示，經(jīng)過對(duì)CPU 資源搶占的異常注入，三個(gè)異常虛擬機(jī)發(fā)生異常，分別是C1集群的O1與O2，C2集群的O3。其中O1與O2的成因與圖3中虛擬機(jī)相同，所以這兩個(gè)異常虛擬機(jī)向CPU利用率較小的C2集群靠近；O3由于CPU資源不足，導(dǎo)致無法在指定時(shí)間內(nèi)向磁盤發(fā)送指令，從而造成了磁盤I/O 異常。并且O1 及O2表現(xiàn)為局部異常，O3為全局異常。可以看出C1集群中O1 虛擬機(jī)與其所在的集群之間的差異較小，而且這個(gè)差異小于C2 集群中正常虛擬機(jī)之間的差異，所以證實(shí)了無法通過統(tǒng)一標(biāo)準(zhǔn)確定核心云虛擬機(jī)。因此LOF 算法更適合應(yīng)對(duì)此類數(shù)據(jù)。

由圖3還可以看出C1集群與C2集群內(nèi)部分別比較均勻，并且C1集群比C2集群更加緊密。這是由于在大量使用CPU資源時(shí)，CPU處于一種穩(wěn)定滿載的狀態(tài)；而對(duì)連續(xù)存儲(chǔ)及刪除操作，只是CPU 在某一時(shí)間發(fā)布若干次命令，所以CPU 利用率波動(dòng)較大。這表明了執(zhí)行同類任務(wù)的正常虛擬機(jī)各項(xiàng)數(shù)據(jù)是相似的。所以本文提出的將同一時(shí)間內(nèi)執(zhí)行同類任務(wù)虛擬機(jī)的數(shù)據(jù)作為彼此的歷史數(shù)據(jù)是可行的。

3.3 異常檢測(cè)及結(jié)果分析

為了驗(yàn)證LOFBDS 算法在云虛擬機(jī)異常檢測(cè)方面的效率，本部分采用原始LOF算法、文獻(xiàn)[6]的算法（LOFSAX）及文獻(xiàn)[11]的算法（DBSCAN-LOF）作為對(duì)比進(jìn)行驗(yàn)證。實(shí)驗(yàn)分為兩部分，第一部分檢測(cè)算法的檢測(cè)精度，通過對(duì)30 組數(shù)據(jù)進(jìn)行測(cè)試，得到檢測(cè)準(zhǔn)確率如圖4所示，檢測(cè)誤判率如圖5 所示；第二部分為檢測(cè)算法的時(shí)間花費(fèi)，檢測(cè)結(jié)果如圖6所示。

圖4 四種算法在30組實(shí)驗(yàn)中的檢測(cè)準(zhǔn)確率

圖5 四種算法在30組實(shí)驗(yàn)中的檢測(cè)誤判率

圖6 云虛擬機(jī)數(shù)量與算法檢測(cè)時(shí)間花費(fèi)的關(guān)系

如圖4所示，四種算法的檢測(cè)準(zhǔn)確率都達(dá)到94%以上，其中LOFBDS 算法表現(xiàn)最好，準(zhǔn)確率達(dá)到98.0%以上，并且誤差僅在0.21%之內(nèi)；LOF-SAX算法表現(xiàn)次之，準(zhǔn)確率接近LOFBDS 算法，達(dá)到97.6%以上，誤差在0.31%之內(nèi)；原始LOF算法表現(xiàn)一般，準(zhǔn)確率約為97.3%左右，誤差為0.96%左右；DBSCAN-LOF算法表現(xiàn)最差，準(zhǔn)確率為94.2%至96.3%之間，誤差高達(dá)2.40%。

如圖5所示，總體來說LOFBDS算法的檢測(cè)誤判率較低并檢測(cè)結(jié)果穩(wěn)定，誤判率為0.7%以下，誤差在0.18%之內(nèi)；LOF-SAX 算法檢測(cè)誤判率次之，并且檢測(cè)結(jié)果也比較穩(wěn)定，誤判率為0.96%以下，誤差在0.28%之內(nèi)；原始LOF算法檢測(cè)誤判率一般，檢測(cè)結(jié)果穩(wěn)定性較差，誤判率在2.4%之下，誤差在1.03%之內(nèi)；DBSCANLOF 算法不論在檢測(cè)誤判率還是穩(wěn)定性方面都表現(xiàn)最差，誤判率在5.9%之下，誤差約在2.2%之內(nèi)。

造成以上情況原因可能在于對(duì)邊緣云虛擬機(jī)處理情況的差異。以原始LOF 算法的檢測(cè)方式為基準(zhǔn)，LOFBDS算法在處理邊緣云虛擬機(jī)時(shí)增加了判斷規(guī)則，可以更加準(zhǔn)確地識(shí)別邊緣云虛擬機(jī)是否為異常云虛擬機(jī)，減少了誤判的發(fā)生，提高了檢測(cè)準(zhǔn)確率；LOF-SAX算法在LOF 算法對(duì)數(shù)據(jù)進(jìn)行異常檢測(cè)之后，還通過SAX 算法對(duì)LOF 算法的檢測(cè)結(jié)果進(jìn)行核實(shí)，減少了誤報(bào)的發(fā)生；DBSCAN-LOF 算法在檢測(cè)之前為了減少計(jì)算花銷對(duì)數(shù)據(jù)集進(jìn)行了剪枝操作，這不僅增加了邊緣云虛擬機(jī)的數(shù)量，同時(shí)還造成了邊緣云虛擬機(jī)密度的降低，造成了檢測(cè)準(zhǔn)確率降低、檢測(cè)誤報(bào)率增加以及誤差增大。

四種算法的計(jì)算時(shí)間花費(fèi)如圖6所示，趨勢(shì)線皆使用多項(xiàng)式來擬合。在有限的數(shù)據(jù)集中，LOF算法的時(shí)間花費(fèi)成指數(shù)式增長(zhǎng)，這符合LOF 算法的時(shí)間復(fù)雜度為O(n2)；LOF-SAX算法在云虛擬機(jī)較少時(shí)時(shí)間花費(fèi)就比較高，隨著云虛擬機(jī)臺(tái)數(shù)的增加，該算法的時(shí)間花費(fèi)成指數(shù)式增加，其原因是該算法相對(duì)于原始LOF算法增加了使用SAX 算法檢測(cè)LOF 算法檢測(cè)結(jié)果的步驟，雖然提高了檢測(cè)效率，但是計(jì)算時(shí)間花費(fèi)大大增加；LOFBDS算法在云虛擬機(jī)較少時(shí)時(shí)間花費(fèi)較低，隨著云虛擬機(jī)臺(tái)數(shù)的增多，其計(jì)算時(shí)間也隨之增加，其趨勢(shì)線更加趨向于線性，說明本文提出的算法在減少時(shí)間花費(fèi)方面有著良好的效果；DBSCAN-LOF 算法在這次實(shí)驗(yàn)中表現(xiàn)結(jié)果最優(yōu)，其擬合的趨勢(shì)線較LOFBDS算法更加趨向于線性，這是其對(duì)數(shù)據(jù)集剪枝產(chǎn)生的結(jié)果。

綜上所述，LOFBDS 與LOF-SAX 算法在異常檢測(cè)過程中檢測(cè)準(zhǔn)確率與檢測(cè)誤判率有著良好的效果，但是LOF-SAX 算法的時(shí)間花費(fèi)過大，不適用于存在大量云虛擬機(jī)的云服務(wù)中。DBSCAN-LOF算法雖然有著最好的時(shí)間花費(fèi)，但是該算法的檢測(cè)準(zhǔn)確率與檢測(cè)誤判率非常不理想。所以本文提出的LOFBDS 算法更加適用于云虛擬機(jī)異常檢測(cè)。

4 結(jié)束語

云服務(wù)提供商為了提高服務(wù)器使用率、降低成本采用了超額預(yù)售策略。該策略在某種物理資源使用殆盡時(shí)會(huì)引發(fā)虛擬機(jī)異常，具體表現(xiàn)為資源搶占的發(fā)生，從而使虛擬機(jī)可用資源減少，導(dǎo)致虛擬機(jī)發(fā)生卡頓甚至宕機(jī)。針對(duì)這種異常提出了一種適用于云虛擬機(jī)異常檢測(cè)的LOFBDS算法。該算法采用上下文異常檢測(cè)策略，將執(zhí)行同類任務(wù)的配置相同的虛擬機(jī)的運(yùn)行數(shù)據(jù)作為彼此的歷史數(shù)據(jù)，再將DBSCAN 算法中密度空間的相關(guān)性質(zhì)引入LOF算法，提出了檢測(cè)過程中的判斷規(guī)則，優(yōu)化對(duì)云虛擬機(jī)的檢測(cè)。實(shí)驗(yàn)表明，本文提出的算法有著良好的檢測(cè)效果，同時(shí)具有較低的時(shí)間花費(fèi)。

本文算法是針對(duì)將任務(wù)進(jìn)行分布式處理的云平臺(tái)所提出的，要求云平臺(tái)中虛擬機(jī)配置相同或者執(zhí)行同類任務(wù)的虛擬機(jī)配置相同，并且要求子任務(wù)在不同服務(wù)器上的虛擬機(jī)中完成，而且本文檢測(cè)算法中的輸入數(shù)據(jù)皆采用原始數(shù)據(jù)，因此在計(jì)算和時(shí)間消耗上還存在優(yōu)化空間，今后的工作內(nèi)容主要集中在尋找適合于大規(guī)模云檢測(cè)數(shù)據(jù)的降維算法。