基于Relief－SBS特征選擇算法的入侵檢測方法研究

楊云峰

(河池學院 計算機與信息科學系，廣西 宜州 546300)

1 概述

互聯網爆炸式的發展給人們生活帶來了很大的便利，并被廣泛應用于各種領域，人們在享受互聯網進步成果的同時，也面臨著其帶來的威脅。網絡安全與互聯網相伴相生，入侵檢測作為網絡安全的焦點技術，可以追溯到1980年，即J.A［1］在研討技術報告中首次提出的。此后，不斷有學者和研究人員深入研究和完善入侵檢測模型和應用技術手段，例如，1990年，Heberlein［2］開發的NSM系統(Network Security Monitor)，通過捕獲ICP/IP分組，直接把局域網上的網絡信息作為審計數據來源進行檢測。2007年，M.R［3］團隊提出的系統是基于誤用檢測代理的分布式入侵檢測，它通過Drools規則引擎和Snort配合使用，提高系統可擴展性。2008年，Aly El－Semary［4］主要針對入侵檢測動態日志問題，通過Apriori算法結合Kuok算法，動態產生模糊邏輯規則。2009年，Ya－Liding［5］等人提出的Apriori算法的神經特征搜索算法能有效提高檢測效率。

隨著網絡技術和存儲技術的迅猛發展，對入侵檢測技術的性能要求也越來越高，本文在仔細分析統計相關性的特征選擇算法(Relief)的基礎上，結合順序后向搜索算法，形成基于Relief－SBS特征選擇算法，將其應用在入侵檢測上，實驗表明該方法能夠提高入侵檢測的效率。

2 數據采集和預處理

入侵檢測的第一步是數據收集，如果收集的數據延時大、數據不完整，或是發生錯誤導致收集到錯誤的數據，入侵檢測性能就會下降甚至無意義。根據信息采集的不同，主要有兩種數據源:第一種是利用系統日志數據作為數據源，第二種是利用網絡數據作為數據源。基于實驗的局限性，難收集到各種攻擊數據，所以本實驗采用目前入侵檢測研究最廣泛使用的標準數據集—KDD99［6］數據集作為數據源，并采用kddcup.data_10_percent_corrected作為訓練集，corrected作為測試集。

KDD99數據集中的樣本特征共41維，主要包含的類型是:基本特征、內容特征、時間流量特征和主機流量特征等四類。由于本文實驗中采用的分類器為支持向量機，其僅能處理數值型數據，標準數據集中的原始數據含有名詞的離散型特征，因此要進行預處理，預處理主要有如下三步:

(1)重新對原始數據的類別標簽進行歸類。

(2)把離散型特征轉換成連續數值型特征。原來取值為0或1的離散型的特征值不變，取值為名詞的，根據所有特征分為多個子特征，并確保不同記錄之間的同一離散型特征差異相等。

(3)數值歸一化。設max和min是訓練集中某一特征的最大值和最小值。設歸一化后的數值范圍為［new_min，new_max］，則由原值u到新值v的映射關系為:

一般情況下，歸一化后的數值范圍可以有［－1，+1］和［0，1］兩種選擇。本文選擇［0，1］作為歸一化后的數值范圍。

數據預處理后，數據集的特征共計118維特征，如表1、2所示，每個特征名稱前面都有一個唯一的標號。完成了數據預處理后，數據集滿足了后續分類器的輸入要求，為特征選擇和分類做好了準備。

表1 預處理后的KDD99數據集的基本特征

表2 預處理后的KDD99數據集的內容、流量、主機流量特征

3 基于Relief－SBS的特征選擇算法描述

本文的特征選擇算法是在分析綜合統計相關性的特征選擇算法(Relief)與順序后向搜索算法的基礎上形成的。Relief算法是基于統計相關性的特征選擇算法，是由Kenji Kira和Larry Rendell提出的，當初是為了解決兩類分類中多個特征相互關聯與作用的問題［7］。其原理是依特征對近距離樣本的區分能力來評估特征，就是好的特征應該能夠使同一類別的樣本之間互相靠近，不同類別的樣本之間相互遠離。順序后向搜索算法是在特征子集中進行搜索時根據方向不同劃分的特征選擇算法。基于Relief與順序后向搜索的特征選擇算法在每一輪迭代后去除一個特征，并在每一輪迭代中，采用Relief算法的結果作為特征的評估標準。

算法流程如下:

輸入:訓練數據集Train;初始特征集 T0={Fj，j=1，2，…，N}及其對應權值 D［1…N］;分類器函數:λ=Classifier(訓練集，特征集)，λ為分類正確率;Relief算法函數:D［1…N］=Relief(Train，T)，D 按從大到小排序。初始化:Tbest=T0;λbest=Classifier(Train，T0);D［1…N］=0;for(i=1;i＜ =N－2;i++){D［1…N－i+1］=Relief(Train，T);//對訓練集 Train執行 Relief算法將特征權值最小的特征去除;獲得新的特征子集 T={Fj，j=1，2，…，N－i}，其對應權值為 D［1…N－i］;λ =Classifier(Train，T);if(λ＜λbest)break;Tbest=T;λbest=λ;}輸出:特征子集Tbest中的特征。

在Relief－SBS算法中，分類器函數——Classifier(訓練集，特征集)的選擇是比較靈活的。本文使用的分類器是支持向量機。

4 實驗結果與分析

4.1 實驗方案

為了更有利于全面考察特征算法的性能，檢測的結果同支持向量機結合起來，并采用了C－SVM和ν－SVM兩種支持向量機作為對特征子集進行評估的分類算法，特征提取上為了比較，還使用預處理后得到的全部特征118維進行實驗，所以形成了四種方案:(1)全部特征+C－SVM;(2)Relief－SBS特征選擇+CSVM;(3)全部特征+ν－SVM;(4)Relief－SBS特征選擇+ν－SVM。

Relief－SBS特征選擇+C－SVM算法在第65輪迭代后中止，也就是總共去除了原特征集118維特征中的64維特征，保留了54維特征，如表3所示。Relief－SBS特征選擇+ν－SVM的算法第70輪迭代后中止，也就是總共去除了原特征集118維特征中的69維特征，保留了49維特征，如表4所示。

表3 采用C－SVM評估的Relief－SBS特征選擇后保留的特征子集(54維)

表4 采用ν－SVM評估的Relief－SBS特征選擇后保留的特征子集(49維)

表4(續)

4.2 實驗性能評價指標

本實驗通過檢測率、虛警率、樣本平均代價三個指標作為入侵檢測系統的性能評價指標。對于入侵檢測系統，檢測率越高越好，虛警率越低越好，樣本平均代價越低越好，但是很難達到檢測率與虛警率同時達到最優的目標，這也是入侵檢測研究的重點之一。因為實際的網絡環境中，正常的樣本數龐大，攻擊的樣本比例小，所以極低的虛警率也可能產生大量的誤報警。

檢測率=正確檢測出來的攻擊樣本數/攻擊樣本總數。

虛警率=誤判為攻擊的正常樣本數/正常樣本總數。

其中，Cost(i，j)是標準數據庫KDD99入侵檢測競賽在對不同的分類器的分類結果進行評價與比較后所給出的錯分代價矩陣。每一行是正確類別:即樣本實際類別，即“正確類別”;每一列是輸出類別:即樣本被分類器分配的類別，矩陣元素表示錯分代價。本文將其作為與其它研究比較性能的基準。

CM(i，j)是指分類器輸出的混淆矩陣(Cofusion Matrix)，每一行是樣本實際類別，每一列是樣本被分類器分配的類別，矩陣元素代表分類器對應類別輸出的樣本數。

4.3 實驗結果

根據設計的實驗方案，實驗中選取用于支持向量機訓練與測試的參數C的取值包括:2－1、21、23、25、26、27、28、29、210、211、212、213、214、215、216共 15 種，σ 的取值包括:20、2－1、2－2、2－3、2－4、2－5、2－6、2－7、2－8、2－9、2－10共11種，它們取值的組合構成了一個網格。每種組合在訓練集上進行交叉驗證，表5列出實驗時部分組合結果，得知當C=29，σ=2－4時全部特征+C－SVM取得了最高的檢測率與最低的平均代價，當C=216，σ=2－3時Relief－SBS特征選擇+C－SVM取得了最高的檢測率與最低的平均代價，將最好結果的組合作為最優參數對支持向量機進行訓練，然后進行測試。得到最終實驗數據如表6所示。

表5 全部特征、Relief－SBS特征選擇分別與C－SVM在測試集上的性能

表6 支持向量機C－SVM與ν－SVM在測試集上的性能綜合比較

4.4 結果分析

由表5、表6可以看出，基于全部特征和C－SVM的性能與基于全部特征和ν－SVM的性能差別不大，基于Relief－SBS特征選擇+ν－SVM的性能略優于基于Relief－SBS特征選擇+C－SVM的性能。基于Relief－SBS特征選擇+C－SVM的性能及基于Relief－SBS特征選擇+ν－SVM的性能都優于KDD99最優方案。可見，本文提出的Relief－SBS特征選擇算法與兩種支持向量機分類器結合起來都能夠有效地促進分類性能的提高，也充分地說明了本文的特征選擇算法的有效性和可靠性，它為入侵檢測技術這一長期目標提供相關技術支持。

［1］Anderson JP.Computer Security Threat Monitoring and Surveillance［R］.Fort Washington，PA:James P.Anderson Co，1980.

［2］Heberlein LT，Dias GV，Levitt KN，et al.A network security monitor［C］.California:IEEE Computer Society Press，1990:296－302.

［3］Mosqueira－Rey E，Alonso－Betanzos A.A Misuse Detection Agent for Intrusion Detection in a Multi－agent Architecture［J］.Agent and Multi－Agent Systems:Technologies and Applications，2007:466－475.

［4］Aly El－ Semary，Janica Edmonds，Jesus Gonzalez－Pino.Applying data mining of fuzzy association rules to network intrusion detection［C］.UK:University of London press，2006:100－107.

［5］Ya－Li Ding，Lei Li，Hong－ Qi Luo.A novel signature searching for intrusion detecting system using data mining［C］.United States:IEEE Transaction on SMCB，2009:122－126.

［6］Charles Elkan.KDD＇99 Classifier Learning Contest［EB/OL］.［2012－10－06］.http://www－cse.ucsd.edu/users/elkan/clresults.html.

［7］Kononenko I.Estimating attributes:analysis and extensions of RELIEF［C］.United States:Morgan Kaufmann，Publishers，1994:171－182.