一種改進遺傳算法優化SVM的入侵檢測方法

侯春雨，王戈文，王崇峻

(1.廣州民航職業技術學院航空港管理學院， 廣州 510403; 2.長沙市化工研究所， 長沙 410007; 3.航天工程大學， 北京 101400)

隨著信息技術發展和普及，網絡信息安全變得日益重要。相比傳統網絡防御技術，網絡入侵檢測系統(NIDS)可主動攔截警報數據[1]，實用價值凸顯。因此，如何提高入侵檢測系統效率成為當前網絡安全領域研究熱點。現有NIDS受到未知攻擊時檢測率較低，且在處理警報數據時開銷較大，因此相關研究人員將機器學習如支持向量機(SVM)、模糊邏輯、人工神經網絡、人工免疫系統(AIM)等方法應用于NIDS中。SVM是一種基于統計學習的機器學習算法，在解決模式識別和語音識別等問題時性能較為優越[2]，相比其他機器學習算法，它能夠較好地解決小樣本、非線性和高維問題，因此常用于識別網絡中惡意流量。

大數據環境下SVM處理入侵檢測數據時碰到了新問題，隨著網絡數據特征維度增加，NIDS訓練時間增加，分類準確率隨之下降，限制了SVM在NIDS中的應用。因此，特征選擇、特征權重及SVM參數的合理設置對提高入侵檢測效率至關重要。遺傳算法利用染色體間信息交換和種群搜索策略展現的較佳全局優化能力來避免局部最優解。為了解決上述問題，本文采用遺傳算子優化支持向量機方法尋優特征子集，并同時優化SVM參數和特征權重，將其用于提高NIDS分類性能。

文獻[3]通過遺傳算法優化SVM的核參數γ，利用啟發式方法動態調整遺傳算子，將分類準確率作為適應度函數，完成基于高斯核函數的SVM參數優化，但卻未考慮特征權值對SVM分類準確率的影響。文獻[4]提出了一種基于主成分分析(PCA)與粒子群優化SVM的入侵檢測方法(PCA-SVM)，利用PCA對網絡入侵數據進行數據降維和特征提取，但是PCA可能會得到對分類無作用的特征，且可能丟失一些有用的數據或特征。文獻[5]提出了一種基于融合FAST與自適應二進制量子引力搜索優化SVM(ABQGSA-SVM)的入侵檢測方法，利用FAST算法過濾掉冗余數據特征以生成特征子集，基于組合優化的量子引力搜索算法對SVM參數和特征子集進行尋優，但該方法收斂速度較慢，不能快速高效找到優化特征子集和SVM參數。近些年，基于SVM的網絡入侵檢測方法存在眾多問題：傳統特征選擇方法容易忽略許多重要特征，選出的特征子集得到的分類準確率會隨之降低；傳統遺傳方法優化SVM用于NIDS中，無法充分搜索特征子集空間，搜到的特征子集具備較高錯誤率，選出的最優特征子集各項特征重要程度未充分體現，無法找到SVM模型最優參數。

根據上述問題，本文提出了一種改進的遺傳算法優化SVM的入侵檢測方法。首先，對遺傳算子的交叉和變異過程進行優化，有利于提高群落早期演化速度，然后，在尋優特征子集階段，提出一種基于數據維度、分類準確率和誤報率優化配置的適應度函數，最后，同時優化SVM的特征權值及相關參數，以增強SVM的分類性能。

1 遺傳算法和梯度下降法

遺傳算法是一種通過模擬自然進化過程搜索優化解的方法，主要包括3個部分：選擇操作、交叉操作和變異操作[6]。其中，選擇操作主要是選取較優的母代染色體進行交叉操作和變異操作，以增加群落的多樣性并避免群落陷入局部最優解[7]，常見的選擇法方法有輪盤賭選擇、精英選擇和錦標賽選擇。當前遺傳算子中種群演化期間的交叉概率和變異概率都是常數，會影響群落后期演化的收斂性，致使SVM訓練時間增加。為了使染色體在群落演化過程中加速搜索，促使遺傳算法盡快找到優化解，本文根據群落演化的不同階段確定交叉概率和變異概率，并引入梯度下降方法增加算法的搜索方式，從而加速找到全局優化解。

1.1 交叉操作

圖1 遺傳算法中交叉操作

根據群落的特性，剛開始群落種類更加隨機和多樣，到了后期群落逐漸收斂，群落相似度增加，故交叉操作在前期作用大于后期作用。所以隨著迭代次數增加，每次迭代的交叉操作染色體個數和交叉概率應該隨之減少，這樣有利于減少計算成本。每次迭代進行交叉操作染色體的個數Pi如式(1)，交叉概率更新如式(2)：

(1)

其中，swsize表示所有染色體個數，it表示迭代次數，maxit表示最大迭代次數。

(2)

其中，prmax是最大交叉概率，prmin是最小交叉概率。

1.2 變異操作

群落中母代染色體某部分基因發生改變，即變異操作，如圖2所示。種群演化初期，主要通過交叉操作尋找優化解，設置較低變異概率有利于降低計算成本；種群演化后期，執行交叉操作的染色體數減少，提高變異概率有利于增加群落多樣性，提高尋找到最優解的概率，因此本文變異概率公式如式(3)。染色體中第d維基因的選擇概率如式(4)。

(3)

(4)

其中，gbestd表示全局最優染色體第d維基因，θ表示選擇閾值。生成范圍在[0,1]的隨機數r，若r>CProbabilityd，執行相應的變異操作，如式(5)，否則將新染色體第d維基因childd賦值為gbestd。

(5)

其中，若gbestd的值小于或等于選擇閾值θ，則將childd的值映射到[θ,1]范圍的實數，否則將childd的值映射到(0,θ]范圍的實數，有利于改變特征的選擇屬性。

圖2 遺傳算法中變異操作

1.3 梯度下降法

梯度下降算法是目前較為流行的優化算法，收斂速度較快，經常與各種算法聯合使用。梯度下降法分為批量梯度下降法、隨機梯度下降法、小批量梯度下降法，其關鍵思想是某質點沿適應度函數梯度下降盡快滑落到函數極值點，主要包含兩個內容：搜索方向，如式(6)計算出最優搜索方向[8]；搜索步長，如式(7)計算搜索步長。

gtm=負梯度=

(6)

(7)

其中，sec代表梯度下降法最多探索次數。基于梯度下降法有利于增加遺傳算法群落多樣性，其算法如下：

算法:本文梯度下降算法輸入:設置誤差ε>0,迭代次數變量m,最多探索次數sec;輸出:全局優化解gbest;Step1:如式(6)計算最優搜索方向,判斷搜索是否滿足迭代次數m≤sec或gtmmaxxi≤ε,若是則跳到Step2,否則跳到Step3;Step2:如式(7)計算最優步長,并如式(8)更新群落全局最優值,并跳到Step1;gbestm+1=gbestm+λmgtm(8)Step3:輸出全局優化解gbest。

2 改進的遺傳算法優化支持向量機的入侵檢測方法

本文將改進的遺傳算法優化SVM用于NIDS中，需要解決兩個主要問題：如何對特征的重要程度進行排序；如何選擇最優SVM內核參數。這兩個問題必須同時解決，因為權重特征會影響SVM的內核參數，反之亦然。本文提出改進的遺傳算法優化SVM體系結構如圖3所示，主要分為3部分：特征選擇、入侵檢測和停止準則，目的是尋找最優特征子集，優化SVM參數和各項特征權重。

圖3 改進的遺傳算法優化SVM體系結構

1) 特征選擇[9]：將KDD CUP99作為初始數據集，利用基于改進遺傳算法的特征選擇算法尋找候選特征子集。其中，特征子集包括特征的權重W1～Wn(特征W=0表示未選特征)以及SVM參數C和γ，如圖4所示。

圖4 特征子集結構

2) 基于SVM的入侵檢測[10]：在初始數據集中，將特征子集中的特征權重對應相乘每條數據的特征值得到入侵檢測輸入數據，并將特征子集中SVM參數C和γ用于構建SVM模型，經過入侵檢測識別后，求解出相應適應度值。其中，各項特征權重是通過隨機方式生成的范圍[0,1]的實數。

3) 停止準則：將適應度值最大的特征子集作為最優特征子集，并利用最優特征子集得到特征權重和SVM參數。

本文中改進的遺傳算法優化SVM具體算法如下：

算法:改進遺傳算法優化SVM在入侵檢測中應用算法輸入:KDD CUP99 樣本訓練集和測試集,隨機初始化的母本群體swarm,群落最優gbest,SVM參數C和γ,交叉概率pcrprobability,變異概率pmuprobability,最大迭代次數maxit,其中,swarm包含10對母本染色體,每條染色體包含一組入侵檢測中特征權重和支持向量機參數C和γ的編碼,染色體中每個基因取值均在實數范圍[0,1]中。輸出:最優特征子集,各項特征權重,SVM參數C和γ;Step1:求解swarm的適應度fswarm,初始化gbest為swarm中最優適應度染色體,并求其適應度fgbest;Step2:判斷是否滿足最大迭代次數maxit或最大適應度值,滿足則跳到Step7,否則跳Step3;Step3:評估每條染色體適應度值,并如式(2)、(3)更新交叉概率pcrprobability、變異概率pmuprobability;Step4:根據3.1節對群體進行交叉操作,更新群體最優值gbest及其適應度;Step5:根據3.2節對群體進行變異操作,更新群體最優值gbest及其適應度;Step6:若全局最優值gbest連續3次迭代不發生變化,根據3.2節梯度下降法產生新染色體,然后跳到Step2;Step7:將全局優化染色體gbest當作最優特征子集,并得到相關權重和參數。

算法中適應度函數是本文算法的一個基本組成部分，用來評估染色體的優劣程度，本文適應度函數設計如式(9)：

(9)

其中，Acc表示分類準確率；fsn表示特征子集的特征維數；Afs表示總特征數量；far表示誤報率；(1-a-b)表示準確率的權重參數，其權重應該大于其他權重；a表示特征維數占總維數比例的權重參數，其權重應該僅次于準確率的權重；b表示誤報率的權重參數。

3 NIDS實驗結果與分析

3.1 實驗環境與數據集

本文實驗環境基于Windows 8系統，Matlab2014b軟件。改進的遺傳算法優化SVM方法參數設置如表1所示。實驗樣本數據集取自KDD CUP 99 數據集[11]，如表2所示，實驗樣本數據集的41維特征[12]如表3所示。

表1 改進遺傳算法優化SVM方法參數設置

表2 KDD CUP 99樣本數據集組成

表3 KDD CUP 99連接記錄41維特征

3.2 實驗結果與分析

本文實驗數據集主要是檢測樣本數據集和特征選擇數據集。檢測樣本數據集組成如表2所示。為了縮短尋優特征子集的時間，從表2的DOS、Probe、R2L和U2R數據集中分別隨機抽取50%、80%、100%和100%的數據作為各自特征選擇數據集，并將上述特征選擇數據集合并作為ALL的特征選擇數據集。

特征選擇前需要預處理檢測樣本數據集和特征選擇數據集，預處理主要分為字符特征數值化和數據歸一化過程。本文從適應度、特征維數、分類準確率及檢測時間四個方面，對比了PCA-SVM[4]和ABQGSA-SVM[5]方法，得到相關實驗結果如圖5，表4～表6。

圖5 3種特征選擇算法得到的適應度對比

從圖5可知，通過比較3種特征選擇算法得到的適應度曲線可以發現：本文算法收斂速度快于其他算法，且本文算法在第17次迭代時適應度趨于穩定，CSVAC和ABQGSA-SVM在第23次迭代時適應度才穩定，說明本文算法穩定后得到的適應度高于其他特征選擇算法。因此，本文算法尋優到的SVM模型優于其他算法。

在特征選擇數據集上比較3種特征算法得到特征子集的特征選擇維數，如表4。其中，特征維數序號和表3相對應。

表4 3種算法得到的特征維數

從表4可知：通過比較3種算法得到平均特征選擇維數發現：本文方法比其他算法少至少20%的特征，3種方法得到的平均特征選擇維數從少到多排序為本文算法、ABQGSA-SVM、CSVAC。

在表2樣本數據集上比較所有特征情況下和上述3種特征選擇算法后得到最優特征子集的分類準確率和檢測時間，得到實驗結果如表5和表6。

表5 3種算法得到的分類準確率

從表5可以得到，通過比較3種算法得到最優特征子集的平均分類準確率發現：本文方法比其他方法提高了至少2%的分類準確率；比所有特征情況提高了約0.5%的分類準確率。

表6 3種算法得到的檢測時間

從表6可以得到，通過比較3種算法得到最優特征子集的檢測時間發現：本文方法比其他方法縮短了至少10%的檢測時間；比所有特征情況縮短了約20%的檢測時間。

綜上所述，本文算法尋優到的特征子集所構建入侵檢測模型相比ABQGSA-SVM和CSVAC算法，有效降低了入侵檢測中惡意流量的特征維度，提高了入侵檢測的分類準確率，縮短了檢測時間，因此本文算法所構建的入侵檢測模型具備更優的性能。

4 結論

針對入侵檢測中高維特征問題，本文提出了一種改進遺傳算法優化SVM方法。首先，利用梯度下降算法對遺傳算法進行改進，并設計了自適應變化的交叉和變異概率；設計了基于分類準確率、數據特征維度和誤報率優化配置的適應度函數；輸出網絡流量特征權重、支持向量機核參數γ和懲罰因子C。由于遺傳算法的初始值對后期尋優效果有較大影響，下一步將研究如何產生合適的遺傳算法初始值，尋找到更優的特征子集，提高SVM的分類性能。