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

徐琴珍 楊綠溪

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

1 引言

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

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

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

2 支持向量機

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

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

在本文提出的方法中，支持向量機用于實現復雜決策過程中的局部最優決策，即作為HSVM中間節點上的嵌入學習模塊。

3 基于HSVM學習模型的異常檢測方法

3.1 HSVM學習模型的結構

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

圖1 HSVM學習模型示例

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

3.2 訓練信號的生成

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

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

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

產生的信息增益為

需要選擇的訓練信號為能夠產生最大信息增益的T*為

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

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

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

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

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

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

4 異常檢測結果及分析

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

4.1 數據預處理

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

4.2 數值結果對比及分析

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

圖2 HSVM異常檢測模型示例

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

表1 中間節點的訓練情況

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

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

表2 不同異常檢測方法的結果對比

5 結束語

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

[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] 徐琴珍, 楊綠溪. 基于改進的混合學習模型的手寫阿拉伯數

字識別方法[J]. 電子與信息學報, 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.