一种改进免疫算法的入侵检测设计

魏明军,王月月,金建国

(华北理工大学信息工程学院,河北唐山 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