2009年10月Journal on Communications October 2009 第30卷第10A期通信学报V ol.30No.10A
正则表达式的DFA压缩算法
杨毅夫1,2,3，刘燕兵1,2,3，刘萍1,3，郭牧怡1,2,3，郭莉1,3
(1. 中国科学院计算技术研究所，北京 100190；2. 中国科学院研究生院，北京 100039;
3. 信息内容安全技术国家工程实验室，北京 100190)
摘要：基于确定有限自动机（DFA）的正则表达式匹配技术通常用于网络流量实时处理、病毒检测等系统中。
随着正则表达式的数量不断增加，DFA的存储空间急剧膨胀。为此，提出了一种有效的DFA压缩算法——簇分割算法，首先总结了DFA的一个结构特征；然后依据此特征把DFA分割为3个部分分别存入3个矩阵中，由此构造出2个特征明显的矩阵和1个典型的稀疏矩阵；最后分别对3个矩阵进行压缩。实验表明，簇分割算法在各组数据中均达到了很好的压缩效果，空间压缩率比较稳定。
关键词：字符串匹配；自动机压缩；正则表达式；入侵检测
中图分类号：TP302 文献标识码：A 文章编号：1000-436X(2009)10A-0036-07
Effective algorithm of compressing regular expressions’ DFA
YANG Yi-fu1,2,3, LIU Yan-bing1,2,3, LIU Ping1,3, GUO Mu-yi1,2,3,GUO Li1,3
(1. Institute of Computing Technology Chinese Academy of Sciences, Beijing 100190, China;
2. Graduate University of Chinese Academy of Sciences, Beijing 100039, China；
3. National Engineering Laboratory for Information Security Technologies, Beijing 100190, China)
Abstract: Regular expression matching technology based on DFA is often used in network real-time processing and virus detection systems. With the number of regular expressions growing, the storage of DFA expands rapidly. An effective al-gorithm of compressing regular expressions’ DFA was presented, which was called cluster-split algorithm. Firstly, a structural characteristic of DFA was summarized. Secondly, the DFA was divided into three parts based the characteristic.
Finally, the three parts was compressed respectively. Experiments show that cluster-split algorithm achieves good effects in all test data, and its space compression rate is relatively stable.
Key words: string matching; automaton compression; regular expressions; intrusion detection
1引言
近年来，正则表达式匹配技术成为计算机安全领域研究的热点问题。正则表达式广泛应用于入侵检测/入侵防御、病毒检测、协议识别等系统中，如Snort[1]、Bro[2]、L7-filter[3]等。随着网络带宽和流量的膨胀以及需要处理的正则表达式规模的不断增加，传统的正则表达式匹配技术正面临严峻的挑战。
传统的正则表达式匹配技术主要是基于非确定有限自动机（NFA）实现的，其匹配速度较慢，并且每次匹配都需要逐条扫描每条表达式。随着表达式规模不断扩大，基于NFA的匹配技术性能急剧下降，已经不能满足应用的需求，因此人们使用匹配速度更快的基于DFA的匹配技术来代替传统的
收稿日期：2009-08-08
基金项目：国家重点基础研究发展计划（“973”计划）基金资助项目（2007CB311100）Foundation Item: The National Basic Research Program of China (973 Program)(2007CB311100)
第10A期杨毅夫等：正则表达式的DFA压缩算法·37·
匹配技术。然而DFA同时带来了另一个问题：DFA 的状态数量有可能指数增加从而导致存储空间急剧增加。例如正则表达式.*AB.{1024}CD对应的DFA的状态规模高达O(21024)。目前对正则表达式的研究主要集中在如何压缩DFA的存储空间，以达到用较少存储空间获取较快匹配速度的目的。
针对DFA占用存储空间过大的问题，本文提出了一种DFA的压缩算法——“簇”分割压缩算法。文章给出了“簇”的定义，并且根据“簇”把DFA 分割成几个部分，然后分别对这些部分进行压缩。本文第2节介绍DFA压缩的相关工作，第3节详细描述簇分割压缩算法，第4节通过详细的实验分析算法的有效性，第5节是结束语。
2 相关工作
正则表达式匹配问题是计算机领域的经典问题，文献[4~6]在正则表达式匹配理论和算法的研究方面卓有成效；随着正则表达式在应用系统中的广泛使用，人们更加关注匹配技术在系统中的实际效果。在实际的系统中，如何降低DFA的状态规模、减少DFA的存储空间仍是研究的焦点。
Fang Y u在文献[7]中用规则分类和规则改写的方法来化简正则表达式。文中依据正则表达式转化成确定有限自动机的状态数规模，把正则表达式分为5类，并提出了2条改写规则以DFA的状态规模。但是经过上述规则改写后的表达式并不与原来的表达式完全等价，只适合于非重叠匹配（non-overlapping match）的情况，因此限制了它的使用范围。
Kumar在文献[8]中提出了D2FA方法来压缩DFA的存储空间。通过引入默认转移边（default transition）来减少转移边的数目，从而降低自动机的存储空间。引入默认转移边能极大地减少了确定DFA的转移边，该文的实验表明，该方法平均能够减少95%的转移边。但是该方法的缺陷是，每处理一个字符可能需要在D2FA中进行多次状态跳转，导致实际的匹配性能不高。
Ficara在文献[9]中提出了δFA方法来压缩DFA 的状态表。该方法提取子状态和父状态的相同元素来消除状态转换表的冗余。在状态访问序列中，如果当前状态t要访问的元素next[t, c]与其前一个状态s的对于元素next[s, c]相同，那么可以直接从前一个状态中读取相应的值。该方法能够取得非常好的压缩效果，但是每次状态转换需要对时间进行更新，因此总的扫描时间是O(n*|Σ|)，这是非常费时的。
Smith在文献[10]中提出了XFA方法来解决正则表达式合并过程中出现的状态爆炸问题。该方法对有限自动机进行扩展，在每个自动机状态上附加计数标记来记录正则表达式中字符的重复次数。该方法能够比较好地解决DFA的状态爆炸问题，但是有如下2个缺陷：①对每个状态需要更新和检查相关的计数器，影响了匹配速度；②该方法只能对单个字符进行计数，在正则表达式中往往出现一个字符串的多次重复，如(abc){1, 4}，XFA无法解决这种计数问题。
陈曙晖等在文献[11]中提出了集合交割的预编码方法（SI-precode）来状态转移表的存储空间。该方法对于包含大量字符组的正则表达式压缩效果非常明显，但是无法解决一般正则表达式状态表的压缩问题。
张伟等在文献[12]中设计并实现了一种多正则表达式匹配的硬件架构MRM。该架构将正则表达式分解为普通字符串和限定重复的简单正则表达式，并针对NIDS系统的规则进行了优化，获得了2.8Gbit/s的扫描速度。但是该方案也只能支持一类特殊的正则表达式规则（分解为普通字符串和限定重复的简单正则表达式），因而限制了其应用范围。
从上面的工作可以看出，现有的正则表达式匹配方法具有如下不足之处：①在已有的对空间进行压缩的方法中，往往只关注压缩比，对匹配性能的分析都是理论层面上的，实际运行效果不佳；②现有的优化方法都是针对一类特殊的正则表达式进行的，无法解决一般正则表达式的匹配问题，其原因在于没有更好地挖掘多正则表达式之间由于正则语义带来的冗余关系和分布特征。因此需要对多正则表达式做进一步的研究。
3 簇分割压缩算法
本节首先引入簇的定义，然后介绍DFA的一个重要特征及压缩思想，接着详细描述整个算法，最后分析算法的状态转移时间复杂度及存储空间复杂度。整个过程以表达式.*A.{2}CD为例，其对应的DFA和存储矩阵如图1所示。
3.1簇的定义
在trie结构中，一个状态的后继状态集合称为一个簇。初始状态是单独的一个簇。簇在本质上就是对trie结构的一个划分，因此trie结构中的每个
