一種基于有監(jiān)督局部決策分層支持向量機的異常檢測方法

徐琴珍 楊綠溪

(東南大學(xué)信息科學(xué)與工程學(xué)院 南京 210096)

1 引言

入侵檢測技術(shù)是網(wǎng)絡(luò)安全防護系統(tǒng)構(gòu)成的重要環(huán)節(jié)，通過從計算機網(wǎng)絡(luò)系統(tǒng)中收集的若干關(guān)鍵信息分析網(wǎng)絡(luò)中是否存在入侵行為。根據(jù)不同的入侵檢測分析方法，網(wǎng)絡(luò)入侵檢測技術(shù)可分為濫用檢測和異常檢測兩類[1]。濫用檢測技術(shù)已經(jīng)廣泛應(yīng)用于絕大多數(shù)商用網(wǎng)絡(luò)入侵檢測系統(tǒng)，對已知的攻擊模式能實現(xiàn)高效檢測，而對未知的攻擊模式無法做出預(yù)測；而異常檢測技術(shù)通過建立主體的正常行為模型，發(fā)現(xiàn)異常行為，從而能對未知攻擊作出預(yù)測，異常檢測作為一個開放性研究課題，已經(jīng)受到越來越廣泛的關(guān)注。

在機器學(xué)習(xí)任務(wù)中，給定樣本特征集的情況下，異常檢測問題可以將看作高維特征空間中的多分類預(yù)測問題：從給定的各維特征數(shù)據(jù)中學(xué)習(xí)到檢測所需的最佳特征信息組合，構(gòu)建決策超曲面，實時準確地預(yù)測出“正?！被颉肮簟痹L問。針對異常檢測問題的常用機器學(xué)習(xí)方法包括：(1)基于符號式學(xué)習(xí)模型的檢測方法，學(xué)習(xí)結(jié)果可以表示成明確的推理規(guī)則集。例如，文獻[2]提出了一種基于數(shù)據(jù)挖掘技術(shù)的RIPPER規(guī)則算法，通過遺傳算法(GA)與RIPPER算法相結(jié)合的檢測方式，抽取有效特征和構(gòu)建檢測規(guī)則集；Cheng等人[3]提出了一種基于有監(jiān)督?jīng)Q策樹與無監(jiān)督貝葉斯聚類法相結(jié)合的異常檢測方法，實現(xiàn)檢測率的提高和誤檢率的下降。(2)基于非符號式學(xué)習(xí)模型的檢測方法，學(xué)習(xí)結(jié)果以權(quán)值、系數(shù)或其他數(shù)值序列的形式存儲。例如，基于人工免疫系統(tǒng)的檢測方法：Jamie等人[4]提出的以多級信息源為輸入數(shù)據(jù)的人工免疫系統(tǒng)入侵檢測方法，Dasgupta等人[5]提出的運用基于免疫算法的技術(shù)檢測和描述網(wǎng)絡(luò)入侵模式?；谏窠?jīng)網(wǎng)絡(luò)的方法：Thomas等人[6]運用通過多種檢測方法的組合實現(xiàn)入侵檢測精確率的全局優(yōu)化，有監(jiān)督學(xué)習(xí)的神經(jīng)網(wǎng)絡(luò)模型用于調(diào)整檢測某種特定入侵方式的學(xué)習(xí)方法的權(quán)重，即用于衡量多種檢測方法集合中某種方法的有效性；基于支持向量機(SVM)的方法：Charles等人[7]采用支持向量機與線性判決分析相結(jié)合的方法來提高支持向量機的異常檢測精確率和線性判決分析的速度。此外，基于非符號式學(xué)習(xí)模型的異常檢測方法還包括基于遺傳算法的檢測法、基于隱馬爾可夫過程的異常檢測技術(shù)、基于粗糙集的異常檢測方法等[1]。

這些方法為異常檢測提供了卓有成效的技術(shù)支持，并為進一步的研究提供了堅實的理論和實踐基礎(chǔ)，同時也遇到了共同的問題：包含多種攻擊的異常檢測問題是一個具有高維特征空間的高度復(fù)雜的多分類問題；檢測所需的最佳特征信息組合往往無法先驗獲得，而冗余的特征信息往往會意外增加學(xué)習(xí)算法搜索解空間的復(fù)雜度，降低學(xué)習(xí)的效率；此外，冗余的特征信息還可能增加決策曲面的復(fù)雜度，影響學(xué)習(xí)結(jié)果的泛化性，甚至造成“維度災(zāi)難”。為此，本文提出了一種基于有監(jiān)督局部決策的分層支持向量機(HSVM)異常檢測方法。通過HSVM的樹型結(jié)構(gòu)在訓(xùn)練信號的監(jiān)督下實現(xiàn)復(fù)雜異常檢測問題的“分而治之”，并在每個層次上，為當前的局部決策曲面選擇最優(yōu)的特征信息子集，簡化問題空間，降低學(xué)習(xí)模型的復(fù)雜度，從而提高檢測的泛化性和效率。

2 支持向量機

支持向量機是由Vapnik等學(xué)者最早提出的一種基于結(jié)構(gòu)風(fēng)險最小化思想的機器學(xué)習(xí)方法[8]，它集成了機器學(xué)習(xí)領(lǐng)域的最大間隔超平面、Mercer核、凸二次規(guī)劃等多項技術(shù)，在包括異常檢測在內(nèi)的若干挑戰(zhàn)性應(yīng)用場景中表現(xiàn)出了優(yōu)良的性能[9]。支持向量機中最簡單的模型是針對線性可分情況下的最大間隔分類器，即給定線性可分樣本：S={(xi, yi)|i=1,2,…,l }，其中xi為第i個觀測樣本，yi∈{+1,?1}為xi對應(yīng)的類別，求解最優(yōu)化問題：min, s.t.，得到最大幾何間隔為γ=1/的最大間隔超平面(w, b)。

在本文研究的異常檢測問題中，特征空間無法線性分開，需要引入松弛變量ξi和懲罰項參數(shù)C，需要求解的最優(yōu)化問題轉(zhuǎn)化為：針對這一情況，可以引入核函數(shù)K(˙)在隱式定義的特征空間中實現(xiàn)線性可分，通過拉格朗日定理可以將問題表述成對偶形式[8]：0≤αi≤C, i=1,2,…,l 。由此得到的決策規(guī)則為，通過對f(x)的符號判別實現(xiàn)支持向量的二分類功能。

在本文提出的方法中，支持向量機用于實現(xiàn)復(fù)雜決策過程中的局部最優(yōu)決策，即作為HSVM中間節(jié)點上的嵌入學(xué)習(xí)模塊。

3 基于HSVM學(xué)習(xí)模型的異常檢測方法

3.1 HSVM學(xué)習(xí)模型的結(jié)構(gòu)

HSVM的整體結(jié)構(gòu)與二叉樹類似(如圖1所示)，中間節(jié)點實現(xiàn)局部決策，葉節(jié)點標識類別。區(qū)別在于在每個中間節(jié)點上嵌入了可以提取相對復(fù)雜特征信息組合的SVM。

圖1 HSVM學(xué)習(xí)模型示例

本文提出基于HSVM學(xué)習(xí)模型的異常檢測方法，主要出于以下3方面的考慮：首先，二叉樹結(jié)構(gòu)的性質(zhì)使模型能夠根據(jù)局部決策訓(xùn)練信號將復(fù)雜的異常檢測問題分解，而后在不同的層次上以相對降低的復(fù)雜度解決子問題；其次，與簡單的決策樹中間節(jié)點相比，嵌入SVM模塊的節(jié)點能夠在局部決策中提取更加有效的特征信息；此外，HSVM相比于其它多分類支持向量機(如DAGSVM, 1-V-1 SVM, 1-V-R SVM)而言，具有更高的檢測效率。

3.2 訓(xùn)練信號的生成

對于二分類問題(如在異常檢測中只需區(qū)分是正常訪問或是攻擊訪問的情況)，訓(xùn)練樣本中的類別標識可直接作為二叉樹節(jié)點分裂時的訓(xùn)練信號。而對于類別數(shù)大于2的多分類問題(例如異常檢測中，除了檢測出正常訪問和攻擊訪問外，還需預(yù)測具體的攻擊種類)，在中間節(jié)點分裂時，需要在訓(xùn)練信號的監(jiān)督下，將包含多類的訓(xùn)練樣本劃分為兩個子集，因此需要為中間節(jié)點的分裂構(gòu)建局部決策訓(xùn)練信號。

在中間節(jié)點上，通過合適的準則構(gòu)建訓(xùn)練信號，可以增加學(xué)習(xí)模型檢測的穩(wěn)定性。本文結(jié)合學(xué)習(xí)模型的二叉樹結(jié)構(gòu)，通過信息增益準則構(gòu)建訓(xùn)練信號。信息增益準則是生成決策樹時采用的節(jié)點分裂準則之一[10]，在c4.5算法中，可以通過信息增益量選取決策樹中間節(jié)點分裂所需的有效特征。與之不同的是，在本文的HSVM樹中，信息增益準則用于選擇生成的訓(xùn)練信號，而非特征。

設(shè)中間節(jié)點上的樣本集合X由k類訪問模式(包括正常訪問和各類攻擊訪問)組成：X={c1,…,ck}，則該樣本集的信息熵為

產(chǎn)生的信息增益為

需要選擇的訓(xùn)練信號為能夠產(chǎn)生最大信息增益的T*為

3.3 局部決策曲面上的特征選擇

SVM的決策曲面邊界對某一特征的敏感程度體現(xiàn)了該特征對分類決策的影響程度，因此，在每個中間節(jié)點的局部決策曲面訓(xùn)練中，選擇相對有效的特征子集在一定程度上有利于促進HSVM結(jié)構(gòu)的簡化和異常檢測泛化性的增強。給定樣本集X={(xi, yi),i=1,2,…,l }，和核函數(shù)K(˙)，其中xi∈RN為第i次觀測樣本，對應(yīng)的訓(xùn)練信號為yi∈{?1,+1}，則SVM決策邊界的平方倒數(shù)為

若K(˙)為高斯核函數(shù)，則決策邊界對第n維特征的敏感程度為

在Sindhwani等提出的基于最大輸出信息的特征選擇方法[11]中，第n維特征的信用度的衡量需要考慮兩個因素：(1)SVM決策邊界對于該特征的敏感度；(2)單個二分類SVM的信用度。由于多分類SVM一般由多個二分類SVM按照一定規(guī)則組合完成多分類任務(wù)，在訓(xùn)練過程中，所有的二分類SVM都依據(jù)特征信用度值在相同的特征子集上訓(xùn)練學(xué)習(xí)，從而在一定程度上導(dǎo)致了每個二分類SVM依然包含了部分冗余的特征信息，而這些冗余的特征信息卻可能是影響其它二分類SVM決策的重要信息。對于多分類的異常檢測而言，各維特征的重要性對于不同的局部決策曲面往往會隨子問題而變化，即各二分類SVM局部決策時所需要的特征子集可能不同。為此，我們結(jié)合HSVM檢測模型分而治之的樹型結(jié)構(gòu)，改進了基于最大信息輸出的特征選擇方法，針對每個中間節(jié)點上局部決策曲面的不同情況靈活地選擇不同的特征子集，使之更適用于多分類的異常檢測問題。

為了實現(xiàn)局部決策曲面上特征自組織選擇的差異性，各維特征在不同局部決策過程中的重要性可以直接以式(7)計算的局部決策邊界對該維特征的敏感度值來衡量，控制特征子集中成員的選擇，同時還需要控制特征子集的規(guī)模。本文在Sindhwani等人的方法上作了改進，以分類邊界對特征的敏感度值的累積量比率來優(yōu)化特征的自組織選擇。決策邊界對特征的敏感度值的累積量比率定義為

其中Dni，ni∈{1,2,…,N}為敏感度值序列{Dn,n=1,2,…,N}經(jīng)降序排列后的結(jié)果，m′為Sr達到給定的閾值Sr*時選用的最佳特征子集的維數(shù)。式(8)在形式上與樣本固有維數(shù)的計算類似，但有著本質(zhì)的區(qū)別。樣本固有維數(shù)以近鄰樣本點的協(xié)方差矩陣特征值的累積量為基礎(chǔ)，為每個樣本計算近鄰點及其協(xié)方差矩陣的特征值，從而得出每個樣本的固有維數(shù)，樣本集的最終固有維數(shù)通過投票決定[12]；而m′的計算則依賴于邊界對各維特征敏感度值Dn，計算復(fù)雜度較固有維數(shù)的計算要低。

4 異常檢測結(jié)果及分析

為驗證本文提出的異常檢測方法，實驗選擇入侵檢測研究人員廣泛使用的KDD Cup 1999入侵檢測數(shù)據(jù)庫中的corrected觀測數(shù)據(jù)集[13]。

4.1 數(shù)據(jù)預(yù)處理

corrected數(shù)據(jù)含311029例樣本，每個觀測樣本含41維特征，在數(shù)據(jù)的預(yù)處理中，我們根據(jù)符號類別標簽將訪問樣例標示為4類攻擊和1類正常訪問：正常訪問樣例類別標示為1，共60593例；dos攻擊類別標示為2，共229853例；u2r攻擊類別標示為3，共70例；r2l攻擊類別標識為4，共16347例；probe攻擊類別標示為5，共4166例。由于u2r攻擊樣例稀少，我們將KDD Cup中kddcup.data_10_percent數(shù)據(jù)包中包含的52例u2r攻擊并入到實驗數(shù)據(jù)中。為改善樣例的極度不平衡狀況，實驗從corrected數(shù)據(jù)集中隨機抽取除u2r攻擊外的7878例訪問樣本，與corrected和kddcup.data_10_percent中的122例u2r攻擊樣例構(gòu)成含8000例訪問樣本的入侵檢測數(shù)據(jù)集，1/3作為訓(xùn)練樣本，2/3作為測試樣本。實驗給出的異常檢測數(shù)值結(jié)果為200次實驗結(jié)果的平均值。

4.2 數(shù)值結(jié)果對比及分析

圖2為在訓(xùn)練集上生成的HSVM異常檢測模型示例。為了在局部決策訓(xùn)練中最大限度地保留有用特征信息，Sr*閾值設(shè)為1，即在每個中間節(jié)點上構(gòu)建的特征子集中僅剔除對局部邊界的敏感度值為0的特征。

圖2 HSVM異常檢測模型示例

與圖2相對應(yīng)的各中間節(jié)點svmi上特征選擇的情況(特征子集規(guī)模N，信息增益IG)，以及訓(xùn)練信號TS對訓(xùn)練樣本的局部決策監(jiān)督情況如表1所示。以第1行數(shù)值為例說明表格中各項的關(guān)聯(lián)：svm1的TS為[2]/[1 3 4 5]，表示該節(jié)點選擇了當前樣本下具有最佳信息增益0.8467的訓(xùn)練信號，該訓(xùn)練信號將第2類訪問模式(dos攻擊)標示為正例，將1、3、4、5類訪問模式(正常訪問，u2r攻擊，r2l攻擊，probe攻擊)標示為反例。svm1在該訓(xùn)練信號監(jiān)督下完成當前節(jié)點上的局部二分類決策訓(xùn)練，根據(jù)各維特征對局部決策邊界的敏感度值，在給定的Sr*下從41維特征中選擇了21維對決策邊界有貢獻的特征構(gòu)成當點節(jié)點上的特征子集。在svm3和svm5這兩個中節(jié)點上的子樣本僅包含兩類訪問模式，因此可以不必計算信息增益，直接構(gòu)建訓(xùn)練信號。從圖2及其對應(yīng)的表1所示的訓(xùn)練情況說明，在不同的局部決策過程中，各SVM所需要的特征子集的規(guī)模和特征子集中的成員都會隨著局部決策任務(wù)的變化而變化，改進的特征選擇方法更好地適應(yīng)了決策曲面上特征自組織選擇的差異性需求。

表1 中間節(jié)點的訓(xùn)練情況

為進一步說明本文提出的異常檢測方法的有效性，我們將檢測結(jié)果與多種異常檢測方法進行了對比：多分類支持向量機(DAG-SVM、1-v-1-SVM和1-v-r-SVM)[14]異常檢測方法；采用啟發(fā)式方法構(gòu)建訓(xùn)練信號的支持向量機樹(CSVMT)檢測方法[12]；基于主分量分析法實現(xiàn)特征信息抽取后結(jié)合k近鄰法實現(xiàn)異常檢測的方法(PCA-KNN)，其中主分量分析的特征值的累積量和參照Sr*取為1；基于徑向基神經(jīng)網(wǎng)絡(luò)(RBF)的異常檢測方法。對比的指標包括：需要訓(xùn)練的二分類SVM數(shù)nsvm，每個二分類SVM構(gòu)建局部決策曲面需要的平均特征數(shù)nf，異常檢測精確率pd及其方差pstd，虛警率pf以及測試時間t(以HSVM的測試時間為單位1)，平均數(shù)值結(jié)果如表2所示。

由表2所示HSVM與其他異常檢測方法的數(shù)值結(jié)果對比可知：(1)與多分類支持向量機相比，由于DAG-SVM和1-v-1-SVM在兩兩配對的攻擊種類間訓(xùn)練二分類SVM，需要的SVM數(shù)為k(k?1)/2個，而1-v-r-SVM需要為某一類訪問模式和剩余訪問模式訓(xùn)練二分類SVM，因此需要k個二分類SVM，而HSVM則可以根據(jù)特征空間復(fù)雜度的不同，自適應(yīng)地調(diào)整SVM的數(shù)量；(2)與具有類似分層結(jié)構(gòu)的CSVMT相比，由于CSVMT采用啟發(fā)式方法構(gòu)建訓(xùn)練信號，具有很大的隨機性，由檢測精確率的方差對比可知，HSVM在最大信息增益訓(xùn)練信號的監(jiān)督下構(gòu)建的檢測模型具有更好的穩(wěn)定性；(3)與進行特征信息抽取的PCA-KNN檢測方法相比，HSVM所需的平均特征維數(shù)較小，且測試時無需進行特征坐標的轉(zhuǎn)換，能夠以更精簡的特征信息實現(xiàn)異常檢測；(4)此外，與包括RBF在內(nèi)的其他檢測方法相比，HSVM獲得了與其他方法相當甚至更優(yōu)越的異常檢測精確率和較低的虛警率；從檢測率的方差還可以看出HSVM具有更好的穩(wěn)定性；從檢測效率看，HSVM也能更好地符合實時快速檢測的要求。

表2 不同異常檢測方法的結(jié)果對比

5 結(jié)束語

本文針對包含多種攻擊模式的高維特征空間中的異常檢測問題，提出了一種基于有監(jiān)督局部決策的HSVM異常檢測方法。通過HSVM的二叉樹結(jié)構(gòu)實現(xiàn)復(fù)雜異常檢測問題的分而治之，通過信息增益準則構(gòu)建中間節(jié)點分裂所需的訓(xùn)練信號，監(jiān)督局部決策，提高檢測方法的穩(wěn)定性和局部決策的有效性；在檢測模型的中間節(jié)點上，以局部決策邊界對特征的敏感度為依據(jù)，自適應(yīng)地優(yōu)化入侵檢測的局部最優(yōu)特征子集(包括特征的選擇和特征子集規(guī)模的調(diào)整)，以優(yōu)化的特征子集訓(xùn)練中間節(jié)點上的SVM。實驗結(jié)果表明，本文提出的異常檢測方法能夠在在訓(xùn)練信號的局部決策監(jiān)督下構(gòu)建具有良好穩(wěn)定性的異常檢測學(xué)習(xí)模型，并能以更精簡的特征信息實現(xiàn)檢測精確率和檢測效率的提高。

[1] Tsang Chi-ho, Kwong Sam, and Wang Han-li. Genetic-fuzzy rule mining approach and evaluation of feature selection techniques for anomaly intrusion detection[J]. Pattern Recognition, 2007, 40(9): 2373-2391.

[2] Helmer G, Wong J S K, and Honavar V, et al.. Automated discovery of concise predictive rules for intrusion detection [J].Journal of Systems and Software, 2002, 60(3): 165-175.

[3] Cheng Xiang, Png Chin-yong, and Lim Swee-meng. Design of multiple-level hybrid classifier for intrusion detection system using Bayesian clustering and decision trees [J]. Pattern Recognition Letters, 2008, 29(7): 918-924.

[4] Jamie T and Uwe A. Information fusion in the immune system[J]. Information Fusion, 2010, 11(1): 35-44.

[5] Dasgupta D and Gonzalez F. An immunity-based technique to characterize intrusions in computer networks[J]. IEEE Transactions on Evolutionary Computation, 2002, 6(3):281-291.

[6] Thomas C and Balakrishnan N. Improvement in intrusion detection with advances in sensor fusion [J]. IEEE Transactions on Information Forensics and Security, 2009,4(3): 542-551.

[7] Charles J J, Das A, Lee B, and Seet B. CARRADS: cross layer based adaptive real-time routing attack detection system for MANETS [J]. Computer Networks, 2010, 54(7):1126-1141.

[8] Cristianini N and Shawe-Taylor J. An Introduction to Support Vector Machines and Other Kernel-based Learning Methods. New York: Cambridge University Press, 2000:93-122.

[9] Hernández-Pereira E, Suárez-Romero J A, Fontenla-Romero O, and Alonso-Betanzos A. Conversion methods for symbolic features: a comparison applied to an intrusion detection problem[J]. Expert Systems with Applications, 2009, 36(7):10612-10617.

[10] Quinlan J R. C4.5: Programs for Machine Learning [M]. San Mateo, California: Morgan Kaufmann publishers, 1993:17-26.

[11] Sindhwani V, Rakshit S, Deodhare D, Erdogmus D, Principe J C, and Nivogi P. Feature selection in MLPs and SVMs based on maximum output information[J]. IEEE Transactions on Neural Networks, 2004, 15(4): 937-948.

[12] 徐琴珍, 楊綠溪. 基于改進的混合學(xué)習(xí)模型的手寫阿拉伯數(shù)

字識別方法[J]. 電子與信息學(xué)報, 2010, 32(2): 433-438.

Xu Qin-zhen and Yang Lu-xi. An improved hybrid learning model based handwritten digits recognition approach [J].Journal of Electronics & Information Technology, 2010, 32(2):433-438.

[13] KDDCup 1999 Data, http://kdd.ics.uci.edu/databases/kddcup99/kddcup99.html, 2010.

[14] Hsu C W and Lin C J. A comparison of methods for multiclass support vector machines [J]. IEEE Transactions on Neural Networks, 2002, 13(2): 415-525.