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

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

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

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

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