KNN-IPSO選擇特征的網(wǎng)絡(luò)入侵檢測

馮瑩瑩，余世干，劉輝

阜陽師范學(xué)院信息工程學(xué)院，安徽阜陽 236041

KNN-IPSO選擇特征的網(wǎng)絡(luò)入侵檢測

馮瑩瑩，余世干，劉輝

阜陽師范學(xué)院信息工程學(xué)院，安徽阜陽 236041

為了提高網(wǎng)絡(luò)入侵檢測的正確率，提出一種基于KNN-IPSO選擇特征的網(wǎng)絡(luò)入侵檢測模型（KNN-IPSO）。首先采用K近鄰算法消除原始網(wǎng)絡(luò)數(shù)據(jù)中的冗余特征，并將其作為粒子群算法的初始解，然后采用粒子群算法找到最優(yōu)特征子集，并對粒子的慣性權(quán)重進(jìn)行自適應(yīng)調(diào)整和種群進(jìn)行混沌操作，幫助種群跳出局部最優(yōu)，最后采用KDD CUP 99數(shù)據(jù)集對KNN-IPSO的性能進(jìn)行測試。結(jié)果表明，KNN-IPSO消除了冗余特征，降低了分類器的輸入維數(shù)，有效提高了入侵檢測正確率和檢測速度。

入侵檢測；特征選擇；特征關(guān)聯(lián)性；改進(jìn)粒子群算法

1 引言

隨著Internet用戶增加，網(wǎng)絡(luò)規(guī)模越來越龐大，網(wǎng)絡(luò)入侵事件日益增多，入侵檢測系統(tǒng)作為安全防御的最后一道防線，能夠檢測各種形式的入侵行為，因此網(wǎng)絡(luò)入侵檢測一直是網(wǎng)絡(luò)安全中的研究熱點[1-2]。

在網(wǎng)絡(luò)入侵檢測過程中，特征選擇結(jié)果優(yōu)劣對網(wǎng)絡(luò)檢測速度和正確率產(chǎn)生直接影響[3]。原始網(wǎng)絡(luò)數(shù)據(jù)包括大量冗余或無用特征，易出現(xiàn)“維數(shù)災(zāi)難”問題，而且入侵檢測過程需要對海量數(shù)據(jù)進(jìn)行處理，實時性要求高。特征選擇是指在保持原有網(wǎng)絡(luò)數(shù)據(jù)信息完整性的基礎(chǔ)上，剔除無用或者冗余特征，以提高網(wǎng)絡(luò)入侵檢測效率[4]。當(dāng)前網(wǎng)絡(luò)特征選擇方法主要有模擬退火算法、蟻群算法、粒子群優(yōu)化算法等群智能算法進(jìn)行特征選擇[1，5-6]。其中粒子群優(yōu)化（Particle Swarm optimization，PSO）算法具有實現(xiàn)簡單，需調(diào)整的參數(shù)少等優(yōu)點，在網(wǎng)絡(luò)入侵特征選擇中應(yīng)用最為廣泛[7]。由于入侵檢測數(shù)據(jù)的特征維數(shù)比較高，直接采用PSO進(jìn)行特征選擇，效率低，而且PSO算法易過早收斂和陷入局部極值，影響特征選擇性能[8]。

為了提高網(wǎng)絡(luò)入侵檢測的正確率和檢測效率，提出一種基于KNN-IPSO選擇特征的網(wǎng)絡(luò)入侵檢測模型（KNN-IPSO）。首先采用K近鄰算法消除原始網(wǎng)絡(luò)數(shù)據(jù)中的冗余特征，并將其作為粒子群算法的初始解，然后通過粒子之間信息共享、協(xié)作找到最優(yōu)特征子集，最后采用KDD CUP 99數(shù)據(jù)集對KNN-IPSO的性能進(jìn)行測試。

2 KNN生成IPSO算法的初始特征子集

設(shè)原始網(wǎng)絡(luò)狀態(tài)特征數(shù)目為M，那么特征集可以表示為：O={Fi，i=1，2，…，M}；消除冗余特征的網(wǎng)絡(luò)狀態(tài)特征子集為R；λ(Fi，F(xiàn)j)用于度量特征Fi和Fj之間關(guān)聯(lián)度；表示特征Fi與消除冗余特征子集R第K個近鄰特征的關(guān)聯(lián)度[9]。KNN算法生成的初始特征子集步驟具體如下：

（1）確定KNN算法的初始K值，初始化消除冗余特征子集R，使R=O。

（2）計算特征子集R中的一個每個特征Fi值。

（3）找出Fi值最小的對應(yīng)的特征，選擇，將其K個最相近特征刪除，令ε=。

（4）若有K＞cardinality(R)-1，那么K=cardinality(R)-1。

（5）若K=1，表示R中沒有特征和其近鄰的λ值小于ε了，轉(zhuǎn)到步驟（8）。

（8）將此時R中特征作IPSO算法的初始特征子集，有效地消除了冗余和無用特征。

3 改進(jìn)粒子群算法選擇網(wǎng)絡(luò)入侵檢測特征

3.1 改進(jìn)的粒子群算法

在標(biāo)準(zhǔn)粒子群（PSO）算法中，每個粒子均具有自己的位置和速度，粒子的位置代表問題的一個可行解，每個粒子按式（1）更新自己的速度v和位置x：

式中，t表示迭代次數(shù)；ω稱為慣性權(quán)重；c1、c2為學(xué)習(xí)因子，rand是在0～1的隨機(jī)函數(shù)；pbest表示粒子本身經(jīng)歷過的最好位置；gbest表示種群經(jīng)歷過的歷史最好位置[10]。

當(dāng)粒子群中粒子陷入局部最優(yōu)后，粒子速度變化接近零，種群多樣性迅速減小，很難跳出局部最優(yōu)值，因此，PSO算法極易陷入局部最優(yōu)解。為了解決該難題，本文提出一種改進(jìn)粒子群（Improved Particle Swarm optimization，IPSO）算法，具體改進(jìn)思想為：首先對慣性權(quán)重進(jìn)行自適應(yīng)調(diào)整，動態(tài)調(diào)整參數(shù)；然后根據(jù)粒子群的適應(yīng)度方差判斷是否陷入局部最優(yōu)，如果陷入局部最優(yōu)，則對種群進(jìn)行混沌擾動，增加粒子種群的多樣性，使粒子易于擺脫局部最優(yōu)，提高全局搜索能力。

為了說明本文改進(jìn)粒子算法（IPSO）的優(yōu)越性，利用2個測試函數(shù)與文獻(xiàn)[11-12]的改進(jìn)粒子群算法的性能進(jìn)行對比。算法參數(shù)：加速常數(shù)c1=c2=2，慣性權(quán)重在[0.4，0.9]之間隨代數(shù)線性遞減，函數(shù)維度設(shè)置為30，種群規(guī)模設(shè)置為20，每次運行迭代6 000次，每個函數(shù)獨立搜索運行30次。不同改進(jìn)粒子群算法的適應(yīng)度的對數(shù)值變化曲線如圖1所示。從圖1可知，IPSO算法的收斂速度明顯優(yōu)于對比算法，尤其對于多峰值Rastrigin函數(shù)，IPSO算法以最快速度找到最優(yōu)解，而文獻(xiàn)[11-12]的改進(jìn)粒子群算法收斂速度慢，因此本文IPSO算法的搜索能力、收斂精度和收斂速度均優(yōu)于對比算法。

圖1 幾種改進(jìn)粒子群優(yōu)化算法的性能對比

3.2 編碼規(guī)則

對于給定含有m維特征的網(wǎng)絡(luò)狀態(tài)數(shù)據(jù)集D，特征選擇的目的是選擇出一個滿足目標(biāo)函數(shù)最優(yōu)的特征子集R，粒子的個體采用二進(jìn)制編碼規(guī)則，選中的特征取為1，否則為0。

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

入侵特征選擇目標(biāo)包括兩個方面：（1）網(wǎng)絡(luò)入侵檢測正確率更高；（2）特征維數(shù)盡量最少，則適應(yīng)度函數(shù)由所選特征子集的大小和檢測正確率兩部分組成。適應(yīng)度函數(shù)計算公式為：

式中，d為選取特征子集的維數(shù)；D為入侵檢測原始特征維數(shù)；Prate表示檢測正確率；λ為檢測正確率權(quán)重系數(shù)。

3.4 IPSO的特征選擇步驟

（1）設(shè)置IPSO最大迭代次數(shù)，位置和速度變化范圍等參數(shù)值。

（2）收集網(wǎng)絡(luò)狀態(tài)信息，提取網(wǎng)絡(luò)狀態(tài)特征。

（3）采用0/1串位表示特征集，根據(jù)特征間的關(guān)聯(lián)度，采用KNN算法來消除原始特征集的冗余特征，得到IPSO群算法的初始特征子集。

（4）計算當(dāng)前種群每一粒子的適應(yīng)度值，選取出粒子歷史最優(yōu)值和全局最優(yōu)位置。

（5）根據(jù)式（4）對慣性權(quán)重進(jìn)行自適應(yīng)調(diào)整，并根據(jù)式（1）、（2）更新粒子的位置和速度。

式中，ωmax，ωmin分別為慣性權(quán)重的最大值和最小值；ti為當(dāng)前迭代次數(shù)；tmax為最大迭代次數(shù)。

（6）計算更新后粒子群的適應(yīng)度值，并更新粒子最優(yōu)位置和全局最優(yōu)位置。

（7）判斷是否達(dá)到迭代次數(shù)，若達(dá)到條件，則進(jìn)入步驟（10）；否則進(jìn)入步驟（8）。

（8）根據(jù)式（5）計算種群適應(yīng)度方差，如果適應(yīng)度方差小于門限值，表示易陷入局部最優(yōu)，則進(jìn)入步驟（7）進(jìn)行混沌處理，否則轉(zhuǎn)入步驟（5）繼續(xù)執(zhí)行。

式中，fi為每一個粒子的適應(yīng)度值；為當(dāng)前粒子群的適應(yīng)度平均值；f為歸一化因子；用于限制σ2的大小。

σ2越小，說明粒子群中粒子波動越小，種群越趨于統(tǒng)一。理論上在全局收斂和早熟收斂情況下σ2=0。但實際上σ2不可能達(dá)到0，故在實際判決時，僅需判斷σ2小于某一門限值（本文σ2=10-4），即可認(rèn)為當(dāng)前粒子群已陷入局部最優(yōu)。

（9）粒子群的混沌擾動。當(dāng)粒子群陷入局部極值時，以當(dāng)前粒子群的gbest為基礎(chǔ)產(chǎn)生混沌序列，并用混沌序列中的適應(yīng)度值最優(yōu)解來代替當(dāng)前粒子群中的任一粒子的位置，具體步驟如下：

①將gbest歸一化至混沌擾動量r的基本取值范圍[0，1]。

②將r作為Jerk混沌系統(tǒng)的初值X(0)，產(chǎn)生M個隨機(jī)數(shù)列。

③將混沌序列還原至原優(yōu)化變量取值區(qū)間，分別計算出對應(yīng)的適應(yīng)度值。

④將最小的適應(yīng)度值對應(yīng)的粒子，代替粒子群中原任一粒子的位置，由于混沌擾動的初值根據(jù)全局最優(yōu)位置決定，可產(chǎn)生當(dāng)前全局最優(yōu)位置附近的若干相鄰點，可以幫助陷入局部最優(yōu)的粒子逃離局部收斂。

（10）根據(jù)種群的最優(yōu)位置得到最優(yōu)特征子集。

4 仿真實驗

4.1 仿真環(huán)境

為了測試KNN-IPSO的性能，在P4 3.0 GHz CPU、2 GB RAM，window s XP環(huán)境中，采用VC++編程實現(xiàn)仿真實驗。數(shù)據(jù)來自入侵檢測的標(biāo)準(zhǔn)數(shù)據(jù)集——KDD CUP 99數(shù)據(jù)集，該數(shù)據(jù)集包括9個星期的空軍局域網(wǎng)絡(luò)連接數(shù)據(jù)，其中訓(xùn)練集包含500萬條記錄，測試集包含200萬條記錄，每一個記錄包含41個特征，具體見表1。IPSO算法參數(shù)：c1=c2=1.5，種群規(guī)模m=20，最大迭代次數(shù)tmax=1 000，ωmax=0.9，ωmin=0.4。

表1 KDD CUP 99的特征

4.2 對比模型和評價標(biāo)準(zhǔn)確度

為了對KNN-IPSO特征選擇方法的性能進(jìn)行全面、準(zhǔn)確地衡量，首先不采用KNN選擇特征，直接采用改進(jìn)粒子群算法進(jìn)行特征選擇（IPSO）；采用KNN對特征進(jìn)行初始選擇，然后采用基本粒子群優(yōu)化算法（PSO）、蟻群算法（ACO）對相同訓(xùn)練集進(jìn)行特征選擇，并建立相應(yīng)的入侵檢測模型，它們分別命名為：KNN-PSO、KNN-ACO模型，所以模型均采用支持向量機(jī)作為分類器。模型性能評價標(biāo)準(zhǔn)為：檢測時間、檢測正確率和誤報率，其中誤報率和檢測正確率的定義如下：

4.3 網(wǎng)絡(luò)數(shù)據(jù)歸一化

在KDD CUP 99數(shù)據(jù)集中，樣本特征屬性范圍各異，而支持向量機(jī)分類是根據(jù)樣本與超平面距離來確定樣本的歸屬，因此少量特征對支持向量分類性能影響大，其他特征影響較小，因此需要進(jìn)行預(yù)處理來消除這種不利影響，對其進(jìn)行歸一化處理，具體為：

式中，n表示訓(xùn)練樣本數(shù)，xstd表示樣本特征標(biāo)準(zhǔn)差。

4.4 KNN參數(shù)K值的確定

KNN算法首先要確定參數(shù)K的值，為此，K的值從1開始，逐漸增加，然后觀察K值選取對網(wǎng)絡(luò)入侵檢測平均正確率的影響，結(jié)果見圖2。

圖2 參數(shù)K值對網(wǎng)絡(luò)入侵檢測正確率的影響

從圖1知，當(dāng)KNN的K值從1增加到4時，網(wǎng)絡(luò)入侵檢測的平均正確率大幅度提高；從4增加到7時，網(wǎng)絡(luò)入侵檢測的平均正確率提高幅度較小，當(dāng)K=7時，達(dá)到最優(yōu)檢測正確率；當(dāng)K值大于7時，檢測正確率逐漸降低，因此KNN的參數(shù)K=7。

4.5 結(jié)果分析

4.5.1 與原始特征的性能比較

采用KNN-IPSO特征選擇方法對訓(xùn)練集進(jìn)行特征選擇，提到的特征子集見表2。從表2可知，采用KNN-IPSO對原始特征進(jìn)行選擇后，大幅度降低了特征維數(shù)，結(jié)果表明，KNN-IPSO算法是一種有效的網(wǎng)絡(luò)入侵特征選擇算法。

表2 KNN-IPSO算法選擇的特征子集

對每一種網(wǎng)絡(luò)入侵類型，采用支持向量機(jī)對表2中的特征子集和原始特征集建立相應(yīng)的入侵檢測模型，不同模型的檢測時間和正確率見表3。從表3中可知，相對于原始特征的入侵檢測模型，KNN-IPSO網(wǎng)絡(luò)入侵檢測模型的檢測時間大幅度降低，這主要是由于采用KNN-IPSO進(jìn)行特征選擇后，消除大量的冗余特征，減少了分類器輸入向量維數(shù)，計算時間復(fù)雜度降低，提高了網(wǎng)絡(luò)入侵檢測效率；同時網(wǎng)絡(luò)入侵檢測正確率得以明顯提高，這表明冗余特征會對網(wǎng)絡(luò)分類器的分類性能產(chǎn)生不利影響，導(dǎo)致全部原始特征的入侵檢測模型檢測正確率降低，說明了對網(wǎng)絡(luò)入侵檢測進(jìn)行特征選擇是必須，可以獲得更優(yōu)的網(wǎng)絡(luò)入侵檢測效果。

表3 特征選擇前后的網(wǎng)絡(luò)入侵檢測性能對比

4.5.2 與其他特征算法的性能比較

KNN-IPSO和其他特征算法的入侵檢測結(jié)果如圖3～4所示。對圖3～4的結(jié)果進(jìn)行分析，可以得到如下結(jié)論：

（1）相對于IPSO算法，KNN-IPSO的網(wǎng)絡(luò)入侵檢測性能優(yōu)勢比較明顯，這表明對特征維數(shù)較高的入侵檢測數(shù)據(jù)，直接采用IPSO進(jìn)行特征選擇，檢測時間長，效率低，然而KNN-IPSO算法通過KNN消除網(wǎng)絡(luò)入侵的冗余特征，得到了更優(yōu)的IPSO初始特征，使IPSO的尋優(yōu)目標(biāo)更加明確，迭代次數(shù)減少，減少了檢測時間，提高了網(wǎng)絡(luò)入侵檢測速度，同時KNN-IPSO找到了更優(yōu)的網(wǎng)絡(luò)特征子集，網(wǎng)絡(luò)入侵檢測正確率相應(yīng)得到提高。

（2）相對于KNN-PSO算法，KNN-IPSO的網(wǎng)絡(luò)入侵檢測綜合性能明顯提升，這說明IPSO通過對粒子群最優(yōu)位置進(jìn)行混沌擾動，幫助陷入局最優(yōu)的粒子逃離局部最優(yōu)位置，找到全局最優(yōu)的網(wǎng)絡(luò)特征子集，消除冗余特征的不利影響，檢測速度更快，提高了網(wǎng)絡(luò)入侵檢測正確率。

圖3 不同特征選擇算法的檢測率比較

圖4 不同特征選擇算法檢測時間比較

（3）相對于KNN-ACO算法，KNN-IPSO不僅提高了網(wǎng)絡(luò)入侵檢測正確率，同時檢測時間相應(yīng)減少，這表明采用KNN-IPSO可以獲得比KNN-ACO算法更優(yōu)的特征子集，降低了計算時間復(fù)雜度，建立了性能更優(yōu)的網(wǎng)絡(luò)入侵檢測模型，可以滿足現(xiàn)代大規(guī)模、高維的網(wǎng)絡(luò)入侵檢測在線、實時要求。

5 結(jié)束語

網(wǎng)絡(luò)入侵檢測要求實時性要求，特征太多會導(dǎo)致計算量大，檢測時間慢，而且無用或冗余特征對網(wǎng)絡(luò)入侵檢測產(chǎn)生不利影響，為了解決該難題，提出一種基于KNN-IPSO的網(wǎng)絡(luò)入侵檢測模型（KNN-IPSO）。結(jié)果表明，KNN-IPSO在保證檢測準(zhǔn)確率的前提下，大幅度提高了入侵檢測效率，可以滿足特征復(fù)雜多變的網(wǎng)絡(luò)入侵檢測要求。

[1]閆新娟，譚敏生，嚴(yán)亞周，等.基于隱馬爾科夫模型和神經(jīng)網(wǎng)絡(luò)的入侵檢測研究[J].計算機(jī)應(yīng)用與軟件，2012，29（2）：294-297.

[2]姜春茂，張國印，李志聰.基于遺傳算法優(yōu)化SVM的嵌入式網(wǎng)絡(luò)系統(tǒng)異常入侵檢測[J].計算機(jī)應(yīng)用與軟件，2011，28（2）：287-289.

[3]井小沛，汪厚祥，聶凱，等.面向入侵檢測的基于IMGA和MKSVM的特征選擇算法[J].計算機(jī)科學(xué)，2012，39（7）：96-100.

[4]牟琦，畢孝儒，庫向陽.基于GQPSO算法的網(wǎng)絡(luò)入侵特征選擇方法[J].計算機(jī)工程，2011，37（14）：103-105.

[5]Denning D E.An intrusion detection model[J].IEEE Transactions on Software Engineering，2010，13（2）：222-232.

[6]Hang C L，Wang C J.A GA-based feature selection and parameters optimization for support vector machines[J].Expert Systems with Applications，2009，31（2）：231-240.

[7]郭文忠，陳國龍，陳慶良，等.基于粒子群優(yōu)化算法和相關(guān)性分析的特征子集選擇[J].計算機(jī)科學(xué)，2008，35（2）：144-146.

[8]高海華，楊輝華，王行愚.基于BPSO-SVM的網(wǎng)絡(luò)入侵征選擇和檢測[J].計算機(jī)工程，2006，32（8）：37-39.

[9]陳仕濤，陳國龍，郭文忠，等.基于粒子群優(yōu)化和鄰域約簡的入侵檢測日志數(shù)據(jù)特征選擇[J].計算機(jī)研究與發(fā)展，2010，47（7）：1261-1267.

[10]李洋，方濱興，郭莉，等.基于TCM-KNN和遺傳算法的網(wǎng)絡(luò)異常檢測技術(shù)[J].通信學(xué)報，2007，28（12）：48-52.

[11]李莉，李洪奇.基于混合粒子群算法的高維復(fù)雜函數(shù)求解[J].計算機(jī)應(yīng)用，2007，27（7）：1754-1756.

[12]孫蘭蘭，王曉超.求解高位函數(shù)優(yōu)化的動態(tài)粒子群算法[J].計算機(jī)工程與應(yīng)用，2011，47（27）：36-38.

[13]張雪芹，顧春華.一種網(wǎng)絡(luò)入侵檢測特征提取方法[J].華南理工大學(xué)學(xué)報：自然科學(xué)版，2010，38（1）：81-85.

[14]陳友，沈華偉，李洋.一種高效的面向入侵檢測系統(tǒng)的特征選擇算法[J].計算機(jī)學(xué)報，2007，30（8）：1398-1408.

FENG Yingying, YU Shigan, LIU Hui

College of Information Engineering, Fuyang Teachers College, Fuyang, Anhui 236041, China

In order to improve the detection accuracy of network intrusion,this paper proposes a novel network intrusion detection model（KNN-IPSO）based on K Nearest Neighbor and Improved Particle Swarm optimization algorithm to select the features.Firstly,KNN algorithm is used to eliminate redundant features and remove the redundant features of network data and the selected features are taken as the initial solution of PSO,secondly,the optimal features are obtained by PSO which inertia weight is adjusted adaptively and chaotic system is intruded to help the swarm s jump out the local optimal solutions,finally the KDD CUP 99 data sets are used to test the performance of KNN-IPSO.The results show that the proposed model can eliminate the redundant features and reduce the input dimensions of classifier.It can improve the network intrusion detection accuracy and detection speed.

intrusion detection; feature selection; feature relevance; improved particle swarm optimization algorithm

FENG Yingying, YU Shigan, LIU Hui. Network intrusion detection based on KNN-IPSO selecting features. Computer Engineering and Applications, 2014, 50（17）：95-99.

A

TP391

10.3778/j.issn.1002-8331.1312-0257

安徽省高等學(xué)校省級自然科學(xué)研究項目（No.KJ2013B206）；安徽省高校省級優(yōu)秀青年人才基金重點項目（No.2013SQRL102ZD）。

馮瑩瑩（1982—），女，講師，主要研究領(lǐng)域為網(wǎng)絡(luò)安全及計算機(jī)圖形學(xué)；余世干（1982—），男，講師，主要研究領(lǐng)域為嵌入式系統(tǒng)開發(fā)；劉輝（1979—），男，講師，主要研究領(lǐng)域為計算機(jī)圖像處理。

2013-12-18

2014-03-12

1002-8331（2014）17-0095-05