张巍等

摘 要： 网络数据包内容检测技术已在网络安全、网络监视、HTTP负载均衡等方面得到广泛的应用，因此，对快速数据包内容的检测就变得异常重要。在数据包内容检测过程中，数据包的净载数据要通过一系列已经定义好的正则表达式模式进行数据匹配。在此，阐述目前数据包检测存在的问题，如传统数据包检测应用程序要求很大的内存空间去存储相应的正则表达式模式，提出一种大大降低对内存空间使用的改进算法。通过将该改进算法应用到以DFA为基础的包检测应用程序中，说明经过真实网络数据来检测算法的改进成果。结果表明了改进算法的有效性。

关键词： 正则表达式； 深度包检测； DFA 模式； 内存使用

中图分类号： TN915.08?34； TP3 文献标识码： A 文章编号： 1004?373X（2015）05?0087?06

Improvement of regular expression matching algorithm for deep packet inspection

ZHANG Wei1， CHEN Jiao2， ZHAO Mei?kai2

（1. China Southern Power Grid Science Academy， Guangzhou 510080， China； 2. Space Star Technology Co.， Ltd.， Beijing 100086， China）

Abstract： Content inspection technology for network data packet has been widely used in network security， network monitoring， HTTP load balancing， etc. In content scanning of data packet， the payload data of the packet needs to be matched by a set of the specified regular expressions. The problem existing in the current data packet inspection is elaborated in this paper. That is， the traditional application program of data packet inspection needs a large memory space to store the corresponding regular expression pattern. A improved algorithm that effectively reduces memory space usage is proposed. The application of the improved algorithm in DFA?based packet inspection program indicates the improvement achievements， which were obtained by detection of the true network data.

Keywords： regular expression； deep packet inspection； DFA pattern； memory usage

0 引 言

网络数据包的内容检测对于网络安全和网络监视软件来说是一个至关重要的技术。在这些软件中，它们已经定义好了一系列的关于应用程序分级、病毒、网络协议等的模式集合，用来检测匹配网络的实时数据。

就目前来说，正则表达式[1]模式已经渐渐成为数据包检测程序的首选，正在慢慢替代明确的字符串匹配[2]模式。正则表达式模式具备了对相应模式超强的表达力和描述的灵活性。例如，L7?filter[3]（在Linux中对数据流进行分类的应用程序），使用模式匹配算法把进入设备的数据包应用层内容与事先定义好的协议规则进行比对，如果匹配成功就说明这个数据包属于某种协议。Snort[4]入侵检测系统也已经从以前不使用正则表达式规则集到现在大量使用正则表达式规则集了，还有一些其他的入侵检测系统，如Bro[5]，同样也使用正则表达式作为它的模式描述语言。

随着正则表达式在数据包内容检测方面得到广泛的采用，它的匹配数据包净载数据的速度应该与包头处理的线性速度保持一致，显得非常重要。但目前现存的大多数相应软件的净载数据检测速度都不能满足线性要求。例如，当L7?filter的70个协议过滤器同时生效时，系统的吞吐量小于10 Mb/s，仅仅相当于局域网的传输速度。并且，需耗用超过90%的CPU使用时间去匹配正则表达式，只留给程序执行入侵检测和监视很少的使用时间。另一方面，最近一些快速匹配字符串的算法有了一定发展，但它们只是关注明确的字符串匹配，这些算法并不能简单地扩展到正则表达式中。

在网络数据包检测过程中，正则表达式模式匹配效率很低的原因如下：

（1） 在许多指定的匹配网络数据的模式中使用了很多不同的通配符（例如，“.” ，“*”）。由于大量使用通配符，导致当正则表达式被转化成模式匹配状态机时，其产生的Deterministic Finite Automaton（DFA）[6]的复杂度呈几何倍数增长。

（2） 大多数通配符的使用都有不同长度的限制，导致更多资源被使用。

（3） 不同的字符组被公共的使用，如有字符集包涵所有可打印的字符和空格符，影响了字符集或通配符的使用，这种相互影响将导致高复杂度状态机的产生。

本文将着重分析如何避免正则表达式模式匹配在数据包内容检测上的问题，并优化其算法。此外还提出一个基于DFA的优化内存使用的高速匹配解决方案。基于以上的分析，提出针对某些特定正则表达式的两条重写规则。最后实验证明，通过重写的正则表达式所构建的DFA将大大提高数据包内容检测软件的匹配速度[7]。

1 问题阐述

1.1 正则表达式

正则表达式是指一个用来描述或者匹配一系列符合某个句法规则的字符串的单个字符串。表1列出了在数据包内容检测中所用的正则表达式元字符的特殊含义。

将两个匹配条件进行逻辑“或”（Or）运算＼&例如正则表达式（him|her） 匹配"it belongs to him"和"it belongs to her"，但是不能匹配"it belongs to them."。＼&.＼&匹配任何单个字符＼&正则表达式r.t匹配这些字符串：rat、rut、r t，但是不匹配root。＼&？＼&匹配0或1个正好在它之前的那个字符＼&＼&*＼&匹配0或多个正好在它之前的那个字符。＼&正则表达式.*意味着能够匹配任意数量的任何字符。＼&{}＼&匹配指定数目的字符，这些字符是在它之前的表达式定义的。＼&正则表达式A[0?9]{3} 能够匹配字符"A"后面跟着正好3个数字字符的串，＼&[]＼&匹配括号中的

任何一个字符。＼&正则表达式r[aou]t匹配rat、rot和

rut，但是不匹配ret。＼&[^]＼&匹配除了指定区间之外的字符＼&正则表达式[^269A?Z] 将匹配除了2、6、9和所有大写字母之外的任何字符。＼&]

1.2 正则表达式实现

有穷自动机是一种比较完美的实现正则表达式的形式。它分为两种：一种是确定的有穷自动机DFA（Deterministic Finite Automaton）；另一种是不确定的有穷自动机NFA（Nondeterministic Finite Automaton）。下面详细说明这两种自动机是如何实现正则表达式的：

一个DFA包括：一个有限的输入字符表，用Σ表示；一个有限的状态集合；一个转移函数[δ。]在网络应用程序中，[Σ]包括所有扩展ASCII码的28个字符表，在状态集中，有惟一的一个开始状态[q0]和一个接收状态集合。转移函数是使自动机从某一状态，因输入一个字符而返回另一状态。DFA的一个重要的特征是无论何时自动机只存在一个活动状态。另一个自动机NFA与DFA的执行机制很相似，其区别在于它的转移函数δ可以从一个状态和一个输入字符返回一个新的状态的集合，因此，NFA允许同时存在多个活动状态。

当一个长度为[n]正则表达式被转换成DFA时，最坏情况下，状态的复杂度[8]为[O（n），]另外，一个长度同样为[n]的正则表达式NFA转换成DFA时，它的状态复杂度为[O（Σn）。]并且对于DFA来说，每一个输入的字符执行的复杂度为[O（1），]但是对于NFA，当所有[n]个状态同时为活动状态时，每一个输入字符的执行复杂度为[O（n2）。]

2 解决问题

在本文中，将寻找一种快速的内存使用高效的数据包内容检测正则表达式匹配方案，下面给出此种方案适用问题的范围。

本文采用以DFA来实现正则表达式匹配的方案，因为NFA方案对于顺序化处理器或者有限的并行化处理器来说效率是非常低的。这里的目标是使每个输入自动机的字符都要以[O（1）]的代价来执行，但是就目前而言，由于DFA过大的内存占用导致不可能完成此目标。因此，本文将重点研究减小DFA的内存占用，以此来使每个输入的字符都已[O（1）]的代价来执行。

本文还将关注在通用的处理器架构下，限制正则表达式匹配速度的原因。并且还要关注在多核处理器上的移植性，因为多核并行处理已经成为处理器的发展趋势。

在DFA的内存资源占用方面有两个因素值得关注，它们是状态量和转移量。转移量是随状态量线性增加的，因为对于每一个状态这里都存在最多28个下一个转移到的状态。因此本文认为DFA的状态量是直接决定DFA内存使用量的主要因素。

3 单独模式匹配优化

3.1 提出概念

尽管正则表达式和自动机理论能够直接应用于数据包检测，但是应该注意到它们应用的不同之处。目前大多数的研究都主要关注在检测某个定长的字符串是否匹配已定义好的正则表达式。更明确地说，如果某个定长的字符串通过了正则表达式DFA的匹配过程，就认为它是符合该正则表达式语言的。但是相比之下，在数据包检测当中，一个正则表达式可以匹配整个输入的字符串，也可以匹配输入字符串的某个子串，则都符合DFA的匹配过程。这个字串没有已知的开始和结束的位置，因此DFA为了匹配所有可能的子串，将导致复杂度大幅度提高。

为了能更好地理解本文提出的优化方案，下面给出实现子串匹配的几个不同的的标准和DFA对于子串匹配的几种执行模式。

3.1.1 实现匹配的标准

已知一个正则表达式模式和一个输入字符串，一个完整的匹配结果应包括所有可能与正则表达式匹配的子串。例如，已知一个模式为ca*和一个输入为caaa，匹配结果应包括ca，caa，caaa。则称这种匹配标准为完全性匹配[9]，它的正式定义如下：

完全性匹配：已知一个处理函数[M，]以一个模式[P]和一个输入字符串[S]作为参数，生成了一个属于[S]的子串集，表示为{[M（P，S）={]S是[S]的子串|S能被[P]的DFA所接受}。

实际上，在大多数应用程序中并不要求包含所有的匹配结果，可能只需要一个这样的结果。因此本文给出了一个新的标准，即非重复性匹配，它将放宽完全式匹配的要求。

非重复性匹配：已知一个处理函数[M，]以一个模式[P]和一个输入字符串[S]作为参数，生成了任意一个属于[S]的子串，简单的说，[M（P，S）={S]的子串[Si|]任意[Si，][Sj]能被[P]的DFA所接受，[Si∩Sj=?}。]

如果一个模式出现在输入字符串的多个位置，这个匹配过程将给出所有非重复性的匹配子串。例如，已知一个模式ca*和一个输入caaa，三个匹配都有一个重复的前缀ca，因此，非重复匹配将得到三个匹配中的一个。

对于大多数数据包检测程序而言，一个非重复性匹配已经足够，因为这些程序仅仅为了探测是否存在网络入侵袭击，或者是否在应用层出现某个匹配。事实上，比如说检测工具grep和flex，系统Snort和Bro都用的是非重复性匹配的特殊情况，如左最长匹配，或者左最短匹配。本文采取的是左最短匹配，非重复性匹配能很好地构建一个内存使用更高效的DFA。

3.1.2 DFA执行子串匹配的方式

下而将关描述的是一类不以“^”开头的模式。这类模式中，它并不知道要匹配的子串是否或者在输入字符串什么位置将出现，对于这类模式，DFA可以采取不同的两种方式去执行：

（1） 重复查找。一个DFA可以通过一个模式经过标准的构建技术所生成。为了去寻找应匹配的子串，DFA将反复查找整个的输入字符串：即从字符串的开始部分查找，直到遇到以下两种情况结束：它已经输出了所有可能的子串匹配（在完全式匹配情况下）或找到一个可能的匹配（在非重复性匹配）；它遇到输出的结尾。这种DFA重复扫描的方式通常在语言匹配[10]处理中使用。但是对于数据包内容检测来说效率是相当低的。

（2） 一次查找。在这种方式中，模式都是以“.*”开头的，这表示它可能在输出字符串的任何位置被匹配，DFA将被这种扩展的模式所创建，因为DFA只需要一遍对输入字符串的查找，他就能获得所有在不同位置匹配的子串。使用这种一次查找的方式，它能取得的每个字符的计算复杂度都为O（1），因此其非常适合网络应用程序。为了能成功获得对字符串的很高的检测率，本文就采取的是这种查找方式。

3.2 单独正则表达式生成DFA解析

下面重点研究一些数据包内容检测应用程序（比如：Linux L7?filter，Snort和Bro）的几种模式所生成DFA的复杂度。它们使用的匹配标准和匹配方式是完全性匹配和一次查找。表2为研究结果。

确定的字符串模式生成DFA的复杂度与该字符串的字符数呈线性关系。

如果一个匹配模式以“^”开头，那么它所构造DFA与两个因素有关：一个是模式的整体长度[k，]一个是通配符所限制的通配字符串个数[j。]本文通过对现有包检测程序的匹配规则的研究发现，通常模式长度[k]是有限的，但通配符匹配长度[j]通常可以达到几百个甚至上千个。因此，情况4导致DFA的复杂度为[j]的平方数量级。

如果模式是以“.*”开始的，所生成的DFA的复杂度与通配符匹配数量呈指数级增长。

下面将重点分析后两种情况状态数量的激增原因。

3.2.1 平方级状态数量的DFA结构

通常的观念认为如果匹配模式以“^”开头，那么它生成的DFA将是一个状态数量比较少的简单的DFA，从表2中可看出，第4种情况尽管是以“^”开头的模式，但它存在这一个可以循环多次任意匹配的字符前缀集，这仍然使它产生了一个复杂的DFA。下面考虑这样一个例子，模式^B+[^＼n]{3}D，其中[^＼n]是一个匹配除了（＼n）以外的任意字符。它所产生的相应的DFA有平方数量级个状态，图1描述了一个它的状态转化图。

产生平方级的复杂度是因为模式中字符B的可重复匹配与三次[^＼n]的匹配集相互重叠，因此产生了模式的内在的匹配模糊[11]。第二个B字符既可以认为是匹配B+的一部分，又可以是认为是匹配[^＼n]{3}的一部分。因此，如果一个输入字符串包括多个B字符，DFA需要去记住B字符的具体个数和准确的输入位置，这样才能准确的匹配接下来的输入字符。如果一个可重复匹配的字符集的匹配限制次数是j，那么DFA需要O（j2）数量级个状态去记住输入字符B的第一个和最后一个。

在实际应用程序模式集中的相似结构：

实际上在Snort中有大量的模式规则集属于这类情况。例如，匹配NNTP规则的正则表达式“^SEARCH＼s+[^＼n]{1 024}”，与图1所示的例子很相似，＼s+与[^＼n]处于重叠的状态。输入的空格符既可以匹配＼s+部分又可以匹配[^＼n]{1 024}部分，这导致了模糊的产生。简单地说，如果一个输入字符串在输入“SEARCH”后输入了1 024个空格符，又输入了1 024个字符A，那么将可能产生1 024个匹配的子串。如，一个空格符去匹配＼s+，剩下的空格符去匹配[^＼n]{1 024}部分，或者两个空格符去匹配＼s+，剩下的空格符去匹配[^＼n]{1 024}部分等。需要10242状态去记录所有可能空格符的序列，这样生成的DFA才能满足所有不同长度的字符匹配需求。注意所有子串都要以SEARCH开头，然后以不同长度重复匹配。

仅仅通过构建NFA是无法解决平方级个状态问题的，也就是说，相应的NFA需要1 042个状态，在这些状态当中，一部分去匹配SEARCH，一部分去匹配＼s+，还需要1 024个状态去记录[^＼n]{1 024}的匹配个数，但是一个黑客可以很容易地构建一个以“SEARCH”为开头，紧接着1 024个空格符的输入。这将导致＼s+状态和所有1 023个非接受状态（因为空格符在结束匹配之前可以重复1 023次）同时处于活动状态，在匹配接下来的一个字符时，NFA需要去相继检测这1 024个状态，然后计算新的活动状态组，这将导致很低的执行效率。这个问题也不能通过固定字符串预先匹配机制来解决（Snort使用这种机制）。这是因为预先过滤只能识别固定字符串“SEARCH”是否存在于输入字符串中。之后，DFA或者NFA匹配机制仍然需要指出输入是否匹配这个模式并且指出这个子串是什么。另外一个选择是在识别“SEARCH”前缀后，要记录随后要处理的字符。这个方法同样也不能解决问题，因为每个包含该前缀的数据包都要触发这个计数过程。另外，一些黑客能很容易地构建具有同样这种前缀数据包，去触发大量的这个处理过程，导致网络瘫痪。

3.2.2 指数级状态数量的DFA

许多数据包检测模式都包含一个匹配任意个字符的开端，图2显示了这样一个模式所构建的DFA的状态转移全过程，例子模式为“.*A.{2}CD”。

模式中的两个通配符一共需要（22+1）个状态来记录所有可能的匹配形式。因为在不断顺序读取输入的字符串时，必须考虑之前读取字符串的所有可能影响最终匹配结果的不同前置输入。如，一个前置输入AAB与一个ABA的前置输入是不同的，因为当随后输入的是字符串BCD时，它与前一个所构成的字符串（AABBCD）是一个合法的匹配结果，但与后一个前置串构成的字符串（ABABCD）就是一个非法的匹配结果。通常情况下，如果一个模式以“.*”开端，其中还包含可以匹配j个任意字符的通配符，那么它将需要O（2j）个状态去满足DFA的匹配要求。比如相似情况的模式还可能有“.*A[A-Z]{j}D”。

在实际应用程序模式集中的相似结构：

在入侵检测系统Snort中，有53.8%的匹配模式包含可重复匹配指定次数的字符集。其中80%是以“^”开头的模式，它们将不会导致指数级状态的增长，但需要注意的是，仍有20%的模式没有以“^”开端，它将导致状态激增的问题。如，用于检测TMAP协议数据包是否溢出的测试规则，它使用的正则表达式是“.*AUTH＼s[^＼n]{100}”。这个规则是用于探测任意一个包含AUTH，然后是一个空格符，最后是100个非换行符的字符串的输入。如果直接用它生成一个DFA，将需要超过10 000个状态去记录所有可能的匹配结果，它是匹配AUTH＼s的第一个AUTH＼s。因为可能出现这样的情况：第二个AUTH＼s即能匹配[^＼n]{100}，也可能作为一个新的正则表达式模式的开始。很显然，指数级状态的增长问题也不能通过构建NFA的方式所解决[12]。图3显示了“.*AUTH＼s[^＼n]{100}”以NFA构建的状态转移实例。

因为第一个状态可能伴随着输入产生无数个自循环，如“AUTH＼sAUTH＼sAUTH＼s…”将导致大量的状态同时处于活动状态，大大降低了系统的执行速度。与表2中的情况4相似，这个问题也不能通过固定字符串预先匹配机制来解决。

3.3 优化重写正则表达式

本文已经详细分析了传统的模式在数据包检测过程中所构建的DFA的规模很大的具体原因。在这一部分，将探究一种优化正则表达式模式的方案，从而大大降低DFA的规模。这个方案的关键就是将传统模式中的完全性匹配标准改用非重复性匹配来实现。尤其是将重点实现两类正则表达式模式的优化重写。一种是表2提到的情况4：平方级状态复杂度，另一种是表2提到的情况5：指数级状态复杂度。这两种情况可以进行优化重写的一个共同特点是，它们的后缀可以匹配一个字符集的指定次数，这与它们的前缀匹配相重叠。这样的情况广泛存在于现实的一些数据包检测程序中如Snort，Bro。对于这样的模式，3.2部分所提到的NFA和预先过滤方式都不能提高它们的匹配效率，下面所提出的优化重写规则能成功的将平方级和指数级复杂度降为线性复杂度。

3.3.1 优化规则一

本文在第3.2节所提到的匹配模式“^SEARCH ＼s+[^＼n]{1 024}”将产生一个与重复匹配次数（这里为1 024次）成平方级规模的DFA。

通常情况下，这类模式是用于检测数据包缓冲区是否溢出[13]，因此本文用非重复性匹配标准去检测是否溢出，是非常高效的而又不失准确性的一种替代方法。基于这个观点，可以等价地将“^SEARCH＼s+[^＼n]{1 024}”优化重写成“^SEARCH＼s[^＼n]{1 024}”。这个新的模式表明，在匹配完第一个空格符后，不管以后的输入字符串是什么，则开始匹配计数[^＼n]{1 024}。用以前的模式匹配，很容易就确定每一个可能匹配的子串s是很困难的一件事情，不过对于新模式所产生的匹配子串s′而言，不是与s保持一致，就是s的一个前缀。换句话说，新的模式是采用左最短非重复性匹配的标准执行的。这样，新模式所产生的状态数量与重复次数j成线性关系，因为已经消除了对＼s的匹配不确定性。最后，本文确定可以将诸如“^A+[A-Z]{j}” 形式的正则匹配模式优化改写为“^A[A-Z]{j}”形式。在实际程序Snort中，本文重新改写了17个相似的模式。

3.3.2 优化规则二

在3.2节中讨论了像“.*AUTH＼s[^＼n]{100}”这种模式产生指数级数量状态，是因为它必须记录从第一个AUTH＼s开始随后所有的AUTH＼s。如果同样使用非重复性匹配标准，在匹配完第一个AUTH＼s后不用去记录第二个AUTH＼s。首先，如果在接下来的100输入的字符中存在＼n，匹配结束，第二个AUTH＼s一定包含在这100字符当中。其次，如果在接下来的100个字符中不包括＼n，那么第一个AUTH＼s和接下来的字符可以完成一次匹配过程。因此可以将模式改写成只去获取一次前缀的匹配模式。这样改写可以消除大量的去处理记录随后AUTH＼s的状态，从而简化了DFA，如图4所示。

4 改进效果验证

首先从常用的网络数据检测程序中挑选3个有代表性的复杂的模式集。第1个是从Linux L?7filter中选取了用于检测不同网络协议的70个正则表达式模式。第2个是从Snort中挑选了1 555个用于入侵检测的正则表达式模式[14]，最后一个是Bro入侵检测系统的所有2 781个正则表达式模式。并且从实际网络中获取了数以百万级数据包进行测试。

从这三个模式集中发现一些可以用3.3节提到的优化重写规则进行改写的模式，在Snort中有71个规则需要被重写，在Bro中有49个模式需要被重写。这120模式中，其中有17个适用于优化规则一，它们将从平方级的状态数量下降为线性数量。另外103种适用于优化规则二，它们将大大降低DFA的内存使用，从而满足大部分的个人电脑系统。表3具体显示了优化效果。

5 结 语

本文以实际存在的包检测程序中的正则表达式模式为基础，通过优化重写规则的运用，大大提高了应用程序的执行效率。但是本文并没有证明优化规则适用于所有可能导致DFA规模激增的模式，优化规则可能还并不通用，但这些优化重写规则经过试验确实可以提高Snort和Bro的执行效率，如果要有新的模式导致DFA规模的激增，还要根据具体模式的结构加以分析，具体问题还需具体分析，从而进行改进。

参考文献

[1] FIREDL J E F.精通正则表达式[M].北京：电子工业出版社，2009.

[2] THOMAS H， CORMEN C E， LEISERSON R L， et al. Introduction to algorithms [M]. 2nd ed. Beijing： Machinery Industry Press， 2006： 557?568.

[3] LEVANDOSKI J， SOMMER E， STRAIT M. Application layer packet classifier for Linux [EB/OL]. [2014?10?14]. http：//l7?filter.sourceforge.net.

[4] Snort Team. Snort network intrusion detection system [EB/OL]. [2014?10?14]. http：//www.snort.org.

[5] The Bro Project. The bro network security monitor [EB/OL]. [2014?10?14]. https：//www.bro.org/documentation/index.html.

[6] ALFRED V， AHO M S， SETHI Lam Ravi， et al. Compilers： principles， techniques and tools [M]. 2nd ed. Beijing： Machi?nery Industry Press， 2009： 93?96.

[7] 刘更楼，丁常福，娄建国.基于状态检测的防火墙系统研究[J].航空计算技术，2009，43（1）：122?125.

[8] WU S， MANBER U. A fast algorithm for multi?pattern sear?ching， TR?94?17 [R]. Arizona： University of Arizona， 2005.

[9] ASOKAN N. Fairness in electronic commerce [D]. Waterloo： Waterloo University， 2006.

[10] LARSSON N J. Structures of string matching and data compression [EB/OL]. [2011?12?16]. http：// www.docin.com...926.html.

[11] BAKER Z K， PRASANNA V K. Automatic synthesis of efficient intrusion detection systems on FPGAs [C]// 14th International Conference on Field Prog Logic and Applications. [S.l.]： [s.n.]， 2004： 311?321.

[12] HOPCROFT J E， ULLMAN J D. Introduction automata theory， languages， and computation [M]. [S.l.]： Addison Wesley， 1984.

[13] 李文嘉，谢高岗，张大方.一种基于数据包分析的网络入侵检测探针[J].同济大学学报，2002，27（10）：185?191.

[14] 吴薄峰.Snort入侵检测实用解决方案[M].北京：机械工业出版社，2005.