適用于云環(huán)境的LASVM異常檢測(cè)研究

王瑞晗，高建瓴，陳 語(yǔ)

(1.貴州大學(xué) 大數(shù)據(jù)與信息工程學(xué)院，貴州 貴陽(yáng) 550025；2.貴州大學(xué) 檔案館，貴州 貴陽(yáng) 550025)

由于云計(jì)算模式能夠?qū)Ψ稚⒌摹悩?gòu)系統(tǒng)中的檔案數(shù)字資源、計(jì)算資源進(jìn)行有效集成和共享，開發(fā)新型的存儲(chǔ)與計(jì)算共享架構(gòu)，能夠建立起區(qū)域內(nèi)聯(lián)動(dòng)的運(yùn)行機(jī)制[1]。所以目前已經(jīng)有越來(lái)越多的檔案館將其業(yè)務(wù)運(yùn)行在云平臺(tái)上，不僅可以節(jié)省資金，減少工作量，并且能夠更好地共享資源。作為負(fù)責(zé)為業(yè)務(wù)系統(tǒng)提供計(jì)算和存儲(chǔ)資源且保證業(yè)務(wù)系統(tǒng)能夠正常運(yùn)行的虛擬機(jī)是云平臺(tái)的基礎(chǔ)是其核心部件[2]，所以為了預(yù)警保障云平臺(tái)的穩(wěn)定運(yùn)行，對(duì)虛擬機(jī)異常進(jìn)行檢測(cè)是其中重要的措施。由于傳統(tǒng)SVM不能處理海量數(shù)據(jù)，且不具備在線學(xué)習(xí)能力，不能進(jìn)行實(shí)時(shí)分類，所以不能滿足云環(huán)境下的異常檢測(cè)要求，所以文章使用具備在線學(xué)習(xí)能力且需求更少內(nèi)存能夠處理海量數(shù)據(jù)的LASVM算法來(lái)進(jìn)行異常檢測(cè)。

1 支持向量機(jī)

1.1 支持向量機(jī)原理

作為一種流行的機(jī)器學(xué)習(xí)算法，支持向量機(jī)[3](Support Vector Machines,SVM)在模式識(shí)別、回歸分析、函數(shù)估計(jì)、時(shí)間序列預(yù)測(cè)等領(lǐng)域都得到了長(zhǎng)足的發(fā)展[4]，它是以統(tǒng)計(jì)學(xué)習(xí)理論[5-6]VC維理論和結(jié)構(gòu)風(fēng)險(xiǎn)最小化原理為基礎(chǔ)的。

支持向量機(jī)是一種二類分類模型，它是在感知器(Perceptron)基礎(chǔ)上發(fā)展而來(lái)，可以表述為以特征空間上的間隔最大的線性分類器為其基本模型，以最大化間隔為其目的，最終轉(zhuǎn)化為一個(gè)凸二次規(guī)劃問(wèn)題的求解[3]的機(jī)器學(xué)習(xí)方法。

圖1 超平面間隔示意

f(x)=sgn(wTx+b)

(1)

根據(jù)幾何知識(shí)，wTx+b=+1和wTx+b=-1兩個(gè)平行超平面間的間隔為2/‖w‖，此時(shí)其數(shù)學(xué)模型類似地描述為

(2)

其中，ξi(ξi≥0)為松弛因子；C為懲罰因子；φ(x)為非線性情形下的映射函數(shù)。這是一個(gè)典型的凸二次規(guī)劃。利用最優(yōu)化知識(shí)，引入Lagrange函數(shù)

(3)

其中，αi≥0,μi≥0是Lagrange乘子。

引入核函數(shù)K(xi,xj)=φ(xi)·φ(xj)來(lái)代替內(nèi)積xiTxj,可得其對(duì)偶規(guī)劃為

(4)

1.2 SMO算法

標(biāo)準(zhǔn)SVM訓(xùn)練算法可以歸結(jié)為求解一個(gè)具有線性不等式約束的二次規(guī)劃(Quadratic Programming,QP)問(wèn)題。歷來(lái)解決式(4)的二次規(guī)劃問(wèn)題是構(gòu)造支持向量機(jī)的核心問(wèn)題，在Osuna[7]等提出的使用一系列小規(guī)模的子QP問(wèn)題替代標(biāo)準(zhǔn)SVM的QP問(wèn)題的分解算法基礎(chǔ)上，由微軟研究院的John Platt[8]發(fā)明的序列最小優(yōu)化(Sequential Optimal Minimization,SMO)算法被認(rèn)為是解決SVM問(wèn)題的最優(yōu)秀算法之一。它將問(wèn)題分解為一系列只含有兩個(gè)變量的最小QP問(wèn)題，避免了一般二次規(guī)劃方法過(guò)大的空間需求，使實(shí)現(xiàn)變得簡(jiǎn)單高效。

為了方便，令αiyi→αi，可將式(4)的對(duì)偶規(guī)劃寫作

(7)

SMO算法類似Vapnik[10]提出的共軛梯度法，都是通過(guò)不斷的搜索，來(lái)尋求最佳的下降方向。每個(gè)方向搜索都是通過(guò)當(dāng)前的向量α和增加的指定方向u。從而產(chǎn)生一個(gè)新的彈性向量α+λu，所以其最優(yōu)解為

λ*=argmaxW(α+λu)
s.t. 0≤λ≤φ(α,u)

(8)

其中，上邊界φ(α,u)確保α+λu是可行的，表達(dá)式為

(9)

對(duì)式(8)中的向量α分別求每個(gè)方向的導(dǎo)數(shù)，則可得到最優(yōu)解

(10)

其中，Kij=K(xi,xj)，gk=?W(α)/?αk=yk-∑iαiK(xi,xk)是W(α)的梯度。

SMO的基本思路是每次迭代過(guò)程中只調(diào)整相應(yīng)的兩個(gè)樣本點(diǎn)的αi和αj。通常使用一個(gè)微小的正容忍度τ>0，選那些使得φ(α,u)>0并且gi-gj>τ的u。這樣可以定義叫做τ違反對(duì)(i,j)

(11)

SMO算法的流程如下：

(1)將α設(shè)置為0，并且計(jì)算初始梯度g；

(2)選擇一個(gè)τ違反對(duì)(i,j)，若不存在則跳出程序g；

(3)λ←min{(gi-gj)/(Kii+Kjj-2Kij)，Bi-αi，αj-Aj}

αi←αi+λ，αj←αj-λ

gs←gs-λ(Kis-Kjs) ?s∈S

(4)重復(fù)步驟(2)。

2 在線主動(dòng)LASVM

由于傳統(tǒng)SVM不能處理海量數(shù)據(jù)集，除了在降低傳統(tǒng)QP問(wèn)題求解的復(fù)雜度的研究外，還有研究者提出了一些新的優(yōu)化方法，比如使標(biāo)準(zhǔn)SVM具備增量學(xué)習(xí)(Incremental Learning)算法的能力[9-10]。亦即是使用增量學(xué)習(xí)中的在線學(xué)習(xí)(Online Learning)來(lái)改善標(biāo)準(zhǔn)支持向量機(jī)在遇到當(dāng)訓(xùn)練集規(guī)模很大時(shí)，出現(xiàn)的訓(xùn)練速度慢、算法復(fù)雜、效率低，且在初期就獲得一個(gè)完備的訓(xùn)練數(shù)據(jù)集是很困難的問(wèn)題。

LASVM[11]算法是由Bordes和Bottou最早提出的，它是一種采用傳統(tǒng)軟間隔模型，對(duì)SMO算法中挑選α對(duì)的過(guò)程進(jìn)行變形的一種算法。它有兩個(gè)潛在的優(yōu)勢(shì)，首先它能夠在線學(xué)習(xí)和主動(dòng)學(xué)習(xí)，其次SVM對(duì)于大數(shù)據(jù)集的計(jì)算需要大量時(shí)間，近似算法處理速度更快，占用內(nèi)存更少，更適合處理大數(shù)據(jù)集。

這種方法由稱之為PROCESS和REPROCESS的兩種方向搜索步驟構(gòu)成。和SMO算法相似，每種方向搜索每回都只選取兩個(gè)樣本。PROCESS至少能夠選擇一個(gè)當(dāng)前判別式的非支持向量，它可以改變這個(gè)樣本的α值，使其成為支持向量將其加入支持向量集。REPROCESS處理當(dāng)前判別式中的兩個(gè)支持向量，它可以將一個(gè)或者兩個(gè)支持向量的α值改為0，從而使其不再成為支持向量，然后將其移出。

對(duì)于PROCESS步驟，其目的是試圖添加一個(gè)樣本k?S到當(dāng)前的支持向量集中。其具體的步驟如下

(1)如果k∈S樣本，那么跳出程序；

(2)αk←0，gk←yk-∑s∈SαsKks，S←S∪{k}

如果yk=+1，那么i←k，j←arg mins∈Sgs且αs>As；

如果yk=-1，那么j←k，i←arg maxs∈Sgs且αs

(3)如果(i,j)不是一個(gè)τ違反對(duì)，那么跳出程序；

(4)λ←min{(gi-gj)/(Kii+Kjj-2Kij)，Bi-αi，αj-Aj}

αi←αi+λ，αj←αj-λ

gs←gs-λ(Kis-Kjs) ?s∈S。

第二個(gè)步驟是REPROCESS，其目的是從S集中移除某些元素。具體的步驟如下

(1)i←arg maxs∈Sgs且αs

j←arg mins∈Sgs且αs>As；

(2)如果(i,j)不是一個(gè)τ違反對(duì)，那么跳出程序；

(3)λ←min{(gi-gj)/(Kii+Kjj-2Kij)，Bi-αi，αj-Aj}

αi←αi+λ，αj←αj-λ

gs←gs-λ(Kis-Kjs) ?s∈S；

(4)i←arg maxs∈Sgs且αs

j←arg mins∈Sgs且αs>As

對(duì)于s∈S中所有αs=0的向量

如果ys=-1且gs≥gi，那么S=S-{s}

如果ys=+1且gs≤gj，那么S=S-{s}；

(5)b←(gi+gj)/2，δ←gi-gj。

有了PROCESS和REPROCESS模塊后，可以搭建LASVM的總體框架，具體的算法流程如圖2所示。

LASVM除了可以在線的進(jìn)行訓(xùn)練，即在每給出一個(gè)連續(xù)的實(shí)時(shí)隨機(jī)樣本時(shí)，都會(huì)更新內(nèi)部支持向量以及其參數(shù)外。LASVM也可以在樣本集充足的情況下，作為一個(gè)批量學(xué)習(xí)的優(yōu)化算法，每次隨機(jī)地抽取一個(gè)樣本作為訓(xùn)練樣本進(jìn)行訓(xùn)練。

圖2 LASVM流程圖

3 不平衡數(shù)據(jù)集處理

3.1 KDD-CUP99數(shù)據(jù)集

該數(shù)據(jù)集是哥倫比亞大學(xué)的Sal Stolfo教授和來(lái)自北卡羅萊納州立大學(xué)的Wenke Lee教授采用數(shù)據(jù)挖掘等技術(shù)，對(duì)美國(guó)國(guó)防部高級(jí)規(guī)劃署(DARPA)在模擬美國(guó)空軍局域網(wǎng)網(wǎng)絡(luò)下仿真各種用戶類型、各種不同的網(wǎng)絡(luò)流量和攻擊手段收集的TCP dump(*)網(wǎng)絡(luò)連接和系統(tǒng)審計(jì)數(shù)據(jù)集進(jìn)行了特征分析和數(shù)據(jù)預(yù)處理后形成的一個(gè)數(shù)據(jù)集。該數(shù)據(jù)集分為了大概500萬(wàn)條網(wǎng)絡(luò)連接記錄的訓(xùn)練集和大概200萬(wàn)條網(wǎng)絡(luò)連接記錄的測(cè)試集。在1999年舉行的KDD CUP競(jìng)賽中被用于比賽，成為著名的KDD99數(shù)據(jù)集[12]。KDD99數(shù)據(jù)集在基于計(jì)算智能的網(wǎng)絡(luò)入侵檢測(cè)研究中常作為網(wǎng)絡(luò)入侵檢測(cè)領(lǐng)域的事實(shí)基準(zhǔn)，當(dāng)做標(biāo)準(zhǔn)數(shù)據(jù)集使用。

3.2 歸一化(Normalizatio)

由于原數(shù)據(jù)集過(guò)于龐大，隨機(jī)選取10%數(shù)據(jù)集作為實(shí)驗(yàn)數(shù)據(jù)，原數(shù)據(jù)集包含包含4類攻擊和正常標(biāo)簽，由于主要進(jìn)行異常檢測(cè)，不需要知道具體異常類型，本文使用了二分類，所以將所有正常和異常數(shù)據(jù)分別標(biāo)記為+1和-1，如表1所示。

表1 歸一化后的訓(xùn)練數(shù)據(jù)集類別和樣本數(shù)

KDD-CUP99數(shù)據(jù)集每條數(shù)據(jù)有41個(gè)屬性，其中34個(gè)是連續(xù)型變量，7個(gè)是離散型變量，其中protocoI_type、service、fIag3個(gè)屬性為標(biāo)稱屬性，首先要對(duì)其進(jìn)行數(shù)值化處理。又由于每個(gè)屬性的取值范圍不同，且取值范圍都為正，所以再進(jìn)行范圍為0～1的歸一化處理，從而避免了不同量綱的選取對(duì)計(jì)算產(chǎn)生的巨大影響。

3.3 過(guò)采樣(Over-Sampling)

當(dāng)面臨不平衡數(shù)據(jù)集的時(shí)候，機(jī)器學(xué)習(xí)算法傾向于產(chǎn)生并不令人滿意的分類器[13]。顯然在總共494 021條數(shù)據(jù)中，正常樣本只占大約19.7%，是一個(gè)典型的不平衡數(shù)據(jù)集，會(huì)影響訓(xùn)練出的分類器的性能，本文采用重采樣技術(shù)中的隨機(jī)過(guò)采樣方法處理訓(xùn)練數(shù)據(jù)集，通過(guò)隨機(jī)復(fù)制正常標(biāo)簽數(shù)據(jù)來(lái)增加正常實(shí)例數(shù)量，從而平衡數(shù)據(jù)集，最終形成正常數(shù)據(jù)和異常數(shù)據(jù)各396 743條總共793 486條數(shù)據(jù)的訓(xùn)練數(shù)據(jù)集。

4 應(yīng)用LASVM方法的入侵檢測(cè)實(shí)驗(yàn)

4.1 基于網(wǎng)格搜索算法的參數(shù)優(yōu)化

懲罰因子和核函數(shù)中的參數(shù)是影響支持向量機(jī)性能的主要參數(shù)，因?yàn)槲恼碌暮撕瘮?shù)使用徑向基核函數(shù)(Radical Basis Kernel Function，RBF核)K(xi,xj)=exp(-gamma×‖xi-xj‖2)，所以需要尋找合適的懲罰因子C和RBF核函數(shù)中的控制因子g=1/σ2。

本文使用網(wǎng)格搜索法(Grid Search Algorithm，GSA)來(lái)進(jìn)行參數(shù)尋優(yōu)，網(wǎng)格搜索法是一種最基本的參數(shù)優(yōu)化算法，適合同時(shí)從不同的增長(zhǎng)方向并行搜索多維數(shù)組。具體流程圖如圖3所示[14]。

圖3 基于網(wǎng)格搜索算法的SVM參數(shù)尋優(yōu)流程圖

使用分層抽樣的方法從訓(xùn)練數(shù)據(jù)集中抽取50 000條數(shù)據(jù)使用網(wǎng)格搜索的方法進(jìn)行參數(shù)尋優(yōu)。設(shè)置懲罰因子C和RBF核函數(shù)中的控制因子g的范圍分別為2-15≤C≤215，2-15≤g≤215，步長(zhǎng)C_step=0.5,g_step=0.5,采用K=10的10折交叉驗(yàn)證方法。

通過(guò)訓(xùn)練最終得到當(dāng)C=256，g=1.0時(shí)準(zhǔn)確率最高，即為最優(yōu)參數(shù)。同時(shí)得到訓(xùn)練出的不同參數(shù)值下的準(zhǔn)確率梯度圖，如圖4所示。

圖4 參數(shù)C和g的準(zhǔn)確率梯度圖

4.2 LASVM和LibSVM的對(duì)比實(shí)驗(yàn)

實(shí)驗(yàn)硬件環(huán)境是Intel(R) Xeon(R) E7 2.00 GHz CPU，8 GB RAM，軟件環(huán)境基于VMWare虛擬機(jī)下的CentOS 7操作系統(tǒng)，以VISUAL C++ 2010實(shí)現(xiàn)LASVM算法，支持向量機(jī)選用C-SVM，核函數(shù)選用徑向基函數(shù)，其中C=256，g=1.0。

LibSVM[15]是由臺(tái)灣大學(xué)林智仁(Lin Chih-Jen)教授等開發(fā)設(shè)計(jì)的目前廣泛使用的經(jīng)典離線學(xué)習(xí)SVM包，它使用SMO算法解決QP問(wèn)題。所以選用LibSVM作為對(duì)比，從準(zhǔn)確性、內(nèi)存占用量等方面驗(yàn)證LASVM算法的效果。其中異常檢測(cè)系統(tǒng)的評(píng)價(jià)標(biāo)準(zhǔn)如下：

精確度(Accuracy)是指所有正確檢測(cè)出來(lái)的正常和異常記錄在總樣本中所占比例，表示為

(12)

查準(zhǔn)率(Precision)是指被檢測(cè)出來(lái)的真正是異常記錄的數(shù)目在總的入侵記錄中所占比例，表示為

(13)

查全率(Recall)是指真正的攻擊記錄中被檢測(cè)出來(lái)的占所有攻擊記錄的比例，表示為

(14)

F-Score是Precision的Recall的調(diào)和平均數(shù)，是用來(lái)評(píng)估一個(gè)檢測(cè)系統(tǒng)好壞的度量，表示為

(15)

使用之前平衡過(guò)的訓(xùn)練集和測(cè)試集進(jìn)行實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果如表2～表4所示。

表2 LibSVM與LASVM檢測(cè)結(jié)果比較(C=256，g=1.0)

表3 LibSVM與LASVM檢測(cè)性能比較(C=256，g=1.0)

表4 libSVM與LASVM進(jìn)程占用的物理內(nèi)存比較(C=256，g=1.0)

從表2和表3可以看出，與LibSVM相比，LASVM的混淆矩陣TP、FP、FN、TN的差距分別是-0.14%、-0.63%、21.33%、0.07%，即二類錯(cuò)誤率稍高，其他接近LibSVM。Accuracy、Precision、Recal、F-Score的差距分別為0.03%、0.11%、-0.10%、0.04%，和LibSVM基本一致，都能夠達(dá)到較好的分類效果，但其支持向量數(shù)量更少。

從表4可以看出，在對(duì)同一個(gè)數(shù)據(jù)集進(jìn)行訓(xùn)練時(shí)，設(shè)置同等大小緩存情況下，由于LASVM具備在線學(xué)習(xí)能力，不需要一次性將整個(gè)數(shù)據(jù)集加入內(nèi)存進(jìn)行訓(xùn)練，所以占用的物理內(nèi)存量要比LibSVM少89.17%。且由圖5可以看到在以1 GB緩存為基點(diǎn)的對(duì)比不同緩存大小情況下的訓(xùn)練時(shí)間變化上，LASVM算法在不同緩存大小情況下，訓(xùn)練時(shí)間變化率不大，對(duì)內(nèi)存資源的要求更低。由于LASVM算法對(duì)物理內(nèi)存的消耗更少，且可在較少緩存下即可實(shí)現(xiàn)較快的訓(xùn)練速度，所以LASVM算法對(duì)于海量數(shù)據(jù)集有更好的適應(yīng)性。

圖5 LibSVM與LASVM在不同緩存大小情況下訓(xùn)練時(shí)間的變化

實(shí)驗(yàn)表明，LASVM算法在具備良好分類效果的同時(shí)，還能處理更大的數(shù)據(jù)集，且對(duì)內(nèi)存資源的消耗更少，還具有在學(xué)學(xué)習(xí)能力，能夠進(jìn)行實(shí)時(shí)檢測(cè)的優(yōu)點(diǎn)。

5 結(jié)束語(yǔ)

通過(guò)理論分析和對(duì)網(wǎng)絡(luò)數(shù)據(jù)的實(shí)驗(yàn)驗(yàn)證，說(shuō)明LASVM算法對(duì)大數(shù)據(jù)集具有較好的分類性能的同時(shí)，對(duì)內(nèi)存的需求更低，并且還能夠進(jìn)行在線和主動(dòng)學(xué)習(xí)，達(dá)到實(shí)時(shí)處理數(shù)據(jù)的目的。較之普通SVM算法，能夠更好地適用于在云環(huán)境下檢測(cè)虛擬機(jī)異常。下一步工作，將使用LASVM算法對(duì)真實(shí)云環(huán)境下采集到的虛擬機(jī)性能指標(biāo)數(shù)據(jù)集進(jìn)行測(cè)試并進(jìn)一步改進(jìn)以提高檢測(cè)精確度。

[1] 祝慶軒,桑毓域,方昀.基于云計(jì)算的檔案信息資源共享模式研究[J].蘭臺(tái)世界,2011(15):8-9.

[2] 王桂平.云環(huán)境下面向可信的虛擬機(jī)異常檢測(cè)關(guān)鍵技術(shù)研究[D].重慶:重慶大學(xué),2015.

[3] 克里斯蒂亞尼尼,Johnshawe-Taylor.支持向量機(jī)導(dǎo)論:英文版[M].北京:機(jī)械工業(yè)出版社,2005.

[4] 吉衛(wèi)衛(wèi),譚曉陽(yáng).SVM及其魯棒性研究[J].電子科技,2012,25(5):97-100.

[5] 瓦普尼克.統(tǒng)計(jì)學(xué)習(xí)理論[M].北京:電子工業(yè)出版社,2015.

[6] Vapnik V. Statistical learning theory[M].London:DBLP,2010.

[7] Osuna E,Freund R,Girosi F.An improved training algorithm for support vector machines[C].Germany:Neural Networks for Signal Processing,IEEE Xplore,1997.

[8] Platt J C.Fast training of support vector machines using sequential minimal optimization[M].MA,USA:MIT Press,1999.

[9] Li Z Y,Zhang J F,Hu S S.Incremental support vector machine algorithm based on multi-kernel learning[J]. 系統(tǒng)工程與電子技術(shù):英文版,2011,22(4):702-706.

[10] Nguyen-Tuong D,Peters J.Incremental online sparsification for model learning in real-time robot control[J].Neurocomputing,2011,74(11):1859-1867.

[11] Bordes A,Ertekin S,Weston J,et al.Fast kernel classifiers with online and active learning[J].Journal of Machine Learning Research,2005,6(6):1579-1619.

[12] 張新有,曾華燊,賈磊.入侵檢測(cè)數(shù)據(jù)集KDD CUP99研究[J].計(jì)算機(jī)工程與設(shè)計(jì),2010,31(22):4809-4812.

[13] 吳磊,房斌,刁麗萍,等.融合過(guò)抽樣和欠抽樣的不平衡數(shù)據(jù)重抽樣方法[J].計(jì)算機(jī)工程與應(yīng)用,2013,49(21):172-176.

[14] Wang J,Zhang L,Chen G.A parameter optimization method for an SVM based on improved grid search algorithm[J].Applied Science & Technology,2012(3):28-31.

[15] Lin C H,Liu J C,Ho C H.Anomaly detection using LibSVM training tools[C].Beijing:International Conference on Information Security and Assurance,IEEE,2008.