r连续位匹配算法的改进

张明清，程 建，孔红山，刘小虎

（信息工程大学，河南 郑州450004）

0 引 言

当前研究人员模仿生物免疫系统相关特性，建立人工免疫系统 （artificial immune system，AIS），用以保护主机或网络，检测入侵行为［1－3］。阴性选择算法是人工免疫系统中常用的免疫算法，而匹配算法是阴性选择算法的重要组成部分［4］，目前主要采用的是r连续位匹配算法［5］。

唐俊等［6］对r值不变进行了改进，提出了一种动态r连续位匹配算法，增强了算法的适用性，但r值的变动会对入侵检测系统造成较大影响；韩亮等［7］对r连续位匹配算法中匹配阈值取值与检测效率的关系进行了研究，指出了相应问题，但并未对算法进行改进；芦天亮等［8］对阴性选择算法中的黑洞问题进行了研究，提出了一种采用双重检测器的阴性选择算法，该算法能够提高黑洞覆盖率，但只在检测器生成方面做了改进，未涉及匹配算法；陈园园［9］对传统r连续位匹配算法进行了改进，提出了基于基因块的匹配，但匹配阈值仍采用传统取值，降低了算法适用性。

从充分反应匹配程度角度进行的r连续位匹配算法研究较少。基于此，本文提出一种改进型r连续位匹配算法，即基于权重的基因块匹配算法，并通过仿真实验验证了算法的有效性。

1 理论基础

1.1 人工免疫基础

生物免疫系统是一个十分精密的，集入侵检测、防御于一体的系统。其将自身物质视为自体，外界入侵视为非自体。生物体主要通过抗体细胞来识别和防御非自体物质，抗体细胞需要通过自身耐受的检验才能生成，如果其与任一自体细胞相匹配则将其杀死，通过自身耐受后才能成为真正起作用的抗体。抗体与抗原 （即非自体）进行作用，如果匹配则将该抗原杀死。人工免疫系统借鉴生物免疫系统的相关特性来解决工程实践中遇到的一些现实问题，其广泛应用于入侵检测等应用领域。人工免疫系统与入侵检测系统概念对比见表1。

表1 人工免疫与入侵检测系统概念对比

1.2 阴性选择算法基础

阴性选择算法是一种异常检测算法，其基本思想是将所有非正常行为视为异常。因此检测器的生成与生物免疫系统中抗体生成相似，需要经过自体耐受训练，也即需要确保生成的检测器不与正常行为匹配。通过自体耐受训练的检测器对网络行为进行检测，如果匹配则认为其是入侵。

2 传统r连续位匹配算法分析

传统r连续位匹配算法指2个字符串X和Y相对应的位置上如果有r个及以上连续字符相同，则称两字符串匹配，其中r为匹配阈值。给出传统匹配算法数学定义如下［10］。

定义 如果字符串X和Y从P1位开始有连续K1位相同；从P2位开始有连续K2位相同，以此类推，从Pn位开始有连续的Kn位相同。则取Kmax＝max｛k1，k2，…，kn｝，Kmax即为字符串X和Y的匹配位数，Kmax≥r则匹配，否则不匹配。举例如图1所示。

该匹配算法简单、易用，但也存在以下缺点：

（1）以位为匹配单位，没有反应匹配程度［11］

某一网络访问由2种属性a、b构成，a采用3位编码，b采用2位编码，自体集为 ｛10001，11011｝，设a、b这2种属性均只有一种取值代表入侵行为，入侵行为记为a：001，b：10，当且仅当a，b中有一种为入侵属性时，该网络行为被认定为入侵行为。当r＝2时，根据阴性选择算法规则，01100是合格检测器，则采用未经改进的r连续位匹配规则，行为A＝10101被认定为入侵行为，然而实际情况则是A为正常访问行为，因为其2个子属性101与01均不是入侵属性。造成此类错误的原因在于传统匹配以位为单位，该网络行为由2个子属性组成，而10101与01100的匹配位则是10，即2个子行为连接部分，因此并未真正体现子行为的匹配程度。错误匹配如图2所示。

（2）没有考虑实际应用中的权重问题［12］

攻击检测需要监视多种参数，各个参数在表征攻击程度方面并不相同。在实际的网络入侵检测中相关参数可能有端口、源IP、目的IP、网络类型等等，而各种参数之间的重要性并不完全相同。例如源IP地址没有在服务器记录的IP地址范围内，该访问很有可能是入侵行为，则参数源IP权重应相对大些，这些在传统的匹配算法中并没有很好的体现。

3 基于权重的基因块匹配算法

针对传统算法的不足，本节提出了基于权重的基因块匹配算法。

3.1 相关定义

（1）检测器集合DET：通过自体集耐受的字符串集合；

（2）字符串S：由二进制字符组成的基因块构成，其包括基因块数目为N，字符总长度为n；

（3）基因GEN：生物学中，基因是指携带有遗传信息的DNA或RNA序列，是控制生物性状的基本遗传单位。阴性选择算法中指能够表示某类信息的字符串，对于入侵检测系统而言基因对应最基本的匹配单位，不同的基因代表不同的特征属性。字符串S＝ ｛gen1，gen2，…，genn｝，genn所代表的性状种类数为i，则其所需编码位数为l，其中l＝示不超过，l为整数），字符串S表示为

（4）权重wi：基因块i对应的权重为wi，其满足w1＋w2＋…＋wn＝1。每个基因的权重wi由基因所代表不同特征对入侵检测的重要性决定；权重越大，表示该基因相对越重要；

（5）基因块匹配阈值ri：基因块之间是否匹配的临界值。匹配程度大于等于ri时，基因块匹配，匹配算法采用传统的r连续位匹配；

（6）亲和度AD：字符串之间的匹配程度；

（7）字符串匹配阈值R：判断字符串之间是否匹配的临界值，当亲和度AD大于等于R时匹配，小于则不匹配。在该改进匹配算法中匹配基因不需要连续。根据亲和度AD的定义，计算得出AD，与R比较即可得出是否匹配。

3.2 匹配算法规则

该算法进行双层匹配。第一层是基因块间的匹配，首先对二进制字符串A、B对应的基因块进行匹配，采用传统的r连续位匹配规则，当匹配位数大于等于ri（ri为基因块Ai与Bi匹配阈值）时，基因块Ai与Bi匹配，由于各基因所代表的行为不同，其位数长短也不尽相同，不同基因的匹配阈值应根据相应基因长度确定。记基因块i长度为lengthi，结合传统的匹配方法得基因块匹配中阈值ri的确定函数为

式中：r——传统连续位匹配阈值，则基因块匹配函数表示如下

第二层为字符串的匹配，根据第一层匹配得出的f（Ai，Bi），即各基因块间的匹配程度，根据基因块的各权重，计算得出字符串A与B的亲和度

若AD≥R匹配，否则不匹配。

3.3 匹配算法检测流程

检测流程如图3所示。

根据阴性选择原理，首先需要生成足够的检测器，然后检测器开始检测。定义自体集集合SELF，非自体集NONSELF，根据实际应用确定字符串S由几种基因组成，并确定基因权重及阈值R，r；随机生成检测器并根据改进匹配算法规则进行耐受训练；如果AD≥R则删除字符串，否则将a加入检测器集合DET；循环上述过程直至生成实验所需数量检测器；检测器对网络行为进行检测，如果全部检测器均没有与之发生匹配，则判断网络行为正常，否则判断其为入侵。

4 仿真分析

针对上节改进的匹配算法，本节进行仿真分析，从检测率、误检率2个方面验证算法的正确性和有效性，并对改进算法的效率进行理论分析。

4.1 实验环境及参数设置

采用Matlab2010b仿真平台进行仿真，实验数据选择R.A.Fisher Iris plants dataset经典数据集［13］。Iris数据集包含3类数据：setosa，versicolour，virginica，分别记为data1，data2，data3。每类50组数据，每组数据4种特征。可以将3类数据分别视为自体集与非自体集，根据不同实验目的相互组合。

（1）权重：实际应用中应根据先验知识或相应专家意见来判断特征的权重。由于本实验数据均已知，因此当某一类数据确定为自体集后，可以采用非自体集与自体集之差的大小来确定相应基因权重；

4.2 仿真结果分析

检测器相关检测性能不仅由匹配算法决定，而且与检测器数量密切相关。在相同匹配算法条件下，检测器数量越多，检测率越高。在相同检测器数量条件下，匹配阈值r的取值对相关检测性能也具有很大影响。因此本节从检测器数量与匹配阈值2个方面对2种算法综合比较。

4.2.1 匹配阈值与相关检测性能仿真分析

实验1：对上述data1、data2、data3设定3种组合情况：①data1为自体集，data2为非自体集；②data2为自体集，data3为非自体集；③data3为自体集，data1为非自体集。根据经验值确定检测器数量为100，对3种组合情况分别进行仿真，对3组仿真结果取平均值。图4是通过仿真得出的2种算法的r值与检测率的关系。

图4 中可以看出，匹配阈值在1到7时二者检测率均达到100%，这是因为匹配阈值较低，每个检测器的检测范围很大，而入侵数据数量较少。匹配阈值进一步增加，可以看出改进算法优于传统算法。当匹配阈值过大时由于检测器数量有限，将导致检测率迅速降低，直至为0。

实验2：对data1、data2、data3，分别取各自的前25组为自体集，后25组为 “非自体集”。对3种组合情况分别进行仿真，对3组仿真结果取平均值。得传统算法与改进算法误检率比较如图5所示。

图5 中可以看出，匹配阈值在1到5时二者误检率均达到100%，这是由匹配阈值过低导致的。匹配阈值进一步增加，可以看出改进算法误检率明显低于传统算法，由于检测器数量有限当匹配阈值过大时误检率迅速降低，直至为0。

4.2.2 检测器数量与相关检测性能仿真分析

综合4.2.1小节中误检率与检测率取值，可得匹配阈值的合理取值范围为9～13。匹配阈值为9时，检测器数量与检测率与误检率的关系分析如下。

实验3：data1、data2、data3的设定与实验1相同。分别进行仿真，取平均值。传统算法与改进算法检测率比较如图6所示。

图6 中可以看出，随着检测器数量的增多，检测率也随之提高，整体上改进算法检测率高于传统算法，从曲线的波动性可以看出传统算法波动性较大，改进算法则相对平缓。

实验4：data1、data2、data3的设定与实验2相同。分别进行仿真，取平均值。传统算法与改进算法误检率比较如图7所示。

图7 中可以看出，随着检测器数量的增多，误检率随之上升，整体上改进算法误检率低于传统算法，且改进算法曲线较为平缓，传统算法曲线波动较大。二者误检率较高的原因在于自体集数量较少，但不影响二者的比较。

综合上述仿真结果可以得出改进算法在相关检测性能方面均优于传统算法。

4.3 改进算法效率分析

对改进算法与传统算法的复杂度进行分析比较，以明确改进算法是否实用。

设字符串S其包括基因块数目为N，每块长度为ij（1≤j≤N）字符串总长度为n，匹配阈值为R。设传统算法时间复杂度为o（n）。在此不考虑传统算法计算最长匹配字符数的具体算法，但显然可知该算法时间复杂度至少与字符串总长度线性相关，即o（n）＝k＊n。则根据改进算法规则，第1层匹配算法的复杂度为而根据式 （3）改进算法第2层只是进行了线性相加，因此从总体上看改进算法的复杂度几乎没有增加。

5 结束语

本文针对阴性选择算法中广泛使用的r连续位匹配算法存在的问题，对其进行了深入分析，提出了基于权重的基因块匹配算法，采用双层匹配，能够充分反应匹配程度。采用matlab进行了仿真实现，从3个方面对改进算法进行了分析。分析结果表明所提出的改进算法明显降低了误检率，提高了检测率，且并未增加算法复杂度。

r连续位匹配算法是目前研究的热点，还有许多问题需要解决。本文未考虑双层匹配算法中基因块权重对基因块内匹配阈值的影响，这是下一步研究的方向［14］。

［1］Astha Keshariya，Noria Foukia.DDoS defense mechanisms：A new taxonomy ［G］.LNCS 5939：Data Privacy Management and Autonomous Spontaneous Security，2010：222－236.

［2］WU S X，Banzhaf W.The use of computational intelligence in intrusion detection systems：A review ［J］.Applied Soft Computing，2010，10 （1）：1－35.

［3］WU Yuanyuan，ZENG Aiguo.Intrusion detection based on artificial immune classifier ［J］.Intelligent Computer and Applications，2013，3 （1）：75－78 （in Chinese）.［伍媛媛，曾爱国.基于人工免疫分类器的入侵检测方法 ［J］.智能计算机与应用，2013，3 （1）：75－78.］

［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］YANG Jin，LIU Xiaojie，LI Tao，et al.Matching algorithm in artificial immune system ［J］.Journal of Sichuan University（Engineering Science Edition），2008，40 （3）：126－131 （in Chinese）.［杨进，刘晓洁，李涛，等.人工免疫中匹配算法研究 ［J］.四川大学学报 （工程科学版），2008，40 （3）：126－131.］

［6］TANG Jun，ZHAO Xiaojuan.Rvariable matching algorithm used for IDS ［J］.Application Research of Computers，2010，27 （2）：745－748 （in Chinese）.［唐俊，赵晓娟.一种用于入侵检测系统的可变r匹配算法 ［J］.计算机应用研究，2010，27 （2）：745－748.］

［7］HAN Liang，LI Chengyun.Research on r contiguous bits matching in immunity network intrusion detection ［J］.Software Guide，2012，11 （11）：60－62 （in Chinese）.［韩亮，李成云.免疫网络入侵检测中的r连续位匹配算法研究 ［J］.软件导刊，2012，11 （11）：60－62.］

［8］LU Tianliang，ZHENG Kangfeng，FU Rongrong.Anomaly detection system with hole coverage optimization based on negative selection algorithm ［J］.Journal on Communications，2013，34 （1）：128－135 （in Chinese）.［芦天亮，郑康锋，傅蓉蓉，等.基于阴性选择算法的异常检测系统黑洞覆盖优化［J］.通信学报，2013，34 （1）：128－135.］

［9］CHEN Yuanyuan.Network intrusion detection system based on artificial immune ［D］.Chongqing：Chongqing University of Technology，2011（in Chinese）.［陈园园.基于人工免疫的网络入侵检测系统 ［D］.重庆：重庆理工大学，2011.］

［10］Feng Xiang，Zhao Tianling.Research on intrusion detection system using improved artificial immune algorithm ［C］／／IEEE International Conference on Computer Science and Information Technology，2011：636－640.

［11］Dasgupta D，YU SH，Nino F.Recent advances in artificial immune systems－models and applications ［J］.Applied Soft Computing，2011，11 （2）：1574－1587.

［12］GAO XZ，Chow MY，Pelta D.Theory and applications of artificial immune systems ［J］.Neural Computing and Applications，2010，19 （8）：1101－1102.

［13］Sir Ronald Fidher.iris ［DB／OL］.［2000－07－11／2013／09－27］.http：／／archive.ics.uci.edu／ml／machine－learning－databases／iris／.

［14］YANG Ning，WANG Qian.Negative Selection algorithm based on niche strategy ［J］.Computer Science，2011，38（10）：181－184 （in Chinese）.［杨宁，王茜.一种基于小生境策略的阴性选择算法 ［J］.计算机科学，2011，38 （10）：181－184.］