蔣亞平,趙軍偉,馬亞瓊,田月霞
(鄭州輕工業(yè)學(xué)院 計(jì)算機(jī)與通信工程學(xué)院,河南 鄭州450001)
生物免疫系統(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è)器集合。
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)空間
入侵檢測(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è)器。
定義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)度的最大值。
檢測(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è)器生成模型
計(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é)果
通過(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è)器。
設(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ù)目。
仿真環(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è)效果較為理想。
本文基于形態(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.