王雪松+梁昔明

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

1引言：

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

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

變異蟻群算法

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

MACO算法優(yōu)化SVM參數(shù)原理

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

MACO算法優(yōu)化SVM參數(shù)過程

1）設(shè)蟻群規(guī)模為m，每只螞蟻k均有一維數(shù)組pathk。其中依次存放第k只螞蟻經(jīng)過n個節(jié)點的縱坐標(biāo)，n為所優(yōu)化參數(shù)的總有效位，這些縱坐標(biāo)連接在一起組成該螞蟻的爬行路徑。

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

3）設(shè)置變量i=1。

4）根據(jù)式（7）計算螞蟻的轉(zhuǎn)移概率，在線段Li上，根據(jù)概率以賭輪算法選擇每只螞蟻下一個轉(zhuǎn)移節(jié)點，并將螞蟻轉(zhuǎn)移到相應(yīng)節(jié)點上，并將該節(jié)點的縱坐標(biāo)存入pathk的第i個元素中。

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

6）根據(jù)數(shù)組pathk計算該路徑對應(yīng)的C和σ。

7）將訓(xùn)練集平均分成k個子集S1，S2，…，Sk。

8）SVM根據(jù)獲得的{C，σ}對訓(xùn)練集進(jìn)行學(xué)習(xí)，計算kfold交叉驗證的檢測率。

9）以kfold交叉驗證中最優(yōu)檢測率作為適應(yīng)度值，檢測率最高對應(yīng)路徑作為本次循環(huán)的最優(yōu)路徑。

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

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

12）如果迭代次數(shù)大于最大迭代數(shù)，則表示算法結(jié)束，并計算輸出最優(yōu)路徑對應(yīng)的SVM參數(shù)C和σ值。

13）SVM根據(jù)最優(yōu)C和σ值對訓(xùn)練集重新學(xué)習(xí)，建立最優(yōu)的網(wǎng)絡(luò)入侵檢測模型。

網(wǎng)絡(luò)入侵檢測多分類器構(gòu)建

網(wǎng)絡(luò)入侵檢測實質(zhì)上一個多分類問題，但SVM只能求解兩分類問題，必須通過組合策略構(gòu)建網(wǎng)絡(luò)入侵檢測器，本文采用有向無環(huán)圖將兩分類的SVM組合在一起，構(gòu)造的網(wǎng)絡(luò)入侵檢測器如圖2所示。

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

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

檢測結(jié)果對比

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

運行速度對比

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

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