基于栈顶(TOS)存储器的有限自动机处理

摘要

本发明的各实施例涉及基于栈顶(TOS)存储器的有限自动机处理。提供了一种方法和相应的装置和系统用于优化在输入流中的至少一个正则表达式图样的匹配，通过存储一个上下文用于行走至少一个有限自动机中的一个给定有限自动机的多个节点中的一个给定节点，该存储包括一个存储确定：基于与该第一存储器相关联的上下文状态信息，确定访问该第一存储器并且不访问该第二存储器或者访问该第一存储器和该第二存储器。另外，为了取回一个未决的上下文，该取回可以包括一个取回确定：基于与该第一存储器相关的该上下文状态信息，确定访问该第一存储器并且不访问该第二存储器或者访问该第二存储器并且不访问该第一存储器。该第一存储器可以具有相对于该第二存储器更快的读写访问时间。

说明书

技术领域

本发明的各实施例涉及基于栈顶(TOS)存储器的有限自动机处理。

背景技术

开放系统互连(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))执行内容搜索。

发明内容

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

根据一个实施例，一种方法可以包括将一个第一存储器和一个第二存储器操作地耦合。该方法可以包括将至少一个处理器操作地耦合到该第一存储器和该第二存储器。该至少一个处理器可以被配置成用于存储一个上下文，该上下文用于行走属于至少一个有限自动机中的一个给定有限自动机的多个节点中的一个给定节点。该存储可以包括基于与该第一存储器相关联的上下文状态信息来确定(i)访问该第一存储器并且不访问该第二存储器还是(ii)访问该第一存储器和该第二存储器。

该上下文可以标识该给定节点以及从网络接收的一个输入流的一个有效载荷中的一个区段的一个偏移，以使该至少一个处理器能够基于对所存储的上下文的取回来以该区段行走该给定节点。

与该第一存储器相关的该上下文状态信息可以包括一个有效性状态，该有效性状态可以指示该第一存储器的一个有效或无效状态。

该有效状态可以指示该第一存储器存储了一个未决的上下文，而该无效状态可以指示该第一存储器没有存储未决的上下文。

所述确定(i)访问该第一存储器并且不访问该第二存储器可以是基于该有效性状态指示该无效状态，而所述确定(ii)访问该第一存储器和该第二存储器可以是基于该有效性状态指示该有效状态。

基于所述确定(i)访问该第一存储器并且不访问该第二存储器，该至少一个处理器可以进一步被配置成用于访问该第一存储器以将该上下文存储在该第一存储器中并且更新与该第一存储器相关的该上下文状态信息。

为了更新与该第一存储器相关的该上下文状态信息，该至少一个处理器可以进一步被配置成用于将包括在该上下文状态信息中的一个有效性状态从一个无效状态改变为一个有效状态以指示该第一存储器存储了一个未决的上下文。

基于所述确定(ii)访问该第一存储器和该第二存储器，该至少一个处理器可以进一步被配置成用于访问该第一存储器以取回存储在该第一存储器中的一个未决的上下文。该至少一个处理器可以被进一步配置成用于访问该第二存储器以存储所取回的未决的上下文。该至少一个处理器可以被进一步配置成用于访问该第一存储器以将该上下文存储在该第一存储器中并且保存与该第一存储器相关的该上下文状态信息。

该第一存储器可以是一个寄存器，并且该寄存器的一个第一字段可以被配置成用于存储该上下文状态信息，而该寄存器的一个第二字段可以被配置成用于存储该上下文。

对该第一存储器的第一读写访问时间可以相对于该第二存储器的第二读写访问时间更快。

该第一读写访问时间可以至少比该第二读写访问时间快三倍。

该第一存储器可以被配置成用于具有单个条目用于存储单个上下文，该第二存储器可以被配置成用于具有多个条目用于存储多个上下文，并且该第二存储器可以被保持为循环缓冲器。

该第二存储器可以被配置成用于存储用于该循环缓冲器的一个头指针，并且基于确定(ii)访问该第一存储器和该第二存储器，该至少一个处理器可以被进一步配置成用于访问该第一存储器以取回存储在该第一存储器中的一个未决的上下文、访问该第二存储器以存储基于该头指针取回的未决的上下文、访问该第一存储器以将该上下文存储在该第一存储器中、并且保存与该第一存储器相关的该上下文状态信息。

为了存储基于该头指针取回的未决的上下文，该至少一个处理器可以被进一步配置成用于更新该头指针并且将所取回的未决的上下文存储在该第二存储器的一个空的上下文条目中，该空的上下文条目通过该更新后的头指针来定址。

该确定可以是一个存储确定，并且该至少一个处理器可以被进一步配置成用于取回一个未决的上下文。该取回可以包括一个取回确定：基于与该第一存储器相关的该上下文状态信息，确定(iii)访问该第一存储器并且不访问该第二存储器或者(iv)访问该第二存储器并且不访问该第一存储器。

与该第一存储器相关的该上下文状态信息可以包括一个有效性状态，该有效性状态指示该第一存储器的一个有效或无效状态。

该有效状态可以指示该第一存储器存储了该未决的上下文，而该无效状态可以指示该第一存储器没有存储未决的上下文。

所述确定(iii)访问该第一存储器并且不访问该第二存储器可以是基于该有效性状态指示该有效状态，而所述确定(iv)访问该第二存储器并且不访问该第一存储器可以是基于该有效性状态指示该无效状态。

基于所述取回确定(iii)访问该第一存储器并且不访问该第二存储器，该至少一个处理器可以进一步被配置成用于访问该第一存储器以从该第一存储器取回该未决的上下文并且更新与该第一存储器相关的该上下文状态信息。

为了更新与该第一存储器相关的该上下文状态信息，该至少一个处理器可以进一步被配置成用于将包括在该上下文状态信息中的一个有效性状态从一个有效状态改变为一个无效状态以指示该第一存储器没有存储未决的上下文。

基于所述取回确定(iv)访问该第二存储器并且不访问该第一存储器，该至少一个处理器可以进一步被配置成用于访问该第二存储器以取回该未决的上下文并且保存与该第一存储器相关的该上下文状态信息。

该第二存储器可以被保持为一个循环缓冲器，并且可以被配置成用于存储一个头指针。为了访问该第二存储器以取回该未决的上下文，该至少一个处理器可以被进一步配置成用于基于该头指针来取回该未决的上下文。

为了基于该头指针来取回该未决的上下文，该至少一个处理器可以被进一步配置成用于从该第二存储器的通过该头指针定址的一个当前条目位置取回该未决的上下文，并且更新该头指针以定址该第二存储器的直接在该当前条目位置之后的下一条目位置。

该上下文可以包括多个字段并且该多个字段可以包括一个上下文条目类型字段，该上下文条目类型字段是基于该给定节点的多个节点类型中的一个节点类型，该上下文条目类型字段表示该多个字段中的哪些字段是与该节点类型相关的。

该上下文条目可以进一步包括一个匹配类型字段，该匹配类型字段基于该上下文条目类型字段是相关的，该匹配类型字段是基于该节点类型并且用于确定该给定节点被配置成用于在一个从网络接收的输入流中匹配一个给定元素的单个实例还是多个连续实例。

该上下文条目可以进一步包括一个元素字段，该元素字段是相关的而无论该上下文条目类型字段如何并且标识该给定元素以在该给定节点进行匹配。

该上下文条目可以进一步包括一个下一节点地址字段，该下一节点地址字段是相关的而无论该上下文条目类型字段如何、并且标识下一节点。

该上下文条目可以进一步包括一个计数字段，该计数字段基于该上下文条目类型字段是相关的并且标识一个计数值，从而基于该上下文条目类型字段，在该给定节点处指示与该给定元素肯定匹配的剩余的连续实例的数目或者已经与该给定元素肯定匹配的连续实例的数目。

该上下文条目可以进一步包括一个丢弃未探索上下文(DUP)字段，该丢弃未探索上下文字段是相关的而无论该上下文条目类型字段如何，并且在该输入流中检测到至少一个正则表达式的完全匹配的事件中标识是丢弃该上下文还是基于该上下文行走该下一节点。

该上下文条目可以进一步包括一个逆向行走方向字段，该逆向行走方向字段是相关的而无论该上下文条目类型字段如何并且标识一个逆向或正向的行走方向。

该上下文条目可以进一步包括一个偏移字段，该偏移字段是相关的而无论该上下文条目类型字段如何并且标识在该输入流中的一个有效载荷的一个区段的一个偏移，以便基于该上下文条目类型字段，在该给定节点对该给定元素进行匹配或者对该下一节点的下一元素进行匹配，该下一元素通过与该下一节点相关联的元数据来标识。

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

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

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

附图说明

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

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

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

图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是另一个NFA图形的框图，该框图可以由一个行走器使用以匹配在一个输入流中的正则表达式图样。

图8是一个有效载荷的框图以及用于以一种贪婪(greedy)非投机方式以该有效载荷遍历图7的NFA图形的处理周期的示例实施例的一个表。

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

图9B是贪婪投机型处理规则的一个表的示例实施例的框图。

图10是一种用于以投机方式处理NFA图形的方法的另一个示例实施例的一个流程图。

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

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

图13是一种用于存储用于行走给定节点的上下文的方法的示例实施例的一个流程图。

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

图15是一种用于取回用于行走给定节点的上下文的方法的示例实施例的一个流程图。

图16是可以根据在此披露的实施例进行存储或取回的上下文的示例实施例的一个框图。

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

具体实施方式

在详细描述本发明的示例实施例之前，直接在下面描述了一种示例安全应用以帮助读者理解在此披露的本发明的特征，这些实施例可以实现在该安全应用中并且典型的处理使用确定型有限自动机(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[^ ],”“.*a[^ ][^ ],”“.*a[^ ][^ ][^ ],”的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中实现一个编译器和一个行走器。

图3A是图1的安全装置102的另一个实施例的框图，其中，可以实现在此披露的实施例。如参考图1描述的，安全装置102可以操作地耦合到一个或多个网络并且可以包括存储器104和网络服务处理器100，该网络服务处理器可以包括加速单元106。参考图3A，网络服务处理器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的状态和该至少一个NFA314的状态之间转换行走器320的映射信息的元数据(未展示)。根据在此披露的实施例，所生成的每个NFA可以用于该组中的一个特定的图样，而一个统一的DFA可以基于来自该组中所有图样的所有子图样来生成。

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

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

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

如在图3A中所示，任选的限定符308可以各自与该组正则表达式图样304中的一个图样相关联。例如，任选的限定符322可以与图样316相关联。任选的限定符308可以各自是指定所希望的定制、高级PCRE签名选项、或其他对于处理与这些限定符相关的图样而言合适的选项的一个或多个限定符。编译器306可以使用选自该组一个或多个正则表达式图样304中的所有图样的子图样302来生成一个统一的DFA312。编译器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图爆。例如，包括重复多次的通配符或更大字符类的子图样(例如，[^ ]*或[^ ]{16})可能导致在DFA中过多的状态并因此可能更有利地适合于NFA。

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

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

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

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

该至少一个工作中的一个给定工作可以指示该至少一个NFA314中的一个给定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的该至少一个工作如S1 459a、S2 459b、或S3 459c可以被存储在用于由HNA 108处理的输入堆栈458中。该至少一个指令的该至少一个工作可以各自属于一个相同的给定的有效载荷，如有效载荷462，该有效载荷由HFA 110处理。

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

HNA 108可以从图形存储器456加载(即，提取)图形457，该图形可以被包括在图1和图3A的二进制图像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中的与当前工作相关联的条目，例如从输入缓冲器加载的工作，如S1 459a，并且将匹配结果(未展示)保存到匹配结果缓冲器466。替代性地，HNA 108可以继续处理运行堆栈460的与当前工作相关的条目，因为所有有可能的匹配路径可能都是有意义的。

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

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

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

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

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

在该示例实施例中，输入流可以包括一个带有有效载荷542的数据包(未展示)。正则表达式图样502是一个图样“h[^ ]*ab”，该图样指定字符“h”之后是与换行字符不匹配的无限数目的连续字符(即，[^ ]*)。该无限数目可以是零或更多。图样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生成的多个节点的图形，如节点N0 506、N1 508、N2 510、N3 512、N4 514、和N5 515。节点N0 506可以表示图样502的一个起始节点，而节点N5 515可以表示图样502的一个标记节点。标记节点N5 515可以与一个指示符相关联，该指示符反映与该输入流匹配的图样502的一个最终(即，完全或完整)的匹配。于是，行走器302可以基于遍历标记节点N5 515确定图样502在输入流中是匹配的。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

根据在此披露的实施例，匹配性能可以通过在该至少两个节点中的每个节点处并行地处理该在给定偏移处的区段来优化。并行地处理该至少两个节点在此可以被称为投机型处理。在此披露的实施例可以是基于以下假设：在至少两个节点中的一个所选节点处的匹配操作将造成失配。该至少两个节点中的所选节点在此可以被称为元素节点。该至少两个节点中的未被选择的节点(将会基于在所选节点处的失配而被遍历)在此可以被称为并行节点，并且可以在与所选节点处理的相同区段的同一个处理周期中投机式地处理，以改进匹配性能。如下面参考图5D描述的，节点N2 510和节点N3 512两者可以用在给定偏移520b处的区段“x”处理，从而在与在节点N2 510处行走在给定偏移520b处的区段“x”的同一个处理周期中，通过投机式地在节点N3 512处行走在偏移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中的一个给定偏移处的一个给定的区段并行地处理节点N2 510和节点N3 512，从而使用图5C中披露的懒惰投机处理规则来优化匹配性能。例如，如下文所披露的，处理周期554c和554d可以基于N2 510和节点N3 512的匹配结果的集合来确定行走器行动536'。

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

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

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

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

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

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

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

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

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

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

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

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

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

与懒惰型可变计数节点N1N3'607相关联的元数据609可以包括一个用于追踪在有效载荷中肯定匹配的元素611的连续实例总数(未展示)的计数(未展示)，以允许该总数与可变数目613的比较。替代性地，该计数可以初始地被配置成用于指示该可变数目613，并且可以对于每个连续肯定匹配减小，使得该计数反映剩余的肯定匹配实例的数目。

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

图6B是用于以一种懒惰非投机方式以有效载荷542遍历图6A的NFA图形604的处理周期628a-g的示例实施例的一个表618。类似于上面披露的图5A和图5B的实施例，行走器320可以用在当前偏移520a(即，“0”)处的区段522a(即，“h”)来行走起始节点N0 606。当区段522a匹配在节点N0 606处的字符“h”时，行走器320可以确定对于处理周期628a该匹配结果624是肯定匹配结果。在图6A的实施例中，由节点N0 606指示的下一节点是懒惰型可变计数节点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，例如，如果该否定匹配结果是在节点N2 610处或沿从节点N2 610延伸的路径上的节点处确定的。为了存储该未探索的上下文，行走器320可以将一个条目推送630a到运行堆栈460，该条目包括一个用于懒惰型可变计数节点N1N3'607和偏移520b的标识符。

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

根据图6B的示例实施例，行走器320可以提取节点N2 610并且可以尝试将处理周期628c中的当前偏移520b(即，“1”)处的区段522b(即，“x”)与节点N2 610的元素“a”进行匹配(即，搜索)。因为“x”并不匹配节点N2 610处的元素“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并且转换回到元素节点N2 610，该节点可以是由与懒惰型可变计数节点N1N3'607相关联的元数据609指示的下一节点。

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

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

如在图6B的表618中所示，用于将有效载荷542与图样502进行匹配的处理周期数目是七个，并且行走器320推送630a并弹出630b了未探索的上下文以便记住并用在偏移520b处的区段“x”返回到懒惰型可变计数节点N1N3'607两次。于是，表618还展示出区段“x”由行走器320在懒惰型可变计数节点N1N3'607和节点N2 610两者处进行处理(即，消耗)，并且在节点N2 610处是失配(即，否定匹配)而在懒惰型可变计数节点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和元素节点N2 610，从而使用上面参考图5C披露的懒惰投机处理规则来优化匹配性能。

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

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

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

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

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

对于区段522d的肯定匹配结果(即，“b”)可以对于处理周期658d在节点N4 614处确定，并且行走器320可以转换到标记节点N5 615，该标记节点可以在与节点N4 614相关联的元数据中指定为节点N4 614的下一节点。因为节点N5 615是一个标记节点，行走器可以将最终匹配结果存储到匹配结果缓冲器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确定在元素节点N2 610处的一个失配区段，从而导致行走器320在元素节点N2 610与并行节点607之间的搅动。在节点之间这样的搅动造成行走器320以性能为代价来提取并行节点607和元素节点N2 610，原因是相应的存储器访问需要附加的处理器周期。这样的存储器访问可能昂贵的，尤其是因为这些存储器可以是纠错码(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(在该示例实施例中为并行节点)和节点N2 610(在该示例实施例中为元素节点)，从而使用上面参考图5C披露的懒惰投机处理规则来优化匹配性能。

如以上所披露的，可变计数节点是可以将一个元素匹配可变次数的节点，该次数可以是由一个范围限定的(例如，零到五次)并且可以与一种节点类型相关，如懒惰型或贪婪型。与可以被配置成用于在该范围内找到一个最短的可能元素匹配的具有贪婪节点类型的可变计数节点(即，贪婪型可变计数节点)不同，具有贪婪节点类型的可变计数节点(即，贪婪型可变计数节点)可以被配置成用于在该范围内找到最长的可能元素匹配。例如，如以上所披露的，行走器320可以被配置成用于选择该上方ε路径530a以在该范围内找到最短的可能元素匹配。然而，为了在该范围内找到最长的可能匹配，行走器320可以被配置成用于选择下方ε路径530b，因为下方ε路径530b表示一个贪婪型路径。

编译器306可以被配置成用于生成分离节点元数据，该元数据可以使行走器320能够选择该下方ε路径530b以进行该贪婪型路径的选择。于是，行走器320可以在分离节点508与投机节点N3 512之间迭代地转换，以处理来自输入流的连续区段，只要这些连续区段中的每一个都在投机节点N3 512处肯定匹配。基于这些连续区段中的一个给定区段的否定匹配，行走器320可以经由上ε路径530a转换到元素节点N2 510，因为贪婪路径可以被配置成用于处理来自有效载荷的连续区段直到确定一个区段失配。

图7是另一个NFA图形704的框图700，该框图可以由一个行走器320使用以匹配在输入流中的正则表达式图样502。在该示例实施例中，图5A的区域507(包括分离节点N1 508、投机节点N3 512、和ε转换路径530a和530b)用一个可变计数节点N1N3'707表示。与图6A的懒惰可变计数节点N1N3'607不同，可变计数节点N1N3'707在该示例实施例中是一个贪婪型可变计数节点。将节点N1N3'707标识为贪婪型可变计数节点的节点类型719可以包括在与节点N1N3'707相关联的元数据709中。

贪婪型可变计数节点N1N3'707可以被配置成用于处理在贪婪型可变计数节点N1N3'707处的连续区段，直到确定一个区段失配(即，否定匹配)或者直到该贪婪型可变计数节点已经处理了一个阈值数目的肯定匹配连续区段。该阈值数目可以是与贪婪型可变计数节点N1N3'707相关联的值范围的上限值。

根据在此披露的实施例，贪婪型可变计数节点N1N3'707可以被配置成用于标识一个给定元素，如字符类711(即，[^ ])，可变实例数目713，如由与贪婪型可变计数节点N1N3'707相关联的元数据709所指示的。可变实例数目713可以是至少零次或任何其他合适的例数目，如在该示例实施例中为无限的。应当理解的是，给定的字符类元素711和可变实例数目713是用于说明该示例实施例的目的并且该给定元素可以是通过贪婪型可变计数节点N1N3'707匹配该可变次数713的任何合适的元素。

在图7的示例实施例中，与贪婪型可变计数节点N1N3'707相关联的元数据709直接或间接地标识下一节点717，如元素节点N2 710。在该示例实施例中，基于在该输入流中已经肯定匹配元素711、可变实例数目713或者基于区段失配，行走器320可以将行走转换到元素节点N2 710。例如，在该示例实施例中，贪婪型可变计数节点N1N3'707被配置成用于匹配在输入流中的该字符类元素“^ ”(即，不是换行字符)无限数目的连续实例。与贪婪型可变计数节点N1N3'707相关联的元数据709可以包括一个用于追踪在有效载荷中肯定匹配的元素711的连续实例总数的计数值(未展示)，以允许该总数与可变数目713的比较。因为可变数目713在该示例实施例中是无限的，行走器320可以行进以在贪婪型可变计数节点N1N3'707处理来自输入流的连续区段直到处理一个换行字符。任选地，指示在贪婪型可变计数节点N1N3'707处的一个最早的肯定匹配区段的一个起始偏移(未展示)也可以被包括在与贪婪型可变计数节点N1N3'707相关联的元数据709中并且与该计数值结合使用以确定该有效载荷中的当前偏移。

图8是一个有效载荷842的框图800以及用于以一种贪婪非投机方式以有效载荷842遍历图7的NFA图形704的处理周期828a-n的示例实施例的一个表818。行走器320可以用在当前偏移820a(即，“0”)处的区段822a(即，“h”)来行走起始节点N0 706。当区段822a匹配在节点N0 706处的字符“h”时，行走器320可以确定对于处理周期828a该匹配结果810是肯定匹配结果。在图7的实施例中，由节点N0 706指示的下一节点是贪婪型可变计数节点N1N3'707。于是，行走器320可以采取处理周期828a的行动812，该行动包括将有效载荷842中的当前偏移更新到820b(即，“1”)并且转换到贪婪型可变计数节点N1N3'707，该节点是N0706的下一节点。

因为贪婪型可变计数节点N1N3'707是一个贪婪型节点，所以处理周期828b-h的行动812可以包括在处理周期828b-h中的每一个中增大包括在与贪婪型可变计数节点N1N3'707相关联的元数据709中的一个计数值，以追踪在贪婪型可变计数节点N1N3'707已经肯定匹配的连续区段总数。处理周期828b-h的行动812可以进一步包括将当前偏移更新到区段偏移818中的下一个区段偏移，以处理区段816中的下一个区段，如处理周期828b-h所示。可以重复这样的增大该计数值并更新当前偏移，直到确定在当前偏移808处的有效载荷区段的失配，如对于处理周期828i所示的情况。

如在表818中所示，在当前偏移820i处的区段822i否定匹配在处理周期828i的贪婪型可变计数节点N1N3'707处。根据在此披露的实施例，未探索的上下文(如贪婪型可变计数节点N1N3'707的下一节点N2 710的一个标识符)可以与贪婪型可变计数节点N1N3'707的计数值和DUP指示符(可以被设定为一)相结合地存储。

基于处理周期828i的否定匹配结果810，行走器可以或直接或间接地通过与贪婪型可变计数节点N1N3'707相关联的元数据709提取所指示的下一节点，并且转换到节点N2 710以便用在贪婪型可变计数节点N1N3'707处具有否定匹配的区段820i来行走节点N2 710，以努力找到最长的可能匹配。

如对于处理周期828j所示的，区段820i具有一个匹配结果810，该匹配结果在节点N2 710处是否定，因为区段“ ”不匹配元素节点N2 710的元素“a”。于是，行走器320可以行进以渐增地展开在贪婪型可变计数节点N1N3'707处先前已经肯定匹配的连续区段。例如，行走器320可以展开区段820h...820b，以努力确定在贪婪型可变计数节点N1N3'707处已经肯定匹配的、还在下一节点N2 710处匹配的一个最近行走过的区段，以努力找到最长的可能匹配。展开行动可以包括弹出存储的上下文，该上下文标识该元素节点和在区段失配之前在可变计数节点处匹配的肯定匹配连续区段的数目的一个计数。展开行动可以包括将计数减小，并且推送标识该元素节点并包括该渐减的计数的所存储上下文。展开行动可以进一步包括更新当前偏移并且提取元素节点。

如处理周期828k所示，区段820h在元素节点N2 710否定匹配，并且行走器320采取所展示的行动812，类似于处理周期828j的展开行动830，并由此行进到通过确定区段820g是否在元素节点N2 710处匹配来展开，如对于处理周期828l所示的。因为区段820g(即，“a”)在元素节点N2 710处肯定匹配，行走器320可以更新当前偏移并且提取可以经由与元素节点N2 710相关联的元数据标识的下一节点N4714。区段820h可以在节点N4 714处肯定匹配，如对于处理周期828m所示的，并且行走器320可以更新当前偏移并且提取可以经由与元素节点N4 714相关联的元数据标识的下一节点N5 715。

节点N5 715是与一个指示符相关联的标记节点，该指示符表示与该输入流中的正则表达式图样842的一个最终(即，完全或完整)的匹配。由此，对于处理周期828n，行走器320可以不继续行走并且通过在匹配结果缓冲器466中存储一个条目来报告该最终匹配。行走器然后可以对运行堆栈460检查存储线程并且如由在运行堆栈460中这些条目的相应的DUP指示符所指示的那样要么丢弃所存储的线程要么激活它们。

基于有效载荷842区段内容，可以增加用于展开的处理周期的数目。如所示的，对于每个展开周期828j和828k的行动812包括弹出并推送可以如上披露的高成本操作的上下文。根据在此披露的实施例，匹配性能可以通过减少匹配所需的处理周期数目、以及通过减少存储和取回上下文的推送和弹出操作的次数而减少访问存储器的次数来改进。根据在此披露的实施例，匹配性能可以通过以投机方式行走来改进。例如，行走器320可以投机方式行走NFA图形704。如以上所披露的，并行地处理至少两个节点在此可以被称为投机型处理。根据在此披露的实施例，基于贪婪型路径处理的匹配性能可以通过如下披露的投机处理来优化。

图9A是一种方法的示例实施例的一个流程图900，该方法可以被实现在至少一个处理器中，该处理器与操作地耦合到网络的一个安全装置中的至少一个存储器操作地耦合。该方法可以开始(902)并在至少一个存储器中存储包括从至少一个正则表达式图样生成的多个节点的至少一个有限自动机，并且将该至少一个存储器操作地耦合到至少一个处理器(904)。该至少一个处理器可以被配置成用于用一个输入流的多个区段行走该至少一个有限自动机以在该输入流中匹配该至少一个正则表达式图样，该输入流经由一个操作地耦合到网络的硬件网络接口接收。该行走可以包括在一个有效载荷之内的当前偏移处用输入流中的数据包的一个区段并行地迭代行走该至少一个有限自动机中的一个给定有限自动机的至少两个节点，基于该区段在并行行走的该至少两个节点中的一个给定节点处的肯定匹配，当前偏移每次迭代被更新为下一个偏移(906)。在该示例实施例中，该方法随后结束(908)。

图9B是贪婪投机型处理规则978a-d的一个表970的示例实施例的框图。表970是一个带有行动976的真值表，这些行动是基于元素节点匹配结果974和贪婪型可变计数节点匹配结果972。根据贪婪投机处理规则978a-d，展示了四个可能的情况。例如，贪婪投机处理规则978a、978b、978c和978d各自具有一个对应的后续行动976，基于匹配结果分别为肯定/肯定、肯定/否定、否定/肯定、和否定/否定。

贪婪投机处理规则978a和978b使得贪婪型可变计数节点和元素节点能够基于在贪婪型可变计数节点处的肯定匹配并行地迭代在一个有效载荷之内的当前偏移处处理一个区段，从而免除用于节点提取的存储器访问。此外，贪婪投机处理规则978a包括如相应的行动976所示的那样存储上下文。贪婪投机处理规则978a包括基于在有效载荷中当前偏移处该区段在该给定节点和元素节点处的肯定匹配来存储一个标识下一偏移和和给定有限自动机的下一节点的上下文。元素节点是与标识该元素节点和下一节点的元数据相关联的。

基于一个区段在贪婪型可变计数节点和元素节点两者的肯定匹配来存储上下文使得行走器320能够记载区段偏移和节点信息，以免除展开，如上面参考图8披露的展开行动830。存储上下文可以包括与更新后的当前偏移(即，下一偏移)相结合推送经由与元素节点相关联的元数据来标识的下一节点的地址或其他标识符。

如通过贪婪投机处理规则978c所示，不继续并行地迭代行走该元素节点和贪婪型可变计数节点，并且更新当前偏移。该下一节点可以被提取并且行走器可以用在更新后的当前偏移处的下一区段行走该下一节点。于是，贪婪投机处理规则978c可以包括不继续迭代行走、将当前偏移更新到下一偏移、并用在有效载荷中的下一偏移处的下一区段行走该下一节点。

如通过贪婪投机处理规则978d所示，基于贪婪型可变计数节点972和元素节点974的匹配结果均为否定，行动976可以包括不继续行走一个给定的路径。于是，可以基于感测未探索的上下文来行走在有效载荷之内的下一给定偏移处的下一区段，如通过对运行堆栈460检查存储的线程并且如果已存储则将所存储的线程弹出。替代性地，该行走可以基于没有感测到未探索的上下文或如果所有存储线程基于相应的丢弃未探索处理(DUP)指示符都被标记为丢弃而被终止。于是，贪婪投机处理规则978d可以指定包括不继续迭代行走的至少一个后续行动，并且从运行堆栈460弹出一个堆栈条目。基于运行堆栈460的非空状态，为最近被推送到堆栈上的条目的一个堆栈条目可以被弹出，并且行走可以基于所弹出的堆栈条目用下一区段前进到下一节点。否则，基于运行堆栈460的空状态，行走可以被终止。

图10是一种用于以投机方式处理NFA图形的方法的另一个示例实施例的一个流程图1000。该方法可以开始(1002)并且提取一个贪婪型可变计数(VCG)节点(1004)。该方法可以检查所提取的VCG节点是否为一个投机节点(1006)。行走器320可以基于包括在与VCG节点相关联的元数据中的一个投机处理指示符来确定该VCG节点为投机型。如果该VCG节点不是投机型，那么在该示例实施例中该方法结束(1032)。

如果该VCG节点是投机型的，该方法可以提取一个元素节点(1008)。所提取的元素节点可以是经由与VCG节点相关联的元数据来标识的下一节点。该方法可以在VCG节点和元素节点两者处理在当前偏移处的区段(1010)。该VCG节点可以被配置成用于匹配有效载荷中的一个第一元素的可变连续实例数目，并且该元素节点可以被配置成用于匹配有效载荷中的一个第二元素的单个实例。

该方法可以检查在当前偏移处的区段是否在VCG节点肯定匹配(1012)。检查在当前偏移处的区段是否在VCG节点肯定匹配可以包括确定该区段肯定匹配经由与VCG节点相关联的元数据标识的第一元素并且确定已经在VCG节点肯定匹配的连续区段的计数值尚未超过一个给定的阈值。如果在当前偏移处的区段肯定匹配该VCG节点，包括在与VCG节点相关联的元数据中的计数值可以被增大(1014)。

该方法可以检查在当前偏移处的区段是否在元素节点肯定匹配(1016)。检查在当前偏移处的区段是否在元素节点肯定匹配可以包括确定该区段肯定匹配经由与元素节点相关联的元数据标识的第二元素。应当理解的是，在VCG节点和元素节点的肯定匹配的这种确定并行地发生，由于在当前偏移处的区段是在这两个节点处并行处理的。VCG节点和元素节点可以用在有效载荷之内当前偏移处的区段在该至少一个处理器的同一个处理周期之内并行地行走。

如果在当前偏移处的区段在元素节点处肯定匹配，该当前偏移可以被更新到下一偏移(1018)并且上下文可以被存储(1020)。存储上下文可以包括与下一偏移相结合地推送经由元素节点的元数据来标识的下一节点的地址或其他标识符。该方法可以行进到通过返回到在VCG节点和元素节点两者处理在当前偏移的区段在下一次迭代中在VCG和元素节点两者处理在当前偏移处的区段(1010)。

然而，如果在元素节点没有确定在当前偏移处的区段的肯定匹配(1016)，该方法可以将当前偏移更新到下一偏移(1034)，并且该方法可以行进到通过返回到在VCG节点和元素节点两者处理在当前偏移的区段在下一次迭代中在VCG和元素节点两者处理在下一偏移处的区段(1010)。于是，行走可以包括基于该区段在VCG节点的肯定匹配用在有效载荷之内的当前偏移处的一个区段并行地行走VCG节点和元素节点。当前偏移对每次迭代可以被更新到下一偏移，如通过(1018)和(1034)所示的。

然而，如果在VCG节点没有确定在当前偏移处的区段的肯定匹配(1012)，该方法可以不继续迭代行走，并且该方法可以确定该在当前偏移处的区段是否在元素节点处肯定匹配(1022)。如果不匹配，该方法可以基于所存储的上下文进行转换(1030)并且在该示例实施例中该方法结束(1032)。

然而，如果在元素节点确定在当前偏移处的区段的肯定匹配(1022)，该方法可以将当前偏移更新到下一偏移(1024)。该方法可以在下一节点处理在下一偏移处的区段(1028)，并且在该示例实施例中该方法随后结束(1032)。

图11是用于以一种贪婪投机方式以图8的有效载荷842遍历图7的NFA图形704的处理周期1158a-k的示例实施例的一个表1148。如在表1148中所示的，处理周期1158a-k可以包括在当前偏移1152用来自有效载荷842的一个区段遍历一个当前节点1150以确定一个匹配结果1154并基于匹配结果1154确定后续行动1156。根据在此披露的实施例，行走器320可以用有效载荷842中的一个给定偏移处的一个给定的区段并行地处理贪婪型可变计数节点N1N3'707和元素节点N2 710，从而使用上面参考图9B披露的贪婪投机处理规则来优化匹配性能。贪婪型可变计数节点N1N3'707和元素节点N2 710可以用在有效载荷之内当前偏移处的区段在该至少一个处理器的同一个处理周期之内并行地行走。

根据在此披露的实施例，与贪婪型可变计数节点相关联的元数据可以包括一个投机处理指示符。根据在此披露的实施例，如果该投机处理指示符没有被包括在与贪婪型可变计数节点N1N3'707相关联的元数据709中，行走器320可以如在图8的示例实施例中一样继续。包括该投机处理指示符可以是以任何使得行走器320能够用在有效载荷中当前偏移处的区段并行地行走贪婪型可变计数节点和元素节点的方式进行的。

根据图11的示例实施例，行走器320可以用在当前偏移820a(即，“0”)处的区段822a(即，“h”)来行走起始节点N0 706。当区段822a匹配在节点N0 706处的字符“h”时，行走器320可以确定对于处理周期1158a该匹配结果1154是肯定匹配结果。在图11的实施例中，由节点N0 706指示的下一节点是贪婪型可变计数节点N1N3'707。于是，行走器320可以采取处理周期1158a的行动1156，该行动包括将有效载荷842中的当前偏移更新到820b(即，“1”)并且提取与节点N0 706的元数据相关联的下一节点，该节点是贪婪型可变计数节点N1N3'707。

根据图11的示例实施例，与贪婪型可变计数节点N1N3'707相关联的元数据709包括该投机处理指示符(未展示)，如对于处理周期1158a所检测到的。于是，行动1156包括提取经由元数据709标识的下一节点，该节点是元素节点N2 710，并且转换到贪婪型可变计数节点N1N3'707和元素节点N2 710两者，以便用在有效载荷842中当前偏移820b(即，“1”)处的区段行走这两个节点。

如对于处理周期1158b所示的，行走器320可以确定对于在元素节点N2 710处对于区段822b(即，“x”)的否定匹配结果和在贪婪型可变计数节点N1N3'707处的肯定匹配结果。这样的匹配结果映射到贪婪投机处理规则条目978b。于是，基于在贪婪型可变计数节点N1N3'707处的肯定匹配结果，行动976指定将当前偏移更新并且使元素和贪婪型可变计数节点(如节点N2 710和N1N3'707)分别被再次处理(即，行走)。由于节点N2 710和N1N3'707已经被提取用于处理周期1158b，所以对于处理周期1158c不需要提取节点。包括在元数据709中的计数值(未展示)可以基于在贪婪型可变计数节点N1N3'707处的肯定匹配结果1154增大到1并且当前偏移可以被更新到2。

如对于处理周期1158c所示的，行走器320用在有效载荷842中的更新后的偏移(为偏移820c(即，“2”))处的区段822c(即，“x”)来行走元素节点N2 710和贪婪型可变计数节点N1N3'707。匹配结果1154在元素节点N2 710为否定而在贪婪型可变计数节点N1N3'707为肯定，因为区段“x”不匹配在元素节点N2 710的元素“a”但是匹配在贪婪型可变计数节点N1N3'707处的“^ ”元素，因为“x”不是换行字符。匹配结果1154再次映射到贪婪投机处理规则条目978b。于是，基于在贪婪型可变计数节点N1N3'707处的肯定匹配结果，行动976指定将当前偏移更新并且使元素和贪婪型可变计数节点(如节点N2710和N1N3'707)分别被再次处理(即，行走)。计数值可以基于在贪婪型可变计数节点N1N3'707处的肯定匹配结果1154增大到2并且当前偏移可以被增大到3。

如对于处理周期1158d所示的，行走器320用在有效载荷842中的当前偏移(为偏移820d(即，“3”))处的区段822c(即，“x”)来行走元素节点N2 710和贪婪型可变计数节点N1N3'707。匹配结果1154再次在元素节点N2 710为否定而在贪婪型可变计数节点N1N3'707为肯定，并且由此，行动1156类似于上面披露的处理周期1158b和1158c。

如对于处理周期1158e所示的，行走器320用在有效载荷842中的当前偏移(为偏移820d(即，“4”))处的区段822e(即，“a”)来行走元素节点N2 710和贪婪型可变计数节点N1N3'707。匹配结果1154在元素节点N2 710和贪婪型可变计数节点N1N3'707均为肯定。匹配结果1154映射到贪婪投机处理规则条目978a。由此，除了增大计数值并更新当前偏移之外，行动1156进一步包括存储未探索的上下文，该未探索的上下文包括推送一个标识节点N4 714的堆栈条目，该节点是经由与元素节点N2 710相关联的元数据标识的下一节点并且当前偏移现在是5。于是，如果一个后续周期确定在贪婪型可变计数节点N1N3'707处的一个区段失配，行走器320可以用在当前偏移5处的区段822f行走节点N4 714，从而免除了展开以找到元素节点N2 710和贪婪型可变计数节点N1N3'707肯定匹配同一个区段处的偏移。

如对于处理周期1158f、1158g、和1158h所示的，行走器320基于在贪婪型可变计数节点N1N3'707处的肯定匹配结果1154继续元素节点N2 710和贪婪型可变计数节点N1N3'707的迭代行走。然而，如对于处理周期1158g所示的，类似于上面披露的处理周期1158e，未探索的上下文可以被存储以使行走器能够用对应于偏移822h(对应于偏移7，为在连续处理周期1158h中使用的更新后的当前偏移)的区段返回到节点N4 714，该节点是经由与元素节点N2 710相关联的元数据标识的下一节点。

如对于处理周期1158i所示的，行走器320可以确定对于在元素节点N2 710处对于区段822i(即，“ ”)的否定匹配结果和在贪婪型可变计数节点N1N3'707处的否定匹配结果。这样的匹配结果映射到贪婪投机处理规则条目978d。于是，元素节点N2 710和贪婪型可变计数节点N1N3'707的迭代行走不继续，因为在贪婪型可变计数节点N1N3'707的匹配结果1154为否定。行走器320可以对堆栈检查所存储的条目，并且如果堆栈为非空，最近推送的条目可以被弹出。于是，对于处理周期1158g推送的条目可以被弹出以使行走器能够提取节点N4714并用在偏移820h处的区段822h转换到节点N4 714。

如对于处理周期1158j所示的，在经由对于处理周期1158h弹出的堆栈条目标识的偏移820h处的区段822h(即，“b”)在节点N4 714肯定匹配。由此，行走器320将当前偏移更新到820i并且提取节点N5715，该节点是经由与节点N4 714相关联的元数据标识的下一节点。

因为节点N5 715是一个标记节点，行走器可以将最终匹配结果存储到匹配结果缓冲器466并且不继续行走该活动线程(例如，当前路径)。行走器320可以对运行堆栈460检查一个空状态。在该示例实施例中，运行堆栈460不是空的，因为未探索的上下文在处理周期1158e中被推送到运行堆栈460中。于是，行走器320可以弹出未探索的上下文，该上下文指示用在偏移820f(即，“5”)处的区段822f(即，“b”)使行走前进到节点N4 714，并且可以基于与该堆栈条目相关的DUP指示符来确定是丢弃未探索的上下文还是处理未探索的上下文。

根据在此披露的实施例，更新当前偏移可以包括基于行走的正向或逆向方向分别增大或减小当前偏移。于是，当前偏移的增大或减小是用于根据该示例的行走方向进行说明的目的。

如在该示例实施例的表1148中所示，使用贪婪投机处理将有效载荷842与图样502匹配的处理周期数目是十一个，与在图8的贪婪非投机处理示例实施例中使用的十四个处理周期相比这个数目更少。应当理解的是，这样的基于如以上所披露的示例实施例所示的贪婪投机处理的性能增加是用于说明的目的并且通过使用贪婪投机处理实现的性能增益可以比所说明的那些更大。例如，此类性能增益可以取决于输入有效载荷而增加。基于输入流的内容，进一步的展开(如对于图8的处理周期828j和828k的展开)可以是对于不同的有效载荷更普遍的，从而造成更大的性能增益。

根据在此披露的实施例，以投机方式行走该给定的NFA可以减少对运行堆栈460的推送或弹出操作的数目，由此优化匹配性能。如以上所披露的，此类的推送或弹出操作可以是昂贵的存储器访问，例如运行堆栈460可以是一个ECC保护类型的存储器。访问ECC受保护的存储器以进行推送或弹出操作可能花费四个时钟周期或更长。除了减少推送或弹出操作的数目，如以上所披露的，在此匹配的实施例可以通过如下面披露地采用补充存储器，进一步优化匹配性能。

参考回图4，在此披露的实施例可以采用补充存储器470以改进匹配性能。补充存储器470可以是一个第一存储器，该第一存储器操作地耦合到一个第二存储器，如运行堆栈460。HNA 108可以操作地耦合到补充存储器470和运行堆栈460。补充存储器470可以被配置成用于存储一个上下文，如一个堆栈条目(在此也被可互换地称为上下文或未探索的上下文)，该堆栈条目可以通过HNA 108推送以行走至少一个有限自动机中的一个给定有限自动机的多个节点中的一个给定节点。例如，如上面相对于图5A-图11所披露的，上下文可以被推送或弹出以行走该给定节点。该上下文可以标识该给定节点和从网络接收的一个输入流的有效载荷中的一个区段的偏移。该上下文可以使HNA 108能够用经由该偏移标识的区段来行走经由该上下文标识的给定节点。

根据在此披露的实施例，补充存储器470可以是与上下文状态信息472相关联的，该信息可以包括一个有效性状态(在此可交换地称为一个有效性指示符)。该有效性状态可以指示对于补充存储器470的有效或无效状态。有效状态可以指示补充存储器470具有一个未决的所存储的上下文。该未决的上下文可以是尚未由HNA 108处理的所存储的上下文。

该无效状态可以指示补充存储器470不具有存储的未决的上下文，例如，存储到补充存储器460的任何条目已经由HNA 108弹出，以便用一个区段行走一个给定节点或否则由HNA 108丢弃。于是，上下文状态信息472可以由HNA 108使用以辨别补充存储器470是否具有未决的上下文。

根据在此披露的实施例，该有效性状态可以作为补充存储器470的一个位、作为补充存储器470的一个多位字段、作为与补充存储器470分离地存储的一个指示符来实现，或者以传达关于补充存储器470寄存器是否存储有未决上下文的任何其他适合形式实现。

补充存储器470在此可以可交换地称为栈顶(TOS)存储器470、TOS寄存器470或TOS 470。如上面所披露的，HNA 108可以采用运行堆栈460以保持上下文，如在行走NFA图形的节点的过程中NFA图形的节点的状态。根据在此披露的实施例，TOS 470寄存器具有比运行堆栈460更快的访问(即，读/写)时间。与ECC保护存储器(一个推送或弹出操作可能花费三个、四个、或更多个时钟周期)不同，如果在TOS寄存器470上执行，该推送或弹出操作可能花费一个时钟周期。

如以上所披露的，处理有限自动机可以包括懒惰或贪婪型处理，该处理可以容易地包括连续的推送/弹出操作。根据在此披露的实施例，TOS寄存器470可以将一个最近推送的堆栈条目保持与较早推送的条目分开，这些较早推送的条目可以经由TOS寄存器470推送到运行堆栈460。将最近推送的条目保持在TOS寄存器470中可以改进行走性能，因为该最近推送的条目可以是一个最频繁访问的条目，也就是，该最近推送的条目有可能在推送另一个条目之前被弹出。

该最近推送的条目可以被频繁地操纵，例如，在贪婪处理过程中，如以上所披露的，由此可以将一个给定的上下文推送、弹出、修改并再次推送。根据在此披露的实施例，此类连续的推送/弹出操作可以经由TOS寄存器470、而不是运行堆栈460进行，由此优化匹配性能。根据在此披露的实施例，TOS寄存器470可以是一个第一存储器并且运行堆栈460可以是一个与该第一存储器操作地耦合的第二存储器。

图12是另一种方法的示例实施例的一个流程图1200，该方法可以被实现在至少一个处理器中，该处理器与操作地耦合到网络的一个安全装置中的至少一个存储器操作地耦合。该方法开始(1202)并且可以操作地耦合一个第一存储器和一个第二存储器(1204)。该方法可以将至少一个处理器操作地耦合到该第一存储器和该第二存储器(1206)。该方法可以存储一个上下文，该上下文用于行走至少一个有限自动机中的一个给定有限自动机的多个节点中的一个给定节点。该存储可以包括基于与该第一存储器相关的该上下文状态信息来确定(i)访问该第一存储器并且不访问该第二存储器还是(ii)访问该第一存储器和该第二存储器(1208)。在该示例实施例中该方法随后结束(1210)。

参考回图4，根据在此披露的实施例，在HNA 108推送474一个第一上下文(即，一个堆栈条目)(未展示)的事件中，可以检查该上下文状态信息472指示TOS 470寄存器的一个有效还是无效状态。如果上下文状态信息472指示无效状态，则在此披露的实施例可以选择TOS寄存器470用于存储该第一上下文而非选择运行堆栈460用于存储该第一上下文，并且上下文状态信息472可以基于将该第一上下文存储到TOS 470寄存器而被更新以指示有效状态。

然而，在HNA 108推送474该第一上下文并且该上下文状态信息472反映有效状态的事件中，一个未决上下文如一个第二上下文应被理解为是存储在TOS 470寄存器中。基于推送该第一上下文和由上下文状态信息472指示的TOS 470寄存器的有效状态，由TOS 470寄存器存储的第二上下文可以被推送476到运行堆栈460。在该第二上下文被推送到运行堆栈460之后，该第一上下文可以被推送到TOS 470寄存器。由于TOS 470寄存器继续存储未决的上下文，上下文状态信息472可以通过HNA 108保存以继续反映TOS 470寄存器的有效状态。

于是，如通过推送该第一上下文来存储上下文可以包括一个存储确定：基于与TOS 470寄存器相关联的上下文状态信息472，确定访问该TOS 470寄存器而不访问运行堆栈460、或者访问TOS 470寄存器和运行堆栈460。访问TOS寄存器470而不访问运行堆栈460的存储确定可以是基于上下文状态信息472指示TOS寄存器470的无效状态。访问TOS寄存器470和运行堆栈460的存储确定可以是基于上下文状态信息472指示TOS寄存器470的有效状态。

图13是一种用于存储用于行走给定节点的上下文的方法的示例实施例的一个流程图1300。该方法开始(1302)并且检查与一个第一存储器相关联的一个有效性状态指示一个有效状态还是一个无效状态(1304)。如果该有效性状态指示无效状态，可以确定访问该第一存储器而不访问一个第二存储器(1316)，并且该方法可以访问该第一存储器以将该上下文存储在第一存储器中(1318)。该方法可以更新与该第一存储器相关联的该上下文状态信息，例如，通过将有效性状态从无效状态改变到有效状态以指示该第一存储器现在存储有一个未决的上下文(1320)，并且在该示例实施例中，该方法随后结束(1322)。

然而，如果有效性状态的检查(1304)指示有效状态，则该确定可以是访问该第一存储器和该第二存储器(1306)。该方法可以访问该第一存储器以取回存储在该第一存储器中的一个未决的上下文(1308)并且访问该第二存储器以存储所取回的未决的上下文(1310)。该方法可以访问该第一存储器以将该上下文存储在该第一存储器中(1312)并且可以保存与该第一存储器相关联的该上下文状态信息(1314)，因为该第一存储器继续存储一个未决的上下文。在该示例实施例中，该方法随后结束(1322)。

根据在此披露的实施例，TOS堆栈470可以被配置有单个条目用于存储单个上下文，并且运行堆栈460可以被配置有多个条目用于存储多个上下文。运行堆栈460可以被保持为循环缓冲器，如可以具有一个相应的头指针482和尾指针484的图4的循环缓冲器481。运行堆栈460可以被配置成用于存储头指针482和尾指针484。访问运行堆栈460以存储一个堆栈条目(即，上下文)可以是基于头指针482。

例如，为了存储该上下文或推送该上下文，HNA 108可以被配置成用于更新头指针482并将该堆栈条目存储在运行堆栈460的一个空的上下文条目中，因为空的上下文条目可以通过更新后的头指针来定址。为了取回或弹出一个堆栈条目(即，上下文)，HNA 108可以被配置成用于从一个通过头指针482定址的当前条目位置取回该堆栈条目。例如，HNA 108可以通过增大头指针来更新头指针482以便直接在当前条目位置之后定址该第二存储器的下一条目位置。替代性地，HNA 108可以通过减小头指针来更新头指针482以便直接在当前条目位置之前定址该第二存储器的下一条目位置。

于是，运行堆栈460的定址可以从上一指针增加到下一指针，即，为了弹出一个堆栈条目，HNA 108可以在头指针处读取该堆栈条目并将该头指针增大以指向下一堆栈条目，而为了推送一个堆栈条目，HNA 108可以减小头指针并且在减小后的头指针所指的位置添加该堆栈条目。替代性地，运行堆栈460的定址可以从当前指针减少到上一指针，即，为了弹出一个堆栈条目，HNA 108可以在头指针处读取该堆栈条目并将该头指针减小以指向前一堆栈条目，而为了推送一个堆栈条目，HNA 108可以增大头指针并且在增大后的头指针所指的位置添加该堆栈条目。

在HNA 108弹出上下文(即，一个堆栈条目)的事件中，例如，为了取回一个所存储的上下文，可以检查上下文状态信息472指示TOS 470寄存器的有效还是无效状态。如果上下文状态信息472指示有效状态，一个最近推送的上下文可以从TOS寄存器470弹出478并且上下文状态信息472可以被更新以指示TOS寄存器470的现在无效的状态，因为TOS寄存器470不再存储未决的上下文。

然而，如果该检查确定上下文状态信息472指示无效状态，则未决的上下文替代地可以被从运行堆栈460弹出480(即，取回)。根据在此披露的实施例，基于与TOS寄存器470相关联的上下文状态信息472的无效状态，未决的上下文从运行堆栈460中被取回，并且由运行堆栈460存储的未决的上下文不被写入到TOS寄存器470。

图14是另一种方法的示例实施例的一个流程图1400，该方法可以被实现在至少一个处理器中，该处理器与操作地耦合到网络的一个安全装置中的至少一个存储器操作地耦合。该方法开始(1402)并且可以操作地耦合一个第一存储器和一个第二存储器(1404)。该方法可以操作地耦合该至少一个处理器操作地耦合到该第一存储器和该第二存储器(1406)。该方法可以存储一个上下文用于行走至少一个有限自动机中的一个给定有限自动机的多个节点中的一个给定节点，该存储可以包括基于与第一存储器相关联的上下文状态信息来确定访问(i)该第一存储器并且不访问该第二存储器或者(ii)访问该第一存储器和该第二存储器(1408)。该方法可以取回一个未决的上下文。该取回可以包括一个取回确定：基于与该第一存储器相关的该上下文状态信息，确定(iii)访问该第一存储器并且不访问该第二存储器或者(iv)访问该第二存储器并且不访问该第一存储器(1410)。在该示例实施例中，该方法随后结束(1412)。

图15是一种用于取回用于行走给定节点的上下文的方法的示例实施例的一个流程图1500。该方法开始(1502)并且检查包括在上下文状态信息中的有效性状态指示第一存储器的有效状态还是无效状态(1504)。

如果该有效性状态指示有效状态，则一个取回确定可以是访问该第一存储器并且不访问该第二存储器(1506)。该第一存储器可以被访问以从该第一存储器取回该未决的上下文(1508)。与该第一存储器相关的该上下文状态信息可以被更新(1510)，例如，以便将包括在该上下文状态信息中的有效性状态从一个有效状态改变为一个无效状态，以指示该第一存储器没有存储未决的上下文。在该示例实施例中，该方法随后结束(1518)。

然而，如果有效性状态的检查(1504)指示无效状态，则该取回确定可以是访问该第二存储器并且不访问该第一存储器(1512)。该第二存储器可以被访问以取回该未决的上下文(1514)并且与该第一存储器相关联的上下文状态信息可以被保存(1516)，因为该第一存储器继续不存储未决上下文。在该示例实施例中，该方法随后结束(1518)。

图16是可以根据在此披露的实施例进行存储或取回的上下文1601的示例实施例的一个框图1600，如通过推送或弹出一个堆栈条目。根据在此披露的实施例，上下文1601可以包括多个字段1602-1618。该多个字段可以包括一个上下文条目类型字段1602，该字段可以是基于多个节点类型(如可变计数节点或元素节点类型)中的一个节点类型，如以上所披露的可变计数节点。上下文条目类型字段1602可以表示该多个字段1602-1618中的哪些字段可以是对该节点类型而言相关的。

上下文1601可以进一步包括一个匹配类型字段1604，该字段可以是基于上下文条目类型字段1602而相关的。该匹配类型字段1604可以基于该节点类型是相关的并且可以用于确定一个给定节点被配置成用于在一个从网络接收的输入流中匹配一个给定元素的单个实例还是多个连续实例。例如，匹配类型字段1604可以指示一个懒惰或贪婪匹配类型。

上下文1601可以进一步包括一个元素字段1608，该元素字段可以是相关的而无论该上下文条目类型字段1602如何并且可以标识该给定元素以在该给定节点进行匹配。

上下文1601可以进一步包括一个下一节点地址字段1610，该字段可以是相关的而无论该上下文条目类型字段如何并且可以标识与该给定节点相关联的下一节点。例如，基于在该给定节点的肯定匹配，用于行走下一区段的该下一节点可以经由下一节点地址字段1610进行标识。

上下文1601可以进一步包括一个计数字段1612，该字段可以是基于上下文条目类型字段1602而相关的。例如，如果上下文条目类型字段1602指示该给定节点是一个固定的计数节点，那么该计数值可能不是相关的，而如果上下文条目类型字段指示该给定节点是一个懒惰型可变计数节点或一个贪婪型可变计数节点(VCG)，那么该计数值可以是相关的。计数字段1612可以基于指示该懒惰型可变计数节点类型的上下文条目类型字段标识用于对由元素字段1608标识的给定元素的肯定匹配而言剩余的连续实例数目的一个计数值。基于指示该给定节点为贪婪型可变计数节点(VCG)节点的上下文条目类型字段1602，计数字段可以指示对在该给定节点处的该给定元素肯定匹配的连续实例数目。例如，该计数值如对于图8的处理循环828b-h所示的计数值。

上下文1601可以进一步包括一个丢弃未探索上下文(DUP)字段1614，该丢弃未探索上下文字段是相关的而无论该上下文条目类型字段1602如何，并且在该输入流中检测到至少一个正则表达式的完全匹配的事件中可以标识是丢弃上下文1601还是行走由该下一节点地址字段1610标识的下一节点。

上下文1601可以进一步包括一个逆向行走方向字段1616，该逆向行走方向字段可以是相关的而无论该上下文条目类型字段1602如何并且可以标识一个逆向或正向的行走方向。

上下文1601可以进一步包括一个偏移字段1618，该偏移字段可以是相关的而无论该上下文条目类型字段1602如何并且可以标识在输入流中的有效载荷的一个区段的偏移以进行对一个特定元素的匹配。该特定元素可以基于上下文条目类型字段1602进行标识。例如，基于指示一个懒惰型可变计数节点的上下文条目类型字段1602，偏移字段1618可以标识该有效载荷的一个区段以匹配由上下文1601的元素字段1608标识的给定元素。然而，基于指示一个贪婪型可变计数节点的上下文条目类型字段1602，偏移字段1618可以标识该有效载荷的一个区段以与下一元素进行匹配，该下一元素经由与该下一节点相关的下一元数据标识，该下一节点经由上下文1601的下一节点地址字段1610标识。该下一元数据可以基于经由下一节点地址字段1610提取该下一节点而获得。

于是，根据在此披露的实施例，推送上下文可以包括配置一个包括上下文1601的堆栈条目并且该堆栈条目可以被存储在一个堆栈中，如以上所披露的图4的运行堆栈460。上下文1601的这些字段的一个第一子集可以基于与该给定节点相关联的给定元数据进行配置，基于先前已经提取该给定节点来获得，如匹配类型字段1604、元素字段1608、和下一节点地址字段1610字段。上下文1601的这些字段的一个第二子集可以基于该行走的运行时间信息由HNA 108来配置，如当前行走方向或对给定节点保持的计数值。例如，该第二子集可以包括逆向行走方向字段1616、计数字段1612、和丢弃未探索上下文(DUP)字段1614。

根据在此披露的实施例，上下文1601可以由HNA 108基于包括在上下文条目类型字段1602中的上下文状态设定(未展示)进行解释。上下文状态设定可以指示上下文1601是完整的还是不完整的。基于指示该上下文1401不完整的一个弹出的堆栈条目的上下文1601的上下文条目类型字段1602的上下文状态设定，HNA 108可以被配置成用于提取经由下一节点地址字段1610标识的该下一节点并且基于由该下一节点存储的元数据和当前运行时间配置(如行走方向)来继续行走，而不是基于弹出的堆栈条目的上下文1601的字段配置来继续行走。

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

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

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

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

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