高性能正则表达式匹配算法评估

摘要：

为对现有的高性能正则表达式匹配算法进行综合比较与分析,实现诸如DFA、D2FA、CD2FA、mDFA 及XFA 等最新算法,采用Snort 规则集综合评估这些算法的存储空间和匹配时间.实验结果表明,在存储空间方面,与mDFA相比,XFA的存储空间减少84.9%～89.9%;在匹配效率方面,与mDFA 相比,XFA 的匹配时间增加了38.9%～174.6%;XFA 在存储空间和匹配效率上具有良好的可伸缩性,即当规则数增加到8 倍时,mDFA 的存储空间增长了64 倍,而XFA 的存储空间仅增加了16 倍,匹配时间仅增加了61.3%.

关键词：正则表达式匹配、确定有限自动机、扩展有限自动机、性能评估

所属期刊栏目：36

分类号：N945(系统科学)

资助基金：国家自然科学基金资助项目60673155, 90718008

在线出版日期：2010-12-21（万方平台首次上网日期，不代表论文的发表时间）

页数：共3页

页码：269-271