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

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

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

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

    本文在研究粗糙集和遺傳算法的理論基礎上，提出一種基于粗糙集的遺傳算法，通過粗糙集屬性精簡遺傳算法種群，并在變異操作中將優異個體朝重要屬性加速變異，降低算法時空復雜度。通過算法對比和實驗分析，本文提出的新算法在提高網絡入侵檢測速度和準確率方面是有效的、可靠的和可行的，為網絡安全信息建設提供強有力的保障。
參考文獻
[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.