改進(jìn)的否定選擇算法在入侵檢測(cè)系統(tǒng)中的應(yīng)用

金 靜，韓 虎，崔永君

（蘭州交通大學(xué) 電子與信息工程學(xué)院，甘肅 蘭州 730000）

入侵檢測(cè)系統(tǒng)（Intrusion Detection System，IDS）是軟件和硬件的組合，它對(duì)系統(tǒng)中的關(guān)鍵點(diǎn)進(jìn)行信息的收集和分析，從而判斷被保護(hù)的目標(biāo)是否被惡意濫用或者非法入侵，并通過(guò)提示報(bào)警、阻斷連接、通知網(wǎng)管等措施及時(shí)中止這些危害。它作為一種積極主動(dòng)的安全防護(hù)技術(shù)，是防火墻后面的第二道安全閘門(mén)。

生物機(jī)體內(nèi)的免疫系統(tǒng)是一個(gè)高度進(jìn)化的系統(tǒng)，它能區(qū)分外部有害抗原和自身組織，清除病原并保持機(jī)體的穩(wěn)定。生物免疫系統(tǒng)的特性與入侵檢測(cè)系統(tǒng)所需要達(dá)到的目標(biāo)是十分相似和一致的，因此通過(guò)模仿和借鑒生物免疫系統(tǒng)的一些機(jī)制和原理來(lái)進(jìn)行入侵檢測(cè)方面的研究，可以彌補(bǔ)當(dāng)前IDS的不足。

1 否定選擇算法

人工免疫系統(tǒng)（Artificial Immune System，AIS）通過(guò)否定選擇算法（NSA）[1-2]實(shí)現(xiàn)對(duì)自體的耐受。該算法是對(duì)免疫細(xì)胞的成熟過(guò)程的模擬，目的是清除那些對(duì)自體產(chǎn)生應(yīng)答的免疫細(xì)胞。算法的具體步驟為：

步驟1定義系統(tǒng)的正常狀態(tài)為自體集S。

步驟2隨機(jī)字符串產(chǎn)生器產(chǎn)生定長(zhǎng)的候選檢測(cè)器。

步驟3將候選檢測(cè)器與自體集合S進(jìn)行比較，即計(jì)算候選檢測(cè)器與自體集的匹配度，達(dá)到匹配閾值的候選檢測(cè)器就會(huì)被清除，否則將候選檢測(cè)器加入成熟檢測(cè)器集合。

步驟4重復(fù)步驟2和步驟3，直到有效檢測(cè)器數(shù)目達(dá)到預(yù)定的大小。該過(guò)程流程圖如圖1所示。

圖1 否定選擇算法Fig.1 Negative select algorithm

算法中變量的定義為：

S：自體串；N：非自體串；R：檢測(cè)器集合；R0：候選檢測(cè)器集合；NR0：R0的規(guī)模；

Ns：自體集規(guī)模；NR：檢測(cè)器規(guī)模；r：匹配長(zhǎng)度；m：位串的字母大??；l：位串長(zhǎng)度；

Pm：任意兩個(gè)字符串匹配的概率；

Pf：任意一個(gè)非自體串不能被R中NR個(gè)檢測(cè)器所匹配的概率，又稱為漏檢概率。

f：任意隨機(jī)字符串與自體集合中的Ns個(gè)字符串都不匹配的概率。

算法中的候選檢測(cè)器是隨機(jī)生成的，該算法初始檢測(cè)集合的大小N與自體集S的大小呈指數(shù)關(guān)系，即

2 否定選擇算法的改進(jìn)

2.1 相關(guān)定義

定義1 r-連續(xù)位匹配規(guī)則（r_continuous bits）如果字符串x和y至少連續(xù)r位相同，則它們滿足r-連續(xù)位匹配，或稱之為匹配成功。r稱之為秩。

例如符號(hào)表為{0，1} x：0110100101

y：1110111101

當(dāng)r≤4時(shí)，x和y匹配成功。定義2匹配概率

兩個(gè)字符串匹配的總概率

pm=（1-1/m）*m-r*（l-r）+m-r（m-r<<1）其中，m為字母表長(zhǎng)度，l為串長(zhǎng)，r為秩。由此可見(jiàn)，對(duì)于r-連續(xù)位匹配規(guī)則，如果給定m和l，其匹配概率Pm是確定的。

2.2 NSA的改進(jìn)

在傳統(tǒng)的NSA中，生成的檢測(cè)器中必然存在重復(fù)與冗余。這是由于候選檢測(cè)器是隨機(jī)生成的。同時(shí)，通過(guò)免疫耐受的候選檢測(cè)器之間有可能互相匹配，即它們均包含某個(gè)長(zhǎng)度為r的子串，而這些互相匹配的檢測(cè)器只需其中之一進(jìn)入成熟檢測(cè)器集合即可。因此，在系統(tǒng)資源有限并且只能生成特定數(shù)量的檢測(cè)器集合的情況下，傳統(tǒng)否定選擇算法生成的檢測(cè)器必然會(huì)降低對(duì)非自體空間的覆蓋率。

基于此，否定選擇算法的改進(jìn)是當(dāng)今研究熱點(diǎn)。例如，文獻(xiàn)[3]提出了基于混沌理論的混合否定選擇算法，文獻(xiàn)[4]使用檢測(cè)器半徑可變的方法改進(jìn)否定選擇算法，文獻(xiàn)[5]分別提出了實(shí)值否定選擇算法。本文分析了傳統(tǒng)NSA算法不足的產(chǎn)生原因，提出對(duì)免疫耐受的檢測(cè)器進(jìn)行重復(fù)的多次篩選的方法?？紤]到時(shí)間成本，將第一次篩選得到的檢測(cè)器再進(jìn)行一次與成熟檢測(cè)器集合的匹配檢查，篩選出與已有檢測(cè)器集合不匹配的元素，以提高檢測(cè)器的整體覆蓋率。算法流程圖如圖2所示。

圖2 二次篩選的NSAFig.2 Screens twice-NSA

2.3 實(shí)驗(yàn)及其分析

實(shí)驗(yàn)中模擬系統(tǒng)使用r-連續(xù)位匹配規(guī)則（r_continuous bits）[6]，分別用傳統(tǒng)的否定選擇算法和改進(jìn)后的否定選擇算法產(chǎn)生同等規(guī)模的檢測(cè)器集合，使用相同的匹配閾值比較檢測(cè)器的整體覆蓋率。設(shè)兩個(gè)算法分別產(chǎn)生的檢測(cè)器集合為Ra和Rb，成熟檢測(cè)器的生成采用窮舉法。算法具體步驟如下：

Procedure Improve_NSA

begin

初始化各種參數(shù)：串長(zhǎng)l，匹配閾值r，檢測(cè)器的數(shù)量n；

構(gòu)造長(zhǎng)為l的模式空間作為自體集合S；

while（Ra規(guī)模

{

隨機(jī)產(chǎn)生候選位串p；

if（p 與 S 匹配）

{丟棄 p； continue；}

else將 p加入 Ra；

if（p 與 Ra不匹配）

將 p加入 Rb；

}

end

對(duì)于生成的檢測(cè)器集合Ra和Rb，分別記錄它們對(duì)于給定的非我集合的空間覆蓋率及檢測(cè)時(shí)間。取l=16，r=9時(shí)，結(jié)果如圖4所示，其中‘*’表示改進(jìn)前算法生成的檢測(cè)器，‘+’表示改進(jìn)后算法生成的檢測(cè)器：

圖3 兩種算法總執(zhí)行時(shí)間和覆蓋率的比較Fig.3 Comparison of two algorithms in execution timeand coverage rate

由圖3可見(jiàn)，檢測(cè)器Rb的覆蓋率比Ra有明顯提高，檢測(cè)器的分布也更均勻。

2.4 改進(jìn)算法在入侵監(jiān)測(cè)模型中的應(yīng)用

模擬生物免疫系統(tǒng)的相關(guān)運(yùn)行機(jī)制，構(gòu)建一個(gè)基于免疫機(jī)理的網(wǎng)絡(luò)入侵檢測(cè)系統(tǒng)（Network IDS）模型[7]，模型的框架如圖4所示。

分別將傳統(tǒng)的NSA和改進(jìn)的二次篩選的NSA應(yīng)用于成熟檢測(cè)器生成模塊，檢驗(yàn)其檢測(cè)率和漏檢率的變化。為保證實(shí)驗(yàn)數(shù)據(jù)的權(quán)威性和多樣性，本文選用美國(guó)國(guó)防部高級(jí)研究計(jì)劃局（DARPA）和麻省工學(xué)院（MIT）的林肯實(shí)驗(yàn)室共同推出的一批網(wǎng)絡(luò)連接記錄集KDD Cup 1999 Data[8]作為數(shù)據(jù)來(lái)源。實(shí)驗(yàn)測(cè)試數(shù)據(jù)集合具體組成如表1所示。

兩種算法對(duì)應(yīng)的檢測(cè)效果如表2所示。其中，TP為正確檢測(cè)率，即準(zhǔn)確檢測(cè)出非自體的概率；FP為錯(cuò)誤檢測(cè)率，表示

圖4 基于免疫原理的入侵檢測(cè)系統(tǒng)模型Fig.4 Immune IDSmodel

表1 測(cè)試集的組成Tab.1 Composition of the test sets

自體被錯(cuò)誤檢測(cè)成非自體的概率。

表2 兩種算法檢測(cè)率對(duì)比Tab.2 Comparison of two algorithm in detection rate

由此檢測(cè)結(jié)果可見(jiàn)，由于降低了檢測(cè)器的冗余度，改進(jìn)的否定選擇算法應(yīng)用于基于免疫原理的IDS中可以有效提高系統(tǒng)的正確檢測(cè)率，降低錯(cuò)誤檢測(cè)率。

3 結(jié) 論

采用篩選兩次的否定選擇算法，在自體集規(guī)模和檢測(cè)器規(guī)模相同的條件下，可以生成覆蓋率更高的檢測(cè)器集合。改進(jìn)算法可以降低成熟檢測(cè)器的重復(fù)率和冗余率，從而有效提高檢測(cè)器的正確檢測(cè)率。改進(jìn)算法的不足在于時(shí)間效率的降低，但是在現(xiàn)如今計(jì)算機(jī)硬件配置水平及運(yùn)算速度十分理想的條件下，這種改進(jìn)是有意義的。后續(xù)研究中應(yīng)考慮進(jìn)一步提高算法的時(shí)間效率。

[1]李濤.計(jì)算機(jī)免疫學(xué)[M].北京：電子工業(yè)出版社，2004．

[2]Forrest.S.Self-Nonself Discrimination in a Computer.Proceeding of 1994 IEEE Symposium on Research in Security and Privacy[M].Los Alamos.CA:IEEE Computer Society Press，1994．

[3]Aydin I，Karakose M，Akin E.Chaotic-based hybrid negative selection algorithm and its applications in fault and anomaly detection[J]．Expert Systems with Applications，2010，3（7）：5285-5294.

[4]伍海波.一種改進(jìn)的否定選擇算法在入侵檢測(cè)中的應(yīng)用[J].計(jì)算機(jī)應(yīng)用與軟件，2013，2（30）:174-176.WUHai-bo.Application of improved negative select algorithm in intrusion detection system[J].Computer Applications and Software，2013，2（30）:174-176.

[5]柴爭(zhēng)義．用于異常檢測(cè)的實(shí)值否定選擇算法[J]．吉林大學(xué)學(xué)報(bào)，2012，42（1）:176-181．CHAI Zhen-yi.Real negative select algorithm in anomaly detection[J].JiLing University Journal，2012，42（1）:176-181．

[6]DASGUPTAA D，YUA S，NINO F.Recent advances in artificial immune systems:models and applications[J].Applied Soft Computing，2011（11）:1574-1587.

[7]陳岳兵.面向入侵檢測(cè)的集成人工免疫系統(tǒng)[J].通信學(xué)報(bào)，2012，2（33）：126-131.CHEN Yue-bing.The integration of artificial immune system for intrusion detection[J].Communication Journal，2012，2（33）：126-131

[8]Lincoln Laboratory.Information Systems Technology[EB/OL].[2009-10-05]．http://www．ll．mit．edu/IST/ideval/data/1999/1999_data_in-dex.html．