基于并行计算的木马免疫算法研究

摘要：传统的木马检测技术在检测正确率、误报率和漏报率上都有不足，针时传统阴性选择算法在检测效率上的不足，提出一种基于并行计算的多特征区域匹配算法。这个算法首先把随机字符串分为多个特征区域，每个特征区域内对应一个检测器集合进行匹配，而且特征区域之间采用r连续位匹配方式再次匹配，同时采用并行计算，设置匹配阈值进行匹配确认。实验证明改进的阴性选择算法在匹配位数和随机字符串位数增加时，候选检测器增加速度较平缓，系统负担增加较缓慢，因此具有较好的检测效率。
关键词：并行计算；木马检测；免疫；算法

免疫算法是借鉴生物免疫系统中抗体识别抗原的原理发展起来的，是人工智能的一个新的研究领域，也是目前国内外研究的一大热点，许多研究学者都针对这一领域开展了深入、富有成效的研究工作。免疫算法主要模拟生物免疫系统中抗原处理的核心原理，运用免疫算法求解问题，本质上是抗体识别抗原的过程，而抗体(检测器)的产生是非常关键的一个步骤，关系到整个免疫检测系统的运行效率。
常见免疫算法主要有阴性选择算法和克隆选择算法等。阴性选择算法由Forrest等人在1994年提出，该算法步骤简单，但却实用有效，阴性选择算法以r连续位匹配规则为基础，实现局部匹配，算法效率较高。但其也存在着致命缺陷，因为当检测字符长度增加或者匹配位数r增加时，检测效率大大降低，系统开销大大增加。
文中提出一种改进的阴性选择算法，把总长度为L的字符串分成n个特征区域时，每一段特征区域产生一系列相应的检测器子集合，然后采用并行计算的匹配方式，对于整体则采用r连续位匹配规则进行匹配。设定匹配阈值，如果匹配度高于该阈值则两个字符串匹配，否则不匹配。

1 阴性选择算法
在免疫系统中，按照机体内外可以把整个机体分为“自我”和“非我”。将所要维护的正常模式行为或者系统的静态行为定义成“自我”，将异常行为模式定义为“非我”。阴性选择算法是个否定选择过程，目的在于区分“自我”和“非我”。设免疫系统整个空间为U，“自我”为S，“非我”为N，它们满足关系式：U=S∪N，S∩N=φ。阴性选择算法以r连续位匹配规则为基础，r代表一个阈值，是衡量单个检测器能匹配字符串子集大小的指标。
图1给出了采用阴性选择算法产生检测器的流程。

Forrest阴性选择免疫算法简述如下：1)分析问题，根据实际问题确定参数PM、NS、Pf、r，其中PM为匹配概率，NS为自体个数，Pf为期望的检测失败率，r为阈值；2)随机产生NS个长度为L的二进制字符串作为自体；3)计算所需检测器个数NR与候选检测器个数NH；4)产生检测器，即随机产生一个长度为L的字符串，并与自体进行比较，如果随机产生的字符串与自体中任何一个字符串匹配，则丢弃该字符串；如果随机产生的字符串与自体中所有字符串都不匹配，则保留该字符串作为检测器。重复该过程直到得到NR个检测器。其重复次数即为候选检测器个数NH；5)验证检测效果，即改变自体中的某个字符串，并用所有检测器与自体进行逐个比较，若出现匹配则表明检测成功否则检测失败。

由表1可知，匹配概率PM、检测失败率Pf对系统整体性能有很大影响。设定检测失败率只和自体规模NS在一定范围内的时候，决定候选检测器规模NH和检测器规模NR的只有匹配概率PM。当PM增大，NH和NR呈指数形式增加，这将导致检测时间大幅增加。而NH决定着系统的整体运行时间，NR决定着系统所占用的空间，因此PM的选择范围对整个系统性能起着决定性作用。传统阴性选择算法采用随机生成字符串的形式，匹配概率PM的值就由两个字符串间的匹配规则、匹配位数来决定。