深度包检测中一种高效的正则表达式压缩算法

摘要：

提出一种基于确定的有穷状态自动机(deterministic finite automaton,简称DFA)的正则表达式压缩算法.首先,定义了膨胀率DR(distending rate)来描述正则表达式的膨胀特性.然后基于DR提出一种分片的算法RECCADR (regular expressions cut and combine algorithm based on DR),有效地选择出导致DFA状态膨胀的片段并隔离,降低了单个正则表达式存储需求.同时,基于正则表达式的组合关系提出一种选择性分群算法REGADR(regular expressions group algorithm based on DR),在可以接受的存储需求总量下,通过选择性分群大幅度减少了状态机的个数,有效地降低了匹配算法的复杂性.

关键词：正则表达式、确定的有穷状态自动机(deterministic、finite、automaton、简称DFA)、深度包检测(deep、packet、inspection、简称DPI)、多模式匹配算法、入侵检测

所属期刊栏目：20

分类号：TP393(计算技术、计算机技术)

资助基金：the National High-Tech Research and Development Plan of China under Grant No.2007AA01Z214 国家高技术研究发展计划863;the Youth Foundation of the Computer Network Information Center;the Chinese Academy of Sciences under Grant No.0714071101

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

页数：共13页

页码：2214-2226