| 存储有效的多模式匹配算法和体系结构 |
| |
| 作者姓名： | 嵩天 李冬妮 汪东升 薛一波 |
| |
| 作者单位： | 北京理工大学 计算机学院 智能信息技术北京市重点实验室, 北京 100081;北京理工大学 计算机学院 智能信息技术北京市重点实验室, 北京 100081;清华大学 微处理器与片上系统技术研究中心, 北京 100084;清华大学 微处理器与片上系统技术研究中心, 北京 100084 |
| |
| 基金项目： | 国家自然科学基金(60803002, 61272510, 60833004, 60970002); 国家高技术研究发展计划(863)(2012AA010905);北京市重点学科建设项目; 北京市自然科学基金(4122069) |
| |
| 摘 要： | 多模式匹配是基于内容检测的网络安全系统的重要功能,同时,它在很多领域具有广泛的应用.实际应用中,高速且性能稳定的大规模模式匹配方法需求迫切,尤其是能够在线实时处理网络包的匹配体系结构.介绍了一种存储有效的高速大规模模式匹配算法及相关体系结构.研究从算法所基于的理论入手,提出了缓存状态机模型,并结合状态机中转换规则分类,提出了交叉转换规则动态生成的匹配算法ACC(Aho-Corasick-CDFA).该算法通过动态生成转换规则降低了生成状态机的规模,适用于大规模模式集.进一步提出了基于该算法的体系结构设计.采用网络安全系统中真实模式集进行的实验结果表明,该算法相比其他状态机类模式匹配算法,可以进一步减少80%~95%的状态机规模,存储空间降低40.7%,存储效率提高近2 倍,算法单硬件结构实现可以达到11Gbps 的匹配速度.
|
| 关 键 词： | 模式匹配 网络安全 网络入侵检测 有限状态自动机 大规模 |
| 收稿时间： | 2011-03-17 |
| 修稿时间： | 2012-04-24 |
|
| 点击此处可从《软件学报》浏览原始摘要信息 |
|
点击此处可从《软件学报》下载免费的PDF全文 |
|
