0、 引言

設計基于免疫的入侵檢測系統的首要問題在于如何生成高質量的檢測器， 檢測器生成算法的好壞直接影響入侵檢測系統是否值得使用。 小生境技術是模擬生態平衡的一種仿生技術， 基于小生境策略的檢測器生成算法能夠盡可能保留較好的基因遺傳給下一代，并維持種群的多樣性。 在此基礎上，本文借鑒復雜網絡的免疫策略， 改進成熟檢測器的進化過程， 提出一種基于復雜網絡免疫策略的檢測器進化算法，并通過仿真實驗對比兩種算法的漏檢率、誤檢率以及數據編碼較長情況下對性能的影響，為該算法用于 IPv6 環境打下基礎。

1、 復雜網絡

計算機網絡的迅猛發展給人類社會與生活帶來巨大便利的同時，也帶來一定隱患，例如各種不良信息和行為入侵計算機系統以及計算機病毒的大面積傳播等。為了應對計算機網絡環境的種種挑戰，研究人員已經針對傳統、 單一的入侵檢測模型和算法存在的缺陷與不足， 將一些新的理論與入侵檢測相結合，例如，借助自然免疫系統對入侵抗原表現出的高度魯棒性、 自組織性和分布性以提高對未知模式的實時監測能力、 對異常行為的識別能力以及智能靈活的反應能力，提出更優化、高效的算法和模型，并已取得了一些成果，但真正高效、成熟的檢測算法和模型還未出現，仍存在較大的研究和提升空間。

復雜網絡理論通過研究各類互不相同的復雜網絡之間的共性，尋找如何進行處理的普適方法。 復雜網絡的研究正滲透到數理學科、 生命學科和工程學科等眾多不同的領域，其復雜性體現在：

a） 結構復雜性：連接結構復雜、混亂，可能隨時間發生變化。

b）節點復雜性：節點具有分岔、混沌等復雜非線性行為，可能存在多種類型的節點。

c）復雜性因素的影響：會受到各種影響和作用，網絡之間存在密切聯系。

自然免疫系統與計算機網絡都屬于復雜網絡的范疇，可以通過對雙方共性和個性的研究，探尋更好的基于自然免疫系統體系結構和原理的入侵檢測方法，為計算機安全系統的設計與維護提供新的途徑。

2、 復雜網絡的免疫策略度

是單獨節點屬性中非常重要的概念， 在某種意義上，度越大，節點越重要。大量研究表明，許多實際網絡的度可用冪律分布 P（k）∝k－γ來描述，也稱無標度分布。 這樣的網絡中， 多數節點的度相對較低，少量節點的度很高。 人們通過實證性研究發現，Internet 的和 WWW 的冪指數 γ 均位于 2 與 3 之間，屬于無標度網絡，而無標度網絡很容易受到攻擊和入侵，因此選擇合適的免疫策略尤為重要。無標度網絡目前有三種免疫策略：

1）隨機免疫

隨機免疫，也稱均勻免疫。隨機免疫策略就是通過完全隨機的方式選取網絡中的部分節點。 度大的節點（感染風險高，即連接的節點多）和度小的節點（相對安全，連接的節點少）被選取的機會是平等的。若在無標度網絡中采用這種策略，需要對幾乎所有節點都實施免疫才能杜絕病毒傳染的途徑，并且需要獲取全部節點的特征信息，難以在效率和可行性之間取得平衡。 這種方式類似于生物免疫學理論中的非特異性免疫，主要應用于個體進化的初始階段。

2）目標免疫

目標免疫，也稱選擇免疫。 根據 Internet 的無標度特性，可以選擇目標免疫策略，對少數度較大的節點進行免疫，降低與高感染風險節點相連的風險，大大降低病毒的感染規模。 目標免疫策略的效率要比隨機免疫策略更高。 這種方式類似于生物免疫學理論中的非特異性免疫， 主要應用于群體進化的全部過程。

3）熟人免疫

目標免疫策略需要事先對網絡中所有節點的度即特征信息進行全面了解， 才能準確選擇度大的節點實施免疫。 這對于龐大、復雜、多變的 Internet 來說可行性較低。因此，Cohen 等人提出一種熟人免疫策略，從 N 個節點中隨機選出比例為 p的節點，再隨機選擇每個被選節點各自的一個鄰居節點實施免疫，被免疫節點占總節點數的比例為 f（可能存在共同鄰居節點）。這種方式不需要了解所有節點的特征信息， 并且使得度大的節點被選中的概率高于度小的節點。

文獻經過實驗發現，熟人免疫和目標免疫的效果要遠好于隨機免疫， 而目標免疫的效果略好于熟人免疫。

3、 基于復雜網絡免疫策略的檢測器進化算法

3.1 算法改進思路

經仿真驗證， 基于小生境策略的檢測器生成算法能夠改善未成熟檢測器的生成效率和性能， 并且更適用于自體模式編碼較長的情況， 具體見參考文獻。

對于基于免疫的入侵檢測來說， 檢測器性能的優劣主要取決于檢測器對非自體空間的分布效果，包括檢測器對非自體空間的覆蓋率（識別區域）和檢測器間的重疊率。 親和力反映了檢測器與非自體模式之間的相似程度，即識別能力，親和力越大，兩者的相似度越高，檢測器的識別能力越強；反之，識別能力越弱。因此，在原算法中，選取 Hamming 相似度計算親和力函數作為算法搜索的依據， 并用于生成檢測器的過程， 若待選字符串與非自體集合的親和力越高，成為檢測器的可能性就越高；反之，可能性越小。 若 i 與 j 有 q 個位上的值相同，則 i 對 j 的親合力函數 g（i，j）值為：g（i，j） = q如果將復雜網絡的免疫策略應用于生物個體和群體的免疫進化，在隨機免疫中，所有個體發生進化的機會是一樣的；在目標免疫中，群體進化的方向是可以選擇的；而熟人免疫中，避免了對所有個體進行特征信息的了解， 并且能夠提高選取與非自體之間的相似程度（即親和力）的可能性。因此，本文利用基于小生境的檢測器生成算法生成未成熟檢測器，對原算法中成熟檢測器的進化做出改進， 借鑒復雜網絡的免疫策略， 提出基于復雜網絡免疫策略的檢測器進化算法。

3.2 算法描述

再次利用親和力函數優化父代檢測器的選擇。

選擇部分檢測器， 是為了通過遺傳操作有針對性地提高部分個體的適應度；采用隨機的方式選擇，是為了保持種群的多樣性； 再次選擇與被選檢測器親和力高的檢測器， 是為了避免在遺傳操作中出現嚴重的退化現象。因此，基于復雜網絡免疫策略的檢測器進化算法描述如下： a）通過基于小生境的檢測器生成算法生成未成熟的檢測器集 D，見文獻。 b）陰性選擇：淘汰與自體發生匹配的未成熟檢測器。c）成熟檢測器的進化： 在余下的未成熟檢測器中隨機抽取比例為 p 的檢測器集合 P， 再針對 P 中的每一個檢測器隨機選擇一個與其親和力最大的檢測器，形成檢測器集合 P′。 將它們作為父代，對父代進行交叉、變異、選擇等遺傳操作之后得到子代 D′。 將子代插入到父代中，得到成熟檢測器集合 R。

基本的遺傳操作同原算法一致：交叉、選擇和變異。分別采用隨機競爭選擇、單點交叉和基本位變異的方式 。 在仿真實驗中， 采用英國設菲爾德（Sheffield）大 學編寫的遺傳算法工具箱 ，交叉點數Npt=1， 交叉概率 XOVR=0.7， 變異概率 Pm=0.7/Lind，Lind 為個體的長度。 算法流程如圖 1 所示。

算法偽碼如下：Procedure Mature DetectorsBegin對 lmmature detectors D 中的 detectors 進行陰性選擇，對與自體集合 S 發生匹配的detectors 進行刪除；在 D 中余下的 detectors 隨機抽取概率為 p的 detectors，得到 P；計算 P 中 detectors 與其它 detectors 之間的親和力 g（i，j），選擇與 P 中 g（i，j）最大的detectors，得到 P′；P+P′作為父代，進行交叉、變異、選擇遺傳操作，生成子代 D′；將子代插入父代，得到 Mature detectors R；End

3.3 仿真驗證

檢測器檢測抗原的過程中可能出現兩種錯誤，一種是將異常行為當作正常，即漏檢；一種是將正常的行為當作異常，即誤檢。漏檢率和誤檢率是評價入侵檢測系統性能的重要指標。

實驗環境：CPU：Intel（R） Pentium（R） Processor1.73 GHz； HD：160 GB； RAM：1.25 GB。 方便起見，未成熟檢測器集合為 A， 本文算法進化得到的成熟檢測器集合為 B， 原算法進化后得到的成熟檢測器集合為 C。 對自體集合 S 取補產生非自體訓練數據集合 testdata。 實驗中，為在父代檢測器的數量和多樣性之間求得平衡，選擇 p = 0.5。

3.3.1 漏檢率與誤檢率

實驗條件：非自體訓練數據 testdata=10000 個，自體集合 S = 10 000 個，進制 m = 2，匹配閾值 r = 8，數據編碼長度 l = 32， 檢測器集合規模 NR=10，18，23，30，36，45，53，67，76；算法各獨立執行 50次，求漏檢率 Pf與誤檢率 Pt的平均值。 實驗結果見表 1。

實驗分析：通過表 1 可知，3 個檢測器集合檢測非自體訓練數據 testdata 得到的漏檢率 Pf和誤檢率Pt的變化趨勢均隨檢測器規模 NR的增大而降低。檢測器達到一定數量之后，Pf和 Pt降低的趨勢變緩，B集合的 Pf和 Pt均低于 A 與 C 集合。 在上述情況下，B 集合的 Pf低于 A 集合 19.17%，Pt低于 14.30%；Pf低于 C 集合 20.05%，Pt低于 12.47%。

3.3.2 編碼長度對漏檢率與誤檢率的影響

實驗條件：非自體訓練數據 testdata =10 000個，自體集合 S = 10000 個 ， 進制 m = 2， 匹配閾值r = 8，數據編碼長度 l = 16，32，64，128，256，296，檢測器集合規模 NR= 76；算法各獨立執行 50 次，求漏檢率 Pf與誤檢率 Pt的平均值。 實驗結果見表 2。

實驗分析：通過表 2 可知，隨著數據編碼長度 l的增長，3 個檢測器集合檢測非自體訓練數據 test-data 得到的 Pf和 Pt表現為增長趨勢。A 集合的 Pf和Pt增長較快，B 與 C 集合增長較緩，B 集合 Pf的平均增長率為 24.3%，C 為 24.8%；B 集合 Pt的平均增長率為 66.04%，C 為 75.12%?？傮w上 B 集合的 Pf和Pt低于 A 與 C 集合。 在上述情況下，B 集合的 Pf低于 A 集合 56.99%，Pt低于 52.23%；Pf低于 C 集合20.68%，Pt低于 19.49%。

4、 結束語

本文在基于小生境策略的檢測器生成算法的基礎上進行改進， 提出了一種基于復雜網絡免疫策略的檢測器進化算法， 以期生成性能更好的成熟檢測器。從實驗結果來看，在檢測器集合規模與數據編碼長度相同的情況下，漏檢率與誤檢率均低于原算法，并且漏檢率與誤檢率的平均增長率也略低于原算法， 適用于 IPv6 環境下數據編碼長度較長的情況，基本達到了算法最初的設計目標。

參考文獻：
1． 劉海龍 ， 張鳳斌 ， 席亮. 基 于 Monte Carlo 估 計的免疫檢測器分布優化算法 ［J］. 計算機應用， 2013， 33（3）：723-726.
2． 汪小帆 ， 李 翔 ， 陳關榮. 復雜網絡理論及其應用 ［M］.北京：清華大學出版社， 2006.
3． 李向華， 王 欣， 高 超. 復雜網絡免疫策略分析［J］. 吉林大學學報：理學版， 2013， 51（3）：444-452.
4． Madar N， Kalisky T， Cohen R， et al. Immunization andepidemics in complex networks ［J］. The European PhysicalJournal B-Condensed Matter and Complex Systems，2004，38（2）：269-276.
5． 時 晨， 申普兵， 沈向余， 等. 基于小生境策略的檢測器生成算法［J］. 計算機技術與發展， 2011， 21（9）：81-84．