论文部分内容阅读
字符串匹配一直都是计算机科学的研究热点和难点。在信息安全领域中,关键字规模变大、互联网流量的增加,使得字符串匹配算法成为网络安全系统的性能瓶颈。本论文首先综述了三种经典的多模式精确匹配算法,深入总结了这三种算法的优缺点。然后,在深入分析了现有规则集合的基础上,总结出了千万模式集合的特点。其次,针对千万模式集合匹配的需求,设计了基于AVL树的AC优化算法ACVL和基于分类思想的多模匹配算法CDWH两种算法。ACVL算法是利用AVL树来优化AC算法的内存占用情况,使AC算法可以支持千万模式集合的要求,同时还给出了ACVL算法的优化方面,使用规则去重、状态压缩、路径压缩三种方法来进一步压缩内存,实验表明ACVL算法在加载千万模式集合时使用内存仅为2.5G。CDWH算法是利用分类的思想,将模式集合分为长字符串模式集合和短字符串模式集合,然后分别采用DAT算法和WM算法进行匹配。CDWH算法还对DAT算法进行了内存压缩和缩短初始化时间的优化,并对WM算法进行了Hash冲突集减小和加快完全匹配速度的优化。最后,本论文分别实现了ACVL算法和CDWH算法,以可扩展的方式支持真实系统的运行,并进行了性能测试。离线测试分别测试算法的正确性,以及算法在不同规则模式集下的性能表现,包括初始化时间、占用内存量和扫描时间等。在线测试则测试了ACVL算法和CDWH算法的扫描速度。然后比较了ACVL算法和CDWH算法的测试结果,结果表明CDWH算法明显优于ACVL算法,它可以为系统带来21.4%的性能提升。