基于免疫識(shí)別的最小檢測(cè)器生成模型

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

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

0 引 言

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

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

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

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

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

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

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

圖1 形態(tài)空間

1.2 基于隸屬度的免疫識(shí)別

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

2 基于免疫識(shí)別的檢測(cè)器生成模型

2.1 相關(guān)定義

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

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

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

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

2.2 模型描述

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

圖2 最小檢測(cè)器生成模型

3 最小檢測(cè)器生成算法及理論驗(yàn)證

3.1 免疫識(shí)別過(guò)程

計(jì)算檢測(cè)器與非自體集的隸屬度，并將隸屬度分為3個(gè)模糊區(qū)間。對(duì)實(shí)驗(yàn)生成的模式空間進(jìn)行抽樣，統(tǒng)計(jì)結(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)造非自體集；③確定隸屬度的計(jì)算方法。

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

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

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

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

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

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

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

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

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

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

步驟4 否則D［i］與下一個(gè)D［k］進(jìn)行匹配，計(jì)算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 若檢測(cè)器集合Dmat中所有檢測(cè)器都進(jìn)行了匹配，轉(zhuǎn)到步驟7；否則轉(zhuǎn)到步驟2。

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

3.3 理論分析

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

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

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

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

4 仿真實(shí)驗(yàn)

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

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

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

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

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

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

表1 兩種算法實(shí)驗(yàn)結(jié)果對(duì)比

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

5 結(jié)束語(yǔ)

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

［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）.［楊東勇，陳晉音.基于多種群遺傳算法的檢測(cè)器生成算法研究 ［J］.自動(dòng)化學(xué)報(bào)，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é)報(bào)：自然科學(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é)報(bào)，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)化計(jì)算、學(xué)習(xí)與識(shí)別 ［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：一種基于免疫的動(dòng)態(tài)入侵檢測(cè)模型 ［J］.科學(xué)通報(bào)，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）.［胡亮，王程明，趙闊.基于人工免疫模型的入侵檢測(cè)系統(tǒng)中檢測(cè)器生成算法的分析與改進(jìn) ［J］.吉林大學(xué)學(xué)報(bào)，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é)報(bào)，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）.［李濤.基于免疫的計(jì)算機(jī)病毒動(dòng)態(tài)檢測(cè)模型［J］.中國(guó)科學(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ò)入侵檢測(cè)模型 ［J］.計(jì)算機(jī)工程與設(shè)計(jì)，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.