论文部分内容阅读
字符串匹配算法一直是计算机科学的研究热点,尤其是信息时代数据爆炸式的增长对字符串匹配算法的性能提出了更高的要求。在信息安全领域中,关键字规模大,实时性要求高、匹配数据复杂多变使得大规模URL关键字的多模匹配算法中巨大的内存消耗成为当今入侵检测等信息安全系统的性能瓶颈。本文研究了多种精确多模匹配算法,总结并分析各算法的优缺点。深入分析了大规模URL关键字的长度特征和匹配需求特征,总结出URL关键字中,长度较长的URL关键字较多,短关键字较少,且具有与表达式匹配需求的关键字比例较少的特点。提出针对大规模URL关键字匹配的性能优化算法PMUC(Multi-pattern Matching Algorithm for URL Based on Classification),该算法结合AC算法和Wu-Mamber算法的优势,对URL关键字进行分类匹配,达到性能优化的目的。对经典的AC算法和Wu-Mamber算法均进行了改进,将长度较短且具有与表达式匹配需求的关键字使用AC算法的改进算法GFAM进行匹配,其余关键字使用Wu-Mamber算法的改进算法WMS进行匹配。本文实现了基于PMUC算法进行性能优化后的URL关键字多模匹配模块,并加入到可扩展的入侵监测系统进行性能测试。离线测试首先测试优化后的匹配算法的正确性,在验证算法正确性的基础上给出了优化后的匹配模块性能与原匹配模块性能的对比结果,同时仔细调整了分类参数:分类长度m和自动机深度D,测试了调整参数对算法的性能影响,给出基于14万条配置的参数经验值。在线测试使用真实的网络动态数据,认为算法针对大规模URL关键字匹配具有实际应用价值。实验结果表明使用PMUC算法对匹配模块进行性能优化后,内存可压缩为未优化前的5%以内,同时针对大规模URL关键字的初始化时间有明显的缩短。