KNN-IPSO選擇特征的網絡入侵檢測

馮瑩瑩，余世干，劉輝

阜陽師范學院信息工程學院，安徽阜陽 236041

KNN-IPSO選擇特征的網絡入侵檢測

馮瑩瑩，余世干，劉輝

阜陽師范學院信息工程學院，安徽阜陽 236041

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

入侵檢測；特征選擇；特征關聯性；改進粒子群算法

1 引言

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

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

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

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

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

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

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

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

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

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

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

3 改進粒子群算法選擇網絡入侵檢測特征

3.1 改進的粒子群算法

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

式中，t表示迭代次數；ω稱為慣性權重；c1、c2為學習因子，rand是在0～1的隨機函數；pbest表示粒子本身經歷過的最好位置；gbest表示種群經歷過的歷史最好位置[10]。

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

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

圖1 幾種改進粒子群優化算法的性能對比

3.2 編碼規則

對于給定含有m維特征的網絡狀態數據集D，特征選擇的目的是選擇出一個滿足目標函數最優的特征子集R，粒子的個體采用二進制編碼規則，選中的特征取為1，否則為0。

3.3 適應度函數

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

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

3.4 IPSO的特征選擇步驟

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

（2）收集網絡狀態信息，提取網絡狀態特征。

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

（4）計算當前種群每一粒子的適應度值，選取出粒子歷史最優值和全局最優位置。

（5）根據式（4）對慣性權重進行自適應調整，并根據式（1）、（2）更新粒子的位置和速度。

式中，ωmax，ωmin分別為慣性權重的最大值和最小值；ti為當前迭代次數；tmax為最大迭代次數。

（6）計算更新后粒子群的適應度值，并更新粒子最優位置和全局最優位置。

（7）判斷是否達到迭代次數，若達到條件，則進入步驟（10）；否則進入步驟（8）。

（8）根據式（5）計算種群適應度方差，如果適應度方差小于門限值，表示易陷入局部最優，則進入步驟（7）進行混沌處理，否則轉入步驟（5）繼續執行。

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

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

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

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

②將r作為Jerk混沌系統的初值X(0)，產生M個隨機數列。

③將混沌序列還原至原優化變量取值區間，分別計算出對應的適應度值。

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

（10）根據種群的最優位置得到最優特征子集。

4 仿真實驗

4.1 仿真環境

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

表1 KDD CUP 99的特征

4.2 對比模型和評價標準確度

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

4.3 網絡數據歸一化

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

式中，n表示訓練樣本數，xstd表示樣本特征標準差。

4.4 KNN參數K值的確定

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

圖2 參數K值對網絡入侵檢測正確率的影響

從圖1知，當KNN的K值從1增加到4時，網絡入侵檢測的平均正確率大幅度提高；從4增加到7時，網絡入侵檢測的平均正確率提高幅度較小，當K=7時，達到最優檢測正確率；當K值大于7時，檢測正確率逐漸降低，因此KNN的參數K=7。

4.5 結果分析

4.5.1 與原始特征的性能比較

采用KNN-IPSO特征選擇方法對訓練集進行特征選擇，提到的特征子集見表2。從表2可知，采用KNN-IPSO對原始特征進行選擇后，大幅度降低了特征維數，結果表明，KNN-IPSO算法是一種有效的網絡入侵特征選擇算法。

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

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

表3 特征選擇前后的網絡入侵檢測性能對比

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

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

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

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

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

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

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

5 結束語

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

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

[2]姜春茂，張國印，李志聰.基于遺傳算法優化SVM的嵌入式網絡系統異常入侵檢測[J].計算機應用與軟件，2011，28（2）：287-289.

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

[4]牟琦，畢孝儒，庫向陽.基于GQPSO算法的網絡入侵特征選擇方法[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]郭文忠，陳國龍，陳慶良，等.基于粒子群優化算法和相關性分析的特征子集選擇[J].計算機科學，2008，35（2）：144-146.

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

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

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

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

[12]孫蘭蘭，王曉超.求解高位函數優化的動態粒子群算法[J].計算機工程與應用，2011，47（27）：36-38.

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

[14]陳友，沈華偉，李洋.一種高效的面向入侵檢測系統的特征選擇算法[J].計算機學報，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

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

馮瑩瑩（1982—），女，講師，主要研究領域為網絡安全及計算機圖形學；余世干（1982—），男，講師，主要研究領域為嵌入式系統開發；劉輝（1979—），男，講師，主要研究領域為計算機圖像處理。

2013-12-18

2014-03-12

1002-8331（2014）17-0095-05