改進(jìn)蟻群算法優(yōu)化支持向量機(jī)的網(wǎng)絡(luò)入侵檢測(cè)

王雪松+梁昔明

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

1引言：

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

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

變異蟻群算法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

檢測(cè)結(jié)果對(duì)比

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

運(yùn)行速度對(duì)比

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

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