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

	一种面向深度数据包检测的紧凑型正则表达式匹配算法
	金军航 1; 黄昆1 ; 张大方 1; 谢高岗 2
	2010
发表期刊	中国科学. 信息科学
ISSN	1674-7267
卷号	40 期号:2 页码:356
摘要	深度数据包检测(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%
关键词	网络安全深度数据包检测特征匹配有限自动机正则表达式
语种	英语
文献类型	期刊论文
条目标识符	http://119.78.100.204/handle/2XEOYT63/36928
专题	中国科学院计算技术研究所期刊论文_中文
作者单位	1.湖南大学 2.中国科学院计算技术研究所
推荐引用方式 GB/T 7714	金军航,黄昆,张大方,等. 一种面向深度数据包检测的紧凑型正则表达式匹配算法[J]. 中国科学. 信息科学,2010,40(2):356.
APA	金军航,黄昆,张大方,&谢高岗.(2010).一种面向深度数据包检测的紧凑型正则表达式匹配算法.中国科学. 信息科学,40(2),356.
MLA	金军航,et al."一种面向深度数据包检测的紧凑型正则表达式匹配算法".中国科学. 信息科学 40.2(2010):356.