免疫算法在入侵检测模型中的应用研究
摘要：在对常见的免疫算法原理进行分析的基础上，采用阴性选择算法和r-连续位匹配算法，提出一种改进的免疫检测机制，建立一个新的入侵检测模型。新的模型主要采取三点措施：改进候选检测集的生成规则；降低检测器冗余；引入协同检测机制等。在入侵识别阶段，采用基于编辑距离的匹配规则，提高了检测效率。试验仿真表明，该模型可有效提高入侵检测系统的检测率，降低误警率。
关键词：免疫算法；入侵检测；检测规则；阴性选择
中图分类号：TP393文献标识码：A文章编号：1009-3044(2011)19-4631-03
The Research of the Intrusion Detection Model Based on Immune Theory
LI Cheng-yun1, ZHI Dong-dong2
(1.Naval Headquarters, Beijing 100841, China; 2.Naval Logistics Department, Beijing 100841, China)
Abstract: After analysis of the immune algorithm characteristics, a new intrusion detection model based on negative selection algorithm and r-contiguous-bit matching rule is established. The new model uses three mechanisms to improve the detection effectiveness: to improve the candidate detectors generating algorithm; to reduce detectors redundancy; introduce the co-detection mechanism. Experiments show that this model can effectively increase the detection rate of the IDS with little increase of false positive rate.
Key words: immune algorithm; intrusion detection; detection rule; negative selection
人体免疫系统是一个高度复杂的系统，主要负责检测并抵御病毒传染。同时它也可以被看作是一个复杂的分布式信息处理系统，这就为研究人工自适应系统提供了一个很好的例子。人工自适应系统的一个很重要的应用领域就是计算机安全领域[1]。计算机安全系统主要功能是防止入侵者或外来代码的侵害行为，以保护单独计算机或一个网络系统。它的这一功能非常类似于人体免疫系统的功能。正是由于这两者之间有如此的相似性，基于人体免疫学原理、工作机制和体系结构的人工免疫入侵检测系统广泛用来保护计算机网络系统的安全。
1 免疫算法概述
目前，人工免疫系统可以分为模型和算法两部分，模型是算法的基础。模型有形态空间模型及基于该模型的亲和力计算方法、免疫细胞生命周期模型、骨髓模型等。在免疫算法中，基于生物免疫系统的阴性选择原理、克隆选择原理、免疫网络理论，提出了对应的阴性选择算法、克隆选择算法、免疫遗传算法等[2-3]。
这三种算法的特点如表1所示，本文采用阴性选择算法，并针对阴性选择算法的缺点进行改进，以提高算法的检测效率和准确率。
2 改进的免疫检测模型
Forrest提出的阴性选择算法中，在一定的检测率下，候选检测器集合大小与需要保护的自体集合呈指数关系[4]。而且由于采用随机方法生成候选检测器，命中率会成为一个很大的问题，即生成的大多数候选检测器可能检测不到异常而伴随生命周期的结束而被抛弃，所以效率不高。针对阴性选择算法的缺陷，在这里给出了改进的算法，主要对阴性选择算法流程中的生成候选检测器集合以及与自体耐受这两步提出改进方案，同时引入了协同检测机制以提高检测的准确性。改进思想如下：
2.1 对候选检测器生成模块的改进
阴性选择算法的候选检测器集合采取完全随机方式生成，生成的候选检测器通过了自体耐受，成为成熟检测器。由于具有很大的随意性，即使其检测到病毒的效率也很低，所以大部分为无效检测器。针对这个问题，在此作了改进，改进方法如下：
1) 对己知异常模式进行编码，变异。该法主要针对随机生成算法的缺陷。该策略主要在于使检测器集合对于己知病毒具有先天抗体。即对于己知的病毒能很快立刻识别出来。对常见的病毒特征，进行二进制编码，交叉变异后放入候选检测器集合。该法可以突出免疫系统的自适应能力，增强群体多样性及保存优良个体，提高算法的搜索性能[5]。
2) 随机生成。为了保证候选检测器集合的多样性和灵活性，仍然需要随机生成候选检测器。根据实践部分的相关参数的设定，随机生成若干个二进制字符串作为候选检测器集合的一部分。
2.2 对检测器存在冗余的改进
为了减少生成的检测器存在冗余，将生成的候选检测器在和自体进行耐受前，先与已存在的检测器集合进行匹配，使其产生的有效检测器的覆盖空间互不相交，以解决检测器冗余问题，并提高检测器的生成效率。这个过程就是进行负筛选，此外，还引入检测集生命周期规则。
负筛选算法的基本思想是使用已知的正常行为特征对那些根据任意的本地主机和网络行为特征随机产生的候选检测规则进行筛选，去除那些产生弃真错误的候选规则，剩下的候选规则就成为真正的检测规则。图1是该过程的示意图。
本文提出的基于人工免疫模型的入侵检测系统中的检测规则的生命周期定义如下：入侵检测系统中预先设定了一个激活时间限制，该时间限制就是检测规则的生命周期的值。一个检测规则如果在其生命周期内未能检测到任何入侵行为，那么当它的存在时间到达生命周期的极限时，它就会被删除。如果某一检测规则在生命周期内达到了激活条件后被激活，则表明它对于检测当前的某种入侵方式十分有效，则该检测规则就会成为记忆检测规则。
2.3 引入协同检测机制
引用协同检测机制的目的主要用两个：一是提高入侵检测的准确性；二是提高网络入侵检测信息的共享性。
和生物免疫系统类似，异常的检测并不足以提高免疫应答，需要从辅助细胞发出协同刺激信号。当记忆检测器检测到异常时，触发请求管理员协同信号，一旦收到协同刺激信号，则产生警告给控制台；如收到协同抑制信号，则此次异常变成虚警。若记忆检测器在一定时间窗口内既没有收到协同激发信号，又没有收到协同抑制信号，则默认此次报警为真实报警。
在入侵检测过程中，多个监视主体有时会同时对同一个网络事件做出反应。如果入侵检测服务器中的决策主体连续收到多个本地决策主体对同一网络事件的检测报告，则它就会怀疑当前的网络事件可能是入侵行为，并通网络安全管理员采取相应的措施。因此，一个网络行为是否是入侵行为，要由几个本地监视主体共同来识别，并且最终要由IDS服务器中的决策主题来决定。采用协同检测机制可以减少自免疫的发生，以及由异常检测引起的虚警，从而进一步提高系统的检测性能。
改进后的检测器模型的检测流程图如图2所示，算法的实现基于动态环境，在检测过程中不断更新检测器集合。
3 免疫匹配检测算法
3.1 免疫匹配规则的定义
在入侵检测领域，由于在计算机中所有的数据都是以二进制的形式存放的，这样可以将网络连接定义在一个域U上，U是一个所有长度为L的二进制字符串的有限集合，它包括两个子集：自体集S和非自体集N。其中S∪N=U，S∩N=Φ。检测过程就是对于一个模式I∈U的分类，看它是自体还是非自体。
网络安全问题就可以定义为判断长度为L的字符串s属于哪个集合。问题的关键在于抗体(检测器)的产生机制上，因为它决定了问题的复杂程度。这里采用编辑距离检测算法。
编辑距离也叫Levenshtein距离。是由Levenshtein于1966年在研究纠错码时提出的[6]。Levenshtein指出,在信道中传输的位串时。有下列三种错误发生：
1) 反转：即1→0或者0→1；
2) 删除：即1→Λ或者0→Λ；
3) 插入：即Λ→1或者Λ→0。
其中，Λ是表示位的丢失。
定义：两个位串a和b之间的编辑距离是指把a变化到b时所需要的最小的编辑操作(反转，删除，插入)数目。例如，“1010”和“1000”之间的编辑距离为1，因为只需把“1010”中的第三位的“1”反转为“0”即可。
3.2 编辑距离的计算
对于两个位串a=a1 a2……am，b=b1 b2……bn。我们定义一个(m+1)×(n+1)阶的距离矩阵Ma,b[.,.]。其中，M [i, j]表示将a的子串a1 a2……ai转化为b的子串b1 b2……bj时，所需要的最小的编辑操作数目，0≤i≤m,0≤j≤n。并且有[6-7]：
1) M[0, j]=j
2) M[i,0]=i
3) 对于i, j ≥1,有:
M[i,j]=min{M[i-1,j]+1,M[i,j-1]+1,M[i-1,j-1]+change (ai, bj)}
其中：
则M[m+1,n+1]即为a和b之间的编辑距离。
3.3 基于编辑距离的检测器检测算法
设K作为检测规则阈值。对于检测到的特征编码，与已知检测规则进行匹配，如果与某一检测规则的编辑距离小于K，则该行为即可判定为入侵行为。编辑距离越小，则相似度就越大，被判定成入侵行为的概率更大。
设K作为检测规则阈值。对于检测到的特征编码，与已知检测规则进行匹配，如果与某一检测规则的编辑距离小于K，则该行为即可判定为入侵行为。编辑距离越小，则相似度就越大，被判定成入侵行为的概率更大。
假设s1=0001, s2=0011为检测到的两条特征编码。再假设d为一个检测规则，令d=0000。根据上面的定义可以得到两个距离矩阵。
得出d与s1、s2的编辑距离分别为1、2。有上两式可以看出这两个矩阵的前三列完全相同，即距离矩阵M[d, s1]的前三列可以直接拷贝距离矩阵M[d, s2]中。同理，其他以“00”开头的特征编码与d的编辑距离计算也可以依此类推。这样，有相同前缀的特征编码与待检测位串的编辑距离便可以共享前面部分列的计算结果，这样就大大减少了计算量。
4 实验仿真分析
4.1 实验数据
在实验中，我们选用了1999年DARPA为KDD(知识发现与数据挖掘)竞赛提供的一个异常检测的标准数据集，它来源于1998年DARPA的入侵检测评估程序，由美国麻省理工学院的林肯实验室建立，目的是观察和评估入侵检测系统的研究工作，用一套标准格式的数据来评估各种入侵检测系统的性能。1999年KDD竞赛中在数据挖掘和入侵检测方面的网络数据也是采用这种格式。
数据中包含41维特征，主要分为四类攻击：(1) Probe攻击，常见的Probing攻击有：Ipsweep、Mscan、Nmap等；(2) DoS(Denial of Service)攻击，常用的DoS攻击有：Apaeh2、Ping of Dath、Smurf、Teardrop等；(3) U2R(User to Root)攻击，常用的U2R攻击有：Eject、Ffbconfig、Perl等；(4) R2L(User to Local)攻击，常见的R2L攻击有：Dictionary、Ftp-write、Imap等[8]。
由于KDD原始数据集过于庞大,为了对算法进行验证,本文选择了其中具有代表性的corrected数据集,分别随机生成训练集、测试集。
4.2 实验结果及分析
试验设定自体集样本数为5000，测试集样本分为两部分：测试集一样本数为2000，且这些样本全部属于自体集；测试集二样本数为1000，且这些样本全部不属于自体集，另外。候选检测规则耐受期为30。
试验参数设定后，利用开源工程WEKA完成数据试验。在这里为了显示人工免疫原理对免疫检测系统的性能的提升，同时将对两种测试集的检测结果显示出来，进行对比。对两类测试集进行检测的实验参数都设置为相同。试验迭代代数为2000。两者检测结果的对比如表2所示。
由此可见，该入侵检测模型具有较强的识别新的入侵行为能力。与基于滥用的入侵检测系统相比，该系统能够较好辨别出新的攻击方式，提取其特征并进行自我学习，生成记忆型字符集，从而形成对该攻击方式免疫的检测规则，提高了系统的检测性能，增加了系统的健壮性、自适应性和动态防护性，适应于复杂的网络环境。
5 结束语
文章首先重点研究分析了阴性选择算法、克隆选择算法和免疫遗传算法的原理，在此基础上给出了改进的基于人工免疫的检测算法模型。在对模型进行改进的同时，系统采用基于编辑距离的检测匹配算法，优化了算法的性能。经过系统仿真实验，表明这种检测算法可以使检测器生成效率得以提高，入侵检测正确率得以提升，能积极主动的保护系统不受实质性攻击。为构建新一代高效合理的网络安全系统提供了一种有效方案。
参考文献：
[1] 周光炎.免疫学原理[M].上海:上海科学技术文献出版社,2002:201-230.
[2] 莫宏伟.人工免疫系统原理与应用[M].哈尔滨: 哈尔滨工业大学出版社,2003:125-160.
[3] 马莉.基于免疫原理的网络入侵检测器生成算法的研究[D].南京:南京理工大学,2006.
[4] 肖锋,杨树堂,陆松年,等.基于人工免疫的入侵检测模型研究[J].计算机应用与软件,2008,25(2): 258-260
[5] Hofneyr S A, Forrest S. Architecture for an artificial immune system [J].Evolutionary Computation,2000,8(4):443-473.
[6] V. I. Levenshtein, Binary codes capable of correcting deletions, insertions, and reversals[J]. Soviet Physics Doklady,1966,10:707-710.
[7] Hunt J E, Cooke D E. Learning Using an Artificial Immune System [J]. Journal of network and computer applications,1996,19:189-212
[8] KDD cup 1999 data. https://kdd.ics.uci.edu/databases/ kddcup99/ kddcup99.html.
注：本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文