一種基于鴿群優(yōu)化算法的入侵檢測技術(shù)

王 康，霍朝賓，李青旭

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

0 引言

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

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

1 理論基礎(chǔ)

1.1 特征選擇

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

適應(yīng)度函數(shù)是用來評價優(yōu)化問題中求解過程的適應(yīng)性。 在本文所闡述的問題中，適應(yīng)度函數(shù)是根據(jù)真陽性率(TPR)、假陽性率(FPR)和特征數(shù)對所選特征子集的解進行評估的。特征的數(shù)量是參與適應(yīng)度函數(shù)的計算過程的，因此如果在特征子集中加入了某個特征但不影響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 用于特性選擇

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

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

2.3 Cosine_PIO 特征選擇算法

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

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

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

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

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

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

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

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

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

地標(biāo)算子的第二部分中，鴿子更新它們達到期望目標(biāo)位置的過程是不同的，因為期望目標(biāo)位置是一個二元向量。 因此，所有的鴿子都會先通過式(9)計算它們的速度，然后根據(jù)式(10)更新它們的位置。

2.6 加入新鴿子

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

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

2.7 評價指標(biāo)

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

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

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

其中，precision 和recall 是另外兩個度量，其計算公式如下：

3 仿真實驗

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

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

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

圖4 SPIO 和CPIO 的收斂曲線

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

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

F1 值比其他度量具有更好的總結(jié)和指示作用，因為它是綜合了精確率和召回率的度量。圖6 顯示了所有檢測算法的F1 值結(jié)果。 由圖可見，CPIO 的F1 值最高。

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

圖6 KDDCUP99 上集中算法的F1 值

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

4 結(jié)論

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

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