第2期 王辉，等：一种可变模糊匹配阴性选择算法 ·179… 用变阈值思想，通过阈值r的调整来减少“黑洞”的 符串Z在T中对应位置上所包含的一系列子串，则 数量.为了提高检测器集的检测效率，利用模糊思 模式串T和Z的连续相似度记为lxsd(Z,T),计算 想，提出了连续相似度与背离度的概念，实现了模糊 式(2)： 匹配，并生成了有效检测器集，提高了系统的检测效 Ixsd(Z,T)=max(Len(Thik;))/Len(T).(2) 率和性能， 式中：max(Len(T,))表示所有连续相同子串长度 的最大值.例如，串B:0111001011001,串Z: 1阴性选择算法及其存在的问题分析 0100110111000,其连续相似度为xsd(Z,B)=max 免疫系统首要任务就是能够区分自己和非己物 (24)/13=4/13=0.3077. 质，并通过免疫应答来发现外来入侵，执行免疫功 定义3背离度.设模式串T=‘t1…tn’和目 能6，这就是免疫系统的自体-非自体识别原理. 标串Z=‘2云n’均为二进制字符串，则字符串Z 1994年Forrest等人[78]基于此原理提出了阴性选择 与模式串T的背离度定义为bld(Z,T)= 算法，实现了自体耐受， 1-xsid(Z,T)=1-ELen(Thi /Len(T). 阴性选择算法描述如下： 例如，对于上述串B和串Z,则背离度为bld 随机生成未成熟检测器； (Z,B)=1-xsid(Z,B）=1-∑Len(Bi,g)/ While(成熟检测器集合还没有产生) Len(B)=1-(2+4)/13=0.5385.背离度体现了2 {计算一个未成熟检测器与自体的亲和力； 个字符串的完全背离程度，即2个字符串对应位不 (未成熟检测器与自体集匹配)该检测器 相同的字符所占的比例 不能成熟； 定义4匹配.在一定匹配规则下，2个模式串 else该检测器成熟，加入到检测器集合中； T和Z的连续相似度超过匹配阈值r/Len(T),则称 . T和Z匹配，记为Ppei(T,Z) 利用经过耐受的成熟检测器集识别非自体，利 2.2算法描述 用阴性选择算法可以在没有先验知识的情况下，对 可变模糊匹配阴性选择算法分2部分，第1部 未知入侵进行有效防御.因此，阴性选择算法主要应 分为可变模糊匹配算法实现，第2部分为生成有效 用在异常检测方面，但在检测过程中存在“黑洞”问 检测器集算法实现9. 题.黑洞的存在取决于模式集的结构及模式匹配所 可变模糊匹配算法实现， 采用的匹配规则6].自我模式集与非我模式集越相 1)定义自我集S为长度L的字符串集， 似，黑洞的数量就会越多.由于黑洞不可能被任何检 2)设置初始阈值r1,计算bldf(背离度阈值)及 测器检测到，因此应尽可能减少黑洞的数量及其出 xsdf(连续相似度阈值). 现的概率， 3)随机生成长度为L的未成熟检测器A,将A 依次与自我集S进行模糊匹配. 2可变模糊匹配阴性选择算法 4)若A未与自我集发生任何匹配，则A成熟， 2.1相关定义 将A及其匹配阈值加入到检测器集中、若检测器个 定义1相似度.设模式串T=‘t2…tn’和目 数已达到要求，转到7)；否则，转到3)· 标串Z=‘a12名n’均为二进制字符串，字符串Z与 5)否则，S中还有未与A进行匹配操作的个体， 模式串T的相似程度记为xsid(Z,T),计算式(1)： 计算A与S中未操作的当前个体的相应背离度.若 xsid(Z,T)=>Len(Thihi)/Len(T).(1) 背离度超过阈值，转到4)；否则，计算连续相似度. 式中：T,为字符串Z在T中对应位置上所包含的 6)若连续相似度未超过阈值，转到4)：超过阈 一系列子串TL,2,T8,4,…,TM,g(1≤h1≤h2<h3≤ 值，调整匹配阈值为'，若'>T。,转到3)，否则，转 h4,…<h.≤h,≤n),Len表示字符串的长度.显然当 到4). xsid(Z,T)=1时，Z=T,Z与T精确匹配 7)生成有效检测器集. 定义2连续相似度.对于2个模式串T=‘t2 算法流程图如图1所示。 …tn’和Z=‘a12zn’,设TM(1≤h:≤h,≤n)为字