HK1212119B - 用於处理有限自动机的方法和装置 - Google Patents

Description

用于处理有限自动机的方法和装置

技术领域

本发明的各实施例涉及用于处理有限自动机的方法和装置。

背景技术

开放系统互连(OSI)参考模型定义了用于通过传输介质进行通信的7个网络协议层(L1-L7)。上层(L4-L7)表示端到端通信并且下层(L1-L3)表示本地通信。

联网应用感知系统需要处理、过滤和切换L3到L7网络协议层的范围，例如，L7网络协议层诸如超文本传输协议(HTTP)和简单邮件传输协议(SMTP)，以及L4网络协议层诸如传输控制协议(TCP)。除了处理网络协议层以外，联网应用感知系统需要以线速(即，在其上传输和接收数据的网络的物理介质上的数据传输速率)通过L4-L7网络协议层来同时通过基于访问和内容的安全性来保护这些协议，这些协议层包括防火墙、虚拟专用网(VPN)、安全套接字层(SSL)、入侵检测系统(IDS)、互联网协议安全(IPSec)、防病毒(AV)和防垃圾邮件功能。

网络处理器可用于高吞吐量L2和L3网络协议处理，即，执行数据包处理从而以线速转发数据包。通常，通用处理器用于处理需要更多智能处理的L4-L7网络协议。虽然通用处理器可以执行此类计算密集型任务，但是没有足够用于处理数据使得其能够被以线速转发的性能。

入侵检测系统(IDS)应用可以检查流过网络的各个数据包的内容，并且可以标识可能指示试图侵入或损害系统的可疑图样。可疑图样的一个示例可以是数据包中的特定文本串，该特定文本串在100个字符以后跟随另一特定文本串。此类内容感知联网可能要求以线速检查数据包的内容。可以对内容进行分析，以确定是否存在安全漏洞或入侵。

可以应用大量的处于正则表达式形式的图样和规则(本文中也称为正则表达式图样)以确保检测到所有的安全漏洞或入侵。正则表达式是用于描述字符串中的图样的一种紧凑的方法。通过正则表达式匹配的最简单的图样是单个字符或字符串，例如/c/或/cat/。正则表达式还可以包括具有特殊含义的运算符和元字符。通过使用元字符，正则表达式可以用于更复杂的搜索，如“abc.*xyz.”。即，在“abc”和“xyz”之间的无限量字符的情况下，找到字符串“abc”，之后是字符串“xyz”。另一示例是正则表达式“abc..abc.*xyz；”，即，找到字符串“abc”，后面两个字符，然后是字符串“abc”并且在无限量字符后由字符串“xyz”跟随。通常使用搜索算法(如用于处理正则表达式的确定有限自动机 (DFA)或非确定有限自动机(NFA))执行内容搜索。

发明内容

本发明的实施例提供了一种可以使用至少一个有限自动机对输入流搜索至少一个正则表达式图样的方法、装置、计算机程序产品、和相应的系统。

根据一个实施例，一种方法可以在至少一个存储器中存储包括从至少一个正则表达式图样生成的多个节点的至少一个有限自动机。该方法包括将该至少一个存储器操作地耦合到至少一个处理器。该至少一个处理器可以被配置成用于以经由操作地耦合到网络的一个硬件网络接口接收的一个输入流的多个区段来行走该至少一个有限自动机，以对该输入流中的该至少一个正则表达式图样进行匹配。该行走可以包括在该输入流中的一个数据包的一个有效载荷之内的一个给定偏移下用一个区段并行地行走该至少一个有限自动机中的一个给定有限自动机的至少两个节点。该行走可以包括在该至少两个节点中的每一个节点处在该有效载荷之内的该给定偏移下确定对于该区段的一个匹配结果。该行走可以进一步包括基于所确定的每个匹配结果的集合来确定用于行走该给定有限自动机的至少一个后续行动。

该区段在此还可以被称为有效载荷区段或该有效载荷的一个区段。该区段可以是该有效载荷的一个正在被检查的部分，以确定该区段与正在用该区段遍历(即，行走)的该至少一个有限自动机的一个节点所指示的元素的匹配。该区段可以是值、字符、字母、字节或其他适合的类型的数据。该区段可以具有任何合适的粒度(如，长度或大小)。例如，该区段的粒度可以是一个字节、多个字节、小于一个字节、任何数量的位、或任何其他适合的粒度。该元素的类型可以是字符、字符串、字符类、或任何其他适合的元素类型。

该至少一个有限自动机可以包括一个确定型有限自动机 (DFA)和至少一个非确定型有限自动机(NFA)。至少一个有限自动机中的该给定的有限自动机可以是该至少一个NFA中的一个给定的 NFA。

在该至少两个节点中的每个节点处的该确定可以是在该至少一个处理器的同一个处理周期之内。

该至少两个节点可以包括一个元素节点和一个并行节点，该元素节点可以被配置成用于匹配在该有效载荷中的一个第一元素的单个实例。该第一元素可以是一个第一字符或第一字符类。该并行节点可以是如下各项之一：(i)被配置成用于匹配在该有效载荷中的一个第二元素的可变数目的连续实例的一个可变计数节点，或者(ii)一个投机节点。该投机节点可以被配置成用于基于从一个分离节点或到改分离节点的转换弧线来匹配在该有效载荷中的一个第二元素的可变数目的连续实例。该第二元素可以是一个第二字符或第二字符类。

该可变计数节点可以是该分离节点和该投机节点的集合。该分离节点可以被配置成用于独立于该有效载荷并且不从该有效载荷进行消耗(即，处理)而将该行走经由ε转换弧线前进到该元素节点和该投机节点并且用在该给定偏移下的该区段并行地行走该元素和投机节点。该投机节点可以被配置成用于将该行走前进回到该分离节点，并且基于在该投机节点处与该第二元素的肯定匹配，通过更新该给定偏移来消耗该区段。

该给定的有限自动机可以是NFA图形，该NFA图形可以包括一个从该可变计数节点到该元素节点的转换弧线。在NFA图形中，该可变计数节点可以在该元素节点之前。

该可变计数节点可以是一个与或直接或间接地标识该元素节点的元数据相关联的懒惰型节点，以基于在该有效载荷中的该第二元素的该可变数目的连续实例中的单个匹配实例使该行走前进到该元素节点。

与该可变计数懒惰节点相关联的该元数据可以包括一个用于追踪在该有效载荷中匹配的该第二元素的连续实例总数的计数，以允许该总数与该可变数目的比较。

基于该并行节点为该投机节点，该给定的有限自动机可以包括该多个节点中的一个分离节点。该元素节点和该投机节点可以基于与该分离节点相关联的元数据来标识。该分离节点可以被配置成用于独立于该有效载荷并且不从该有效载荷进行消耗而将该行走经由ε转换弧线前进到该元素节点和该投机节点，并且基于包括在与该分离节点相关联的元数据中的一个投机处理指示符，用在该给定偏移下的该区段并行地行走该元素和投机节点。

该方法可以基于在与该分离节点相关联的该元数据中不包括该投机处理指示符而不并行地行走该元素和投机节点。

在该给定偏移下用该区段行走该投机节点可以是基于在该元素节点处在该给定偏移下对于该区段的一次。

在该给定偏移下用该区段行走该投机节点可以是进一步基于存储和取回未探索的上下文。该未探索的上下文可以或直接或间接地标识该投机节点和该给定偏移。

存储该未探索的上下文可以包括在一个堆栈条目中存储该未探索的上下文并且将该堆栈条目推送到一个堆栈上。取回该未探索的上下文可以包括从该堆栈弹出该堆栈条目。

该投机节点可以被配置成用于基于在该投机节点处与该第二元素的肯定匹配将该行走前进到该分离节点。

基于该集合包括在并行行走的该至少两个节点中的每个节点处的一个否定匹配结果，该至少一个后续行动可以包括在并行行走的该至少两个节点中的每个节点处不继续行走一个给定的路径。该给定的路径可以部分地匹配在该给定的有限自动机中的该至少一个正则表达式图样。该方法可以基于感测未探索的上下文用在该有效载荷内的一个下一给定偏移处的一个下一区段来行走该多个节点中的一个下一节点。该方法可以基于没有感测到该未探索的上下文而终止该行走。

该未探索的上下文可以或直接或间接地标识该下一节点和该下一给定偏移，以便用该下一区段在该下一节点处沿另一个路径前进该行走，该路径部分匹配该给定的有限自动机中的该至少一个正则表达式图样。

感测该未探索的上下文可以包括确定一个堆栈的非空状态并且从该堆栈弹出一个堆栈条目。该堆栈条目可以包括该未探索的上下文并可以是一个最近推送到该堆栈上的条目。

该至少两个节点可以包括一个元素节点和一个并行节点。基于该集合包括在该元素节点对于该区段的一个肯定匹配结果和在该并行节点对于该区段的该肯定匹配结果或一个否定匹配结果，该至少一个后续行动包括更新该给定偏移以产生一个下一偏移，基于与该元素节点相关联的元数据来标识该多个节点中的一个下一节点，在该有效载荷内的该下一偏移处用一个下一区段来行走所标识的该下一节点，确定在所标识的该下一节点处对于该下一区段的一个下一匹配结果，以及基于所确定的该下一匹配结果来确定用于行走该给定的有限自动机的至少一个下一后续行动。

基于在该并行节点处对于该区段的该肯定匹配结果，该至少一个后续行动可以进一步包括在一个堆栈条目中存储一个未探索的上下文并且将该堆栈条目推送到一个堆栈上，该未探索的上下文或直接或间接地标识该并行节点和该给定偏移。

基于该下一匹配结果为该否定匹配结果，该至少一个下一后续行动可以包括基于感测未探索的上下文用在该有效载荷内的该给定偏移处的该区段行走该并行节点，并且基于未感测该未探索的上下文来终止该行走。

感测该未探索的上下文可以包括确定一个堆栈的非空状态并且从该堆栈弹出一个堆栈条目。该堆栈条目可以包括该未探索的上下文并可以是一个最近推送到该堆栈上的条目。

更新该给定偏移以产生该下一偏移可以包括基于该行走的方向为一个正向方向而增大该给定偏移并且基于该行走的方向为一个反向方向而减小该给定偏移。

该至少两个被并行行走的节点可以包括一个元素节点和一个并行节点。基于该集合包括在该元素节点处对于该区段的一个否定匹配结果和在该并行节点处对于该区段的一个肯定匹配结果，该至少一个后续行动可以进一步包括更新该给定偏移以产生一个下一偏移并且用在该下一偏移处的一个下一区段并行地行走该元素节点和该并行节点。

更新该给定偏移以产生改下一偏移可以包括基于该行走的方向为一个正向方向而增大该给定偏移并且基于该行走的方向为一个反向方向而减小该给定偏移。

并行行走该至少两个节点可以优化该匹配的性能，这是通过免除存储和取回上下文(如果不并行行走该至少两个节点时则需要)，以便基于在该给定偏移处的该区段的一个否定匹配结果，用在该给定偏移处的该区段使该行走从该至少两个节点中的一个第一节点前进到该至少两个节点中的一个第二节点。

在此披露的另一个示例实施例包括一种对应于与在此披露的方法实施例相一致的操作的装置。

另外，再另一个示例实施例可以包括一种非瞬态计算机可读介质，其上存储有一个指令序列，该指令序列当被处理器加载并执行时致使处理器执行在此披露的方法。

附图说明

根据本发明的示例性实施例的以下更具体的说明，上述内容将是明显的，如在这些附图中展示的，其中贯穿这些不同的视图的相同的参照字符是指相同的部分。附图不一定按比例，而是着重于展示本发明的实施例。

图1是一个安全装置的实施例的框图，其中，可以实现在此披露的实施例。

图2A-G是示例NFA和DFA图形以及展示图爆(graph explosion)概念的一个表。

图3是一个安全装置的实施例的另一个框图，其中，可以实现在此披露的实施例。

图4是一个超非确定型自动机(HNA)协处理器的一个环境的示例实施例的框图。

图5A是一个非确定型有限自动机(NFA)图的示例实施例的框图，该框图可以由一个行走器(walker)使用以匹配在一个输入流中的正则表达式图样。

图5B是用于以一种非投机(lazy non-speculative)方式以一个有效载荷行走图5A的NFA图形的处理周期的示例实施例的一个表。

图5C是投机型处理规则的一个表的示例实施例的框图。

图5D是用于以一种投机方式以该有效载荷遍历图5A的NFA 图形的处理周期的示例实施例的一个表。

图6A是一个NFA图形的另一个示例实施例的框图，该框图可以由一个行走器使用以匹配在一个输入流中的正则表达式图样。

图6B是用于以一种非投机方式以该有效载荷遍历图6A的 NFA图形的处理周期的示例实施例的一个表。

图6C是用于以该有效载荷遍历图6A的NFA图形的处理周期的另一个示例实施例的一个表。

图6D是可以用图6A的NFA图形遍历的另一个有效载荷的框图。

图6E是用于以一种非投机方式以图6D的有效载荷遍历图6A 的NFA图形的处理周期的示例实施例的一个表。

图6F是用于以一种投机方式以图6D的有效载荷遍历图6A的 NFA图形的处理周期的另一个示例实施例的一个表。

图7是一种方法的示例实施例的一个流程图，该方法可以被实现在至少一个处理器中，该处理器与操作地耦合到网络的一个安全装置中的至少一个存储器操作地耦合。

图8是任选地在此处披露的实施例内的一台计算机的示例内部结构的一个框图。

具体实施方式

在详细描述本发明的示例实施例之前，直接在下面描述了一种示例安全应用以帮助读者理解在此披露的本发明的特征，这些实施例可以实现在该安全应用中并且典型的处理使用确定型有限自动机(DFA) 和非确定型有限自动机(NFA)。

图1是一个安全装置102的实施例的框图，其中，可以实现在此披露的实施例。安全装置102可以包括一个网络服务处理器100。安全装置102可以是一个单独的系统，该系统可以将在一个网络接口103a 接收的包切换到另一个网络接口103b并且可以在转发这些包之前在所接收的数据包上执行多个安全功能。例如，安全装置102可以用于对数据包101a执行安全处理，这些数据包可以是在一个广域网(WAN)105a 或者任何其他合适的网络上接收的，然后将这些处理过的数据包101b 转发到一个局域网(LAN)105b或者任何其他合适的网络。

网络服务处理器100可以被配置成用于处理封装在所接收的数据包中的开放系统互连(OSI)网络L2-L7层协议。如本领域技术人员公知的，OSI参考模型定义了七个网络协议层(L1-7)。物理层(L1) 表示将设备连接到传输媒介的实际接口，包括电气接口和物理接口。数据链路层(L2)执行数据组帧。网络层(L3)将数据格式化为数据包。传输层(L4)处理端到端的传输。会话层(L5)管理设备之间的通信，例如，无论通信是半双工的还是全双工的。表现层(L6)管理数据格式化及表现，例如，语法、控制代码、特殊图形及字符集。应用层(L7)允许多个用户之间的通信，例如，文件传送及电子邮件。

网络服务处理器100可以为高层网络协议(例如，L4-L7)调度和排列工作(例如，数据包处理操作)，并且允许在所接收到的待执行的数据包中进行高层网络协议的处理，以便以线速转发数据包。通过处理这些协议来以线速转发这些数据包，该网络服务处理器100不会降低网络数据传送速率。网络服务处理器100可以从网络接口103a或103b 接收数据包，这些接口可以是物理硬件接口并且可以对所接收的数据包执行L2-L7网络协议处理。网络服务处理器100可以后续地将处理过的数据包101b通过网络接口103a或103b转发到网络中的另一跳、最终目的地、或通过另一个总线(未展示)以便由一个主机处理器(未展示) 进行进一步处理。网络协议处理可以包括网络安全协议的处理，如防火墙、应用防火墙、虚拟专用网(VPN)包括IP层安全协议(IPSec)和/ 或安全套接层(SSL)、入侵检测系统(IDS)和防病毒(AV)。

网络服务处理器100可以使用多个处理器(即，内核)来提供高应用性能。每个内核(未展示)可以专用于执行数据面或控制面的操作。数据面操作可以包括用于转发数据包的数据包操作。控制面操作可以包括处理复杂的高层协议部分，如IP层安全协议(IPSec)、传输控制协议(TCP)和安全套接层(SSL)。数据面操作可以包括处理这些复杂的高层协议的其他部分。

网络服务处理器100还可以包括特定用途协处理器，该协处理器可以使内核分流，使得网络服务处理器100实现高吞吐量。例如，网络服务处理器100可以包括一个加速单元106，该加速单元可以包括一个超非确定型自动机(HNA)协处理器108用于硬件加速NFA处理、以及一个超级有限自动机(HFA)协处理器110用于硬件加速DFA处理。HNA 108和HFA 110协处理器可以被配置成用于使网络服务处理器100的通用内核(未展示)分流执行计算和内存密集型图样匹配法的沉重负担。

网络服务处理器100可以执行图样搜索、正则表达式处理、内容验证、变换、和安全性加速数据包处理。正则表达式处理和图样搜索可以用于对AV和IDS应用以及其他需要字符串匹配的应用执行字符串匹配。在网络服务处理器100中的存储器控制器(未展示)可以控制对存储器104的访问，该存储器操作地耦合到网络服务处理器100。该存储器可以是内部的(即，芯片上的)或外部的(即，芯片外的)或其组合，并且可以被配置成用于存储所接收的数据包，如用于由网络服务处理器100进行处理的数据包101a。该存储器可以被配置成用于存储用于在DFA和NFA图形表达式搜索中进行查询和图样匹配的编译规则数据。编译规则数据可以被存储为一个二进制图像112，该图像可以包括用于DFA和NFA两者的编译规则数据，或者将DFA编译规则数据与 NFA编译规则数据分开的多个二进制图像。

典型的内容感知应用处理可以使用或者DFA或者NFA来识别所接收的数据包的内容中的图样。DFA和NFA都是有限状态机，也就是，每个计算模型包括一组状态、一个启动状态、一个输入字母表(所有可能的符号的集合)以及一个转换函数。计算在启动状态中开始并且变化为取决于转换函数的新状态。

该图样通常是用正则表达式来表达的，该正则表达式包括基本元素，例如正常的文本字符如A-Z和0-9以及元字符如*、^和|。正则表达式的基本元素是有待匹配的符号(单个字符)。基本元素可以与允许连结(+)、交替(|)的元字符以及克莱尼星号(*)组合。用于连结的元字符可以用于从单个字符(或多个子字符串)创造多个字符匹配图样，而用于交替(|)的元字符可以用于创造可以匹配两个或多个子字符串中任一者的正则表达式。元字符克莱尼星号(*)允许一个图样匹配任意次，包括不出现前面的字符或字符串。

将不同运算符和多个单个字符相组合允许构造复杂的表达式子图样。例如，子图样如(th(is|at)*)可以匹配多个字符串，如：th、this、 that、thisis、thisat、thatis、或thatat。表达式的复杂子图样的另一个示例可以是结合了允许罗列一个要搜索的字符清单的一个字符类构造[...] 的子图样。例如，gr[ea]y查找grey和gray两者。其他的复杂子图样的示例是可以使用破折号来表示字符范围的那些，例如，[A-Z]或匹配任何一个字符的元字符“.”。图样的一个元素可以是一个基本元素或者一个或多个基本元元组合与一个或多个元字符的组合。

对DFA或NFA状态机的输入典型地是一个区段，如一个(8 位)字节的字符串，也就是，字母表可以是来自输入流(即，所接收的数据包)的单个字节(一个字符或符号)。输入流中的每个区段(例如，字节)可以造成从一个状态到另一个状态的转换。DFA或NFA状态机的这些状态和转换函数可以通过一个图形来表示。图形中的每个节点可以表示一个状态并且图中的弧线(在此也被称为转换弧线)可以代表状态转换。该状态机的当前状态可以通过一个节点标识符来代表，该标识符选择该图形中的一个特定的节点。

使用DFA来处理正则表达式并且在字符输入流中找到由正则表达式描述的一个或多个图样可以被表征为具有确定型运行时间性能。 DFA的下一状态可以从一个输入字符(或符号)以及该DFA的当前状态来确定，因为每个DFA状态仅有一次状态转换。于是，DFA的运行时间性能被称为是确定型的，并且其行为可以从该输入进行完全地预测。然而，确定论的折中是这样一个图形：其中节点的数目(或图形尺寸)可能随着图样的尺寸以指数增长。

相反，NFA图形的节点数目(或图形尺寸)可以被表征为随着图样的尺寸线性地增长。然而，使用NFA来处理正则表达式并且在字符输入流中找到由正则表达式描述的一个或多个图样可以被表征为具有非确定型运行时间性能。例如，给定一个输入字符(或符号)以及 NFA的一个当前状态，有可能存在该NFA转换到一个以上的下一状态。于是，NFA的下一状态不能从输入和NFA的当前状态唯一地确定。因此，NFA的运行时间性能被称为是非确定型的，因为其行为不能从该输入进行完全地预测。

图2A-G展示了DFA“图爆”概念。图2A、2B、和2C展示了分别用于图样“.*a[^\n]，”“.*a[^\n][^\n]，”“.*a[^\n][^\n][^\n]，”的NFA图形，而图2D、2E、和2F展示了分别用于相同图样的DFA图形。如在图2A-2F中所示并且由图2G的表总结的，NFA图形可以对于某些图样线性地增长而DFA图形对于相同的图样可能指数地增长，从而导致图爆。如所示的，对于一个或多个给定的图样，DFA状态的数目可以大于NFA状态的数目，典型地是在多数百个或多数千个状态的量级。这是“图爆”的一个示例，这是DFA的标志特征。

根据在此披露的实施例，内容搜索可以使用DFA、NFA或其组合来进行。根据一个实施例，一个运行时间处理器、协处理器、或其组合可以硬件实现并且可以被配置成实现一个编译器或行走器。

该编译器可以将一个图样或一个图样输入列表(也称为签名或规则)编译到DFA、NFA或其组合中。DFA和NFA可以是二进制数据结构，如DFA和NFA图形和表。

行走器可以执行运行时间处理，例如可以标识在输入流中的一个图样的存在或者将该图样与在输入流中的内容进行匹配的行动。内容可以是一个互联网协议(IP)数据报的一个有效载荷部分、或在输入流中的任何其他合适的有效载荷。DFA或NFA图形的运行时间处理在此可以被称为使用该有效载荷行走或遍历该DFA或NFA图形，以确定图样匹配。被配置成用于生成DFA、NFA或其组合的一个处理器在此可以被称为编译器。被配置成用于使用所生成的DFA、NFA或其组合来实现有效载荷的运行时间处理的一个处理器在此可以被称为行走器。根据在此披露的实施例，网络服务处理器100可以被配置成用于在安全装置102中实现一个编译器和一个行走器。

图3是图1的安全装置102的另一个实施例的框图，其中，可以实现在此披露的实施例。如参考图1描述的，安全装置102可以操作地耦合到一个或多个网络并且可以包括存储器104和网络服务处理器 100，该网络服务处理器可以包括加速单元106。参考图3，网络服务处理器100可以被配置成用于实现一个编译器306，该编译器生成二进制图像112和一个使用二进制图像112的行走器320。例如，编译器306 可以生成包括由行走器320使用的编译规则数据的二进制图像112以便在所接收的数据包101a(在图1中展示)上执行图样匹配方法。编译器 306可以基于确定有利地适合DFA和NFA的规则数据通过确定DFA、 NFA或其组合的编译规则数据来生成二进制图像112。

根据在此描述的实施例，编译器306可以通过处理一个规则集 310来生成二进制图像112，该规则集可以包括一组一个或多个正则表达式图样304和任选的限定符308。从规则集310中，编译器306可以使用选自该一个或多个正则表达式图样中所有图样的子图样生成一个统一的DFA 312以及用于在该组一个或多个正则表达式图样304中的至少一个图样的至少一个NFA 314，用于由行走器320在运行时间处理过程中使用，以及包括用于在统一的DFA 312的状态和该至少一个NFA 314的状态之间转换行走器320的映射信息的元数据(未展示)。根据在此披露的实施例，所生成的每个NFA可以用于该组中的一个特定的图样，而一个统一的DFA可以基于来自该组中所有图样的所有子图样来生成。

该统一的DFA 312和该至少一个NFA 314可以逐数据结构地作为图形或者以其他任何合适的形式来表示，并且在元数据中的映射可以逐数据结构地作为一个或多个表或者以其他任何合适的形式来表示。根据在此披露的实施例，如果选自一个给定图样的一个子图样是该整个给定图样，那么对于该给定图样不生成NFA。

行走器320可以被配置成用于基于消耗来自所接收的数据包 101a中的有效载荷的区段通过转换该统一的DFA 312和该至少一个 NFA的状态用该有效载荷来行走该统一的DFA 312和该至少一个NFA 314。消耗可以包括更新该有效载荷内从一个当前区段到另一个区段的一个当前偏移。更新该当前偏移可以是基于行走方向，例如，行走器320 可以在一个正向或逆向的方向中行走该统一的DFA 312或该至少一个 NFA 314，基于正向行走方向增大该当前偏移而基于反向行走方向减小该当前偏移。于是，行走器320使该有效载荷走过该统一的DFA 312 和该至少一个NFA 314。

规则集310可以包括一组一个或多个正则表达式图样304，并且可以处于Perl兼容的正则表达式(PCRE)脚本文件形式或者当前已知或今后将开发的任何其他合适的形式。PCRE已经成为在安全和联网应用中正则表达式句法的事实标准。由于更多的要求深度数据包检查的应用已经出现或者更多的威胁已经在互联网上变得流行，用于标识病毒 /攻击或应用的相应的签名/图样也已经变得更复杂。例如，签名数据库已经从具有简单的字符串图样演进到具有通配符、范围、字符类和高级 PCRE签名的正则表达式(regex)图样。

如在图3中所示，任选的限定符308可以各自与该组正则表达式图样304中的一个图样相关联。例如，任选的限定符322可以与图样 316相关联。任选的限定符308可以各自是指定所希望的定制、高级 PCRE签名选项、或其他对于处理与这些限定符相关的图样而言合适的选项的一个或多个限定符。编译器306可以使用选自该组一个或多个正则表达式图样304中的所有图样的子图样302来生成一个统一的DFA 312。编译器306可以从该组一个或多个正则表达式图样304中的每一个图样中选择子图样302。编译器306还可以生成用于该组中的至少一个图样316的至少一个NFA 314，该至少一个图样316的一部分(未展示)用于生成该至少一个NFA 314，并且用于运行时间处理(即，行走) 该至少一个NFA 314的至少一个行走方向可以是基于所选的子图样318 的长度是固定的还是可变的、以及所选的子图样318在该至少一个图样 316中的位置来确定。编译器306可以将该统一的DFA 312和该至少一个NFA 314存储在该至少一个存储器104中。

一个子图样是一组来自一个图样的一个或多个连续的元素，其中，来自该图样的每一个元素可以通过一个在DFA或NFA图形中的节点表示，这是为了匹配来自该有效载荷的区段的目的。如上所述，一个元素可以是由一个节点表示的单个文本字符，或由一个节点表示的一个字符类。基于一个子图样是否有可能导致过多的DFA图爆，如上面参考图2A-G描述的，编译器306可以确定该图样中的哪个子图样更好地适合NFA。例如，从一个包括连续文本字符的子图样生成DFA将不会导致DFA图爆，而如上所述的复杂的子图样可能包括运算符以及字符并因此可能导致DFA图爆。例如，包括重复多次的通配符或更大字符类的子图样(例如，[^\n]*或[^\n]{16})可能导致在DFA中过多的状态并因此可能更有利地适合于NFA。

确定整个图样的匹配可以通过采用来自该统一的DFA、该至少一个NFA或其组合的匹配结果来发现。根据在此披露的实施例，如果在所接收的数据包101中的一个有效载荷包括与来自图样316的一个所选子图样318匹配的内容，则该行走器可以转换到行走图样318的至少一个NFA。行走器320可以报告该所选子图样318的匹配以及一个偏移，该偏移将该匹配子图样的最后一个字符在所接收的数据包中的位置标识为在该有效载荷中该子图样的结束偏移。

子图样匹配可以是对该图样的部分匹配，如果该自图样是该图样的一个子集。于是，行走器320可以通过行走该图样的至少一个NFA 来在有效载荷中继续搜索该图样的剩余部分，以便确定该图样的最终匹配。应当理解的是，该图样可以遍历所接收的数据包101a中的一个或多个有效载荷。

图4是图1的HNA协处理器108的一个环境的示例实施例的框图450。根据在此披露的实施例，HFA 110可以被配置成用于实现行走器320相对于DFA处理的功能性，并且HNA108可以被配置成用于实现行走器320相对于NFA处理的功能性。

根据在此披露的实施例，HNA 108可以被配置成用于从一个指令队列454读取至少一个指令453。指令队列454可以被配置成用于存储该至少一个指令453，该指令可以是由一个主机(未展示)发送的以便由HNA 108进行处理。该至少一个指令453可以包括至少一个工作，如S1459a、S2459b、或S3459c。该至少一个工作各自可以基于由图1 的HFA协处理器110标识的对于图3的这些子图样302的一个给定子图样(在输入流中正在进行匹配)的部分匹配结果来确定。

该至少一个工作中的一个给定工作可以指示该至少一个NFA 314中的一个给定NFA、该给定NFA的至少一个给定节点、一个给定有效载荷中的至少一个给定偏移、以及至少一个行走方向，该至少一个行走方向各自对应于该至少一个给定节点中的一个节点。该至少一个工作各自可以包括由该HFA处理的结果，从而使得HNA能够在对于该至少一个图样304中的一个给定图样的给定NFA中将一个对应于给定子图样的匹配前进。于是，每个工作表示由HFA协处理器110确定的部分匹配结果，以便通过HNA协处理器108将该给定图样的匹配前进。

HNA 108可以通过读取存储在其中的至少一个指针(未展示) 或其他合适的指令信息来处理该至少一个指令453。该至少一个指针可以包括指向一个输入缓冲器458的一个输入缓冲器指针(未展示)。该至少一个指令453还可以包括指向一个有效载荷462的一个有效载荷指针(未展示)、指向一个匹配结果缓冲器466的一个结果缓冲器指针(未展示)、指向一个保存缓冲器464的一个保存缓冲器指针(未展示)和指向一个运行堆栈460的一个运行堆栈指针(未展示)。

输入缓冲器458、运行堆栈460、和保存缓冲器464在此可以分别被称为输入堆栈、运行堆栈和保存堆栈，虽然输入缓冲器458、运行堆栈460、和保存缓冲器464可以展现或不展现堆栈的后进先出 (LIFO)特性。输入缓冲器458、运行堆栈460、和保存缓冲器464可以位于相同的或不同的物理缓冲器之内。如果位于相同的物理缓冲器之内，输入缓冲器458、运行堆栈460、和保存缓冲器464的条目可以是基于这些条目的字段设定而有差别的或者是以任何其他合适的方式而有差别的。输入缓冲器458和运行堆栈460可以位于相同的物理缓冲器 (可以是芯片上的)中，而保持缓冲器464可以位于另一个物理缓冲器 (可以是芯片外的)中。

该至少一个指令453的该至少一个工作如S1459a、S2459b、或S3459c可以被存储在用于由HNA 108处理的输入堆栈458中。该至少一个指令的该至少一个工作可以各自属于一个相同的给定的有效载荷，如有效载荷462，该有效载荷由HFA 110处理。

HNA 108可以被配置成用于基于该输入缓冲器指针从该输入缓冲器458加载(即，提取或取回)至少一个工作，如工作S1459a、S2459b、或S3459c。HNA 108可以将该至少一个工作推送(即，存储) 至运行堆栈460。HNA 108可以从该运行堆栈弹出(即，读取、提取、加载等)一个给定的工作，如条目S1459a、S2459b、或S3459c，并且处理该给定的工作。该至少一个工作各自(例如，S1459a、S2459b、或S3459c)可以包括到该有效载荷462的一个区段(未展示)的一个有效载荷偏移(未展示)，以及指向一个图形457的指针，可以是至少一个有限自动机中的一个给定有限自动机，如图3的该至少一个NFA 314。

HNA 108可以从图形存储器456加载(即，提取)图形457，该图形可以被包括在图1和图3的二进制图像112中，并且开始使用对应于有效载荷462的对应有效载荷偏移的有效载荷区段来处理图形 457。HNA 108可以通过用有效载荷区段行走图形457的节点来处理图形457。图形457的部分匹配的路径可以包括图形457的至少两个节点，这些节点将该有效载荷的连续区段与一个所使用的给定图样相匹配以生成图形457。部分匹配的路径在此可以被称为线程或活动线程。

HNA 108可以使用来自有效载荷462的有效载荷区段处理图形 457，将条目推送到运行堆栈460/从该运行堆栈弹出，以保持并且恢复它在图形457中的位置。例如，如果一个行走过的节点呈现出对于下一要走的节点的多个选项，HNA 108可能需要保持其在图形中的位置。例如，HNA 108可以行走一个呈现多个处理路径选项的节点，如在该图形中表示的一个叉形。根据在此披露的实施例，DFA或NFA的节点与一个节点类型相关。与一个分离或可变计数节点类型相关联的节点可以呈现多个处理路径选项。分离和可变计数节点类型在下面参考图5A和图 6A进一步进行披露。

根据在此披露的实施例，HNA 108可以被配置成用于选择该多个处理路径中的一个给定的路径，并且将一个条目推送到运行堆栈460 中，该运行堆栈可以基于确定沿所选路径的行走过的节点处的不匹配 (即，否定)结果允许HNA 108返回并且沿该多个处理路径中的未选择的路径前进。于是，推送运行堆栈460上的条目可以在图形457中保存一个表示未探索的上下文的位置。未探索的上下文可以指示图形457 的一个给定节点和一个相应的有效载荷偏移以使HNA 108能够返回到该给定节点并且用该有效载荷462的给定区段来行走该给定节点，因为该给定区段可能位于有效载荷462中的相应的有效载荷偏移处。于是，运行堆栈460可以用于允许引擎462记住并在稍后行走图形457的一个未探索的路径。推送或存储一个指示给定节点和在给定有效载荷中的相应偏移的条目在此可以被称为存储未探索的上下文、线程或非活动线程。弹出、提取、或加载一个指示该给定节点和在该给定有效载荷中的相应的偏移的条目以便用在该给定有效载荷中的相应的偏移处定位的一个区段来行走该给定节点，在此可以被称为激活一个线程。丢弃一个指示该给定节点和在该给定有效载荷中的相应偏移的条目在此可以被称为清除一个条目或止用一个线程。

在用图形457行走该有效载荷462的区段时达到有效载荷462 的一端的事件中，运行堆栈460可以允许HNA 108保存其在图形457 中的位置。例如，HNA 108可以确定该有效载荷或有效载荷462的一部分部分地匹配一个给定图样，并且有效载荷462的一个当前有效载荷偏移是该有效载荷462的一个结束偏移。于是，HNA 108可以确定仅发现该给定图样的一个部分匹配并且该整个有效载荷462已消耗。于是， HNA 108可以将运行堆栈460的内容保存到保存缓冲器464以用对应于与已消耗的有效载荷462同一个流的下一有效载荷继续行走。保存缓冲器464可以被配置成用于在有效载荷462被消耗的事件中存储运行堆栈 460的至少一个运行堆栈条目，镜像运行堆栈460的一个运行状态。

基于找到该图样的一个最终(即，完全或完整)的匹配，HNA 可以弹出并丢弃在运行堆栈460中的与当前工作相关联的条目，例如从输入缓冲器加载的工作，如S1459a，并且将匹配结果(未展示)保存到匹配结果缓冲器466。替代性地，HNA 108可以继续处理运行堆栈460 的与当前工作相关的条目，因为所有有可能的匹配路径可能都是有意义的。

匹配结果可以包括与确定该图样的最终匹配之处的节点相关联的节点地址。确定该图样的最终匹配之处的节点在此可以被称为标记节点。节点地址、或在图形457中的一个最终匹配位置的其他标识符、匹配图样的标识符、匹配图样的长度、或任何其他合适的匹配结果、或其组合可以被包括在这些匹配结果中。

基于处理所有与当前工作相关联的运行堆栈条目，HNA 108可以从运行堆栈加载下一工作，该下一工作先前已经从输入缓冲器458加载(例如，S2459b)，因为HNA 108可以被配置成用于顺序地处理指令453的工作。于是，HNA 108可以从图形存储器456提取下一个图形 (未展示)、用来自有效载荷462的一个或多个有效载荷区段行走该下一个图形、并且继续处理另外的工作直到运行堆栈460为空。

基于在用有效载荷462行走图形457时找到有效载荷462的不匹配，HNA 108可以从运行堆栈460弹出一个与该当前工作(例如，S1 459a)相关联的条目并且基于所弹出的条目的内容用有效载荷462的下一区段来行走下一节点。如果运行堆栈460不包括一个与当前工作相关联的条目，则HNA 108可以结束当前工作并可以从运行堆栈460加载先前已经从输入缓冲器458加载的下一工作(例如，S2459c)。于是， HNA 108可以被配置成用于基于所加载的下一工作来行走下一个图形，并且继续处理另外的工作直到运行堆栈460为空。

根据在此披露的实施例，HNA 108的行走器320功能性可以包括通过以投机方式行走一个给定的NFA来优化至少一个正则表达式图样对一个输入流的匹配。该投机方式可以包括在该输入流中的一个数据包的一个有效载荷之内的一个给定偏移下用一个区段并行地行走该给定NFA的至少两个节点。该行走可以包括在该至少两个节点中的每一个节点处在该有效载荷之内的该给定偏移下确定对于该区段的一个匹配结果。该行走可以进一步包括基于所确定的每个匹配结果的集合来确定用于行走该给定有限自动机的至少一个下一后续行动。通过以投机方式行走该给定NFA进行的该至少一个正则表达式对该输入流的此类优化的匹配在下面进一步披露。

图5A是一个NFA图形504的示例实施例的框图500，该图形可以由一个行走器320使用以匹配在一个输入流(未展示)中的正则表达式图样502。如上所述，HNA 108可以被配置成用于实现行走器320 相对于NFA处理的功能性。

在该示例实施例中，输入流可以包括一个带有有效载荷542的数据包(未展示)。正则表达式图样502是一个图样“h[^\n]*ab”，该图样指定字符“h”之后是与换行字符不匹配的无限数目的连续字符(即， [^\n]*)。该无限数目可以是零或更多。图样502进一步包括连续跟随在与换行字符不匹配的无限数目的字符之后的字符“a”和“b”。在该示例实施例中，有效载荷542包括区段552a-d(即，h、x、a、和b)，在有效载荷542中分别具有偏移520a-d(即，0、1、2、和3)。

应当理解的是，正则表达式图样502、NFA图形504、有效载荷542、区段522a-d、以及偏移520a-d表示用于说明目的的示例，并且在此披露的系统、方法和相应的装置可以适用于任何合适的正则表达式图样、NFA图形、有效载荷、区段、和偏移。此外，应当理解的是，NFA图形504可以是一个更大的NFA图形(未展示)的一个子区域。另外，有效载荷542可以是一个更大的有效载荷(未展示)的一部分，并且该部分可以是在该更大的有效载荷的开始、结束、或任何位置处，从而导致与在该示例实施例中不同的偏移。

在该示例实施例中，NFA图形504被配置成用于将该正则表达式图样502与该输入流进行匹配。例如，NFA图形504可以是一个包括由编译器306生成的多个节点的图形，如节点N0506、N1508、N2510、 N3512、N4514、和N5515。节点N0506可以表示图样502的一个起始节点，而节点N5515可以表示图样502的一个标记节点。标记节点 N5515可以与一个指示符相关联，该指示符反映与该输入流匹配的图样 502的一个最终(即，完全或完整)的匹配。于是，行走器302可以基于遍历标记节点N5515确定图样502在输入流中是匹配的。

根据在此披露的实施例，行走器320可以一次行走一个区段地通过NFA图形504行走有效载荷542的区段522a-d，以将正则表达式 502与该输入流进行匹配。这些区段516中用于行走一个给定节点的一个给定区段可以基于在这种偏移518中其对应的偏移是有效载荷542之内的当前偏移而进行确定。根据在此披露的实施例，行走器320可以通过增大或减小当前偏移来更新该当前偏移。例如，行走器320可以在正向或逆向的方向中行走NFA图形504，并且因此可以通过分别增大或减小当前偏移，在一个正向543或逆向546方向中行走来自有效载荷542 的区段。

节点N0506、N2510、N3512、和N4514可以被配置成用于将一个对应的元素对有效载荷542的一个给定的区段进行匹配，而节点N1508和N5515可以是不指示匹配功能性并因此不会从有效载荷542 进行消耗的节点类型的节点。在该示例实施例中，节点N1508是对行走器320呈现多个转换路径选项的分离节点。例如，行走分离节点N1 508呈现ε路径530a和530b。根据在此披露的实施例，行走器320可以基于与行走器306互相一致的隐含设定来选择该多个路径530a和 530b中的一个给定路径。例如，编译器306可以基于行走器320遵循一条确定性路径的隐含理解来生成NFA图形504，例如隐含地理解行走器 320基于行走分离节点508来选择一条上方ε路径530a。根据在此披露的实施例，上方ε路径530a可以被选择为表示懒惰路径的上方ε路径 530a。懒惰路径可以是代表元素的最短可能匹配的路径。

根据在此披露的实施例，分离节点508可以是与分离节点元数据(未展示)相关联的，以呈现该多个路径选项。例如，在该示例实施例中，该分离节点元数据可以或直接或间接地指示多个下一节点，如节点N2510和N3512。如果该多个下一节点是直接指示的，那么该元数据可以包括指向这些下一节点N2510和N3512的绝对地址或指针。如果该多个下一节点是间接指示的，那么该元数据可以包括可用于解析这些下一节点N2510和N3512的绝对地址或指向这些下一节点的指针的索引或偏移。替代性地，也可以使用用于或直接或间接地指示该多个下一节点的其他合适的形式。

该隐含的理解可以包括配置行走器320以基于包括在该分离节点元数据之内的一个特定的条目位置中的节点元数据来选择多个下一节点中的一个给定的下一节点。编译器306可以被配置成用于生成该分离节点元数据，包括一个该给定的下一节点在所指定的条目位置的指示。于是，编译器306可以使用如下隐含的理解来生成NFA图形504：一个给定路径，如上方ε路径530a，在分离节点N1508处将被行走器 320选择。

图5B是用于以一种非投机方式以一个有效载荷542行走图5A 的NFA图形的处理周期的示例实施例的一个表538。应当理解的是，一个处理周期可以包括一个或多个时钟周期。

如在表538中所示的，处理周期540a-h可以包括在当前偏移 532用来自有效载荷542的一个区段行走一个当前节点530以确定一个匹配结果534并基于匹配结果534确定行走行动536。在该示例实施例中，节点N0506可以具有字符节点类型。例如，节点N0506可以是一个字符节点，该字符节点被配置成用于匹配在输入流中的字符“h”。在该示例实施例中，行走器320可以在处理周期540a中在当前偏移520a 处用区段522a(即，“h”)行走起始节点N0506。

当区段522a匹配在节点N0506处的字符“h”时，行走器320 可以确定匹配结果534是肯定匹配结果。如经由与起始节点N0506相关联的元数据(未展示)通过编译器306指定的，行走器320可以在正向方向上行走并提取由与节点N0506相关联的元数据指示的下一节点并且可以将当前偏移从520a(即，“0”)增大到520b(即，“1”)。通过节点N0506指示的下一节点在该示例实施例中是分离节点N1 508。于是，行走器320采取处理周期540a的行动536，该行动包括将有效载荷542中的当前偏移更新到“1”并且转换到分离节点N1508。转换可以包括提取(在此也被称为加载)分离节点N1508。

由于分离节点N1508呈现多个转换路径选项，如ε路径530a 和530b，处理周期540b的行动536可以包括选择上方ε路径530a并提取与有效载荷542无关的节点N2510而不从有效载荷542进行消耗。因为没有通过分离节点N1508执行匹配功能，所以当前偏移/区段532没有变化，并且由此对于处理周期540b而言有效载荷没有被消耗。

因为分离节点N1508呈现多个路径选项，行动536可以包括存储未探索的上下文，如通过存储节点N3512和当前偏移520b(即，“1”)的一个间接或直接的标识符。所选的转换路径在此可以被称为当前的或活动的线程，并且所存储的每个未遍历的转换路径在此可以被称为存储线程。每个线程可以通过一个相应的节点标识符和在有效载荷中的偏移来标识。于是，未探索的上下文可以标识一个未探索的线程 (即，路径)。

存储该未探索的上下文可以使得行走器320能够记得返回到节点N3512以便在沿所选的部分匹配路径发生否定匹配结果的事件中在有效载荷542中的偏移520b处用区段“1”行走节点N3512，例如，如果该否定匹配结果是在节点N2510处或沿从节点N2510延伸的路径上的节点处确定的。根据在此披露的实施例，未探索的上下文可以用一个丢弃未探索的处理(DUP)指示符来标记，该指示符指示在沿所选的转换路径标识一个用于图样502的最终匹配的事件中行走器320是丢弃还是处理该未探索的上下文。

例如，基于到达指示在输入流中对于图样502的最终(即，完整或完全)的匹配的标记节点N5515，行走器320可以采用该DUP指示符来确定是否通过在偏移520b处以区段“x”行走节点N3512来处理该未探索的上下文，以努力确定NFA图形504的匹配图样502的另一个路径，或者是否丢弃该未探索的上下文。用DUP指示符标记该未探索的上下文可以包括以任何合适的方式标记该未探索的上下文，如通过将与该未探索的上下文相关的一个位或字段设定为真，以表示堆栈条目的所希望的处理，或者设定为假，以表示堆栈条目的所希望的丢弃。

一个存储线程是否被遍历可以通过编译器306来确定。例如，编译器306可以控制是否对应于每个节点的元数据来配置一种设定从而设定该DUP指示符。替代性地，编译器306可以配置一个包括在与该有限自动机相关联的全局元数据中的全局设定，指定所有存储线程都需要被遍历，从而使得所有可能的匹配能够得到标识。

在该示例实施例中，ε转换路径530a的选择可能造成检测到在节点N2510或在当前线程的一个后续节点如N4514处的匹配失败。于是，如果检测到匹配失败，则用于ε转换路径530b的存储线程可以被遍历。替代性地，如果由编译器306指定，ε转换路径530b可以被遍历，而无论遍历ε转换路径530b是否造成检测到匹配失败。

存储该未遍历的转换路径可以包括在一个堆栈(如图4的运行堆栈460)中推送一个条目，这是通过与在该条目中的当前偏移522b 的指示相关联地存储下一节点N3513的一个标识符。下一节点N3513 的标识符可以是一个值、指针或该下一节点的任何其他合适的指示符。偏移的值可以是一个数值、指针或标识区段516在有效载荷542中位置的任何其他合适的值。

根据该示例实施例，基于选择上方路径(即，ε转换路径530a)，行走器320可以提取节点N2510并且尝试将在当前偏移520b(即，“1”) 处的区段522b(即，“x”)与处理周期540c中节点N2510的元素“a”进行匹配。因为“x”并不匹配节点N2510处的元素“a”，处理周期540c的行动536可以包括从运行堆栈460弹出一个条目。弹出的条目 544b可以是一个最近弹出的条目，如在该示例实施例中指示节点N3512 和偏移520b(即，“1”)的一个存储条目544a。

行走器320可以转换并且行走节点N3512并且用在有效载荷 542中偏移520b处定位的区段“x”。于是，处理周期540d展示了匹配结果534对于处理周期540d是肯定的。处理周期540d的行动536可以包括将当前偏移更新到偏移520c并且转换回到分离节点N1508，该节点可以是由节点N3512指示的下一节点。

因为所有从分离节点508的弧线转换都是ε转换，所以行走器 320可以再次选择该多个路径选项中的一个路径，并且不从有效载荷 542中进行消耗，由于当前偏移对于处理周期540e没有更新。在示例实施例中，行走器320再次选择ε转换路径530a。于是，行走器320通过在运行堆栈460上推送节点N3512和当前偏移(现在为520c(即，“2”)) 再次存储一个线程。如对于处理周期540f所示的，行走器320提取节点N2510并将在偏移520c(即，“2”)处的区段522c(即，“a”) 与节点N2510的元素“a”进行匹配。因为“a”在节点N2510处匹配，行走器320将当前偏移更新到520d(即，“3”)并且转换到节点N4514，该节点由如通过编译器306配置的节点N2510元数据指定。

于是，对于处理周期540g，行走器320可以提取下一节点N4 514和在偏移520d处的下一区段522d(即，“b”)。因为“b”在节点N4514处匹配，行走器320可以转换到下一节点N5515。节点N5515 是与一个指示符相关联的标记节点，该指示符表示与该输入流中的正则表达式图样542的一个最终(即，完全或完整)的匹配。由此，对于处理周期540h，行走器320可以不继续沿当前路径行走并且通过在匹配结果缓冲器466中存储一个条目来报告该最终匹配。行走器320然后可以对运行堆栈460检查存储线程并且如由相应的DUP指示符所指示的那样要么丢弃所存储的线程要么激活它们。于是，行走器320弹出标识节点N3512和偏移520(即，“2”)的条目，并且根据与所弹出的条目相关的DUP指示符来确定是通过以在偏移520c处的区段522c行走节点N3512来激活存储的线程还是丢弃所存储的线程。

如在图5B的表538中所示，用于将有效载荷542与图样502 进行匹配的处理周期数目是八个，并且行走器320推送并弹出了未探索的上下文以便记住并返回到节点N3512两次。此外，表538展示了以非投机方式用有效载荷542行走NFA图形504造成在节点N2510和N3512处以两个处理周期处理该区段“x”。根据在此披露的实施例，此类性能可以通过减少匹配所需的处理周期数目、减少可以处理一个区段的次数、以及减少存储和取回未探索上下文所需的访问存储器以进行推送和弹出操作的次数来改进。

从在此披露的实施例获得的性能优化可以是基于以下结论：在一个给定偏移处的一个给定的区段可以通过在NFA中的至少两个节点来处理，并且对于大多数时间(例如，99％)，该在给定偏移处的给定区段是通过至少两个节点处理的，该给定的区段在该至少两个节点中的第一节点处无法匹配并且在该至少两个节点中的第二节点处匹配。例如，在图5A的示例实施例中，如上面参考图5B的表538披露的，在给定偏移520b(即，“1”)处的区段522b(即，“x”)是通过两个节点N2510和N3512处理的，并且在节点N2510处不匹配但在节点N3512处匹配。

根据在此披露的实施例，匹配性能可以通过在该至少两个节点中的每个节点处并行地处理该在给定偏移处的区段来优化。并行地处理该至少两个节点在此可以被称为投机型处理。在此披露的实施例可以是基于以下假设：在至少两个节点中的一个所选节点处的匹配操作将造成失配。该至少两个节点中的所选节点在此可以被称为元素节点。该至少两个节点中的未被选择的节点(将会基于在所选节点处的失配而被遍历)在此可以被称为并行节点，并且可以在与所选节点处理的相同区段的同一个处理周期中投机式地处理，以改进匹配性能。如下面参考图5D 描述的，节点N2510和节点N3512两者可以用在给定偏移520b处的区段“x”处理，从而在与在节点N2510处行走在给定偏移520b处的区段“x”的同一个处理周期中，通过投机式地在节点N3512处行走在偏移520b处的区段“x”来优化匹配性能。

图5C是投机型处理规则578a-d的一个表570的示例实施例的框图。表570是一个带有行动576的真值表，这些行动是基于元素节点匹配结果574和并行节点匹配结果572。根据该投机处理规则578a-d，展示了四个可能的情况。例如，投机处理规则578a、578b、578c和578d 各自具有一个对应的后续行动576，基于匹配结果分别为肯定/肯定、肯定/否定、否定/肯定、和否定/肯定。后续行动576可以是基于并行节点 572的匹配结果和在元素节点574的匹配结果的集合。

投机处理规则578b可以是特别有意义的，因为它通过在元素节点和并行节点处并行地进行匹配而优化了匹配性能，如行动576指示更新该偏移且没有转换。于是，投机处理规则578b使得元素节点和并行节点能够并行地处理下一区段，从而免除了用于节点提取的存储器访问。

由于并行节点是投机式处理的，如果对于元素节点的匹配结果为肯定，后续行动576针对的是提供用于元素节点的后续行动。例如，如果在元素节点的匹配结果为肯定，那么后续行动576包括更新在有效载荷中的当前偏移并且转换到下一节点，该下一节点通过与元素节点相关联的元数据来指定。如果元素节点的匹配结果为肯定，那么并行节点的匹配结果用于确定后续行动576是否包括推送并行节点和当前偏移以便存储为探索的上下文。

例如，投机处理规则578a将一个条目推送到运行堆栈460以允许行走器320用在当前偏移处的区段返回到并行节点，因为返回可以产生在NFA图形中的另一个部分匹配的线程。然而，如果在并行节点的匹配结果是否定匹配结果，如对于投机处理规则578c的情况，那么不将未探索的上下文推送到堆栈上，因为用在当前偏移的区段返回到并行节点将不会使该图样的部分匹配前进。于是，匹配的性能也可以通过投机处理规则578c来优化，因为投机处理规则578c免除了用于匹配的至少一组推送和弹出操作。

如通过投机处理规则578d所示，基于并行节点572的匹配结果和元素节点574的匹配结果的集合，包括在每个节点的否定匹配结果，该至少一个下一后续行动可以包括不继续行走一个给定路径。在有效载荷之内的下一个给定偏移处的下一区段可以基于感测未探索的上下文来行走，如通过对运行时间堆栈460检查存储的线程并且如果已存储则将所存储的线程弹出。该方法可以基于没有感测到该未探索的上下文而终止该行走。

如通过投机处理规则578a和578c所示，基于元素节点574的匹配结果(包括在元素节点处的一个肯定匹配结果)和并行节点572的匹配结果(包括在平行节点处对该区段的一个肯定匹配结果或否定匹配结果)的集合，该至少一个后续行动包括更新该给定偏移以产生下一偏移并转换到下一节点。该下一节点可以基于与该元素节点相关联的元数据来标识。于是，该下一节点可以用在有效载荷之内的下一偏移处的下一区段进行行走。如通过投机处理规则578a所示，基于在平行节点处对该区段的肯定匹配结果，该至少一个下一后续行动可以进一步包括在一个堆栈条目中存储一个未探索的上下文并且将该堆栈条目推送到一个堆栈上。未探索的上下文或直接或间接地标识该并行节点和该给定偏移。

图5D是用于以一种投机方式以该有效载荷542遍历图5A的 NFA图形504的处理周期554a-f的示例实施例的一个表550。如在表 550中所示的，处理周期554a-f可以包括在当前偏移532'用来自有效载荷542的一个区段遍历一个当前节点530'以确定一个匹配结果534'并基于匹配结果534'确定行走行动536'。根据在此披露的实施例，行走器320 可以用有效载荷542中的一个给定偏移处的一个给定的区段并行地处理节点N2510和节点N3512，从而使用图5C中披露的投机处理规则来优化匹配性能。例如，如下文所披露的，处理周期554c和554d可以基于N2510和节点N3512的匹配结果的集合来确定行走器行动536'。

类似于上面披露的图5B的实施例，行走器320可以用在当前偏移520a(即，“0”)处的区段522a(即，“h”)来行走起始节点 N0506。当区段522a匹配在节点N0506处的字符“h”时，行走器320 可以确定匹配结果534'是肯定匹配结果。类似于图5B的实施例，由节点N0506指示的下一节点是分离节点N1508。于是，行走器320采取处理周期554a的行动536'，该行动包括将有效载荷542中的当前偏移更新到520b(即，“1”)并且转换到分离节点N1508。转换可以包括提取(在此也被称为加载)分离节点N1508。

根据图5D的示例实施例，分离节点的与分离节点508相关联的元数据可以包括一个投机处理指示符。如果该投机处理指示符没有被包括在分离节点元数据中，行走器320可以如在图5B的示例实施例中一样继续。包括该投机处理指示符可以包括在分离节点元数据中设定一个字段或其他合适的数据。设定该字段可以包括将该字段配置为真，以指示投机处理，以及将该字段配置为假，以指示非投机处理。包括该投机处理指示符可以按使行走器320能够行走有待投机处理的NFA图形 504的至少两个节点的任何合适的方式进行(即，并行地)。

根据图5D的示例实施例，如果分离节点元数据包括该投机处理指示符，那么对于处理周期554b不消耗来自有效载荷的区段，然而行走器320提取节点N2510和节点N3512两者。节点N2510可以被称为元素节点，而节点N3512可以被称为并行节点或者在该示例实施例中被称为投机节点，因为节点N3512是被投机式处理(即，行走) 的。

如对于处理周期554c所示的，行走器320可以确定对于在元素节点N2510处对于区段522b(即，“x”)的否定匹配结果和在并行节点N3512处的肯定匹配结果。这些匹配结果的集合映射到图5C的投机处理规则条目578b。于是，投机处理规则条目578b的后续行动576指定将当前偏移更新并且将元素和并行节点N2510和N3512分别再次处理。由于节点N2510和N3512已经被提取用于处理周期554c，所以对于处理周期554d不需要提取节点。

如对于处理周期554d所示的，行走器320用在更新后的偏移 (为偏移520c(即，“2”))处的区段522c(即，“a”)来行走元素节点N2510和并行节点N3512。匹配结果534'在元素节点N2510和并行节点N3512两者都为肯定，因为区段“a”匹配在节点N2510的元素“a”并且也匹配在节点N3512处的“^\n”元素，因为“a”不是换行字符。于是，处理周期554d的肯定匹配结果534'的集合映射到图 5C的投机处理规则条目578a。由此，可以将指示并行节点N3512和当前偏移520c(即，“2”)的未探索上下文推送到运行堆栈460上，并且可以提取由元素节点的元数据指定的下一节点。

根据该示例实施例，可以将当前偏移更新到520d(即，“3”) 并且可以提取节点N4514，从而使行走器320转换。对于区段522d的肯定匹配结果(即，“b”)可以对于处理周期554e在节点N4514处确定，并且行走器320可以提取标记节点N5515，从而转换到标记节点N5515，该标记节点可以在与节点N4514相关联的元数据中指定为节点N4514的下一节点。因为节点N5515是一个标记节点，行走器可以将最终匹配结果存储到匹配结果缓冲器466并且不继续行走该活动线程(例如，当前路径)并激活一个存储线程，如果运行堆栈460为非空。

例如，行走器320可以对运行堆栈460检查一个空状态。在该示例实施例中，运行堆栈460是非空的，因为未探索的上下文在处理周期554d中被推送到运行堆栈460中。于是，行走器320可以弹出未探索的上下文，该上下文指示用在偏移520d(即，“3”)处的区段522d(即，“b”)使行走前进到并行节点N3512，并且可以基于如上披露的那样与该堆栈条目相关联的DUP指示符来确定是丢弃未探索的上下文还是处理未探索的上下文。如在该示例实施例的表550中所示，用于将有效载荷542与图样502匹配的处理周期数目是六个，与在图5B的示例实施例中使用的八个处理周期相比这个数目更少。

图6A是一个NFA图形604的框图600，该图形可以由一个行走器320使用以匹配在输入流中的正则表达式图样502。在该示例实施例中，图5A的一个区域507(包括分离节点N1508、投机节点N3512、和ε转换路径530a和530b)用一个可变计数节点N1N3'607表示。可变计数节点N1N3'607是图5A的分离节点N1508和并行(即，投机) 节点N3512的集合。

根据在此披露的实施例，可变计数节点N1N3'607可以被配置成用于标识一个给定元素，如字符类611(即，[^\n])，可变实例数目 613，如无穷，如由可变计数节点所指示的。可变实例数目613可以是至少零次或任何其他合适的实例数目。应当理解的是，给定元素字符类 611是用于说明该示例实施例的目的并且该给定元素可以是通过可变计数节点N1N3'进行匹配的任何合适的元素。

可变计数节点是可以将一个元素匹配可变次数的节点，该次数可以是由一个范围限定的(例如，零到五次)。可变计数节点可以是四种可变计数节点之一：懒惰型、贪婪型、领属型、或全匹配型节点。懒惰型可变计数节点可以被配置成用于在该范围内找到一个最短的可能元素匹配。贪婪型或领属型可变计数节点可以被配置成用于在该范围内找到一个最长的可能元素匹配。全匹配型可变计数节点可以被配置成用于返回该有效载荷中的所有匹配。

懒惰型计数可变节点可以被配置成用于基于与该懒惰型可变计数节点相关联的元数据所标识的下一节点处的一个区段的失配消耗 (即，处理)来自有效载荷的一个区段的单个实例。贪婪型可变计数节点可以被配置成用于消耗来自有效载荷的连续的区段，直到在贪婪型可变计数节点出确定这些连续区段之一的失配或者直到贪婪型可变计数节点已经消耗(即，处理)了可变的连续区段数目的总数。

在图6A的示例实施例中，可变计数节点N1N3'607是一个与元数据609相关联的懒惰型可变计数节点，该元数据或直接或间接地标识下一节点617，如元素节点N2610。在该示例实施例中，基于在输入流中给定元素611的可变数目连续实例613的零个或更多个匹配实例，行走器将行走前进到元素节点N2610。例如，在该示例实施例中，懒惰型可变计数节点N1N3'607被配置成用于匹配该字符类元素“^\n”(即，不是换行字符)的零个或更多个实例无限次。

根据在此披露的实施例，NFA的每个节点可以与元数据相关联，该元数据包括至少四个字段，如一个节点类型、元素、计数、和下一节点，虽然基于节点类型该至少四个字段中的一个或多个可能是不适用的。

与懒惰型可变计数节点N1N3'607相关联的元数据609可以包括一个用于追踪在有效载荷中肯定匹配的元素611的连续实例总数(未展示)的计数(未展示)，以允许该总数与该可变数目613的比较。

根据在此披露的实施例，行走器320可以被配置成用于以投机方式行走NFA图形604，以优化在输入流中对正则表达式图样502进行匹配的性能。

图6B是用于以一种非投机方式以有效载荷542遍历图6A的 NFA图形604的处理周期628a-g的示例实施例的一个表618。类似于上面披露的图5A和图5B的实施例，行走器320可以用在当前偏移520a (即，“0”)处的区段522a(即，“h”)来行走起始节点N0606。当区段522a匹配在节点N0606处的字符“h”时，行走器320可以确定对于处理周期628a该匹配结果624是肯定匹配结果。在图6A的实施例中，由节点N0606指示的下一节点是懒惰型可变计数节点N1N3'607。于是，行走器320采取处理周期628a的行动626，该行动包括将有效载荷542中的当前偏移更新到520b(即，“1”)并且转换到懒惰型可变计数节点N1N3'607。转换可以包括提取(在此也被称为加载)懒惰型可变计数节点N1N3'607。

因为懒惰型可变计数节点N1N3'607是懒惰的，处理周期628b 的行动626可以包括存储该未探索的上下文，如通过存储该节点N1N3' 607和当前偏移520b(即，“1”)的一个间接或直接的标识符并且前进到由该懒惰型可变计数节点N1N3'607标识的下一节点617而没有更新当前偏移。于是，对于处理周期628a，懒惰型可变计数节点N1N3'607 没有消耗有效载荷。

存储该未探索的上下文可以使得行走器320能够记得返回到懒惰型可变计数节点N1N3'607以便在沿所选的部分匹配路径发生否定匹配结果的事件中在有效载荷542中的偏移520b处用区段“x”行走懒惰型可变计数节点N1N3'607，例如，如果该否定匹配结果是在节点N2610 处或沿从节点N2610延伸的路径上的节点处确定的。为了存储该未探索的上下文，行走器320可以将一个条目推送630a到运行堆栈460，该条目包括一个用于懒惰型可变计数节点N1N3'607和偏移520b的标识符。

根据在此披露的实施例，未探索的上下文可以用DUP指示符来标记，该指示符指示在沿所选的转换路径标识一个用于图样502的最终匹配的事件中行走器320是丢弃还是处理所推送的该未探索的上下文。例如，基于到达指示在输入流中对于图样502的最终(即，完整或完全)的匹配的标记节点N5615，行走器320可以采用所推送的该堆栈条目的DUP指示符来确定是否通过在偏移520b处以区段“x”行走懒惰型可变计数节点N1N3'607来处理该未探索的上下文，以努力确定 NFA图形604的匹配图样502的另一个路径，或者是否丢弃该未探索的上下文，由于在输入流中的图样502的仅单条匹配路径是有意义的。

根据图6B的示例实施例，行走器320可以提取节点N2610并且可以尝试将处理周期628c中的当前偏移520b(即，“1”)处的区段 522b(即，“x”)与节点N2610的元素“a”进行匹配(即，搜索)。因为“x”并不匹配节点N2610处的元素“a”，处理周期628c的行动 626可以包括从运行堆栈460弹出630b一个条目。弹出的条目可以是一个最近弹出的条目，如指示懒惰型可变计数节点N1N3'607和偏移520b (即，“1”)的最近推送630a的条目。

行走器320可以转换并且用在有效载荷542中偏移520b处定位的区段“x”来行走懒惰型可变计数节点N1N3'607。因为“x”不是换行字符，所以“x”是在懒惰型可变计数节点N1N3'607处的肯定匹配，并且处理周期628d展示出匹配结果624对于处理周期528d为肯定。处理周期528d的行动618可以包括将当前偏移更新到偏移520c并且转换回到元素节点N2610，该节点可以是由与懒惰型可变计数节点N1N3' 607相关联的元数据609指示的下一节点。

如对于处理周期628e所示的，行走器320提取节点N2610并将在偏移520c(即，“2”)处的区段522c(即，“a”)进行比较。因为“a”是在元素节点N2610处的肯定匹配，行走器320将当前偏移更新到520d(即，“3”)并且转换到节点N4614。

于是，对于处理周期628f，行走器320可以提取节点N4614 和在偏移520d处的区段522d(即，“b”)。因为“b”是在节点N4614 处的肯定匹配，行走器320可以转换到节点N5615。节点N5615是与一个指示符相关联的标记节点，该指示符表示与该输入流中的正则表达式图样542的一个最终(即，完全或完整)的匹配。由此，对于处理周期628g，行走器320可以不继续行走并且通过在匹配结果缓冲器466 中存储一个条目来报告该最终匹配。行走器然后可以对运行堆栈460检查存储线程并且如由在运行堆栈460中这些条目的相应的DUP指示符所指示的那样要么丢弃所存储的线程要么激活它们。

如在图6B的表618中所示，用于将有效载荷542与图样502 进行匹配的处理周期数目是七个，并且行走器320推送630a并弹出630b 了未探索的上下文以便记住并用在偏移520b处的区段“x”返回到懒惰型可变计数节点N1N3'607两次。于是，表618还展示出区段“x”由行走器320在懒惰型可变计数节点N1N3'607和节点N2610两者处进行处理(即，消耗)，并且在节点N2610处是失配(即，否定匹配) 而在懒惰型可变计数节点N1N3'607处是肯定匹配。

根据在此披露的实施例，此类性能可以通过减少匹配所需的处理周期数目、通过减少可以处理一个给定区段的处理周期数目、以及通过减少存储和取回未探索上下文的推送和弹出操作的次数而减少访问存储器的次数来改进。类似于上面对于图5D披露的行走，在此披露的实施例可以用投机方式行走NFA图形604。

例如行走器320可以被配置成用于在有效载荷542之内的一个给定偏移下用一个给定的区段并行地行走NFA 604中的至少两个节点。行走器320可以在该至少两个节点中的每一个节点处在该有效载荷之内的该给定偏移下确定对于该区段的一个匹配结果。行走器320可以基于所确定的每个匹配结果的集合来确定用于行走NFA图形604的至少一个后续行动。

图6C是用于以该有效载荷542遍历图6A的NFA图形604的处理周期658a-e的另一个示例实施例的一个表648。如在表648中所示的，处理周期658a-e可以包括在当前偏移652用来自有效载荷542的一个区段遍历一个当前节点650以确定一个匹配结果654并基于匹配结果 654确定行走行动656。根据在此披露的实施例，行走器320可以用有效载荷542中的一个给定偏移处的一个给定的区段并行地处理懒惰型可变计数节点N1N3'607和元素节点N2610，从而使用上面参考图5C 披露的投机处理规则来优化匹配性能。

根据图6C的示例实施例，与懒惰型可变计数节点N1N3'607 相关联的元数据609可以包括一个投机处理指示符(未展示)。如果该投机处理指示符没有包括在懒惰型可变计数节点元数据中，行走器320 可以如在图6B的示例实施例中一样继续。

包括该投机处理指示符可以按使行走器320能够行走有待以投机方式处理的NFA图形604的至少两个节点的任何合适的方式进行 (即，并行地)。该至少两个被并行处理的节点可以包括一个元素节点和一个并行节点。在该示例实施例中，节点N2610可以被称为元素节点而懒惰型可变计数节点N1N3'607可以被称为并行节点。

根据图6C的示例实施例，如果懒惰型可变计数节点元数据包括该投机处理指示符，则对应于有效载荷中的当前偏移的区段可以对于处理周期658b被处理并且行走器320可以提取元素节点N2610和懒惰型可变计数节点N1N3'607这两个节点。如对于处理周期658b所示的，行走器320可以确定对于在元素节点N2610处对于区段522b(即，“x”) 的否定匹配结果和在并行节点N1N3'607处的肯定匹配结果。这些匹配结果的集合映射到投机处理规则条目578b。于是，行动576指定将当前偏移更新并且使元素和并行节点(如节点N2610和N1N3'607)分别被再次处理(即，行走)。由于节点N2610和N1N3'607已经被提取用于处理周期658b，所以对于处理周期658c不需要提取节点。

如对于处理周期658c所示的，行走器320用在更新后的偏移 (为偏移520c(即，“2”))处的区段522c(即，“a”)在有效载荷542中来行走元素节点N2610和并行节点N1N3'607。匹配结果654 在元素节点N2610和并行节点N1N3'607两者都为肯定，因为区段“a”匹配在元素节点N2610的元素“a”并且也匹配在并行节点N1N3'607 处的“^\n”元素，因为“a”不是换行字符。

处理周期658c的匹配结果中的肯定匹配结果654的集合映射到投机处理规则条目578a。由此，可以将指示并行节点N1N3'607和当前偏移520c(即，“2”)的未探索上下文推送到运行堆栈460上，并且可以提取由元素节点610的元数据指定的下一节点。根据该示例实施例，可以将当前偏移更新到520d(即，“3”)并且可以提取节点N4614，由于节点N4614是由元素节点N2610的元数据指示的下一节点。

对于区段522d的肯定匹配结果(即，“b”)可以对于处理周期658d在节点N4614处确定，并且行走器320可以转换到标记节点 N5615，该标记节点可以在与节点N4614相关联的元数据中指定为节点N4614的下一节点。因为节点N5615是一个标记节点，行走器可以将最终匹配结果存储到匹配结果缓冲器466并且不继续行走该活动线程(例如，当前路径)。

行走器320可以对运行堆栈460检查一个空状态。在该示例实施例中，运行堆栈460不是空的，因为未探索的上下文在处理周期658c 中被推送到运行堆栈460中。于是，行走器320可以弹出未探索的上下文，该上下文指示用在偏移520c(即，“2”)处的区段522d(即，“a”) 使行走前进到并行节点N1N3'607，并且可以基于与该堆栈条目相关的 DUP指示符来确定是丢弃未探索的上下文还是处理未探索的上下文。

如在该示例实施例的表648中所示，使用投机处理将有效载荷 542与图样502匹配的处理周期数目是五个，与在图6B的非投机处理示例实施例中使用的七个处理周期相比这个数目更少。应当理解的是，这样的基于如以上所披露的示例实施例所示的投机处理的性能增加是用于说明的目的并且通过使用投机处理实现的性能增益可以比所说明的那些更大。例如，此类性能增益可以取决于输入有效载荷而增加。基于输入流的内容，进一步搅动(churning)如图6B的用于从并行节点或到并行节点的转换的推送630a和弹出630b操作可以更普遍地用于不同的有效载荷，从而造成比如下所述的更大的性能增益。

图6D是可以用图6A的NFA图形604行走的另一个有效载荷 662的框图660。输入有效载荷662包括在偏移672处的区段670。区段 674a-f对应于区段h、x、x、x、a、和b，它们分别映射到偏移676a-f (即，0、1、2、3、4、和5)。

图6E是用于以一种非投机方式以图6D的有效载荷662行走图6A 的NFA图形604的处理周期681a-k的示例实施例的一个表680。如在表680中所示的，处理周期681a-k可以包括在当前偏移684用来自有效载荷662的一个区段行走一个当前节点682以确定一个匹配结果686并基于匹配结果686确定行走行动688。如在该示例实施例中所示，在有效载荷662中找到图样502的最终匹配之前需要十一个处理周期。另外，处理周期反映出并行节点N1N3'607的未探索的上下文已经被推送并弹出多次，因为行走器320确定在元素节点N2610处的一个失配区段，从而导致行走器320在元素节点N2610与并行节点607之间的搅动。在节点之间这样的搅动造成行走器320以性能为代价来提取并行节点 607和元素节点N2610，原因是相应的存储器访问需要附加的处理器周期。这样的存储器访问可能昂贵的，尤其是因为这些存储器可以是纠错码(ECC)受保护型的存储器。于是，访问ECC受保护的存储器以进行推送或弹出操作可能花费四个时钟周期或更长。

图6F是用于以一种投机方式以图6D的有效载荷662遍历图 6A的NFA图形604的处理周期691a-g的另一个示例实施例的一个表 690。如在表690中所示的，处理周期691a-g可以包括在当前偏移694 用来自有效载荷662的一个区段遍历一个当前节点692以确定一个匹配结果696并基于匹配结果696确定行走行动698。如在该示例实施例中所示，在有效载荷662中找到图样502的最终匹配之前需要七个处理周期，与图6E的非投机处理实施例的十一个处理周期681a-k不同。根据在此披露的实施例，行走器320可以用有效载荷662中的一个给定偏移处的一个给定的区段并行地处理懒惰型可变计数节点N1N3'607(在该示例实施例中为并行节点)和节点N2610(在该示例实施例中为元素节点)，从而使用上面参考图5C披露的投机处理规则来优化匹配性能。

图7是一种方法的示例实施例的一个流程图700，该方法可以被实现在至少一个处理器中，该处理器与操作地耦合到网络的一个安全装置中的至少一个存储器操作地耦合。该方法可以开始(702)并在至少一个存储器中存储包括从至少一个正则表达式图样生成的多个节点的至少一个有限自动机(704)。该方法可以包括将该至少一个存储器操作地耦合到至少一个处理器并且该至少一个处理器可以被配置成用于以经由操作地耦合到网络的一个硬件网络接口接收的一个输入流的多个区段来行走该至少一个有限自动机，以对该输入流中的该至少一个正则表达式图样进行匹配(706)。该行走可以包括在该输入流中的一个数据包的一个有效载荷之内的一个给定偏移下用一个区段并行地行走该至少一个有限自动机中的一个给定有限自动机的至少两个节点 (708)。该行走可以包括在该至少两个节点中的每一个节点处在该有效载荷之内的该给定偏移下确定对于该区段的一个匹配结果(710)。该行走可以进一步包括基于所确定的每个匹配结果的集合来确定用于行走该给定有限自动机的至少一个后续行动(712)，并且在该示例实施例中，该方法随后结束(714)。

图8是一台计算机800的内部结构的示例的一个框图，其中，可以实现本发明的各实施例。计算机800包含一个系统总线802，其中，总线是用于在计算机或处理系统的组件之间进行数据传输的一组硬件线。系统总线802实质上是连接计算机系统的不同元件(例如处理器、磁盘存储器、存储器、输入/输出端口、网络端口等等)、使得在这些元件之间能够进行信息传输的一种共享管道。与系统总线802一起工作的是一个I/O设备接口804，用于将各种输入和输出设备(例如键盘、鼠标、显示器、打印机、扬声器等等)连接到计算机800。网络接口806 允许计算机800连接到附接于网络的各种其他设备。存储器808提供用于计算机软件指令810和数据812的易失性存储，这些指令和数据可以用于实现本发明的实施例。磁盘存储器814提供用于计算机软件指令 810和数据812的非易失性存储，这些指令和数据可以用于实现本发明的实施例。中央处理器单元818还与系统总线802一起工作并且提供计算机指令的执行。

本发明的其他示例实施例可以使用计算机程序产品进行配置；例如，控制可以在软件中编程为实现本发明的示例实施例。本发明的其他示例实施例可以包括一种非瞬态计算机可读介质，该介质含有可以由处理器执行的指令并且当执行时致使处理器完成在此描述的方法。应当理解的是，在此描述的这些框图和流程图的元素可以软件、硬件、固件或在将来确定的其他类似的实现方式来实现。此外，在此描述的这些框图和流程图的元素可以在软件、硬件、或固件中以任何方式被组合或拆分。

应当理解的是，术语“在此”可转移到结合有在此呈现的传授内容的申请或专利中，使得主题、定义或数据在进行此结合的申请或专利中沿用。

如果在软件中实现，那么软件可以任何能够支持在此披露的示例实施例的语言书写。该软件可以被存储在任何形式的计算机可读介质中，如随机存取存储器(RAM)、只读存储器(ROM)、光盘只读存储器(CD-ROM)等等中。在工作中，通用或特定用途处理器以本领域中充分已知的方式加载和执行软件。应当理解的是，此外该框图和流程图可以包括更多或更少的元件、不同地安排或取向、或不同地表示。应当理解的是，实现方式可以指框图、流程图、和/或网络图以及展示本发明实施例的执行的框图和流程图的数目。

虽然通过参考本发明的示例实施例已经具体地示出和描述了本发明，但本领域普通技术人员将会理解在不脱离由所附权利要求书限定的本发明范围的情况下可在形式和细节中做出不同的改变。

Claims (51)

1.一种操作性耦合到网络的安全装置，该安全装置包括：

至少一个存储器，该至少一个存储器被配置成用于存储包括从至少一个正则表达式图样生成的多个节点的至少一个有限自动机；

至少一个处理器，该至少一个处理器操作地耦合到该至少一个存储器并且被配置成用于以经由网络接收的一个输入流的多个区段来行走该至少一个有限自动机，以匹配在该输入流中的该至少一个正则表达式图样，该行走包括：

在该输入流中的一个数据包的一个有效载荷之内的一个给定偏移下用一个区段并行地行走该至少一个有限自动机中的一个给定有限自动机的至少两个节点；

在该至少两个节点中的每一个节点处在该有效载荷之内的该给定偏移下确定对于该区段的一个匹配结果；以及

基于所确定的每个匹配结果的集合来确定用于行走该给定有限自动机的至少一个后续行动。

2.如权利要求1所述的安全装置，其中，该至少一个有限自动机包括一个确定型有限自动机(DFA)和至少一个非确定型有限自动机(NFA)，该给定有限自动机是该至少一个NFA中的一个给定的NFA。

3.如权利要求1所述的安全装置，其中，在该至少一个处理器的同一个处理周期中，在该至少两个节点中的每个节点处，确定对于该区段的该匹配结果。

4.如权利要求1所述的安全装置，其中，该至少两个节点包括一个元素节点和一个并行节点，该元素节点被配置成用于匹配在该有效载荷中的一个第一元素的单个实例，该第一元素是一个第一字符或第一字符类，该并行节点是以下各项之一：(i)一个可变计数节点，该可变计数节点被配置成用于匹配在该有效载荷中的一个第二元素的可变数目的连续实例，该第二元素是一个第二字符或第二字符类，或者(ii)一个投机节点，该投机节点被配置成用于基于从一个分离节点或到该分离节点的转换弧线来匹配在该有效载荷中的该第二元素的该可变数目的连续实例。

5.如权利要求4所述的安全装置，其中，该可变计数节点是以下各项的集合：

该分离节点，该分离节点被配置成用于独立于该有效载荷并且不从该有效载荷进行消耗而将该行走经由ε转换弧线前进到该元素节点和该投机节点并且用在该给定偏移下的该区段并行地行走该元素和投机节点；以及

该投机节点，该投机节点被配置成用于将该行走前进回到该分离节点并且基于在该投机节点处与该第二元素的一个肯定匹配通过更新该给定偏移来消耗该区段。

6.如权利要求4所述的安全装置，其中，该给定的有限自动机是一个NFA图形，该NFA图形包括从该可变计数节点到该元素节点的一次转换，在该NFA图形中该可变计数节点在该元素节点之前。

7.如权利要求4所述的安全装置，其中，该可变计数节点是与或直接或间接地标识该元素节点的元数据相关联的懒惰型节点，以基于在该有效载荷中的该第二元素的该可变数目的连续实例中的单个匹配实例使该行走前进到该元素节点。

8.如权利要求7所述的安全装置，其中，与该可变计数懒惰节点相关联的该元数据包括一个用于追踪在该有效载荷中匹配的该第二元素的连续实例总数的计数，以允许该总数与该可变数目的比较。

9.如权利要求4所述的安全装置，其中，基于该并行节点为该投机节点，该给定的有限自动机包括该多个节点中的一个分离节点，该元素节点和该投机节点是基于与该分离节点相关联的元数据来标识的，该分离节点被配置成用于：

独立于该有效载荷并且不从该有效载荷进行消耗而将该行走经由ε转换弧线前进到该元素节点和该投机节点，并且基于包括在与该分离节点相关联的元数据中的一个投机处理指示符，用在该给定偏移下的该区段并行地行走该元素和投机节点。

10.如权利要求9所述的安全装置，其中，基于在与该分离节点相关联的该元数据中不包括该投机处理指示符而不并行地行走该元素和投机节点。

11.如权利要求10所述的安全装置，其中，用在该给定偏移下的该区段行走该投机节点是基于在该元素节点处在该给定偏移下对于该区段的一次否定匹配。

12.如权利要求11所述的安全装置，其中，用在该给定偏移下的该区段行走该投机节点是进一步基于未探索的上下文的存储和取回，该未探索的上下文或直接或间接地标识该投机节点和该给定偏移。

13.如权利要求12所述的安全装置，其中，该未探索的上下文的该存储包括：

将该未探索的上下文存储在一个堆栈条目中；以及

将该堆栈条目推送到一个堆栈上，并且取回该未探索的上下文包括从该堆栈弹出该堆栈条目。

14.如权利要求13所述的安全装置，其中，该投机节点被配置成用于基于在该投机节点处与该第二元素的一次肯定匹配将该行走前进到该分离节点。

15.如权利要求1所述的安全装置，其中，基于该集合包括在被并行行走的该至少两个节点中的每个节点处的一个否定匹配结果，该至少一个后续行动包括：

在被并行行走的该至少两个节点中的每个节点处不继续行走一个给定的路径，该给定的路径部分地匹配在该给定的有限自动机中的该至少一个正则表达式图样；

基于感测未探索的上下文，用在该有效载荷内的一个下一给定偏移处的一个下一区段来行走该多个节点中的一个下一节点；以及

基于没有感测到该未探索的上下文而终止该行走。

16.如权利要求15所述的安全装置，其中，该未探索的上下文或直接或间接地标识该下一节点和该下一给定偏移，以便用该下一区段在该下一节点处沿另一个路径前进该行走，该路径部分匹配该给定的有限自动机中的该至少一个正则表达式图样。

17.如权利要求16所述的安全装置，其中，该未探索的上下文的该感测包括：

确定一个堆栈的非空状态；以及

从该堆栈弹出一个堆栈条目，该堆栈条目包括该未探索的上下文并且是一个最近推送到该堆栈上的条目。

18.如权利要求1所述的安全装置，其中，该至少两个节点包括一个元素节点和一个并行节点，并且基于该集合包括以下各项：

在该元素节点处对于该区段的一个肯定匹配结果；以及

在该并行节点处对于该区段的该肯定匹配结果或一个否定匹配结果，该至少一个后续行动包括：

更新该给定偏移以产生一个下一偏移；

基于与该元素节点相关联的元数据来标识该多个节点中的一个下一节点；

用在该有效载荷之内的该下一偏移处的一个下一区段行走该下一节点；

在所标识的该下一节点处确定对于该下一区段的一个下一匹配结果；以及

基于所确定的该下一匹配结果来确定用于行走该给定有限自动机的至少一个下一后续行动。

19.如权利要求18所述的安全装置，其中，基于在该并行节点处对于该区段的该肯定匹配结果，该至少一个后续行动进一步包括：

将一个未探索的上下文存储在一个堆栈条目中；以及

将该堆栈条目推送到一个堆栈上，该未探索的上下文或直接或间接地标识该并行节点和该给定偏移。

20.如权利要求19所述的安全装置，其中，基于该下一匹配结果为该否定匹配结果，该至少一个下一后续行动包括：

基于感测未探索的上下文，用在该有效载荷中的该给定偏移处的该区段来行走该并行节点；以及

基于没有感测到该未探索的上下文而终止该行走。

21.如权利要求20所述的安全装置，其中，该未探索的上下文的该感测包括：

确定一个堆栈的非空状态；以及

从该堆栈弹出一个堆栈条目，该堆栈条目包括该未探索的上下文并且是一个最近推送到该堆栈上的条目。

22.如权利要求18所述的安全装置，其中，更新该给定偏移以产生该下一偏移包括：

基于该行走的方向为一个正向方向而增大该给定偏移；以及

基于该行走的方向为一个反向方向而减小该给定偏移。

23.如权利要求1所述的安全装置，其中，被并行行走的该至少两个节点包括一个元素节点和一个并行节点，并且基于该集合包括在该元素节点处对于该区段的一个否定匹配结果和在该并行节点处对于该区段的一个肯定匹配结果，该至少一个后续行动包括：

更新该给定偏移以产生一个下一偏移；以及

用在该下一偏移处的一个下一区段并行地行走该元素节点和该并行节点。

24.如权利要求23所述的安全装置，其中，更新该给定偏移以产生该下一偏移包括：

基于该行走的方向为一个正向方向而增大该给定偏移；以及

基于该行走的方向为一个反向方向而减小该给定偏移。

25.如权利要求1所述的安全装置，其中，并行行走该至少两个节点通过以下方式优化了该匹配的性能：

免除如果不并行行走该至少两个节点时需要的上下文的存储和取回，以便基于在该给定偏移处的该区段的一个否定匹配结果，用在该给定偏移处的该区段使该行走从该至少两个节点中的一个第一节点前进到该至少两个节点中的一个第二节点。

26.一种用于处理有限自动机的方法，包括：

在至少一个存储器中存储包括从至少一个正则表达式图样生成的多个节点的至少一个有限自动机；以及

将该至少一个存储器操作地耦合到至少一个处理器，该至少一个处理器被配置成用于以经由操作地耦合到网络的一个硬件网络接口接收的一个输入流的多个区段来行走该至少一个有限自动机，以对该输入流中的该至少一个正则表达式图样进行匹配，该行走包括：

在该输入流中的一个数据包的一个有效载荷之内的一个给定偏移下用一个区段并行地行走该至少一个有限自动机中的一个给定有限自动机的至少两个节点；

在该至少两个节点中的每一个节点处在该有效载荷之内的该给定偏移下确定对于该区段的一个匹配结果；以及

基于所确定的每个匹配结果的集合来确定用于行走该给定有限自动机的至少一个后续行动。

27.如权利要求26所述的方法，其中，该至少一个有限自动机包括一个确定型有限自动机(DFA)和至少一个非确定型有限自动机(NFA)，该给定有限自动机是该至少一个NFA中的一个给定的NFA。

28.如权利要求26所述的方法，其中，在该至少两个节点中的每个节点处的该确定是在该至少一个处理器的同一个处理周期中。

29.如权利要求26所述的方法，其中，该至少两个节点包括一个元素节点和一个并行节点，该元素节点被配置成用于匹配在该有效载荷中的一个第一元素的单个实例，该第一元素是一个第一字符或第一字符类，该并行节点是以下各项之一：(i)一个可变计数节点，该可变计数节点被配置成用于匹配在该有效载荷中的一个第二元素的可变数目的连续实例，该第二元素是一个第二字符或第二字符类，或者(ii)一个投机节点，该投机节点被配置成用于基于从一个分离节点或到该分离节点的转换弧线来匹配在该有效载荷中的该第二元素的该可变数目的连续实例。

30.如权利要求29所述的方法，其中，该可变计数节点是以下各项的集合：

该分离节点，该分离节点被配置成用于独立于该有效载荷并且不从该有效载荷进行消耗而将该行走经由ε转换弧线前进到该元素节点和该投机节点并且用在该给定偏移下的该区段并行地行走该元素和投机节点；以及

该投机节点，该投机节点被配置成用于将该行走前进回到该分离节点，并且基于在该投机节点处与该第二元素的一次肯定匹配，通过更新该给定偏移来消耗该区段。

31.如权利要求29所述的方法，其中，该给定的有限自动机是一个NFA图形，该NFA图形包括从该可变计数节点到该元素节点的一个转换弧线，在该NFA图形中该可变计数节点在该元素节点之前。

32.如权利要求29所述的方法，其中，该可变计数节点是一个与或直接或间接地标识该元素节点的元数据相关联的可变计数懒惰节点，以基于在该有效载荷中的该第二元素的该可变数目的连续实例中的单个匹配实例使该行走前进到该元素节点。

33.如权利要求32所述的方法，其中，与该可变计数懒惰节点相关联的该元数据包括一个用于追踪在该有效载荷中匹配的该第二元素的连续实例总数的计数，以允许该总数与该可变数目的比较。

34.如权利要求29所述的方法，其中，基于该并行节点为该投机节点，该给定的有限自动机包括该多个节点中的一个分离节点，该元素节点和该投机节点是基于与该分离节点相关联的元数据来标识的，该分离节点被配置成用于：

独立于该有效载荷并且不从该有效载荷进行消耗而将该行走经由ε转换弧线前进到该元素节点和该投机节点，并且基于包括在与该分离节点相关联的元数据中的一个投机处理指示符，用在该给定偏移下的该区段并行地行走该元素和投机节点。

35.如权利要求34所述的方法，其中，基于在与该分离节点相关联的该元数据中不包括该投机处理指示符而不并行地行走该元素和投机节点。

36.如权利要求35所述的方法，其中，在该给定偏移下用该区段行走该投机节点是基于在该元素节点处在该给定偏移下对于该区段的一次否定匹配。

37.如权利要求36所述的方法，其中，用在该给定偏移下的该区段行走该投机节点是进一步基于未探索的上下文的存储和取回，该未探索的上下文或直接或间接地标识该投机节点和该给定偏移。

38.如权利要求37所述的方法，其中，该未探索的上下文的该存储包括：

将该未探索的上下文存储在一个堆栈条目中；以及

将该堆栈条目推送到一个堆栈上，并且取回该未探索的上下文包括从该堆栈弹出该堆栈条目。

39.如权利要求38所述的方法，其中，该投机节点被配置成用于基于在该投机节点处与该第二元素的一次肯定匹配将该行走前进到该分离节点。

40.如权利要求26所述的方法，其中，基于该集合包括在被并行行走的该至少两个节点中的每个节点处的一个否定匹配结果，该至少一个后续行动包括：

在被并行行走的该至少两个节点中的每个节点处不继续行走一个给定的路径，该给定的路径部分地匹配在该给定的有限自动机中的该至少一个正则表达式图样；

基于感测未探索的上下文，用在该有效载荷内的一个下一给定偏移处的一个下一区段来行走该多个节点中的一个下一节点；以及

基于没有感测到该未探索的上下文而终止该行走。

41.如权利要求40所述的方法，其中，该未探索的上下文或直接或间接地标识该下一节点和该下一给定偏移，以便在用该下一区段在该下一节点处沿另一个路径前进该行走，该路径部分匹配该给定的有限自动机中的该至少一个正则表达式图样。

42.如权利要求41所述的方法，其中，该未探索的上下文的该感测包括：

确定一个堆栈的非空状态；以及

从该堆栈弹出一个堆栈条目，该堆栈条目包括该未探索的上下文并且是一个最近推送到该堆栈上的条目。

43.如权利要求26所述的方法，其中，该至少两个节点包括一个元素节点和一个并行节点，并且基于该集合包括以下各项：

在该元素节点处对于该区段的一个肯定匹配结果；以及

在该并行节点处对于该区段的该肯定匹配结果或一个否定匹配结果，该至少一个后续行动包括：

更新该给定偏移以产生一个下一偏移；

基于与该元素节点相关联的元数据来标识该多个节点中的一个下一节点；

用在该有效载荷之内的该下一偏移处的一个下一区段行走该下一节点；

在所标识的该下一节点处确定对于该下一区段的一个下一匹配结果；以及

基于所确定的该下一匹配结果来确定用于行走该给定有限自动机的至少一个下一后续行动。

44.如权利要求43所述的方法，其中，基于在该并行节点处对于该区段的该肯定匹配结果，该至少一个后续行动进一步包括：

将一个未探索的上下文存储在一个堆栈条目中；以及

将该堆栈条目推送到一个堆栈上，该未探索的上下文或直接或间接地标识该并行节点和该给定偏移。

45.如权利要求44所述的方法，其中，基于该下一匹配结果为该否定匹配结果，该至少一个下一后续行动包括：

基于感测未探索的上下文，用在该有效载荷中的该给定偏移处的该区段来行走该并行节点；以及

基于没有感测到该未探索的上下文而终止该行走。

46.如权利要求45所述的方法，其中，该未探索的上下文的该感测包括：

确定一个堆栈的非空状态；以及

从该堆栈弹出一个堆栈条目，该堆栈条目包括该未探索的上下文并且是一个最近推送到该堆栈上的条目。

47.如权利要求46所述的方法，其中，更新该给定偏移以产生该下一偏移包括：

基于该行走的方向为一个正向方向而增大该给定偏移；以及

基于该行走的方向为一个反向方向而减小该给定偏移。

48.如权利要求26所述的方法，其中，被并行行走的该至少两个节点包括一个元素节点和一个并行节点，并且基于该集合包括在该元素节点处对于该区段的一个否定匹配结果和在该并行节点处对于该区段的一个肯定匹配结果，该至少一个后续行动包括：

更新该给定偏移以产生一个下一偏移；以及

用在该下一偏移处的一个下一区段并行地行走该元素节点和该并行节点。

49.如权利要求48所述的方法，其中，更新该给定偏移以产生该下一偏移包括：

基于该行走的方向为一个正向方向而增大该给定偏移；以及

基于该行走的方向为一个反向方向而减小该给定偏移。

50.如权利要求26所述的方法，其中，并行行走该至少两个节点通过以下方式优化了该匹配的性能：

免除如果不并行行走该至少两个节点时需要的上下文的存储和取回，以便基于在该给定偏移处的该区段的一个否定匹配结果，用在该给定偏移处的该区段使该行走从该至少两个节点中的一个第一节点前进到该至少两个节点中的一个第二节点。

51.一种非瞬态计算机可读介质，其上编码有一个指令序列，该指令序列在由至少一个处理器执行时致使该至少一个处理器：

用一个输入流的多个区段行走至少一个有限自动机，该有限自动机包括从至少一个正则表达式图样生成的多个节点，以便对在该输入流中的该至少一个正则表达式图样进行匹配，该行走包括：

在该输入流中的一个数据包的一个有效载荷之内的一个给定偏移下用一个区段并行地行走该至少一个有限自动机中的一个给定有限自动机的至少两个节点；

在该至少两个节点中的每一个节点处在该有效载荷之内的该给定偏移下确定对于该区段的一个匹配结果；以及

基于所确定的每个匹配结果的集合来确定用于行走该给定有限自动机的至少一个后续行动。