CN101360088B - 正则表达式编译、匹配系统及编译、匹配方法 - Google Patents

Abstract

本发明提供了一种正则表达式编译、匹配系统及编译、匹配方法。本发明的正则表达式编译系统包括词法分析模块和至少一编译模块，所述词法分析模块分析正则表达式的词法特点，根据预设词法规则将正则表达式送往不同的编译模块处理，所述编译模块接收正则表达式，将其编译成特定形式的数据结构。本发明有益的技术效果在于：在完全支持正则表达式语法的前提下，达到较高的处理速度；能够根据实时流量的特征调整引擎的处理行为，提高系统吞吐量。

Description

正则表达式编译、匹配系统及编译、匹配方法

技术领域

本发明属于通讯领域，也可应用于搜索引擎、数据库检索、自然语言理解、文档分类等可能使用正则表达式的领域，尤其涉及一种正则表达式编译、匹配系统及编译、匹配方法。

背景技术

随着全IP网络(ALL-IP)、固定移动融合(Fixed and Mobile Convergence，简称FMC)、多重播放(Triple-play)等概念的提出，传统的IP网络正在向融合数据、语音和视频于一体的多业务统一承载网转变。但是IP网络固有的数据传送方式和本质上开放的特征无法很好地满足电信级业务的需要，在网络安全性、可管理性和关键业务的QoS和QoE保证等方面都有待改进。为了对一些关键业务进行精确的业务识别和控制，除了按照传统的方法分析报文头中的五元组等字段外，还需要对报文的负荷部分进行检测，比如一些P2P流量使用非知名的端口，这样仅靠分析五元组就无法识别出此类流量。DPI(Deep PacketInspection，深度报文检测)技术作为一种灵活有效的业务识别技术应运而生，并广泛应用在防火墙、IDS/IPS、业务控制网关等设备上，实现比如应用层负载均衡、基于特征的安全过滤等业务。和传统的报文检测方式相比，DPI不仅对原来的TCP/IP4层(IP层)以下的协议进行分析，还增加了4层以上信息的检测，因而其提供的信息更丰富，但处理也更为复杂。

传统的DPI检测系统通过将报文负荷和预先设定的字符串集合进行比较来判断报文是否满足特定特征。近年来，越来越多的系统采用正则表达式取代字符串来描述报文特征。和字符串相比，正则表达式能够非常灵活、简单、有效 地描述各种特征，使得特征串具有动态特性，适合各种动态搜索，比如b，ab，aab，aaab，aaaab...这一系列的字符串特征可以简单地用一个正则表达式a*b来表示。不同的正则表达式语言规范的描述能力不同，一般目前业界比较流行的正则表达式规范有POSIX(Portable Operating System Interface，可移植的操作系统界面)和PCRE(Perl Compatible Regular Expression，Perl兼容的正则表达式)两种。PCRE中增加了一些POSIX不支持的扩展，具有更强大的表达能力。比如开源代码Snort就采用PCRE规范来描述其部分规则。目前大部份设备还是使用POSIX规范，有些设备号称能够支持PCRE规范，但是从其产品资料分析，其实仍然只是PCRE规范中兼容POSIX规范的一个子集，并没有真正支持复杂的PCRE语法。

判断报文内容中是否包含正则表达式表示的规则的操作称为正则表达式匹配，目前，业界比较流行的正则表达式匹配方法有：

一种方法是基于DFA确定性有限状态机方法，这类方法都是预先将正则表达式转换为某种形式描述的状态转换表，匹配过程中，将报文中的符号作为输入条件查询状态转换表确定下一个跳转状态来实现状态迁移。这种方法的优点是“查表-跳转”的操作模式比较简单，能够很方便用硬件实现，匹配速度很快。缺点是只支持较为简单的正则表达式规范，对PCRE中的很多扩展选项(比如条件表达式、^、$等和位置相关的符号、匹配选项)都无法很好地支持。此外，部分正则表达式(比如：.*AB.{j}CD)用DFA表示时，其状态数目随正则表达式的长度呈指数级增长关系，给存储带来很大的负担。

另一种方法是NFA非确定性有限状态机方法，其基本原理类似于DFA方法，所不同的是：NFA允许出现空符号(即不输入任何符号实现跳转)，且NFA输入一个符号可以对应多个下一个跳转状态。这种不确定性导致其用硬件实现非常困难，目前也有一些使用硬件实现NFA的方法，一般都是将NFA状态表直接用逻辑器件实现，这样如果更新正则表达式需要对逻辑器件更新逻辑更新，存在扩展性差的问题。

第三种方法是程序解析的方法。这类方法一般不显示生成状态转换表。以PCRE源码库为例，它将正则表达式分解为程序可以理解的最小片段。匹配过程中，程序将报文中的符号按照出现的位置落入不同的片段中，如果符号能够符合这个片段，则要么在这个片段中等待下一个符号，或者进入下一个片段。一些软件实现可能采用其他特定的处理方式，但都可以归类为程序解析。这种方法通常具有很良好的扩展性，能够支持较为复杂的正则表达式语法，但是和状态机的方式比，它的匹配速度比较慢，容易成为整个系统的瓶颈。

现有技术一给出一种分层的报文过滤架构，在每一层过滤器上可以定义不同的过滤标准。通过第一层过滤的报文送往第二层过滤器进行过滤，直到得出过滤结果。现有技术一适合于各层完成的过滤标准不相同的情况，而且通常由较先出现的层次完成一定的筛选，减少后面层次所需的数据处理量。因而各层次之间有严格的先后顺序，从提高整体效率的角度考虑，应该将处理越复杂的过滤器越往后放置。现有技术一主要有以下缺点：各层过滤器间有严格的顺序关系，不够灵活；会造成报文的处理延迟时间加长，比如一些报文根本不需要第一层过滤器进行处理，但是按照层次化过滤的架构，这些报文也需要经过第一层过滤器后再进入第二层过滤器进行匹配，一方面浪费了第一层过滤器的处理能力，另一方面也造成了整个报文匹配的时间增加。只是笼统地给出了过滤标准的定义，并没有给出针对正则表达式匹配的具体方案；

请参阅图1，为现有技术二利用TCAM存储DFA来实现正则表达式匹配系统的结构示意图。利用TCAM(Ternary Content Addressable Memory，三重内容可寻址存储器)存储DFA来实现正则表达式匹配的方法。其实现步骤可以描述为：

1.利用正则表达式中的元字符(如.^*)将一个正则表达式分为多个子表达式，使用TCAM存储正则表达式(实际存放的是DFA状态表)。利用TCAM可以一次比较多个字符的特性，可以以多步长方式实现状态机；

2.在RAM中存放报文处理动作；

3.预解析器从接受的原始网络报文中提取需要处理的字段放在消息缓存中；

4.消息缓存用来存放需要进行正则表达式匹配的报文消息；

5.译码电路对报文译码，执行和报文相关的指令；

6.在译码电路的控制下，移位器将报文中的不同部分取出，和Tag中存放的当前状态一起送到CAM中进行比较；

7.一旦TCAM检测出正则表达式，则RAM中对应的动作会被译码电路执行，译码电路产生信号给流量控制器。

现有技术二主要有以下缺点：实现和TCAM可以同时访问多位的特性密切相关，不具有通用性；TCAM价格昂贵、功耗较大也限制了其使用；方案中为了减少子表达式的数目以达到减少占用TCAM条目数的目的，需要将不同的DFA合成为一个DFA，如果对正则表达式进行更新，需要重新编译整个DFA；对于PCRE中的很多扩展选项都无法很好地支持。

现有技术三中在整个检测系统中使用专门的正则表达式检测模块，遇到需要检测正则表达式时将流量输入到该模块进行处理，该模块采用ASIC芯片实现DFA，目前只支持POSIX正则表达式，实现细节属于商业秘密无法获知。现有技术三的缺点：无法支持PCRE正则表达式；经分析得知，如果需要支持PCRE正则表达式，需要用户在ASIC芯片以外提供实现，且没有给出具体的实现方案。

发明内容

本发明的实施例的目的在于提供一种正则表达式编译、匹配系统及编译、匹配方法，该正则表达式编译系统及方法，旨在解决现有技术中的系统没有考虑到正则表达式本身的特点，仅采用DFA方法处理所有正则表达式，无法真正支持PCRE正则表达式的问题。

本发明的实施例是这样实现的，一种正则表达式编译系统，包括词法分析模块和至少一编译模块，所述词法分析模块分析正则表达式的词法特点，根据预设词法规则将正则表达式送往不同的编译模块处理，所述编译模块接收正则表达式，将其编译成特定形式的数据结构。

本发明的实施例所采取的另一技术方案包括一种正则表达式匹配系统，包括仲裁模块和至少一匹配模块，所述仲裁模块查找正则表达式相关的分类信息，确定由哪个匹配模块进行匹配处理，所述匹配模块对符合其词法特点的正则表达式规则进行匹配。

本发明的实施例所采取的又一技术方案包括一种上述正则表达式编译系统编译正则表达式的方法，包括：

词法分析模块接收用户输入的正则表达式规则，对正则表达式进行词法解析，

词法分析模块根据预设规则将正则表达式送往不同的编译模块处理，由所述编译模块接收正则表达式，将其编译成特定形式的数据结构。

本发明的实施例所采取的又一技术方案包括一种上述正则表达式匹配系统匹配正则表达式的方法，包括：

仲裁模块接收前端模块发送的需要进行匹配操作的数据报文；

所述仲裁模块查找正则表达式相关的分类信息，确定由哪个匹配模块进行匹配处理；

所述匹配模块对符合其词法特点的正则表达式规则进行匹配。

本发明的实施例的正则表达式匹配系统及匹配方法通过结合使用多种正则表达式匹配算法，既保证了正则表达式匹配引擎具有较高的处理速度，又保证了对正则表达式的各种扩展语法的兼容性；本发明的实施例的正则表达式编译系统及编译方法通过使用具有反馈机制的编译器，能够根据实时流量的特征调整引擎的处理行为，提高系统吞吐量。

本发明的特征及优点将通过实施例结合附图进行详细说明。

附图说明

图1是现有技术二利用TCAM存储DFA来实现正则表达式匹配系统的结构示意图；

图2是本发明实施例的正则表达式匹配引擎的结构示意图；

图3是本发明实施例的正则表达式匹配系统采用单通道链接方式的结构示意图；

图4是本发明实施例的正则表达式匹配系统采用并联链接方式的结构示意图；

图5是本发明实施例的正则表达式匹配系统采用串联链接方式的结构示意图。

具体实施方式

为了使本发明实施例的目的、技术方案及优点更加清楚明白，以下结合附图及实施例，对本发明实施例进行进一步详细说明。

请参阅图2，为本发明实施例的正则表达式匹配引擎的结构示意图。本发明实施例的正则表达式匹配引擎包括正则表达式编译系统和正则表达式匹配系统。正则表达式编译系统与系统接口相连，接收用户输入的需要匹配的正则表达式规则。正则表达式匹配系统与前端模块连接，接收需要进行匹配操作的数据报文，正则表达式匹配系统还可以接收正则表达式信息，用来指示需要匹配的正则表达式。

本发明实施例的正则表达式编译系统包括词法分析模块、分类信息库、DFA编译模块、DFA状态转换表、PCRE编译模块和PCRE片段。词法分析模块接收到用户输入的正则表达式规则，对正则表达式进行词法解析，根据预设规则和其词法特点确定该正则表达式是送到DFA编译模块，还是PCRE编译模块进行编译，同时，该决策信息被记录在分类信息库中。如果DFA编译模块接收到正则表达式，将正则表达式编译为DFA状态转换表，并存储，如果PCRE编译模块接收到正则表达式，将正则表达式编译为PCRE片段，并存储。

本发明实施例的正则表达式的编译方法包括：

用户通过系统接口(比如命令行或操作界面等)将需要匹配的正则表达式规则输入到引擎；

词法分析模块接收到用户输入的正则表达式规则，对正则表达式进行词法解析，根据预设规则和其词法特点确定该正则表达式是送到DFA编译模块，还是PCRE编译模块进行编译。同时，该决策信息被记录在分类信息库中；

如果DFA编译模块接收到正则表达式，将正则表达式编译为DFA状态转 换表，并存储，其中，状态转换表并不一定指原始的二维转换表或转换图等特定形式，出于其他因素如空间效率考虑，还可能对状态转换表进行压缩，对不同的DFA进行合并等操作，这时状态转换表的存储形式可能发生变化，不影响本发明的实质内容；

如果PCRE编译模块接收到正则表达式，将正则表达式编译为PCRE片段，并存储。在实际软件实现时PCRE片段的存储形式是和具体实现相关的，形式上的不同不影响本发明的实质内容；

本发明实施例的正则表达式匹配系统包括仲裁模块、DFA适配器、PCRE适配器和综合输出模块。前端模块发送需要进行匹配操作的数据报文和正则表达式(可选)信息给引擎，其中，数据报文可以是通常所说的IP报文，为方便起见，前端的某个模块可以将原始IP报文中的三层、四层协议头移除后交给正则表达式匹配引擎处理；为了跨报文检测某个正则表达式，前端的某个模块还可能将报文进行重组；对于需要综合输出模块进行排序、统计的情况，需要送入的数据报文中有用于标识报文的字段，比如原始报文中的顺序号或者由前端模块分配的某种标识，不同的报文格式不影响本发明实施例的实质内容。图中前端模块送给仲裁模块的正则表达式是编译模块为正则表达式设定的标识符，用来指明检测输入数据报文中含有哪个正则表达式。该标识符在编译阶段产生，由前端模块根据自己的处理结果和某种映射规则确定该标识符。这样做的好处是在不同的正则表达式用不同DFA表示时，可以缩小需要匹配的正则表达式范围；如果由DFA编译模块编译的所有正则表达式被编译进一个大DFA中，则在进行匹配操作时，前端模块不需要指定标识符；不同DFA实现方式下入口参数的变化应不影响本发明实施例的实质内容。仲裁模块查找正则表达式相关的分类信息，确定由哪个适配器进行匹配处理，在进行匹配操作时，仲裁模块可以确定数据报文的流向和顺序，可以只有一个匹配模块进行处理，也可以由多个匹配模块进行处理。

本发明实施例的正则表达式匹配方法包括：

前端模块发送需要进行匹配操作的数据报文和正则表达式(可选)信息给引擎；

仲裁模块查找正则表达式相关的分类信息，确定由哪个适配器进行匹配处理；

DFA适配器/PCRE适配器对数据报文进行适配，匹配结果统一送到综合输出模块，如果有多个DFA/PCRE适配器线程对不同的数据报文进行匹配处理，可能因为数据报文的长度不同、需要匹配的正则表达式的复杂程度不同等因素，造成先收到的报文比后收到的报文的处理时间长，这时如果直接输出匹配结果给后续业务模块，匹配结果可能是乱序的。如果这种顺序很重要，可以在综合输出模块中设置一个缓存来对报文匹配结果进行排序；排序的方法有多种，比如可以根据报文的序号来进行。可选的，该模块还可以对匹配结果进行数据统计，数据统计条件可以灵活设定，比如在最近30分钟内被DFA适配器处理的前10位的正则表达式；不同的统计条件不影响本发明的实质内容；

综合输出模块将匹配结果送给后续业务处理模块，作为业务处理模块执行动作的依据，可选的，综合输出模块可以将统计信息反馈给词法分析模块，作为其分发正则表达式的参考依据；比如当检测到某个正则表达式最近经常由DFA适配器处理，词法分析模块可以将此正则表达式再送到PCRE编译模块进行编译，当DFA适配器忙不过来时，仲裁模块可以协调该报文到PCRE适配器进行处理。

在进行匹配操作时，仲裁模块可以确定数据报文的流向和顺序，可以只有一个匹配模块进行处理，也可以由多个匹配模块进行处理；按照各匹配模块间的链接关系不同，可以分为单通道、并联和串联三种链接方式。

请参阅图3，单通道链接方式是仲裁模块将数据报文调度到DFA适配器或者是PCRE适配器进行处理，数据只流向唯一的适配器。为了简化起见，在以下的图中都省略了控制层面的模块(有些情况下还省略了综合输出模块)。如(a)所示，大部分情况下，一条用户规则中只包含某种特定的正则表达式，由仲裁 模块将报文送到DFA或PCRE适配器进行处理；另外一种实施方式如(b)所示，如果某个数据报文应该是由DFA适配器进行处理，但DFA适配器处理不过来，而这时PCRE适配器刚好空闲，可以由仲裁模块协调报文到PCRE适配器进行处理。这种情况下两个匹配模块可能是用不同的器件实现，比如DFA适配器用FPGA实现，PCRE适配器用多核实现。这样处理能很方便地实现负载均衡，提高整个引擎的吞吐量。

请参阅图4，并联链接方式和单通道方式的实施方式(b)的模块关系很类似，不同的是，数据报文会被分配到各个适配器进行处理。有一些用户规则中包含有多个正则表达式，部分正则表达式适合用DFA方式表示，另外一部分正则表达式只能用PCRE方式表示。当有数据报文需要匹配这样的规则时，两个适配器可以同时处理报文。这种方式的优点是缩短了整个正则表达式匹配引擎的处理时间。

请参阅图5，串联链接方式下仲裁模块可以单独存在，链接在DFA适配器前；也可以不需要实现仲裁模块，将数据报文和正则表达式缺省先送到DFA适配器，隐含地由DFA适配器兼任仲裁模块的角色。如(a)所示，先通过DFA适配器过滤掉不满足DFA方式表示的正则表达式的数据报文，可以避免后续不必要的PCRE匹配操作；或者如(b)所示，报文缺省被送到DFA适配器，如果DFA适配器能够处理，就执行DFA匹配操作，输出结果；否则将报文再送到PCRE适配器进行处理。这样做的优点是模块间结构较简单，不需要单独实现仲裁模块。

本发明实施例的正则表达式编译、匹配系统及编译、匹配方法以DFA和PCRE适配器作为实例进行说明，本发明的实施例也适合采用其他的匹配方法来处理正则表达式，比如采用DFA和NFA方法。本发明主要是保护一种结合使用多种匹配算法进行正则表达式匹配的系统和方法，对使用的算法并不做限制。本发明实施例的正则表达式编译、匹配系统及编译、匹配方法只采用了两种编译/匹配模块，但是可以很方便地扩展到更多种类的编译/匹配模块；模块的 数量不影响本发明的实质内容。

本发明实施例中，只列举了一个DFA适配器和一个PCRE适配器；在实际实现时，没有这个限制；事实上为了达到最大的处理性能，往往会同时使用多个DFA适配器和多个PCRE适配器，比如采用多个线程。此时，仲裁模块可以根据各线程的负荷情况对报文进行分流。这不影响本发明的实质内容。

本发明以PCRE规范的正则表达式为实例进行说明，但是方法对于其他可能的正则表达式规范也适用。采用不同的正则表达式规范不影响本发明的实质内容。

本发明实施例的正则表达式编译、匹配系统及编译、匹配方法是针对网络环境下对数据报文进行高速正则表达式匹配的情况，但对于搜索引擎、数据库检索、自然语言理解、文档分类等这些情况下可能使用其他的正则表达式规范，而且正则表达式匹配对象也不局限于报文，比如数据库检索时针对的是数据表中的数据条目，但本发明提供的方法和系统同样适用。

本发明实施例的匹配系统可以在不同的器件中实现，也可以在相同器件中实现；可以使用硬件的方式实现，也可以采用软件的方式实现，甚至可以作为同一个软件中不同的函数来实现。因此本发明具有实现方式灵活的特点，但实现方式不同不影响本发明的实质内容。

本发明实施例的正则表达式编译、匹配系统及编译、匹配方法考虑了正则表达式本身的特点，能真正支持PCRE正则表达式，可以有效减少设备的存储器件成本；在对正则表达式进行编译时，如果正则表达式集合不经常变化，可以选择将所有正则表达式编译到同一个DFA以节省存储空间；在正则表达式集合需要经常更新的情况下，将不同的正则表达式编译到不同DFA，可以在更新个别正则表达式时，不需要对整个DFA进行重新编译，节省编译时间；不管在以上哪种情况下，由于词法分析已经将状态数目较多的正则表达式区分出来，交由PCRE编译器处理，因此可以节省存储空间；本发明实施例的正则表达式编译、匹配系统及编译、匹配方法在保证网络设备报文高速处理的同时，提供 对类似于PCRE的正则表达式规范的全面支持。

以上所述仅为本发明的较佳实施例而已，并不用以限制本发明，凡在本发明的精神和原则之内所作的任何修改、等同替换和改进等，均应包含在本发明的保护范围之内。

Claims (18)

1.一种正则表达式编译系统，其特征在于：包括词法分析模块和至少一编译模块，所述词法分析模块分析正则表达式的词法特点，根据预设词法规则将正则表达式送往不同的编译模块处理，所述编译模块接收正则表达式，将其编译成特定形式的数据结构。

2.如权利要求1所述的正则表达式编译系统，其特征在于，还包括分类信息库，所述词法分析模块产生的决策信息记录在分类信息库中。

3.如权利要求2所述的正则表达式编译系统，其特征在于，所述编译模块包括DFA确定性有限状态机编译模块和PCRE Perl兼容的正则表达式编译模块，所述DFA确定性有限状态机编译模块收到正则表达式，将正则表达式编译为DFA状态转换表并存储，所述PCRE Perl兼容的正则表达式编译模块接收到正则表达式，将正则表达式编译为PCRE片段，并存储。

4.如权利要求2所述的正则表达式编译系统，其特征在于，所述编译模块包括DFA确定性有限状态机编译模块和NFA非确定性状态机编译模块，所述DFA确定性有限状态机编译模块收到正则表达式，将正则表达式编译为DFA状态转换表并存储，所述NFA非确定性状态机编译模块接收到正则表达式，将正则表达式编译为NFA状态转换表并存储。

5.一种正则表达式匹配系统，其特征在于：包括仲裁模块和至少一匹配模块，所述仲裁模块查找正则表达式相关的分类信息，确定由哪个匹配模块进行匹配处理，所述匹配模块对符合其词法特点的正则表达式规则进行匹配。

6.如权利要求5所述的正则表达式匹配系统，其特征在于，所述仲裁模块还根据预设规则确定数据报文在各匹配模块间的处理顺序，所述匹配模块间的处理方式包括单通道链接方式、并联链接方式和串联链接方式。

7.如权利要求5或6所述的正则表达式匹配系统，其特征在于，还包括综合输出模块，所述综合输出模块与匹配模块相连接，接收匹配模块输出的匹配结果。

8.如权利要求7所述的正则表达式匹配系统，其特征在于，所述综合输出模块中设置有缓存来对报文匹配结果进行排序。

9.如权利要求7所述的正则表达式匹配系统，其特征在于，所述综合输出模块对匹配结果进行数据统计。

10.如权利要求9所述的正则表达式匹配系统，其特征在于，所述综合输出模块将统计信息反馈给词法分析模块，由词法分析模块根据这些数据更新预设词法规则，并发起二次编译。

11.一种权利要求1所述的正则表达式编译系统编译正则表达式的方法，包括：

词法分析模块接收用户输入的正则表达式规则，对正则表达式进行词法解析，

词法分析模块根据预设规则将正则表达式送往不同的编译模块处理，由所述编译模块接收正则表达式，将其编译成特定形式的数据结构。

12.如权利要求11所述的正则表达式编译方法，其特征在于，所述编译正则表达式成特定形式的数据结构包括：

DFA确定性有限状态机编译模块收到正则表达式，将正则表达式编译为DFA状态转换表并存储；

PCRE Perl兼容的正则表达式编译模块接收到正则表达式，将正则表达式编译为PCRE片段并存储。

13.一种权利要求5所述的正则表达式匹配系统匹配正则表达式的方法，包括：

仲裁模块接收前端模块发送的需要进行匹配操作的数据报文；

所述仲裁模块查找正则表达式相关的分类信息，确定由哪个匹配模块进行匹配处理；

所述匹配模块对符合其词法特点的正则表达式规则进行匹配。

14.如权利要求13所述的正则表达式匹配方法，其特征在于，所述方法还包括：根据预设规则确定数据报文在各匹配模块间的处理顺序，所述匹配模块间的处理方式包括单通道链接方式、并联链接方式和串联链接方式。

15.如权利要求14所述的正则表达式匹配方法，其特征在于，所述匹配模块将匹配结果统一送到综合输出模块。

16.如权利要求15所述的正则表达式匹配方法，其特征在于，所述综合输出模块中设置有缓存来对报文匹配结果进行排序。

17.如权利要求15所述的正则表达式匹配方法，其特征在于，所述综合输出模块对匹配结果进行数据统计。

18.如权利要求17所述的正则表达式匹配方法，其特征在于，所述综合输出模块将统计信息反馈给词法分析模块，由词法分析模块模块根据这些数据更新预设词法规则，并发起二次编译。

Images