基于競爭機制粒子優化算法選擇NIDS系統特征子集*

周利均

（中國電子科技網絡信息安全有限公司，四川 成都 610041）

0 引言

入侵檢測系統是計算機系統的關鍵組成部分，一般分為外部異常檢測和內部誤用檢測，近年已有相關的系統研究和綜合性論述[1-5]。異常檢測核心是通過訓練數據搭建分類模型來實時分析檢測網絡入侵行為，重點是檢測的實時性、準確性以及兼容性等。網絡入侵檢測系統通過分析TCP/IP數據流來挖掘分析潛在的異常攻擊行為，在萬物互聯的網絡時代顯得尤為重要。攻擊者攻擊手段已經向著自動化、智能化方向發展[6-7]。面對攻擊手段更加隱蔽、攻擊方式更加多樣的情況，本文研究在構建NIDS系統分類器模型中的特征優化選擇問題，以便適應海量網絡流量數據的挖掘分析。

構建NIDS系統分類器核心是選擇較為合適的特征子集[8-14]，具有D個特征的流量數據，會有2D-1種不同的特征子集組合。合適的特征子集既可以消除冗余信息，也可以降低計算的復雜度[15]。根據評價方式，特征選擇主要分為3種[16]。

（1）過濾式（Filter）：先選擇特征再訓練分類器，主要有卡方檢驗、信息增益以及相關系數法等。

（2）包裹式（Wrapper）：分類器作為分類評價函數選擇最優子集，主要有GA、PSO、DE以及ABC等算法。

（3）嵌入式（Embedding）：特征選擇與分類器學習融合，主要有正則化方法等。

以上3種方式比較，Wrapper方法具有更好的分類性能[17]，因此啟發式優化算法在該領域有廣泛應用。GA算法通過生產染色體種群解，通過每一代的選擇、交叉和突變完成進化，已有相關特征選擇研究[18-19]，在大數據等特征選擇領域也有相關研究[20-23]。人工蜂群算法通過初始化蜂群，采用不同角色之間的信息交流、轉換以及協作來實現優化，該算法也在特征選擇有相關研究[24-25]。以上方法的參數設置對優化結果有較大影響。

粒子群優化算法通過初始化粒子種群，每個粒子在搜索空間中獨立搜索其局部最優解，速度代表向最優解靠近的快慢，用位置代表移動方向，通過記憶局部最優并采取全局共享機制獲取全局最優解，所有粒子根據其局部最優和當前全局最優更新其位置和速度。PSO算法用于特征選擇問題已有相關研究[26-29]，但是PSO因其采用的經驗學習機制，存儲的個體最優極易使得算法陷入局部最優解，且針對海量數據時會消耗大量的計算資源。

基于PSO算法的思想，提出了一種基于競爭機制的粒子優化算法。該算法隨機選取粒子對競爭，競爭中的優勝者直接進入下一代，失敗者向優勝者學習。學習機制舍棄了對局部最優和當前全局最優解的依賴，因此相對PSO算法不易陷入局部最優解，且每次迭代只有一半的粒子向優勝粒子學習，因此在解決大規模數據優化方面更具有優勢。本文以KDDCUP99的訓練集（10%）和測試集[30]來對算法進行驗證，利用錯誤率和選擇特征數的線性組合為適應度函數，準確率更重要，權重值設置更大，錯誤率來源于分類結果，采用KNN等分類算法計算。

本文共分為5個部分：第1部分為序言，主要回顧該方向前期研究成果以及本文研究思路；第2部分主要介紹競爭機制粒子優化算法原理，并對算法模型進行穩定性分析，求得控制參數取值范圍，再分析了二值化方法的更新函數及流程；第3部分主要分析KDDCUP99數據集，并研究該數據集的預處理方法及流程；第4部分是實驗設計及驗證，利用提出的優化算法選擇合適的特征子集，利用選擇的特征子集搭建訓練模型，采用交叉驗證方法的訓練模型的檢測準確度進行驗證；第5部分是結論，根據本文提出的算法模型仿真得出的實驗結果得出結論，結合該方向分析和展望后續研究重點。

1 競爭機制粒子優化算法

1.1 競爭機制粒子優化算法描述

競爭機制粒子群優化算法框架見圖1，其中P(t)和P(t+1)分別代表第t和t+1代粒子群，每一代粒子群共有m個粒子，每個粒子位置和速度為n維，第i個粒子位置和速度分別表示為：

在每一次迭代過程中，粒子群P(t)被隨機分成種群大小為m/2的兩部分（若m為奇數，隨機劃分時競爭優勝者比失敗者多1個粒子，從優勝者子群里隨機選取1個補充到失敗者子群），從兩個子群中分別選擇粒子成對競爭，優勝者直接進入下一次迭代，失敗者通過學習機制向優勝者學習更新，再進入下一代，即每一次迭代每個粒子只參與1次競爭，只有m/2的粒子通過學習機制更新。可見，該算法計算消耗主要是在失敗粒子的更新上，計算復雜度為O(mn)。

圖1 競爭機制粒子優化算法框架

令Xl,k(t)和Vl,k(t)表示第t次迭代中第k輪競爭中失敗粒子的位置和速度；Xw,k(t)和Vw,k(t)表示第t次迭代中第k輪競爭中優勝粒子的位置和速度；R1(k,t),R2(k,t),R3(k,t)∈[0,1]n表示第t次迭代中，第k輪競爭中失敗者向優勝者學習的隨機數向量，其中k=1,2,3,…,m/2。

1.2 算法穩定性分析

根據式（3）和式（4），改寫得到動態方程形式：

改寫成如式（6）所示的形式，成一對一對應關系：

其中，A為狀態轉移矩陣，B為輸入矩陣。

根據勞斯穩定性判據[31]，上述動態方程穩定的充分必要條件是：勞斯表中第1列各值為正，如果勞斯表第1列中出現小于零的數值，系統不穩定，且第1列各系數符號的改變次數，代表特征方程（7）的正實部根的數目。

列出特征方程（7）的勞斯表，如表1所示。

表1 特征方程勞斯表

根據穩定的充分必要條件，第1列各值為正，R1(k,t)介于[0,1]之間是正數，只需滿足φ(R3(k,t)+R2(k,t))-R1(k,t)-1＞0，求得：

由于R1(k,t),R2(k,t),R3(k,t)∈[0,1]n，顯然不等式（8）右側取得最小值時，分母趨近于2，分子趨近于1，因此其最小值趨近于0.5，即φ＞0.5。此時，上述動態系統是穩定的，可以實現解空間內的快速收斂。

1.3 二值化方法

競爭機制粒子優化算法每次迭代時更新粒子速度，對粒子速度利用S函數[32]進行二值化處理，并根據規則對粒子位置進行0、1的離散空間處理，其中1代表選擇該特征，0代表不選擇該特征。

3種S函數表達式、S函數圖形、粒子位置離散化公式詳見表2。

表2 S函數表達式及圖形

連續空間到離散空間的映射關系詳見圖2。

2 KDDCUP99數據集預處理

2.1 KDDCUP99數據集分析

從源IP地址到目標IP地址，通過TCP或UDP協議建立連接，每個網絡連接分為正常或異常。異常類型共分為4大類共39種攻擊類型，其中22種攻擊類型在訓練集中，另外17種攻擊類型在測試集中。4種異常類型分類如下。

圖2 連續空間到離散空間映射關系

（1）Denial of Service Attacks（DoS）：拒 絕服務攻擊，有back、land、neptune、pod、smurf和teardrop共6種。

（2）User to Root Attacks（U2R）：來自遠程主機的未授權訪問，有ipsweep、nmap、portsweep和satan共4種；

（3）Remote to Local attacks（R2L）：未授權的本地超級用戶特權訪問，有ftp_write、guess_passwd、imap、multihop、phf、spy、warezclient和warezmaster共8種。

（4）Probing attacks：端口監視或掃描，以躲避系統安全控制獲取信息，有buffer_overflow、loadmodule、perl和rootkit共4種。

KDDCUP99每一條連接記錄由41個特征組成，分為4種類型（基本特征，內容特征，內容特征，流量特征），第42位是特征標簽，特征數據結構見圖3。KDDCUP99由約500萬條記錄組成，同時還包括10%的訓練子集和測試子集，樣本類別分布如圖3所示。部分特征屬于字符型，在數據預處理時需要轉換成數值型；部分連續性數據需進行數據標準化處理，避免出現數據覆蓋現象。

圖3 特征數據結構

2.2 字符型轉換成數值型

圖3為KDDCUP99數據集特征數據的數據結構，斜體下劃線標注的是字符型特征，根據其在列表中出現的順序值進行數值替換。以protocol-type為例，有3種協議類型，依次為tcp、udp和icmp，根據上述原則一次將其替換成0，1，2。同樣，service共有70種網絡服務類型，轉換成數值0～69；flag共有11種網絡連接狀態，轉換成數值0～10；label共有22種攻擊類型，外加正常狀態標識normal（放在攻擊類型之前），轉換成數值0～22。

以上將KDDCUP99數據集中字符型轉換成了數值型，便于后續進一步進行數據處理。

2.3 數據標準化

KDDCUP99數據集中特征數據較為分散，特征數據的數值類型有連續型和離散型，連續型特征數據之間的數值差也較大。為了避免數值差異較大導致的數據覆蓋現象，提高模型訓練速度，需對數據進行標準化處理。本文采用極值法，即帶正向指標的極差變換法。通過式（9）處理后，數據被標準化至[0，1]區間。

3 實驗設計及驗證

3.1 適應度函數

本文適應度函數采用分類錯誤率與特征數的線性組合，通過調整權重系數α的值分配分類錯誤率和特征數影響比重：

ErrorRate代表分率錯誤率，由python自帶KNN分類器計算；d代表第i個粒子所選取的特征數；D是每個粒子總的特征數，針對KDDCUP99數據集，D為41；α為權重值，用于調節錯誤率和選擇特征數權重。

3.2 參數設置

經過數據預處理的KDDCUP99數據集共有494 021條數據，利用train_test_split函數將該數據集隨機分成訓練集和測試集。在進行模型訓練和預測中，為了便于快速計算，隨機從訓練集和測試集中各選取1 000條數據，數據標簽選取相對應的標簽。

用預測精度、最優適應度值、最差適應度值、平均適應度值以及選擇特征來評估模型預測結果。

參數設置如表4所示。

表4 參數設置

3.3 實驗結果

3個S函數所對應的預測精度、最優適應度值、最差適應度值以及平均適應度值如表5所示。

表5 預測精度及適應度值

3個S函數所對應的選擇特征數個數及位置如表6所示，在每條記錄41個特征中，0表示不選擇，1表示選擇。

表6 特征數個數及位置

適應度值變化曲線詳見圖4。可以看出，初始化適應度值在迭代之處能到達一個較為理想的水平，且SFunc1較另外兩個轉換函數較為平整，SFunc2和SFunc3均有較大突變，突變后趨于穩定。可以看出，基于競爭機制的二值化粒子優化算法具有在短時間內可以到達較為穩定的狀況。

以SFunc1為例，設置K值范圍為1～20，采用sklearn的cross_val_score進行交叉驗證，求取準確度的平均值。通過比較準確度值，選取最合適的K值，實現參數調優。通過仿真計算，準確度隨K值變化曲線詳見圖5，其中K=4時準確度為0.994 5，此時為模型參數最優。

圖4 適應度值變化曲線

圖5 精確度隨K（實例個數）值變化曲線

4 結語

本文采用二值化競爭機制粒子優化算法優化選擇KDDCUP99數據集的特征子集，實現數據的降維處理，創新性地采用穩定性理論分析算法模型，選取調控參數取值范圍，分析了KDDCUP99數據集的預處理思路、方法和流程，并采用sklearn的KNN算法搭建訓練模型，利用選擇的特征子集進行模型訓練，利用交叉驗證機制對模型進行精確度校驗。實驗結果表明，通過優化算法選取的特征子集搭建的訓練模型具有較高的精確度，且在處理大數據時具有較大優勢。

本文以KDDCUP99數據集進行驗證。KDDCUP99數據集主要是網絡流量數據，在入侵檢測領域具有較高的代表性。后續將以實際入侵檢測模型搭建需求為牽引，將本文研究的優化算法結合實際需求搭建合適的入侵檢測模型，對實際的入侵檢測行為進行實時的分析感知。