基于改進蟻群求解特征子集的入侵檢測方法

2021-07-16 08:03:06梁本來

計算機應用與軟件 2021年7期

梁本來朱磊

1(中山職業技術學院信息工程學院廣東中山 528404) 2(西安理工大學計算機科學與工程學院陜西西安 710048)

0 引言

網絡流量的激增，對入侵檢測系統(Intrusion Detection System，IDS)的性能提出了更高的要求[1]，為解決這一問題，機器學習在IDS的應用研究是當今的一個趨勢[2]。網絡流量包含大量的特征信息，其中包含與檢測目標關聯度較低的特征，以及與其他特征相關性較高的特征，這兩類特征可以統稱為冗余特征[3]。冗余特征過多，會導致IDS檢測算法的時空復雜度增加，降低IDS的檢測性能。因此，在原始的特征點中篩選出最優特征子集，保留數據中貢獻度較大的特征，去掉一些冗余特征甚至噪聲特征[4]，以提高IDS分類器性能，是當今IDS領域的一個研究熱點和難點[5]。

隨機搜索算法及啟發搜索算法是目前選擇網絡特征子集的兩大方法，其中隨機搜索算法采用窮舉法，策略簡單，但計算機量大，對于海量數據的處理效率過低，難以滿足IDS的實時性要求[6]。啟發式搜索速度快，目前的研究文獻主要集中在蟻群算法(Ant Colony Optimization，ACO)、粒子群算法(Particle Swarm Optimization，PSO)等生物智能算法。Mehdi等[7]提出了利用ACO求解特征子集的方法，較為完整地介紹了ACO在特征向量圖中搜索特征子集的過程。但該方法并未對ACO進行改進，容易陷入局部最優且不穩定。王峰[8]提供了改進傳統ACO的思路，引入同數量級參數優化轉移概率，設置優先級優化信息素揮發系數。但該文獻對網絡流量特征分析較少，沒有描述特征拓撲的構建過程，對螞蟻的起始位置和搜索過程介紹較為籠統，實驗數據樣本的構造也較為簡單。肖國榮[9]提出一種改進ACO和支持向量機(SVM)網絡入侵檢測方法ACO-SVM，采用動態隨機抽取的方法來確定目標個體引導螞蟻進行全局搜索，優化SVM模型參數。但該算法重在SVM分類器參數的確定，并未求解網絡特征子集。朱麗[10]提出了一種基于蟻群分類規則挖掘算法的網絡入侵檢測方法(ADM-ACCRMA)，用改進ACO挖掘網絡攻擊的分類規則，再對網絡流量進行分類規則的檢測，提供了一個較好的IDS檢測思路。但該文獻對于網絡流量的分類較為籠統，實驗較為理想化，實際上網絡流量特征復雜，分類規則的設計是一個難點。袁琴琴等[11]提出一種基于改進ACO和遺傳算法(Genetic Algorithm，GA)組合的網絡入侵檢測方法IACO-GA，采用遺傳算法對網絡入侵的特征進行快速選取，再利用改進ACO選取特征子集。混合算法為求解特征子集提供了比較好的思路，但該文獻并未對改進ACO及GA的關鍵參數做具體分析，事實上算法參數對IDS分類器性能的影響很大，如何確定算法參數是研究難點。Nguyen等[12]提出了利用遺傳算子優化PSO的特征選擇方法(CMPSO)，利用遺傳算子提高PSO的搜索性能，但因遺傳算子中交叉、變異概率是固定的，容易陷入局部最優。張震等[13]提出改進粒子群聯合禁忌搜索的特征選擇算法IPSO-TS，采用遺傳算子求得特征選擇初始最優解，然后進行禁忌搜索得到特征子集全局優化解，思路較好，但該方法采用KNN作為分類器，KNN不能處理特征維度太高的數據，另外該方法的復雜度較高，導致求解特征子集的時間較長。

綜合分析以上文獻的優缺點，本文提出一種基于改進ACO求解特征子集的入侵檢測方法(IDM-FS-IACO)，該方法可以在初步提取的特征點中進一步求解特征子集，并在訓練階段優化改進ACO及SVM的參數。實驗證明，相比其他方法，IDM-FS-IACO的F-Measure值有一定提升，測試時間顯著減少。

1 IDM-FS-IACO思路

(1) 對KDD CUP 99數據集特征屬性做預處理，通過信息熵理論求得初步提取的特征點，并構造特征拓撲。

(2) 由改進ACO進一步求解特征子集。在改進ACO中，螞蟻的初始位置、啟發函數、信息素更新策略及狀態轉移概率函數均做了優化。

(3) 采用KDD CUP 99數據集[14]，通過十折交叉驗證法訓練及優化改進ACO及SVM的參數，并測試該入侵檢測方法的性能。

IDM-FS-IACO方法的流程如圖1所示。

圖1 IDM-FS-IACO流程

2 數據預處理及構造特征拓撲

2.1 構造數據子集

采用KDD CUP 99的10%，按照原始比例分別選出四類入侵樣本和正常樣本，混合構成四個數據子集：DoS+Normal，Probe+Normal，U2R+Normal，R2L+Normal，再分別將這些數據集十等分，十等分后各數據子集的樣本類別及平均數量如表1所示。

表1 各數據子集的樣本類別及平均數量

2.2 數據歸一化處理

不同特征屬性的取值范圍差異較大，對數據分析結果有較明顯的影響，因此應先進行數據的歸一化處理，具體公式如下：

(1)

式中：x′i表示歸一化后的特征值；xi表示原始特征值；max(xi)和min(xi)分別為該特征屬性的最大取值和最小取值。歸一化處理后，所有的特征屬性取值范圍為[0,1]。

2.3 數據離散化

因KDD CUP 99數據集中，既有離散化數據，也有連續型數據，因此采用信息熵的離散化方法，將連續型數據進行離散化。

假設I為一個連續實數區間，L(I)為該區間長度，A為該區間內所有的樣本集合，|A|為集合A的樣本總數，D(I)為集合A在區間B上的密度，公式如下：

(2)

假設特征F在區間A上所有的取值升序排列后為f1，f2，…，fn，則有如下分割點bi：

(3)

以分割點bi為例，可以將集合A劃分為兩個子集A1i和A2i，對應的兩個子區間為I1i和I2i。

A1i={a∈A|AF

(4)

A2i={a∈A|AF≥bi}

(5)

式中：AF表示特征F在集合A上的取值。

計算以上兩個子集的信息熵，公式如下：

(6)

(7)

式中：Pkj為類別j的樣本個數在Ak中所占的比例。記bi為b，則劃分后的兩個子集為A1和A2，對應的兩個區間為I1和I2，信息熵閾值計算如下：

?i=D(Ii)·E(A)i=1,2

(8)

如果E(A,bi)>?i，對區間Ii按照如上方法遞歸地進行劃分。

2.4 特征的初步提取

根據信息熵理論對特征屬性進行初步提取分析，信息熵的取值可以反映不同特征屬性間的差別。

pxy表示第x個特征屬性取第y個值的概率，nxy表示第x個特征取第y個值的樣本個數，nx表示第x個特征的全部取值個數(相同取值個數也累加)，mx表示第x個特征的不同取值個數，Ex表示第x個特征的信息熵，CVx表示第x個特征的差異系數，則有如下公式：

(9)

(10)

CVx=1-Ex

(11)

得出第x個特征屬性的權重系數Wx如下：

(12)

式中：N表示數據對應的全部特征個數。

將所有特征屬性按其權重系數按降序排列，按式(13)選取權重較大的特征屬性。

(13)

式中：δ=0.80；m取最小值，將前m個特征屬性提取出，其余特征屬性刪除。按照此方法對實驗所用的表1中的數據樣本特征進行初步提取分析，得出各類入侵類型樣本對應的主要特征個數、權重、對應的特征屬性如表2所示。

表2 初步提取后的特征屬性及權重比例

分析表2，經過初步提取，僅保留了13～15個特征，但這些特征權重比例超過了80%，保留了絕大部分的有效信息，同時大幅度減少了后續的數據處理量。

2.5 構造特征鄰接拓撲

根據圖論知識，系統中多個元素之間的關系可由圖來表示，令圖G={V,E,W}，其中：V表示點集；E表示邊集；W表示每條邊的權重集合，此處邊的權重描述兩個節點的選擇期望，在后面啟發函數的改進中有詳細分析。

因此，以m個特征屬性對應構造m個特征點，其中m的取值見表2。m個特征點之間兩兩相連，構造鄰接拓撲。四種不同的入侵類型，對應四個不同的特征鄰接拓撲。特征點m較多時，特征拓撲相對復雜，下面是以5個特征點為例構造的特征鄰接拓撲，如圖2所示。

圖2 特征鄰接拓撲

3 改進ACO求解特征子集

3.1 改進ACO與傳統ACO的類比

傳統ACO通常用來求解最短路徑，而本文提出的改進ACO用來求解特征子集，兩者類比分析如表3所示。

表3 改進ACO與傳統ACO的類比分析

3.2 螞蟻初始位置的改進

在改進ACO求解特征子集的過程中，第1次迭代時，n只螞蟻被平均分配到m個特征點上，以免漏掉重要的特征點。在第i(i=2,3，…,t*)次迭代時，按照以下方法初始分配螞蟻。

假設每只螞蟻求解的特征子集中特征點的數量為u，n只螞蟻第i-1次迭代后求解得到的n個特征子集中，特征點vj(j=1,2,…,m)總共出現的次數記為Ci-1(vj)。第i次迭代時，按照Ci-1(vj)的降序對特征點vj進行排列后，依次為特征點vj初始分配的螞蟻數量計算如下：

(14)

按照式(14)，將nj只螞蟻分配到特征點vj上，如果剩余的螞蟻數量小于nj時，則將剩余的螞蟻全部分配到特征點vj上。

3.3 啟發函數的改進

啟發函數ηij(t)用來描述t時刻，螞蟻從特征點vi到vj的選擇期望。ηij(t)的數值大小取決于特征點vi和vj的相似性，相似性越低，則兩個特征之間具有互補性，兩個特征全部被選中的概率也就越大，ηij(t)也就越大；反之，兩個特征點的相似性越高，則ηij(t)也就越小，ηij(t)計算公式如下：

ηij(t) = 1 -prij

(15)

(16)

3.4 信息素更新策略的改進

第t+1次時刻，特征點vi到特征點vj的信息素更新函數如下：

τij(t+1)=(1-ρ)·τij(t)+ρ·Δτij(t)

(17)

(18)

(19)

3.5 狀態轉移概率函數的改進

在傳統蟻群算法中，t時刻第k只螞蟻從特征點vi轉移到vj的狀態轉移概率函數公式如下：

(20)

式中：α和β表示兩個權重參數，分別反映螞蟻在運動中所積累的信息素和啟發函數值對螞蟻選擇下一跳時的影響；Aki表示允許螞蟻k從節點i跳到的下一特征點的集合。式(20)容易導致螞蟻過早收斂至局部最優解，為解決此問題，將狀態轉移概率函數改進如下：

(21)

(22)

式中：Random表示返回在該區間內隨機生成的一個實數。

(23)

改進的狀態轉移概率函數不僅有φ的概率按照Pk(ij)(t)搜索下一跳，同時還有γ的概率隨機進行搜索，目的是防止過早收斂至局部最優。特別是在早期迭代時，t數值較小，Pk(ij)(t)相對不夠科學，因此γ取值不可忽略，可以凸顯出隨機搜索的相對重要性。但隨著螞蟻迭代次數累加，t數值逐漸增大時，Pk(ij)(t)相對更具科學指導意義，因此γ取值逐漸趨近于0，螞蟻搜索下一跳更依賴于Pk(ij)(t)，以便可以最終收斂至最優解。

3.6 改進ACO偽代碼

算法1改進算法

輸入：G,m,n,m*,α,β,λ,t*,τij(0)等。

輸出：S*(t*)。

1. Lett=1,Sk(t)={}

//開始迭代，初始化特征子集為空

2. while(t≤t*)

3. {Place ants with formula(15);

//確定螞蟻位置

4. For each antk(k=1,2,…,n)

5. {Updateηijandτijby formula(15)and(17);

//更新參數

6. From current feature nodevi，select the next feature

nodevjby formula(21);

//尋找下一特征點

7. Add feature nodevjtoSk(t);}

//添加特征點到特征子集

8.t=t+1;}

9. End while

10. Return the best subsetS*(t*)

//返回最佳特征子集

3.7 改進ACO的收斂性及復雜度分析

(1) 改進蟻群收斂性分析。因傳統ACO的收斂性已經得到證明，可參見文獻[16]，本文只需證明，式(21)隨著t的增加，收斂于傳統ACO的狀態轉移概率函數即可。

根據式(22)和式(23)，可以得出：

(24)

(25)

由式(24)、式(25)，可以得出：

(26)

因此，隨著迭代次數的遞增，改進的狀態轉移概率函數收斂于傳統ACO的轉移函數，證畢。

(2) 時空復雜度分析。分析算法1可以得出，時間復雜度最高的語句應為6，即螞蟻k執行式(21)的復雜度，這與集合Sk(t)及Aki都直接相關，也就是取決于鄰接拓撲G的特征點個數m，因此，算法1中語句6的時間復雜度應為O(m2)。

因螞蟻數量為n，所以n個螞蟻執行完一次全局搜索，時間復雜度為O(m2·n)。假設改進蟻群算法收斂完畢需總共執行t*次，則改進ACO的完整時間復雜度應為O(t*·m2·n)，并沒有增加原ACO的時間復雜度。

因特征節點數量為m，則鄰接拓撲G及信息素變量各需要一個m(m-1)/2的二維數組來存儲數據，此處空間復雜度為O(m2)；兩個集合Sk(t)及Aki中的元素均為G中的節點，因此空間復雜度為O(m)，考慮到螞蟻數量為n，此處空間復雜度為O(n·m)。因此，ACO的空間復雜度應為O(m2)+O(n·m)。

但考慮到本文的改進蟻群算法，在每次迭代前要按照式(14)重新分配螞蟻，此處的空間復雜度為O(m)。綜合以上分析，改進蟻群算法的空間復雜度為O(m2)+O((n+1)·m)，基本等同于原ACO的空間復雜度O(m2)+O(n·m)。

4 評估指標及參數的訓練優化

4.1 評估指標

定義1實例類別。TP(True Positive)：真正類，實際為入侵樣本并且被成功檢測為入侵的樣本數量；FN(False Negative)：假負類，實際為入侵樣本但沒有被成功檢測出，即漏報的樣本數量；FP(False Positive)：假正類，實際為正常樣本但被檢測為入侵，即誤報的樣本數量；TN(True Positive)：真負類，實際為正常樣本并且沒有被誤報的樣本數量。

定義2召回率指標Recall和查準率指標Precision：

(27)

(28)

定義3F-Measure評價指標。僅考慮召回率及查準率，并不能準確評估入侵檢測方法性能，因此采用調和函數F-Measure進行評價，公式如下：

(29)

在本文中，θ=1，均衡考慮召回率及精確率。

4.2 IDM-FS-IACO參數優化模型

本文采用徑向基RBF函數作為SVM核函數，將IDM-FS-IACO的參數優化數學模型描述如下：

maxF(S,P)

(30)

式中：(S,P)是一個混合向量，S表示改進ACO求解特征子集的參數，包括初始時刻信息素τij(0)、信息素揮發系數ρ、信息素更新權重參數α、啟發函數權重參數β、螞蟻數量n、最大迭代次數t*、特征子集中特征的個數m*，P表示SVM參數，包括誤差懲罰參數C和RBF核參數σ；F表示IDS模型的F-Measure值。

參考文獻[17-18]，確定改進ACO的參數取值或取值范圍，其中m的取值見表2；參考文獻[19-20]確定SVM的參數取值范圍，詳見表4。

表4 IDM-FS-IACO的參數取值或取值范圍

續表4

4.3 IDM-FS-IACO的訓練優化

服務器采用HP ProLiant ML10,內存16 GB，Xeon四核3.1 GHz主頻CPU，Windows 10 64 bit操作系統，采用林智仁教授的Libsvm-3.23實現仿真實驗。采用表1中十等分后混合的數據子集，通過循環十折交叉驗證求取平均值的方法進行訓練并優化參數。具體參數取值計算公式如下：

(31)

將四個數據子集訓練及測試獲得最佳F-Measure值時，對應的參數列入表5。

表5 IDM-FS-IACO的參數優化結果

表6 改進ACO求解的特征子集

分析表6，改進ACO對初步提取的特征(見表2)進行了進一步精簡，僅保留了4～6個有效特征，大幅度減少了冗余特征。

5 測試實驗結果對比分析

5.1 Recall和Precision結果的對比分析

采用與4.3節相同的實驗環境，采用林智仁教授的Libsvm-3.23實現仿真實驗。通過十折交叉驗證求取平均值的方法對表1中十等分后的數據子集進行測試實驗，綜合對比文獻[9]方法ACO-SVM、文獻[10]方法ADM-ACCRMA、文獻[11]方法IACO-GA、文獻[12]方法CMPSO、文獻[13]方法IPSO-TS，以及本文方法IDM-FS-IACO，將測試實驗的Recall平均值及Precision平均值結果列入表7。

表7 不同方法的Recall和 Precision平均值

分析表7，對于DoS、Probe入侵類型樣本，以上6種方法的實驗結果表現都較好，Recall平均值及Precision平均值均達到90%以上，其中IDM-FS-IACO的Recall平均值相比IPSO-TS分別提升1.87百分點、2.19百分點。

對于R2L入侵類型樣本，IDM-FS-IACO的實驗結果表現更好，相比IPSO-TS，Recall平均值及Precision平均值分別提升4.43百分點和2.09百分點。

對于U2R入侵類型樣本，因實驗所用數據集中該入侵類型的樣本很少，實驗結果表現均不好，但IDM-FS-IACO的Recall平均值仍達到了80%，Precision平均值相比IPSO-TS提升10百分點。

5.2 F-Measure結果的對比分析

僅考慮Recall平均值及Precision平均值并不能科學地評價以上方法的性能，根據式(29)計算F-Measure平均值，該結果對召回率及查準率進行了調和平均，可以全面科學地反映算法模型的性能，對比結果見圖3。

圖3 不同方法的F-Measure平均值

分析圖3，對于DoS、Probe、U2R、R2L四種不同入侵類型樣本，本文方法IDM-FS-IACO的F-Measure平均值相比其他5種方法均有一定程度的提升，特別是對于U2R及R2L入侵類型樣本，性能提升明顯。另外，IPSO-TS的性能表現也較為優秀，現具體對比分析IDM-FS-IACO及IPSO-TS的F-Measure值，結果如表8所示。

表8 IDM-FS-IACO及IPSO-TS的F-Measure平均值%

定義如下公式：

提升值= IDM-FS-IACO的F-Measure平均值- IPSO-TS的F-Measure平均值

提升百分比=(提升值/IPSO-TS的F-Measure平均值)×100%

分析表8，盡管IPSO-TS方法的F-Measure值比較優秀，但相比本文方法IDM-FS-IACO仍有一定差距，特別是對U2R和R2L入侵樣本，IDM-FS-IACO的F-Measure值提升較為顯著。

5.3 訓練時間及測試時間的對比分析

不同方法的訓練時間平均值如圖4所示，可以看出，ACO-SVM的訓練時間最長，原因是該方法重在SVM分類器參數的確定，并未去除冗余特征；而IACO-GA、IPSO-TS、IDM-FS-IACO的訓練時間則相差不大，因IDM-FS-IACO在訓練實驗時需對算法參數進行優化，因此訓練時間上沒有明顯優勢。但訓練時間處于離線階段，不會增加系統的在線檢測時間[21]。

圖4 不同方法的訓練時間平均值

不同方法的測試時間平均值如圖5所示，可以看出，因未去除冗余特征，ACO-SVM的測試時間最長；IDM-FS-IACO的測試時間相比其他方法均有所減少。另外，IPSO-TS方法在測試時間的表現上也較為優秀，現具體對比分析IDM-FS-IACO及IPSO-TS的測試時間，結果如表9所示。

圖5 不同方法的測試時間平均值

表9 IDM-FS-IACO及IPSO-TS的測試時間詳細對比