王 康，霍朝賓，李青旭

(華北計(jì)算機(jī)系統(tǒng)工程研究所，北京100083)

0 引言

隨著互聯(lián)網(wǎng)使用規(guī)模的不斷擴(kuò)大，網(wǎng)絡(luò)上傳輸?shù)闹匾畔⒁苍谥饾u增加， 但也暴露出很多的安全性問(wèn)題。入侵檢測(cè)系統(tǒng)作為網(wǎng)絡(luò)空間安全的核心組件，直接影響了網(wǎng)絡(luò)的安全性。入侵檢測(cè)的主要功能是識(shí)別網(wǎng)絡(luò)中可能包含攻擊的非正常行為。根據(jù)入侵檢測(cè)功能的執(zhí)行位置，可分為基于網(wǎng)絡(luò)的入侵檢測(cè)和基于主機(jī)的入侵檢測(cè)。

本文將介紹一種鴿群優(yōu)化算法應(yīng)用于入侵檢測(cè)系統(tǒng)。 通過(guò)提出的算法對(duì)公開(kāi)數(shù)據(jù)集進(jìn)行特征選擇，然后用決策樹(shù)對(duì)選擇的特征進(jìn)行建模分析。特征選擇后的數(shù)據(jù)集維度顯著降低，不但加快和簡(jiǎn)化了模型的建立，還提高了模型的泛化性。 在此基礎(chǔ)上，對(duì)算法進(jìn)行了一定程度改進(jìn)，使其更適合于離散空間的特征選擇。

1 理論基礎(chǔ)

1.1 特征選擇

特征選擇是按照某種規(guī)則在原特征中選擇對(duì)分類更加有益的特征子集而刪除對(duì)建模無(wú)用或者有害的特征，從而簡(jiǎn)化模型以算提高算法性能。

由于特征選擇是一個(gè)機(jī)器學(xué)習(xí)的概念，它主要是通過(guò)各種算法來(lái)實(shí)現(xiàn)的，因此經(jīng)常使用統(tǒng)計(jì)分析、支持向量機(jī)、神經(jīng)網(wǎng)絡(luò)和數(shù)據(jù)挖掘等方法完成特征選擇[1]。 此外，特征選擇假設(shè)了一種檢測(cè)機(jī)制，可以將其分為3 類：隨機(jī)選擇、遞增選擇和遞減選擇。 選擇機(jī)制用于確定和選擇數(shù)據(jù)集中的相關(guān)特征。 值得注意的是，特征選擇可以通過(guò)多種技術(shù)實(shí)現(xiàn)，包括智能模式、群體智能、人工神經(jīng)網(wǎng)絡(luò)、確定性算法、模糊和粗糙集[2]。

1.2 鴿群優(yōu)化算法

鴿群優(yōu)化(Pigeon Inspired Optimation，PIO)算法是一種仿生群體智能算法[3]。 群體智能用于解決非確定性多項(xiàng)式(NP)問(wèn)題或搜索空間過(guò)大的問(wèn)題。 它模仿一些生物群體社會(huì)機(jī)制，試圖用數(shù)學(xué)模型模擬一個(gè)群體的自然行為，以提高求解問(wèn)題的質(zhì)量[4]。

鴿群優(yōu)化算法通過(guò)兩個(gè)算子運(yùn)行：地圖和指南針?biāo)阕优c地標(biāo)算子。

式中，R 是地圖和指南針?biāo)阕拥囊驍?shù)，rand 是從[0，1]之間的均勻分布中隨機(jī)取的，Xg為當(dāng)前鴿群的全局最優(yōu)解，Xi(t)、Vi(t)分別表示在t 的迭代輪次中鴿子i 的位置和速度。

圖1 所示為地圖和指南針?biāo)阕邮疽鈭D，飛行中的鴿子會(huì)根據(jù)最佳鴿子的位置調(diào)整自己的飛行方向。 式(1)中的第一個(gè)部分表示鴿子的當(dāng)前方向，第二部分表示鴿子跟隨最佳鴿子(當(dāng)前最優(yōu)解)的過(guò)程。

圖1 地圖和指南針?biāo)阕邮疽鈭D

在地標(biāo)算子中，所有的鴿子會(huì)根據(jù)它們的適應(yīng)度排序。 排序前一半的鴿子將根據(jù)式(3)來(lái)計(jì)算中心鴿的位置，這個(gè)位置被當(dāng)作地標(biāo)，其余一半的鴿子將根據(jù)這個(gè)地標(biāo)來(lái)更新自己的位置，如式(4)所示。

式中，Xc是中心鴿(地標(biāo))的位置，Xi是所有鴿子的當(dāng)前位置，F(xiàn)itness 是適應(yīng)度函數(shù)，Np(t) 是代表鴿子的數(shù)量。

圖2 是地標(biāo)算子的示意圖，在算法模擬的過(guò)程中，認(rèn)為低適應(yīng)度的鴿子對(duì)地標(biāo)是不熟悉的，它們必須跟隨高適應(yīng)度的鴿子。 圖2 中的黑鴿子表示地標(biāo)的位置，圈內(nèi)的鴿子數(shù)量是根據(jù)式(5)計(jì)算的鴿子數(shù)的一半。

圖2 地標(biāo)算子示意圖

2 基于鴿群優(yōu)化算法的特征選擇

鴿群優(yōu)化（PIO）算法在解決無(wú)人機(jī)路徑規(guī)劃、無(wú)人機(jī)自主編隊(duì)[5]、自動(dòng)著陸系統(tǒng)[6]、PID 設(shè)計(jì)控制器[7]等諸多優(yōu)化問(wèn)題中得以實(shí)踐。本文采用了一種基于鴿群優(yōu)化的特征選擇算法應(yīng)用于入侵檢測(cè)系統(tǒng)。 在本節(jié)中，提出了PIO 的兩個(gè)版本。 第一個(gè)版本的算法使用Sigmoid 函數(shù)離散化鴿子向量，而第二個(gè)版本是使用離散的鴿子向量基于余弦相似度重新定義鴿子的速度。雖然兩個(gè)版本都使用了相同的適應(yīng)度函數(shù)，但是每個(gè)版本的算法其求解方式又不盡相同。

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

適應(yīng)度函數(shù)是用來(lái)評(píng)價(jià)優(yōu)化問(wèn)題中求解過(guò)程的適應(yīng)性。 在本文所闡述的問(wèn)題中，適應(yīng)度函數(shù)是根據(jù)真陽(yáng)性率(TPR)、假陽(yáng)性率(FPR)和特征數(shù)對(duì)所選特征子集的解進(jìn)行評(píng)估的。特征的數(shù)量是參與適應(yīng)度函數(shù)的計(jì)算過(guò)程的，因此如果在特征子集中加入了某個(gè)特征但不影響TPR 或FPR，則傾向于消除它。式（6）給出了本文使用的適應(yīng)度函數(shù)：

式中，SF 為所選特性的數(shù)量，NF 為所有特征的數(shù)量，w1+w2+w3=1。 由 于TPR 和FPR 同 等 重 要[8]，因 此 權(quán) 重 值設(shè)置如下：w1= 0.1，w2=w3=0.45。

2.2 Sigmoid_PIO 用于特性選擇

在第一個(gè)PIO 特征選擇的方法中，首先將速度和位置向量每一維的值被初始化為[0，1]區(qū)間的隨機(jī)數(shù)。 通過(guò)式(1)計(jì)算每只鴿子的速度，然后用式(7)中的Sigmoid函數(shù)[9]轉(zhuǎn)化速度向量。 如式(8)所示，為了二元化鴿子的位置向量，根據(jù)Sigmoid 函數(shù)的值和一個(gè)隨機(jī)數(shù)r 來(lái)更新鴿子的位置。

式中，Vi(t)為迭代t 中的鴿子速度，r 為均勻隨機(jī)數(shù)。

2.3 Cosine_PIO 特征選擇算法

第二種PIO 方法的提出是為了克服第一種方法的局限性而設(shè)計(jì)的。 Cosine_PIO 使用余弦相似度來(lái)計(jì)算鴿子的速度。 Cosine_PIO 與Sigmoid_PIO 有3 個(gè)不同點(diǎn)：解向量(鴿子)的表示；更新位置和速度的方式；允許新的鴿子加入鴿群以增加算法達(dá)到全局最優(yōu)解的機(jī)會(huì)。

Cosine_PIO 中的解是一個(gè)長(zhǎng)度為輸入數(shù) (特征數(shù))的向量，向量的值由0 或者1 隨機(jī)初始化。 0 表示當(dāng)前向量(鴿子)中沒(méi)有對(duì)應(yīng)的特征，1 表示當(dāng)前向量中存在對(duì)應(yīng)的特征。 圖3 顯示了一個(gè)為KDDCUP99[10]數(shù)據(jù)集隨機(jī)生成的解決方案的示例。

圖3 KDDCUP99 數(shù)據(jù)集上特征選擇示意

2.4 修改地圖和指南針?biāo)阕?/h3>

如前所述，PIO 的基本工作原理是用最優(yōu)鴿子的位置減去當(dāng)前鴿子的位置Xi，如式(1)所示。 但是當(dāng)鴿子向量為離散值時(shí)，不能將離散的0、1 向量作為常規(guī)向量減法來(lái)減，因此本文用新的方式來(lái)模擬PIO 在連續(xù)問(wèn)題中的減法過(guò)程來(lái)更新鴿子的速度向量。 式(9)給出了鴿子速度的計(jì)算，這里每只鴿子的速度取決于它們和最優(yōu)鴿子的相似度程度。 根據(jù)式(9)求出鴿子的速度值Vp，根據(jù)式(10)來(lái)更新鴿子的位置。

其中，r 是均勻隨機(jī)數(shù)。

根據(jù)式(10)，如果當(dāng)前鴿子不是全局解的近鄰，則其有更高的概率向全局最優(yōu)解更新其位置。

2.5 修改的地標(biāo)算子

Cosine_PIO 的地標(biāo)算子第一部分與基本PIO 基本算法相同。 先根據(jù)適應(yīng)度對(duì)鴿群排序，然后計(jì)算中心鴿子(地標(biāo))的位置。

地標(biāo)算子的第二部分中，鴿子更新它們達(dá)到期望目標(biāo)位置的過(guò)程是不同的，因?yàn)槠谕繕?biāo)位置是一個(gè)二元向量。 因此，所有的鴿子都會(huì)先通過(guò)式(9)計(jì)算它們的速度，然后根據(jù)式(10)更新它們的位置。

2.6 加入新鴿子

二元鴿群優(yōu)化算法中的另一個(gè)變化就是以一定的可能加入新鴿子，這個(gè)想法的來(lái)源是在二元鴿群優(yōu)化算法執(zhí)行的過(guò)程中有很高的可能存在重復(fù)的解。鴿子的加入過(guò)程只能在地圖和指南針?biāo)阕又型瓿?。如果存在重?fù)解，則有一半的概率直接丟棄重復(fù)解，以一般的概率隨機(jī)改變重復(fù)解的0.2 來(lái)加入鴿群。 這將有助于更大范圍的探索解空間。

二元的解向量限制了鴿群優(yōu)化的有效性，但是本文通過(guò)余弦相似度解決了向量速度的問(wèn)題，通過(guò)加入適應(yīng)度解決了鴿群中心位置難以計(jì)算的問(wèn)題，使得鴿群優(yōu)化算法在二元化的特征選擇問(wèn)題中表現(xiàn)出優(yōu)異的效果。

2.7 評(píng)價(jià)指標(biāo)

本文用到的評(píng)價(jià)指標(biāo)有檢測(cè)精度(Accuracy)、檢測(cè)率(True Positive Rate)、F1 值。 以上評(píng)價(jià)指標(biāo)都是基于混淆矩陣中4 個(gè)度量來(lái)計(jì)算的。 混淆矩陣中，TP 表示實(shí)際為正預(yù)測(cè)為正的樣本，TN 表示實(shí)際為負(fù)預(yù)測(cè)為負(fù)的樣本，F(xiàn)N 表示實(shí)際為正預(yù)測(cè)為負(fù)的樣本，F(xiàn)P 表示實(shí)際為負(fù)預(yù)測(cè)為負(fù)的樣本。 Accuracy 表示正確分類的樣本數(shù)占所有樣本數(shù)的百分比，常用于表征算法檢測(cè)能力的指標(biāo)。 檢測(cè)精度定義如下。

檢測(cè)率(True Positive Rate，TPR)是指被檢測(cè)出的正樣本占全部正樣本的比例，檢測(cè)率越高表明算法檢測(cè)性能越好。 檢測(cè)率定義如下：

F1 值指標(biāo)綜合了Precision 與Recall 的結(jié)果。F1 值的取值范圍為0～1，1 代表模型的輸出最好，0 代表模型的輸出結(jié)果最差，其定義如下：

其中，precision 和recall 是另外兩個(gè)度量，其計(jì)算公式如下：

3 仿真實(shí)驗(yàn)

本節(jié)將介紹PIO 特征選擇算法評(píng)估KDDCUP99 數(shù)據(jù)集。 該算法與目前常用的一些特征選擇算法(如遺傳算法、粒子群算法、蝙蝠算法等)進(jìn)行了比較。 所有的特征選擇算法都使用Python 中scikit-learn 庫(kù)中的決策樹(shù)分類器進(jìn)行建模與評(píng)估。

所有被檢測(cè)的算法都進(jìn)行了TPR、FPR、F1 值和準(zhǔn)確率的評(píng)估。表1 給出的是一系列其他算法所選擇的特征。 使用決策樹(shù)對(duì)每個(gè)用于特征選擇的算法進(jìn)行評(píng)估，只使用指定的特征對(duì)模型進(jìn)行訓(xùn)練，然后使用測(cè)試集對(duì)模型進(jìn)行評(píng)估。所有的模型都使用相同的方法在相同的數(shù)據(jù)集上進(jìn)行訓(xùn)練，以確保比較的公平性。的收斂速度慢于CPIO；在第60 次迭代時(shí)，解的質(zhì)量停止 提 高。 從 圖 中 結(jié) 果 來(lái) 看，CPIO 比SPIO 更 有 效。 余 弦 相似度法用于PIO 的離散化，比傳統(tǒng)方法收斂速度快得多。CPIO 所采用的新鴿群優(yōu)化算法有助于算法不斷增強(qiáng)解的穩(wěn)定性，并很容易地跳過(guò)算法的局部最優(yōu)解。

表1 KDDCUP99 特征選擇的結(jié)果

圖4 SPIO 和CPIO 的收斂曲線

圖5 展示了在KDDCUP99 上測(cè)試的7 種算法的TPR結(jié)果和準(zhǔn)確性。 每個(gè)柱表示相應(yīng)測(cè)試算法30 次運(yùn)行的評(píng)分結(jié)果均值。從圖中可以看出，所提出的CPIO 算法相對(duì)于其他所有經(jīng)過(guò)檢驗(yàn)的算法具有最高的精度。結(jié)果表明，在相同的迭代次數(shù)下，CPIO 在TPR 和精度方面都優(yōu)于SPIO。 使用Cuttlefifish 算法訓(xùn)練的模型在準(zhǔn)確性方面的結(jié)果最差。從圖5 可以看出，TPR 高、準(zhǔn)確率低的算法在適應(yīng)度函數(shù)中沒(méi)有考慮誤報(bào)率。

圖5 幾種算法的TPR 和準(zhǔn)確率

F1 值比其他度量具有更好的總結(jié)和指示作用，因?yàn)樗蔷C合了精確率和召回率的度量。圖6 顯示了所有檢測(cè)算法的F1 值結(jié)果。 由圖可見(jiàn)，CPIO 的F1 值最高。

影響特征選擇算法質(zhì)量的另一個(gè)度量方法是選擇特征的數(shù)量。 特征的數(shù)量影響模型的構(gòu)建和測(cè)試時(shí)間。圖7 展示了3 種情況下的構(gòu)建和測(cè)試時(shí)間：使用數(shù)據(jù)集中的所有特征(41 個(gè)特征)、使用SPIO 選擇的10 個(gè)特征、使用CPIO 選擇的7 個(gè)特征。結(jié)果表明，特征的數(shù)量影響了模型構(gòu)建和測(cè)試所需的時(shí)間。

圖6 KDDCUP99 上集中算法的F1 值

圖7 KDDCUP99 訓(xùn)練和測(cè)試的時(shí)間

4 結(jié)論

本文提出了一種基于鴿子優(yōu)化算法的入侵檢測(cè)系統(tǒng)特征選擇算法。 提出的PIO 特征選擇旨在減少構(gòu)建健壯的IDS 所需的特征數(shù)量，同時(shí)保持較高的檢測(cè)率、準(zhǔn)確性和較低的誤報(bào)。 提出的PIO 特征選擇算法將KDDCUPP99、特征數(shù)量分別從41 個(gè)減少到7 個(gè)。 該方法保持了較高的TPR 和精度，大大減少了建模所需的時(shí)間。

特征選擇是一個(gè)離散優(yōu)化問(wèn)題。 對(duì)于連續(xù)的群體智能優(yōu)化算法，必須采用離散化處理算法來(lái)解決這樣的問(wèn)題。 提出了一種基于余弦相似度的連續(xù)算法離散化方法，并與傳統(tǒng)離散化方法進(jìn)行了比較。 在相同迭代次數(shù)下，該離散化方法比傳統(tǒng)方法收斂速度快。