一種用于入侵檢測系統的可變r匹配算法

摘 要:針對目前基于免疫的IDS中匹配算法存在的問題， 提出了一種r可變匹配算法。該算法通過動態調整匹配r值，控制匹配速度，提高了檢測性能。同時，給出了檢測性能的形式化定義，定義了自體非自體、抗體以及r匹配算法的動態變化方程;最后給出了具體的實現過程。理論分析和實驗結果表明，該算法具有較高的效率，提高了入侵檢測系統的檢測性能。

關鍵詞:入侵檢測系統; 人工免疫系統; 可變r匹配算法; 檢測性能

中圖分類號:TP393

文獻標志碼:A

文章編號:1001-3695(2010)02-0745-03

doi:10.3969/j.issn.1001-3695.2010.02.095

r- variable matching algorithm used for IDS

TANG-Jun1，2， ZHAO Xiao-juan2

(1.School of Software Engineering， Tongji University， Shanghai 200092， China; 2.Dept. of Information Engineering， Hunan Urban Construction College， Xiangtan Hunan 411101， China )

Abstract:Aiming at the deficiencies of current matching algorithm based on AIS (artificial immune system)，proposed an improved evolution optimization with r-continuous bit matching rule.Gave the concepts and formal definitions of immune cells，presented affinity accumulation process. This new algorithm introduces evolution operator into the matching rule during the affinity accumulation process to improve the detection efficiency and overcome the short-coming of the local optimum. Theoretical analysis and experimental results show that the algorithm greatly enhances detection performance.

Key words:intrusion detection system; artificial immune system(AIS); r-variable matching algorithm; detection perfor-mance

0 引言

目前，入侵檢測系統(intrusion detection system，IDS)面臨的一個主要問題是:隨著網絡帶寬的不斷增加，需要檢測的數據量猛增， IDS的檢測任務越來越重。入侵檢測本質上是一個模式匹配問題，因此，匹配算法影響著入侵檢測系統的檢測性能。如果匹配算法過于緩慢或需要較大的空間，就會造成計算瓶頸現象，導致檢測性能下降[1]。入侵檢測問題與生物免疫系統(biological immune system，BIS )消滅外來病原體入侵問題具有驚人的相似性。基于免疫的入侵檢測匹配算法中，常見的有Euclidean、Manhattan、Hamming距離等方法。另外，還有類似于采用求向量夾角余弦的方法。這些方法是利用歐氏空間或是微分幾何中單純形等概念，把抗原與抗體描述成空間中的向量，再在向量空間中定義諸如內積等運算，由此來定量地描述抗體與抗原之間的相似度并且都有一定的優點。但由于求相似度的大量乘法運算，使得計算速度較慢且需要較大的空間。尤其是在處理入侵規模值較大、編碼串長值較大時，會造成許多數據來不及處理，導致漏報現象出現，影響檢測性能[2~4]。目前，常用的匹配算法為基本的r-連續位匹配算法。該算法認為:當抗體Ab與抗原Ag之間連續匹配的位數大于等于r值時， 則Ab與Ag兩者匹配。因此，如何設置r值的大小非常關鍵。本文針對固定r匹配算法的不足，提出了一種r可變連續匹配的算法，通過動態調整r值，提高了檢測性能。

1 理論基礎

定義1 入侵檢測系統的檢測性能。筆者采用錯誤概率作為檢測性能的指標，用符號DP表示。用符號∑IDS表示入侵檢測系統，用符號RTP、RMP、RFP分別表示入侵檢測系統的檢測率、漏警率(其值等于1-檢測率)、虛警率，則入侵檢測系統∑IDS的檢測性能可以表示為

DP(∑IDS)=WMP×RMP(∑IDS)+WFP×RFP(∑IDS)(1)

其中:WMP和WFP為權值，且有0≤WMP≤1，0≤WFP≤1，0≤WMP+WFP≤1。因此，DP(∑IDS)∈[0，+1]，且其值越小說明檢測性能越好，理想的入侵檢測系統的DP=0。因此，一個優異的入侵檢測系統應該具有高的檢測率和低的虛警率。WMP、WFP權值可根據具體情況下對漏警和虛警的側重點不同而賦值。

定義2 r可變連續位匹配算法。定義r-連續位匹配算法如式(2)所示。其中1表示匹配，0表示不匹配，l為字符串長。

fmatch(x，y)=1iffi，j(xi=yi，xi+1=yi+1，…，xj=yj， j-i≥r，0

當抗體Ab與抗原Ag之間連續匹配的位數大于等于r值時， 則認為Ab與Ag兩者匹配。因此，如何設置r值的大小非常關鍵。若r值過小，抗原與抗體之間的差異不明顯，會造成親和力累積過快，使得形成的成熟抗體根本不具有識別足夠多的抗原的能力，會造成虛警率增大。當r值過大，又會使得親和力總是累積失敗，形成成熟抗體的時間太長，最后入侵檢測系統又會出現漏報的狀況，因此，r過大過小都會影響檢測性能[5]。所以，如果能讓r的值根據用戶對檢測系統性能的要求動態改變，將有效提高檢測性能。

r可變連續匹配算法的思想是，根據系統自身的運行狀態，動態調整r值的大小。在入侵檢測中體現為，當網絡訪問量較少、連接數目不多時，加大r值抑制匹配速度，使得生成的成熟抗體能正確反應和識別抗原，提高免疫系統識別入侵行為的準確率，降低虛警率。當網絡流量加劇、網絡連接數目增多時，通過降低r值，采用加快匹配速度，盡快生成成熟抗體，及時發現入侵行為。當然，可能此時檢測結果的虛警率會稍微增加，但由于免疫系統學習周期變短后，系統反應速度加快，漏警率會明顯降低，根據式(1)，系統檢測性能依然得到提高。此外，還降低了系統資源的占用率。

2 r可變連續匹配算法在入侵檢測系統中的實現

入侵檢測系統中，免疫系統中的抗原被映射成IDS中的網絡行為，抗體被映射為檢測器。自體抗原被映射成正常網絡行為，非自體抗原被映射成非法網絡行為。檢測器檢測網絡行為是否正常的過程就被抽象為BIS中抗體識別判斷抗原是自體/非自體的過程。下面給出實現過程的形式化描述。

2.1 自體與非自體(抗原)形式化描述

定義論域D{0，1}l，抗原集合AgD，自體集合SelfAg，非自體集合nonselfAg。有self∪nonself=Ag，self∩noself=。其中:Ag表示對網絡上傳輸的IP包進行特征提取得到的長度為l的二進制字符串，包括IP地址、端口號、協議類型等網絡事務特征;self集為正常網絡服務事務;nonself集為非法活動或網絡攻擊。

2.2 抗體形式化描述

免疫中，抗體分為三類，即未成熟抗體、成熟抗體和記憶抗體[6]。定義抗體細胞集合B={〈d，age，count〉|d∈D∧age∈N∧count∈N}。其中:d為抗體(長度為L的二進制字符串);age為抗體年齡;count為抗體的累計親和力數目;N為自然數集合。

定義未成熟免疫抗體集合為尚未進行自體耐受的抗體Ib={〈d，age〉|d∈D，age∈N}。檢測抗體集合B=Mb∪Tb，Tb為成熟免疫抗體集合，由經過自體耐受過程的未成熟免疫抗體構成，Tb{x|x∈B，x.count≤β}(β為匹配閾值)。記憶免疫抗體集合Mb={x|x∈B，x.count>β}，即記憶抗體由被激活的成熟抗體進化而來。

2.3 r的動態變化方程

入侵檢測系統中，檢測器檢測入侵行為的過程，隱喻為抗體識別抗原的過程。本算法中抗體識別抗原通過動態r 匹配策略實現。動態變化方程定義如下:定義抗體抗原匹配速度v1與輸入數據包速度v2呈正比例關系:v1=k1×v2。其中k1為比例系數。當網絡流量加劇、連接數目增多(輸入數據包增多)時，加快匹配速度;反之，降低匹配速度。匹配速度v1與r值的關系:v1每提高k2%，r值減少1;反過來，當v1每降低k2%，r值增加1(k2為比例系數)。r的動態變化方程定義為:r(t+1)=rt-(v(t+1)-vt)/n」，」，表示向下取整，vt表示t時刻網絡的數據流強度，n為比例系數，可根據實際情況確定。

2.4 抗體動態變化方程

由于網絡入侵行為(抗原)是動態變化的，如果檢測器集合(成熟抗體和記憶抗體)不進行動態更新，系統將具有很高的漏警率和虛警率。定義了如下的抗體動態變化方程，以更好地提高檢測性能。

成熟抗體集合Tb的動態變化方程為

Tb(t)=Tb(t-1)+Tnew(t)-(Tactive(t-1)+Tdead(t-1))(3)

其中:Tnew=Ib-{d/d∈Ib∧y∈self∧fmatch(d，y)=1}(4)

Tactive={x|x∈Tb∧x.count≥β∧x.age≤λ}(5)

Tdead={x|x∈Tb∧x.count<β∧x.age>λ}(6)

Tnew(t)表示t時刻經過自體耐受新生成的成熟抗體。其中fmatch(x，y)采用本文提出的r可變匹配算法。Tactive表示在生命周期λ內，累積親和力數目達到激活閾值，激活為記憶抗體的成熟抗體。Tdead表示在生命周期λ內，累積親和力數目未達到激活閾值，而死亡的成熟抗體。

記憶抗體動態變化方程為

Mb(t)=Mb(t-1)+Mnew(t)-Mdead(t)(7)

其中:Mdeath(t)={x|x∈Mb(t)，fmatch(x，self(t-1))=1}(8)

Mnew(t)=Tactive(t)(9)

Mdeath(t)模擬記憶細胞死亡過程，若某記憶細胞匹配了一個已經被證實的自體抗原，該記憶細胞被刪除掉。其中fmatch(x，y)采用本文提出的r可變匹配算法。Mnew(t)由成熟抗體進化而來?？贵w的動態變化方程保證了抗體可以隨著時間的推移而動態變化，有效降低了系統的虛警率和漏警率。

2.5 系統檢測過程

在入侵檢測中，抗原的檢測是通過檢測抗體集合實現的，抗體抗原的匹配采用本文的r可變匹配算法。當有入侵發生時，首先通過記憶抗體集合Mb進行檢測，稱為二次應答，檢測效率高。記憶抗體無法識別的抗原，交給成熟抗體集合檢測，稱為初次應答，可以識別一些未知病毒。

3 仿真實驗與結果分析

實驗在網絡安全實驗室進行，實驗數據為KDDCup1999入侵檢測數據集[7]。采用不包括任何攻擊的數據作為訓練數據， 測試數據集中包含正常數據和攻擊數據， 攻擊數據分為DoS、Probe、U2R、R2L4四大類。用不同攻擊類型，如Syn-flood、Lan、Smurf等模擬對網絡進行攻擊，模擬網絡流量的突然加劇，對系統進行了測試，重復進行五次實驗。實驗結果采用平均TP值(檢測率)和FP值(虛警率)進行評估。系統主要參數取值如下:取二進制串抗原l=96，選取初始自體集合大小n=40。經過反復比較實驗，在系統表現穩定的情況下，最終選定參數β=40，λ=7天，k1=2，k2=5。

對不同的r值進行實驗，以驗證r固定時，其對TP、FP的影響。圖1為成熟抗體親和力累積階段r值對TP、FP值的影響結果。在實驗中發現，隨著r的增加，系統的TP值也增加，FP值減小。這是由于r的增加加大了抗體成熟難度，抗體能正確反應和識別抗原，提高了檢測器識別入侵行為的準確率，降低了虛警率。但r值過大時， 會增加計算復雜度，在需要處理的數據量過大時，由于有些數據來不及檢測，會增加漏警率MP，TP(1-MP)值反而又降低。在本實驗條件下，通過分析比較r取20附近，能得到較滿意結果。當參數選擇合適，TP值能穩定在94%以上，FP值降低到1.5%左右。

為了驗證r可變匹配算法的性能，本文與固定r匹配算法進行了對比實驗。固定r匹配算法取r=20，也就是前面實驗得出的最佳值。在對比實驗中，控制發往監控主機的數據包，模擬網絡攻擊的強度變化。測試采用本文提出的r可變匹配規則與r=20(最優值)固定匹配規則下，系統的TP值和FP值變化情況。數據包的數目變化如圖3所示，測得的TP值和FP值變化情況如圖4所示。

從圖4中可以看到，采用r可變的匹配規則，入侵檢測系統的TP(檢測率)好于采用r固定(r=20)的匹配規則。主要是由于r的動態改變，提高了系統對入侵的識別率。而系統的FP值采用r可變的匹配規則時，在一些情況下比r固定的匹配規則要稍高，這主要是由于r值的降低使得親和力成熟過快，造成了一定的誤報，但此時，系統的檢測率TP較高，系統的資源占有較少，根據檢測性能的定義式(1)，檢測性能仍然得到了提高。因此，本算法具有一定的應用價值。

4 結束語

本文針對入侵檢測系統中使用最多的固定r連續位匹配算法的不足，提出了一種r可變匹配算法， 闡述了其基本思想，給出了此算法用于入侵檢測中的具體實現過程，并通過實驗驗證了其有效性。與固定r連續位匹配算法相比，它通過動態地調節匹配速度，滿足實際網絡需求，達到在不提高算法復雜度和系統資源占用容量的前提下，又很好地提高了檢測性能。理論分析和實踐表明，本算法具有一定的優越性。如何更好地動態調整r的變化，進一步提高檢測性能，還需要進一步研究。同時，本算法對基于免疫的病毒檢測等領域也有一定的借鑒意義。參考文獻:

[1]李濤.基于免疫的網絡監控模型[J].計算機學報，2006，29(9):1515-1522.

[2]閆巧，喻建平，謝維信.入侵檢測系統的可信問題[J].計算機研究與發展，2003，40(8):1203-1208.

[3]張衡，吳禮發，張毓森，等.一種r 可變陰性選擇算法及其仿真分析[J].計算機學報，2005，28(10):1614-1619.

[4]HOFMEYR S，FORREST S.Architecture for an artificial immune system[J]. Evolutionary Computation，2000，8(4):443-473.

[5]楊義先，鈕心忻.入侵檢測理論與技術[M].北京:高等教育出版社，2006.

[6]何申， 羅文堅， 王煦法.一種檢測器長度可變的非選擇算法[J].軟件學報，2007，18(6):1361-1368.

[7]University of California. KDDLib[EB/OL]. [2009-03-02].http://kdd.ics.uci.edu/databases/kddcup99.

[8]符海東，王楓.基于數理統計及人工免疫的入侵檢測模型[J].計算機工程與設計，2008，29(12):3037-3039.