一種粗糙集遺傳算法在入侵檢測中的應(yīng)用*

李鋒

（廣東交通職業(yè)技術(shù)學(xué)院，廣東 廣州 510650）

隨著信息技術(shù)和網(wǎng)絡(luò)的發(fā)展及應(yīng)用，安全問題日益突出。入侵檢測系統(tǒng)作為繼防火墻后第二道安全防線，已成為保障網(wǎng)絡(luò)安全的重要核心技術(shù)[1]。傳統(tǒng)基于聚類的檢測方法對數(shù)據(jù)輸入順序敏感，需要事先指定聚類數(shù)目等，造成聚類結(jié)果不理想，難以形成入侵特征，并且收斂速度慢，檢測率不高。本文提出一種基于粗糙集的遺傳算法并應(yīng)用于入侵檢測系統(tǒng)之中，通過粗糙集屬性精簡運(yùn)算，降低算法時(shí)空復(fù)雜度。

1 入侵檢測系統(tǒng)及其分類

1.1 入侵檢測系統(tǒng)

入侵檢測系統(tǒng)是一種主動(dòng)防御體系，它從計(jì)算機(jī)系統(tǒng)或網(wǎng)絡(luò)環(huán)境中采集分析數(shù)據(jù)，通過檢測引擎判斷可疑攻擊和異常事件，在計(jì)算機(jī)網(wǎng)絡(luò)和系統(tǒng)受到危害之前攔截特征行為攻擊[2]。系統(tǒng)遭受入侵后，IDS能將收集到的入侵行為和相關(guān)信息納入知識(shí)庫，通過主動(dòng)學(xué)習(xí)方式避免重復(fù)或類似攻擊，有效彌補(bǔ)防火墻被動(dòng)防御的不足。

1.2 入侵檢測分類

入侵檢測系統(tǒng)根據(jù)檢測技術(shù)可以為分特征檢測和異常檢兩類。特征檢測是通過監(jiān)視特定活動(dòng)并與預(yù)先所設(shè)置的模式進(jìn)行匹配來檢測入侵[2]。這種利用特征庫檢測已知入侵行為的方法檢測率高，速度快，并且對檢測結(jié)果有明確的處理參照，但是不能檢測未知攻擊，很難將具體入侵手段抽象成知識(shí)特征。異常檢測是基于系統(tǒng)或用戶的正常行為模式檢測入侵。該方法首先建立用戶正常行為模式，當(dāng)系統(tǒng)運(yùn)行時(shí)將實(shí)時(shí)行為與正常行為模式進(jìn)行匹配，一旦發(fā)生顯著偏離即認(rèn)為是入侵[2]。異常檢測方式與系統(tǒng)環(huán)境無關(guān)，通用性較好，可以檢測未知攻擊和潛在威脅，但需要對每個(gè)戶行為作全面描述，兼之個(gè)體行為的不確定性和獨(dú)特性導(dǎo)致算法復(fù)雜，檢測速度緩慢，漏報(bào)、誤報(bào)率較高。

2 粗糙集理論

粗糙集理論是處理不精確、不確定和不完整數(shù)據(jù)的數(shù)學(xué)理論，能夠?qū)Σ灰恢?、不完整、不完善信息提煉?nèi)在特征，揭示隱含規(guī)律。

粗糙集理論可以對決策表的屬性進(jìn)行約簡，以便提高分類性能，獲取潛在規(guī)則。對于任意決策表，不是每個(gè)屬性對分類決策表的分類能力都有效，因此，在決策表分類能力不變的情況下，刪掉冗余的條件或者決策屬性，可以得到相對簡單、易理解、易操作的決策表[3]。通過粗糙集理論對決策表屬性進(jìn)行約簡，有利于過濾典型分類屬性，形成新的決策表。通過約簡決策表中的無關(guān)屬性可以有效降低計(jì)算的時(shí)空復(fù)雜度，加速算法收斂。粗糙集理論如下。

表1給出一個(gè)簡單的決策系統(tǒng)，包含 a、b、c、d 4個(gè)條件屬性和一個(gè)決策屬性e，隸屬于8個(gè)目標(biāo)對象。

表1 決策系統(tǒng)

令X?U，在屬性集合P中用P上近似和P下近似對集合X進(jìn)行近似分類，分別用和表示P的上下近似值，表示如下：

（（X），（X））所在區(qū)間稱為粗糙集，如圖 1 所示。圖中每個(gè)方格表示一個(gè)等價(jià)類，通過等價(jià)類可以構(gòu)建集合X的上下近似區(qū)域，位于P下近似內(nèi)的等價(jià)類可以確定它們屬于集合X。

圖1 粗糙集示意圖

令P和Q是論域U中的等價(jià)關(guān)系，Q的P正域記為POSP（Q），負(fù)域?yàn)?NEGP（Q），邊界域?yàn)?BNDP（Q），有如下關(guān)系：

根據(jù)表1 決策系統(tǒng)，令P={b，c}，令Q={e}，按式（2）分別可以算出{e}的{b，c}正域、負(fù)域和邊界域：

從計(jì)算結(jié)果可以得出，對象 3、4、6能夠被{b，c}劃分為{e}所確定的類別，分別是R、S和 T，而其他對象不能明確地分類，因?yàn)閧b，c}對其對象不可分辨。

3 遺傳算法

遺傳算法 GA（Genetic Algorithms）源于達(dá)爾文的進(jìn)化論和孟德爾、摩根的遺傳學(xué)理論，由美國John Holland教授于20世紀(jì)60年代末提出，模擬生物遺傳機(jī)制“適者生存、優(yōu)勝劣汰”。遺傳算法操作對象是一群二進(jìn)制串，稱為染色體或種群，每個(gè)染色體都對應(yīng)于問題的一個(gè)解。從初始種群出發(fā)，采用基于適應(yīng)度比例的選擇策略在當(dāng)前種群中選擇個(gè)體，通過交叉選擇和變異操作產(chǎn)生新一代適應(yīng)度更高的染色體，重復(fù)上述繁衍進(jìn)化過程直到收斂到一個(gè)最合適的染色體上，從而找出問題的最優(yōu)解。遺傳算法擁有卓越的智能學(xué)習(xí)效率和自適應(yīng)性，近年來應(yīng)用于故障診斷、行為仿真和入侵檢測等領(lǐng)域。

決定遺傳算法性能的3個(gè)參數(shù)分別為群體大小pop、交叉概率pc和變異概率pm。群體大小pop太小時(shí)難以找出最優(yōu)解，太大則增加收斂時(shí)間；交叉概率pc太小時(shí)難以向前搜索，太大則容易破壞高適應(yīng)值的結(jié)構(gòu)；變異概率pm太小難以產(chǎn)生新的基因結(jié)構(gòu)，太大使遺傳算法成了單純的隨機(jī)搜索。

4 一種基于粗糙集遺傳算法

粗糙集理論和遺傳算法各有優(yōu)勢。粗糙集適用于主動(dòng)學(xué)習(xí)模式，通過約簡高維數(shù)據(jù)屬性維數(shù)降低算法時(shí)空復(fù)雜度。而遺傳算法處理數(shù)據(jù)量不大時(shí)具有良好的收斂性和魯棒性，但在處理海量數(shù)據(jù)時(shí)，特別是當(dāng)處理高維數(shù)據(jù)時(shí)，參數(shù)難以界定，易出現(xiàn)染色體的變異交叉操作使得算法經(jīng)高次迭代繁衍仍無法收斂的問題。

本文將粗糙集約簡原理與遺傳算法進(jìn)行整合，通過自適應(yīng)學(xué)習(xí)方式為入侵檢測系統(tǒng)提供行為特征?；舅枷胧峭ㄟ^粗糙集約簡策略先過濾數(shù)據(jù)流量的無關(guān)屬性，然后對處理后數(shù)據(jù)采用結(jié)合鄰域思想進(jìn)行分類，為遺傳算法初始化種群，并保證篩選樣本的穩(wěn)定性和典型性，避免遺傳算法處理數(shù)據(jù)量過大難以收斂的問題，最后由遺傳算法迭代完成入侵行為特征的提煉和描述。

4.1 算法思想和流程

粗糙集的屬性約簡原理適合于處理精確數(shù)據(jù)，進(jìn)行數(shù)據(jù)知識(shí)分類與獲取，同時(shí)對決策分析進(jìn)行輔助。經(jīng)過粗糙集屬性約簡后的系統(tǒng)，屬性的減少降低了計(jì)算的復(fù)雜性，但仍能夠保持相同的決策要求和效果。遺傳算法對數(shù)據(jù)特征進(jìn)行選擇和優(yōu)化建立在選擇合適的適應(yīng)度函數(shù)以及合理進(jìn)行選擇、交叉和變異的基礎(chǔ)上。

另外在遺傳算法中，交叉變異算子作用是將群體中優(yōu)良個(gè)體遺傳到下一代，加速算法的收斂速度，并增加和維持群體多樣性，以免陷入局部最優(yōu)解的問題。但是傳統(tǒng)算法中，交叉變異算子以一個(gè)極小概率隨機(jī)改變?nèi)旧w某些字位，隨意性和任意性影響算法的收斂速度。本文再次利用粗糙集約簡屬性，將優(yōu)異個(gè)體朝重要屬性加速變異，并將其基因繁衍給下一代個(gè)體，以此改善遺傳算法進(jìn)行隨機(jī)選擇的不足，優(yōu)化算法收斂速度。算法流程如圖2所示。

4.2 算法實(shí)現(xiàn)步驟

（1）對網(wǎng)絡(luò)流量進(jìn)行二進(jìn)制編碼。

（2）用粗糙集理論尋找重要屬性。

圖2 新算法流程圖

其中，γ（X）表示屬性子集B對屬性X的依賴度。

②若B?A滿足 γB（X）=γA（X），稱B是 A 的一個(gè)約簡，記為 redx（A）。

③所有約簡子集的交集，記作：

在分類方法中，鄰域作為劃分類別的判別標(biāo)準(zhǔn)。

④對于X上的任意對象Xi，其鄰域表示為：δ（Xi）={X|Δ（X，Xi）≤δ}且 δ≥0，δ（Xi）稱為Xi的鄰域粒子。其中Δ是一個(gè)度量函數(shù)，它滿足對于任意的Xi、Xj和Xk，重要屬性需滿足以下條件：

（3）初始化種群。屬性占有數(shù)為M的染色體作為初代種群，產(chǎn)生初始種群N={N1，N2，…，Ni}，適應(yīng)度分別為N1，N2，…，Ni。

（4）計(jì)算平均適應(yīng)度為：

（5）適應(yīng)度函數(shù)的選擇：

其中，|A|是原始數(shù)據(jù)集屬性個(gè)數(shù)；|B|是遺傳算法中染色體二進(jìn)制串中的“1”的個(gè)數(shù)，即屬性占有數(shù)；Hr（B，s）為染色體命中率。

（6）選取大于平均適應(yīng)度的染色體個(gè)體是正常個(gè)體，設(shè)異常個(gè)體適應(yīng)度為A，正常個(gè)體適應(yīng)度為B，將適應(yīng)度函數(shù)定義為{A，B}兩類。

（7）根據(jù)步驟（2）過濾的屬性構(gòu)建信息數(shù)據(jù)表，其中，N={N1，N2，…，Ni}為 論域，Ni={X1，X2，X3，…，Xi}表 示第i條染色體；Xi表示第i種基因，即網(wǎng)絡(luò)中的位置為i的網(wǎng)絡(luò)連接數(shù)據(jù)；C為條件屬性集；D為決策屬性。

（8）以概率Pm對染色體依照信息數(shù)據(jù)表中的重要屬性進(jìn)行變異操作。

（9）把經(jīng)過遺傳算法迭代收斂后得到的染色體都放入池中，重新計(jì)算染色體適應(yīng)度值，將滿足重要屬性的優(yōu)良特征加入入侵特征庫，并以此檢測攻擊行為。

5 實(shí)驗(yàn)測試

5.1 新算法檢測率測試

新算法對基核函數(shù)的3個(gè)參數(shù)和NIDS試驗(yàn)數(shù)據(jù)的32個(gè)特征進(jìn)行測試。編碼方式采用n位參數(shù)編碼加上32位的特征編碼，組成64位聯(lián)合優(yōu)化編碼?；旌蟽?yōu)化中遺傳算法參數(shù)設(shè)置如下：初始化群體大小為300，最大遺傳代數(shù)為2 000，變異概率為0.25，交叉概率為0.92，參數(shù)測試結(jié)果如表 2所示。

表2 新算法參數(shù)測試

5.2 新算法在入侵檢測中的測試

本文數(shù)據(jù)集取自KDD99數(shù)據(jù)訓(xùn)練樣本集中的513 021個(gè)樣本，每個(gè)樣本包括41個(gè)條件屬性，1個(gè)決策屬性，其中有34個(gè)屬性值是數(shù)值類型，4個(gè)屬性值是二元變量類型，其余4個(gè)屬性值為標(biāo)稱類型[4]。分別從該數(shù)據(jù)集中分別選取5 000和10 000個(gè)數(shù)據(jù)為訓(xùn)練樣本，經(jīng)MATLAB 7.0處理工具將標(biāo)稱類型數(shù)字化。為驗(yàn)證新算法的有效性，本文采取表2中的新參數(shù)，并與遺傳算法（GA）、遺傳算法改進(jìn)支持向量機(jī)（GA-SVM）進(jìn)行比較[5-12]，實(shí)驗(yàn)結(jié)果如表3所示。

表3 3種算法測試數(shù)據(jù)表

新算法通過粗糙集理論約簡屬性，一方面為遺傳算法提供初始化種群，減少訓(xùn)練時(shí)間；另一方面可避免隨機(jī)變異造成的緩慢收斂，減少算法時(shí)空復(fù)雜度，隨著樣本的增多，新算法在訓(xùn)練時(shí)間上更具優(yōu)勢。在檢測精度和檢測率方面，新算法有效去除無用樣本和冗余屬性，檢測更為方便快捷，檢測精度和檢測率都有不錯(cuò)表現(xiàn)。

5.3 個(gè)體適應(yīng)度和迭代次數(shù)測試

新算法個(gè)體適應(yīng)度明顯優(yōu)于其余兩種算法。新算法利用粗糙集約簡屬性，將優(yōu)異個(gè)體朝重要屬性加速變異，并將其基因繁衍給下一代個(gè)體，使得個(gè)體適應(yīng)度更高，新算法在第640次迭代已趨于收斂，如圖3所示。而其余兩種算法由于變異的隨機(jī)性和任意性，適應(yīng)度不高，分別在經(jīng)760次和740次迭代才趨于收斂。

圖3 個(gè)體適應(yīng)度和迭代次數(shù)測試圖

5.4 種群占重要屬性比例趨勢

新算法在變異操作中將優(yōu)異個(gè)體朝重要屬性加速變異并繁衍給下一代個(gè)體，種群占重要屬性比例在500次迭代后呈指數(shù)上升，在630次迭代達(dá)到峰值，如圖4所示，測試結(jié)果與圖3數(shù)據(jù)相吻合。其余兩種算法由于變異操作的不確定性，種群占重要屬性比例在800次迭代前幾乎呈線性關(guān)系，并且達(dá)不到峰值，這表明新算法能切實(shí)提高個(gè)體適應(yīng)度，加快向優(yōu)異群體變異速度，保持物種優(yōu)勢。

圖4 種群占重要屬性比例圖

本文在研究粗糙集和遺傳算法的理論基礎(chǔ)上，提出一種基于粗糙集的遺傳算法，通過粗糙集屬性精簡遺傳算法種群，并在變異操作中將優(yōu)異個(gè)體朝重要屬性加速變異，降低算法時(shí)空復(fù)雜度。通過算法對比和實(shí)驗(yàn)分析，本文提出的新算法在提高網(wǎng)絡(luò)入侵檢測速度和準(zhǔn)確率方面是有效的、可靠的和可行的，為網(wǎng)絡(luò)安全信息建設(shè)提供強(qiáng)有力的保障。

[1]HOFMEYR S A，F(xiàn)ORREST S.Architecture for an artificial immune system[J].Evolutionary Computation Journal， 2000，8（4）：443-473.

[2]TSUI J B.Fundamentals of global positioning system receivers：a software approach[M].New York： Wiley， 2000.

[3]HOFMEYR S，F(xiàn)ORREST S.Architecture for an artificial immune system[J].Evolutionary Computation， 2000，8（4）：443-473.

[4]TARAKANOV A，DASGUPTA D.A formal model of an artificial immune system[J].BioSystems， 2000，55（55）：151-158.

[5]BEHDINAN N A K，F(xiàn)AWAZ Z.Applicability and viability ofa GA based finite elementanalysis architecture for structural design optimization[J].Computers and Structures，2003，81（22-23）：2259-2271.

[6]MIDDLEMISS M，DICK G.Feature selection of intrusion detection data using a hybrid genetic algorithm/KNN approach[C].Design and Application of Hybrid Intelligent Systems， IOS Press Amsterdam，2003：519-527.

[7]KWON Y， KWON S， JIN S， et al.Convergence enhanced genetic algorithm with successive zooming method for solving continuousoptimization problems[J].Computers and Structures，2003， 81 （17） ：1715-1725.

[8]HUSSEIN O，SAADAWI T.Ant routing algorithm for mobile ad-hoc networks （ARAMA）[C].Proceedings of the 2003 IEEE International Conference on Performance， Computing，and Communications， 2003：281-290.

[9]ONDREJ HRSTKA，ANNA KUCEROVA.Improvements of real coded genetic algorithms based on differential operators preventing premature convergence[J].Advances in Engineering Software， 2004（35）：237-246.

[10]KABREDE H，HENTSCHKE R.Improved genetic algorithm for global optimization and its application to sodium chloride clusters[J].Journal of Physical Chemistry B， 2002，106 （39） ：10089-10095.

[11]HEISSENB U M，BRAUN T.Ants based routing in large scale mobile ad-hoc networks[C].Proceedings of the 13th ITG/GI-Fachta-gung Kommunikation Inverteilten System（KiVS2003）， 2003：181-190.

[12]TIMMISJ， NEALM， HUNT J.Anartificialimmune system for data analysis[J].BioSystems， 2000，55，（55）：143-150.