一種粗糙集遺傳算法在入侵檢測中的應用*

李鋒

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

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

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

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

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

1.2 入侵檢測分類

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

2 粗糙集理論

粗糙集理論是處理不精確、不確定和不完整數(shù)據(jù)的數(shù)學理論，能夠對不一致、不完整、不完善信息提煉內在特征，揭示隱含規(guī)律。

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

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

表1 決策系統(tǒng)

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

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

圖1 粗糙集示意圖

令P和Q是論域U中的等價關系，Q的P正域記為POSP（Q），負域為 NEGP（Q），邊界域為 BNDP（Q），有如下關系：

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

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

3 遺傳算法

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

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

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

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

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

4.1 算法思想和流程

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

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

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

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

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

圖2 新算法流程圖

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

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

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

在分類方法中，鄰域作為劃分類別的判別標準。

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

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

（4）計算平均適應度為：

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

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

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

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

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

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

5 實驗測試

5.1 新算法檢測率測試

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

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

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

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

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

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

5.3 個體適應度和迭代次數(shù)測試

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

圖3 個體適應度和迭代次數(shù)測試圖

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

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

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

本文在研究粗糙集和遺傳算法的理論基礎上，提出一種基于粗糙集的遺傳算法，通過粗糙集屬性精簡遺傳算法種群，并在變異操作中將優(yōu)異個體朝重要屬性加速變異，降低算法時空復雜度。通過算法對比和實驗分析，本文提出的新算法在提高網(wǎng)絡入侵檢測速度和準確率方面是有效的、可靠的和可行的，為網(wǎ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.