存储有效的多模式匹配算法和体系结构*

摘要

cqvip:多模式匹配是基于内容检测的网络安全系统的重要功能，同时，它在很多领域具有广泛的应用．实际应用中，高速且性能稳定的大规模模式匹配方法需求迫切，尤其是能够在线实时处理网络包的匹配体系结构．介绍了一种存储有效的高速大规模模式匹配算法及相关体系结构．研究从算法所基于的理论入手，提出了缓存状态机模型，并结合状态机中转换规则分类，提出了交叉转换规则动态生成的匹配算法ACC（Aho．Corasick．CDFA）．该算法通过动态生成转换规则降低了生成状态机的规模，适用于大规模模式集．进一步提出了基于该算法的体系结构设计．采用网络安全系统中真实模式集进行的实验结果表明，该算法相比其他状态机类模式匹配算法，可以进一步减少80％-95％的状态机规模，存储空间降低40．7％，存储效率提高近2倍’算法单硬件结构实现可以达到11Gbps的匹配速度．