一种分段检测器集合生成算法的研究与实现

张小梅

（兰州资源环境职业技术学院 信息管理系，甘肃 兰州 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的规模，最后利用递归求解的序号，随机生成检测器。于是，检测器集合生成算法描述如下：

步骤（1）：推导递归公式，计算候选检测器C的规模

（1）规定 Ci[s]为模板 Ti，s的右实现中所有与 s未匹配的字符串总数。其中，字符串s的长度为r。根据i的值分情况处理：

①i=l-r+1

此种情况下，Ti，s由 l-r个未确定的位和连续的 r个确定的位组成，其中，l-r个未确定的位在左边，r个确定的位紧跟在l-r个未确定位的后边，于是，模板的右实现就是该模板本身。由此得到Cl-r+1[s]的值为：

此种情况下，找出i+1位置开始的未被匹配的右实现的数量，即可求出模板的未被匹配右实现数量。当Ti，s与S中的位串相匹配时，Ci[s]=0；不匹配时，则在 Ti，s的 r连续位后附加1或0，于是，求模板的未被匹配的右实现数量，就变成了求s←.m的右实现数量。于是得到如下递归公式：

（2）对未匹配的空间，根据 r位字符串 s进行分割，这一过程记作C1[.]。C1[s]代表每个分隔空间的大小。对从s开始的所有未被匹配的字符串，在字符串s后的相应位上附加 1或 0，记作 C[s→.m]。 同样地，C2[.]可看作是对未被匹配空间的进一步分割。以此类推，从C3[.]到Cl-r+1[.]进行更加详细地分割。经过Cl-r+1[.]分割后，每个分割便是一个长度为l的字符串。

（3）循环，重复 l-r+1 次。

①计算2r个字符串s的右实现Ci[s]。

循环结束后，C1[.]的右实现就是一个所有位均被确定且长度为l的字符串。因此，由r位字符串s开始的未被S匹配的长度为l的字符串的总数是个C1[s]。于是得到未被匹配的字符串数目为：

步骤（2）：生成未被匹配的检测器集合

（1）给每个未被匹配的字符串分配1…sum序号。

（2）根据分配的序号，查找生成相应的字符串。生成相应的未被S匹配的字符串的步骤如下：

以此类推，形成了一个完整的字符串s1。

该算法需要一个（l-r）×2r维的数组，用来存放两个字符串可能r连续位匹配的所有情形。因此，它的空间复杂度为：O（2r（l-r）2），时间复 杂度为：O（2r（l-r））+O（Ns（l-r））+O（NRl）。

3 算法在实际工程中的应用

尝试将本文的研究内容应于实际的工程。利用本文算法开发出一套故障诊断在线检测监测系统。以YVP系列45 kW异步电机为实验对象，对正常电机和三种故障电机（电机输出轴失衡、电机轴承噪音大、电机转子动偏心）进行训练学习。

（1）采集各种工况下的电机振动信号，消噪并进行特征提取；

（2）将反映信号特征矢量数据归一化处理，组成字符串，长度为 6；

（3）将字符串各位上的数值范围变换到区间0～1范围内，并放大区间至 0～100；

（4）将区间 0～100划分为 60个小区间，并按从小到大的顺序依次编号为 0，1，2…59；

（5）将相应的数据进行二进制编码，结合自体集生成方法，对应的子空间分别由 3 600，4 800，6 000，10 000个自体数据串组成。于是，整个自体空间的自体数据串为24 400个。

采用3个连续位匹配方法，假定检测器未检测到异常的概率为5%，即检测的准确率为95%，那么，由式（4）可知，只要生成73 096个抗体字符串即可达到要求。

通过对表1所列的差速器样本的检测，得到实验检测数据。

表1 实验检测结果

该算法的检测准确率高于90%，虽然未达到预先设定的95%的检测率（这是由于“孔洞”[2]问题导致的），但是已经满足了故障在线检测问题的需求。而且，该算法在生成检测器集合时，所花费的时间为2分42秒，而传统否定算法则需要5分33秒，可见，改进后的算法的时间性能提高显著。

论文将检测器集合的生成分段进行，并对算法的性能进行了验证。实验结果表明，本文的检测器生成算法的匹配速度更快，且能够有效地提高检测效率，减小漏报率与误报率，具有实际的工程应用价值，为进一步研究入侵检测系统提供了新的算法依据。

[1]ROEKE A J， DEMARA R F.Confidant： Collaborative ObjeetNotifieation Framework forInsiderDefense using AutonomousNetwork Transactions.AutonomousAgentsand Multi-Agent System[J].2006（1）.

[2]FORREST S， PERELSON A， A LLEN L， et al.Selfnonself discrim ination in a computer[C].In Proceedings IEEE Symposium on Research in Security and Privacy，Los A lan itos，CA，1994，IEEE Computer Society Press.

[3]FORREST S，HOFMEYR S A.Engineeringanimmune system[J].Graft，2001（4）：5-9.

[4]BALTHROP J， FORREST S， GLICKMAN M R.Revisting L ISYS：parameters and normal behavior[C].In Procceding of the 2002 Congress on Evolutionary Computation CEC 2002.

[5]FAMER J D， PACKARD N H， PERELSON A S.The immune system， adaptation， and machine learning[J].Physical D，1996.

[6]ZHANG H， WU L F， ZHANG Y S， et al.An algorithm of r-adjustable negative selection algorithm and its simulation analysis[J]. Chinese Journal of Computers， 2005， 28（10）：1614-1619（in Chinese with English abstract）

[7]SMITH R， FORREST S.Searching for diverse， cooperative populations with genetic algorithm[J].Evolutionary Computation，1993.