◆向 婷 譚敏生 于俊勇

（南華大學(xué)衡陽(yáng)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 湖南 421000）

基于粗糙集的免疫入侵檢測(cè)器優(yōu)化算法

◆向 婷 譚敏生 于俊勇

（南華大學(xué)衡陽(yáng)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 湖南 421000）

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

免疫入侵檢測(cè)器; 實(shí)值形態(tài)空間; 粗糙集; 屬性重要度; 加權(quán)歐式距離

0 前言

隨著網(wǎng)絡(luò)的飛速發(fā)展，信息安全防護(hù)顯得尤為重要。入侵檢測(cè)作為一種積極主動(dòng)的網(wǎng)絡(luò)安全技術(shù)，成為了保證網(wǎng)絡(luò)安全的重要手段。由于生物免疫系統(tǒng)具有自適應(yīng)、魯棒性等諸多優(yōu)點(diǎn)，將免疫機(jī)理應(yīng)用到入侵檢測(cè)系統(tǒng)中的研究也越來(lái)越多。然而對(duì)于基于免疫機(jī)理的入侵檢測(cè)系統(tǒng)（IDS）來(lái)說(shuō)，檢測(cè)器的質(zhì)量是決定檢測(cè)性能的重中之重，所以檢測(cè)器的優(yōu)化問(wèn)題成為各個(gè)學(xué)者爭(zhēng)相研究的熱點(diǎn)。

1 形態(tài)空間

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

2 問(wèn)題分析

在實(shí)值形態(tài)空間中，檢測(cè)器存在的問(wèn)題如下:

（1）檢測(cè)器高重疊和黑洞問(wèn)題

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

（2）檢測(cè)器數(shù)量問(wèn)題

假設(shè)檢測(cè)器相互獨(dú)立，設(shè)每個(gè)檢測(cè)器匹配異常事件的概率為Pi，則任一個(gè)異常沒(méi)有被檢測(cè)器集合匹配的概率當(dāng) Nd很大的時(shí)候，Pi維持在一個(gè)較小的水平，為了方便表示，設(shè)定Pi為定值Pm，則上式可近似表示為:當(dāng) Pm一定時(shí)，檢測(cè)器集合規(guī)模與一次誤報(bào)率成指數(shù)關(guān)系。而且在實(shí)際應(yīng)用中，檢測(cè)器相互獨(dú)立不可能全部成立，使得檢測(cè)的失敗概率增大，也增大了系統(tǒng)的檢測(cè)負(fù)擔(dān)。

（3）檢測(cè)器屬性維度問(wèn)題

對(duì)于實(shí)值檢測(cè)器，屬性數(shù)較多，且有些屬性的相關(guān)性較強(qiáng)，從而帶來(lái)了巨大的額外的計(jì)算代價(jià)。

3 粗糙集理論

粗糙集理論是一種用于處理不確定、不精確、不完整知識(shí)的數(shù)學(xué)工具。其相關(guān)概念如下:

（1）定義1 知識(shí)庫(kù)[4]

對(duì)于一個(gè)論域U，S為U上的等價(jià)關(guān)系簇，那么二元組K=（U，S）就叫一個(gè)知識(shí)庫(kù)，表示論域U上的一個(gè)近似空間。

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

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

（3）定義3 不可分辨關(guān)系[4]

對(duì)于論域U上的等價(jià)簇S，若?P≠?，P?S，則∩P依然是U上的一個(gè)等價(jià)關(guān)系集合，稱(chēng)為P上的不可分辨關(guān)系，記為IND（P），簡(jiǎn)稱(chēng)P，即:

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

對(duì)于一個(gè)知識(shí)庫(kù)K=（U，S），U為論域，S為U上的等價(jià)關(guān)系簇，那么?X?U和U上的一個(gè)等價(jià)關(guān)系R∈IND（K），那么定義子集X關(guān)于知識(shí)R的上近似和下近似分別為:

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

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

4 基于粗糙集的免疫入侵檢測(cè)器優(yōu)化算法

4.1 改進(jìn)的親和度計(jì)算方法

對(duì)于傳統(tǒng)的親和力計(jì)算方法，往往忽略了各個(gè)屬性本身存在的重要度的差異，而采用統(tǒng)一的標(biāo)準(zhǔn)來(lái)對(duì)待數(shù)據(jù)的每一個(gè)屬性，而基于屬性重要度加權(quán)歐式距離很好的考慮到了屬性間的關(guān)系，屬性重要度越大，那么對(duì)于親和力計(jì)算的結(jié)果就越重要，影響就越大?，F(xiàn)兩個(gè)檢測(cè)器d1和d2，其加權(quán)歐式距離可以表示為:

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

4.2 基本思想

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

4.3 算法步驟

圖1 算法流程

（1）正規(guī)化方式

本文的正規(guī)化處理采用如下方式:首先計(jì)算每一個(gè)屬性值的方差μj和標(biāo)準(zhǔn)差σj，再根據(jù)如下兩個(gè)公式將樣本進(jìn)行正規(guī)化:

5 實(shí)驗(yàn)

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

（1）估計(jì)單個(gè)檢測(cè)器占整個(gè)形態(tài)空間的體積（百分比）:

（2）估計(jì)單個(gè)檢測(cè)器與其他檢測(cè)器重疊區(qū)域占其本身區(qū)域的百分比:

（3）估計(jì)檢測(cè)器集合對(duì)非自體空間的覆蓋率:

（4）估計(jì)檢測(cè)器集合的總重疊率:

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

從實(shí)驗(yàn)結(jié)果可以看出，優(yōu)化后的算法雖然在檢測(cè)器對(duì)非自體的覆蓋率有所下降，但是檢測(cè)器間的重疊率遠(yuǎn)遠(yuǎn)降低。在保證的覆蓋率的情況，大幅度降低的重疊率，優(yōu)化了檢測(cè)器。

6 結(jié)束語(yǔ)

本文利用粗糙集理論，先將檢測(cè)器屬性降維，再利用屬性重要度改進(jìn)傳統(tǒng)的簡(jiǎn)單的利用歐式距離來(lái)計(jì)算親和度，通過(guò)檢測(cè)器間的親和力對(duì)比來(lái)優(yōu)化檢測(cè)器的分布。實(shí)驗(yàn)結(jié)果表明，本文提出的檢測(cè)器優(yōu)化算法，在保證一定的覆蓋率的前提下，大大的降低了檢測(cè)器間的重疊率，進(jìn)而提高了檢測(cè)率。

[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]席亮.免疫入侵檢測(cè)自體與檢測(cè)器動(dòng)態(tài)自適應(yīng)機(jī)制研究[D].哈爾濱理工大學(xué)，2012.

[4]蔡忠閩，管曉宏，邵萍，孫國(guó)基.基于粗糙集理論的入侵檢測(cè)新方法 [J].計(jì)算機(jī)學(xué)報(bào)，2003.

[5]苗奪謙，李道國(guó).粗糙集理論、算法及應(yīng)用[M].清華大學(xué)出版社，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.