基于競(jìng)爭(zhēng)機(jī)制粒子優(yōu)化算法選擇NIDS系統(tǒng)特征子集*

周利均

（中國(guó)電子科技網(wǎng)絡(luò)信息安全有限公司，四川 成都 610041）

0 引言

入侵檢測(cè)系統(tǒng)是計(jì)算機(jī)系統(tǒng)的關(guān)鍵組成部分，一般分為外部異常檢測(cè)和內(nèi)部誤用檢測(cè)，近年已有相關(guān)的系統(tǒng)研究和綜合性論述[1-5]。異常檢測(cè)核心是通過(guò)訓(xùn)練數(shù)據(jù)搭建分類模型來(lái)實(shí)時(shí)分析檢測(cè)網(wǎng)絡(luò)入侵行為，重點(diǎn)是檢測(cè)的實(shí)時(shí)性、準(zhǔn)確性以及兼容性等。網(wǎng)絡(luò)入侵檢測(cè)系統(tǒng)通過(guò)分析TCP/IP數(shù)據(jù)流來(lái)挖掘分析潛在的異常攻擊行為，在萬(wàn)物互聯(lián)的網(wǎng)絡(luò)時(shí)代顯得尤為重要。攻擊者攻擊手段已經(jīng)向著自動(dòng)化、智能化方向發(fā)展[6-7]。面對(duì)攻擊手段更加隱蔽、攻擊方式更加多樣的情況，本文研究在構(gòu)建NIDS系統(tǒng)分類器模型中的特征優(yōu)化選擇問(wèn)題，以便適應(yīng)海量網(wǎng)絡(luò)流量數(shù)據(jù)的挖掘分析。

構(gòu)建NIDS系統(tǒng)分類器核心是選擇較為合適的特征子集[8-14]，具有D個(gè)特征的流量數(shù)據(jù)，會(huì)有2D-1種不同的特征子集組合。合適的特征子集既可以消除冗余信息，也可以降低計(jì)算的復(fù)雜度[15]。根據(jù)評(píng)價(jià)方式，特征選擇主要分為3種[16]。

（1）過(guò)濾式（Filter）：先選擇特征再訓(xùn)練分類器，主要有卡方檢驗(yàn)、信息增益以及相關(guān)系數(shù)法等。

（2）包裹式（Wrapper）：分類器作為分類評(píng)價(jià)函數(shù)選擇最優(yōu)子集，主要有GA、PSO、DE以及ABC等算法。

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

以上3種方式比較，Wrapper方法具有更好的分類性能[17]，因此啟發(fā)式優(yōu)化算法在該領(lǐng)域有廣泛應(yīng)用。GA算法通過(guò)生產(chǎn)染色體種群解，通過(guò)每一代的選擇、交叉和突變完成進(jìn)化，已有相關(guān)特征選擇研究[18-19]，在大數(shù)據(jù)等特征選擇領(lǐng)域也有相關(guān)研究[20-23]。人工蜂群算法通過(guò)初始化蜂群，采用不同角色之間的信息交流、轉(zhuǎn)換以及協(xié)作來(lái)實(shí)現(xiàn)優(yōu)化，該算法也在特征選擇有相關(guān)研究[24-25]。以上方法的參數(shù)設(shè)置對(duì)優(yōu)化結(jié)果有較大影響。

粒子群優(yōu)化算法通過(guò)初始化粒子種群，每個(gè)粒子在搜索空間中獨(dú)立搜索其局部最優(yōu)解，速度代表向最優(yōu)解靠近的快慢，用位置代表移動(dòng)方向，通過(guò)記憶局部最優(yōu)并采取全局共享機(jī)制獲取全局最優(yōu)解，所有粒子根據(jù)其局部最優(yōu)和當(dāng)前全局最優(yōu)更新其位置和速度。PSO算法用于特征選擇問(wèn)題已有相關(guān)研究[26-29]，但是PSO因其采用的經(jīng)驗(yàn)學(xué)習(xí)機(jī)制，存儲(chǔ)的個(gè)體最優(yōu)極易使得算法陷入局部最優(yōu)解，且針對(duì)海量數(shù)據(jù)時(shí)會(huì)消耗大量的計(jì)算資源。

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

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

1 競(jìng)爭(zhēng)機(jī)制粒子優(yōu)化算法

1.1 競(jìng)爭(zhēng)機(jī)制粒子優(yōu)化算法描述

競(jìng)爭(zhēng)機(jī)制粒子群優(yōu)化算法框架見(jiàn)圖1，其中P(t)和P(t+1)分別代表第t和t+1代粒子群，每一代粒子群共有m個(gè)粒子，每個(gè)粒子位置和速度為n維，第i個(gè)粒子位置和速度分別表示為：

在每一次迭代過(guò)程中，粒子群P(t)被隨機(jī)分成種群大小為m/2的兩部分（若m為奇數(shù)，隨機(jī)劃分時(shí)競(jìng)爭(zhēng)優(yōu)勝者比失敗者多1個(gè)粒子，從優(yōu)勝者子群里隨機(jī)選取1個(gè)補(bǔ)充到失敗者子群），從兩個(gè)子群中分別選擇粒子成對(duì)競(jìng)爭(zhēng)，優(yōu)勝者直接進(jìn)入下一次迭代，失敗者通過(guò)學(xué)習(xí)機(jī)制向優(yōu)勝者學(xué)習(xí)更新，再進(jìn)入下一代，即每一次迭代每個(gè)粒子只參與1次競(jìng)爭(zhēng)，只有m/2的粒子通過(guò)學(xué)習(xí)機(jī)制更新?？梢?jiàn)，該算法計(jì)算消耗主要是在失敗粒子的更新上，計(jì)算復(fù)雜度為O(mn)。

圖1 競(jìng)爭(zhēng)機(jī)制粒子優(yōu)化算法框架

令Xl,k(t)和Vl,k(t)表示第t次迭代中第k輪競(jìng)爭(zhēng)中失敗粒子的位置和速度；Xw,k(t)和Vw,k(t)表示第t次迭代中第k輪競(jìng)爭(zhēng)中優(yōu)勝粒子的位置和速度；R1(k,t),R2(k,t),R3(k,t)∈[0,1]n表示第t次迭代中，第k輪競(jìng)爭(zhēng)中失敗者向優(yōu)勝者學(xué)習(xí)的隨機(jī)數(shù)向量，其中k=1,2,3,…,m/2。

1.2 算法穩(wěn)定性分析

根據(jù)式（3）和式（4），改寫(xiě)得到動(dòng)態(tài)方程形式：

改寫(xiě)成如式（6）所示的形式，成一對(duì)一對(duì)應(yīng)關(guān)系：

其中，A為狀態(tài)轉(zhuǎn)移矩陣，B為輸入矩陣。

根據(jù)勞斯穩(wěn)定性判據(jù)[31]，上述動(dòng)態(tài)方程穩(wěn)定的充分必要條件是：勞斯表中第1列各值為正，如果勞斯表第1列中出現(xiàn)小于零的數(shù)值，系統(tǒng)不穩(wěn)定，且第1列各系數(shù)符號(hào)的改變次數(shù)，代表特征方程（7）的正實(shí)部根的數(shù)目。

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

表1 特征方程勞斯表

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

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

1.3 二值化方法

競(jìng)爭(zhēng)機(jī)制粒子優(yōu)化算法每次迭代時(shí)更新粒子速度，對(duì)粒子速度利用S函數(shù)[32]進(jìn)行二值化處理，并根據(jù)規(guī)則對(duì)粒子位置進(jìn)行0、1的離散空間處理，其中1代表選擇該特征，0代表不選擇該特征。

3種S函數(shù)表達(dá)式、S函數(shù)圖形、粒子位置離散化公式詳見(jiàn)表2。

表2 S函數(shù)表達(dá)式及圖形

連續(xù)空間到離散空間的映射關(guān)系詳見(jiàn)圖2。

2 KDDCUP99數(shù)據(jù)集預(yù)處理

2.1 KDDCUP99數(shù)據(jù)集分析

從源IP地址到目標(biāo)IP地址，通過(guò)TCP或UDP協(xié)議建立連接，每個(gè)網(wǎng)絡(luò)連接分為正常或異常。異常類型共分為4大類共39種攻擊類型，其中22種攻擊類型在訓(xùn)練集中，另外17種攻擊類型在測(cè)試集中。4種異常類型分類如下。

圖2 連續(xù)空間到離散空間映射關(guān)系

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

（2）User to Root Attacks（U2R）：來(lái)自遠(yuǎn)程主機(jī)的未授權(quán)訪問(wèn)，有ipsweep、nmap、portsweep和satan共4種；

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

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

KDDCUP99每一條連接記錄由41個(gè)特征組成，分為4種類型（基本特征，內(nèi)容特征，內(nèi)容特征，流量特征），第42位是特征標(biāo)簽，特征數(shù)據(jù)結(jié)構(gòu)見(jiàn)圖3。KDDCUP99由約500萬(wàn)條記錄組成，同時(shí)還包括10%的訓(xùn)練子集和測(cè)試子集，樣本類別分布如圖3所示。部分特征屬于字符型，在數(shù)據(jù)預(yù)處理時(shí)需要轉(zhuǎn)換成數(shù)值型；部分連續(xù)性數(shù)據(jù)需進(jìn)行數(shù)據(jù)標(biāo)準(zhǔn)化處理，避免出現(xiàn)數(shù)據(jù)覆蓋現(xiàn)象。

圖3 特征數(shù)據(jù)結(jié)構(gòu)

2.2 字符型轉(zhuǎn)換成數(shù)值型

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

以上將KDDCUP99數(shù)據(jù)集中字符型轉(zhuǎn)換成了數(shù)值型，便于后續(xù)進(jìn)一步進(jìn)行數(shù)據(jù)處理。

2.3 數(shù)據(jù)標(biāo)準(zhǔn)化

KDDCUP99數(shù)據(jù)集中特征數(shù)據(jù)較為分散，特征數(shù)據(jù)的數(shù)值類型有連續(xù)型和離散型，連續(xù)型特征數(shù)據(jù)之間的數(shù)值差也較大。為了避免數(shù)值差異較大導(dǎo)致的數(shù)據(jù)覆蓋現(xiàn)象，提高模型訓(xùn)練速度，需對(duì)數(shù)據(jù)進(jìn)行標(biāo)準(zhǔn)化處理。本文采用極值法，即帶正向指標(biāo)的極差變換法。通過(guò)式（9）處理后，數(shù)據(jù)被標(biāo)準(zhǔn)化至[0，1]區(qū)間。

3 實(shí)驗(yàn)設(shè)計(jì)及驗(yàn)證

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

本文適應(yīng)度函數(shù)采用分類錯(cuò)誤率與特征數(shù)的線性組合，通過(guò)調(diào)整權(quán)重系數(shù)α的值分配分類錯(cuò)誤率和特征數(shù)影響比重：

ErrorRate代表分率錯(cuò)誤率，由python自帶KNN分類器計(jì)算；d代表第i個(gè)粒子所選取的特征數(shù)；D是每個(gè)粒子總的特征數(shù)，針對(duì)KDDCUP99數(shù)據(jù)集，D為41；α為權(quán)重值，用于調(diào)節(jié)錯(cuò)誤率和選擇特征數(shù)權(quán)重。

3.2 參數(shù)設(shè)置

經(jīng)過(guò)數(shù)據(jù)預(yù)處理的KDDCUP99數(shù)據(jù)集共有494 021條數(shù)據(jù)，利用train_test_split函數(shù)將該數(shù)據(jù)集隨機(jī)分成訓(xùn)練集和測(cè)試集。在進(jìn)行模型訓(xùn)練和預(yù)測(cè)中，為了便于快速計(jì)算，隨機(jī)從訓(xùn)練集和測(cè)試集中各選取1 000條數(shù)據(jù)，數(shù)據(jù)標(biāo)簽選取相對(duì)應(yīng)的標(biāo)簽。

用預(yù)測(cè)精度、最優(yōu)適應(yīng)度值、最差適應(yīng)度值、平均適應(yīng)度值以及選擇特征來(lái)評(píng)估模型預(yù)測(cè)結(jié)果。

參數(shù)設(shè)置如表4所示。

表4 參數(shù)設(shè)置

3.3 實(shí)驗(yàn)結(jié)果

3個(gè)S函數(shù)所對(duì)應(yīng)的預(yù)測(cè)精度、最優(yōu)適應(yīng)度值、最差適應(yīng)度值以及平均適應(yīng)度值如表5所示。

表5 預(yù)測(cè)精度及適應(yīng)度值

3個(gè)S函數(shù)所對(duì)應(yīng)的選擇特征數(shù)個(gè)數(shù)及位置如表6所示，在每條記錄41個(gè)特征中，0表示不選擇，1表示選擇。

表6 特征數(shù)個(gè)數(shù)及位置

適應(yīng)度值變化曲線詳見(jiàn)圖4?？梢钥闯觯跏蓟m應(yīng)度值在迭代之處能到達(dá)一個(gè)較為理想的水平，且SFunc1較另外兩個(gè)轉(zhuǎn)換函數(shù)較為平整，SFunc2和SFunc3均有較大突變，突變后趨于穩(wěn)定。可以看出，基于競(jìng)爭(zhēng)機(jī)制的二值化粒子優(yōu)化算法具有在短時(shí)間內(nèi)可以到達(dá)較為穩(wěn)定的狀況。

以SFunc1為例，設(shè)置K值范圍為1～20，采用sklearn的cross_val_score進(jìn)行交叉驗(yàn)證，求取準(zhǔn)確度的平均值。通過(guò)比較準(zhǔn)確度值，選取最合適的K值，實(shí)現(xiàn)參數(shù)調(diào)優(yōu)。通過(guò)仿真計(jì)算，準(zhǔn)確度隨K值變化曲線詳見(jiàn)圖5，其中K=4時(shí)準(zhǔn)確度為0.994 5，此時(shí)為模型參數(shù)最優(yōu)。

圖4 適應(yīng)度值變化曲線

圖5 精確度隨K（實(shí)例個(gè)數(shù)）值變化曲線

4 結(jié)語(yǔ)

本文采用二值化競(jìng)爭(zhēng)機(jī)制粒子優(yōu)化算法優(yōu)化選擇KDDCUP99數(shù)據(jù)集的特征子集，實(shí)現(xiàn)數(shù)據(jù)的降維處理，創(chuàng)新性地采用穩(wěn)定性理論分析算法模型，選取調(diào)控參數(shù)取值范圍，分析了KDDCUP99數(shù)據(jù)集的預(yù)處理思路、方法和流程，并采用sklearn的KNN算法搭建訓(xùn)練模型，利用選擇的特征子集進(jìn)行模型訓(xùn)練，利用交叉驗(yàn)證機(jī)制對(duì)模型進(jìn)行精確度校驗(yàn)。實(shí)驗(yàn)結(jié)果表明，通過(guò)優(yōu)化算法選取的特征子集搭建的訓(xùn)練模型具有較高的精確度，且在處理大數(shù)據(jù)時(shí)具有較大優(yōu)勢(shì)。

本文以KDDCUP99數(shù)據(jù)集進(jìn)行驗(yàn)證。KDDCUP99數(shù)據(jù)集主要是網(wǎng)絡(luò)流量數(shù)據(jù)，在入侵檢測(cè)領(lǐng)域具有較高的代表性。后續(xù)將以實(shí)際入侵檢測(cè)模型搭建需求為牽引，將本文研究的優(yōu)化算法結(jié)合實(shí)際需求搭建合適的入侵檢測(cè)模型，對(duì)實(shí)際的入侵檢測(cè)行為進(jìn)行實(shí)時(shí)的分析感知。