吳慶濤，曹繼邦，鄭瑞娟，張聚偉

基于粒子群優(yōu)化的入侵特征選擇算法

吳慶濤，曹繼邦，鄭瑞娟，張聚偉

針對高維數(shù)入侵檢測數(shù)據(jù)集中信息冗余導(dǎo)致入侵檢測算法處理速度慢的問題，提出了一種基于粒子群優(yōu)化的入侵特征選擇算法，通過分析網(wǎng)絡(luò)入侵?jǐn)?shù)據(jù)特征之間的相關(guān)性，可使粒子群優(yōu)化算法在所有特征空間中優(yōu)化搜索，自主選擇有效特征子集，降低數(shù)據(jù)維度。實驗結(jié)果表明該算法能夠有效去除冗余特征，減少特征選擇時間，在保證檢測準(zhǔn)確率的前提下，有效地提高了系統(tǒng)的檢測速度。

入侵檢測；粒子群優(yōu)化；特征選擇；優(yōu)化搜索；特征關(guān)聯(lián)性

1 引言

入侵檢測技術(shù)是網(wǎng)絡(luò)安全的一個重要研究方向。該技術(shù)通過分析網(wǎng)絡(luò)流量或系統(tǒng)審計記錄等方式來發(fā)現(xiàn)網(wǎng)絡(luò)或系統(tǒng)中是否有違反安全策略的攻擊行為，以便制定相應(yīng)策略，彌補系統(tǒng)漏洞和填補系統(tǒng)功能。但是，在入侵檢測中，探測器收集到的數(shù)據(jù)量龐大且提取出來的特征繁多，其中有些特征與檢測無關(guān)，這些特征一方面降低了分類或聚類的精度，另一方面大大增加了學(xué)習(xí)及訓(xùn)練的時間和空間復(fù)雜度，影響算法運行效率。因此，在保證檢測正確率的前提下，如何提高系統(tǒng)的檢測速度已經(jīng)成為當(dāng)前的一個研究熱點。研究發(fā)現(xiàn)，特征選擇可以在保持原有網(wǎng)絡(luò)數(shù)據(jù)信息完整性的基礎(chǔ)上去除其中的冗余特征，達(dá)到提高系統(tǒng)檢測速度的目的。從現(xiàn)有特征選擇算法來看，文獻(xiàn)[1-3]中有諸如正向搜索（forward searching）、反向搜索（backward searching）、順序搜索（sequential searching）等啟發(fā)式搜索策略（heuristic searching strategies）；文獻(xiàn)[4]中采用了擴(kuò)張矩陣?yán)碚摵瓦z傳算法（genetic algorithm）相結(jié)合的方法等。

對于大規(guī)模數(shù)據(jù)集上的特征選擇，這些搜索策略的計算資源耗用大，收斂速度慢，時間復(fù)雜度較高。而在文獻(xiàn)[5]中提出的非搜索性策略，雖然其時間復(fù)雜度相對較低，但是所得到的特征子集中有較多冗余特征，影響了分類準(zhǔn)確率。針對現(xiàn)有算法中所存在的缺點，本文提出一種基于粒子群優(yōu)化的入侵特征選擇算法（Intrusion Feature Selection Algorithm，IFSA）。該方法引入相關(guān)性分析特征之間的關(guān)聯(lián)度，指導(dǎo)收斂速度較快的粒子群算法在特征空間里搜索，實現(xiàn)入侵特征選擇的自適應(yīng)和自優(yōu)化。

2 特征相關(guān)性分析

關(guān)聯(lián)度[6]被廣泛地應(yīng)用在機(jī)器學(xué)習(xí)和統(tǒng)計相關(guān)性分析中，用來評價特征之間的相關(guān)性，關(guān)聯(lián)度的選取在很大程度上影響著特征選擇的效率。兩個隨機(jī)變量之間的關(guān)聯(lián)度通常以基于信息論中定義的熵[7]來量度。

定義1（熵）對于一個數(shù)據(jù)集中的離散特征X，它的可能取值為{x1，x2，…，xn}，對應(yīng)的概率分布為{p(x1)，p(x2)，…，p(xn)}，則X的熵定義為：

熵表達(dá)了特征 X所包含信息量的多少，熵越小，表明X中的數(shù)據(jù)在取值上分布越不均勻，X取某個值或某幾個值的數(shù)據(jù)較多，則取其他值的數(shù)據(jù)就較少，如果X的所有數(shù)據(jù)都取同一個值，那么X的熵就為0，此時該特征所包含的信息為0，即該特征在數(shù)據(jù)集合中不存在對數(shù)據(jù)有用的信息；反之，X的熵越大，說明數(shù)據(jù)在取值上分布越均勻，其蘊含的信息越多。

定義2（聯(lián)合熵）一個數(shù)據(jù)集中的離散特征X和Y，若它們的取xi和 yj的值的聯(lián)合概率為 p(xi，yj)，則 X和Y聯(lián)合熵定義為：

聯(lián)合熵的概念是從熵引申出來的，刻畫的是兩個隨機(jī)變量之間共有的信息量，其值越大，說明兩個變量之間的相關(guān)性越大。如果兩個變量之間的聯(lián)合熵為0，則說明兩個變量是是獨立的。

3 入侵特征選擇算法

入侵特征選擇算法（IFSA）采用收斂速度較快的粒子群算法進(jìn)行特征空間搜索，引入相關(guān)性分析指導(dǎo)算法的搜索，實現(xiàn)特征選擇的自適應(yīng)和自優(yōu)化。

3.1 特征選擇定義及原則

定義3（特征子集）特征子集是將輸入屬性集合中不相關(guān)和冗余的屬性刪除后得到的新屬性集合。

定義4（特征選擇）特征選擇（也稱為屬性選擇或特征提取）是指識別和選取一個有效屬性子集，用于描述一個相對較大的通常含有冗余和不相關(guān)屬性的數(shù)據(jù)集中的有效模式。特征子集選擇過程中，算法一般根據(jù)以下原則選取有效的、最小規(guī)模的屬性集合：（1）保證分類精度不能明顯下降；（2）特征選擇前后，類的分布盡可能一致。

3.2 粒子群優(yōu)化算法

Kennedy和Eberhart受到鳥群捕食行為的研究結(jié)果啟發(fā)[8]，于1995年提出粒子群（PSO）算法，PSO算法具有執(zhí)行速度快，受維數(shù)變化影響小等優(yōu)點，迅速受到了人們的重視，算法描述如下：

假設(shè)在一個D維的目標(biāo)搜索空間中，有m個粒子組成一個群落，其中第i個粒子表示為一個 D維向量，xi= (xi1，xi2，…，xiD)T，i=1，2，…，m，即第i個粒子在D維的搜索空間中的位置是xi，每個粒子的位置就是一個潛在的解。將xi代入一個目標(biāo)函數(shù)就可以計算出其適應(yīng)值，根據(jù)適應(yīng)度的大小衡量xi的優(yōu)劣。第i個粒子的“飛翔”速度也是一個D維的向量，記為vi=(vi1，vi2，…，viD)T。第i個粒子迄今為止搜索到的最優(yōu)位置記為 pg=(pg1，pg2，…，pgD)T?；綪SO就是根據(jù)下面的兩個公式對所示的粒子進(jìn)行操作[12]：

其中，d=1，2，…，D;i=1，2，…，m，m為種群規(guī)模；ω為慣性權(quán)重，保持原速度的系數(shù)；c1是粒子跟蹤自己歷史最優(yōu)值的權(quán)重系數(shù)，它表示粒子自身的認(rèn)識，所以叫“認(rèn)知”，通常設(shè)置為2；c2是粒子跟蹤群體最優(yōu)值的權(quán)重系數(shù)，它表示粒子對整個群體知識的認(rèn)識，所以叫做“社會知識”，經(jīng)常叫做“社會”，通常設(shè)置為2；r1、r2是[0，1]之間的隨機(jī)數(shù)；η是對位置更新的時候，在速度前面加的一個系數(shù)，這個系數(shù)叫做約束因子，通常設(shè)置為1；n=1，2，…為迭代次數(shù)。

3.3 離散二進(jìn)制PSO算法

1997年Kennedy和Eberhart又提出了PSO算法的離散二進(jìn)制版本（BPSO）[10]，使這種算法進(jìn)入了組合優(yōu)化領(lǐng)域。BPSO采用二進(jìn)制編碼的形式，在BPSO模型中將每一維xi和 pi限制為1或者為0，而速度vi不作這種限制。用速度的Sigmoid函數(shù)表示位置狀態(tài)改變的可能性。

二進(jìn)制版本PSO的速度更新公式?jīng)]有改變，還是公式（3）；而位置式（4）變?yōu)椋?/p>

式中，rand()為[0，1]之間的隨機(jī)數(shù)，可用最大速度Vmax來限制xi為0或者1的可能性。利用粒子群算法解決優(yōu)化問題的關(guān)鍵在于適應(yīng)度函數(shù)選擇，適應(yīng)度函數(shù)體現(xiàn)了實際問題和優(yōu)化算法之間的聯(lián)系。

3.4 編碼模式

特征選擇的實質(zhì)就是從M個特征中，選出N個特征構(gòu)成子集。因此可以把每一個特征定義為粒子的一維離散二進(jìn)制變量，M個特征構(gòu)成粒子的M維離散二進(jìn)制空間。對于每一個粒子，如果第i位為1，表示第i個特征被選中，反之表示該特征沒有被選中。因此，每個粒子代表了一個不同的特征子集，也就是一個候選集。比如，粒子i= 100 110，那么表明特征1、特征3和特征5被選中，特征子集為{1，3，5}。

3.5 適應(yīng)度函數(shù)

在特征選擇中，適應(yīng)度評價函數(shù)的選擇至關(guān)重要。雖然人們提出了距離評測、相關(guān)性評測等幾種不同的建議，但目前還沒有能被一致接納的度量標(biāo)準(zhǔn)。本文采用相關(guān)性評測方法，其核心思想在于選擇一個屬性子集，屬性各自與類屬性有較大關(guān)聯(lián)，但幾乎沒有內(nèi)部關(guān)聯(lián)，以此達(dá)到消除無關(guān)屬性，同時也消除重復(fù)屬性的目的。兩屬性A和B之間關(guān)系可用對稱不確定性（symmetric uncertainty）來度量：

基于相關(guān)性的屬性選擇決定了一個屬性集的優(yōu)良，用公式（8）度量：

其中，C是類屬性，i和 j包括屬性集里的所有屬性。公式（8）也就是粒子群的適應(yīng)度函數(shù)，顯然值越大，粒子的適應(yīng)度越高。

3.6 算法描述

根據(jù)以上的分析，本文算法的主要步驟如下：

步驟1裝載訓(xùn)練數(shù)據(jù)集，設(shè)置初始化參數(shù)。

步驟2隨機(jī)產(chǎn)生初始群體，為每個粒子生成隨機(jī)初始化速度，設(shè)置粒子的個體極值pbest和群體的全局極值gbest。

步驟3根據(jù)公式（8）評價每個粒子的適應(yīng)值。

步驟4對每個粒子，將其適應(yīng)值與其經(jīng)歷過的最好位置pbest進(jìn)行比較，如果優(yōu)于pbest，則將其作為當(dāng)前的最好位置pbest。

步驟5對每個粒子，將其適應(yīng)值與群體所經(jīng)歷過的最好位置gbest進(jìn)行比較，若優(yōu)于gbest，則將其作為群體最優(yōu)位置，并重新設(shè)置gbest的索引號。

步驟6根據(jù)公式（3）、（5）、（6）更新粒子速度和位置。

步驟7如果迭代次數(shù)達(dá)到最大，轉(zhuǎn)步驟8；否則轉(zhuǎn)步驟3。

步驟8把群體最優(yōu)位置轉(zhuǎn)換為對應(yīng)的特征子集返回。

4 實驗過程與結(jié)果分析

4.1 實驗數(shù)據(jù)集

為了驗證算法的有效性，實驗數(shù)據(jù)采用KDD99數(shù)據(jù)集。該測試數(shù)據(jù)集收集了模擬網(wǎng)絡(luò)5個星期的運行數(shù)據(jù)，其中第1個和第3個星期是沒有攻擊的訓(xùn)練數(shù)據(jù)，用來訓(xùn)練異常檢測系統(tǒng)；第2個星期的數(shù)據(jù)是含有43個攻擊例子的測試數(shù)據(jù)（整個測試數(shù)據(jù)集有64種攻擊方法），用來訓(xùn)練誤用檢測系統(tǒng)；第4和第5星期是測試數(shù)據(jù)，所有數(shù)據(jù)集大約共計500萬條記錄，每條記錄包含41個特征（屬性）。因為KDD99數(shù)據(jù)集中的數(shù)據(jù)量非常龐大，為了便于驗證本文算法，需要對數(shù)據(jù)集進(jìn)行取樣，使數(shù)據(jù)量減少。分別對訓(xùn)練數(shù)據(jù)集與測試數(shù)據(jù)集中的數(shù)據(jù)采取隨機(jī)抽樣，然后將隨機(jī)抽樣出的數(shù)據(jù)進(jìn)行組合，形成實驗用的訓(xùn)練數(shù)據(jù)子集和測試數(shù)據(jù)子集，其中，訓(xùn)練子集共有21 836條，測試子集共有36 715條。算法參數(shù)設(shè)置如下：D=41，m=30，ω=0.9，c1=c2=2.0，Vmax=4.0，迭代次數(shù)為50次。

4.2 實驗方案

為了可以更清晰準(zhǔn)確地驗證入侵特征選擇算法的性能，設(shè)計了以下三個實驗。

實驗1比較基于所有41個特征的入侵檢測模型和基于特征選擇后的特征子集的模型在檢測時間，以及檢測準(zhǔn)確率方面的性能。首先在隨機(jī)抽樣后的數(shù)據(jù)集上應(yīng)用本文提出的特征選擇方法，得到對應(yīng)的特征子集，然后分別在訓(xùn)練集上，基于所有41個特征和特征選擇后的特征子集建立入侵檢測模型。

實驗2比較采用本文算法的入侵檢測模型與應(yīng)用遺傳算法（GA算法）和Relief算法的入侵檢測模型在檢測時間和檢測準(zhǔn)確率方面的性能。首先在數(shù)據(jù)集上應(yīng)用本文所提出的特征選擇算法，得到對應(yīng)的特征子集，并基于該特征子集建立入侵檢測模型，然后采用GA算法和Relief算法對同一訓(xùn)練數(shù)據(jù)集進(jìn)行特征選擇。

實驗3使用SVM作為分類器，比較方案二在特征選擇后得到的3個特征子集用于樣本分類時所產(chǎn)生的分類錯誤率。

4.3 實驗結(jié)果分析

首先在隨機(jī)抽樣后的實驗訓(xùn)練數(shù)據(jù)集上應(yīng)用本文的IFSA算法，所產(chǎn)生的特征子集如表1所示。

表1 應(yīng)用IFSA算法得到的特征子集

從表l中可以看出經(jīng)過特征選擇后，針對不同的攻擊得到不同的特征子集。接下來針對每一種攻擊類型，分別在未經(jīng)過特征選擇的數(shù)據(jù)集以及表1所示的特征選擇后的特征子集上建立入侵檢測模型，并對每個入侵檢測模型在檢測時間以及檢測準(zhǔn)確率上的表現(xiàn)進(jìn)行對比。對比結(jié)果如表2所示。

表2 特征選擇前后檢測率以及檢測時間的比較

從表2中可以看出，使用本文提出的算法的入侵檢測模型，在檢測準(zhǔn)確率以及檢測時間方面的表現(xiàn)都要明顯優(yōu)于未經(jīng)特征選擇的入侵檢測模型。在隨機(jī)抽樣后的實驗用訓(xùn)練數(shù)據(jù)子集上，分別應(yīng)用IFSA算法、GA算法和Relief算法，獲得的實驗結(jié)果如表3、表4所示。

表3 IFSA、GA、Relief算法分類準(zhǔn)確率對比

表4 IFSA、GA、Relief算法分類檢測時間對比

最后，使用SVM作為分類器，將IFSA算法、遺傳算法和Relief算法對實驗訓(xùn)練數(shù)據(jù)集進(jìn)行特征選擇后得到的特征子集作為分類樣本，實驗結(jié)果如表5、表6所示。

表5 SVM分類器下IFSA、GA、Relief分類準(zhǔn)確率對比

表6 SVM分類器下IFSA、GA、Relief檢測時間對比

從表4中可以看出，由本文提出的IFSA算法和基本遺傳算法所產(chǎn)生的特征子集作為分類樣本的分類準(zhǔn)確率差別不大，并且準(zhǔn)確率高于Relief算法；而在特征選擇時間方面，本文提出的方法則是表現(xiàn)最好的。

結(jié)合實驗1、實驗2以及實驗3的結(jié)果可以看出，本文提出的IFSA算法，有效降低了數(shù)據(jù)信息的特征維數(shù)；在此基礎(chǔ)上所建立的入侵檢測模型在檢測時間及檢測準(zhǔn)確率方面，表現(xiàn)均優(yōu)于未經(jīng)特征選擇的入侵檢測模型；在同GA算法及Relief算法進(jìn)行比較后，可以看出本文方法能夠在保證較高的分類準(zhǔn)確率的情況下，使特征選擇的時間復(fù)雜度降低，較為有效地縮短了特征選擇的時間。

5 總結(jié)

提出了一種基于粒子群優(yōu)化的入侵特征選擇算法，本文方法通過分析網(wǎng)絡(luò)入侵?jǐn)?shù)據(jù)中所有特征之間的相關(guān)性，利用粒子群優(yōu)化算法在所有特征空間里優(yōu)化搜索，并依據(jù)相關(guān)性進(jìn)行指導(dǎo)搜索，能夠自適應(yīng)、自優(yōu)化地選擇有效的特征子集以降低數(shù)據(jù)維度。通過建立入侵檢測模型對KDD99數(shù)據(jù)集進(jìn)行實驗驗證，結(jié)果表明，本文提出的特征選擇方法應(yīng)用于入侵檢測系統(tǒng)后，能夠在保證檢測準(zhǔn)確率的前提下，有效地提高系統(tǒng)的檢測性能，并且在檢測時間和分類準(zhǔn)確率方面的表現(xiàn)都要優(yōu)于已有特征選擇方法。

[1]詹勇，聲錫藏，王勇軍.攻擊特征自動提取技術(shù)綜述[J].通信學(xué)報，2009，30（2）：96-105.

[2]牟永敏，李美貴，粱琦.入侵檢測系統(tǒng)中模式匹配算法的研究[J].電子學(xué)報，2006，34（12A）：2488-2490.

[3]Jain A K，ZongKer D.Feature selection：evaluafion，application，and small sample performance[J].IEEE Transactions on Pattern Analysis and Machine Intelligence，1997，19（2）：153-158.

[4]陳志賢，黃皓.應(yīng)用擴(kuò)張矩陣?yán)碚摰墓籼卣魈崛J].計算機(jī)科學(xué)，2010，37（4）：49-51.

[5]Mitra P，Murthy C A，Pal S K.Unsupervised feature selection using feature similarity[J].IEEE Trans on Pattern Recognition and Machine Intelligence，2002，24（3）：301-312．

[6]肖立中，劉云翔.適合于入侵檢測的分步特征選擇算法[J].計算機(jī)工程與應(yīng)用，2010，46（11）：81-84.

[7]饒鮮，楊紹全，魏青.基于熵的入侵檢測特征參數(shù)選擇[J].系統(tǒng)工程與電子技術(shù)，2006，28（4）：599-601.

[8]Kennedy J，Eberhart R C.Particle swarm optimization[C]// ProcofIEEE Conferenceon NeuralNetworks，1995：1942-1948.

[9]赫然，王永吉，王青，等.一種改進(jìn)的自適應(yīng)逃逸微粒群算法及實驗分析[J].軟件學(xué)報，2005，16（12）：2036-2044.

[10]Eberhart R C，Kennedy J.A discrete binary version of the particle swarm algorithm[C]//Proceedings of the IEEE Conference on Systems，Man，and Cybernetics.Orlando，F(xiàn)L：IEEE Press，1997：4104-4109.

WU Qingtao,CAO Jibang,ZHENG Ruijuan,ZHANG Juwei

河南科技大學(xué) 電子信息工程學(xué)院，河南 洛陽 471003

Electronic and Information Engineering College,Henan University of Science and Technology,Luoyang,Henan 471003,China

Intrusion feature selection can improve the correctness and detection rate of the intrusion detection system effectively. A intrusion feature subset selection algorithm based on Particle Swarm Optimization（PSO）is proposed.Depending on the analyses of correlation between all features of network intrusion data,the PSO algorithm is used to search and choose effective feature subset independently to reduce data dimension in the feature space.The experimental results show that the algorithm can effectively remove redundant features,reduce the time of feature selection,ensure detection accuracy and improve detecting speed.

intrusion detection;Particle Swarm Optimization（PSO）;intrusion feature selection;optimization searching; feature relevance

A

TP393.08

10.3778/j.issn.1002-8331.1109-0031

WU Qingtao,CAO Jibang,ZHENG Ruijuan,et al.Intrusion feature selection algorithm based on Particle Swarm Optimization.Computer Engineering and Applications,2013,49（7）：89-92.

國家自然科學(xué)基金（No.61003035，No.61040010）；河南省高等學(xué)校青年骨干教師資助計劃項目（No.2009GGJS-050）；河南省教育廳自然科學(xué)基礎(chǔ)研究資助計劃項目（No.2009A520012，No.2010A520018）。

吳慶濤（1975—），男，博士，副教授，CCF會員，研究方向為計算機(jī)系統(tǒng)安全，智能信息處理；曹繼邦（1987—），男，碩士研究生，研究方向為網(wǎng)絡(luò)安全；鄭瑞娟（1980—），女，博士，副教授；張聚偉（1980—），男，博士，副教授。E-mail：wqt8921@126.com

2011-09-13

2011-12-23

1002-8331（2013）07-0089-04