基于ReliefF的入侵特征選擇方法

楊志偉,努爾布力,賈 雪,胡 亮

(1.新疆大學 信息科學與工程學院,烏魯木齊 830046；2.吉林大學 計算機科學與技術學院,長春 130012)

?

基于ReliefF的入侵特征選擇方法

楊志偉1,努爾布力1,賈 雪1,胡 亮2

(1.新疆大學 信息科學與工程學院,烏魯木齊 830046；2.吉林大學 計算機科學與技術學院,長春 130012)

基于ReliefF的入侵特征選擇方法,結合入侵檢測數據集類內緊密和類外差距大的特點,通過對入侵特征權重計算的優化,提出一種改進算法:Re-ReliefF算法,解決了網絡安全領域數據維度導致處理效率較低的問題.實驗結果表明,在安全測試數據集下,改進算法相對傳統算法在性能上有一定提高.

入侵檢測；特征選擇；ReliefF算法

隨著互聯網的快速發展,網絡安全問題日益惡化.因此,快速提高入侵檢測系統的性能是目前互聯網領域內亟待解決的問題之一.本文針對目前海量網絡數據量導致入侵檢測系統壓力過大的問題,尤其針對數據維度中噪聲屬性影響檢測效率的問題,通過分析特征選擇的特性,結合針對入侵檢測領域攻擊數據集的特點,提出一種新算法----Re-ReliefF算法.該算法可得到低維度、少冗余數據的優良特征子集.實驗結果表明,改進算法可有效降低入侵檢測數據中的噪聲屬性,通過低維度的有效特征維度提升檢測效率,從而有效降低資源消耗,減少檢測時間.

1 入侵檢測與特征選擇

1.1入侵檢測

入侵是指未經授權就嘗試訪問信息、篡改信息,使系統不可靠或無法使用的行為[1].入侵檢測是指能夠發現和識別入侵行為.入侵檢測系統主要用于收集和分析主機系統或若干網絡關鍵節點的異常行為,一旦發現,主動記錄并發出警報,以保證主機系統和網絡資源的機密性、完整性和可用性.根據數據來源可分為主機型、網絡型和混合型入侵檢測系統;根據檢測的時效性可分為實時和離線入侵檢測系統;根據檢測方法可分為異常檢測和誤用檢測.

目前,入侵檢測技術已將數據挖掘、機器學習、模式識別和分布式等方法與入侵檢測相結合,使入侵檢測進入智能化時代.如Zhang等[2]針對智能電網的安全問題,提出了用于智能電網分析的分布式入侵檢測系統;Ahmad等[3]將遺傳算法和PCA(principal component analysis)算法相結合,提出了一種新的應用于入侵檢測領域的特征選擇方法;Ganapathy等[4]分析了智能特征選擇方法在入侵檢測領域的應用;楊杰明等[5]提出一種新的特征選擇方法,該方法從兩方面綜合度量某個特征對于分類的程度,結果表明了算法的有效性;朱琳等[6]通過對高速網絡環境下進行實時入侵檢測技術的研究,提出了基于滑動窗口數據流聚類算法,并構建了基于該算法的IDS(intrusion detection systems)網絡安全防御模型.

1.2特征選擇

圖1 特征選擇框架Fig.1 Feature selection framework

數據采集和存儲技術的發展,出現了信息爆炸的現象,特別是在網絡檢測、生物科學和金融分析等領域,不斷涌現大規模、高維度、高噪聲的數據.如何快速處理這些數據,已引起人們的廣泛關注,特征選擇方法是解決該問題的方法之一.例如一些機器學習問題,通常要處理的數據特征維度較高,因此采用特征選擇方法能降低數據維度,并提高算法效率.文獻[7]利用機器學習的思想提出一個通用的特征選擇框架,如圖1所示.該框架的思想是在不顯著降低分類精度和盡量接近原始類別分布的前提下,從原始特征空間中選擇出盡可能小的特征子集,并在該特征子集上采用學習方法,選擇出最優特征子集.

特征選擇在文本分類、圖像識別、醫療、入侵檢測和基于生物特征的身份識別等領域應用廣泛.Shang等[8]為解決文本分類中的維數災難問題,提出了一種全局信息增益特征選擇算法MGIG,結果表明MGIG比其他高階算法在處理速度上有較大提升；Rashedi等[9]將特征降維方法應用到圖像處理中,提出了一種混合的特征選擇方法;在人臉識別方面,Zhang等[10]利用稀疏化表示方法提出一種新的特征選擇方法;文獻[11]運用特征選擇算法,使得當基因表達數據很少時,也可提供一個合適的特征選擇組合,使分類算法精確率較高;陳友等[12]對基于特征選擇的輕量級入侵檢測系統進行分類比較,通過分析和總結各種系統的優缺點及其各自的適用條件,給出了入侵檢測領域特征選擇的發展趨勢.

1.3ReliefF特征選擇算法

Relief算法[13]是一種適用于二類問題的有監督特征選擇算法,基于距離度量計算特征權重,利用統計學方法選擇相關特征.算法中特征和類別的相關性是基于特征對近距離樣本的區分能力判斷的,按照一定的規則賦予每個特征一個權重值,以權重值的大小識別各特征對不同類別的區分能力.Kononenko[14]對Relief算法進行擴展,提出了可應對多類別數據集分類情況及噪聲數據與數據缺失問題的ReliefF算法.Relief系列算法通常被視為應用于模型學習前預處理步驟中的特征子集選擇方法.

ReliefF算法在處理多類問題時,每次先從訓練集隨機抽取一個樣本R,再從R同類樣本集中找出R的k個近鄰樣本H,從每個R不同類樣本集中找出k個近鄰樣本M,然后更新每個特征的權值w[A],權值更新公式為

(1)

其中:m表示樣本抽樣次數;Mj(C)表示不同類別C中的第j個最近鄰樣本;P(C)表示C類目標樣本數占樣本總數的比例;class(Ri)表示Ri所屬的類別;函數diff(A,Ri,Rj)用于計算樣本實例Ri和Rj關于某個特征A間的距離：

(2)

由式(1)可見,對于某個特征A,同類的兩個樣本在A上的距離diff(A,Ri,Hj)越小,或者不同類的兩個樣本在A上的距離diff(A,Ri,Mj(C))越大,特征A越有利于分類,w[A]越大.

ReliefF算法易擴展,穩定性好,目前已有多種改進算法,如Jia等[15]提出一種面向對象高維分辨圖像特征選擇的改進Relief算法,避免了高維帶來的運算困難,也提高了分類精度和速度;Wang等[16]通過結合DDNA和SOEKS RELIEF-F特征選擇學習算法,得到一個通用的、可拓展的增強型學習算法,提高了預測精度.

2 Re-ReliefF算法

2.1算法設計

圖2 基于ReliefF入侵特征選擇算法的邏輯結構Fig.2 Logical structure of ReliefF-based intrusionfeature selection algorithm

網絡數據的大規模和高維度,為入侵檢測系統實時、快速、準確地分析網絡數據帶來了巨大挑戰.本文將特征選擇方法應用到入侵檢測領域,解決對高維數據處理的問題.將ReliefF算法應用到入侵檢測領域,通過實驗分析其有效性.ReliefF入侵特征選擇算法邏輯結構如圖2所示.

2.2定義

定義1基于ReliefF入侵特征選擇算法的輸入矩陣定義為D：(A,F).其中:A表示網絡數據特征,包括協議類型、持續連接時間及目標主機的網絡服務類型等41個特征；F表示攻擊數據類別標簽,如Normal,DOS,U2R等.

定義2基于ReliefF入侵特征選擇算法的參數模型定義為R(m,k,N).其中：m表示初始隨機選擇的樣本個數,即隨機選取輸入矩陣D的若干行；k表示在m個網絡數據樣本中選取一個樣本后選擇其最近鄰樣本的數量,包括同類的最近鄰樣本H和不同類的最近鄰樣本M；N表示攻擊數據特征維度,N=41.

定義3基于ReliefF入侵特征選擇算法的特征權值定義為w[A],表示m個網絡數據樣本在特征A上的距離間隔累加結果,數值越大表示特征A區分攻擊類別的能力越強.

定義4基于ReliefF入侵特征選擇算法的特征子集定義為S(D),其為根據定義3中w[A]大小選擇較大值的w[A]所對應特征的特征子集.

定義5基于ReliefF入侵特征選擇算法的最優特征子集定義為S′,其為定義4中眾多特征子集S中通過SVM分類預測,由時間和準確率等指標選出的最優子集.

2.3算法描述

輸入：網絡數據集D;輸出：最優特征子集S.

1)數值化D：num(D)；歸一化A：nor(A)∈[-1,1]；

2)抽樣產生訓練集trainD及預測集testD；

3)初始化w[A]=0；

4)確定特征選擇參數模型k,m值,隨機選擇m個樣本實例；

5)Fori=1 tomdo；

6)計算選擇k個最近鄰樣本：H,M；

7)Fori=1 toNdo；

8)計算特征A的權值w[A]；

9)產生特征子集S=generate(D)；

10)產生目標系統的分類模型model=train(trainD,S)；

11)對測試集進行分類預測,predict(testD,model),選擇最優子集S′,算法結束.

在該算法中,步驟1)和2)為數據的預處理過程;步驟3)～9)是對trainD特征選擇的過程;步驟10),11)是對算法性能的驗證過程.

2.4改進算法

由于網絡安全數據中有些類別不易區分,如KDD CUP99數據集中,包含5大類,有些大類又有許多小類,因此如何突出類內緊密、增大類間差距是一個亟待解決的問題.針對該問題,本文參考文獻[17]修改了特征權值的更新,提出ReliefF算法針對入侵檢測特征選擇的改進算法：Re-ReliefF.其中更新特征權值公式為

(3)

Re-ReliefF算法采用樣本與不同類最近鄰樣本間的距離,與樣本和同類最近鄰樣本間的距離比值評估特征權值.為類間差異性較大、類內差異性較小的特征賦以較高權重；為類間差異較小、類內差異較大的特征賦以較小權重.以突出類內緊密性強、類間差距大的特征,從而達到降低有效特征數量的目的.

3 實驗與分析

實驗環境：操作系統Windows 7；CPU 16×2.1 GHz；內存64 GB；軟件環境MATLAB R2010b 64位.實驗數據是KDD CUP99數據集,其提供5類數據集:Normal,Denial-of-Service(DOS),Surveillance or probe(Probe),User to Root(U2R),Remote to Local(R2L).其中,Normal類占19.69%；Probe大類包含4小類,共占0.83%；DOS大類包含6小類,共占79.24%；U2R包含4小類,共占0.01%；R2L大類包含8小類,共占0.23%.數據集里每一行表示一個記錄,每條記錄有41個特征值,最后一個是攻擊類型.實驗包括兩部分：算法參數模型的建立和算法性能指標對比.

實驗1模型構建.

由算法描述步驟5)可見,實驗需要選擇合適的參數m和k,本文通過Re-ReliefF入侵特征選擇算法選擇合適的值.

1)m值的選擇.當k=1時,m分別為50,100,500,1 000,5 000次迭代時,統計訓練時間、預測時間、準確率、誤報率和漏報率,結果列于表1.

表1 Re-ReliefF算法取不同m值時的相關參數Table 1 Parameters of Re-ReliefF algorithm for different m values

由表1可見,在較小迭代次數下與較大迭代次數下的實驗結果相差較小.表明當樣本規模較大時,迭代次數在遠小于樣本總數時,可得到較準確的評估結果.綜合表1的數據,選擇m=500.

2)k值的選擇.當m=500,k=1,20,40時,統計訓練時間、預測時間、準確率、誤報率和漏報率,結果列于表2.由表2可見,k=1與k=40相比,預測時間更短.所以,可選擇k=20.

實驗2Re-ReliefF算法與傳統ReliefF算法對比結果.

通過實驗1的參數選定,結合SVM分類算法,比較ReliefF入侵特征選擇算法和Re-ReliefF入侵特征選擇算法中每個特征權值大小,結果如圖3所示.ReliefF算法和Re-ReliefF算法的訓練時間、預測時間和準確率對比結果分別如圖4～圖6所示.

表2 Re-ReliefF算法取不同k值時的相關參數Table 2 Parameters of Re-ReliefF algorithm for different k values

圖3 ReliefF算法與Re-ReliefF算法下的特征權值比較Fig.3 Comparison of feature weights ofReliefF and Re-ReliefF

圖4 ReliefF算法與Re-ReliefF算法訓練時間對比Fig.4 Comparison of training time ofReliefF and Re-ReliefF

圖5 ReliefF算法與Re-ReliefF算法預測時間對比Fig.5 Comparison of predicting time ofReliefF and Re-ReliefF

圖6 ReliefF算法與Re-ReliefF算法準確率對比Fig.6 Comparison of accuracy ofReliefF and Re-ReliefF

由圖3可見,大部分Re-ReliefF入侵特征選擇算法的特征值比ReliefF入侵特征選擇算法的特征值都大,根據對算法的理論分析,實驗證明了Re-ReliefF入侵特征選擇算法類內差異減小,類間差異增大,可更方便地選擇最優特征子集.由圖4～圖6可見:1)ReliefF入侵特征選擇算法和Re-ReliefF入侵特征選擇算法訓練時間均隨著特征維數的減少而減少；預測時間在維數少于34時明顯增多；準確率在維數小于34時顯著下降,所以兩種算法都適合取34個特征作為最優特征子集的集合數量.2)Re-ReliefF算法相對于原始的ReliefF算法,可在分類準確率相對穩定的情況下降低訓練和預測時間.

通過對ReliefF算法和Re-ReliefF算法的實驗結果對比可見:

1)當類間差異較大,類內差異較小時,改進后的特征權值w(A)相對于原有ReliefF算法的權值大,此時能夠區分原有ReliefF算法中較相近的入侵特征,從而減少有效區分入侵攻擊類別的入侵特征數量,達到降低有效特征數量的目的;

2)當類間差異較小,類內差異較大時,改進后的特征權值w(A)相對于原有ReliefF算法的權值小,此時將原有ReliefF算法中已判為能進行入侵分類的有效特征,重新計算判別為非有效特征,從而減少非有效區分入侵攻擊類別的入侵特征數量,達到降低有效特征數量的目的.

綜上所述,論文通過對特征選擇算法的研究,明確與入侵特征指標模型間的映射關系提出了基于ReliefF的入侵特征選擇方法;并進一步根據入侵檢測數據集類內緊密和類外差距大的特點,結合已有工作對ReliefF的權重計算方法進行優化.實驗結果表明,改進的Re-ReliefF算法結合SVM能更有效地區分入侵的特征差異,在降低數據維度后,特征子集能保障較好的正確率并有效減少時間復雜度.

[1] James P A.Computer Security Threat Monitoring and Surveillance [R].Fort Washington,Pennsylvania:Anderson Company,1980.

[2] ZHANG Yichi,WANG Lingfeng,SUN Weiqing,et al.Distributed Intrusion Detection System in a Multi-layer Network Architecture of Smart Grids [J].IEEE Transactions on Smart Grid,2011,2(4):796-808.

[3] Ahmad I,Hussain M,Alghamdi A,et al.Enhancing SVM Performance in Intrusion Detection Using Optimal Feature Subset Selection Based on Genetic Principal Components [J].Neural Computing and Applications,2014,24(7/8):1671-1682.

[4] Ganapathy S,Kulothungan K,Muthurajkumar S,et al.Intelligent Feature Selection and Classification Techniques for Intrusion Detection in Networks:A Survey [J/OL].EURASIP Journal on Wireless Communications and Networking,2013,2013(1):doi:10.1186/1687-1499-2013-271.

[5] 楊杰明,劉元寧,曲朝陽,等.文本分類中基于綜合度量的特征選擇方法 [J].吉林大學學報:理學版,2013,51(5):887-893.(YANG Jieming,LIU Yuanning,QU Zhaoyang,et al.Feature Selection Algorithm Based on Comprehensive Measurement for Text Categorization [J].Journal of Jilin University:Science Edition,2013,51(5):887-893.)

[6] 朱琳,朱參世.滑動窗口數據流聚類算法在IDS中的應用 [J].計算機工程與應用,2014,50(1):87-90.(ZHU Lin,ZHU Canshi.Data Stream Sliding Window Clustering Algorithm Applied in IDS [J].Computer Engineering and Applications,2014,50(1)：87-90.)

[7] LIU Ling,Tamer?zsu T.Encyclopedia of Database Systems [M].New York:Springer,2009:1119-1125.

[8] SHANG Changxin,LI Ming,FENG Shengzhong,et al.Feature Selection via Maximizing Global Information Gain for Text Classification [J].Knowledge-Based Systems,2013,54:298-309.

[9] Rashedi E,Nezamabadi-Pour H,Saryazdi S.A Simultaneous Feature Adaptation and Feature Selection Method for Content-Based Image Retrieval Systems [J].Knowledge-Based Systems,2013,39:85-94.

[10] ZHANG Haichao,ZHANG Yanning,Huang T S.Pose-Robust Face Recognition via Sparse Representation [J].Pattern Recognition,2013,46(5):1511-1521.

[11] Alonso-Gonzlez C J,Moro-Sancho Q I,Simon-Hurtado A,et al.Microarray Gene Expression Classification with Few Genes:Criteria to Combine Attribute Selection and Classification Methods [J].Expert Systems with Applications,2012,39(8):7270-7280.

[12] 陳友,程學旗,李洋,等.基于特征選擇的輕量級入侵檢測系統 [J].軟件學報,2007,18(7):1639-1651.(CHEN You,CHENG Xueqi,LI Yang,et al.Lightweight Intrusion Detection System Based on Feature Selection [J].Journal of Software,2007,18(7):1639-1651.)

[13] Kira K,Rendell L A.The Feature Selection Problem:Traditional Methods and a New Algorithm [C]//Proceeding of the 10th National Conference on Artifical Intelligence.San Jose:DBLP,1992:129-134.

[14] Kononenko I.Estimating Attributes:Analysis and Extensions of RELIEF [C]//Machine Learning:ECML-94.Berlin:Springer,1994:171-182.

[15] JIA Jianhua,YANG Ning,ZHANG Chao,et al.Object-Oriented Feature Selection of High Spatial Resolution Images Using an Improved Relief Algorithm [J].Mathematical and Computer Modelling,2013,58(3/4):619-626.

[16] WANG Peng,Sanín C,Szczerbicki E.Prediction Based on Integration of Decisional DNA and a Feature Selection Algorithm RELIEF-F [J].Cybernetics and Systems,2013,44(2/3):173-183.

[17] 齊濱.高光譜圖像分類及端元提取方法研究 [D].哈爾濱:哈爾濱工程大學,2012.(QI Bin.Research on Hyperspectral Image Classification and Endmember Extraction Methods [D].Harbin:Harbin Engineering University,2012.)

(責任編輯：韓 嘯)

IntrusionFeatureSelectionMethodsBasedonReliefF

YANG Zhiwei1,Nurbol1,JIA Xue1,HU Liang2

(1.CollegeofInformationScienceandEngineering,XinjiangUniversity,Urumqi830046,China;2.CollegeofComputerScienceandTechnology,JilinUniversity,Changchun130012,China)

The authors analyzed the intrusion feature selection methods and algorithms based on ReliefF.Combining with the characteristics,in which data points have high similarity in the same class and nonsimilarity in different classes,and optimizing the compute method of intrusion feature weight,we proposed an improved algorithm Re-ReliefF.It resolved the problems about processing efficiency with the data dimensions in network security.Experiments on the network security test datasets showed the effectiveness of the proposed algorithms,and the improved algorithm has advantages on performance compared to the traditional one.

intrusion detection;feature selection;ReliefF algorithm

10.13413/j.cnki.jdxblxb.2015.03.30

2014-08-04.

楊志偉(1989—),男,漢族,碩士研究生,從事云計算和網絡安全的研究,E-mail:758408528@qq.com.通信作者:努爾布力(1981—),男,哈薩克族,博士,副教授,從事數據挖掘和網絡安全的研究,E-mail:nurbol_mail@163.com.

國家自然科學基金(批準號:61163052;61303231)、國家自然科學基金重點項目(批準號:61433012)、國家自然科學基金聯合基金(批準號:U1435215)、新疆維吾爾自治區青年科技創新人才培養工程項目(批準號:2014731002)、新疆大學多語種實驗室開放課題和新疆大學校級創新團隊資助項目.

TP309

：A

：1671-5489(2015)03-0505-06