一种面向深度数据包检测的紧凑型正则表达式匹配算法

• 作者: 张大方 谢高岗 金军航 黄昆
• 来源期刊: 中国科学(信息科学)
• 学科: 工学
• 关键词: 网络安全 深度数据包检测 特征匹配 有限自动机 正则表达式
• 年，卷（期）: 2010,（2）
• 页码范围: 356-370
• 页数: 15页
• 分类号: TP274|TP393.08
• 语种: 中文

摘要

深度数据包检测(Deep Packet Inspection,DPI)采用正则表达式匹配算法,将每个数据包内容与一组预定义的特征进行匹配.正则表达式匹配算法是一种多模式特征匹配算法,采用确定型有限自动机(Deterministic Finite Automaton,DFA)表示一组正则表达式特征,实现一次内容扫描可匹配多个特征.基于硬件的正则表达式匹配算法面临存储空间需求大等挑战,即片上嵌入式存储器难以存储日益增长的DFA存储空间需求,从而限制了DPI的性能和可伸缩性.近年来,Smith等人提出了一种基于扩展有限自动机(eXtended Finite Automaton,XFA)的正则表达式匹配算法,即在状态上增加辅助变量和简单操作指令,消除了DFA状态空间爆炸问题,从状态方面减少存储空间需求.为了进一步减少XFA存储空间需求,该文提出了一种基于紧凑型有限自动机(Compact Finite Automaton,CFA)的正则表达式匹配算法,称为紧凑型正则表达式匹配算法.CFA是一种存储高效的有限自动机,即从迁移边方面减少XFA存储空间需求.在CFA构建过程,该文提出了基于优先级的迁移边压缩方法,融合相同目的状态最多的迁移边,从而减少存储空间需求;在CEA匹配过程,该文提出了基于位图的迁移边查找方法,并行查找不同优先级的迁移边子集,从而确保匹配效率.Snort特征规则集的实验结果表明:与XFA相比,CFA在迁移边条数上减少了88.2%,在存储空间大小上减少了83%,在匹配时间上减少了12%.