改進的否定選擇算法在入侵檢測系統中的應用

金 靜，韓 虎，崔永君

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

入侵檢測系統（Intrusion Detection System，IDS）是軟件和硬件的組合，它對系統中的關鍵點進行信息的收集和分析，從而判斷被保護的目標是否被惡意濫用或者非法入侵，并通過提示報警、阻斷連接、通知網管等措施及時中止這些危害。它作為一種積極主動的安全防護技術，是防火墻后面的第二道安全閘門。

生物機體內的免疫系統是一個高度進化的系統，它能區分外部有害抗原和自身組織，清除病原并保持機體的穩定。生物免疫系統的特性與入侵檢測系統所需要達到的目標是十分相似和一致的，因此通過模仿和借鑒生物免疫系統的一些機制和原理來進行入侵檢測方面的研究，可以彌補當前IDS的不足。

1 否定選擇算法

人工免疫系統（Artificial Immune System，AIS）通過否定選擇算法（NSA）[1-2]實現對自體的耐受。該算法是對免疫細胞的成熟過程的模擬，目的是清除那些對自體產生應答的免疫細胞。算法的具體步驟為：

步驟1定義系統的正常狀態為自體集S。

步驟2隨機字符串產生器產生定長的候選檢測器。

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

步驟4重復步驟2和步驟3，直到有效檢測器數目達到預定的大小。該過程流程圖如圖1所示。

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

算法中變量的定義為：

S：自體串；N：非自體串；R：檢測器集合；R0：候選檢測器集合；NR0：R0的規模；

Ns：自體集規模；NR：檢測器規模；r：匹配長度；m：位串的字母大小；l：位串長度；

Pm：任意兩個字符串匹配的概率；

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

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

算法中的候選檢測器是隨機生成的，該算法初始檢測集合的大小N與自體集S的大小呈指數關系，即

2 否定選擇算法的改進

2.1 相關定義

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

例如符號表為{0，1} x：0110100101

y：1110111101

當r≤4時，x和y匹配成功。定義2匹配概率

兩個字符串匹配的總概率

pm=（1-1/m）*m-r*（l-r）+m-r（m-r<<1）其中，m為字母表長度，l為串長，r為秩。由此可見，對于r-連續位匹配規則，如果給定m和l，其匹配概率Pm是確定的。

2.2 NSA的改進

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

基于此，否定選擇算法的改進是當今研究熱點。例如，文獻[3]提出了基于混沌理論的混合否定選擇算法，文獻[4]使用檢測器半徑可變的方法改進否定選擇算法，文獻[5]分別提出了實值否定選擇算法。本文分析了傳統NSA算法不足的產生原因，提出對免疫耐受的檢測器進行重復的多次篩選的方法。考慮到時間成本，將第一次篩選得到的檢測器再進行一次與成熟檢測器集合的匹配檢查，篩選出與已有檢測器集合不匹配的元素，以提高檢測器的整體覆蓋率。算法流程圖如圖2所示。

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

2.3 實驗及其分析

實驗中模擬系統使用r-連續位匹配規則（r_continuous bits）[6]，分別用傳統的否定選擇算法和改進后的否定選擇算法產生同等規模的檢測器集合，使用相同的匹配閾值比較檢測器的整體覆蓋率。設兩個算法分別產生的檢測器集合為Ra和Rb，成熟檢測器的生成采用窮舉法。算法具體步驟如下：

Procedure Improve_NSA

begin

初始化各種參數：串長l，匹配閾值r，檢測器的數量n；

構造長為l的模式空間作為自體集合S；

while（Ra規模

{

隨機產生候選位串p；

if（p 與 S 匹配）

{丟棄 p； continue；}

else將 p加入 Ra；

if（p 與 Ra不匹配）

將 p加入 Rb；

}

end

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

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

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

2.4 改進算法在入侵監測模型中的應用

模擬生物免疫系統的相關運行機制，構建一個基于免疫機理的網絡入侵檢測系統（Network IDS）模型[7]，模型的框架如圖4所示。

分別將傳統的NSA和改進的二次篩選的NSA應用于成熟檢測器生成模塊，檢驗其檢測率和漏檢率的變化。為保證實驗數據的權威性和多樣性，本文選用美國國防部高級研究計劃局（DARPA）和麻省工學院（MIT）的林肯實驗室共同推出的一批網絡連接記錄集KDD Cup 1999 Data[8]作為數據來源。實驗測試數據集合具體組成如表1所示。

兩種算法對應的檢測效果如表2所示。其中，TP為正確檢測率，即準確檢測出非自體的概率；FP為錯誤檢測率，表示

圖4 基于免疫原理的入侵檢測系統模型Fig.4 Immune IDSmodel

表1 測試集的組成Tab.1 Composition of the test sets

自體被錯誤檢測成非自體的概率。

表2 兩種算法檢測率對比Tab.2 Comparison of two algorithm in detection rate

由此檢測結果可見，由于降低了檢測器的冗余度，改進的否定選擇算法應用于基于免疫原理的IDS中可以有效提高系統的正確檢測率，降低錯誤檢測率。

3 結 論

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

[1]李濤.計算機免疫學[M].北京：電子工業出版社，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].計算機應用與軟件，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]柴爭義．用于異常檢測的實值否定選擇算法[J]．吉林大學學報，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]陳岳兵.面向入侵檢測的集成人工免疫系統[J].通信學報，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．