基于免疫识别的最小检测器生成模型

蒋亚平，赵军伟，马亚琼，田月霞

（郑州轻工业学院 计算机与通信工程学院，河南 郑州450001）

0 引 言

生物免疫系统是一个自学习、自组织和自适应系统，能够有效地抵御抗原的入侵［1］。人工免疫系统就是受生物免疫系统的启发而发展起来的，并被应用于网络入侵检测领域。其中，检测器生成算法是入侵检测系统的核心，决定着系统的性能和效率［2］。1994年Forrest等最早提出否定选择算法 （negative selection algorithm，NSA）［3］，并首次实现检测器的耐受［4］，此后，高效的检测器生成模型逐渐成为一个研究热点。

国内学者李涛、焦李成、莫宏伟等进行了相应的研究，并取得了一定的成果［5－7］。文献 ［8］提出了一种改进的否定选择算法，通过减少匹配检测器的数量提高了检测器的覆盖率，但检测器生成算法中使用的是固定阈值，即确定性方法。文献 ［9］提出了一种基于模糊匹配的检测器生成算法，提高了检测器的检测效率，但不能去除克隆变异后检测器集合内可能存在的冗余。针对以上算法的不足，本文提出一种基于免疫识别的最小检测器生成模型，通过免疫识别算法解决边界检测器的识别问题，克隆选择和变异算法能够产生高效的检测器，并通过冗余优化算法去除检测器冗余，最终得到最小有效检测器集合。

1 形态空间理论与免疫识别

1.1 检测器的形态空间分析

Perelson和Oster提出免疫事件都在形态空间S（shapespace）中发生［10］。因此形态空间中有一体积为V 的区域，包含着抗体和抗原及其形状互补区域。抗体识别抗原就是其与抗原匹配并结合的过程，这种匹配并不是完全精确的匹配，只要积累的亲和力超过一定的阈值即可。由于采用不完全匹配机制，一种抗体可以识别多种抗原，从而可以利用有限数量的抗体及其覆盖区域来识别尽可能多的抗原。

如图1所示，X为抗原，大圆代表形态空间S（体积为V），小圆表示抗体及其匹配范围，半径为ε，n为空间内的抗体个数，Vε为抗原覆盖空间，那么每个抗原可由nVε／V个不同的抗体识别，其不被识别的概率为

由式 （1）可知，V不变的情况下要降低P 就要增大nVε的值，而检测器集合的大小即n值往往有限制，因此有必要去除检测器集合的冗余，利用尽可能小的检测器集合覆盖更大的抗原空间。

图1 形态空间

1.2 基于隶属度的免疫识别

入侵检测系统检测过程中难免出现误检和漏检，主要是因为某些检测器在形态空间中处于 “非我”空间的边缘，它们接近于 “非我”但严格来说却不属于 “非我”空间，即它们具体是否隶属于 “非我”集合是个模糊的概念。目前常用算法在区分边界检测器时采用的都是确定性方法，即采用固定阈值来衡量匹配程度，因此难以生成有效的检测器，最终造成入侵检测系统误检或漏检的发生。因此，为了生成高效的检测器，本文在抗体进化过程中采用基于隶属度的免疫识别算法代替传统的否定选择算法，通过隶属度代替确定性方法中的匹配阈值以筛选出边界检测器。

2 基于免疫识别的检测器生成模型

2.1 相关定义

定义1 自体／非自体：所有的数据包组成集合U［0，1］l，正常的数据包定义为自体集合selfU；非正常的数据包定义为非自体集合nonselfU［11］。D表示检测器集合，分为初始检测器D0、成熟检测器Dmat、最小检测器Dmin、边界检测器Dbounds四类。D中的元素di，i∈［1，ξ］为一个检测器，ξ为D中元素的个数。

定义2 贴近度：贴近度表征两个字符串的相似程度，字符串L1和L2的贴近度计算如下

定义3 隶属度：隶属度代表字符串对字符串集合的隶属程度，那么di与非自体集合的隶属度可以用di与nonself中元素 （nonselfj，j∈ ［1，m］）的贴近度的加权值表示，权值设为其中x为随机抽取的子集包含的样本数量，即

定义4 最大相似位：设有字符串L1和L2，其中L1＝X1X2X3···Xl，L2＝Y1Y2Y3···Yl，Xi，j（1≤i≤j≤l）为字符串L2在L1中对应位置上相同的子串，那么最大 相 似 位 max（L1，L2）＝ max（Len（Xi，j））， 其 中max（Len（Xi，j））表示所有连续相同子串长度的最大值。

2.2 模型描述

检测器生成模型如图2所示，随机产生的初始检测器首先经过与非自体集的免疫识别过程，通过计算隶属度将初始检测器分为三类 （成熟检测器、边界检测器以及未通过耐受的检测器）。其中，成熟检测器直接加入成熟检测器Dmat，未通过耐受的检测器直接被丢弃，边界检测器作为父代检测器并经过克隆选择和变异过程，将满足条件的边界检测器加入成熟检测器Dmat，经过冗余优化算法最终生成最小检测器。

图2 最小检测器生成模型

3 最小检测器生成算法及理论验证

3.1 免疫识别过程

计算检测器与非自体集的隶属度，并将隶属度分为3个模糊区间。对实验生成的模式空间进行抽样，统计结果大致成正态分布 （如图3所示），其中相应区间随参数a、b（0＜a＜b＜1）的确定而确定，分别为：［0，a），［a，b），［b，1］，根据图3可知a取0.46，b取0.55较为合理。算法具体步骤如下：

步骤1 准备：①确定self、nonself的描述形式；②定义非自体，构造非自体集；③确定隶属度的计算方法。

步骤2 初始化：随机生成初始检测器D0，其中di∈D0，i∈ ［1，ξ］，ξ为初始检测器的检测器个数。

步骤3 免疫识别：随机抽取非自体集的一部分作为子集 （包含x个样本），计算di与子集的隶属度，并重复该过程m次。如果在m次计算中有任何一次的隶属度小于a，则该检测器未通过自体耐受而被丢弃；如果隶属度大于b的次数不少于隶属度大于a的次数，则将该检测器加入成熟检测器Dmat；如果隶属度大于b的次数少于隶属度大于a的次数，则将其加入边界检测器Dbounds。

步骤4 克隆选择与变异：边界检测器Dbounds中的检测器通过克隆选择、交叉变异直至隶属度满足要求或达到最大进化代数。

步骤5 若D0中所有检测器都通过免疫识别，则免疫识别过程结束，得到成熟检测器集合Dmat；否则转到步骤3。

图3 隶属度抽样结果

3.2 冗余优化算法

通过免疫识别的检测器即为成熟检测器Dmat，然后经过冗余优化算法生成最小检测器。冗余优化算法的具体步骤如下，其中D［i］为当前的检测器；D［k］为未进行匹配的检测器；θ为匹配阈值，NR为预设的最小检测器数目。

步骤1 产生成熟检测器集合Dmat，确定检测器个数n，并初始化匹配阈值θ；

步骤2 设置循环变量i和k（k＝i＋1：n），取当前检测器D［i］与Dmat中的检测器D［k］进行匹配；

步骤3 若D［i］与所有的D［k］都进行了匹配，则加入最小检测器Dmin，转到步骤6；

步骤4 否则D［i］与下一个D［k］进行匹配，计算D［i］与当前D［k］的最大连续相似位 max（D［i］，D［k］）；

步骤5 若max（D［i］，D［k］）大于或等于阈值θ，则删掉D［i］，转到步骤6；否则转到步骤3；

步骤6 若检测器集合Dmat中所有检测器都进行了匹配，转到步骤7；否则转到步骤2。

步骤7 若当前检测器Dmin中检测器的数目小于NR，转到步骤1；否则算法结束，最终生成的Dmin即为最小检测器。

3.3 理论分析

设Pm为成熟检测器Dmat中的两个随机串的匹配概率，那么在r连续位匹配规则下则有

式中：l——字符串的长度。假设NR为最小有效检测器的数目，那么可得系统的漏报率pf和检测率pt分别为

对式 （5）两边取对数，可得最小检测器的数量为

由式 （7）可知，对于固定的字符串和匹配阈值，在一定漏报率Pf和检测率Pt之内的检测器数量与自我集的规模无关，即有效检测器的数量不随被保护的自我集的增大而增加，因此，NR即为最小检测器集合中检测器的数目。

4 仿真实验

仿真环境与参数设置：用randerr（120，13，［0：13］）函数随机生成150个二进制串 （l＝13）作为自我集，并随机生成100个字符串组成非我集，初始检测器包含60个抗体，并构造长度为l的模式空间 （8000个字符串）。隶属度区间边界参数a＝0.46，b＝0.55，选取冗余优化阈值θ＝9，Pf＝0.08时NR取48。本算法与经典的否定选择算法在相同的检测器个数及匹配阈值的情况下进行覆盖空间的比较，实验结果如图4所示。

图4 两种算法覆盖空间和空间覆盖率的比较 （θ＝9）

为了验证匹配阈值对本算法的影响，其它参数不变的情况下选取冗余优化阈值θ＝11进行另一组实验，实验结果如图5所示。

由图4和图5可知，匹配阈值不同的情况下，改进算法的覆盖检测器个数和空间覆盖率在整体上均高于经典算法，但两种算法的结果均有跳变现象，这与字符串生成的随机性和长度限制有关。

图5 两种算法覆盖空间和空间覆盖率的比较 （θ＝11）

检测器整体性能可通过TP值 （检测率）和FP值 （误报率）来衡量。分别对改进算法和文献 ［12］算法进行三次测试，实验统计结果及平均值见表1。

表1 两种算法实验结果对比

由表1可知，改进算法的检测结果优于文献 ［12］算法，平均TP值提高了2.32%，而FP值降低了2.53%。究其原因是改进算法采用免疫识别算法更好地模拟了生物免疫系统的机理，克隆选择和变异算法提高了检测器的整体质量，因而检测效果较为理想。

5 结束语

本文基于形态空间分析了检测器集合去除冗余的必要性，通过对模式空间进行抽样给出了检测器边界区间参数的选取依据，在免疫识别、克隆选择、变异算法以及冗余优化算法的基础上建立了基于免疫识别的最小检测器生成模型并通过理论验证给出了最小检测器的概念。该模型的核心在于采用基于隶属度的免疫识别算法识别边界检测器，同时通过冗余优化算法去除成熟检测器的冗余，最终生成最小有效检测器。实验结果表明本模型可以产生高效的检测器，与传统模型相比具有更好的检测效果。

［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）.［杨东勇，陈晋音.基于多种群遗传算法的检测器生成算法研究 ［J］.自动化学报，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）.［蒋亚平，吕廷勤，甘勇.基于疫苗接种的网络安全防御模型 ［J］.东北大学学报：自然科学版，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］.通信学报，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）. ［焦李成，杜海峰，刘芳，等.免疫优化计算、学习与识别 ［M］.北京：科学出版社，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：一种基于免疫的动态入侵检测模型 ［J］.科学通报，2009，50 （17）：1912－1919.］

［7］MO Hongwei，FU 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）.［胡亮，王程明，赵阔.基于人工免疫模型的入侵检测系统中检测器生成算法的分析与改进 ［J］.吉林大学学报，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］.智能系统学报，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］.中国科学，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］.计算机工程与设计，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.