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

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

?

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

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

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

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

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

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

1 入侵檢測與特征選擇

1.1入侵檢測

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

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

1.2特征選擇

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

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

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

1.3ReliefF特征選擇算法

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

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

(1)

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

(2)

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

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

2 Re-ReliefF算法

2.1算法設計

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

網(wǎng)絡數(shù)據(jù)的大規(guī)模和高維度,為入侵檢測系統(tǒng)實時、快速、準確地分析網(wǎng)絡數(shù)據(jù)帶來了巨大挑戰(zhàn).本文將特征選擇方法應用到入侵檢測領域,解決對高維數(shù)據(jù)處理的問題.將ReliefF算法應用到入侵檢測領域,通過實驗分析其有效性.ReliefF入侵特征選擇算法邏輯結(jié)構(gòu)如圖2所示.

2.2定義

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

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

定義3基于ReliefF入侵特征選擇算法的特征權(quán)值定義為w[A],表示m個網(wǎng)絡數(shù)據(jù)樣本在特征A上的距離間隔累加結(jié)果,數(shù)值越大表示特征A區(qū)分攻擊類別的能力越強.

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

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

2.3算法描述

輸入：網(wǎng)絡數(shù)據(jù)集D;輸出：最優(yōu)特征子集S.

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

2)抽樣產(chǎn)生訓練集trainD及預測集testD；

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

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

5)Fori=1 tomdo；

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

7)Fori=1 toNdo；

8)計算特征A的權(quán)值w[A]；

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

10)產(chǎn)生目標系統(tǒng)的分類模型model=train(trainD,S)；

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

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

2.4改進算法

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

(3)

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

3 實驗與分析

實驗環(huán)境：操作系統(tǒng)Windows 7；CPU 16×2.1 GHz；內(nèi)存64 GB；軟件環(huán)境MATLAB R2010b 64位.實驗數(shù)據(jù)是KDD CUP99數(shù)據(jù)集,其提供5類數(shù)據(jù)集: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%.數(shù)據(jù)集里每一行表示一個記錄,每條記錄有41個特征值,最后一個是攻擊類型.實驗包括兩部分：算法參數(shù)模型的建立和算法性能指標對比.

實驗1模型構(gòu)建.

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

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

表1 Re-ReliefF算法取不同m值時的相關(guān)參數(shù)Table 1 Parameters of Re-ReliefF algorithm for different m values

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

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

實驗2Re-ReliefF算法與傳統(tǒng)ReliefF算法對比結(jié)果.

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

表2 Re-ReliefF算法取不同k值時的相關(guān)參數(shù)Table 2 Parameters of Re-ReliefF algorithm for different k values

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

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

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

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

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

[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] 朱琳,朱參世.滑動窗口數(shù)據(jù)流聚類算法在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] 陳友,程學旗,李洋,等.基于特征選擇的輕量級入侵檢測系統(tǒng) [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—),男,漢族,碩士研究生,從事云計算和網(wǎng)絡安全的研究,E-mail:758408528@qq.com.通信作者:努爾布力(1981—),男,哈薩克族,博士,副教授,從事數(shù)據(jù)挖掘和網(wǎng)絡安全的研究,E-mail:nurbol_mail@163.com.

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

TP309

：A

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