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

Efficient Regular Expression Compression Algorithm for Deep Packet Inspection

作　　者：徐乾[1,2] 鄂跃鹏[1,2] 葛敬国[1] 钱华林[1] 

机构地区：[1]中国科学院计算机网络信息中心,北京100190 [2]中国科学院研究生院,北京100049

出　　处：《软件学报》2009年第8期2214-2226,共13页Journal of Software

基　　金：国家高技术研究发展计划(863)No.2007AA01Z214;CNIC青年基金No.0714071101~~

摘　　要：提出一种基于确定的有穷状态自动机(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),在可以接受的存储需求总量下,通过选择性分群大幅度减少了状态机的个数,有效地降低了匹配算法的复杂性.A memory efficient regular expression compression algorithm is devised for deep packet inspection. First, a parameter DR （distending rate） is defined to quantify the explosive quality of regular expressions. Then based on DR, a regular expression cutting algorithm is proposed to downsize the storage needs of individual regular expression, by detecting and confining the parts which cause DFA （deterministic finite automaton） states＇ exponential growth. Then according to the relation of different regular expressions, a selective grouping algorithm is introduced for regular expression sets, which could cut down the number of finite automata, and reduce the runtime memory consumption.

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

分 类 号：TP393[自动化与计算机技术—计算机应用技术]