张小梅

（兰州资源环境职业技术学院 信息管理系，甘肃 兰州 730021）

阴性选择算法是Forrest等人研究出来的应用于计算机安全防护的检测算法[1]，其用于故障检测最大的优势是用有限数量的检测器检测无限种类的故障[2-5]。但这些算法都要检查抗原中长度超过匹配阈值的所有子串是否在检测器中出现，在都未出现的情况下，才能够判断抗原合法，由此导致检测效率较低。国内的一些否定选择算法，如参考文献[6-7]的研究也主要用于这一方面，缺乏对否定选择算法检测效率的研究。

本文深入研究了传统否定算法的缺点及其产生的原因，提出了一种新的分段选择检测器生成算法并加以实现，克服了现有方法的不足。

1 典型的否定选择算法研究

设l表示自体字符串的长度，m表示字符串中使用的符号数目，则对于两个连续r个位匹配的随机字符串，其发生匹配的概率为：

设Ns表示自体集的数目；NR0表示候选检测器的数目；NR表示实际使用检测器数目；Pf表示检测失败的概率，则：

在 式（5）中 ，当 r≤l≤2r 时，T（l）=ml-ml-r（l-r）l-r-1；当 l>2r时，T（l）=2T（l-1）-T（l-r-1），这是一个递归定义。

因此，对于给定的漏检率，为了能够覆盖所能检测到的“非我”空间，需要：

2 基于否定选择的快速检测器生成算法

当否定选择算法采用r连续位匹配规则时，可以考虑对线性时间算法分段实现的方法进行：先推导递归公式，然后利用有限的递归运算解决那些不被S中字符串匹配的循环计数问题，以此计算出候选检测器C的规模，最后利用递归求解的序号，随机生成检测器。于……