基于多种群遗传算法的检测器生成算法研究

Research on Detector Generation Algorithm Based on Multiple Populations GA

有效的检测器生成算法是异常检测的核心问题,针对现有算法存在检测率低、匹配阈值固定、检测器集合庞大等问题,本文提出了基于多种群遗传算法的检测器生成算法,根据形态学空间的分析和覆盖问题原理,自体集根据特征进行划分,各个种群根据划分独立按遗传算法进化,最后求得所有检测器种群的并集得到成熟的检测器.所提出的算法有效降低检测器的冗余度,减少检测器规模,保持检测器的多样性;并利用maxSelf实现匹配阈值r的自适应,适用于多种匹配规则,减小了阈值设置的局限性,给出了算法的检测率高于传统算法的理论证明,并通过实验验证了算法的有效性.另外,通过统计算法的时间复杂度,证明算法时间复杂度没有明显增加.

Efficient detector generation algorithm is the kernel of anomaly detection. Aiming at low true positive （TP） value, unhandy matching threshold value and large detector set size of existent algorithms, a novel detector generation algorithm based on multiple populations genetic algorithm is put forward in this paper. According to morphologic analysis of intrusion detection system and covering problem principle, self set is divided into several partitions on the basis of their characters. Each population evolves according to each self partition independently and their best populations will be combined as the final matured detector set, which decreases redundancy of detectors, minimizes the size of detector set, and maintains diversity of detectors. Matching threshold r is self-adaptive according to maxSelf which enlarges application area of the algorithm by applying several matching rules. The TP value is improved compared with traditional algorithm through theoretical proof and efficiency of the algorithm is testified by simulation tests. Time complexity of the algorithm is analyzed and the algorithm does not have a significant time complexity increase.