改進蟻群算法優化支持向量機的網絡入侵檢測

王雪松+梁昔明

摘要：針對支持向量機參數優化問題，為了提高網絡入侵檢測率，提出一種變異蟻群算法優化支持向量機的網絡入侵檢測模型（MACOSVM）。首先采用蟻群搜索路徑節點代表支持向量機參數，并將網絡入侵檢測率為目標函數，然后通過蟻群算法的全局尋優能力和反饋機制尋找最優參數，并對螞蟻進行高斯變異，克服蟻群陷入局部極值，最后將最優路徑上的節點連接起來得到SVM的最優參數，建立最優網絡入侵檢測模型。采用KDD99數據集對模型進行仿真實驗，仿真結果表明，MACOSVM的網絡入侵檢測速度要快于其它網絡入侵檢測模型，而且提高了網絡入侵檢測率。

1引言：

入侵檢測系統（intrusion detection system，IDS）作為防火墻之后的第二道安全閘門，能夠發現網絡入侵行為，因此網絡入侵檢測已成為網絡安全領域的研究熱點[1]。網絡入侵檢測分為誤用檢測（misuse intrusion detection，MID）和異常檢測（anomaly intrusion detection，AID）兩類[2]。誤用檢測技術只可以檢測已知入侵行為，不能對未知或變入侵行為進行檢測，而異常檢測可以較好對未知入侵行為進行檢測，成為入侵檢測中的主要研究方向[3]。傳統網絡入侵異常檢測算法有：模式匹配算法、BM算法、QS算法等，這些算法均屬于單模式的網絡入侵檢測算法，難以適應現代大規模網絡安全檢測要求[4]。近年來，隨著人工智能技術的發展，出現了隱馬爾可夫模型、支持向量機和神經網絡等入侵檢測模型，其中支持向量機（support vector machine，SVM）較好的克服了神經網絡等傳統機器學習算法的過擬合、泛化推廣能力差等缺陷，對于高維、小樣本的網絡入侵檢測具有明顯優勢[5-7]。大量實驗表明，基于SVM的網絡入侵檢測模型性能與其參數：懲罰因子C和核函數參數等直接相關。為了獲得較優SVM參數，學者們提出采用遺傳算法（GA）、粒子群算法（PSO），在一定程度上優化了SVM的入侵檢測性能[8-10]。蟻群算法（ant colony optimization algorithm，ACO）是一種源于大自然中生物世界的新仿生類算法，吸收了螞蟻的行為特性，通過其內在的搜索機制，易于與其他啟發式方法相結合[11，12]。

為了提高網絡入侵檢測率，提出一種變異蟻群算法（mutation ant colony optimization algorithm，MACO優化支持向量機的網絡入侵檢測模型（MACO-SVM），并通過仿真實驗對其有效性進行檢驗。

變異蟻群算法

蟻群算法是由意大利學者M Dorigo等人在1991年受到螞蟻搜索食物過程中依據同伴遺留下的信息激素進行最短路徑選擇的啟發而提出的一種新的仿生優化計算方法，具有正反饋、分布式計算和貪婪啟發式搜索等特點，但是基本蟻群算法存在過早收斂以及局部聚集等問題，為此，本文探路過程中，對螞蟻進行高斯變異，打破蟻群嚴重聚集的情況（局部極值），產生一種變異蟻群算法（MACO），以便探索新的路徑，提高問題求解的效率。

MACO算法優化SVM參數原理

采用MACO算法對SVM的參數C和σ優化過程，節點值表示C和σ，以入侵檢測率作為目標函數，激素物質遺留在螞蟻所走過的每個節點上，MACO算法所搜索出的最終路徑表示最優網絡入侵模型參數。SVM 參數優化的蟻群系統根據目標函數值來更新信息素的濃度，目標函數中包含各螞蟻所爬行過的全部節點信息以及所建模型的網絡入侵檢測率。待優化的變量為SVM的參數C和σ，程序終止時，從蟻群的最優化路徑中得到相對應的SVM的參數C和σ值，原理如圖1所示。

MACO算法優化SVM參數過程

1）設蟻群規模為m，每只螞蟻k均有一維數組pathk。其中依次存放第k只螞蟻經過n個節點的縱坐標，n為所優化參數的總有效位，這些縱坐標連接在一起組成該螞蟻的爬行路徑。

2）全部螞蟻置于起始點O，循環次數N=0，時間計數器t=0，最大迭代次數為：Nmax，初始化節點上信息量△τ（xi，yi，j，0），并設Δτ（xi，yi，j）=0。

3）設置變量i=1。

4）根據式（7）計算螞蟻的轉移概率，在線段Li上，根據概率以賭輪算法選擇每只螞蟻下一個轉移節點，并將螞蟻轉移到相應節點上，并將該節點的縱坐標存入pathk的第i個元素中。

5）i=i+1，如果i>n，跳轉到步驟6），不然跳轉到步驟4）繼續爬行。

6）根據數組pathk計算該路徑對應的C和σ。

7）將訓練集平均分成k個子集S1，S2，…，Sk。

8）SVM根據獲得的{C，σ}對訓練集進行學習，計算kfold交叉驗證的檢測率。

9）以kfold交叉驗證中最優檢測率作為適應度值，檢測率最高對應路徑作為本次循環的最優路徑。

10）N=N+1，t=t+n，更新每個節點上的信息濃度，pathk中的全部元素置零。

11）對螞蟻進行高斯變異，打破蟻群嚴重聚集的情況（局部極值），以便探索新的路徑，并將新的路徑與原有路徑進行比較，選出最優螞蟻。

12）如果迭代次數大于最大迭代數，則表示算法結束，并計算輸出最優路徑對應的SVM參數C和σ值。

13）SVM根據最優C和σ值對訓練集重新學習，建立最優的網絡入侵檢測模型。

網絡入侵檢測多分類器構建

網絡入侵檢測實質上一個多分類問題，但SVM只能求解兩分類問題，必須通過組合策略構建網絡入侵檢測器，本文采用有向無環圖將兩分類的SVM組合在一起，構造的網絡入侵檢測器如圖2所示。

在CPU 2.8 GHz，RAM 1 GB 環境上，采用Libsvm 2，98實現仿真實驗。按照一般的做法，實驗采用KDD CUP 99數據集中的10%的數據（約10萬條記錄）中隨機抽取的的正常連接記錄作為訓練樣本。MACO算法的參數為：螞蟻數m=10，最大迭代次數Nmax=100，Q=100，α=2，β=4。

為了使MACO-SVM模型檢測更具說服力，在相同條件下，采用遺傳算法優化SVM（GA-SVM）和基本蟻群算優化SVM（ACO-SVM）作為對比實驗。模型性能評價指標為：檢測率、誤報率和運行速度。檢測率和誤報率定義如下：

檢測結果對比

GA、ACO、MACO算法對SVM參數選擇的結果見表3。然后采用表3的參數建立相應的網絡入侵檢測模型，GASVM、ACOSVM和MACOSVM的檢測結果見表3。從表3可知，相對于對比模型GASVM、ACOSVM，MACOSVM的中支持向量數更少，但檢測結果最佳，這表明 MACO算法比GA、ACO在SVM參數優化方面具有更好的較強的全局搜索能力，獲得更優的SVM參數C，σ，可以降低網絡入侵檢測誤報率，有效提高了網絡入侵檢測率。

運行速度對比

為了檢測模型的運行速度，采用模型對驗證集的檢測時間（秒，s）作為衡量指標，各模型的檢測時間見圖3。從圖3可知，相對于GASVM、ACOSVM，MACOSVM檢測速度大幅度提高，主要由于MACOSVM減少了支持向量點數量，收斂速度加快，滿足了現代網絡入侵檢測系統的實時性要求。

結論：基于SVM的網絡入侵檢測模型泛化能力與其參數選取密切相關，為了解決了SVM參數優化難題，提出一種基于MACOSVM的網絡入侵檢測模型。采用蟻群搜索路徑節點表示SVM參數，將最優路徑上的節點連接起來就可以得到SVM的最優參數C，σ值。仿真實驗結果表明，MACOSVM可以獲得較優的SVM參數，不僅可以加快網絡入侵檢測速度，同時提高了網絡入侵的檢測率，誤報率明顯降低。