◆程新黨 趙學(xué)武

（南陽師范學(xué)院軟件學(xué)院 河南473061）

基于雙極快速進(jìn)化特征選擇算法的異常入侵檢測

◆程新黨 趙學(xué)武

（南陽師范學(xué)院軟件學(xué)院 河南473061）

異常入侵檢測技術(shù)在入侵檢測系統(tǒng)中有著重要的地位，該技術(shù)依據(jù)用戶的正常行為模式來檢測未知攻擊。但由于網(wǎng)絡(luò)鏈接數(shù)據(jù)復(fù)雜多變的特性和冗余無關(guān)網(wǎng)絡(luò)鏈接屬性的干擾，時常導(dǎo)致現(xiàn)有異常檢測技術(shù)的失效。針對該問題，提出了一種新的雙極快速進(jìn)化算法，該算法在每一代解集的最差與最優(yōu)兩個極端分別引入最差反轉(zhuǎn)進(jìn)化和最優(yōu)迭代繁殖等搜索策略，改善算法的收斂速度與全局尋優(yōu)能力，然后將本算法與特征選擇相結(jié)合，快速選出最優(yōu)的網(wǎng)絡(luò)鏈接特征組合，并結(jié)合決策樹ID3算法構(gòu)造異常入侵檢測規(guī)則，在數(shù)據(jù)集KDD CUP99上的多項(xiàng)比較實(shí)驗(yàn)表明該算法能夠獲得較優(yōu)的特征組合，并取得了較高的檢測率與準(zhǔn)確率，同時具有較低的誤警率，為異常入侵檢測模型的設(shè)計提供了參考。

入侵檢測系統(tǒng)；快速進(jìn)化算法；決策樹；特征選擇；異常檢測

0 前言

隨著計算機(jī)技術(shù)和通信技術(shù)的發(fā)展，計算機(jī)網(wǎng)絡(luò)在社會的方方面面扮演著越來越重要的角，但是計算機(jī)和網(wǎng)絡(luò)的安全已經(jīng)成為人們急需面對的新難題，據(jù)統(tǒng)計，黑客入侵事件逐年增加，給個人和相關(guān)機(jī)構(gòu)造成了巨大的損失。作為網(wǎng)絡(luò)安全防御的主要手段之一，入侵檢測系統(tǒng)（Intrusion Detection System,IDS）可以檢測到多種攻擊和入侵行為，并發(fā)出報警信號。 目前常見的IDS可以分為異常檢測系統(tǒng)、誤用檢測系統(tǒng)或簽名檢測系統(tǒng)[1]。早期的入侵檢測技術(shù)主要利用預(yù)定義的已知入侵模式與目標(biāo)系統(tǒng)的特定行為進(jìn)行匹配來判斷是否有入侵事件發(fā)生，具有較高的正確率，但不能發(fā)現(xiàn)未知的攻擊模式，所以需要經(jīng)常更新特征庫以保證系統(tǒng)的檢測效果。而在異常檢測系統(tǒng)中，系統(tǒng)基于一定周期內(nèi)用戶的工作模式和網(wǎng)絡(luò)狀態(tài)，對網(wǎng)絡(luò)數(shù)據(jù)進(jìn)行分析將偏離正常行為的網(wǎng)絡(luò)鏈接判定為入侵事件，這種方法雖然可以發(fā)現(xiàn)未知的入侵攻擊，但具有較高的誤報率。

近年來，基于機(jī)器學(xué)習(xí)的異常入侵檢測技術(shù)得到較大的發(fā)展，研究者們運(yùn)用分類、聚類或者規(guī)則關(guān)聯(lián)等技術(shù)對入侵行為進(jìn)行分析挖掘，并建立了多種數(shù)學(xué)模型，已經(jīng)取得了較好的實(shí)際效果；但是由于用戶行為的多變性和復(fù)雜性，不論是分類還是聚類方法，在具體的工程實(shí)踐中都分別存在著一些問題，比如對初始值敏感，收斂速度慢，易陷入局部最優(yōu)等。針對這些問題，已經(jīng)有人提出了一些針對性的改進(jìn)算法和策略，如文獻(xiàn)[2，3，4]。其中Srinoy等人[2]將粗糙模糊聚類的方法應(yīng)用于冗余數(shù)據(jù)的消除，并使用粗糙集理論實(shí)現(xiàn)對正常異常行為的軟劃分；在文獻(xiàn)[3]中Denatious等人將聚類、分類以及關(guān)聯(lián)規(guī)則綜合應(yīng)用到入侵行為的檢測發(fā)現(xiàn)上；文獻(xiàn)[4]中 Mohanabharathi等人將信息增益率與k-means法結(jié)合起來用于無線網(wǎng)絡(luò)系統(tǒng)中行為屬性的特征選擇與入侵事件的判定。但隨著互聯(lián)網(wǎng)日漸融入人們的生活，網(wǎng)絡(luò)應(yīng)用日新月異、豐富多樣，這不僅導(dǎo)致了網(wǎng)絡(luò)數(shù)據(jù)量的與日俱增，同時對應(yīng)用層網(wǎng)絡(luò)數(shù)據(jù)信息的描述也需要較多的特征，但多數(shù)特征對入侵檢測來說可能是冗余的，因此龐大而復(fù)雜的數(shù)據(jù)信息導(dǎo)致入侵檢測效率低下，而檢測復(fù)雜度日益上升。現(xiàn)有的研究并不能很好地解決這些逐漸出現(xiàn)問題，最終導(dǎo)致了已經(jīng)部署的IDS出現(xiàn)了誤警率較高或檢測率較低的現(xiàn)象，已經(jīng)對整個社會造成了較大的損失。如何快速選出最佳的表示異常入侵行為的網(wǎng)絡(luò)鏈接特征組合，已經(jīng)成為提升IDS檢測效果的一個關(guān)鍵性問題?；诖?，本文提出了一種雙極性快速進(jìn)化特征選擇算法，旨在以較快的速度選擇出最能表征入侵行為的特征組合，再結(jié)合特定的分類算法來快速準(zhǔn)確地檢測到入侵行為，不僅能為IDS的相關(guān)技術(shù)的研究實(shí)施提供技術(shù)支持，而且該算法對組合優(yōu)化問題的研究也有一定的參考意義。

1 相關(guān)工作

在入侵檢測中，網(wǎng)絡(luò)連接行為通常需要多個特征（屬性）加以描述，例如在KDD CUP99 數(shù)據(jù)集中，每條數(shù)據(jù)共包含41個特征，研究表明這些特征中僅有部分與入侵行為密切相關(guān)，剩余部分特征對入侵檢測來說是冗余無關(guān)的，并嚴(yán)重影響著檢測的效率與準(zhǔn)確度。同時，數(shù)據(jù)集包含數(shù)據(jù)量巨大，如果直接進(jìn)行建模分析不僅運(yùn)算時間長，而且分類的精度不高。因此運(yùn)用特征選擇算法對數(shù)據(jù)進(jìn)行預(yù)處理不僅可以縮減運(yùn)算時間，而且可以提高分類的精度。在機(jī)器學(xué)習(xí)算法中，尤其在涉及高維特征空間時，數(shù)據(jù)降維操作已經(jīng)成為常用的數(shù)據(jù)預(yù)處理步驟。自從上世紀(jì)70年代，特征選擇技術(shù)被提出以來，已經(jīng)成為提升機(jī)器學(xué)習(xí)算法性能的一種重要技術(shù)途徑，并且被廣泛地應(yīng)用到多個領(lǐng)域，例如：分類、數(shù)據(jù)挖掘、目標(biāo)識別、入侵檢測等，被證明是一種從原始數(shù)據(jù)集中去除冗余無關(guān)特征的有效手段。在入侵檢測方面，唐成華等[5]利用信息增益算法對網(wǎng)絡(luò)攻擊鏈接數(shù)據(jù)的特征進(jìn)行排序，然后利用約登指數(shù)刪減數(shù)據(jù)集屬性，并取得了較好的聚類效果。Karimi-Nasab等人[6]提出了基于多對象遺傳算法（Multi-object genetic algorithm,MOGA）的隨機(jī)搜索策略；陳友等人[7]提出了一種基于遺傳算法（GA）和禁忌搜索相混合的搜索策略；Stein等人[8]提出一種稱為遺傳決策樹的模型，其使用遺傳算法選擇最優(yōu)特征子集，然后使用這些子集構(gòu)造C4.5決策樹；Lin和Ying等人[9]使用模擬退火算法（Simulated annealing algorithm）和支持向量機(jī)來搜索最優(yōu)特征子集；Mohanabharuthi等人[4]使用信息增益和k-Means相結(jié)合的方法進(jìn)行特征選擇。上述研究表明特征選擇雖然方法眾多，但主要集中在信息增益和智能算法兩大類上，而信息增益法需要人工決定最終需要選擇的特征數(shù)，同時信息增益最高的若干特征的組合不一定是最優(yōu)的，所以元智能啟發(fā)類算法在特征的選擇上具有先天優(yōu)勢。本文將運(yùn)用一種被稱為雙極性快速進(jìn)化算法（Bipolar Fast Evolutionary Algorithm BFEA）的特征選擇技術(shù)搜索最優(yōu)特征子集，并結(jié)合ID3決策樹進(jìn)行分類，在數(shù)據(jù)集KDD CUP99上的實(shí)驗(yàn)結(jié)果表明，該算法具有實(shí)現(xiàn)簡單，收斂速度快，無早熟現(xiàn)象等特點(diǎn)。

決策樹算法是Salzberg在1994年所提出的一個非常著名的機(jī)器學(xué)習(xí)算法，決策樹主要由節(jié)點(diǎn)（內(nèi)部節(jié)點(diǎn)）、?。ㄓ邢蜻叄┖腿~子（葉子節(jié)點(diǎn)）三部分組成，每個內(nèi)部節(jié)點(diǎn)與一個屬性（特征）對應(yīng)，根據(jù)樣本在該屬性上的取值范圍將樣本空間劃分為兩個或多個類別，每個從節(jié)點(diǎn)出發(fā)的弧使用對應(yīng)的屬性值進(jìn)行標(biāo)注，每個葉子節(jié)點(diǎn)代表一個類別。使用訓(xùn)練樣本遞歸地產(chǎn)生決策樹，直到不能繼續(xù)為止，該算法的更多描述以及變種參見文獻(xiàn)[11]等。決策樹構(gòu)造完成后，將每個測試樣本按照決策樹的結(jié)構(gòu)自頂而下進(jìn)行判決，直到進(jìn)入葉子節(jié)點(diǎn)，則將測試樣本標(biāo)注為該葉子節(jié)點(diǎn)對應(yīng)的類別。目前常用的決策樹算法有ID3和C4.5，本文采用ID3算法。

2 雙極快速進(jìn)化特征選擇算法

雙極性快速性進(jìn)化算法是針對離散型組合優(yōu)化問題所提出的一種高效迭代型進(jìn)化算法，但通過合適的編碼方案可以很容易應(yīng)用到連續(xù)型問題的求解上，其基本思想是針對進(jìn)化類算法中全局尋優(yōu)能力差、收斂速度慢等缺點(diǎn)，首先引入最差解反轉(zhuǎn)進(jìn)化策略來快速擴(kuò)大搜索范圍，即在每代解集中，親和度最差的若干解表明它們與最優(yōu)解偏離較大，一般的進(jìn)化類算法是丟棄這些解，而在本算法中則是該重新計算最差解補(bǔ)集的親和度，并與當(dāng)前最優(yōu)解比較決定去留；其次是在算法中增加了最優(yōu)解迭代繁殖進(jìn)化策略來細(xì)化局部搜索，即利用“優(yōu)則優(yōu)待”的原則允許最優(yōu)解一次產(chǎn)生多個相似子代，因?yàn)楫?dāng)前最優(yōu)解可能已經(jīng)非常接近全局最優(yōu)了，所以該策略可以用較少的迭代次數(shù)發(fā)現(xiàn)全局最優(yōu)解。實(shí)驗(yàn)表明本算法在收斂速度和尋優(yōu)能力上相對于其他類似算法都具有一定的優(yōu)勢。

本文將該算法應(yīng)用到IDS標(biāo)準(zhǔn)數(shù)據(jù)集KDD CUP99上進(jìn)行網(wǎng)絡(luò)數(shù)據(jù)鏈接的特征選擇，并使用決策樹（decision tree 簡稱 DT）ID3算法生成檢測規(guī)則，然后使用DT分類結(jié)果對算法求得的最優(yōu)特征子集進(jìn)行評估，親和度函數(shù)設(shè)計如下式（1），即約登指數(shù)。

其中DR為檢測率(Detection Rate)，AR為準(zhǔn)確率（Accuracy Rate），對本系統(tǒng)而言就是要求系統(tǒng)具有較高的報警率和較低的誤警率。

2.1 算法流程

設(shè)特征集合為 F={a1，a2，ai，…am}，m=|F|為集合大小，random()為（0，1）上均勻分布的隨機(jī)函數(shù)，G為最大迭代次數(shù)，f(s)為親和度函數(shù)，其流程圖如圖1所示，描述見下述的1-9個步驟；

圖1 BFEA算法流程圖

（1）對特征集合F采取不放回采樣R=random()*m次，則經(jīng)過R次采樣后，特征集F被劃分為集合FY和FN，F(xiàn)Y表示被選中的特征集合，F(xiàn)N表示F中未被選中的特征集合，有FN□F，F(xiàn)Y□F，且FN∩FY=□，記s=＜FY，F(xiàn)N＞為問題的一個解。

（2）上述步驟1)共執(zhí)行N+X次，取其中N個不同的解s作為問題的初始解集合，即對特征集F進(jìn)行了N次異構(gòu)劃分，記初始解集為 S=(s1， s2， … ，si， …， sN)。

（3）對集合S中的si使用式（1）計算親和度函數(shù)值vi=f(si)，然后依照vi對si進(jìn)行降序排序，將s1存入sbest，其親和度值存入vbest，取其中前 k=random()*N/2個進(jìn)行步驟 4)運(yùn)算， 取后 k’=random()*N/2 進(jìn)行步驟5)運(yùn)算，然后刪除剩余的N-k-k’個解，構(gòu)成新的解集S。

（4）對于集合S中的前k個解 si=＜，i=1,2,…k , 設(shè)

（7）如果sbest發(fā)生變化，且|sbest|＞1,則依次從集合sbest移除一個特征，構(gòu)成|sbest|個特征子集，遍歷每個子集，計算親和度如果 v’＞vbest, 則用 v’替換 vbest，對應(yīng)的記入臨時變量s’中，遍歷結(jié)束，如果存在v’＞vbest,則用對應(yīng)的替換 sbest，然后遞歸執(zhí)行該過程。

（8）使用步驟1)中的方法，隨機(jī)生成若干（小于N-k-k’）個新解，且與解集S中現(xiàn)有解不同，加入到解集S中，使解數(shù)量達(dá)到N。

（9）評估最優(yōu)解，如果符合終止條件或達(dá)到設(shè)定的最大迭代次數(shù)G，則輸出最優(yōu)解并結(jié)束，否則迭代次數(shù)加1，轉(zhuǎn)步驟3)繼續(xù)執(zhí)行。

2.2 算法分析

該快速進(jìn)化算法可以看作是遺傳算法GA或其他進(jìn)化算法的變種，也屬于進(jìn)化算法范疇，但對尋優(yōu)策略進(jìn)行了優(yōu)化。該算法步驟（1）和步驟（8）用來產(chǎn)生初始種群（解集），它們彼此不同且是異質(zhì)的，相當(dāng)于執(zhí)行全局隨機(jī)搜索，與其他進(jìn)化類算法相同；本算法中的步驟（3）和步驟（4）類似于GA算法中的交叉運(yùn)算，即最優(yōu)染色體的特征重組，而本算法采取的方法是單親進(jìn)化，具體措施是隨機(jī)替換最優(yōu)解中的若干特征，跳躍幅度和搜索范圍更大，而步驟（5）則是針對若干最差解采用完全反轉(zhuǎn)操作，進(jìn)一步擴(kuò)大全局搜索范圍。本算法的步（6）和步驟（7）用作局部尋優(yōu)，相當(dāng)于GA的變異操作，但與變異操作相比，該算法的特征變化幅度更小，局部搜索更細(xì)致。經(jīng)過上述搜索策略上的改善，不僅使算法收斂速度得以提高，而且最終解更接近全局最優(yōu)。因此本算法可以看作是一種進(jìn)化算法的改進(jìn)，其僅用單個父代來產(chǎn)生子代，研究表明（Schwefel 1995）這種使用單個親代產(chǎn)生單個子代的方式對搜索最為有效[10]。下面對該算法的時間復(fù)雜度做個簡要的分析?？疾焐鲜鰧λ惴鞒痰拿枋?，待求解的規(guī)模為m=|F|維，種群規(guī)模為N，解的編碼長度取大值m，最大進(jìn)化代數(shù)為G；算法中一次親和度計算時間為T，本例采用ID3算法，其時間為O(m×N×logN) 。算法中步驟（3）和（4）操作時間平均為(m/2) ×(N/4) × T ， 即O(m2×N2×logN)，同理步驟（5）時間也為O(m2×N2×logN)，而步驟6)僅需一次親和度計算時間T，分析算法步驟（7）其可能導(dǎo)致遞歸操作，時間復(fù)雜度為 O(m×logm)，因此一次迭代所需的時間為O(m2×N2×logN+ m×logm)，即O(m2×N2×logN); 其中時間O(m×N×logN) 由ID3算法消耗，而單獨(dú)考慮該BFEA算法，其時間復(fù)雜度僅為O(m×N)。

2.3 算法收斂性證明

設(shè)種群(解集)在第t次迭代共有解N個，分別記作s1t，s2t，…，

sNt， 設(shè)所求問題的最優(yōu)解記為 sbest，親和度函數(shù)記為 f(s)，則算法的收斂性可以定義如下：

定義2.1.

則稱算法以概率1收斂到最優(yōu)解。下面根據(jù)上述算法收斂性定義，給出定理2.1。

定理2.1. BFEA算法必然以概率1收斂到全局最優(yōu)解?，F(xiàn)證明如下：

證明：所有解構(gòu)成的解集記為S，其中任一解用s表示，有s∈S，對BFEA算法來說，任一解可以看作為一個特定的狀態(tài)，記算法的馬氏鏈狀態(tài)空間為G，其維數(shù)記為M=|G|=|S|，分析2.1節(jié)所述算法流程，發(fā)現(xiàn)每次迭代均是在最優(yōu)解的基礎(chǔ)上通過若干次隨機(jī)替換而產(chǎn)生下一代最優(yōu)解，即到達(dá)另一狀態(tài)。設(shè)pij為從狀態(tài) si到 sj的轉(zhuǎn)移概率，算法的最終目標(biāo)是尋找最優(yōu)解，所以 pij的取值共分為三種情況：

（1）隨機(jī)被選中的若干最優(yōu)解直接進(jìn)入下一代 ，即 pij=被選中的概率 。

（2）針對2.1 節(jié)算法流程的步驟 3)、4)、5)操作，若 f(si)＞ f(sj)，則進(jìn)入下一代，概率設(shè)為pij。

（3）若 f(si)＜ f(sj) ，則 pij=0；

將解按照親和度降序排列，則算法的有限狀態(tài)馬氏鏈一步轉(zhuǎn)移概率矩陣為：

在算法實(shí)現(xiàn)中，選擇每代最優(yōu)解中前k個，使之直接進(jìn)入子代解集，這些解的親和度值在上下兩代之間是相同的；對于那些親和度值不同的最優(yōu)值解上下代之間的狀態(tài)轉(zhuǎn)移則是單向的，即只能向親和度增大方向轉(zhuǎn)移。設(shè)：

即 Sxt為使第 t代解取親和度值為 f(St-best)的狀態(tài)集合。因此與最優(yōu)解集對應(yīng)的狀態(tài)集為一閉集。從狀態(tài)空間的任一狀態(tài)si開始，最終進(jìn)入上述閉集Sxt的概率稱為閉集Sxt對si的吸收率，而閉集對狀態(tài)si的吸收率為1 。一般情況下，問題的最優(yōu)解只有1個，則P11=1，P1j=0（j ）是以全局最優(yōu)解為超個體的狀態(tài)轉(zhuǎn)移概率，綜上所述可得：

P為齊次馬氏鏈的一步轉(zhuǎn)移矩陣，記t步轉(zhuǎn)移矩陣為Pt=P(t)，由齊次馬氏鏈呈現(xiàn)無后效性的特點(diǎn)可得：

因此可得：

至此，算法收斂性得證。

3 實(shí)驗(yàn)與結(jié)果分析

3.1 評估標(biāo)準(zhǔn)

本文采用常用的三個性能指標(biāo)對算法進(jìn)行評估，即檢測率（DR）、正確率（AR）和誤警率（FPR），定義分別如下式所示。

較高的檢測率和正確率，以及較低的誤警率代表較好的IDS性能，是所有IDS檢測算法設(shè)計與優(yōu)化的目標(biāo)。

3.2 實(shí)驗(yàn)數(shù)據(jù)集

本文實(shí)驗(yàn)數(shù)據(jù)采用KDD Cup99數(shù)據(jù)集，該數(shù)據(jù)集可以從站點(diǎn)http：//kdd.ics.uci.edu上下載。其中訓(xùn)練數(shù)據(jù)集包含大量數(shù)據(jù)記錄，每條鏈接記錄使用41個屬性（特征）進(jìn)行描述。在10%數(shù)據(jù)集中包含391458個拒絕服務(wù)類（DoS）攻擊，52個權(quán)限提升類（U2R）攻擊，4107條端口掃描探測類（Probe）攻擊，1126條遠(yuǎn)程登錄類（R2L）攻擊和97278條正常鏈接數(shù)據(jù)。這其中包含大量重復(fù)數(shù)據(jù)，為了更快速地訓(xùn)練模型，在實(shí)驗(yàn)中，首先剔除重復(fù)數(shù)據(jù)，將剩余數(shù)據(jù)按照攻擊類別各選部分到新的訓(xùn)練數(shù)據(jù)集，而測試數(shù)據(jù)則從KDD Cup99 Corrected（test）中隨機(jī)抽取，實(shí)驗(yàn)所用樣本分布情況如表1所示。實(shí)驗(yàn)數(shù)據(jù)集包含離散型和連續(xù)型屬性數(shù)據(jù)，為了簡化的決策樹的結(jié)構(gòu)，需要將連續(xù)型數(shù)據(jù)轉(zhuǎn)化為離散型數(shù)據(jù)，轉(zhuǎn)化方法采用文獻(xiàn)[12]中的經(jīng)典方法將連續(xù)數(shù)據(jù)劃分為2個區(qū)間：首先找出數(shù)據(jù)集中屬性為連續(xù)型的最大與最小值，分別記為max和min，取中值MP=(min+(max-min)/2)作為分割點(diǎn)進(jìn)行劃分即可。

表1樣本數(shù)據(jù)分布表

3.3 實(shí)驗(yàn)結(jié)果與分析

算法使用C#語言在Windows7 64位系統(tǒng)上設(shè)計實(shí)現(xiàn)，運(yùn)行環(huán)境為Intel i5-4200M CPU，2.5GHz，8GB RAM。設(shè)定算法最大迭代次數(shù)G=500，初始種群（解集）大小為50，算法終止條件為5代之間親和度增量δ＜0.005（特征數(shù)分別取5，10，..35，對算法稍微調(diào)整，丟棄長度不符的解即可）。然后分別針對每種情況，算法獨(dú)立運(yùn)行10次得到的平均結(jié)果如圖2、圖3和表2所示。對算法不做最優(yōu)解特征數(shù)限制，10次運(yùn)行后最優(yōu)解的平均長度為

20個特征數(shù)，與文獻(xiàn)[9]推薦最優(yōu)解21～22特征數(shù)近似一致。

表2 BFEA不同特征長度下的FPR/DR/AR/f(s)值

圖2 特征數(shù)與DR、AR的關(guān)系圖

表2的結(jié)果列出了算法在給定特征數(shù)的情況下檢測率、準(zhǔn)確率、誤警率以及對應(yīng)的親和度函數(shù)值，圖2則是它們之間的變化趨勢圖。我們可以很直觀的看出隨著BFEA算法對樣本數(shù)據(jù)特征的選擇與優(yōu)化組合，不論是檢測率、還是準(zhǔn)確率都隨著特征數(shù)的減少而逐漸增大，當(dāng)特征數(shù)為20時基本上達(dá)到峰值，而準(zhǔn)確率在特征數(shù)為 10時達(dá)到最大值，但此時檢測率并非最大。從圖 2還可以看出對KDD CUP99數(shù)據(jù)集來說，41個特征中冗余無關(guān)特征項(xiàng)在一半以上，體現(xiàn)出了特征選擇的必要性。

圖3 特征數(shù)與誤警率的關(guān)系圖

圖4 ROC曲線圖

分析圖3發(fā)現(xiàn)誤警率在特征數(shù)為30個時達(dá)到最低，但配合圖2，發(fā)現(xiàn)該點(diǎn)對應(yīng)的檢測率和準(zhǔn)確率都較低。分析圖4所示的ROC曲線圖發(fā)現(xiàn)特征數(shù)目為20時效果最好，有著最高的檢測率和相對較低的誤警率，結(jié)合表2特征數(shù)目為20時恰好對應(yīng)著最高親和度值。但在實(shí)際設(shè)計IDS系統(tǒng)時，特征數(shù)的選擇可以根據(jù)IDS的檢測速度與FPR，DR的實(shí)際需求在20，15，10，5之間做出權(quán)衡，因此本文的研究對IDS開發(fā)設(shè)計具有一定的指導(dǎo)意義。

圖5 三種算法在不同特征數(shù)時的綜合性能比較

圖 6 三種算法收斂性能比較

圖5是三種不同算法的比較，他們分別是BFEA，IG（信息增益）、GA（遺傳算法），實(shí)驗(yàn)分別用這三種算法在特征數(shù) 10，15，20個的情況下進(jìn)行綜合性能比較，發(fā)現(xiàn)特征數(shù)較少時IG方法最優(yōu)，這表明在特征數(shù)目有嚴(yán)格要求的系統(tǒng)中，使用IG法可以取得最優(yōu)的效果，但隨著特征數(shù)的增加，智能算法的優(yōu)勢逐漸明顯，即智能算法通過多次迭代，可以找出全局最優(yōu)的組合。

對算法的限制特征數(shù)目，并將最大迭代次數(shù)G設(shè)為500，取5代之間親和度增大量δ＜0.005時為算法的終止條件， 比較GA算法、BFEA和文獻(xiàn)[9]提出的SA-SVM在本數(shù)據(jù)集上的收斂速度，實(shí)驗(yàn)結(jié)果如圖6所示。結(jié)果表明，BFEA算法在進(jìn)化代數(shù)較少時，與另外兩種算法相差不大，但隨著進(jìn)化代數(shù)的增加，BFEA收斂速度優(yōu)勢逐漸體現(xiàn)，觀察三種算法在較高代數(shù)的表現(xiàn)，BFEA有逐漸加快的趨勢。

4 結(jié)論與后續(xù)研究

本文提出了一種新的快速智能進(jìn)化類特征選擇算法，該算法采用一對一進(jìn)化，最差解逆轉(zhuǎn)進(jìn)化，最優(yōu)解迭代小振幅繁殖進(jìn)化等一系列策略來快速精確地搜索全局最優(yōu)解。然后我們將該算法與ID3決策樹相結(jié)合應(yīng)用到異常入侵檢測系統(tǒng)中；針對特征復(fù)雜多樣（41個特征）的較大規(guī)模樣本數(shù)據(jù)（103以上）進(jìn)行特征選擇，并使用 ID3算法生成決策規(guī)則進(jìn)行異常入侵檢測實(shí)驗(yàn)，在KDD CUP99上的實(shí)驗(yàn)結(jié)果取得了較高檢測率和較低的誤警率，證明了該算法相對于其他算法的收斂速度以及求解精度上的優(yōu)勢。此外，本算法不僅可以應(yīng)用于特征選擇這種離散型的最優(yōu)化組合問題的求解，而且使用合適的編碼方案本算法完全可以應(yīng)用到函數(shù)優(yōu)化領(lǐng)域，這也是我們下一步將要研究的一個內(nèi)容。

[1]Liao H J，Lin C H R，Lin Y C，et al． Review：Intrusion detection system：A comprehensive review．Journal of Network &Computer Applications，2013．

[2]Srinoy S，Kurutach W，Chimphlee W，et al．Intrusion detection via independent component analysis based on rough fuzzy．Wseas Transactions on Computers，2006．

[3]Denatious D K,John A．urvey on data mining techniques to enhance intrusion detection．International Conference on Computer Communication and Informatics．IEEE，2012．

[4]Mohanabharathi R,Kalaikumaran T,KarthiS． Feature selection for wireless instrusion detection system using filterandwrappermodel．InternationalJournal of Modern EngineeringResearch，2012．

[5]唐成華， 劉鵬程， 湯申生．基于特征選擇的模糊聚類異常入侵行為檢測．計算機(jī)研究與發(fā)展，2015．

[6]Karimi-Nasab M,Konstantaras I．A random search heuristic for a multi-objective production planning． Computers & Industrial Engineering，2012．

[7]陳友， 沈華偉， 李洋．一種高效的面向輕量級入侵檢測系統(tǒng)的特征選擇算法．計算機(jī)學(xué)報，2007．

[8]Stein G,Chen B,Wu A S,et al．Decision tree classifier for network intrusion detection with GA-based feature selection．Southeast Regional Conference． Kennesaw ，Georgia,Alabama,Usa，2005．

[9]Lin S W,Ying K C,Lee C Y,et al．An intelligent algorithm with feature selection and decision rules applied to anomaly intrusion detection．Applied Soft Computing，2012．

[10]Schwefel H P P．Evolution and Optimum Seeking： The Sixth Generation．John Wiley & Sons,Inc，1995．

[11]潘大勝， 屈遲文．一種改進(jìn) ID3型決策樹挖掘算法．華僑大學(xué)學(xué)報：自然科學(xué)版，2016．

[12]Anusha K，Sathiyamoorthy E．Comparative study for feature selection algorithms in intrusion detection system．Automatic Control and Computer Sciences，2016．

國家自然科學(xué)基金項(xiàng)目（61401242）、河南省基礎(chǔ)與前沿技術(shù)研究項(xiàng)目（142300410396）資助。