一種改進免疫算法的入侵檢測設計

魏明軍,王月月,金建國

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

?

一種改進免疫算法的入侵檢測設計

魏明軍,王月月,金建國

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

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

關鍵詞:入侵檢測;免疫系統;多種群克隆選擇算法;匹配;屬性

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

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

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

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

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

1 多種群克隆選擇算法

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

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

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

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

1.1 數據集及研究屬性選取

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

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

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

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

1.2 初始種群特殊化處理

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

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

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

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

2 r匹配規則及其改進

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

圖1 r位匹配規則示意圖　

圖2 r連續位匹配規則示意圖

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

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

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

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

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

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

(1)兩條數據記錄對應屬性的二進制串進行異或操作,若對應的二進制編碼相同,則記為1,若不同,則為0,結果統記為c.

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

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

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

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

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

圖4 改進匹配規則示意圖

3 仿真實驗及結果分析

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

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

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

圖5 r與誤報率的關系示意圖

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

表2 混合數據集測試結果

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

表3 3種算法的測試結果比較

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

4 結束語

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

參考文獻:

[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]劉星寶,蔡自興,王勇,等.用于全局優化問題的混合免疫進化算法[J].西安電子科技大學學報,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]馬文萍,尚榮華,焦李成,等.免疫克隆優化聚類技術[J].西安電子科技大學學報,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].系統工程,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].湖南:湖南大學,2010.

[16]馬鑫,李琴.克隆選擇算法的研究與實現[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.

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

收稿日期:2014-11-04 網絡出版時間:2015-05-21

doi:10.3969/j.issn.1001-2400.2016.02.022

中圖分類號:TP393

文獻標識碼:A

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

網絡出版地址:http://www.cnki.net/kcms/detail/61.1076.TN.20150521.0902.019.html