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

• 作者: 嵩天 李冬妮 汪东升 薛一波
• 来源期刊: 软件学报
• 学科: 工学
• 关键词: 模式匹配 网络安全 网络入侵检测 有限状态自动机 大规模
• 年，卷（期）: 2013,（7）
• 页码范围: 1650-1665
• 页数: 16页
• 分类号: TP393
• 字数: 11657字
• 语种: 中文

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	汪东升	清华大学微处理器与片上系统技术研究中心	74	1037	18.0	29.0
2	薛一波	清华大学微处理器与片上系统技术研究中心	26	215	10.0	13.0
3	李冬妮	北京理工大学计算机学院智能信息技术北京市重点实验室	13	96	6.0	9.0
4	嵩天	北京理工大学计算机学院智能信息技术北京市重点实验室	30	331	10.0	18.0