丁 贏，殷肖川，胡 傲

(空軍工程大學(xué) 電訊工程學(xué)院，陜西 西安 710077)

對入侵檢測的研究可以追溯到20世紀(jì)80年代，入侵檢測的概念由James Anderson[1]首次引入。檢測技術(shù)從基于規(guī)則的匹配發(fā)展到智能檢測，入侵檢測系統(tǒng)的性能在很大程度上取決于入侵檢測技術(shù)的優(yōu)劣，設(shè)計有效的入侵檢測技術(shù)對提高系統(tǒng)性能非常關(guān)鍵。由于入侵檢測方法的重要性，已出現(xiàn)多種檢測技術(shù)[2-4]，其中的智能檢測技術(shù)由于在檢測正確率和自學(xué)習(xí)方面具有的良好性能而引起了廣泛關(guān)注。

現(xiàn)有智能檢測技術(shù)還存在一些不盡人意的地方。首先，現(xiàn)有的智能檢測技術(shù)忽略了合適的特征分析技術(shù)對入侵檢測的重要作用，且未考慮入侵檢測所面臨背景的特殊性；其次，在大規(guī)模網(wǎng)絡(luò)環(huán)境下，現(xiàn)有檢測技術(shù)在檢測正確率、誤警率、漏警率和檢測效率方面不能滿足要求，需設(shè)計新型的智能檢測技術(shù)解決日益增長的網(wǎng)絡(luò)規(guī)模以及處理數(shù)據(jù)量日益增大的問題。基于以上不足，本文提出一種新的解決方案，可明顯提高檢測正確率，且減低檢測時延。

遺傳算法模擬生物界物競天擇、適者生存的原則，通過交叉、變異、選擇操作來進(jìn)行全局優(yōu)化運算；蟻群算法模擬大量無意識個體組成有意識群體的生物界行為，通過正反饋使系統(tǒng)趨近于有序化，從而可進(jìn)行優(yōu)化運算，但初期需要大量的重復(fù)運算。本文利用遺傳螞蟻算法進(jìn)行特征提取，然后把支持向量機的參數(shù)作為特征加入到遺傳算法染色體，從而在對入侵特征進(jìn)行抽取的同時對支持向量機進(jìn)行優(yōu)化。

1 遺傳螞蟻算法

遺傳螞蟻算法的思想是在滿足目標(biāo)函數(shù)的限定條件之前采用遺傳算法，充分利用遺傳算法的群體性、全局收斂性、隨機性、快速搜索等優(yōu)勢生成初始解，即產(chǎn)生有關(guān)問題的初始信息素分布。隨后，采用蟻群算法，在有一定初始信息素分布的情況下，最大限度地利用蟻群算法的正反饋性、并行性、求精效率高等特點求取任務(wù)調(diào)度的最優(yōu)解。遺傳螞蟻算法流程如圖1所示，具體步驟如下：

(1)定義目標(biāo)函數(shù)和適應(yīng)值函數(shù)。

(2)隨機生成1組二進(jìn)制或者實數(shù)編碼。

(3)根據(jù)適應(yīng)函數(shù)選擇1對個體，并對其進(jìn)行交叉計算。

(4)根據(jù)適應(yīng)值函數(shù)進(jìn)行變異操作，通過比較解的結(jié)果，若沒生成若干組優(yōu)化解，則進(jìn)行選擇操作，并到第(2)步重新進(jìn)行交叉計算。

(5)如果生成若干優(yōu)化解，則進(jìn)入下一步螞蟻算法。

(6)nc←0(nc為迭代步數(shù)或搜索次數(shù))，初始化各參數(shù)，即 τij和 Δτij的初始化，根據(jù)優(yōu)化生成信息素初始分布，將m只螞蟻置于n個節(jié)點上。

(9)對所有路徑信息素進(jìn)行更新 τij(t+1)=(1-ρ)τij(t)+Δτij(t)，對各邊弧 Δτij←0，并且 nc←nc+1，若 nc 小于預(yù)定的迭代次數(shù)且無退化行為(即找到的都是相同解)，則轉(zhuǎn)入(7)步重新計算，否則進(jìn)入下一步。

(10)進(jìn)行重新的返回迭代或輸出最終結(jié)果。

2 基于條件熵的遺傳螞蟻算法參數(shù)設(shè)置

下面詳細(xì)介紹基于條件熵的遺傳螞蟻算法的步驟。

2.1 遺傳算法參數(shù)設(shè)置

2.1.1 遺傳個體編碼

遺傳個體的表示涉及編碼問題。借鑒參考文獻(xiàn)[5-6]的思想，設(shè)計新的遺傳個體結(jié)構(gòu)。采用二進(jìn)制編碼與實數(shù)編碼相結(jié)合的方式。遺傳個體都是由定長的個體構(gòu)成，表示可能的最優(yōu)特征子集和對應(yīng)的權(quán)重，以及SVM訓(xùn)練模型的參數(shù)。遺傳個體的結(jié)構(gòu)如圖2所示，前L參數(shù)表示原始輸入特征的個數(shù)，后L參數(shù)表示每個特征的權(quán)重，最后2個參數(shù)表示SVM模型中的參數(shù)C和核函數(shù)參數(shù)。這樣通過優(yōu)化適應(yīng)度函數(shù)可以得到最優(yōu)的入侵特征子集及對應(yīng)的權(quán)值，以及SVM模型中的參數(shù)C及核函數(shù)參數(shù)。

選擇不同的核函數(shù)構(gòu)造支持向量機模型，核函數(shù)以及相應(yīng)核函數(shù)參數(shù)的選擇會對支持向量機的分類性能產(chǎn)生較大影響，進(jìn)而對檢測性能產(chǎn)生重要影響。這也是將SVM模型中的參數(shù)納入遺傳個體設(shè)計的原因，期望通過遺傳算法的尋優(yōu)過程找到優(yōu)化的SVM模型參數(shù)，以進(jìn)一步提高分類性能。本文選用的核函數(shù)是徑向基函數(shù) RBF(Radial Basis Function)核函數(shù)，K(xi，xj)=exp(-ε|xi-xj|2)，其中ε是RBF核函數(shù)參數(shù)。

圖1 遺傳螞蟻算法流程圖

圖2 遺傳個體編碼表示

2.1.2 適應(yīng)度函數(shù)(目標(biāo)函數(shù))的定義

根據(jù)Helman建立入侵?jǐn)?shù)學(xué)模型[7]，將系統(tǒng)活動的特征參數(shù)看成平穩(wěn)隨機過程H在離散時間ti的取值，取值空間是有限集合S。系統(tǒng)活動的狀態(tài)集為X，X={正常，異常}。由于抽樣的隨機性，在得到特征參數(shù)后，對于系統(tǒng)活動狀態(tài)的判斷還存在風(fēng)險，即某種不確定性。這種不確定性可用條件熵來度量[8]：

式(1)中，H(X|S)越小，系統(tǒng)的不確定性也越小，越容易判斷系統(tǒng)狀態(tài)。式(1)中聯(lián)合概率分布和條件概率分布根據(jù)樣本數(shù)據(jù)來估計。記樣本的大小為N，n(x，s)為系統(tǒng)活動為x、特征參數(shù)為s的樣本在樣本集合中出現(xiàn)的次數(shù)，n(s)是特征參數(shù)為s的樣本在樣本集合中出現(xiàn)的次數(shù)。于是有：

以往采用條件熵進(jìn)行特征抽取時，先確定選取特征數(shù)量，再采用順序后退法[9]。然而，由于特征個數(shù)不易確定，順序后退法剔除特征存在較大的隨機性，且被剔除的特征不能再被召回。

本文利用遺傳螞蟻算法啟發(fā)式搜索的優(yōu)點，以降低條件熵和分類錯誤率為目標(biāo)，在保證高的分類正確率的同時，考慮到數(shù)據(jù)的統(tǒng)計特性，進(jìn)一步消除冗余特征。用條件熵遺傳螞蟻算法進(jìn)行特征抽取時，使用條件熵和分類錯誤率聯(lián)合對抽取的特征進(jìn)行評估。由此定義的目標(biāo)函數(shù)如式(4)所示：

2.1.3 遺傳算子設(shè)計

選擇操作:采用輪盤賭的選擇方法，同時保留種群中的最優(yōu)個體直接進(jìn)入下一代的進(jìn)化中。

交叉操作:對實數(shù)值采用非均勻算術(shù)交叉。假設(shè)對A、B 2個個體進(jìn)行交叉，交叉后產(chǎn)生的個體為：

變異操作:對于實數(shù)值采用均勻變異，對于二進(jìn)制值則采用隨機變異。

在種群演化的過程中需要保留優(yōu)秀個體的模式，增強較差個體的變異能力，使算法跳出局部最優(yōu)解，克服早熟的缺點。結(jié)合最小化目標(biāo)函數(shù)的條件，對交叉和變異概率做以下的改進(jìn)[10]：

(1)對于適應(yīng)度函數(shù)值較大的個體，增加其交叉率和變異率。

(2)當(dāng)種群中的大部分個體擁有相近的適應(yīng)度且平均適應(yīng)度與最小適應(yīng)度接近時，說明此時群體可能收斂到局部最優(yōu)解，此時應(yīng)該增加大多數(shù)個體的交叉率和變異率，以跳出局部最優(yōu)。

(3)在進(jìn)化后期，交叉率應(yīng)逐漸減少，以利于保留最優(yōu)個體，但變異率應(yīng)逐漸提高，以跳出局部最優(yōu)解。

按照以上思路，提出如下交叉率pc和變異率pm的公式。

2.2 螞蟻算法參數(shù)設(shè)置

一般而言，蟻群算法的參數(shù)可通過反復(fù)試湊得到，但嚴(yán)重影響算法的運算效率。所以，國內(nèi)外研究人員在蟻群算法的參數(shù)分析和優(yōu)化組合方面做了大量工作。Dorigo M等人最早對 α、β、ρ、m等參數(shù)的選擇進(jìn)行了初步研究[11]；隨后 BOTEE[12]等人也對下面參數(shù)的選擇進(jìn)行了研究。

(1)啟發(fā)因子α的選擇

啟發(fā)因子α是表示殘留信息相對重要程度的參數(shù)，其大小反映了螞蟻在路徑搜索過程中隨機性因素作用的強弱：α值越大，螞蟻選擇以前走過的路徑的可能性也越大；α值太小時，易使蟻群的搜索過程過早陷于局部最優(yōu)。本算法選擇α∈[0.5，1.0]。

(2)期望啟發(fā)因子β的選擇

β是反映能見度相對重要程度的參數(shù)。β的大小反映了螞蟻在路徑搜索過程中確定性因素作用的強弱，其值越大，螞蟻選擇鄰近的局部最短路徑的可能性也越大；β過小，將導(dǎo)致螞蟻群體陷入純粹的隨機搜索，很難找到最優(yōu)解。隨著β的增大，算法收斂速度加快。本算法選擇 β∈[2，2.5]。

(3)信息素?fù)]發(fā)度ρ的選擇

參數(shù)ρ表示信息消逝程度，則1-ρ就是信息素殘留系數(shù)。ρ的大小直接關(guān)系到蟻群算法的全局搜索能力及其搜索收斂速度，1-ρ反映螞蟻個體相互影響的程度。本算法取 ρ∈[0.3，0.5]。

(4)蟻群數(shù)量m的選擇

蟻群算法也是一種隨機搜索算法，通過多個候選解組成群體的進(jìn)化過程來尋求最優(yōu)解。蟻群在搜索過程中表現(xiàn)出復(fù)雜而有序的行為，個體間的信息交流與相互協(xié)作起重要作用。本算法取m=25。

3 基于遺傳螞蟻算法與支持向量機聯(lián)合優(yōu)化(CEGAA-SVM)的網(wǎng)絡(luò)入侵檢測算法

基于條件熵的遺傳螞蟻算法與機器學(xué)習(xí)聯(lián)合優(yōu)化的方法來進(jìn)行網(wǎng)絡(luò)入侵檢測，CEGAA-SVM的總體框架圖如圖3所示。

CEGAA-SVM檢測算法分為訓(xùn)練階段和檢測階段兩部分。訓(xùn)練階段步驟如下：

圖3 CEGAA-SVM總體框架示意圖

其提供的“部分財產(chǎn)清單”顯示，黃道龍父子及親戚名下有多套房產(chǎn)，包括別墅。還有寶馬、凱迪拉克、奧迪車以及翡翠吊墜、書畫、古玩等。另一張賬戶明細(xì)顯示，黃宇名下有430萬余元現(xiàn)金。

(2)隨機生成初始種群。

(3)由個體的基因位確定所選擇的特征、權(quán)重以及SVM訓(xùn)練模型參數(shù)，根據(jù)適應(yīng)度函數(shù)計算每個個體的適應(yīng)度函數(shù)值，計算交叉率和變異率。

(4)對被選中的2個個體進(jìn)行交叉操作，產(chǎn)生后代個體。對被選中的個體進(jìn)行變異操作。根據(jù)輪盤賭選擇法按照個體的適應(yīng)度函數(shù)值大小對個體進(jìn)行選擇操作，保留最優(yōu)個體直接進(jìn)入下一代種群。

(5)重復(fù)執(zhí)行步驟(3)，直到進(jìn)化到最大代數(shù)，得到 1個可行解的子集，設(shè)子集中解的個數(shù)為n。

(6)根據(jù)上一小節(jié)，設(shè)置一群算法的初始參數(shù)，并以遺傳算法的輸出作為信息素的初始值。

(9)對所有路徑信息素進(jìn)行更新 τij(t+1)=(1-ρ)τij(t)+Δτij(t)，對各邊弧 Δτij←0，并且 nc←nc+1，若 nc 小于預(yù)定的迭代次數(shù)且無退化行為，則轉(zhuǎn)入第(7)步重新計算，否則進(jìn)入下一步。

檢測階段根據(jù)選擇的最優(yōu)特征子集及其權(quán)重和SVM優(yōu)化參數(shù)建立SVM檢測模型，對待分類個體進(jìn)行判斷。

4 仿真與分析

4.1 仿真數(shù)據(jù)集

實驗數(shù)據(jù)來源于KDDCUP99數(shù)據(jù)集，分為訓(xùn)練集和測試集，該數(shù)據(jù)集由麻省理工學(xué)院林肯實驗室提供。每條連接信息包含41維特征，包括基本特征集、內(nèi)容特征集、流量特征集和主機流量特征集。每個網(wǎng)絡(luò)連接都被標(biāo)記為正常或攻擊， 取值包括 Normal、Probe、DOS、U2R和RZL 5種類型。

在仿真中，將實驗數(shù)據(jù)集分為4個部分:Probe、DOS、R2L和U2R數(shù)據(jù)集，各數(shù)據(jù)集樣本數(shù)量如表1所示，測試集從KDDCUP99數(shù)據(jù)集的測試集中隨機抽取。

表1 仿真數(shù)據(jù)集的樣本數(shù)量

CEGAA的參數(shù)設(shè)置如表2所示。

表2 CEGAA的參數(shù)設(shè)置表

4.2 仿真結(jié)果及分析

實驗在Matlab7.0環(huán)境中運行。CEGAA-SVM的實驗結(jié)果如表3所示。通過對各類數(shù)據(jù)集(Probe、DOS、U2R、R2L)的測試集進(jìn)行實驗，由仿真結(jié)果可以看出，對特征進(jìn)行維數(shù)約減和空間變換后，不僅入侵特征的數(shù)量基本減少了一半，而且正確檢測率仍然取得了滿意的結(jié)果。

表3 CEGAA-SVM試驗結(jié)果

為進(jìn)一步驗證CEGAA-SVM的性能，分別采用標(biāo)準(zhǔn)SVM進(jìn)行入侵檢測、采用標(biāo)準(zhǔn)遺傳算法進(jìn)行特征抽取，以分類錯誤率為適應(yīng)度函數(shù)，結(jié)果如表4所示。

根據(jù)對特征數(shù)目、正確檢測率和檢測時間的比較可以看出，采用特征抽取與SVM聯(lián)合優(yōu)化的GA-SVM和CEGAA-SVM，在正確檢測率和檢測時間上明顯優(yōu)于傳統(tǒng)SVM算法。而采用條件嫡遺傳算法的CEGAA-SVM不僅降低了特征的維數(shù)，而且檢測率比GA-SVM高，以Probe數(shù)據(jù)集為例，正確率提高了3.0%。在正確率提高的同時也降低了檢測時延，檢測時延減少了0.023 ms。表5～表8是采用CEGAA-SVM分別對4個數(shù)據(jù)集檢測結(jié)果的混淆矩陣。

表4 CEGAA-SVM與SVM、GA-SVM性能比較

表5 Probe數(shù)據(jù)集混淆矩陣

表6 Dos數(shù)據(jù)集混淆矩陣

表7 U2R數(shù)據(jù)集混淆矩陣

表8 R2L數(shù)據(jù)集混淆矩陣

從分類正確率的角度來看，本文所提供算法的平均性能要優(yōu)于其他文獻(xiàn)的算法，特別是在較難檢測的U2R數(shù)據(jù)集上取得了滿意的檢測效果。

通過以上的仿真結(jié)果，可以得到如下結(jié)論:

(1)將特征分析技術(shù)和分類算法相結(jié)合的入侵檢測技術(shù)能夠有效地提高檢測精度和檢測效率。

(2)將特征抽取和分類模型進(jìn)行聯(lián)合優(yōu)化的入侵檢測技術(shù)，特征選擇時考慮到數(shù)據(jù)的統(tǒng)計特性，在得到優(yōu)化的特征向量的同時也得到與之相匹配的分類檢測模型。算法不論是在檢測正確率還是在檢測時延方面都比較理想，對檢測正確率不高的U2R數(shù)據(jù)集性能提升非常明顯，算法的漏警率和誤警率也較低。

(3)使用權(quán)重表示各個特征的重要程度，對特征空間進(jìn)行線性變換。這種方法相對于簡單地選擇或丟棄某些特征能夠取得更好的檢測效果。

本文提出結(jié)合條件熵遺傳螞蟻算法和支持向量機的入侵檢測技術(shù)CEGAA-SVM，將條件熵遺傳螞蟻算法用于最優(yōu)特征子集的選擇，同時進(jìn)行SVM模型參數(shù)優(yōu)化，尋找最佳特征子集和與之相匹配的SVM檢測模型，從而實現(xiàn)對入侵的檢測。實驗表明，采用CEGAA-SVM所提取的特征數(shù)量為SVM算法的一半，為GA-SVM算法的83%左右。CEGAA-SVM的正確率也有所提高，比SVM和GA-SVM算法分別提高10%和3%，其漏檢率和誤檢率也有明顯下降?？梢?，CEGAA-SVM是一種有效的入侵檢測算法。

[1]DAKE R.BIOMETRIC security[J].Dr.Dobb’s Journal，2001，26(11):93-96.

[2]HONG J.Plan reeognition through goal graph analysis[C].Proeeedings of 14th ECAI.Beriin， Gennany， 2000:496-500.

[3]劉日仙，谷文祥，殷明浩.智能規(guī)劃識別及其應(yīng)用的研究[J].計算機工程，2005，31(15):169-171.

[4]段新生.證據(jù)理論與決策[M].北京:中國人民大學(xué)出版社，1993.

[5]WHITE G B，F(xiàn)ISCH E A，POOCH U W.Cooperating security manager：a peer-based intrusion detection system[J].IEEE Network， 1996，10(1):20-23.

[6]ASAKA M，TAGUCHI A，GOTO S.The implementation of IDA:an intrusion detection agent system.Proceedings of the FIRST Conf[C].Brishane，1999.

[7]陳志文，王開云，姜建國.網(wǎng)絡(luò)入侵檢測系統(tǒng)的警報合成算法設(shè)計[J].信息與電子工程，2005，3(3):182-185.

[8]VALEU F，CUI Y.An intrusion alert correlator based on prerequisites of intrusion.Technical Report， TR-2002-01，Department of Computer Science，North Carolina State U-niversity，2002.

[9]張國宣，孔銳，施澤生，等.基于核聚類方法的多層次支持向量機分類樹[J].計算機工程，2005，31(5).

[10]MURPHY S.The advanced encryption standard (AES)[J].Information Security Technical Report， 1999，4(4):12-17.

[11]SEHNEIER B.Cryptographic design vulnerabilities[J].IEEE Computer.1999，31(9):29-33.

[12]NACEACHE D.Padding attacks on RSA[J].Information Security Technical Report， 1999，4(4):28-33.