电子产品世界

如果采用完全匹配规则(r=L)，则当且仅当两个随机字符串相应位置的每一位字符均相同时，则两个字符串匹配，其匹配概率为PM=1／2L；如果采用部分匹配规则，即rL时，则匹配概率PM≈m-r[(l-r)(m-1)m+1]。当在试验中字符串采用二进制码，即m=2时，匹配概率公式则变为PM≈2-r[(l-r)／2+1]。
候选检测器NH的数量将随着“自我”集合中二进制编码长度的增加成指数级增长，经阴性选择的检测器没有经过冗余检查就直接将其作为成熟检测器中的一个元素进入下一个环节，这可能导致成熟检测器集合R中的数据冗余。尽管在Forrest之后也提出了一些改进方法，如线性算法、贪婪算法、二进制模块算法，但都没有很好地解决上述问题。

2 阴性选择算法的改进
Forrest阴性选择算法中步骤4随机产生一个长度为L的字符串，并与自体进行比较，一般是采用局部匹配的方式进行比较，也就是采用r连续位匹配的方式；如果匹配位数r太小，在“自我”和“非我”相似度较大时，检测器会把“非我”当成“自我”而删除；但是随着r的增加和字符串L的增加，匹配次数呈指数形式增加，匹配效率明显不足，并且会产生大量的候选检测器，使得该算法时间复杂度太大，因此，在实际应用中就存在一个如何选择字串长度和匹配区域的问题。
文中提出一种基于并行计算的多特征区域匹配方式，产生检测器和自体进行匹配，然后对于冗余的候选检测器进行筛选，最后产生成熟检测器。
该算法步骤如下：
1)把总长度为L的字符串分成n个特征区域，每个特征区域长度记为Li(i=1，2，3…，n)；
2)每一段特征区域产生一系列相应的检测器子集合Ni(i=1，2，3…，n)，用这个检测器子集合对相应的特征区域进行特征匹配，各个特征区域的检测器集合是相互独立的，整个字符串的检测器集合N={N1，N2，N3…，Nn}；
3)对于每一个特征区域，采用并行计算的匹配方式，采用多指令流多数据流(MIMD)的体系结构。把自体串和特征区域放人两个数组中进行比较，通过n个处理器并行计算；
4)根据检测器子集合对每一个特征区域进行检测，得到它的匹配长度ri，设定每个特征区域的重要性权值Ii，有0≤ri≤li，0≤Ii≤1；
5)设定Mi表示特征区域的匹配情况，Mi=1表示该特征区域匹配，Mi=0表示不匹配，对于由各个特征区域组成的整体字符串，采用r连续位匹配规则进行匹配，得到它的匹配度R；6)设定匹配阈值μ，如果公式(1)成立，则两个字符串匹配，否则不匹配。

对于r连续位匹配算法，影响算法的主要因素是样本个数、字符串长度和连续位数。运用以往的r连续位算法，要至少遍历两个字符串的对应位置，但是如果采用并行算法，最佳效果是仅匹配一次即可成功，这将大大减少计算量，并增加运行效率。对于木马检测这种对实时反应时间要求较高的匹配模式来说，运用并行算法能较好地提高检测成功率和减少误报率；本算法采用了特征区域生成的办法产生检测器集合，以避免由于匹配区域r增大所带来的效率过低的问题，改进算法能较快速高效地产生满足精度要求的检测器集合。
但是对于各个特征区域，该算法都要产生一系列对应的检测器子集合，各个特征区域的检测器集合是独立的，因此区域与区域之间的检测器有可能会重复，从而产生检测器冗余。针对这个问题，文中加入了冗余检测器筛选步骤，对经过改进的阴性选择算法后产生的候选检测器进行筛选，把它们和已经存在的成熟检测器进行比对，判断该候选检测器是否重复，如果是重复的则删除该检测器，否则把它加入到成熟检测器集合中。

1 2 3

关键词： 并行计算 木马 免疫 算法研究