蔣亞平，趙軍偉，馬亞瓊，田月霞

（鄭州輕工業(yè)學(xué)院 計算機與通信工程學(xué)院，河南 鄭州450001）

0 引 言

生物免疫系統(tǒng)是一個自學(xué)習(xí)、自組織和自適應(yīng)系統(tǒng)，能夠有效地抵御抗原的入侵［1］。人工免疫系統(tǒng)就是受生物免疫系統(tǒng)的啟發(fā)而發(fā)展起來的，并被應(yīng)用于網(wǎng)絡(luò)入侵檢測領(lǐng)域。其中，檢測器生成算法是入侵檢測系統(tǒng)的核心，決定著系統(tǒng)的性能和效率［2］。1994年Forrest等最早提出否定選擇算法 （negative selection algorithm，NSA）［3］，并首次實現(xiàn)檢測器的耐受［4］，此后，高效的檢測器生成模型逐漸成為一個研究熱點。

國內(nèi)學(xué)者李濤、焦李成、莫宏偉等進(jìn)行了相應(yīng)的研究，并取得了一定的成果［5－7］。文獻(xiàn) ［8］提出了一種改進(jìn)的否定選擇算法，通過減少匹配檢測器的數(shù)量提高了檢測器的覆蓋率，但檢測器生成算法中使用的是固定閾值，即確定性方法。文獻(xiàn) ［9］提出了一種基于模糊匹配的檢測器生成算法，提高了檢測器的檢測效率，但不能去除克隆變異后檢測器集合內(nèi)可能存在的冗余。針對以上算法的不足，本文提出一種基于免疫識別的最小檢測器生成模型，通過免疫識別算法解決邊界檢測器的識別問題，克隆選擇和變異算法能夠產(chǎn)生高效的檢測器，并通過冗余優(yōu)化算法去除檢測器冗余，最終得到最小有效檢測器集合。

1 形態(tài)空間理論與免疫識別

1.1 檢測器的形態(tài)空間分析

Perelson和Oster提出免疫事件都在形態(tài)空間S（shapespace）中發(fā)生［10］。因此形態(tài)空間中有一體積為V 的區(qū)域，包含著抗體和抗原及其形狀互補區(qū)域。抗體識別抗原就是其與抗原匹配并結(jié)合的過程，這種匹配并不是完全精確的匹配，只要積累的親和力超過一定的閾值即可。由于采用不完全匹配機制，一種抗體可以識別多種抗原，從而可以利用有限數(shù)量的抗體及其覆蓋區(qū)域來識別盡可能多的抗原。

如圖1所示，X為抗原，大圓代表形態(tài)空間S（體積為V），小圓表示抗體及其匹配范圍，半徑為ε，n為空間內(nèi)的抗體個數(shù)，Vε為抗原覆蓋空間，那么每個抗原可由nVε／V個不同的抗體識別，其不被識別的概率為

由式 （1）可知，V不變的情況下要降低P 就要增大nVε的值，而檢測器集合的大小即n值往往有限制，因此有必要去除檢測器集合的冗余，利用盡可能小的檢測器集合覆蓋更大的抗原空間。

圖1 形態(tài)空間

1.2 基于隸屬度的免疫識別

入侵檢測系統(tǒng)檢測過程中難免出現(xiàn)誤檢和漏檢，主要是因為某些檢測器在形態(tài)空間中處于 “非我”空間的邊緣，它們接近于 “非我”但嚴(yán)格來說卻不屬于 “非我”空間，即它們具體是否隸屬于 “非我”集合是個模糊的概念。目前常用算法在區(qū)分邊界檢測器時采用的都是確定性方法，即采用固定閾值來衡量匹配程度，因此難以生成有效的檢測器，最終造成入侵檢測系統(tǒng)誤檢或漏檢的發(fā)生。因此，為了生成高效的檢測器，本文在抗體進(jìn)化過程中采用基于隸屬度的免疫識別算法代替?zhèn)鹘y(tǒng)的否定選擇算法，通過隸屬度代替確定性方法中的匹配閾值以篩選出邊界檢測器。

2 基于免疫識別的檢測器生成模型

2.1 相關(guān)定義

定義1 自體／非自體：所有的數(shù)據(jù)包組成集合U［0，1］l，正常的數(shù)據(jù)包定義為自體集合selfU；非正常的數(shù)據(jù)包定義為非自體集合nonselfU［11］。D表示檢測器集合，分為初始檢測器D0、成熟檢測器Dmat、最小檢測器Dmin、邊界檢測器Dbounds四類。D中的元素di，i∈［1，ξ］為一個檢測器，ξ為D中元素的個數(shù)。

定義2 貼近度：貼近度表征兩個字符串的相似程度，字符串L1和L2的貼近度計算如下

定義3 隸屬度：隸屬度代表字符串對字符串集合的隸屬程度，那么di與非自體集合的隸屬度可以用di與nonself中元素 （nonselfj，j∈ ［1，m］）的貼近度的加權(quán)值表示，權(quán)值設(shè)為其中x為隨機抽取的子集包含的樣本數(shù)量，即

定義4 最大相似位：設(shè)有字符串L1和L2，其中L1＝X1X2X3···Xl，L2＝Y(jié)1Y2Y3···Yl，Xi，j（1≤i≤j≤l）為字符串L2在L1中對應(yīng)位置上相同的子串，那么最大 相 似 位 max（L1，L2）＝ max（Len（Xi，j））， 其 中max（Len（Xi，j））表示所有連續(xù)相同子串長度的最大值。

2.2 模型描述

檢測器生成模型如圖2所示，隨機產(chǎn)生的初始檢測器首先經(jīng)過與非自體集的免疫識別過程，通過計算隸屬度將初始檢測器分為三類 （成熟檢測器、邊界檢測器以及未通過耐受的檢測器）。其中，成熟檢測器直接加入成熟檢測器Dmat，未通過耐受的檢測器直接被丟棄，邊界檢測器作為父代檢測器并經(jīng)過克隆選擇和變異過程，將滿足條件的邊界檢測器加入成熟檢測器Dmat，經(jīng)過冗余優(yōu)化算法最終生成最小檢測器。

圖2 最小檢測器生成模型

3 最小檢測器生成算法及理論驗證

3.1 免疫識別過程

計算檢測器與非自體集的隸屬度，并將隸屬度分為3個模糊區(qū)間。對實驗生成的模式空間進(jìn)行抽樣，統(tǒng)計結(jié)果大致成正態(tài)分布 （如圖3所示），其中相應(yīng)區(qū)間隨參數(shù)a、b（0＜a＜b＜1）的確定而確定，分別為：［0，a），［a，b），［b，1］，根據(jù)圖3可知a取0.46，b取0.55較為合理。算法具體步驟如下：

步驟1 準(zhǔn)備：①確定self、nonself的描述形式；②定義非自體，構(gòu)造非自體集；③確定隸屬度的計算方法。

步驟2 初始化：隨機生成初始檢測器D0，其中di∈D0，i∈ ［1，ξ］，ξ為初始檢測器的檢測器個數(shù)。

步驟3 免疫識別：隨機抽取非自體集的一部分作為子集 （包含x個樣本），計算di與子集的隸屬度，并重復(fù)該過程m次。如果在m次計算中有任何一次的隸屬度小于a，則該檢測器未通過自體耐受而被丟棄；如果隸屬度大于b的次數(shù)不少于隸屬度大于a的次數(shù)，則將該檢測器加入成熟檢測器Dmat；如果隸屬度大于b的次數(shù)少于隸屬度大于a的次數(shù)，則將其加入邊界檢測器Dbounds。

步驟4 克隆選擇與變異：邊界檢測器Dbounds中的檢測器通過克隆選擇、交叉變異直至隸屬度滿足要求或達(dá)到最大進(jìn)化代數(shù)。

步驟5 若D0中所有檢測器都通過免疫識別，則免疫識別過程結(jié)束，得到成熟檢測器集合Dmat；否則轉(zhuǎn)到步驟3。

圖3 隸屬度抽樣結(jié)果

3.2 冗余優(yōu)化算法

通過免疫識別的檢測器即為成熟檢測器Dmat，然后經(jīng)過冗余優(yōu)化算法生成最小檢測器。冗余優(yōu)化算法的具體步驟如下，其中D［i］為當(dāng)前的檢測器；D［k］為未進(jìn)行匹配的檢測器；θ為匹配閾值，NR為預(yù)設(shè)的最小檢測器數(shù)目。

步驟1 產(chǎn)生成熟檢測器集合Dmat，確定檢測器個數(shù)n，并初始化匹配閾值θ；

步驟2 設(shè)置循環(huán)變量i和k（k＝i＋1：n），取當(dāng)前檢測器D［i］與Dmat中的檢測器D［k］進(jìn)行匹配；

步驟3 若D［i］與所有的D［k］都進(jìn)行了匹配，則加入最小檢測器Dmin，轉(zhuǎn)到步驟6；

步驟4 否則D［i］與下一個D［k］進(jìn)行匹配，計算D［i］與當(dāng)前D［k］的最大連續(xù)相似位 max（D［i］，D［k］）；

步驟5 若max（D［i］，D［k］）大于或等于閾值θ，則刪掉D［i］，轉(zhuǎn)到步驟6；否則轉(zhuǎn)到步驟3；

步驟6 若檢測器集合Dmat中所有檢測器都進(jìn)行了匹配，轉(zhuǎn)到步驟7；否則轉(zhuǎn)到步驟2。

步驟7 若當(dāng)前檢測器Dmin中檢測器的數(shù)目小于NR，轉(zhuǎn)到步驟1；否則算法結(jié)束，最終生成的Dmin即為最小檢測器。

3.3 理論分析

設(shè)Pm為成熟檢測器Dmat中的兩個隨機串的匹配概率，那么在r連續(xù)位匹配規(guī)則下則有

式中：l——字符串的長度。假設(shè)NR為最小有效檢測器的數(shù)目，那么可得系統(tǒng)的漏報率pf和檢測率pt分別為

對式 （5）兩邊取對數(shù)，可得最小檢測器的數(shù)量為

由式 （7）可知，對于固定的字符串和匹配閾值，在一定漏報率Pf和檢測率Pt之內(nèi)的檢測器數(shù)量與自我集的規(guī)模無關(guān)，即有效檢測器的數(shù)量不隨被保護(hù)的自我集的增大而增加，因此，NR即為最小檢測器集合中檢測器的數(shù)目。

4 仿真實驗

仿真環(huán)境與參數(shù)設(shè)置：用randerr（120，13，［0：13］）函數(shù)隨機生成150個二進(jìn)制串 （l＝13）作為自我集，并隨機生成100個字符串組成非我集，初始檢測器包含60個抗體，并構(gòu)造長度為l的模式空間 （8000個字符串）。隸屬度區(qū)間邊界參數(shù)a＝0.46，b＝0.55，選取冗余優(yōu)化閾值θ＝9，Pf＝0.08時NR取48。本算法與經(jīng)典的否定選擇算法在相同的檢測器個數(shù)及匹配閾值的情況下進(jìn)行覆蓋空間的比較，實驗結(jié)果如圖4所示。

圖4 兩種算法覆蓋空間和空間覆蓋率的比較 （θ＝9）

為了驗證匹配閾值對本算法的影響，其它參數(shù)不變的情況下選取冗余優(yōu)化閾值θ＝11進(jìn)行另一組實驗，實驗結(jié)果如圖5所示。

由圖4和圖5可知，匹配閾值不同的情況下，改進(jìn)算法的覆蓋檢測器個數(shù)和空間覆蓋率在整體上均高于經(jīng)典算法，但兩種算法的結(jié)果均有跳變現(xiàn)象，這與字符串生成的隨機性和長度限制有關(guān)。

圖5 兩種算法覆蓋空間和空間覆蓋率的比較 （θ＝11）

檢測器整體性能可通過TP值 （檢測率）和FP值 （誤報率）來衡量。分別對改進(jìn)算法和文獻(xiàn) ［12］算法進(jìn)行三次測試，實驗統(tǒng)計結(jié)果及平均值見表1。

表1 兩種算法實驗結(jié)果對比

由表1可知，改進(jìn)算法的檢測結(jié)果優(yōu)于文獻(xiàn) ［12］算法，平均TP值提高了2.32%，而FP值降低了2.53%。究其原因是改進(jìn)算法采用免疫識別算法更好地模擬了生物免疫系統(tǒng)的機理，克隆選擇和變異算法提高了檢測器的整體質(zhì)量，因而檢測效果較為理想。

5 結(jié)束語

本文基于形態(tài)空間分析了檢測器集合去除冗余的必要性，通過對模式空間進(jìn)行抽樣給出了檢測器邊界區(qū)間參數(shù)的選取依據(jù)，在免疫識別、克隆選擇、變異算法以及冗余優(yōu)化算法的基礎(chǔ)上建立了基于免疫識別的最小檢測器生成模型并通過理論驗證給出了最小檢測器的概念。該模型的核心在于采用基于隸屬度的免疫識別算法識別邊界檢測器，同時通過冗余優(yōu)化算法去除成熟檢測器的冗余，最終生成最小有效檢測器。實驗結(jié)果表明本模型可以產(chǎn)生高效的檢測器，與傳統(tǒng)模型相比具有更好的檢測效果。

［1］Dasgupta D，Yua S，Nino F.Recent advances in artificial immune systems：Models and applications ［J］.Applied Soft Computing，2011，11 （2）：1574－1578.

［2］YANG Dongyong，CHEN Jinyin.Research on detector gene－ration algorithm based on multiple populations GA ［J］.Acta Automatica Sinica，2009，35 （4）：425－432 （in Chinese）.［楊東勇，陳晉音.基于多種群遺傳算法的檢測器生成算法研究 ［J］.自動化學(xué)報，2009，35 （4）：425－432.］

［3］JIANG Yaping，LV Tingqin，GAN Yong.A network security prevention model based on vaccine ［J］.Journal of Northeastern University （Natural Science），2011，32 （51）：204－207 （in Chinese）.［蔣亞平，呂廷勤，甘勇.基于疫苗接種的網(wǎng)絡(luò)安全防御模型 ［J］.東北大學(xué)學(xué)報：自然科學(xué)版，2011，32 （51）：204－207.］

［4］JIN Zhangzan，LIAO Minghong，XIAO Gang.Survey of negative selection algorithms ［J］.Journal on Communications，2013，34（1）：159－170 （in Chinese）.［金章贊，廖明宏，肖剛.否定選擇算法綜述 ［J］.通信學(xué)報，2013，34 （1）：159－170.］

［5］JIAO Licheng，DU Haifeng，LIU Fang，et al.The immune optimization，learning and recognition ［M］.Beijing：Science Press，2006：26－31（in Chinese）. ［焦李成，杜海峰，劉芳，等.免疫優(yōu)化計算、學(xué)習(xí)與識別 ［M］.北京：科學(xué)出版社，2006：26－31.］

［6］LI Tao.Idid：A model of dynamic intrusion detection based on immune ［J］.Chinese Science Bulletin，2009，50 （17）：1912－1919（in Chinese）.［李濤.Idid：一種基于免疫的動態(tài)入侵檢測模型 ［J］.科學(xué)通報，2009，50 （17）：1912－1919.］

［7］MO Hongwei，F(xiàn)U Dongmei，XU Lifang.Research of a kind of improved immune controller based immune network ［J］.International Journal of Intelligent Computing and Cybernetics，2010，3 （2）：310－333.

［8］HU Liang，WANG Chengming，ZHAO Kuo.Research and improvement of detector generation algorithm in intrusion detection system based on artificial immune model ［J］.Journal of Jilin University，2010，48 （1）：67－72 （in Chinese）.［胡亮，王程明，趙闊.基于人工免疫模型的入侵檢測系統(tǒng)中檢測器生成算法的分析與改進(jìn) ［J］.吉林大學(xué)學(xué)報，2010，48 （1）：67－72.］

［9］WANG Hui，YU Lijun，WANG Keji.An adjustable fuzzy matching negative selection algorithm ［J］.Transactions on Intelligent Systems，2011，6 （2）：178－184 （in Chinese）. ［王輝，于立君，王科技.一種可變模糊匹配陰性選擇算法 ［J］.智能系統(tǒng)學(xué)報，2011，6 （2）：178－184.］

［10］LI Tao.The model of computer virus dynamic detection based on immune ［J］.Science in China，2009，33 （4）：422－430（in Chinese）.［李濤.基于免疫的計算機病毒動態(tài)檢測模型［J］.中國科學(xué)，2009，39 （4）：422－430.］

［11］ZHANG Dengyong，GONG Rongrong，PENG Jian.Model of network intrusion detection based on mended negative selection arithmetic ［J］.Computer Engineering and Design，2009，30 （11）：2663－2665 （in Chinese）.［章登勇，宮蓉蓉，彭建.基于改進(jìn)否定選擇算法的網(wǎng)絡(luò)入侵檢測模型 ［J］.計算機工程與設(shè)計，2009，30 （11）：2663－2665.］

［12］Zhou Ji，Dasgupta D.Real－valued negative selection algorithm with variable－sized detectors ［G］.LNCS 3102：Proceedings of GECCO.Berlin：Springer，2007：287－298.