基于隨機(jī)最小冗余條件互信息和支持向量機(jī)的混合入侵檢測(cè)特征選擇

丁宣宣 郭淵博

(解放軍信息工程大學(xué) 河南 鄭州 450001) (數(shù)學(xué)工程與先進(jìn)計(jì)算國家重點(diǎn)實(shí)驗(yàn)室 江蘇 無錫 214000)

基于隨機(jī)最小冗余條件互信息和支持向量機(jī)的混合入侵檢測(cè)特征選擇

丁宣宣 郭淵博

(解放軍信息工程大學(xué) 河南 鄭州 450001) (數(shù)學(xué)工程與先進(jìn)計(jì)算國家重點(diǎn)實(shí)驗(yàn)室 江蘇 無錫 214000)

針對(duì)入侵檢測(cè)日志中存在著大量的不相關(guān)和冗余特征屬性，嚴(yán)重影響檢測(cè)的實(shí)時(shí)性，而大多數(shù)特征選擇算法不能兼顧相關(guān)性和信息量，且容易陷入局部最優(yōu)解，提出一種基于隨機(jī)最小冗余條件互信息和支持向量機(jī)的混合入侵檢測(cè)特征選擇方法。首先利用互信息和相關(guān)性去除沒有分類信息量和特征間高度相關(guān)的冗余特征，然后利用隨機(jī)最小冗余條件互信息準(zhǔn)則以及支持向量機(jī)選擇出具有最多分類信息量的最優(yōu)特征子集，一定程度地避免了局部最優(yōu)解。實(shí)驗(yàn)結(jié)果表明，該方法能在確保入侵檢測(cè)正確率的情況下以更高的效率選擇出最小最優(yōu)的入侵檢測(cè)特征子集。

信息熵 互信息 支持向量機(jī) 特征選擇 入侵檢測(cè)

0 引 言

入侵檢測(cè)技術(shù)是網(wǎng)絡(luò)安全主動(dòng)防御中的核心技術(shù)之一，主要通過收集和分析來自系統(tǒng)和應(yīng)用程序的審計(jì)日志以及網(wǎng)絡(luò)中數(shù)據(jù)包發(fā)現(xiàn)入侵行為或者企圖，并及時(shí)給出警報(bào)[1]?？梢詫⑷肭謾z測(cè)看成檢測(cè)系統(tǒng)狀態(tài)為“正?！边€是“異?！钡亩诸悊栴}。隨著云計(jì)算時(shí)代的來臨，計(jì)算機(jī)網(wǎng)絡(luò)越來越普及，產(chǎn)生了大量的網(wǎng)絡(luò)流量數(shù)據(jù)，如果不能及時(shí)檢測(cè)到這些網(wǎng)絡(luò)數(shù)據(jù)中隱藏的安全問題或者攻擊行為，容易造成漏報(bào)警，嚴(yán)重者可能會(huì)給企業(yè)和個(gè)人帶來巨大的損失。只有及時(shí)地從網(wǎng)絡(luò)傳輸數(shù)據(jù)中發(fā)現(xiàn)威脅并做出響應(yīng)，才能將入侵帶來的損失降到最低。如何能準(zhǔn)確并快速地從海量傳輸數(shù)據(jù)中發(fā)現(xiàn)潛在威脅一直是入侵檢測(cè)技術(shù)面臨的一個(gè)主要問題。因此，對(duì)入侵檢測(cè)系統(tǒng)的要求不僅包括準(zhǔn)確性，還要有實(shí)時(shí)檢測(cè)能力。如何在保證準(zhǔn)確性的前提下提高入侵檢測(cè)系統(tǒng)的反應(yīng)能力成為當(dāng)前研究的熱點(diǎn)之一。通過分析可以發(fā)現(xiàn)，檢測(cè)日志和數(shù)據(jù)包中包含了大量的不相關(guān)和冗余特征，它們并非或者極少是反映系統(tǒng)安全狀態(tài)信息的特征，對(duì)檢測(cè)結(jié)果幾乎沒有影響。一條網(wǎng)絡(luò)連接行為通常利用多個(gè)屬性加以描述，例如KDD-Cup99數(shù)據(jù)集中采用41種特征屬性來描述每條連接。過多的維數(shù)包含的不相關(guān)和冗余特征會(huì)增加檢測(cè)算法的運(yùn)行時(shí)間，不能及時(shí)發(fā)現(xiàn)入侵威脅。如果不對(duì)這些數(shù)據(jù)源進(jìn)行處理，將包含冗余和噪聲的數(shù)據(jù)直接用于檢測(cè)算法，會(huì)使運(yùn)算效率大幅度降低。大多數(shù)檢測(cè)算法的運(yùn)行時(shí)間會(huì)隨著數(shù)據(jù)維數(shù)的增加迅速增長，當(dāng)數(shù)據(jù)維數(shù)很大時(shí)會(huì)產(chǎn)生維數(shù)爆炸，嚴(yán)重影響檢測(cè)的實(shí)時(shí)性。其次，面對(duì)大規(guī)模數(shù)據(jù)集的特征挖掘，通過特征選擇方法找出準(zhǔn)確刻畫多結(jié)構(gòu)、多類型的網(wǎng)絡(luò)連接行為的特征，保留能夠反映系統(tǒng)狀態(tài)的重要特征對(duì)于提高入侵檢測(cè)系統(tǒng)檢測(cè)效率至關(guān)重要[2]。因此，很多研究者通過特征選擇技術(shù)解決這個(gè)問題。目前，已有不少研究者提出在搜索策略和評(píng)估算法等不同階段優(yōu)化特征選擇算法。Yu 等[3]通過分析特征之間的相關(guān)性和冗余性來有效選取特征，但選出的特征不能確保分類能力。Sung等[4]提出使用支持向量機(jī)和神經(jīng)網(wǎng)絡(luò)進(jìn)行入侵檢測(cè)特征的選擇，該算法雖然能選擇與分類信息相關(guān)的所有特征，卻忽略了特征之間存在的相關(guān)性，且實(shí)現(xiàn)起來相對(duì)復(fù)雜。Park[5]利用特征與目標(biāo)類的相關(guān)矩陣進(jìn)行輕量級(jí)入侵檢測(cè)系統(tǒng)的特征選擇，但當(dāng)特征維度較高時(shí)，其運(yùn)算效率迅速降低。朱等[6]提出使用遺傳算法選擇檢測(cè)特征，該算法比啟發(fā)式算法更有優(yōu)勢(shì)，具有較好的選擇效果，可時(shí)間復(fù)雜度達(dá)到了O(m3)。Sun[7]提出一種基于信息熵的并行特征選擇方案，可處理大規(guī)模數(shù)據(jù)的特征選擇，但其沒有考慮特征之間可能存在冗余。Peng[8]提出的算法較全面地分析了特征選擇過程中的相關(guān)性和冗余性。Yu[9]提出一種通過支持向量機(jī)概率靈敏度分析的特征選擇算法，選出那些最具有分類信息的特征集，但效率不高。

結(jié)合以上分析，本文提出一種結(jié)合隨機(jī)最小冗余條件互信息和支持向量機(jī)的混合入侵檢測(cè)特征選擇方法。該方法首先使用互信息和線性相關(guān)性對(duì)所有特征進(jìn)行初選，去除了特征之間具有強(qiáng)相關(guān)性的冗余特征以及不具有分類信息量的不相關(guān)特征，再使用提出的LRCI-SVM算法保留具有最多分類信息的最優(yōu)特征子集，其可以在保證原始特征分類精度的情況下選擇出最小的特征子集。由于該入侵檢測(cè)特征選擇方法的運(yùn)算過程容易實(shí)現(xiàn)，且效率較高，具有很好的可擴(kuò)展性，能用于高維度的特征選擇。

1 本文工作及論文結(jié)構(gòu)

針對(duì)入侵檢測(cè)收集的網(wǎng)絡(luò)連接數(shù)據(jù)，包括連續(xù)數(shù)據(jù)與離散數(shù)據(jù)，本文研究的主要方法是針對(duì)離散數(shù)據(jù)的特征選擇。因此，首先是將所有收集到的數(shù)據(jù)集進(jìn)行預(yù)處理，這個(gè)處理過程包括連續(xù)屬性離散化以及波動(dòng)范圍較大的特征屬性正則化等。然后將預(yù)處理過的所有數(shù)據(jù)按照原來的數(shù)據(jù)分布分成三份，即訓(xùn)練集、驗(yàn)證集，以及測(cè)試集。所有的入侵檢測(cè)訓(xùn)練數(shù)據(jù)通過基于最小冗余條件互信息和支持向量機(jī)的混合特征選擇方法進(jìn)行子集的選擇，其結(jié)果就是所選的最優(yōu)特征子集。測(cè)試數(shù)據(jù)集去除不相干特征之后利用5折交叉驗(yàn)證的方法訓(xùn)練分類器，驗(yàn)證該特征子集最終的入侵檢測(cè)性能等。本文提出的混合特征選取方法的整體結(jié)構(gòu)如圖1所示。

圖1 本文特征選擇方法的整體結(jié)構(gòu)

2 基于隨機(jī)最小冗余條件互信息的特征選擇

2.1 最小冗余條件互信息準(zhǔn)則

信息熵可以量化隨機(jī)變量{Xi}的不確定性，基于信息熵的互信息能夠衡量任意兩個(gè)變量之間的統(tǒng)計(jì)依賴性，互信息的值越大，表明這兩個(gè)變量之間的相關(guān)性越高。利用信息熵和互信息來選擇特征子集，可以理解為選擇一個(gè)與目標(biāo)類具有最大依賴性的最小特征子集，假設(shè)該特征子集S具有m個(gè)特征{Xi}，k為分類的類別數(shù)，則最優(yōu)的特征子集S應(yīng)該與目標(biāo)類C具有最大的依賴性，該準(zhǔn)則叫做最大依賴準(zhǔn)則，可用公式表達(dá)：

(1)

盡管最大依賴性的理論能夠找到一個(gè)最優(yōu)的特征子集S，但每選出一個(gè)特征都需要估算多變量概率p(X1,X2,…,Xm)和p(X1,X2,…,Xm,Cl)的值。由于缺少足夠的樣本數(shù)目，難以得到精確的估計(jì)，且對(duì)于高維特征的選擇，多變量的概率計(jì)算效率太低。雖然最大依賴準(zhǔn)則能夠?qū)さ阶钚〉奶卣髯蛹?，卻不適合投入應(yīng)用。

由于最大依賴準(zhǔn)則難以實(shí)現(xiàn)，則需要尋找一個(gè)可替代的方案近似地實(shí)現(xiàn)最大依賴性。特征選擇的衡量標(biāo)準(zhǔn)是基于這樣的假設(shè)：子集中特征應(yīng)該與目標(biāo)類具有高度相關(guān)性，即強(qiáng)相關(guān)性；且特征之間沒有關(guān)聯(lián)，即低冗余性[10]。這個(gè)假設(shè)給了我們兩個(gè)定義特征好壞的標(biāo)準(zhǔn)，一個(gè)就是特征與類的關(guān)聯(lián)，另一個(gè)就是特征與特征之間的關(guān)聯(lián)。就互信息而言，可以理解為特征-類之間應(yīng)該具有最大的互信息，即該特征或者特征子集應(yīng)該包含盡可能多的與類相關(guān)的信息量，具有很高的類辨識(shí)度。特征-特征之間的互信息應(yīng)盡可能小，即子集內(nèi)任意兩個(gè)特征Xi與Xj應(yīng)該包含不同的關(guān)于分類的信息量，這樣才能確保特征子集中的冗余信息最小。條件互信息能夠衡量在某個(gè)變量已知時(shí)，另外兩個(gè)變量之間的互信息量，通過改變選擇策略，可以很好地權(quán)衡高相關(guān)性和低冗余性，適合用于特征子集的選擇。條件信息熵H(Xj|Xi)衡量了當(dāng)Xi已知時(shí)，Xj中剩余的不確定性[11]。當(dāng)Xi已知時(shí)，Xj與目標(biāo)類C的條件互信息可用公式表示：

I(C;Xj|Xi)=H(C|Xi)-H(C|Xi,Xj)

(2)

式(2)描述了當(dāng)Xi已知時(shí)，估計(jì)Xj與C共享的信息量是多少。此時(shí)，如果Xi是Xj的一個(gè)決定函數(shù)，則當(dāng)Xi已知時(shí)這個(gè)條件互信息的值為0，不需要Xj中的任何信息來描述C了。如果他們是獨(dú)立的，Xi沒有包含Xj帶來的關(guān)于C的信息，條件互信息的值就等于該特征與目標(biāo)類的互信息。特征選擇的主要目的是找到一個(gè)包含盡可能多的關(guān)于分類信息的最小特征子集，而條件互信息能夠判斷在已有信息的基礎(chǔ)上新選擇特征包含的分類信息量。

為使選取的特征之間具有最小的冗余信息和最大的分類信息量，本文使用增量搜索的策略，當(dāng)且僅當(dāng)特征Xj與所有已選特征Xi具有最大條件互信息時(shí)，該特征才能被選取。這就意味著新選擇的特征包含了所有已選特征都沒有的信息量。但現(xiàn)實(shí)中，特征與特征之間經(jīng)常存在著或大或小的弱依賴性，難以找到與所有已選特征都具有最大條件互信息的待選特征。所以，本文使用最小冗余條件互信息準(zhǔn)則LRCMI(Least Redundant Conditional Mutual Information criteria)來衡量待選特征具有的額外信息量：每次從待選特征集中搜索特征Xj，選擇使得Xj與所有已選特征Xi的最小條件互信息最大的特征變量，這樣就確保了每次迭代都能夠選取更多已選子集中沒有的關(guān)于C的分類信息量，使得已選特征與待選特征的冗余最低。假設(shè)第m(1

(3)

可以看出：LRCMI準(zhǔn)則可以在已選特征集的基礎(chǔ)上選擇一個(gè)與所有已選特征具有最小冗余分類信息的特征變量，確保每次選取的特征能夠帶來更多“純凈”的分類信息量。

2.2 隨機(jī)最小冗余條件互信息算法

由于增量搜索策略是貪心算法的一種，其結(jié)果容易陷入局部最優(yōu)解，而結(jié)合隨機(jī)化算法可以一定程度地避免局部最優(yōu)解，雖然不是最優(yōu)，但仍比單純的隨機(jī)化算法更接近最優(yōu)[12]。文獻(xiàn)[13-15]提出了將Filter算法結(jié)合隨機(jī)算法的特征選擇，比如遺傳算法、模擬退火算法以及蟻群算法等。由于最終的優(yōu)化結(jié)果跟初始值的選取有很大關(guān)系[16]，為了盡可能避免出現(xiàn)局部最優(yōu)解，使用隨機(jī)搜索初始值的方法。假設(shè)最終需要選擇包含K個(gè)特征的最優(yōu)特征子集，則當(dāng)k=1時(shí)，隨機(jī)獲取待選特征集中的某一特征作為初始已選特征，再使用增量搜索策略按照最大條件互信息準(zhǔn)則選取剩余的K-1個(gè)。使用這種隨機(jī)初始值結(jié)合增量搜索的方法，選出T個(gè)符合條件的次優(yōu)特征子集，最后判斷保留分類精度最優(yōu)的一個(gè)。該算法的核心是按照LRCMI準(zhǔn)則選擇特征子集的過程，則第t(1≤t≤T)次迭代時(shí)，算法1給出了最小冗余條件互信息特征選擇算法的偽代碼，具體描述如下：

算法1最小冗余條件互信息特征選擇算法

form=1…Mdo

min_inf[m]←inf(m)

當(dāng)k=1時(shí)，

s[k]=random(1,M)

form=1…M do

min_inf[m]←min(min_inf[m],cond_inf(m,s[k]))

fork=2…K do

s[k]=arg maxm{min_inf[m]}

for m=1…M do

min_inf[m]←min(min_inf[m],cond_inf(m,s[k]))

end

上述算法在每次迭代都會(huì)挑選剩余特征與所有已選特征的最小條件互信息值最大的特征s[k]，min_inf[m]存放了第m個(gè)特征與已選子集中的特征具有的最小條件互信息。cond_inf(m,s[k])表示在已知特征s[k]的條件下，特征m與目標(biāo)類C的互信息，這也是該算法最核心的部分，所有互信息中概率的計(jì)算都是基于統(tǒng)計(jì)每種狀態(tài)值出現(xiàn)的次數(shù)。從實(shí)現(xiàn)過程可以看出，該算法的時(shí)間復(fù)雜度為O(M×K)。為了排除隨機(jī)性選擇初始值帶來的不確定性，需要將該算法執(zhí)行T次，假設(shè)每次迭代輸出的特征子集為St，若maxt[K]表示第t次選擇的子集中第K個(gè)條件互信息的最大值，我們認(rèn)為maxt[K]的值越大，該子集包含的最終信息量越多，則St為最優(yōu)特征子集。綜上所述，經(jīng)過T次迭代后，總的算法時(shí)間復(fù)雜度為O(M×K×T)。

3 基于LRCMI和SVM的混合入侵檢測(cè)特征選擇模型

3.1 基于LRCMI和SVM的混合特征選擇方法

按照采用的評(píng)價(jià)準(zhǔn)則類別的不同，特征選擇可分為兩種模式：Filter和Wrapper。Filter模式的特征選擇利用數(shù)據(jù)本身的概率關(guān)系或者相關(guān)性等作為子集的評(píng)價(jià)函數(shù)，而Wrapper則利用機(jī)器學(xué)習(xí)算法的正確率作為特征選擇的標(biāo)準(zhǔn)。通常情況下Filter特征選擇的速度比較快，但所選特征子集的分類精度不高。Wrapper特征選擇用到的分類算法復(fù)雜度高，選擇速度慢，其結(jié)果依賴于所用的分類算法，選取的特征子集通常有較高的分類精度。本文提出的隨機(jī)最小冗余條件互信息特征選擇算法屬于Filter模式，雖能選擇出具有更多分類信息的特征子集，但分類信息的多少與其分類能力并不是嚴(yán)格線性相關(guān)的[11]。為了選擇出具有較高分類精度的入侵檢測(cè)特征子集，我們?cè)O(shè)計(jì)了一種結(jié)合了隨機(jī)最小冗余條件互信息和支持向量機(jī)的混合入侵檢測(cè)特征選擇模型。由于支持向量機(jī)算法是一種高精度的分類算法，在入侵檢測(cè)問題上具有很好的識(shí)別性能，結(jié)合提出的最小冗余條件互信息進(jìn)行特征選擇，不僅能保留最大的分類信息量，還能選擇出精度較高的特征子集。具體的混合特征選擇算法流程如圖2所示。

圖2 基于LRCMI與SVM的混合入侵檢測(cè)特征選擇算法流程圖

我們用max[K]表示當(dāng)前最大的maxt[K]的值，Sbest表示迭代后篩選的最優(yōu)特征子集。從圖2可以看出，本文將入侵檢測(cè)特征選擇的過程主要分為三個(gè)模塊，1) 入侵檢測(cè)特征的初選，將選出的特征子集記為F；2) 利用基于最小冗余互信息的特征選擇算法構(gòu)建候選特征子集St；3) 將最優(yōu)選特征子集交給SVM分類器評(píng)估，選出具有最佳分類能力的特征子集Sbest。

3.2 基于LRCMI和SVM的混合入侵檢測(cè)特征選擇

(1) 入侵檢測(cè)特征初選

特征選擇是數(shù)據(jù)預(yù)處理的一個(gè)階段，用于選取一個(gè)訓(xùn)練學(xué)習(xí)機(jī)器的有效屬性子集，原始數(shù)據(jù)集通常包含了各種與檢測(cè)結(jié)果不相關(guān)的和冗余的屬性。為了能在允許的時(shí)間和計(jì)算代價(jià)之內(nèi)找出最優(yōu)的特征子集，先對(duì)原始特征進(jìn)行一次初選，去除與檢測(cè)結(jié)果相關(guān)性很小或者包含較少分類信息量的屬性，使特征集中的每一個(gè)特征都與檢測(cè)結(jié)果具有不同程度的相關(guān)性。因此，我們首先使用互信息作為入侵檢測(cè)特征初選的依據(jù)。

定義2對(duì)于特征Xi與入侵檢測(cè)目標(biāo)類C，其互信息可用下式表示：

(4)

互信息越大則表示該特征變量與類變量的互信息越高，其包含的分類信息就越多。設(shè)定閾值ε2，若I(Xi;C)≥ε2，則保留入侵檢測(cè)特征Xi。

定義3相關(guān)性分析能夠分析特征變量與類變量以及任意兩特征變量之間的相關(guān)性，特征變量Xi與Xk的線性相關(guān)系數(shù)可用下式表示：

(5)

這里的cov(Xi,Xk)是兩個(gè)變量的協(xié)方差，σXi,σXk是Xi與Xk的標(biāo)準(zhǔn)差。ρXi,Xk越大表明這兩變量之間的相關(guān)性就越大。設(shè)定閾值ε3，若ρXi,Xk≥ε3，則保留入侵檢測(cè)特征Xi。

相關(guān)性分析可以分析特征與類以及特征之間的線性相關(guān)性，本文在利用相關(guān)性分析時(shí)每一輪只比較當(dāng)前特征與剩余未選特征之間的線性相關(guān)性，滿足所有條件時(shí)，則該特征為可選特征。另外，為了保證在初選時(shí)不丟失可用信息，閾值設(shè)置時(shí)通常要求保留大部分?jǐn)?shù)據(jù)，因此，其閾值要求可盡量放寬松。綜上，按照定義1-定義3，逐一排查原始入侵檢測(cè)數(shù)據(jù)集中的特征變量，保留滿足條件的所有特征組成初始候選子集F，包含M個(gè)特征。

(2) 基于LRCMI和SVM的混合入侵檢測(cè)特征選擇算法描述

由于特征初選只是排除原始特征集中不具有分類信息以及特征之間存在近乎完全相關(guān)的冗余特征?，F(xiàn)實(shí)數(shù)據(jù)中，大部分特征之間都存在著一定程度的弱依賴性，且他們之間的分類信息也都有著或大或小的交集，幾乎很少有兩個(gè)完全獨(dú)立且都與目標(biāo)類相關(guān)度較高的特征，所以經(jīng)過初選的特征中也必然存在著大量冗余。本文給出的隨機(jī)最小冗余條件互信息特征選擇算法，可以在所有已選特征的分類信息已知的情況下，加入與目標(biāo)類有最大互信息的待選特征。同時(shí)為了避免陷入局部最優(yōu)解，使用隨機(jī)初始值的策略，這樣既保證了選擇結(jié)果可以擇優(yōu)而取，還能避免隨機(jī)性帶來的缺陷。入侵檢測(cè)選擇特征最終的目的是用于分類，使用支持向量機(jī)分類正確率評(píng)價(jià)特征子集，可以在保證分類精度的情況下，選擇出具有最多分類信息的最小特征子集。

由于入侵檢測(cè)數(shù)據(jù)中存在著連續(xù)數(shù)據(jù)，在將原始數(shù)據(jù)集進(jìn)行特征選擇之前，需要先對(duì)數(shù)據(jù)集預(yù)處理，將所有連續(xù)屬性的數(shù)據(jù)值離散化。去除比較嚴(yán)重的不完全數(shù)據(jù)記錄，對(duì)于缺少一兩個(gè)值的數(shù)據(jù)樣本采用平均值填補(bǔ)法，補(bǔ)全缺失的數(shù)據(jù)?；バ畔⒗昧烁怕式y(tǒng)計(jì)的基礎(chǔ)，為使所有狀態(tài)值的概率分布值更加精確，要保證有足夠的訓(xùn)練樣本。將所有的數(shù)據(jù)按照原始的統(tǒng)計(jì)規(guī)律分成三份，即訓(xùn)練集D0、測(cè)試集Dt、評(píng)估驗(yàn)證集Dv。具體的入侵檢測(cè)混合特征選擇算法描述如下：

1) 輸入預(yù)處理過的入侵檢測(cè)數(shù)據(jù)集D0、Dt、Dv，記初始入侵檢測(cè)特征向量為X，設(shè)置參數(shù)ε1、ε2、ε3、max[K]、T以及K的值。

2) 從第一個(gè)入侵檢測(cè)特征開始，計(jì)算H(X1)值，若H(X1)>ε1，則判斷I(X1,C)，若I(X1,C)>ε2，再計(jì)算X1與所有剩余特征的線性相關(guān)性，若它們的相關(guān)性ρ(X1,Xi)>ε3且I(X1,C)>I(Xi,C) ，則將特征X1保留到待選子集F，否則將其去除。

3) 依次按照第2)步，篩選出所有符合條件的入侵檢測(cè)特征，最終的待選子集F作為下一步的輸入，剩余特征總數(shù)為M。

4) 取部分Dt使用候選入侵檢測(cè)特征子集訓(xùn)練SVM，并用Dv測(cè)試該候選子集分類精度，記為γbest。Fort=1,2,…,T。

5) 隨機(jī)選取一個(gè)特征作為已選初始特征，加入St。

6) 按照最小冗余條件互信息準(zhǔn)則，即算法1，選取St的剩余K-1個(gè)特征，完成構(gòu)建入侵檢測(cè)特征子集St，第K次選取的最小條件互信息的值為maxt[K]，若maxt[K]大于max[K]，則更新max[K]的值并轉(zhuǎn)到第6步，否則轉(zhuǎn)到第4步。

8) 輸出Sbest以及γbest，結(jié)束。

4 實(shí)驗(yàn)及結(jié)論

為了驗(yàn)證算法的有效性，本文進(jìn)行了如下仿真實(shí)驗(yàn)，實(shí)驗(yàn)數(shù)據(jù)采用KDD Cup 1999的IDS數(shù)據(jù)庫[17]，并在開源數(shù)據(jù)分析軟件RStudio上完成。該數(shù)據(jù)庫的數(shù)據(jù)分布能很好地模擬真實(shí)環(huán)境，廣泛地用于對(duì)IDS日志數(shù)據(jù)進(jìn)行分析研究。KDD99共包含三種數(shù)據(jù)集：1) 全部數(shù)據(jù)集；2) 10%數(shù)據(jù)集；3) 帶攻擊標(biāo)記的數(shù)據(jù)集，常用于異常檢測(cè)分析。本次實(shí)驗(yàn)使用10%數(shù)據(jù)集，該數(shù)據(jù)集中每個(gè)樣本有41個(gè)輸入變量，包括9個(gè)基本連接特征、13個(gè)鏈接內(nèi)容特征和19個(gè)網(wǎng)絡(luò)流量特征。還包括1個(gè)響應(yīng)變量，響應(yīng)變量有Dos(拒絕服務(wù)供給)、Probe(端口監(jiān)視或掃描)、U2R(未授權(quán)的本地超級(jí)用戶特權(quán)訪問)、R2L(來自遠(yuǎn)程主機(jī)的未授權(quán)訪問)和Normal五種，共有494 020條記錄。為了更好地關(guān)注特征選擇的效果，本文對(duì)每個(gè)連接只取它是“Normal”還是“Attack”，即所有的入侵類型都?xì)w為“Attack”，這樣就變成了二分類問題。按原始數(shù)據(jù)分布的特征，將所有數(shù)據(jù)集分成3份，其中一個(gè)數(shù)據(jù)集進(jìn)行特征選擇訓(xùn)練，把該數(shù)據(jù)集上訓(xùn)練得到的次優(yōu)特征子集在驗(yàn)證集上進(jìn)行驗(yàn)證，然后將測(cè)試集分成5份，交叉測(cè)試檢測(cè)準(zhǔn)確率、誤檢率及漏檢率。實(shí)驗(yàn)硬件環(huán)境是AMD Phenom(tm) Ⅱ Processor 2.20 GHz，3.49 GB內(nèi)存，軟件環(huán)境是Win7，Java1.7，Matlab7.1，R3.2.1，實(shí)驗(yàn)中用到了R語言entropy.ChaoShen包、kernlab包以及RSNNS包，分別用于計(jì)算信息熵的值和訓(xùn)練SVM以及神經(jīng)網(wǎng)絡(luò)。為了達(dá)到最佳效果，實(shí)驗(yàn)中參數(shù)ε1、ε2、ε3、max[K]以及K均是通過前期不斷調(diào)整得到，根據(jù)最終的實(shí)驗(yàn)效果，設(shè)置ε1=9.27，ε2=9.05，ε3=0.96，max[K]=0，K=8。為了評(píng)估基于近似最小冗余互信息的入侵檢測(cè)特征選擇算法的性能，本文選用四個(gè)入侵檢測(cè)特征選擇常用的評(píng)價(jià)指標(biāo)：平均建模時(shí)間、平均分類精度、檢測(cè)率、誤報(bào)率。其中，檢測(cè)率TPR(true positive rate)=正確檢測(cè)的攻擊樣本數(shù)/總攻擊樣本數(shù)；誤檢率FPR(false positive rate)=被判攻擊樣本的正常數(shù)/總的正常樣本數(shù)；漏檢率MR(missing rate)=未被檢測(cè)到的攻擊樣本/總的攻擊樣本。

該實(shí)驗(yàn)共分為三部分，第一部分實(shí)驗(yàn)分析了本文所提算法及其他算法所選的特征子集，主要評(píng)價(jià)指標(biāo)為特征數(shù)和包含的重要特征，第二部分實(shí)驗(yàn)分析了LRCMI-SVM算法所選特征子集的入侵檢測(cè)性能，主要的評(píng)價(jià)指標(biāo)為誤檢率、漏檢率、檢測(cè)時(shí)間。第三部分實(shí)驗(yàn)分析了不同算法所選特征的入侵檢測(cè)性能以及運(yùn)行效率。

實(shí)驗(yàn)1針對(duì)入侵檢測(cè)數(shù)據(jù)集進(jìn)行特征選擇的算法有很多，如mRAR(最大相關(guān)最小冗余特征選擇)、NN(基于神經(jīng)網(wǎng)絡(luò))、IG-J48(基于信息熵和決策樹)、CFS-SVM(基于關(guān)聯(lián)規(guī)則和支持向量機(jī))等，結(jié)合以上四種算法以及本文的LRCMI-SVM(隨機(jī)最小冗余條件互信息與支持向量機(jī))五個(gè)特征選擇算法在KDD CUP-99中10%數(shù)據(jù)集上進(jìn)行篩選的結(jié)果如表1所示。在保證檢測(cè)準(zhǔn)確率的同時(shí)選擇的有用特征數(shù)越少，說明該特征選擇算法越有效。

表1 各種特征選擇算法選擇的特征子集

從表1的結(jié)果可以看出，入侵檢測(cè)日志數(shù)據(jù)中有幾個(gè)特征在以上算法的選擇結(jié)果中出現(xiàn)次數(shù)比較多，主要包括：src_bytes(源主機(jī)到目標(biāo)主機(jī)的數(shù)據(jù)字節(jié)數(shù))、count(過去兩秒內(nèi)與當(dāng)前連接具有相同目標(biāo)主機(jī)的連接數(shù))、service(目標(biāo)主機(jī)的網(wǎng)絡(luò)服務(wù)類型)等，說明他們對(duì)于甄別入侵行為有很重要的作用，特征選擇的目的就是發(fā)現(xiàn)像他們一樣的特征。本文提出的LRCMI-SVM算法選擇的特征子集也包含了這些，且該算法所選的子集數(shù)目也相對(duì)少。相比其他算法，說明本文提出的針對(duì)入侵檢測(cè)的特征選擇算法能夠有效去除特征中存在的冗余信息，去除相關(guān)性較高的特征屬性，選出包含信息量較高的最小的特征子集。

實(shí)驗(yàn)2該實(shí)驗(yàn)將10%數(shù)據(jù)集中的測(cè)試集隨機(jī)分成5×2份，分別使用R語言自帶的C4.5決策樹算法訓(xùn)練5×2個(gè)分類器，進(jìn)行5折交叉驗(yàn)證，得出特征選擇前后的平均誤檢率、平均漏檢率以及平均檢測(cè)時(shí)間。針對(duì)本文算法選出的特征子集與原始數(shù)據(jù)集全部特征的入侵檢測(cè)性能進(jìn)行的對(duì)比。實(shí)驗(yàn)結(jié)果如表2所示。

表2 特征選擇前后入侵檢測(cè)的檢測(cè)率、誤檢率與檢測(cè)時(shí)間

從表2中可以看出，使用本文提出的LRCMI-SVM算法進(jìn)行測(cè)試時(shí)，相比原始特征集具有更低的誤檢率和漏檢率，其分類精度得到了保證，可見在特征選擇過程中去除了影響檢測(cè)率的部分特征。該算法的檢測(cè)時(shí)間縮減了將近一半，有效地提高了入侵檢測(cè)的實(shí)時(shí)性，對(duì)于實(shí)時(shí)性要求較高的系統(tǒng)，該算法的性能更優(yōu)。

實(shí)驗(yàn)3在R語言中使用C4.5決策樹算法以及KDD CUP-99數(shù)據(jù)集中的測(cè)試集驗(yàn)證五種(mRAR(最大相關(guān)最小冗余特征選擇)、NN(基于神經(jīng)網(wǎng)絡(luò))、IG-J48(基于信息熵和決策樹)、CFS-SVM(基于關(guān)聯(lián)規(guī)則和支持向量機(jī))以及本文提出的LRCMI-SVM(最小冗余信息熵與支持向量機(jī)))算法所選特征子集進(jìn)行入侵檢測(cè)時(shí)的檢測(cè)率，并統(tǒng)計(jì)各個(gè)特征選擇算法的平均訓(xùn)練時(shí)間。見表3。

表3 不同特征選擇算法的檢測(cè)率和建模時(shí)間

從表3中可以看出，基于神經(jīng)網(wǎng)絡(luò)的特征選擇算法的訓(xùn)練效果最好，但其訓(xùn)練時(shí)間太久，難以應(yīng)對(duì)高維數(shù)據(jù)集的選擇過程。CFS-SVM的訓(xùn)練結(jié)果雖不如神經(jīng)網(wǎng)絡(luò)，但其訓(xùn)練時(shí)間明顯縮短。本文提出的算法的訓(xùn)練精度最接近神經(jīng)網(wǎng)絡(luò)，其訓(xùn)練所用時(shí)間也比CFS-SVM更短，在同時(shí)保證檢測(cè)率和算法運(yùn)行效率上，本文算法具有更優(yōu)的綜合性能。綜上，本文提出的算法不僅可以提高特征選擇的速度，所選特征還能比其他兩種wrapper算法保持更高的檢測(cè)率。

5 結(jié) 語

特征選擇是一種常用的選取有效屬性子集的方法，一個(gè)好的算法可以在較短的時(shí)間內(nèi)找到與目標(biāo)類較相關(guān)且冗余較小的特征子集。本文提出的基于隨機(jī)最小冗余條件互信息和SVM的混合特征選擇算法在保證特征中包含的攻擊信息最多的情況下，通過使用隨機(jī)初始值策略的最小冗余條件互信息準(zhǔn)則，選擇出包含信息量最多的特征子集。相比其他的混合特征選擇算法不僅提高了入侵檢測(cè)的檢測(cè)效率，還能保證所選特征子集具有較高的分類精度，較低的漏檢率以及誤檢率，能很好地應(yīng)用于構(gòu)建輕量級(jí)的入侵檢測(cè)系統(tǒng)。后期的工作重點(diǎn)主要放在了優(yōu)化評(píng)價(jià)函數(shù)以及搜索策略上，進(jìn)一步提高特征選擇的效率，通過設(shè)計(jì)一種并行化的特征選擇方案，使其可以處理大規(guī)模的入侵檢測(cè)數(shù)據(jù)。

[1] Mukheijee B,Heberlein L T,Levitt K N.Network intrusion detection[J].IEEE Network,1994,8(3):26-41.

[2] 陳友,程學(xué)旗,李洋,等.基于特征選擇的輕量級(jí)入侵檢測(cè)系統(tǒng)[J].軟件學(xué)報(bào),2007,18(7):1639-1651.

[3] Yu L,Liu H.Efficient Feature Selection via Analysis of Relevance and Redundancy[J].Journal of Machine Learning Research,2004,5(12):1205-1224.

[4] Sung A H,Mukkamala S.Identifying important features for intrusion detection using support vector machines and neural networks[C]//Applications and the Internet,2003.Proceedings.2003 Symposium on,2003:22-25.

[5] Park J S,Shazzad K M,Dong S K.Toward Modeling Lightweight Intrusion Detection System Through Correlation-Based Hybrid Feature Selection[J].Lecture Notes in Computer Science,2005,3822:279-289.

[6] 朱紅萍,鞏青歌,雷戰(zhàn)波.基于遺傳算法的入侵檢測(cè)特征選擇[J].計(jì)算機(jī)應(yīng)用研究,2012,29(4):1417-1419.

[7] Sun Z.Parallel Feature Selection Based on MapReduce[J].IEEE Transactions on Pattern Analysis & Machine Intelligence,2014,13(3):252-264.

[8] Peng H,Long F,Ding C.Feature Selection Based on Mutual Information:Criteria of Max-Dependency,Max-Relevance,and Min-Redundancy[J].IEEE Transactions on Pattern Analysis & Machine Intelligence,2005,27(8):1226-1238.

[9] Shen Kaiquan,Ong Chongjin,Li Xiaoping,et al.Feature selection via sensitivity analysis of SVM probabilistic outputs[J].Machine Learning,2008,70(1):1-20.

[10] Hall M A.Correlation-based Feature Selection for Discrete and Numeric Class Machine Learning[C].Seventeenth International Conference on Machine Learning,2000:359-366.

[11] Fleuret F.Fast Binary Feature Selection with Conditional Mutual Information[J].Journal of Machine Learning Research,2004,5(3):1531-1555.

[12] The Greedy Algorithm[M]//Graphs,Networks and Algorithms.Springer Berlin Heidelberg,2005.

[13] 裘國永,王娜,汪萬紫.基于互信息和遺傳算法的兩階段特征選擇方法[J].計(jì)算機(jī)應(yīng)用研究,2012,29(8):2903-2905.

[14] 劉素華,侯惠芳,李小霞.基于遺傳算法和模擬退火算法的特征選擇方法[J].計(jì)算機(jī)工程,2005,31(16):157-159.

[15] 王璐,邱桃榮,何妞,等.基于粗糙集和蟻群優(yōu)化算法的特征選擇方法[J].南京大學(xué)學(xué)報(bào)(自然科學(xué)),2010,46(5):487-493.

[16] Niu G.Feature Selection Optimization[M]//Data-Driven Technology for Engineering Systems Health Management.Springer Singapore,2016.

[17] KDD cup 1999 dataset[DB/OL].http://kdd.ics.uci.edu/ databases/kddcup99/kdd cup99. html.

FEATURESELECTIONOFINTRUSIONDETECTIONBASEDONRANDOMLEASTREDUNDANTCONDITIONALMUTUALINFORMATIONANDSVM

Ding Xuanxuan Guo Yuanbo

(PLAInformationEngineeringUniversity,Zhengzhou450001,Henan,China) (StateKeyLaboratoryofMathematicalEngineeringandAdvancedComputing,Wuxi214000,Jiangsu,China)

There are a lot of irrelevant and redundant attributes in intrusion detection logs, which seriously affect the detection of real-time. Most feature selection algorithms cannot take into account the correlation and the amount of information, and are easy to fall into the local optimal solution. To solve this problem, a hybrid intrusion detection feature selection method based on random minimum redundancy conditional mutual information and support vector machines (SVM) is proposed. Firstly, mutual information and correlation were used to eliminate redundant features without classification information and a high degree of correlation between features. Then, the random minimum redundancy condition mutual information criterion and SVM were used to select the optimal feature subset with the maximum classification information quantity, avoiding the local optimal solution to a certain extent. Our results show that it can get an optimal minimum feature subset effectively on condition of ensuring the intrusion detection classification accuracy.

Information entropy Mutual information SVM Feature selection Intrusion detection

2016-12-22。國家自然科學(xué)基金項(xiàng)目(61501515)。丁宣宣，碩士生，主研領(lǐng)域：數(shù)據(jù)挖掘與態(tài)勢(shì)感知。郭淵博，教授。

TP391

A

10.3969/j.issn.1000-386x.2017.11.054