摘  要： 分析了目前入侵檢測系統(tǒng)運行機制和不足,，提出了一種基于粗糙集的遺傳算法，通過粗糙集屬性精簡遺傳算法種群,，并在變異操作中將優(yōu)異個體朝重要屬性加速變異,，降低算法時空復雜度。通過實驗驗證,，該算法收斂速度快,，檢測率高，能很好地應用于目前入侵檢測系統(tǒng)之中,。
關(guān)鍵詞： 入侵檢測,；粗糙集；遺傳算法,；屬性

    隨著信息技術(shù)和網(wǎng)絡(luò)的發(fā)展及應用,，安全問題日益突出。入侵檢測系統(tǒng)作為繼防火墻后第二道安全防線,，已成為保障網(wǎng)絡(luò)安全的重要核心技術(shù)[1],。傳統(tǒng)基于聚類的檢測方法對數(shù)據(jù)輸入順序敏感，需要事先指定聚類數(shù)目等,，造成聚類結(jié)果不理想,，難以形成入侵特征，并且收斂速度慢,，檢測率不高,。本文提出一種基于粗糙集的遺傳算法并應用于入侵檢測系統(tǒng)之中，通過粗糙集屬性精簡運算,，降低算法時空復雜度,。
1 入侵檢測系統(tǒng)及其分類
1.1 入侵檢測系統(tǒng)
    入侵檢測系統(tǒng)是一種主動防御體系，它從計算機系統(tǒng)或網(wǎng)絡(luò)環(huán)境中采集分析數(shù)據(jù),，通過檢測引擎判斷可疑攻擊和異常事件,，在計算機網(wǎng)絡(luò)和系統(tǒng)受到危害之前攔截特征行為攻擊[2]。系統(tǒng)遭受入侵后,，IDS能將收集到的入侵行為和相關(guān)信息納入知識庫,，通過主動學習方式避免重復或類似攻擊，有效彌補防火墻被動防御的不足,。
1.2 入侵檢測分類
    入侵檢測系統(tǒng)根據(jù)檢測技術(shù)可以為分特征檢測和異常檢兩類,。特征檢測是通過監(jiān)視特定活動并與預先所設(shè)置的模式進行匹配來檢測入侵[2]。這種利用特征庫檢測已知入侵行為的方法檢測率高,，速度快,，并且對檢測結(jié)果有明確的處理參照,，但是不能檢測未知攻擊，很難將具體入侵手段抽象成知識特征,。異常檢測是基于系統(tǒng)或用戶的正常行為模式檢測入侵。該方法首先建立用戶正常行為模式,，當系統(tǒng)運行時將實時行為與正常行為模式進行匹配,，一旦發(fā)生顯著偏離即認為是入侵[2]。異常檢測方式與系統(tǒng)環(huán)境無關(guān),，通用性較好,，可以檢測未知攻擊和潛在威脅，但需要對每個戶行為作全面描述,，兼之個體行為的不確定性和獨特性導致算法復雜,，檢測速度緩慢，漏報,、誤報率較高,。
2 粗糙集理論
    粗糙集理論是處理不精確、不確定和不完整數(shù)據(jù)的數(shù)學理論,，能夠?qū)Σ灰恢?、不完整、不完善信息提煉?nèi)在特征,，揭示隱含規(guī)律,。
    粗糙集理論可以對決策表的屬性進行約簡，以便提高分類性能,，獲取潛在規(guī)則,。對于任意決策表，不是每個屬性對分類決策表的分類能力都有效,，因此,，在決策表分類能力不變的情況下，刪掉冗余的條件或者決策屬性,，可以得到相對簡單,、易理解、易操作的決策表[3],。通過粗糙集理論對決策表屬性進行約簡,，有利于過濾典型分類屬性，形成新的決策表,。通過約簡決策表中的無關(guān)屬性可以有效降低計算的時空復雜度,，加速算法收斂。粗糙集理論如下,。

3 遺傳算法
    遺傳算法GA（Genetic Algorithms）源于達爾文的進化論和孟德爾,、摩根的遺傳學理論,，由美國John Holland教授于20世紀60年代末提出，模擬生物遺傳機制“適者生存,、優(yōu)勝劣汰”,。遺傳算法操作對象是一群二進制串，稱為染色體或種群,，每個染色體都對應于問題的一個解,。從初始種群出發(fā)，采用基于適應度比例的選擇策略在當前種群中選擇個體,，通過交叉選擇和變異操作產(chǎn)生新一代適應度更高的染色體,，重復上述繁衍進化過程直到收斂到一個最合適的染色體上，從而找出問題的最優(yōu)解,。遺傳算法擁有卓越的智能學習效率和自適應性,，近年來應用于故障診斷、行為仿真和入侵檢測等領(lǐng)域,。
    決定遺傳算法性能的3個參數(shù)分別為群體大小pop,、交叉概率pc和變異概率pm。群體大小pop太小時難以找出最優(yōu)解,，太大則增加收斂時間,；交叉概率pc太小時難以向前搜索，太大則容易破壞高適應值的結(jié)構(gòu),；變異概率pm太小難以產(chǎn)生新的基因結(jié)構(gòu),，太大使遺傳算法成了單純的隨機搜索。
4 一種基于粗糙集遺傳算法
    粗糙集理論和遺傳算法各有優(yōu)勢,。粗糙集適用于主動學習模式,，通過約簡高維數(shù)據(jù)屬性維數(shù)降低算法時空復雜度。而遺傳算法處理數(shù)據(jù)量不大時具有良好的收斂性和魯棒性,，但在處理海量數(shù)據(jù)時,，特別是當處理高維數(shù)據(jù)時，參數(shù)難以界定,，易出現(xiàn)染色體的變異交叉操作使得算法經(jīng)高次迭代繁衍仍無法收斂的問題,。
    本文將粗糙集約簡原理與遺傳算法進行整合，通過自適應學習方式為入侵檢測系統(tǒng)提供行為特征,?；舅枷胧峭ㄟ^粗糙集約簡策略先過濾數(shù)據(jù)流量的無關(guān)屬性，然后對處理后數(shù)據(jù)采用結(jié)合鄰域思想進行分類,，為遺傳算法初始化種群,，并保證篩選樣本的穩(wěn)定性和典型性，避免遺傳算法處理數(shù)據(jù)量過大難以收斂的問題,，最后由遺傳算法迭代完成入侵行為特征的提煉和描述,。
4.1 算法思想和流程
    粗糙集的屬性約簡原理適合于處理精確數(shù)據(jù),，進行數(shù)據(jù)知識分類與獲取，同時對決策分析進行輔助,。經(jīng)過粗糙集屬性約簡后的系統(tǒng),，屬性的減少降低了計算的復雜性，但仍能夠保持相同的決策要求和效果,。遺傳算法對數(shù)據(jù)特征進行選擇和優(yōu)化建立在選擇合適的適應度函數(shù)以及合理進行選擇,、交叉和變異的基礎(chǔ)上。
    另外在遺傳算法中,，交叉變異算子作用是將群體中優(yōu)良個體遺傳到下一代,，加速算法的收斂速度,，并增加和維持群體多樣性,，以免陷入局部最優(yōu)解的問題。但是傳統(tǒng)算法中,，交叉變異算子以一個極小概率隨機改變?nèi)旧w某些字位,，隨意性和任意性影響算法的收斂速度。本文再次利用粗糙集約簡屬性,，將優(yōu)異個體朝重要屬性

    新算法通過粗糙集理論約簡屬性,，一方面為遺傳算法提供初始化種群，減少訓練時間,；另一方面可避免隨機變異造成的緩慢收斂,，減少算法時空復雜度，隨著樣本的增多,，新算法在訓練時間上更具優(yōu)勢,。在檢測精度和檢測率方面，新算法有效去除無用樣本和冗余屬性,，檢測更為方便快捷,，檢測精度和檢測率都有不錯表現(xiàn)。
5.3 個體適應度和迭代次數(shù)測試
    新算法個體適應度明顯優(yōu)于其余兩種算法,。新算法利用粗糙集約簡屬性,，將優(yōu)異個體朝重要屬性加速變異，并將其基因繁衍給下一代個體,，使得個體適應度更高,，新算法在第640次迭代已趨于收斂，如圖3所示,。而其余兩種算法由于變異的隨機性和任意性,，適應度不高，分別在經(jīng)760次和740次迭代才趨于收斂,。

    本文在研究粗糙集和遺傳算法的理論基礎(chǔ)上,，提出一種基于粗糙集的遺傳算法,，通過粗糙集屬性精簡遺傳算法種群，并在變異操作中將優(yōu)異個體朝重要屬性加速變異,，降低算法時空復雜度,。通過算法對比和實驗分析，本文提出的新算法在提高網(wǎng)絡(luò)入侵檢測速度和準確率方面是有效的,、可靠的和可行的,，為網(wǎng)絡(luò)安全信息建設(shè)提供強有力的保障。
參考文獻
[1] HOFMEYR S A,， FORREST 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,， FORREST 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,， FAWAZ Z. Applicability and viability of a GA based finite element analysis 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] TIMMIS J,， NEAL M， HUNT J. An artificial immune system for data analysis[J]. BioSystems,， 2000,，55，（55）：143-150.