魏明軍,王月月,金建國

(華北理工大學(xué)信息工程學(xué)院,河北唐山 063009)

?

一種改進免疫算法的入侵檢測設(shè)計

魏明軍,王月月,金建國

(華北理工大學(xué)信息工程學(xué)院,河北唐山 063009)

摘要:為提高入侵檢測的檢測效率和降低誤報率,在多種群免疫算法和克隆選擇算法的基礎(chǔ)上,提出多種群克隆選擇算法.針對該算法改進了匹配規(guī)則,并且采用KDDCUP99數(shù)據(jù)集的10%抽樣數(shù)據(jù)進行仿真實驗.該數(shù)據(jù)集每條記錄有固定的41個屬性,選取基于單個傳輸控制協(xié)議連接基本特征的9個屬性進行研究.根據(jù)數(shù)據(jù)集的特點,結(jié)合多種群克隆選擇算法,把經(jīng)過編碼、去重的4種攻擊類型數(shù)據(jù)作為多種群克隆選擇算法的初始種群進行免疫操作,輸出最優(yōu)群體.根據(jù)正常數(shù)據(jù)遠大于異常數(shù)據(jù)的原則,混合4種攻擊類型的測試數(shù)據(jù)集通過自體集進行過濾,過濾后的數(shù)據(jù)與最優(yōu)群體進行匹配.實驗結(jié)果表明,其能夠有效識別異常數(shù)據(jù).經(jīng)過對比分析可得,多種群克隆選擇算法和改進的匹配規(guī)則能夠提高入侵檢測的檢測率.

關(guān)鍵詞:入侵檢測;免疫系統(tǒng);多種群克隆選擇算法;匹配;屬性

人工免疫系統(tǒng)是模仿生物免疫系統(tǒng)建立起來的多智能系統(tǒng).生物免疫系統(tǒng)是一個健壯的、復(fù)雜的、保護身體免受外來病原體入侵的自適應(yīng)系統(tǒng),它將身體內(nèi)的所有細胞(或分子)區(qū)分為自我或異我物質(zhì)[1].人工免疫系統(tǒng)繼承了生物免疫系統(tǒng)的這些特征,來解決許多計算機安全面臨的問題[2].人工免疫應(yīng)用于入侵檢測首先是由文獻[3]提出的,其把計算機安全問題和免疫系統(tǒng)學(xué)習(xí)區(qū)分自我——非自我相結(jié)合,提出了陰性選擇算法,為后續(xù)研究人員將免疫機制引入入侵檢測領(lǐng)域開啟了序幕.之后,免疫理論和算法在入侵檢測領(lǐng)域蓬勃發(fā)展,相繼提出了克隆選擇[4]、動態(tài)克隆[5]、樹突細胞[6]等算法.同時,研究人員還將許多智能算法與人工免疫相結(jié)合,提出免疫遺傳算法、免疫聚類算法、免疫進化算法、免疫神經(jīng)網(wǎng)絡(luò)等算法,應(yīng)用于入侵檢測領(lǐng)域[7-10].

這些算法在入侵檢測領(lǐng)域的研究和發(fā)展方面發(fā)揮了巨大作用,尤其是陰性選擇算法,因其簡便并易于編程而被廣泛應(yīng)用.但它們依然存在很多缺陷和困難,不能產(chǎn)生與生物免疫系統(tǒng)一樣的高性能:將陰性選擇算法用于解決網(wǎng)絡(luò)入侵檢測問題時,會導(dǎo)致規(guī)模性問題,并產(chǎn)生大量的無用檢測器而導(dǎo)致誤報漏報;克隆選擇算法可能把克隆變異時產(chǎn)生的新的抗原放入到正常數(shù)據(jù)集中,導(dǎo)致漏報;動態(tài)克隆選擇算法實現(xiàn)了正常數(shù)據(jù)集的自動更新,但過程較慢;免疫遺傳算法復(fù)雜度較高,不易于編程實現(xiàn),且耗時長、檢測速度慢,無法在大數(shù)據(jù)量下進行快速匹配[8-10].

而且,較典型的免疫算法,如陰性選擇算法、克隆選擇算法等都涉及到模式匹配過程.比較典型的匹配規(guī)則有,基于字符串匹配的Boyer-Moore匹配算法、r匹配規(guī)則、基于概率統(tǒng)計的匹配規(guī)則、Landscape-affinity matching、海明距離匹配規(guī)則及其變體、基于實值向量匹配的雙向批判規(guī)則、空間包含匹配規(guī)則、閔可夫斯基距離和隸屬函數(shù).匹配算法的性能對檢測的誤報率、漏報率有直接影響.

針對這些問題,研究人員在這些算法的基礎(chǔ)上進行了許多改進:把抗體濃度與抗體-抗原親和力相結(jié)合,通過抗體濃度抑制來達到免疫調(diào)節(jié)的目的;提出高低頻變異方法解決檢測器冗余、重疊問題;將免疫優(yōu)勢理論運用到克隆選擇算法中,通過免疫優(yōu)勢算子實現(xiàn)先驗知識的動態(tài)獲得和不同個體之間的資源共享;“非自體”空間覆蓋程度方面提出球狀實體檢測器能夠更好地覆蓋“非我”空間等;為避免群體因過早收斂而得不到最優(yōu)解,提出多種群免疫算法、雙倍體免疫算法等[11-13].

筆者將多種群免疫算法的初始種群特殊化,提出基于Hightower匹配算法的r匹配算法,以達到提高入侵檢測的檢測率、降低漏報率的目的.

1 多種群克隆選擇算法

文獻[14]提出的多種群免疫算法是借鑒遺傳算法中采用并行機制避免局部收斂的思想,在免疫算法中建立多個初始種群,分別進行克隆變異操作,并且在群體之間進行免疫操作,以達到更高的平衡狀態(tài).該算法加入了免疫記憶、免疫疫苗的概念,還加入了雜交算子、傳優(yōu)算子等免疫算子,理解起來比較困難,也不易于編程實現(xiàn).

克隆選擇算法作為人工免疫中的一個基礎(chǔ)算法,多種群免疫算法等都借鑒了它的克隆變異理論.相較于多種群免疫算法,克隆選擇算法易于理解編程,但它只有一個初始種群,經(jīng)過多次進化后,可能進入局部收斂,得不到最優(yōu)解.

文中結(jié)合這兩種算法的優(yōu)勢,采用克隆選擇算法,借鑒多種群思想,將克隆選擇算法隨機生成初始種群優(yōu)化為隨機生成多個初始種群,即多種群克隆選擇算法(Multi-Colony Clonal Selection Algorithm,MCCSA).

多種群克隆選擇算法中隨機生成初始種群,保證了種群隨機性,但也有可能因為其隨機性而導(dǎo)致某些特性丟失.因此,可根據(jù)實驗數(shù)據(jù)人為選擇或確定初始種群,以保證種群完整性和多樣性.

1.1 數(shù)據(jù)集及研究屬性選取

文中將研究者經(jīng)常使用的KDDCUP99數(shù)據(jù)集的10%抽樣數(shù)據(jù)作為實驗數(shù)據(jù).KDDCUP99訓(xùn)練數(shù)據(jù)集中每條連接記錄包含了41個固定的特征屬性.在41個固定的特征屬性中,既有離散型屬性,又有連續(xù)型屬性.因此,實驗選取的研究屬性也必須包含離散型和連續(xù)型.

考慮到應(yīng)選擇對判斷數(shù)據(jù)是否異常有正面影響的屬性進行研究,文中采用文獻[15]提出的方法:利用平均值來計算連續(xù)屬性對判斷數(shù)據(jù)是否異常有無正面影響.屬性在自體集的平均值(aself)和非自體集的平均值(anonself)之差與屬性在整個集合中的平均值(aall)的比率越大,該屬性越有益于判斷數(shù)據(jù)是否異常,其表達式為因此,要選擇R值較大的連續(xù)屬性進行研究.

綜合上述因素,文中選取基于單個傳輸控制協(xié)議(Transmission Control Protocol,TCP)連接的基本特征的9個屬性進行研究.這些屬性既包含連續(xù)型,又包含離散型,連續(xù)型屬性的R較大,但度量集相同(都是描述單個TCP連接的基本特征).這些屬性的特征名、類型及連續(xù)屬性的R值如表1所示.

表1 選取研究的屬性及R值

1.2 初始種群特殊化處理

二進制是計算機最熟悉的語言,現(xiàn)實世界的事物也經(jīng)常被抽象或轉(zhuǎn)化成二進制數(shù)據(jù)被計算機識別.文中就是基于二進制數(shù)據(jù)進行免疫算法設(shè)計的.同時,為保證多種群克隆選擇算法初始種群的完整性與多樣性,要根據(jù)KDDCUP99數(shù)據(jù)集人為選擇或確定初始種群.因此,數(shù)據(jù)集要經(jīng)過預(yù)處理.

首先,將數(shù)據(jù)源轉(zhuǎn)換成二進制編碼:duration、src_bytes、dst_bytes屬性轉(zhuǎn)換成16位二進制字符串,protocol_type、flag、wrong_fragment、urgent轉(zhuǎn)換成4位二進制字符串,service轉(zhuǎn)換成7位二進制串,land僅有0、1形態(tài),不必轉(zhuǎn)換.即每條數(shù)據(jù)記錄轉(zhuǎn)換成72位二進制字符串.

其次,去除重復(fù)數(shù)據(jù)記錄:因文中選取了9個屬性進行分析,可能不同攻擊標識的數(shù)據(jù)記錄對應(yīng)的這9個屬性的值是相同的,為避免大量重復(fù)數(shù)據(jù)造成數(shù)據(jù)量過大及重復(fù)計算,僅保留1條相同記錄.經(jīng)去重運算后,normal標識數(shù)據(jù)為56 083條,DoS攻擊數(shù)據(jù)為183條,probing攻擊數(shù)據(jù)為223條,R2L攻擊數(shù)據(jù)為314 條,U2R攻擊數(shù)據(jù)為50條.

文中根據(jù)去重結(jié)果,把去重后的這4種攻擊類型數(shù)據(jù)作為多種群克隆選擇算法的4個初始種群.

2 r匹配規(guī)則及其改進

經(jīng)多種群克隆選擇算法輸出最佳方案后,待檢測數(shù)據(jù)還需與其進行匹配.匹配規(guī)則多采用r匹配規(guī)則.r匹配規(guī)則有兩種,即r位匹配和r連續(xù)位匹配.圖1和圖2分別表示r位匹配規(guī)則和r連續(xù)位匹配規(guī)則(r=6).

圖1 r位匹配規(guī)則示意圖　

圖2 r連續(xù)位匹配規(guī)則示意圖

文中實驗數(shù)據(jù)的每條記錄都是由多個屬性的二進制字符串組成的,直接使用r匹配規(guī)則難免會遇到下面描述的問題.設(shè)1條數(shù)據(jù)記錄由3個屬性組成(字符串1,字符串2,字符串3),如圖3所示,A為正常數(shù)據(jù),B為異常數(shù)據(jù),A與B應(yīng)不匹配,若采用r連續(xù)位匹配規(guī)則,令r=7,則會判定B與A匹配.

增加r的取值,可避免圖3所示的失誤.但是,隨著r值的增加,匹配概率會不斷降低,會影響最后的檢測效果.在字符串長度n相同的情況下,r值越大,匹配概率越小;r值越小,匹配概率越大.因此,在r匹配規(guī)則中,r值的選取尤為重要.

為獲得最優(yōu)r值,需要通過試驗進行多次測試.文中的實驗數(shù)據(jù)集經(jīng)過處理后,每條記錄的二進制字符串長度為72,但因長度過長,不易測試最佳r值.

圖3 r(r=7)匹配規(guī)則失誤圖示意圖

為使匹配結(jié)果更為準確,文中改進了匹配規(guī)則.把每條數(shù)據(jù)記錄按屬性進行劃分,對每個屬性的字符串采用Hightower提出的匹配算法,然后,對整條數(shù)據(jù)記錄采用r位匹配.

Hightower提出的匹配算法[16]描述如下:

(1)兩條數(shù)據(jù)記錄對應(yīng)屬性的二進制串進行異或操作,若對應(yīng)的二進制編碼相同,則記為1,若不同,則為0,結(jié)果統(tǒng)記為c.

(2)將對應(yīng)屬性的二進制串逐位進行異或操作結(jié)果的累積和,記為

(3)由兩個或者更多個1組成的每一連續(xù)區(qū)域的長度記為l,將它們的最大值記為L.

(5)返回步驟(1),循環(huán)執(zhí)行下一屬性,得到每個屬性的L值與結(jié)合度.

每個屬性設(shè)定一個ri值,然后根據(jù)r連續(xù)位匹配規(guī)則(其中r=ri)判斷該屬性是否匹配.若L≥r,則判定該屬性是r連續(xù)位匹配的.針對一條數(shù)據(jù)記錄再設(shè)定一個r值,若該條數(shù)據(jù)記錄有r個屬性匹配,則判定該條數(shù)據(jù)記錄匹配.以圖3數(shù)據(jù)為例,設(shè)r1=3,r2=4,r3=3,r=2,則屬性1、屬性3不匹配,屬性2匹配,即有1個屬性匹配,不滿足r位匹配規(guī)則(r=2),B與A不匹配,如圖4所示.

同時,根據(jù)式(3),可得出兩條數(shù)據(jù)記錄相應(yīng)屬性的結(jié)合度,結(jié)合度之和記為兩條數(shù)據(jù)記錄的結(jié)合度M.設(shè)定一個閾值Mr,若種群中每個個體的結(jié)合度Mi≥Mr,則該種群記為最優(yōu)解,即以結(jié)合度作為適應(yīng)度函數(shù)的評價標準.

圖4 改進匹配規(guī)則示意圖

3 仿真實驗及結(jié)果分析

在真實情況下,正常數(shù)據(jù)遠大于異常數(shù)據(jù),因此,在多種群克隆選擇算法之前,先對測試集進行過濾.過濾方法如下:在去重normal標識數(shù)據(jù)中隨機選取若干數(shù)據(jù)構(gòu)成自體集,根據(jù)r匹配規(guī)則,選取適當(dāng)?shù)膔值,對每個屬性進行匹配,若匹配,則為正常數(shù)據(jù),過濾掉;若不匹配,則與多種群克隆選擇算法輸出的最優(yōu)群體進行匹配.

對數(shù)據(jù)經(jīng)過編碼、去重運算后,接下來確定匹配規(guī)則中r的取值.整個實驗中有4類r值需要確定:過濾匹配時每個屬性的ri值,過濾匹配時測試集每條數(shù)據(jù)記錄的r值,多種群克隆選擇算法匹配時每個屬性的ri值,多種群克隆選擇算法匹配時每條數(shù)據(jù)記錄的r值.

分別選取不同數(shù)據(jù)集進行測試,經(jīng)過多次測試,選定最優(yōu)r值.圖5是不同測試集時,多種群克隆選擇算法匹配時每條數(shù)據(jù)記錄不同r值下的誤報率.

圖5 r與誤報率的關(guān)系示意圖

表2為最優(yōu)r值下,混合數(shù)據(jù)集(測試數(shù)據(jù)集中包含所有攻擊類型)的測試結(jié)果.其中,過濾匹配時每個屬性的ri值設(shè)定為:ri=[0.9L](其中,L為該屬性字符串的長度,[·]為取整運算),每條數(shù)據(jù)記錄的r值為8;過濾后數(shù)據(jù)匹配時每個屬性的ri值為:ri=[0.8L],每條數(shù)據(jù)記錄的r值為9.

表2 混合數(shù)據(jù)集測試結(jié)果

同時,將文中多種群克隆選擇算法的實驗結(jié)果(表2平均值)與一些經(jīng)典算法進行比較,結(jié)果如表3所示.

表3 3種算法的測試結(jié)果比較

由上述對比可知,文中算法的檢測率明顯提高,雖然誤報率稍微偏高,但總體實驗效果較理想.

4 結(jié)束語

采用KDDCUP99數(shù)據(jù)集的10%抽樣數(shù)據(jù),選取基于單個TCP連接基本特征的9個屬性進行實驗.首先,將混合攻擊類型數(shù)據(jù)集進行編碼、去重、過濾操作;然后,過濾后的數(shù)據(jù)與多種群克隆選擇算法生成的最優(yōu)群體進行匹配.匹配結(jié)果表明,文中算法能夠有效識別異常數(shù)據(jù),取得了較好的檢測結(jié)果.接下來的研究重點就是針對不同攻擊類型的數(shù)據(jù)集進行實驗分析,同時優(yōu)化算法來降低誤報率.

參考文獻:

[1]BURKE E K,KENDALL G.Search Methodologies:Introductory Tutorials in Optimization and Decision Support Techniques[M].2nd Edition.Berlin:Springer Verlag,2014.

[2]ZHANG L,BAI Z Y,LU Y L,et al.Integrated Intrusion Detection Model Based on Artificial Immune[J].The Journal of China Universities of Posts and Telecommunications,2014,21(2):83-90.

[3]POGGIOLINI M,ENGELBRECHT A.Application of the Feature-detection Rule to the Negative Selection Algorithm [J].Expert Systems with Applications,2013,40(8):3001-3014.

[4]DAI H W,YANG Y,LI H,et al.Bi-direction Quantum Crossover-based Clonal Selection Algorithm and Its Applications[J].Expert Systems with Applications,2014,41(16):7248-7258.

[5]HONG Y Y,LIAO W J.Optimal Passive Filter Planning Considering Probabilistic Parameters Using Cumulant and Adaptive Dynamic Clone Selection Algorithm[J].International Journal of Electrical Power& Energy Systems,2013,45(1):159-166.

[6]GU F,GREENSMITH J,AICKELIN U.Theoretical Formulation and Analysis of the Deterministic Dendritic Cell Algorithm[J].Biosystems,2013,111(2):127-135.

[7]SILVA G C,PALHARES R M,CAMINHAS W M.Immune Inspired Fault Detection and Diagnosis:a Fuzzy-based Approach of the Negative Selection Algorithm and Participatory Clustering[J].Expert Systems with Applications,2012,39(16):12474-12486.

[8]LIU R C,JIAO L C,ZHANG X R,et al.Gene Transposon Based Clone Selection Algorithm for Automatic Clustering [J].Information Sciences,2012,204(30):1-22.

[9]劉星寶,蔡自興,王勇,等.用于全局優(yōu)化問題的混合免疫進化算法[J].西安電子科技大學(xué)學(xué)報,2010,37(5):971-980.LIU Xingbao,CAI Zixing,WANG Yong,et al.Hybrid Immune Evolutionary Algorithm for Global Optimization Problems[J].Journal of Xidian University,2010,37(5):971-980.

[10]馬文萍,尚榮華,焦李成,等.免疫克隆優(yōu)化聚類技術(shù)[J].西安電子科技大學(xué)學(xué)報,2007,34(6):911-915.MA Wenping,SHANG Ronghua,JIAO Licheng,et al.Immune Clonal Optimization Clustering Technique[J].Journal of Xidian University,2007,34(6):911-915.

[11]AFANEH S,ZITAR R A.Virus Detection Using Clonal Selection Algorithm with Genetic Algorithm(VDC Algorithm) [J].Applied Soft Computing,2013,13(1):239-246.

[12]LIU R C,ZHANG X R,YANG N,et al.Immunodomaince Based Clonal Selection Clustering Algorithm[J].Applied Soft Computing,2012,12(1):302-312.

[13]ROBIN G,SATO Y,DESPLANCQ D,et al.Restricted Diversity of Antigen Binding Residues of Antibodies Revealedby Computational Alanine Scanning of 227 Antibody-Antigen Complexes[J].Journal of Molecular Biology,2014,426 (22):3729-3743.

[14]余建軍,孫樹棟,吳秀麗,等.4種改進免疫算法及其比較[J].系統(tǒng)工程,2006,24(2):106-112.YU Jianjun,SUN Shudong,WU Xiuli,et al.Four Improved Immune Algorithm and Its Comparison[J].Systems Engineering,2006,24(2):106-112.

[15]趙麗.基于量子免疫原理的入侵檢測模型研究[D].湖南:湖南大學(xué),2010.

[16]馬鑫,李琴.克隆選擇算法的研究與實現(xiàn)[J].改革與開放,2010,6(12):102-104.MA Xin,LI Qin.Research and Implementation of Clonal Selection Algorithm[J].Reform and Opening,2010,6(12): 102-104.

[17]LEE W,STOLFO S.A Framework for Constructing Features and Models for Intrusion Detection Systems[J].ACM Transactions on Information and System Security,2000,3(4):227-261.

[18]LIU Y,CHEN K,LIAO X,et al.A Genetic Clustering Method for Intrusion Detection[J].Pattern Recognition,2004,37(5):927-94.

(編輯:齊淑娟)

Intrusion detection design of the impoved immune algorithm

WEI Mingjun,WANG Yueyue,JIN Jianguo
(College of Information Engineering,North China Univ.of Science and Technology,Tangshan 063009,China)

Abstract:In order to improve the detection efficiency of intrusion detection and reduce the rate of misstatement,on the basis of the multi-colony immune algorithm and clonal selection algorithm,the multicolony clonal selection algorithm is put forward,the matching rule is improved and the 10%sampling data of KDDCUP99 data set is adopted as the test data of the simulation test.Each record has 41 fixed properties.Nine attributes based on the basic features of a single TCP connection are selected for study.According to the characteristics of the data set,in combination with the multi-colony clonal selection algorithm,four types of attack data which are encoded and de-weighed are regarded as the initial populations of multi-colony clonal selection algorithm for immune operation.Then,the optimal group is output.Based on the principle that normal data is greater than abnormal data,the test data set need to be filtered by the self-data set.The filtered data match the optimal group.Experimental results show that abnormal data can be effectively identified.Through comparison and analysis,the multi-colony clonal selection algorithm and the improved matching rule can improve the detection rate of intrusion detection.

Key Words:intrusion detection;immune system;multi-colony clonal selection algorithm;matching; attributes

作者簡介:魏明軍(1969-),男,教授,E-mail:weimj@ncst.edu.cn.

基金項目:河北省自然科學(xué)基金資助項目(F2014209108);河北省科技計劃資助項目(13210706)

收稿日期:2014-11-04 網(wǎng)絡(luò)出版時間:2015-05-21

doi:10.3969/j.issn.1001-2400.2016.02.022

中圖分類號:TP393

文獻標識碼:A

文章編號:1001-2400(2016)02-0126-06

網(wǎng)絡(luò)出版地址:http://www.cnki.net/kcms/detail/61.1076.TN.20150521.0902.019.html