论文部分内容阅读
正则表达式匹配(Regular expression matching)是很多网络应用(如入侵检测、内容过滤、协议分析等)的核心引擎技术,随着互联网及网络应用的高速发展,对高速可扩展(fast and scalable)的正则表达式匹配的需求越来越大,但多年来如何实现高速可扩展的正则表达式这一难题一直困扰着研究者们。正则表达式用等价的有限自动机表示,包括非确定性有限自动机(non-deterministic finite automaton, NFA)和确定性有限自动机(deterministic finite automaton, DFA)。NFA所需存储空间很小但是匹配速度很慢；DFA由于匹配速度很快使得DFA方法成为了实现正则表达式匹配的普遍选择,但DFA的高匹配速度是以可呈指数膨胀的状态空间为代价的。高速可扩展的正则表达式匹配的终极目标就是实现像DFA一样的高匹配速度,即每匹配一个输入字符只需一次存储访问,并且实现像NFA一样的低存储空间,即所需存储空间随正则表达式规则集呈线性增长。因为三态内容可寻址存储器(ternary content addressable memory, TCAM)具有独特的并行查找、三态存储与模糊匹配的能力,最近研究者们提出了基于TCAM的DFA实现技术。然而,这些方法所需的TCAM条目数仍然高于呈指数增长的DFA状态数,因此其所需的存储空间仍然过于庞大。本文提出一种基于TCAM的DFA压缩技术,该技术每处理一个输入字符仅需一次简单的TCAM查询,并且将所需的TCAM条目数降低到了DFA状态数以下。本文通过发现和利用NFA与DFA之间存在的结构联系,识别出源自相同NFA状态的DFA状态,这些DFA状态实际上是相同NFA状态在DFA中不同的副本结构。本文为DFA状态设计合适的TCAM编码和TCAM条目压缩算法,得以有效地将DFA中的这些相似的副本结构进行压缩。基于真实规则集的实验结果表明,本文方法所使用的TCAM条目数最多比DFA状态数小两个数量级。在DFA实现方法之外,本文又提出首个基于TCAM的NFA实现方法,通过合适的TCAM编码,本文的NFA实现方法和DFA实现方法一样,每处理一个字符只需一次TCAM查找。NFA运行时,并非所有的状态都会同时活跃,通过将同时活跃的NFA状态划分到不同分组中进行编码,使得可以用较少的比特数表示一个NFA活跃状态集合。基于NFA活跃状态集的编码和相应的TCAM条目压缩算法,本文的NFA实现方法既具备和DFA完全一样的运行速度,同时所需存储空间又接近与正则表达式规则集大小呈线性增长的NFA大小。基于真实规则集的实验结果表明,相比基于TCAM的DFA实现方法,本文的NFA实现方法能将存储空间和匹配速度均各自减少和提高一个数量级。此外,本文还设计出一种快速的DFA构造算法,以打破基于DFA的正则表达式匹配方法的一个瓶颈——DFA方法都需要预先从NFA构造一个与之等价的DFA。本文通过深入探索自动机内在运行特性——NFA状态间活跃关系和NFA中导致DFA空间膨胀的因素,设计了一种NFA状态子集的编码方法和查询方法,减少了DFA构造过程中状态子集的查询代价。实验结果表明,与传统的子集构造算法相比,本文的方法减少了88.33%～93.57%的DFA构造时间。