一種基于信息論模型的入侵檢測特征提取方法

宋 勇，蔡志平

(1.湖南民族職業學院工程技術系 湖南 岳陽 414000；2.國防科技大學計算機學院 長沙 410073)

隨著網絡技術的快速發展，計算機網絡在各個領域得到廣泛應用，網絡安全也變得日益重要。入侵檢測是一種通過采集和分析被保護系統的信息從而發現入侵行為的技術。入侵檢測的數據源通常來自網絡中的數據包和系統的審計日志等，這些原始數據通常包含多達幾十個特征，如果直接將它們應用到檢測算法中，將導致檢測速度緩慢，響應不及時。因此，從大量特征中提取可替代的特征子集是入侵檢測數據預處理需要解決的重要問題。

如何選擇一個度量對量化特征進行測度是在進行特征選取前的一項重要工作。信息論中的熵是對隨機信息中不確定性的度量。熵作為一種良好全局測度，在特征選取時，它能夠幫助我們尋找到更有作用的特征。本文在深入分析網絡流量數據集的基礎上，提出了一種改進的面向入侵檢測的基于信息論模型的特征提取方法。

1 相關工作

特征提取作為數據挖掘技術中的一項重要的預處理步驟，在機器學習領域具有重要的研究價值。根據樣本集是否有標記，特征提取方法可以分為3種：無監督學習算法[1-2]、半監督學習算法[3-4]和有監督學習算法[5-6]。有監督模式特征提取算法是在計算類別與特征之間的相關度時，依據標記的類別信息，選擇類別區分力最大的特征子集。該算法的優點是分類性能比較高，但缺點是必須在樣本集中標記類別，故通用性不強。無監督模式特征提取算法是在沒有前面的經驗指導下，通過特征間的內在聯系，利用樣本數據的方差或分離性從特征集中提取重要的特征。該算法的優點是無需具有標記的數據樣本，具有一定的通用性，但性能不如有監督模式特征提取算法，并且算法的時間和空間復雜度也高于前者。結合無監督學習算法和有監督學習算法，出現了半監督模式特征提取算法，該算法為了提高大量未標記類別樣本數據的特征提取，先對少數樣本數據標記類別，并以之為指導。

根據與學習算法結合的方式不同，一般將特征提取算法大致分為4類：Embedded、Filter、Wrapper和Hybrid模型[7]。Embedded模型將特征提取與學習過程同時進行，在學習訓練的過程中選擇合適的特征，學習過程完成后，算法所涉及到的特征即為提取的特征結果。該模型的典型算法是決策樹算法，如文獻[8]提出的ID3和C4.5算法。Filter特征提取算法的評估標準直接由數據集求得，獨立于學習算法。該算法以特征之間相互獨立為條件，依據每一個特征對于分類的區分能力，選擇其中區分能力最強的n個特征進行組合。與Filter模型特征提取算法不同，基于Wrapper模型的特征提取算法使用分類器的分類評價來確定特征子集，即首先利用分類器對不同的特征子集組合進行評價，然后對不同的特征子集評價對比得出最優的特征子集。但是該算法一個明顯的缺點是算法的時間和空間復雜度比較高。Hybrid模型特征提取算法結合Filter模型和Wrapper模型確定最后的特征子集。它一般先采用前者除掉與類別無關的特征，然后將剩下的特征和類別作為后者的輸入，進一步獲取最優的特征子集。

2 特征提取方法

特征選擇是一種典型的搜索尋優問題。大小為n的特征集合，根據選擇或不選擇兩種情況，可以形成2n種集合空間，然后從這個空間中搜索出最優的結果。但是在特征數目多的情況下，如果采用窮盡式的選擇算法，那么將會導致特征選擇過程占用大量的計算資源、花費大量的時間，因此許多研究人員致力于用一種智能化的搜索算法來尋找最優解。一般特征選擇算法必須確定以下4個方面[9]：1)搜索起點；2)搜索策略；3)特征評估函數；4)終止條件。本文從這4個方面出發，根據入侵檢測中數據集的特點，提出了一種結合信息熵中的信息增益和條件互信息概念的特征提取方法。

2.1 問題模型及相關定義

設入侵檢測訓練數據集為D，|D|表示其樣本的容量，即樣本個數。設數據集中的類別標記為C={C1,C2,…,Ck}，在本文中將入侵檢測數據集類別標記劃分為normal和abnormal兩類，即將所有正常數據標記為normal，所有攻擊數據均標記為abnormal，因此|Ci|=2。數據集中類別標記集合F是類別C的一種組合。設數據集的特征集合為T={t1,t2,…,tn}，|T|表示其特征的個數，T′為特征集合T的一個子集，即T′?T。特征選取方法的基本思想是從原特征集合T中選擇出它的—個子集構成新的特征空間。

對于某一個特征tx，其可能取值集合記為Stx。對于x∈Stx，其概率為P(x)，根據Shannon信息理論，tx的信息熵定義為：

在信息論里面，式(1)是信息不確定性的一個度量，值越大則表示信息的不確定程度越高。對于訓練數據集，可以得到數據集類別標記集合的信息熵為H(F)，也是數據集的經驗熵。

當訓練數據集中特征ty已知時，特征tx中剩余的不確定性用條件熵來定義：

對于訓練數據集中兩個隨機特征tx和ty的統計依存關系用互信息來定義：

互信息越大，這兩個隨機特征之間的聯系越緊密；當互信息趨近于零時，這兩者之間相互獨立。

在機器學習領域，信息增益作為信息論統計中的一個重要概念被廣泛應用。對分類系統來說，信息增益是某—特征項t在系統中出現與否的信息量之差，它定義為：

式中，p(ci)表示ci類在樣本標記集合F中出現的概率；p(t)和p(t′)表示數據集中特征t所有取值的概率；p(ci|t)和p(ci|t′)表示數據集中特征t取某一值時屬于ci類的概率。在特征選擇中，某個特征的信息增益越大，說明它的作用越大，對F也越重要。因此，在進行特征選擇時，信息增益值大的特征將會是候選特征。但通過式(4)可以看出：給定一個數據集后，它的H(F)是固定的，因此IG(t)的大小取決于H(F|t)。當特征t的取值都不相同時，H(F|t)將會等于0，這時IG(t)將最大，顯然這種情況的特征意義不大。因此根據C4.5[8]算法，為了解決這個問題，一般采用信息增益率，定義如下：

式中，H(t)表示特征t的信息熵。

在入侵檢測數據集中，類別標記是由離散型數據{normal，abnormal}表示，但有些樣本特征的值是連續型的數據，如duration、src_bytes等特征的值。在評判這些連續特征與類別標記的相關性時，需要對連續特征進行離散化。由于入侵檢測數據集的類別標記只有normal和abnormal兩類，所以對于連續型特征的值域只需要將它們劃分為兩個區域，分別對應前面的兩種標記類型。具體劃分點的計算方法如下。

對于連續特征T，對它的樣本數據集中不重復的值經排序后為v1＜v2＜…＜vn，并按下面的步驟進行計算：

1) 設i=1;

2)令v=(vi+vi+1)/2；設樣本數據集中特征T的值≤v時為0，>v時為1；

3) 令Ii=I(T;C)，設i=i+1，重復步驟2)，直到i≤n；

4) 輸出{I1,I2,…}值最大對應的v值。

v值就是特征T值域的劃分點，利用該值將特征T的值域分成兩個區域，按照約定分別將在這兩個區域的值指定為0或者1。

2.2 搜索起點

被選取特征子集的初始狀態稱為算法的搜索起點，它對搜索結果有十分重要的影響。當被選取特征子集為空時，可以按照一定方法逐個地向被選取特征子集加入特征；當被選取特征子集為全集時，可以按照一定方法不斷地刪減特征；當被選取特征子集從特征集的某個子集開始時，那么搜索策略一般采用隨機或者啟發式。

本文根據最優被選取特征集中一定包含了對數據集類別信息增益最高的特征這一原則，搜索起點為：max{IGR(t1), IGR(t2),…, IGR(tn)}。IGR函數為某一特征的信息增益率，具體如式(5)所示。

2.3 搜索策略

被選取特征集搜索算法一般采用順序搜索和隨機搜索。順序搜索算法采用順序的方式，從特征集中選取特征到被選取特征集，從而逐步擴展搜索，如順序前向搜索和順序后向搜索等。隨機搜索算法包括模擬退火、遺傳算法和集束式搜索等。本算法采用順序搜索的方式，基本步驟如下：

1) 初始化：提取特征子集T′=max{IGR(t1), IGR(t2),…, IGR (tn)}，T={除T′外所有的屬性}；

2) ?t∈T，按特征評估函數計算特征t的值；

3)計算T集合中所有特征的值，獲得具有最大值的特征tmax，設置T=T?{tmax}，T′=T′∪{tmax}；

4)重復步驟2)和步驟3)直至滿足終止條件；

5)輸出特征集T′。

2.4 特征評估函數

特征評估函數是特征選擇的評價標準，即可以利用單獨的特征獨立進行評價，也可以利用某個特征子集整體進行評價。

在文獻[10]中，針對利用信息增益思想提取特征時存在的一些問題，分別提出了增加了頻度、集中度和分散度3項測試指標的方法。在MaxMI[11]特征選擇算法中，提出了最大化互信息的基本思想，即提取的特征子集應當盡可能多地提供關于類別的信息，也就是最大化I(C;T′)。這兩個算法最大的問題就是只考慮到了各特征與類別之間的關系，而沒有考慮到提取的特征之間的相互影響。在PG-HMI[12]算法中，雖然評估函數即考慮到了特征選取準則既與屬性能夠提供的新信息量I(C；f |S)相關，也與屬性和類別標記的相關度I(C；f)相關，但是沒有考慮到新選擇的特征f可能會對已提取的特征子集產生冗余。

結合前面的研究成果和信息論模型，提出一種基于信息論模型的特征選擇算法，該算法即考慮到在已選取特征子集確定的條件下，候選特征與類別之間的關系，又將候選特征與已選取特征子集之間的相關度作為該特征是否選取的重要依據。

設原始特征集為T={T1,T2,…,Tn}，選取的特征子集為T′={T′1,T′2,…}，候選特征為t。在已選取特征子集確定的條件下，候選特征與類別之間的相關性根據式(2)和式(3)得到：

候選特征與已選取特征子集之間的相關度定義為：

式中，H(t)表示候選特征數據集的信息熵；表示候選特征數據集與當前已選取特征子集數據集的聯合熵；表示當前已選取特征子集數據集的聯合熵。式(7)的值等于零時，表示候選特征與已選取特征子集不相關。但是根據入侵檢測數據集的分析，MI(t;T′)為零的可能性幾乎很小，所以必須設置一個閥值控制候選特征與已選特征子集之間的相關度。

綜合上述得到本算法的搜索評估函數為：

該函數表示在已選取特征子集確定的條件下，從所有候選特征中選取與已選取特征子集的互信息小于閥值ε∈[0,1]、并且與樣本標記的互信息值最大且大于零的特征。

2.5 終止條件

算法的終止條件可以選擇固定的迭代次數和特征數目來進行，也可以自己定義終止條件函數。本算法的終止條件為：

上述終止條件表示當所有候選特征在已選取特征子集確定的條件下，與樣本標記的互信息都小于閥值β∈[0,1]時終止，或者在前面表達式不成立的條件下，所有候選特征與已選取特征子集的互信息大于閥值ε∈[0,1]。

3 實驗結果及分析

3.1 實驗數據

為了檢驗本文提出的特征提取算法的有效性，選用了KDD99數據集作為實驗數據集。KDD CUP 1999數據集是由麻省理工學院的林肯實驗室采用1998年美國國防部高級規劃署的入侵檢測數據集建立起來的。數據提取了41個特征，包括34個連續型特征和7個離散型特征。

由于原始數據集過于龐大，因此只選取KDD99中的kddcupdata10percent數據集。該數據集包含494 021條連接記錄，其中攻擊連接記錄396 743條，正常連接記錄97 278條，攻擊類型22個。為了驗證本算法提取的特征集對未知攻擊類型的有效性，在訓練數據集中只包含12種攻擊類型，記錄條數4 000條，其中攻擊記錄2 000條。測試數據集中包含22種攻擊類型，記錄條件10 000條，其中攻擊記錄3 000條。

3.2 實驗設置

在實驗過程中，本方法的主要參數是搜索函數和終止條件函數的兩個閥值。其中通過閥值β可以控制選取特征子集與樣本標記的相關性程度。如果β太大，它們的相關程度變高，入選特征數少，可能一些較重要的特征無法選取，從而導致分類算法精確度不高；若β值太小，入選特征數變多，不利于分類算法的性能。通過多次實驗，確定β為0.35。閥值ε主要控制被提取特征之間的相關性程度，較大時導致被提取特征之間的冗余度較高，因此ε值設為0.05。

實驗環境為CPU Inter Core i7 2.50 GHz，內存8.00 GB，操作系統Windows8 64位，開發工具Matlab2010。

3.3 特征選取結果和分析

根據上面的實驗數據和實驗設置，利用本文提出的特征提取算法，得到特征子集的屬性ID為1、3、5、6、12、23、24、32、33、36、37、40。為了驗證特征選取的有效性，本文使用支持向量機分類算法(support vector machines, SVM)對測試數據集進行兩組實驗，分別是原始特征全集和本文提出的方法所選出的特征子集，并進行入侵檢測性能評估。本文采用檢測時間、檢測率和誤報率3個評價指標進行性能評估，其中：

式中，DR表示檢測率；DC表示檢測的異常記錄個數；AC表示真實入侵記錄個數；FPR表示誤碼報率；MIC表示正常記錄誤報為異常的個數；NIC表示正常記錄個數。實驗結果如表1所示。

表1 特征提出前后的效果比較

從表中可以看出，使用本文的特征提取算法，特征維度降低了70.7%，但是檢測率和誤警率影響不大，算法的處理速度提高了50.8%。

4 結束語

本文面向入侵檢測提出了一種基于信息論模型的特征提取方法，本方法依據最優被選取特征集中一定包含對數據集類別信息熵增益最高的特征這一原則，首先從所有特征中選取信息增益最大的特征作為搜索起點，然后充分考慮樣本數據集分類標記、已選取特征子集和候選特征三者之間的信息相關性基礎上順序搜索最合適的特征，最后在搜索終止條件下完成所有特征的選取。通過在KDD99數據集上的實驗表明，本文提出的特征選擇方法在保證檢測準確率的前提下，大大降低了入侵檢測數據的特征維度，從而減輕了檢測系統的存儲負擔，提高了入侵檢測分類器的性能。后續將在真實系統架構[13]中驗證本文方法在大數據流量情況的性能，并考慮在Spark等大數據處理平臺[14]上的實現方法。

[1]CHIMIENTI M，CORNULIER T，OWEN E.The use of an unsupervised learning approach for characterizing latent behaviors in accelerometer data[J].Ecology & Evolution,2016, 6(3): 1948-1952.

[2]楊國亮, 謝乃俊, 王艷芳, 等.基于低秩稀疏評分的非監督特征選擇[J].計算機工程與科學, 2015, 37(4): 649-656.YANG Guo-liang, XIE Nai-jun, WANG Yan-fang, et al.Unsupervised feature selection based on low rank and sparse score[J].Computer Engineering and Science, 2015,37(4): 649-656.

[3]]ZHENG Zhao, LIU Huan.Semi-supervised featrue selection via spectral analysis[C]//Proceedings of the 7th SIAM International Conference on Data Mining.[S.l.]:DBLP, 2007: 1193-1201.

[4]史彩娟.網絡空間圖像標注中半監督稀疏特征選擇算法研究[D].北京: 北京交通大學, 2015.SHI Cai-juan.Research on semi-supervised sparse feature selection for image annotation in web space[D].Beijing:Beijing Jiaotong University, 2015.

[5]YU Lei, LU Ling.Featrue selection based on loss-margin of nearest neighborclassification[J].Pattern Recongnition,2009, 42(9): 1914-1921.

[6]鄭瑩斌.有監督的視覺特征提取算法研究[D].上海: 復旦大學, 2013.ZHENG Ying-bin.Research on supervised visual feature extraction algorithms[D].Shanghai: Fudan University, 2013.

[7]MANSOORI E G, SHAFIEE K S.On fuzzy feature selection in designing fuzzy classifiers for high-dimensional data[J].Evolving Systems, 2015, 7(4): 1-11.

[8]QUINLAN J R.Programs for machine learning[M].San Mateo, CA: Morgan Kaufmann, 1993.

[9]張麗新, 王家欽, 趙雁南, 等.機器學習中的特征選擇[J].計算機科學, 2004, 31(11): 180-184.ZHANG Li-xin, WANG Jia-qin, ZHAO Yan-nan, et al.Feature selection in machine learining[J].Computer Science,2004, 31(11): 180-184.

[10]李玲, 劉華文, 徐曉丹, 等.基于信息增益的多標簽特征選擇算法[J].計算機科學, 2015, 42(7): 52-56.LI Ling, LIU Hua-wen, XU Xiao-dan, et al.Multi-label feature selection algorithm based on information gain[J].Computer Science, 2015, 42(7): 52-56.

[11]唐亮, 段建國, 許洪波, 等.基于互信息最大化的特征選擇算法及應用[J].計算機工程與應用, 2008, 44(13):130-133.TANG Liang, DUAN Jian-guo, XU Hong-bo, et al.Mutual information maximization based feature selection algorithm in text classification[J].Computer Engineering and Applications, 2008, 44(13): 130-133.

[12]WANG H, SUN H B, ZHANG B M.PG-HMI: Mutual information based feature selection method[J].Pattern Recognition & Artificial Intelligence, 2007, 20(1): 55-63.

[13]CAI Zhi-ping, WANG Zhi-jun, ZHENG Kai, et al.A distributed TCAM coprocessor architecture for integrated longest prefix matching, policy filtering, and content filtering[J].IEEE Trans Computers, 2013, 62(3): 417-427.

[14]方峰, 蔡志平, 肇啟佳, 等.使用Spark Streaming的自適應實時DDoS檢測和防御技術[J].計算機科學與探索,2016, 10(5): 601-611.FANG Feng, CAI Zhi-ping, ZHAO Qi-jia, et al.Adaptive technique for real-time DDoS detection and defense using spark streaming[J].Journal of Frontiers of Computer Science and Technology, 2016, 10(5): 601-611.