一种新型的否定选择算法生成检测器的研究

张清华 ， 赵红霞 ，2， 朱月君 ，3， 杨晖泽 ，3

（1.茂名学院 计算机与电子信息学院自动化系，广东 茂名 525000；2.太原理工大学 计算机与软件学院，山西 太原 030024；3.太原理工大学 信息工程学院，山西 太原 030024）

否定选择算法主要应用于检测器的生成。传统的否定选择算法存在的问题主要有：问题空间过大时算法时空复杂度成指数级递增，可行性不高[1]；检测效率较低，容易产生漏洞；冗余检测器较多，导致检测效率的下降[2]；用二进制字符串描述抗原和检测器不利于管理并且此种形式难以表示某些领域的信息；目前自适应性对于人工免疫系统仍是复杂的、函待解决的问题；大部分否定选择算法中检测器的管理方式较为简单[3]；寻找相应的检测器花费时间较长等等。本文根据否定选择算法所存在的问题，提出一种新型的否定选择算法生成检测器算法，并证实算法原理和仿真模拟来体现此种方法的优越性，最后通过实验来确认此算法，最后进行总结。

1 改进的算法

1.1 算法的原理

1.1.1 检测器问题定义

自体集S，非自体集T和全集U是用0，1二进制代码串表示其特征，U=[0，1]n，S⊆U，T⊆U。自体集 S 与非自体集 T 交集为空，自体集S与非自体集T构成全集U，如式（1）。

定义 1：待测检测器 d与检测器集 x匹配，匹配值 r为：d match x=xj=djfor j=i，…，i+r-1。表示当检测器 d与抗原 x的从第i位开始存在不少于r个连续相同的对应位时，二者匹配；r（1〈r≤l）为静态匹配阈值。

自体集 S，非自体集 T和全集 U是 n维空间 （ndimensions），其中 S={X1，…，Xn，f}，T={X1，…，Xn，f}，f表示检测器状态，如式（2）。 设有 2 个阈值 R，r（R＞r），R 表示最高匹配阈值，表示初始匹配阈值，根据匹配阈值大小可直接判断其检测器状态，检测器存在3种状态：自体 （self），非自体（nonself）和不确定检测器（uncertain）。

定义 2：待 测检 测 器（Detector），D={X1，…，Xn，f}与检测集匹配，当匹配值 r〈match（x，d）〈R，即 uncertain 状态，设定递增匹配阈值 r′（r〈r′〈R）来判断检测器是否是新增的自体集（或非自体集），如式（3）：

1.1.2 self定义

定义自体集 S={X1，…，Xn，1}，其中 X1，…，Xn代表自体集的特征码，f=1代表此检测器状态为正常。网络是个动态环境，随着时间T的推移，自体检测器也在变化，方程（4）所表示是 t时刻所存在的自体集，S（t）是由 S（t-1）演变而来的，包含一次响应保留下来的 Sretain（t-1）（方程（5））和需要进行变异的 Supdate（t-1）（方程（6）），还有 t时刻由待测检测器检测转变的和新增的Snew（t）（方程 （7））， 其中待测检测器转变包含uncertain，通过改变r可将其归为 S′。

1.1.3 nonself定义

定义非自体集：T={X1，…，Xn，0}，其中 X1，…，Xn代表检测器的特征码，f=0代表此检测器状态为异常。网络是个动态环境，随着时间T的推移，非自体也在变化，方程（8）所表示是t时刻所存在的非自体类别，T（t）是由 T（t-1）演变而来的，包含一次响应保留下来的 Tretain（t-1）（方程（9））和需要进行变异的 Tupdate（t-1）（方程（10）），为了防止检测器冗余，提高检测器的有效率，对非自体集进行耐受以排除相似或相近的检测器Tdetection（t）（方程（11））。 t时刻由待测检测器检测转变的与新增加的Tnew（t），其中待测检测器转变包含 uncertain，通过改变 r可将其归为 T′（方程（12））。

1.2 切割否定选择算法[3]

根据故障诊断检测中所采用在自己空间变异搜索来训练检测器的阴性选择算法，采用非己空间变异搜索的故障检测算法[4-7]，采用空间切割否定选择算法。如图1所示，检测器的生成有固定检测器，变长检测器，和基于切割的检测器，固定检测器由于检测器检测范围的不可变性，容易引起漏洞的产生，造成系统检测率和检测效率均不高。可变检测器算法中候补检测器的空间生成位置存在不确定性，相同检测器可检测出部分相同的异常数据，动态调节检测器的大小同样会使得某些检测器成为冗余检测器。因为需采用一种自适应的成熟检测器生成算法，在动态调整检测器检测范围的同时防止冗余的产生。

图1 检测器的生成方式Fig.1 Generation mode of detector

切割检测器可以有效防止漏洞产生，同时与固定和变长的检测器相比较，可以用较少的成熟检测器检测同样区域的抗原，并且有效防止检测器生成冗余。

本文所涉及的是对于二进制代码串，进行匹配阈值为固定r，可变阈值 r，矩形切割（方程 13），此方程主要是对自体在耐受中，匹配值达到R时，进行相同部分取反。中所引用的CNSA算法如图2所示。

图2 CNSA算法流程图Fig.2 Flow chart of CNSA algorithm

检测器生成算法步骤如下：

Step1：匹配待测检测器 D（x）与自体集 S，观察 match（s，d）的匹配值；

Step2： 当 match（d，s）≥R 时，将相同的特征码取反变成新的检测器 D′（x）；

Step3：将D′（x）与 S匹配看是否小于 r，满足时变成非自体集 Tnew，否则r自增，返回Step2；

Step4：当 match（d，s）时〈R，看是否 match（d，s）〈r，满足时检测器为Tnew，否则r自增，直到不发生匹配，则为Snew。

检测器检测阶段原理如图3所示。

图3 检测器检测阶段的流程图Fig.3 Flow chart of detector phase

该算法步骤如下：

Step1：待测检测器d与检测器集m相匹配，观察匹配值；

Step2：当 match（d，m）≥R 时，且 m 属于自体集 S，进行CNSA算法；

Step3：当 match（d，m）≥R 时，且 m 属于非自体集 T，删除该检测器（防止产生冗余）；

Step4：当 match（d，s）〈R 时，且 m 属于 T，直到其匹配值不等于 r，则 d属于 Tnew；

Step5：当 match（d，s）〈R 时，且 m 属于 T，match（d，m）〈r，则 d属于Snew；

Step6：当 match（d，s）〈R 时，且 m 属于 S，进行 CNSA 算法。

2 仿真和实验

2.1 仿真

在自体集有限的条件下，比较RV，RVVD和CNSA算法的检测效率（图4，图5），RV算法中检测阈值 r固定，因此检测率上升趋势平稳且相对较低。又因r相对自体长度较大容易造成漏洞产生，导致检测率低下，候选检测器产生的随机性也使得检测率难以提高。参与耐受自体数量为10时，算法最高检测率只能达到90.62%，如图4；自体数量为40时候，最高检测率只有78%，如图5。RVVD算法动态改变检测器识别范围r，使用识别范围较小的检测器以弥补漏洞的产生，并通过消除大量冗余提高检测效率，图中其检测率上升幅度相对RV算法较大，但当且仅当参与检测的成熟检测器数增加到一定范围内，才一可提高其检测率到较高水平。CNSA算法只需较少成熟检测器即可识别较大范围的非自体抗原，保证较高检测率，当参与检测的成熟检测器数量一定时，其检测率明显具有优势；进一步也可以看出，本算法成功的减少了漏洞的产生，只需相对较少的成熟检测器即可使得检测率维持在90%以上，有效地保证了人工免疫系统的安全性。

图4 自体集数目为10

图5 自体集数目为40

2.2 实验

在计算机病毒检测中，利用特征码检测器可以检测未知病毒，提高计算机主动防御病毒的安全性。采取KDDcup99[8]数据，从数据筛选分析数据来源3种协议不同的数据包分别是TCP，UDP和ICMP 3种类型。从大量的数据集中TCP所占的79.21%，所以为了便于对TCP连接记录进行分析，观察41个属性特征信息选用具有代表性能体现出状态变化的8个数 据 是 连 续 的 特 征 ：src_bytes、dst_bytes、count、srv_count、srror_rate、srv_serror_rate、same_srv_rate、diff_srv_rate。 对样本数据进行预处理，得到长度为32位的二进制字符串，匹配长度R取值15，匹配r取值9。

由于数据量庞大，选取部分数据作为实验数据。本文选择抽样每个选取8000条数据作为训练数据，其中正常数据5000条，异常数据3000条。抽取正常数据作为自体集，训练集中的入侵数据包括DoS攻击和R2L攻击。正常数据3000条，入侵数据2000条。其中入侵数据包括已知入侵和未知入侵。

实验采用测试数据进行测试，在入侵数据大于自体集数据的情况下，自体集是随机抽样，为使检测器的检测率达到99%，随着自体数的增加迭代次数T在减少，需要的实验结果如表1所示。试验结果表明在确保检测率达到99%，检测等量入侵检测器，在随着自体集数目递增的情况下，需要迭代的次数在递减，说明随着自体集的逐步完善，检测率会逐步提高，所用的时间会减少。自体集不同分布情况影响检测器生成的迭代次数。

表1 自体集的个数与入侵检测器个数之间的关系Tab.1 The relationship between number of selfset and number of non-selfset

3 结 论

本文提出一种新的否定选择算法生成检测器的方法，该算法通过自体耐受生成检测器防止漏洞产生，能有效提高病毒的检测率；通过递增改变阈值减少黑洞产生，有效阻止误报率产生；通过对检测器集自体耐受防止检测集产生冗余。此外，该算法的不足之处，随着自体集的扩增，生成庞大的检测器，计算复杂度和搜索时间相应增大，在这一方面改进，还需进一步研究。

[1] ZHAO Bing-je， SUN Fu-xiong， XIE Wei.The research of generation algorithm of detectors in immune-based detection model [C]// International Symposium on Knowledge Acquisition and Modeling， 2008：693-697.

[2] QIN Ren-chao， LI Tao， ZHANG Yu.An immunity based computer virus detection method with GA-RVNS[C]//Second International Symposium on Intelligent Information Technology Application，2008：864-868.

[3] ZENG Jin-quan， LI Tao， LIU Xiao-jie.A feedback negative selection algorithm to anomaly detection [C]//Third International Conference on Natural Computation（ICNC 2007），2007：575-579.

[4] ZHAO Yu-feng，FU Dong-mei.An improved artificial immune network optimization algorithm and its performance analysis[J].2009，19（4）：434-445.

[5] WANG Qian，FENG Xiao-kai.A detector generation algorithm based on negative selection [C]//Fourth International Conference on National Computation，2008：605-611.

[6] ZHANG Qing-hua， SHAO Long-qiu， ZHANG Ya-she.Design of unit fault diagnosis system software based on artificial immune system [C]//2008 International Conference on Computer Science and Software Engineering， 2008：431-435.

[7] ZHANG Qing-hua，QIAN Yu，XU Bu-hong， et al.Application study of non-dimension-parameter to fault diagnosis technology in artificial immune system [J].Noise and Vibration Control，2008（1）：89-92.

[8] ZHANG Qing-hua，QIAN Yu，XU Bu-gong， et al.Negative selection algorithm of the method of mutation search in self space to train detector[J].Computer Application，2007（3）：627-629.