基于粗糙集的免疫入侵檢測器優化算法

◆向 婷 譚敏生 于俊勇

（南華大學衡陽計算機科學與技術學院 湖南 421000）

基于粗糙集的免疫入侵檢測器優化算法

◆向 婷 譚敏生 于俊勇

（南華大學衡陽計算機科學與技術學院 湖南 421000）

本文分析了免疫入侵檢測器在實值空間下存在的問題，提出一種基于粗糙集的免疫入侵檢測器優化算法（IIDOA-R&A）：利用粗糙集約簡理論將高維形態空間轉換為低維空間，并利用屬性重要度加權歐式距離來計算親和度大小，通過親和度對比來優化檢測器。實驗表明：優化后的檢測器不僅提高了檢測的速度，改善檢測器存在的高重疊問題，對非自體集的覆蓋效果也相對理想。

免疫入侵檢測器; 實值形態空間; 粗糙集; 屬性重要度; 加權歐式距離

0 前言

隨著網絡的飛速發展，信息安全防護顯得尤為重要。入侵檢測作為一種積極主動的網絡安全技術，成為了保證網絡安全的重要手段。由于生物免疫系統具有自適應、魯棒性等諸多優點，將免疫機理應用到入侵檢測系統中的研究也越來越多。然而對于基于免疫機理的入侵檢測系統（IDS）來說，檢測器的質量是決定檢測性能的重中之重，所以檢測器的優化問題成為各個學者爭相研究的熱點。

1 形態空間

基于免疫機理的IDS，主要是在形態空間下進行討論[1]。形態空間U主要包含自體空間US和非自體空間UN兩個部分在理想狀態下，US由自體集合S覆蓋，UN由檢測器集合覆蓋。而現實中卻肯定存在沒有被檢測器覆蓋的非自體空間，稱之為黑洞H。檢測器集合是由候選檢測器集合C通過自體耐受過程得到。目前，檢測器根據表示的形態空間不同，分為二進制形態空間和實值形態空間。由于二進制空間比較簡單，這里不予討論。在實值空間中，每個自體樣本可以表示為:其中i=1，2，…，Ns， sij為該自體樣本的第j維屬性值，j=1，2，…，N，r為該自體樣本訓練半徑，OtherAttribute為該自體樣本的其他屬性，如年齡等。同理，也可以用相同方法表示檢測器。檢測器主要通過親和力匹配來進行檢測。

2 問題分析

在實值形態空間中，檢測器存在的問題如下:

（1）檢測器高重疊和黑洞問題

高重疊和黑洞問題是基于免疫機理的入侵檢測系統一直存在的問題。為此，很多學者也做了相當多的研究:Li[2]等人提出的V-detector檢測器生成算法，以檢測器中心與其親和力最大的自體邊界間的距離作為檢測半徑。但是它又造成每個檢測器都會覆蓋自體與非自體邊界區域，重疊覆蓋現象嚴重。席亮[3]提出一種檢測器優化算法，通過比較檢測器間的親和力判斷檢測器的優良程度，并利用子代替換效果較差的個體，取得比較好的結果。

（2）檢測器數量問題

假設檢測器相互獨立，設每個檢測器匹配異常事件的概率為Pi，則任一個異常沒有被檢測器集合匹配的概率當 Nd很大的時候，Pi維持在一個較小的水平，為了方便表示，設定Pi為定值Pm，則上式可近似表示為:當 Pm一定時，檢測器集合規模與一次誤報率成指數關系。而且在實際應用中，檢測器相互獨立不可能全部成立，使得檢測的失敗概率增大，也增大了系統的檢測負擔。

（3）檢測器屬性維度問題

對于實值檢測器，屬性數較多，且有些屬性的相關性較強，從而帶來了巨大的額外的計算代價。

3 粗糙集理論

粗糙集理論是一種用于處理不確定、不精確、不完整知識的數學工具。其相關概念如下:

（1）定義1 知識庫[4]

對于一個論域U，S為U上的等價關系簇，那么二元組K=（U，S）就叫一個知識庫，表示論域U上的一個近似空間。

（2）定義2 決策表[5]

對于一個五元組DT=（U，C，D，V，f），其中U={x1，x2，…，xn}是由n個非空對象組成的對象集合，稱之為論域; C={a|a∈C}且C≠?是條件屬性集合; D={d|d∈D}且D≠?為決策屬性集; 對于條件屬性集C和決策屬性集D有:C∩D=?; V=∪Va（?a∈C∪D）為信息系統f的值域，可以用Va來表示; f={fa|fa:U→Va，?a∈C∪D}是一個信息函數，fa表示屬性a的信息函數; 此時該五元組DT就叫決策表。

（3）定義3 不可分辨關系[4]

對于論域U上的等價簇S，若?P≠?，P?S，則∩P依然是U上的一個等價關系集合，稱為P上的不可分辨關系，記為IND（P），簡稱P，即:

（4）定義4 上近似，下近似[4]

對于一個知識庫K=（U，S），U為論域，S為U上的等價關系簇，那么?X?U和U上的一個等價關系R∈IND（K），那么定義子集X關于知識R的上近似和下近似分別為:

（5）定義5 屬性重要度[5]

給定一個決策表DT，對于條件屬性a∈C，相對于決策屬性D的重要度為:

4 基于粗糙集的免疫入侵檢測器優化算法

4.1 改進的親和度計算方法

對于傳統的親和力計算方法，往往忽略了各個屬性本身存在的重要度的差異，而采用統一的標準來對待數據的每一個屬性，而基于屬性重要度加權歐式距離很好的考慮到了屬性間的關系，屬性重要度越大，那么對于親和力計算的結果就越重要，影響就越大。現兩個檢測器d1和d2，其加權歐式距離可以表示為:

其中SGFi是第i個屬性的重要度，d1i和d2i分別表示檢測器d1和檢測器d2的第i個屬性值。

4.2 基本思想

實值檢測器中的屬性眾多，且有些屬性的相關性較強，那么有必要將檢測器的屬性進行約簡，從而減少計算代價的同時，也不影響檢測器的分類性。對于約簡后的檢測器，可以用親和度來表示兩個檢測器間的相似程度。親和度越高，那么兩個檢測器就越相似。而這種相似的個體越多，則相應的重疊率就越高。所以采取在多個相似的個體之中，只保留較優秀的那個個體的方法來優化檢測器的分布。同時由于屬性之間有重要度的差異，所以在計算親和度的時候，應該充分考慮各個屬性本身的重要度，利用屬性重要度來計算親和力的大小。

4.3 算法步驟

圖1 算法流程

（1）正規化方式

本文的正規化處理采用如下方式:首先計算每一個屬性值的方差μj和標準差σj，再根據如下兩個公式將樣本進行正規化:

5 實驗

實驗首先將各個數據集樣本的屬性進行正規化，并設定自體半徑為0.05。為了驗證本文提出的改進算法和v-detector算法對非自體集的覆蓋效果和檢測器間的重疊率，實驗采用二維空間，以五角星數據集進行實驗[6]，分別用本文的優化算法和v-detector算法優化含120個檢測器的檢測器集合。并使用Monte Carlo方法[7-8]計算檢測器對非自體的覆蓋率和檢測器間的重疊率:

（1）估計單個檢測器占整個形態空間的體積（百分比）:

（2）估計單個檢測器與其他檢測器重疊區域占其本身區域的百分比:

（3）估計檢測器集合對非自體空間的覆蓋率:

（4）估計檢測器集合的總重疊率:

表1 二種算法檢測器覆蓋率與重疊率的比較

從實驗結果可以看出，優化后的算法雖然在檢測器對非自體的覆蓋率有所下降，但是檢測器間的重疊率遠遠降低。在保證的覆蓋率的情況，大幅度降低的重疊率，優化了檢測器。

6 結束語

本文利用粗糙集理論，先將檢測器屬性降維，再利用屬性重要度改進傳統的簡單的利用歐式距離來計算親和度，通過檢測器間的親和力對比來優化檢測器的分布。實驗結果表明，本文提出的檢測器優化算法，在保證一定的覆蓋率的前提下，大大的降低了檢測器間的重疊率，進而提高了檢測率。

[1]TEW J,PHIPPS P,MANDEL T.The maintenance and regulation of human immune response:persisting antigen and t he role of follicular antigen-binging dendritic cell [J].Immunol ogical Review,1980.

[2]Li G Y,Li T,Zeng J,et al.Negative selection algorithm based on immune suppression[C]//Proceedings of 8th Internati onal Conference on Machine Learning and Cybernetics.Baodin g,China,IEEE,2009.

[3]席亮.免疫入侵檢測自體與檢測器動態自適應機制研究[D].哈爾濱理工大學，2012.

[4]蔡忠閩，管曉宏，邵萍，孫國基.基于粗糙集理論的入侵檢測新方法 [J].計算機學報，2003.

[5]苗奪謙，李道國.粗糙集理論、算法及應用[M].清華大學出版社，2008.

[6]ZHOU J,DASGUPTA D.Estimating the detector cover age in a negative selection algorithm.In:Proceedings of the 20 05 Conference on Genetice and Evolutionary Computation,W ashington DC,USA,2005.

[7]MACK AY J C.Introduction to Monte Carlo method [M].Oak Ridge National Laboratory,Oak Rigde,USA,1995.

[8]LIU J.S.Monte Carlo Strategies in Scientific Computin g [M].Springer-Verleg,Berlin,Germany,2001.