HK1214695B - 基於存储器层次的有限自动机的编译 - 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))执行内容搜索。

概述

本发明的实施例提供一种用于有限自动机的编译和运行时间处理的方法、装置、计算机程序产品和相应的系统。

根据一个实施例，在操作地耦合到一个网络的一个安全装置中的至少一个处理器中，一种方法可以包括生成至少一个每图样非确定型有限自动机(NFA)。该至少一个处理器可以被操作地耦合到多个存储器，该多个存储器被映射到在一个存储器层次中的多个层级中。每个每图样NFA可以对于单个正则表达式图样而生成并且可以包括一组对应的节点。该方法可以分布每个每图样NFA的该组对应的节点的节点以基于所映射的层级和为这些层级配置的每图样NFA存储分配设定来将其存储在该多个存储器中。

该方法可以包括基于该分布在该多个存储器中静态地存储所生成的每个每图样NFA的该组对应的节点的这些节点。

生成该至少一个每图样NFA可以包括指定从一个给定节点经由一个与该给定节点相关联的下一节点地址到一个下一节点的转换并且配置该下一节点地址以标识该下一节点和分布给该下一节点用于进行存储的该多个存储器中的一个给定存储器。

该方法可以包括配置这些每图样NFA存储分配设定中的每个每图样NFA存储分配设定用于这些层级中的一个对应的层级，以表示所生成的每个每图样NFA的该组对应的节点的目标数量的唯一节点，以分布用于在该多个存储器中的一个映射到该对应的层级的给定存储器中进行存储。

该组对应的节点中的唯一节点可以是按一种连续方式安排在该至少一个每图样NFA的一个包括该组对应的节点的给定的每图样 NFA内。

该方法可以包括对于该对应的层级配置每个每图样NFA存储分配设定，其方式为，在为一组正则表达式图样中的每个正则表达式图样生成一个每图样NFA的事件中，使得该给定存储器能够提供足够的存储容量用于存储从所生成的每个每图样NFA表示的该目标数量的唯一节点。

该方法可以包括经由一个绝对值来表示该目标数量的唯一节点。该绝对值可以是对于每组对应的节点的一个共用值，从而使得每组对应的节点能够具有对于该目标数量的唯一节点的一个相同的值，以便存储在被映射到该对应的层级的该给定存储器中。

该方法可以包括经由一个百分比值来表示该目标数量的唯一节点，该百分比值用于应用到每组对应的节点的对应的节点总数，从而使得每组对应的节点能够具有对于该目标数量的唯一节点的一个单独的值，以便存储在被映射到该对应的层级的该给定存储器中。

该多个存储器中的每个存储器可以基于该多个存储器的性能排序以降序连续地映射到这些层级的一个对应的层级。该多个存储器中的一个性能排序最高的存储器可以被映射到这些层级中一个排序最高的层级。

这些每图样NFA存储分配设定可以包括一个第一每图样NFA 存储分配设定和一个第二每图样NFA存储分配设定。这些层级可以包括一个排序最高的层级和一个排序次高的层级。该第一每图样NFA存储分配设定可以被配置成用于该排序最高的层级。该第二每图样NFA 存储分配设定可以被配置成用于该排序次高的层级。

分布所生成的每个每图样NFA的该组对应的节点的这些节点可以包括以一种连续方式分布，该分布包括该组对应的节点的这些节点的一个第一分布，用于存储在该多个存储器中的一个第一存储器中。该第一存储器可以被映射到这些层级中的一个排序最高的层级。该分布可以包括该组对应的节点中的这些的节点的一个第二分布，基于在该组对应的节点中剩余的至少一个未分布的节点。每个至少一个第二分布可以是用于在该多个存储器中的一个给定存储器中进行存储。该给定存储器可以被映射到这些层级中的一个给定的层级，对于该组对应的节点的这些节点的每一次分布，该给定的层级连续地低于该排序最高的层级。

如果该给定的层级是这些层级中排序最低的层级，则该至少一个第二分布中的一个给定的分布可以包括在该组对应的节点中的所有剩余的未分布节点。

该方法可以包括将在该第一分布中的节点数目最大化，并且该最大化后的数目可以是由这些每图样NFA存储分配设定中的一个被配置成用于该排序最高的层级的对应的每图样NFA存储分配设定来限制的。

该方法可以包括将在每个至少一个第二分布中的节点数目最大化，并且该最大化后的数目可以是对于每一次分布由这些每图样NFA 存储分配设定中的一个被配置成用于该给定层级的对应的每图样NFA 存储分配设定来限制的。

该方法可以包括静态地存储每个每图样NFA的该组对应的节点的这些节点，使得能够用在从网络接收的一个输入流中的多个有效载荷的多个区段来行走每组对应的节点的这些节点，以确定在该输入流中的至少一个正则表达式图样的一次匹配。

该行走可以基于该组对应的节点的匹配这些有效载荷的区段的单独节点来进行。

该方法可以进一步包括基于在一组正则表达式图样中的正则表达式图样总数和与该行走相关联的所希望的性能度量来确定这些每图样NFA存储分配设定。

该方法可以包括基于选自一组正则表达式图样中的每个图样的至少一个子图样来生成一个统一的确定型有限自动机(DFA)并且将该统一的DFA存储在该多个存储器中的一个给定存储器中。

该多个存储器可以包括一个第一存储器、一个第二存储器、和一个第三存储器，并且该第一和第二存储器可以与该至少一个处理器共同定位在一个芯片上，而该第三存储器可以是定位在该芯片之外的一个外部存储器并且被映射到这些层级中的一个排序最低的层级。

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

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

附图说明

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

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

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

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

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

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

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

图5B是用于以一个有效载荷行走图5A的NFA图形的处理周期的示例实施例的一个表。

图6是该行走器的一个环境的示例实施例的框图。

图7是该编译器的一个环境的示例实施例的框图。

图8是对于多个每图样NFA的节点分布的示例实施例的框图。

图9是一种方法的示例实施例的一个流程图，该方法可以在至少一个处理器中执行，该至少一个处理器与多个存储器操作地耦合，该多个存储器映射到操作地耦合到网络的一个安全装置中的存储器层次中的多个层级。

图10是对于多个每图样NFA的节点的另一个节点分布的示例实施例的框图。

图11是一种用于分布至少一个每图样NFA的节点的方法的示例实施例的一个流程图。

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

具体实施方式

在详细描述本发明的示例实施例之前，直接在以下描述了一种示例安全应用以帮助读者理解在此披露的本发明的特征，这些实施例可以实现在该安全应用中并且典型的处理使用确定型有限自动机(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转发到网络中的另一跳、最终目的地、或通过另一个总线(未展示)以便由一个主机处理器(未展示)进行进一步处理。网络协议处理可以包括网络安全协议的处理，如防火墙、应用防火墙、包括IP层安全协议(IPSec)和/或安全套接层(SSL)的虚拟专用网(VPN)、入侵检测系统(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。存储器104可以是内部的(即，芯片上的)或外部的(即，芯片外的)或其组合，并且可以被配置成用于存储所接收的数据包，如用于由网络服务处理器100进行处理的数据包101a。存储器104可以被配置成用于存储用于在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-图2G展示了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中实现一个编译器和一个行走器。

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

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

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

行走器320基于消耗(即，处理)来自所接收的数据包101a 中的有效载荷的区段(如字节)通过转换该统一的DFA 312和该至少一个NFA的状态用该有效载荷来行走该统一的DFA 312和该至少一个 NFA 314。于是，行走器320使该有效载荷走过该统一的DFA 312和该至少一个NFA 314，该至少一个NFA可以是对于单个正则表达式图样生成的一个每图样NFA。

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

如在图3A中所示，任选的限定符308可以各自与该组正则表达式图样304中的一个图样相关联。例如，任选的限定符322可以与图样316相关联。任选的限定符308可以各自是指定所希望的定制、高级 PCRE签名选项、或其他对于处理与这些限定符相关的图样而言合适的选项的一个或多个限定符。例如，限定符322可以指示该高级PCRE签名选项的一个起始偏移(即，在有效载荷中匹配的一个图样的一个第一匹配字符在有效载荷中的位置)选项对于图样316是否是希望的。

根据在此披露的实施例，编译器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中。

该编译器可以确定所选的潜在子图样的长度是固定的还是可变的。例如，如“cdef”的子图样的长度可以被确定为具有为4的固定长度，因为“cdef”是一个字符串，而包括运算符的复杂的子图样可以被确定为具有可变的长度。例如，如“a.*cd[^\n]{0,10}.*y”的复杂子图样可以具有“cd[^\n]{0,10}”作为所选的子图样，该子图样可以具有2 到12的可变长度。

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

如以上所披露的，从在该组一个或多个正则表达式304中的每个图样选择一个子图样可以是基于至少一种启发法。根据一个实施例，该至少一种启发法可以包括将所选唯一子图样的数目和所选每个子图样的长度最大化。例如，如“ab.*cdef.*mn”的一个图样可以具有多个潜在的子图样，如“ab.”、“cdef”和“.*mn”。该编译器可以选择“cdef”作为该图样的子图样，因为它是在图样“ab.*cdef.*mn”中不太可能导致DFA图爆的最大的子图样。然而，如果子图样“cdef”已经对另一个图样选中，则该编译器可以选择图样“ab.*cdef.*mn”的一个替代子图样。替代性地，该编译器可以对于该另一个图样用另外的子图样来替换子图样“cdef”，使得子图样“cdef”能够对于图样“ab.*cdef.*mn”进行选择。

于是，编译器306可以基于对于这些图样304中的每个而言可能的子图样的上下文来对图样304选择子图样，使得能够将所选的唯一子图样的数目和所选的每个子图样的长度最大化。于是，编译器306可以从所选的子图样302生成一个统一的DFA 312，这通过增加一个图样在该至少一个NFA 314中匹配的概率而使在该至少一个NFA 314的图样匹配中误报(即，无匹配或部分匹配)的数目最小化。

通过使子图样长度最大化，在NFA处理中的误报可以避免。在NFA处理中的误报可能导致非确定型运行时间处理，并且因此可能降低运行时间性能。另外，通过使所选的唯一子图样的数目最大化，编译器306使得在该统一的DFA与从该统一的DFA中(来自该图样)的一个子图样的匹配所给定的组中的一个子图样所生成的该至少一个 NFA 314的1:1的转换成为可能。

例如，如果所选的子图样由多个图样共享，那么该统一的DFA 的一个行走器将会需要转换到多个至少一个NFA，因为每个至少一个 NFA是一个每图样NFA，并且来自该统一的DFA的子图样匹配表示对于该多个图样中的每个的部分匹配。于是，使唯一子图样的数目最大化减少了DFA:NFA数目1:N的转换，从而减少了通过行走器320的运行时间处理。

为了使唯一子图样的数目能够最大化，编译器302可以计算所选子图样318的一个哈希值326并且将所计算的哈希值326与从中选择子图样318的一个图样316的一个标识符(未展示)相关联地进行存储。例如，编译器306可以对于在该组304中的每个图样计算所选子图样的一个哈希值。所计算的哈希值324可以作为一个表或以任何合适的方式存储在该至少一个存储器104中。所用的哈希方法可以是任何合适的哈希方法。该编译器可以将所计算的哈希值与对于该组中其他图样所选的子图样的一个哈希值列表进行比较，以便确定所选的子图样是否唯一。

如果所计算的哈希值存在于该列表中，该编译器可以确定是(i) 用来自该图样的另一个子图样替换该子图样还是(ii)用选自该组中的另一个图样的一个替代子图样来替换对于该组中的该另一个图样所选的子图样。该组中的另一个图样可以基于与该列表中与所计算的哈希值的关联进行标识。确定是替换(i)还是(ii)可以是基于比较考虑用于替换的子图样的长度，以便如上所述使正被选择的唯一子图样的长度最大化。替换一个所选的子图样可以包括选择对于一个给定图样标识的下一最长子图样或者下一最高优先级的子图样。例如，潜在的子图样可以基于造成DFA图爆的可能性或者预期的DFA图爆的强度来确定优先级。

根据在此披露的实施例，该至少一种启发法可以包括标识每个图样的子图样并且如果给定的子图样具有小于一个最小阈值的长度，则忽略每个图样的这些所标识的子图样中的一个给定的子图样。例如，为了减少在该至少一个NFA中的误报，该编译器可以忽略具有小于该最小阈值的长度的子图样，因为此类子图样可能导致在该至少一个NFA 中的更高的误报概率。

该至少一种启发法可以包括访问与使用指示符的历史频率相关联的一个子图样知识库(未展示)，并且如果在所访问的知识库中对于该给定子图样的使用指示符的历史频率大于或等于一个频率使用阈值，则忽略每个图样的这些所标识的子图样中的一个给定的子图样。例如，应用或协议专用的子图样可以具有高使用频率，如对于超文本传送协议(HTTP)有效载荷、“回车换行”、或空流量(clear traffic)如来自二进制文件的多个连续的0，或任何其他频繁使用的子图样。

该至少一种启发法可以包括标识每个图样的子图样，并且对于每个图样，通过选择所标识的子图样中的一个给定的子图样，基于该给定的子图样具有这些所标识的子图样中最大的连续文本字符数目并且基于该给定的子图样对于该组一个或多个正则表达式所选的所有子图样中是唯一的，来最大化在所选子图样中的连续文本字符的数目。如以上所披露的，使所选的子图样的长度最大化可以使能在该至少一个NFA 中存在更高的匹配概率。

该至少一种启发法可以包括基于这些给定子图样中每个的子图样类型和这些给定子图样的长度来设置每个图样的给定子图样的优先级。该子图样类型可以是纯文本、交替、单字符重复、或多字符重复，并且对于子图样类型从最高到最低的优先级顺序可以是纯文本、交替、单字符重复、和多字符重复。于是，为具有至少一个最小长度阈值的长度的文本串的子图样可以被设置为优先级高于可变长度的复杂子图样。

编译器306可以使更长长度的子图样的优先级高于较短长度的另一个子图样。编译器306可以基于优先级设置选择一个唯一子图样作为该所选子图样。如上所述，所选的唯一子图样可以具有至少一个最小长度阈值的长度。

如果给定的子图样都不是唯一并且具有至少该最小长度阈值的长度的，则编译器306可以基于优先级设置选择一个非唯一子图样作为所选的子图样。于是，编译器306可以从一个图样中选择一个子图样，该子图样是选自另一个图样的子图样的一个副本，而不是选择具有小于该最小阈值的长度的一个子图样。为了协助完成子图样，编译器306可以在这些图样上进行多次忽略并且将可能的子图样通过长度分类。于是，对于在该组一个或多个正则表达式304中的一个给定图样的编译器子图样选择可以在对于在该组一个或多个正则表达式304中的其他图样的子图样选择的上下文内进行。

如上所述，限定符322可以指示希望报告一个起始偏移。然而，该起始偏移可能不容易分辨。例如，在给定一个如“axycamb”的有效载荷时，在有效载荷匹配图样中找到一个起始偏移如“a.*b”或“a.*d”可能是困难的，因为可能正在匹配两个图样“axycamb”和“amb.”。于是，可能需要追踪对于在该有效载荷中“a”的两个实例的偏移作为潜在起始偏移。根据在此披露的实施例，潜在的起始偏移不需要被追踪，由于在已经确定在一个有效载荷中找到该整个图样的匹配之前不确定该起始偏移。确定整个图样的匹配可以通过采用来自该统一的DFA、该至少一个NFA或其组合的匹配结果来发现。

根据在此披露的实施例，如果在所接收的数据包101中的一个有效载荷包括与来自图样316的一个所选子图样318匹配的内容，则该行走器可以转换到行走图样318的至少一个NFA。行走器320可以报告该所选子图样318的匹配以及一个偏移，该偏移将该匹配子图样的最后一个字符在所接收的数据包中的位置标识为在该有效载荷中该子图样的结束偏移。子图样匹配可以是对该图样的部分匹配，如果该自图样是该图样的一个子集。于是，行走器320可以通过行走该图样的至少一个 NFA来在有效载荷中继续搜索该图样的剩余部分，以便确定该图样的最终匹配。应当理解的是，该图样可以遍历所接收的数据包101a中的一个或多个有效载荷。

图3B是一种方法的示例实施例的一个流程图(350)，该方法可以被实现在至少一个处理器中，该处理器与操作地耦合到网络的一个安全装置中的至少一个存储器操作地耦合。该方法可以开始(352)并且基于至少一种启发法从该组一个或多个正则表达式图样中的每一个图样中选择一个子图样(354)。该方法可以使用选自该组中所有图样的这些子图样生成一个统一的确定型有限自动机(DFA)(356)。该方法可以生成用于该组中的至少一个图样的至少一个非确定型有限自动机(NFA)，该至少一个图样的一部分用于生成该至少一个NFA，并且用于该至少一个NFA的运行时间处理的至少一个行走方向可以是基于所选的子图样的长度是固定的还是可变的、以及所选的子图样在该至少一个图样中的位置来确定(358)。该方法可以将该统一的DFA和该至少一个NFA存储在该至少一个存储器中(360)。在该示例实施例中，该方法随后结束(362)。

如上所述，编译器306可以生成该统一的DFA 312和该至少一个NFA 314以使得行走器320能够在所接收的数据包101a中搜索一个或多个正则表达式图样304的匹配。编译器306可以基于至少一种启发法从该组一个或多个正则表达式图样304中的每一个图样中选择一个子图样。统一的DFA 312可以使用选自该组304中的所有图样的这些子图样302来生成。编译器306可以对于该组304中的至少一个图样316 生成至少一个NFA 314。于是，编译器306可以被配置成用于将规则集 310编译成二进制图像112，该二进制图像标识来自规则集310的可能最好适合DFA或NFA处理的部分。由此，二进制图像112可以包括至少两个区段，其中，一个第一区段用于DFA处理并且一个第二区段用于NFA处理，如统一的DFA 312和该至少一个NFA 314。如以上所披露的，二进制图像112可以包括用于DFA和NFA两者的编译规则数据，或者可以是将DFA编译规则数据与NFA编译规则数据分开的多个二进制图像。例如，NFA编译规则可以与DFA编译规则分开并存储在操作地耦合到HNA 108的图形存储器中。存储器104可以是图形存储器，该图形存储器可以是多个存储器，例如下文相对于图4披露的图形存储器456。

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

根据在此披露的实施例，HNA 108可以被配置成用于从一个指令队列454读取至少一个指令453。指令队列454可以被配置成用于存储该至少一个指令453，该指令可以是由一个主机(未展示)发送的以便由HNA 108进行处理。该至少一个指令453可以包括至少一个工作，如S1459a、S2459b、或S3459c。该至少一个工作各自可以基于由图1 的HFA协处理器110标识的对于图3A的这些子图样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的该至少一个工作如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的指针，可以是至少一个有限自动机中的一个给定有限自动机，如图3A的该至少一个NFA 314。

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

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

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

图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图形。例如，NFA 图形504可以是一个包括由编译器306生成的多个节点的图形，如节点 N0 506、N1 508、N2 510、N3 512、N4 514、和N5 515。节点N0506 可以表示图样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呈现多个转换路径选项的分离节点。例如，行走分离节点N1 508呈现ε路径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的绝对地址或指向下一节点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可以具有字符节点类型。例如，节点NO 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指示的下一节点在该示例实施例中是分离节点N1 508。于是，行走器320采取处理周期540a的行动536，该行动包括将有效载荷542中的当前偏移更新到“1”并且转换到分离节点N1508。转换可以包括提取(在此也被称为加载)分离节点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上推送节点N3512和当前偏移 (现在为520c(即，“2”))再次存储一个线程。如对于处理周期540f 所示的，行走器320提取节点N2 510并将在偏移520c(即，“2”)处的区段522c(即，“a”)与节点N2 510的元素“a”进行匹配。因为“a”在节点N2 510处匹配，行走器320将当前偏移更新到520d(即，“3”)并且转换到节点N4 514，该节点由如通过编译器306配置的节点N2 510元数据(未展示)指定。例如，N2 510元数据可以指定从一个给定节点如节点N2 510经由与给定节点N2 510相关联的下一节点地址(未展示)到下一节点如节点N4 514的转换511。根据在此披露的实施例，该下一节点地址可以被配置成用于标识该下一节点和该多个存储器456中的编译器306将该下一节点分布到其中用于存储的一个给定存储器。

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

在此披露的实施例可以由于以上披露的组合的DFA和NFA类型的处理而能够获得优化的匹配性能。例如，以上披露的实施例可以减少在NFA处理中的误报的数目，因为NFA处理可以是基于经由DFA 处理标识的部分匹配。另外，因为在此披露的实施例包括每规则(即，每图样)NFA，这些NFA可以通过DFA处理进行标识，在此披露的实施例进一步优化匹配性能。

如以上所披露的，DFA 312是一个统一的DFA并且该至少一个NFA 314各自是一个每图样NFA。通过HFA 110使有效载荷走过该统一的DFA 312可以被认为是标记图样的起始点(中间匹配)的一个第一解析块并且对可能从该标记继续行走的该至少一个NFA 314提供该起始点以确定一个最终匹配。例如，基于由穿过一个统一的DFA 312 处理一个输入流的有效载荷的多个区段而确定的部分匹配结果，行走器 320可以确定规则集310的给定数目的规则(即，图样)需要被进一步处理，并且HFA 110可以产生可能被变换为给定数目的NFA行走的图样匹配结果，因为该至少一个NFA 314各自是一个每图样NFA。

图6是行走器320的一个环境600的示例实施例的框图600。一个数据包101a输入流可以被接收602并且可以包括数据包616a-f，这些数据包可以是来自不同流，如一个第一流614a和一个第二流614b。例如，数据包P1 616a、P4 616d、和P6 616f可以是在第一流614a中的数据包，而数据包P2 616b、P3 616c、和P5 616e可以属于第二流614b。处理内核603可以是安全装置102的通用处理器内核，如以上参考图1 所披露的，该安全装置可以被配置成用于执行处理数据包101a的高层协议并且可以被配置成用于是该图样匹配方法分流到HFA110和HNA 108。

数据包101a可以被转发604到HFA 110并且行走器320可以使这些数据包101a的区段走过该统一的DFA，如图3A的统一的DFA 312，以确定在该输入流中的正则表达式图样304的部分匹配。行走器 320可以被配置成用于转发606这些部分匹配的结果，这些部分匹配的结果可以标识数据包101a的区段的偏移和每图样NFA的节点，如该至少一个NFA 314，以通过HNA 108来进行这些部分匹配，该HNA 108 可以基于HFA 110的DFA处理的部分匹配结果来行走该至少一个NFA 314，因为这些部分匹配结果可以与数据包101a中的相应数据包一起被转发608到HNA 108。

HNA 108可以允许确定部分匹配结果618c、618b、和618a形成对该输入流中的这些正则表达式图样304中的一个给定的正则表达式图样的一个最终(即，完整的)匹配。例如，通过间接地经由处理内核603或直接地从HFA 110，从HFA 110转发606这些HFA部分匹配结果到HNA 108，每个通过HFA 110部分匹配的数据包可以使得HNA 108能够使该部分匹配前进，因为行走器320可以用来自HFA 110的“提示”或起始信息使数据包101a的区段走过该至少一个NFA 314。

例如，如以上参考图4披露的，输入堆栈458可以包括至少一个工作，如该至少一个指令453中的S1 459a、S2 459b、或S3 459c，用于通过HNA 108进行处理。该至少一个指令的该至少一个工作可以各自属于一个相同的给定的有效载荷，如有效载荷462，该有效载荷由HFA 110处理。可以基于由HFA 110“预筛选”的数据包的此类“提示”或起始信息可以包括NFA开始节点以及相应的有效载荷区段的偏移，用于以一个每图样NFA行走，如以上所披露的。于是，行走器320可以确定对于可以从HNA 108转发到处理内核603的数据包101a和可以在适当时作为网络中的数据包101b然后被转发612的数据包101a的最终匹配结果610。

除了可以减少NFA处理的误报数目的通过HFA 110进行的此类数据包预筛选之外，在此披露的实施例可以通过将每个每图样NFA 的节点基于节点局域性分布到在一个存储器层次中的多个存储器来进一步优化匹配性能。由于每个NFA可以是一个每图样NFA，在此披露的实施例可以基于如下理解有利地将每个每图样NFA的节点分布到在一个层次中的多个存储器：规则(即，图样)越长，从该规则的结束部分生成的节点需要被访问(即，行走或遍历)的可能性就越小。通过将该每图样NFA的每个的更早的节点存储在相对更快的(即，更高性能) 的存储器中，在此披露的实施例可以进一步优化匹配性能。应当理解的是，因为此类节点分布可以是基于层级到存储器映射，所以节点可以有利地基于所映射的层级来分布，从而能够采用优化匹配性能的任何合适的分布。

如以上所披露的，该至少一个NFA 314(如图5A的每图样NFA 504)可以被存储在至少一个存储器中，如图1的存储器104或图4的图形存储器456。根据在此披露的实施例，行走器320的匹配性能可以基于智能编译器306有利地跨可以包括在一个存储器层次中的多个图形存储器的该至少一个存储器456来分布该每图样NFA 504的节点来进行优化。

例如，行走器320的匹配性能可以是基于将连续的节点(如图 5A的每图样NFA 504的区段509的节点N0 506、N1 508、N2 510和 N3 512)存储在一个更快性能的存储器中来进行优化，该存储器相对于可以在存储器层次中映射到更低层级的另一个存储连续节点N4514和 N5 515的存储器映射到一个更高层级。由于NFA 504是从单个图样(如图样502)生成的一个每图样NFA，NFA 504与从其他图样生成的其他NFA分离并且因此在此披露的实施例可以是基于对该每图样NFA的节点的所识别的局域性并不存在于一个统一的NFA的节点中。

在此披露的实施例可以是基于以下理解，即，一个每图样NFA 图形(如每图样NFA图形504)的更早的节点(如节点N0 506、N1 508、 N2 510和N3 512)可以具有比节点N4 514和N5 515更高的被遍历的可能性，因为节点N4 514和N5 515是朝向该规则(即，图样)502的结束处定位的并因此要求该有效载荷中的更多得到匹配以便进行行走 (即，遍历)。于是，一个每图样HFA(如NFA 504)或其他任何合适的每图样NFA图形的更早的节点可以被认为是与仅在出现图样完整匹配的事件中被访问的“低触摸”节点相比由于误报可以被更频繁访问的“高触摸”节点。

根据在此披露的实施例，编译器306可以基于对每个每图样 NFA中的哪些节点被认为是“高触摸”节点而哪些节点被认为是“低触摸”节点的理解将每个每图样NFA的节点分布到在一个层次中的存储器。这种理解可以被用于通过将这些节点分布到在一个存储器层次中的存储器来“预高速缓存”(即，静态存储)每个每图样NFA的节点，从而允许改进的匹配性能。例如，“高触摸”节点可以基于以下理解被分布到更快的存储器：“高触摸”节点由于其在该每图样NFA中的局域性将被更频繁地访问(即，行走或遍历)。

一般而言，基于一组正则表达式图样生成的一个统一NFA的正则表达式访问图样可以是随机的，因为这种访问图样可以是基于具体的有效载荷。因此，正则表达式访问图样的历史无法用于预测进一步的正则表达式访问图样。例如，高速缓存一个统一的NFA的最近遍历的节点不能对行走器提供性能收益，因为在该统一的NFA内访问的下一节点可能不是所高速缓存的节点。

图7是编译器306的一个环境700的实施例的框图。如以上所披露的，编译器306可以被称为智能编译器，该智能编译器可以被配置成用于通过标识规则集310的可能最好适合DFA或NFA处理的部分来将规则集310编译成二进制图像112。由此，二进制图像112可以包括至少两个区段，其中，一个第一区段用于DFA处理并且一个第二区段用于NFA处理，如统一的DFA 312和该至少一个NFA 314，如以上关于图3A披露的。根据在此披露的实施例，HNA108可以操作地耦合到可以包括图形存储器456的多个存储器，如以上关于图4披露的。根据在此披露的实施例，编译器306可以被配置成用于确定该统一的DFA 312和该至少一个NFA314的节点在图形存储器456中的放置。

根据在此披露的实施例，该统一的DFA 312可以被静态地存储在图形存储器456的一个给定存储器中，而至少一个NFA 314可以具有跨图形存储器456分布并静态地存储的节点，因为编译器306可以将分布特定NFA节点用于存储在特定存储器中以便优化行走器匹配性能作为目标。根据在此披露的实施例，图形存储器456可以是在一个可以包括多个层级708a-c的存储器层次743中。该多个层级708a-c可以被映射到可以包括存储器756a-c的该多个图形存储器456。

编译器306可以将层级708a-c以任何合适的方式进行映射，并且层级708a-c可以用降序712排序，使得层级708a可以是排序最高的等级708a而等级708c可以是排序最低的等级。图形存储器756a-c可以包括一个随机存取存储器(RAM)，该存储器可以为与一个网络服务处理器100上的片上搜索存储器(OSM)共同定位的最高性能存储器。图形存储器756a-c可以包括一个可以是在外部并操作性耦合到网络服务处理器100的系统存储器。

基于根据存储器性能(即，读和写访问时间)的映射，该RAM 存储器可以被映射到排序最高的层级708a，该OSM可以被映射到排序次高的层级708b，而系统存储器可以被映射到排序最低的层级708c。然而，应当理解的是，在该多个层级708a-c与图形存储器756a-c之间的映射可以是以任何合适的方式形成的。例如，该映射可以是基于如下的理解：可以生成一个与规则集310(这些节点从其中被分布到存储器 756a-c)相关联的应用，因此最高性能的存储器可能不配映射到排序最高的层级。另外，应当理解的是，所示出的存储器层次743中的层级数目和图形存储器756a-c的数目是为了说明的目的并且可以是任何合适的层级和存储器数目。

如以上所披露的，一个每图样NFA的节点的局域性可以由智能编译器306利用，这是通过存储从在更快的存储器中的一个给定图样的多个更早的部分生成的NFA节点。另外，因为，由于给定图样的部分匹配是通过HFA 110的DFA处理来确定的，给定图样的匹配的概率已经更高，所以组合此类实施例以优化匹配性能。

例如，如以上所披露的，DFA处理可以用于减少由NFA处理找到的误报数目。由于每个NFA可以是每图样NFA，每个每图样NFA 的节点可以是有利地基于该多个存储器到存储器层次743的层级的映射而跨该多个存储器分布的。例如，从相对更短长度的图样生成的更小的NFA可以使所有节点分布到一个第一层级并且存储在一个被映射到该第一层级的第一存储器中，而从相对更长长度的图样生成的更大的 NFA可以使一个第一节点部分分布到该第一层级并且剩余的部分分布在剩余的层级中。该第一层级可以是一个映射到最高性能存储器的排序最高的层级。

于是，这些每图样NFA的更早的节点可以被存储在该最高性能的存储器中。因为由于误报更早的节点可以具有更高的被遍历的可能性，在此披露的实施例可以使得大多数误报能够经由访问映射到在存储器层次743中的更高层级的存储器来处理。根据在此披露的实施例，可以通过使得对映射到排序最高的层级(如在存储器层次743中的层级 708a)的存储器756a的访问数目能够比对可以被映射到排序最低的层级708c的存储器756c的访问数目相对更高来优化匹配性能。

存储器756a可以是允许例如每秒1300百万次事务处理的最高性能的存储器，而存储器756b可以具有允许每秒150百万次事务处理的较差的性能，并且存储器756c可以是允许每秒12百万次事务处理的最差性能的存储器。另外，根据在此披露的实施例，映射到排序更高的层级的此类更高性能的存储器的量可以是在大小上相对小于映射到排序最低的层级708c的更低性能的存储器，如存储器756c(相比之下可以是相对大的存储器)。例如，存储器756c可以是外部的且提供受物理上所附接的存储器的量限制的相对大量的存储容量的一种系统存储器。

根据在此披露的实施例，每图样NFA存储分配设定710a-c可以被配置成用于层级708a-c。每图样NFA存储分配设定710a-c可以表示用于从每个每图样NFA分布到这些层级708a-c中的一个对应的层级以存储在一个映射到该对应的层级的给定存储器的该目标数量的唯一节点。编译器306可以被配置成用于确定每图样NFA分布设定710a-c，其方式为使得映射到层级708a-c的存储器756a-c在对于规则集310中的该一个或多个图样中的每个生成一个每图样NFA的事件中能够提供足够的存储容量。

每图样NFA存储分配设定710a-c可以表示每个每图样NFA的该组对应的节点中用于在一个对应的层级分布以存储到映射到该对应的层级的一个给定存储器的该目标数量的唯一节点。例如，基于被配置成用于层级708a的每图样NFA存储分配设定710a，编译器306可以分布每图样NFA 714a的该组对应的节点702a的一个第一部分704a和每图样NFA 714b的该组对应的节点702b的一个第二部分704b用于存储在映射到层级708a的存储器756a中。

基于被配置成用于层级708b的每图样NFA存储分配设定 710b，编译器306可以分布每图样NFA 714a的该组对应的节点702a的一个第三部分706a和每图样NFA 714b的该组对应的节点702b的一个第四部分706b用于存储在映射到层级708b的存储器756b中。这种分布是目标分布，因为一组给定的对应的节点的节点数目可能不包括该目标数目，因为在用于分布的对应组中可能之前产生了少于目标数目或者剩余少于目标数目。

在该示例实施例中，每图样NFA存储分配设定710c可以被配置成用于存储器层次743的排序最低的层级708c并且可以表示无限数目的方式来指定。在该示例实施例中映射到排序最低的层级708c的存储器756c可以是具有相对大存储量的一种系统存储器。于是，编译器 306可以将节点分布到系统存储器，包括将为这些每图样NFA 714a-b 中每个所生成的每组对应的节点的任何剩余的未分布节点进行分布以存储在系统存储器756c中。

应当理解的是，对于存储器映射的层级可以固有地由该编译器理解，并且于是可以免除特定的层级708a-c。例如，编译器306可以配置这些每图样NFA存储分配设定710a-c并且基于对存储器756a-c中的每个在存储器层次743中的层级映射的固有理解将这些设定直接映射到存储器756a-c。还应当理解的是，在图7中所示的每图样NFA、这些每图样NFA的节点、和分布的数目是用于说明的目的并且可以是任何合适的每图样NFA、节点或分布数目。

图8是对于多个每图样NFA的节点分布的示例实施例的框图800。在该示例实施例中，对于一个或多个图样804中的一个图样816a 生成一个第一NFA 814a，对于该一个或多个图样804中的一个第二图样816b生成一个第二NFA 814b，并且对于该一个或多个图样804中的一个第三图样816c生成一个第三NFA 814c。

第一每图样NFA 814a的一个第一节点部分804a被分布到映射到在存储器层次812中的一个第一存储器856a的层级808a，并且一个第二节点部分806a被分布到映射到一个第二存储器856b的第二层级 808b。在该示例实施例中，层级808a是排序最高的层级，而层级808b 是排序最低的层级。第二每图样NFA 814b的一个第三节点部分804b 被分布到映射到在存储器层次812中的第一存储器856a的层级808a，并且一个第四节点部分806b被分布到映射到第二存储器856b的第二层级808b。第三每图样NFA 814c的一个第五节点部分804c被分布到映射到在存储器层次812中的第一存储器856a的层级808a，并且一个第六节点部分806c被分布到映射到第二存储器856b的第二层级808b。

如在图8中所示，分布用于存储在映射到层级808a的存储器 856a中的第二NFA814b的第二节点部分804b可以是分别小于第一 NFA 814a和第三NFA 814c的第一节点部分804a和第五节点部分804c。如果每图样NFA 814b的节点数目小于由用于层级808a的一个每图样 NFA存储分配设定(未展示)所表示的唯一目标节点数目，于是例如可以是这种情况。另外，由于层级808b是在存储器层次812中的排序最低的层级，用于层级808b的下一每图样NFA存储分配设定(未展示) 可以是非常大的，从而使得所有未分布的节点能够在已经进行了到高于层级808b的每个层级的分布之后被分布以存储在被映射到层级808b的存储器856a中。于是，在该示例实施例中，第二节点部分806a可以包括比第六节点部分806c更多的节点，因为图样816a可以是比图样816c 更长的规则。另外，第四节点部分806b可以为空，因为图样816b可以是相对较短的，其中，对于每图样NFA 814b生成的少数节点造成每图样NFA814b的所有节点被分布到层级808a以存储在存储器856a中。

编译器306可以作为生成每个每图样NFA的一部分来分布每个每图样NFA的节点。如以上所披露的，在NFA中从一个第一节点到一个第二节点的转换可以经由通过一个下一节点地址标识该第二节点的第一节点元数据来指定。根据在此披露的实施例，该下一节点地址可以被编译器306配置为包括一个部分，该部分指示该多个存储器中的已经将该第二节点分布到其中用于存储的一个给定存储器。

图9是一种方法900的示例实施例的一个流程图，该方法可以在至少一个处理器中执行，该至少一个处理器与多个存储器操作地耦合，该多个存储器映射到操作地耦合到网络的一个安全装置中的存储器层次中的多个层级。该方法可以开始(902)并且生成至少一个每图样非确定型有限自动机(NFA)(904)。每个每图样NFA可以对于单个正则表达式图样而生成并且可以包括一组对应的节点。该方法可以分布每个每图样NFA的该组对应的节点的节点以基于所映射的层级和为这些层级配置的每图样NFA存储分配设定来将其存储在该多个存储器中 (906)并且在该示例实施例中该方法然后结束(908)。

图10是对于多个每图样NFA的节点的另一个节点分布的示例实施例的框图1000。在该示例实施例中，节点分布1004和1006被示出为用于存储在一个第一存储器1056a和一个第二存储器1056b中。每个每图样NFA 1014a-c的分布1004可以是基于每图样NFA存储分配设定 1010a和1010b，这些设定被配置成用于分别用于层级1008a和1008b。在该示例实施例中，层级1008a和1008b分别被映射到第一存储器1056a 和第二存储器1056b。

图11是一种用于分布至少一个每图样NFA的节点的方法的示例实施例的一个流程图1100。根据在此披露的实施例，分布所生成的每个每图样NFA的该组对应的节点的这些节点可以包括以一种连续方式分布该组对应的节点中的这些节点，该分布包括该组对应的节点的这些节点的一个第一分布，用于存储在该多个存储器中的一个第一存储器中。该第一存储器可以被映射到这些层级中排序最高的层级。该分布可以包括在上一次分布之后该组对应的节点中的这些节点的一个第二分布，基于在该组对应的节点中剩余的至少一个未分布的节点。每个至少一个第二分布可以是用于在该多个存储器中的一个给定存储器中进行存储。该给定存储器可以被映射到这些层级中的一个给定的层级，对于每一次分布，该给定的层级连续地低于该排序最高的层级。

该方法可以开始(1102)并且将一个给定的层级设定到一个存储器层次中的排序最高的层级(1104)。该方法可以将一个给定的每图样NFA设定到从一组一个或多个正则表达式图样生成的至少一个NFA 中的一个第一每图样NFA(1106)。该方法可以检查该给定的每图样 NFA的未分布节点数目(1108)。如果该给定的每图样NFA的未分布节点数目是零，则该方法可以检查该给定的每图样NFA是否是从该组一个或多个正则表达式图样生成的最后一个NFA(1116)。

如果该给定的每图样NFA是所生成的最后一个每图样NFA，则该方法可以检查该给定的层级是否是排序最低的层级(1120)，并且如果该给定的层级是排序最低的层级，则在该示例实施例中，该方法然后结束(1126)。然而，如果检查该给定的层级是否是排序最低的层级 (1120)结果为否，则该方法可以将该给定的层级设定到下一连续更低的层级(1124)并且再次将该给定的每图样NFA设定到由该组一个或多个正则表达式图样生成的至少一个NFA中的该第一每图样NFA (1106)并且继续检查该给定的每图样NFA的未分布节点数目(1108)。如果该给定的每图样NFA的未分布节点数目为零，则该方法可以如以上所披露的那样继续进行。

如果检查该给定的每图样NFA的未分布节点数目(1108)的结果是非零，则该方法可以检查该给定的层级是否是排序最低的层级 (1110)。如果结果为是，则该方法可以将未分布节点数目分布到映射到该给定层级的一个给定存储器(1114)并且该方法可以检查该给定的每图样NFA是否是从该组一个或多个正则表达式图样生成的最后一个 NFA(1116)。如果是，则该方法可以如以上所披露的那样继续进行。如果否，则该方法可以将该给定的每图样NFA设定到所生成的下一每图样NFA(1118)，并且该方法可以迭代以再次检查已经更新到所生成的该下一每图样NFA的该给定的每图样NFA的未分布节点数目 (1108)。

如果检查该给定的层级是否是排序最低的层级(1110)的结果是否，则该方法可以检查该给定的每图样NFA的未分布节点数目是否超过由对于该给定的层级(1112)配置的一个每图样NFA存储分配设定表示的节点数目。如果是，则该方法可以将由对于该给定的层级配置的该每图样NFA存储分配设定表示的节点数目分布以存储在映射到该给定层级的该给定存储器中(1122)并且检查该给定的每图样NFA是否是从该组一个或多个正则表达式图样生成的最后一个NFA(1116)。如果是，则该方法可以如以上所披露的那样继续进行。

如果检查该给定的每图样NFA是否是最后一个每图样NFA (1116)的结果为否，则该方法可以将该给定的每图样NFA设定到所生成的下一每图样NFA(1118)，并且该方法可以迭代以再次检查已经更新到所生成的该下一每图样NFA的该给定的每图样NFA的未分布节点数目(1108)。

然而，如果检查该给定的每图样NFA的未分布节点数目是否超过由对于该给定的层级配置的一个每图样NFA存储分配设定表示的节点数目(1112)的结果为否，则该方法可以将该未分布节点数目分布到映射到该给定的层级的该给定存储器(1114)并且如以上所披露的那样继续进行。

根据在此披露的实施例，该每图样NFA存储分配设定可以经由一个绝对值来表示该目标数量的唯一节点。该绝对值可以是对于每组对应的节点的一个共用值，从而使得每组对应的节点能够具有对于该目标数量的唯一节点的一个相同的值，以便存储在被映射到该对应的层级的给定存储器中。例如，如图10中所示，这些每图样NFA中的每个 1014a-c具有一个所选的第一部分1004，该第一部分表示来自这些每图样NFA 1014a-c的有待分布到映射到层级1008a(配置每图样存储分配设定1010a用于该层级)的存储器1056a的同一个节点数目。

替代性地，该目标数量的唯一节点可以经由一个百分比值表示，该百分比值用于应用到每组对应的节点的对应的节点总数，从而使得每组对应的节点能够具有对于该目标数量的唯一节点的一个单独的值，以便存储在被映射到该对应的层级的该给定存储器中。例如，如果一个如25％的数被配置成用于每图样NFA存储分配设定1010a，该设定被配置成用于层级1008a，那么第一部分1004将会包括这些每图样NFA 1014a-c中每个的25％的节点。由于每个每图样NFA 1014a-c的节点可以不同，来自这些每图样NFA 1014a-c中每个的节点数目可以不同。

这些每图样NFA存储分配设定可以包括一个第一每图样NFA 存储分配设定和一个第二每图样NFA存储分配设定。这些层级可以包括一个排序最高的层级和一个排序次高的层级。该第一每图样NFA存储分配设定可以被配置成用于该排序最高的层级。该第二每图样NFA 存储分配设定可以被配置成用于该排序次高的层级。该第一每图样NFA 存储分配设定可以小于该第二每图样NFA存储分配设定。例如，被表示以用于分布到最高性能存储器的来自每个每图样NFA的节点数目可以是小于被表示以用于最低性能存储器的节点数目(如可以表示无限数目)的一个系统存储器。

在此披露的实施例可以将在一个给定分布中的节点数目最大化，并且最大化后的数目可以是由这些每图样NFA存储分配设定中的一个被配置成用于一个给定层级的对应的每图样NFA存储分配设定来限制的。例如，由一个每图样NFA存储分配设定表示的节点数目可以是十。于是，包括十个或更多未分布节点的每个每图样NFA将会使十个节点被分布。包括少于十个未分布节点的每个每图样将会分布未分布节点数目中的一个对应的数目。

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

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

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

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

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

Claims (37)

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

映射到在一个存储器层次中的多个层级的多个存储器，以及操作性耦合到该多个存储器的至少一个处理器，该至少一个处理器被配置成用于：

生成至少一个每图样非确定型有限自动机(NFA)，每个每图样NFA是为单个正则表达式图样生成的并且包括一组对应的节点；以及

分布所生成的每个每图样NFA的该组对应的节点的节点，以基于所映射的这些层级和为这些层级配置的每图样NFA存储分配设定来存储在该多个存储器中。

2.如权利要求1所述的安全装置，其中，该至少一个处理器被进一步配置成用于基于该分布在该多个存储器中静态地存储所生成的每个每图样NFA的该组对应的节点的这些节点。

3.如权利要求1所述的安全装置，其中，生成该至少一个每图样NFA包括指定从一个给定节点经由一个与该给定节点相关联的下一节点地址到一个下一节点的转换，并且该下一节点地址被配置成用于标识该下一节点和分布给该下一节点用于进行存储的该多个存储器中的一个给定存储器。

4.如权利要求1所述的安全装置，其中，这些每图样NFA存储分配设定中的每个每图样NFA存储分配设定被配置成用于这些层级中的一个对应的层级，以表示所生成的每个每图样NFA的该组对应的节点的目标数量的唯一节点，以分布用于在该多个存储器中的一个映射到该对应的层级的给定存储器中进行存储。

5.如权利要求4所述的安全装置，其中，该组对应的节点中的这些唯一节点是按一种连续方式安排在该至少一个每图样NFA中的一个包括该组对应的节点的给定的每图样NFA内。

6.如权利要求4所述的安全装置，其中，每个每图样NFA存储分配设定被配置成用于该对应的层级，其方式为，在为一组正则表达式图样中的每个正则表达式图样生成一个每图样NFA的事件中，使得该给定存储器能够提供足够的存储容量用于存储从所生成的每个每图样NFA表示的该目标数量的唯一节点。

7.如权利要求4所述的安全装置，其中，该目标数量的唯一节点是由一个绝对值表示并且是对于每组对应的节点的一个共用值，从而使得每组对应的节点能够具有对于该目标数量的唯一节点的一个相同的值，以便存储在被映射到该对应的层级的该给定存储器中。

8.如权利要求4所述的安全装置，其中，该目标数量的唯一节点由一个百分比值来表示，该百分比值用于应用到每组对应的节点的对应的节点总数，从而使得每组对应的节点能够具有对于该目标数量的唯一节点的一个单独的值，以便存储在被映射到该对应的层级的该给定存储器中。

9.如权利要求1所述的安全装置，其中，基于该多个存储器的性能排序该多个存储器中的每个存储器以降序被连续地映射到这些层级中的一个对应的层级，并且该多个存储器中的一个性能排序最高的存储器被映射到这些层级中的一个排序最高的层级。

10.如权利要求1所述的安全装置，其中，这些每图样NFA存储分配设定包括一个第一每图样NFA存储分配设定和一个第二每图样NFA存储分配设定，这些层级包括一个排序最高的层级和一个排序次高的层级，该第一每图样NFA存储分配设定被配置成用于该排序最高的层级，该第二每图样NFA存储分配设定被配置成用于该排序次高的层级。

11.如权利要求1所述的安全装置，其中，分布所生成的每个每图样NFA的该组对应的节点的这些节点包括以一种连续方式分布该组对应的节点中的这些节点，该分布包括：

对该组对应的节点中的这些节点的一个第一分布，用于存储在该多个存储器中的一个第一存储器中，该第一存储器被映射到这些层级中的一个排序最高的层级；以及

对该组对应的节点中的这些节点的一个第二分布，基于在前一分布之后在该组对应的节点中剩余的至少一个未分布节点，每个至少一个第二分布用于存储在该多个存储器中的一个给定存储器中，该给定存储器被映射到这些层级中的一个给定的层级，对于该组对应的节点的这些节点的每一次分布，该给定的层级连续地低于该排序最高的层级。

12.如权利要求11所述的安全装置，其中，如果该给定的层级是这些层级中一个排序最低的层级，则该至少一个第二分布中的一个给定的分布包括在该组对应的节点中的所有剩余的未分布节点。

13.如权利要求11所述的安全装置，其中，该至少一个处理器进一步被配置成用于将在该第一分布中的节点数目最大化，并且该最大化后的数目可以是由这些每图样NFA存储分配设定中的一个被配置成用于该排序最高的层级的对应的每图样NFA存储分配设定来限制的。

14.如权利要求11所述的安全装置，其中，该至少一个处理器进一步被配置成用于将在每个至少一个第二分布中的节点数目最大化，并且该最大化后的数目可以是对于每一次分布由这些每图样NFA存储分配设定中的一个被配置成用于该给定层级的对应的每图样NFA存储分配设定来限制的。

15.如权利要求1所述的安全装置，其中，静态地存储每个每图样NFA的该组对应的节点的这些节点，以使得能够用在从网络接收的一个输入流中的多个有效载荷的多个区段来行走每组对应的节点的这些节点，以确定在该输入流中的至少一个正则表达式图样的一次匹配。

16.如权利要求15所述的安全装置，其中，该行走基于该组对应的节点的匹配这些有效载荷的区段的单独节点来进行，并且该至少一个处理器进一步被配置成用于基于在一组正则表达式图样中的正则表达式图样总数和与该行走相关联的所希望的性能度量来确定这些每图样NFA存储分配设定。

17.如权利要求1所述的安全装置，其中，该至少一个处理器进一步被配置成用于：

基于选自一组正则表达式图样中的每个图样的至少一个子图样来生成一个统一的确定型有限自动机(DFA)；以及

将该统一的DFA存储在该多个存储器中的一个给定存储器中。

18.如权利要求1所述的安全装置，其中，该多个存储器包括一个第一存储器、一个第二存储器、和一个第三存储器，并且该第一和第二存储器与该至少一个处理器共同定位在一个芯片上，而该第三存储器是定位在该芯片之外的一个外部存储器并且被映射到这些层级中的一个排序最低的层级。

19.一种用于实现每图样非确定型有限自动机的方法，包括：

在至少一个处理器中，该至少一个处理器与多个存储器操作地耦合，该多个存储器映射到操作地耦合到一个网络的一个安全装置中的一个存储器层次中的多个层级：

生成至少一个每图样非确定型有限自动机(NFA)，每个每图样NFA是为单个正则表达式图样生成的并且包括一组对应的节点；以及

分布每个每图样NFA的该组对应的节点的节点，以基于所映射的这些层级和为这些层级配置的每图样NFA存储分配设定来存储在该多个存储器中。

20.如权利要求19所述的方法，进一步包括基于该分布在该多个存储器中静态地存储所生成的每个每图样NFA的该组对应的节点的这些节点。

21.如权利要求19所述的方法，其中，生成该至少一个每图样NFA包括指定从一个给定节点经由一个与该给定节点相关联的下一节点地址到一个下一节点的转换，并且配置该下一节点地址用于标识该下一节点和分布给该下一节点用于进行存储的该多个存储器中的一个给定存储器。

22.如权利要求19所述的方法，进一步包括配置这些每图样NFA存储分配设定中的每个每图样NFA存储分配设定用于这些层级中的一个对应的层级，以表示所生成的每个每图样NFA的该组对应的节点的目标数量的唯一节点，以分布用于在该多个存储器中的一个映射到该对应的层级的给定存储器中进行存储。

23.如权利要求22所述的方法，其中，该组对应的节点中的这些唯一节点是按一种连续方式安排在该至少一个每图样NFA中的一个包括该组对应的节点的给定的每图样NFA内。

24.如权利要求22所述的方法，进一步包括对于该对应的层级配置每个每图样NFA存储分配设定，其方式为，在为一组正则表达式图样中的每个正则表达式图样生成一个每图样NFA的事件中，使得该给定存储器能够提供足够的存储容量用于存储从所生成的每个每图样NFA表示的该目标数量的唯一节点。

25.如权利要求22所述的方法，其中，该目标数量的唯一节点是由一个绝对值表示并且是对于每组对应的节点的一个共用值，从而使得每组对应的节点能够具有对于该目标数量的唯一节点的一个相同的值，以便存储在被映射到该对应的层级的该给定存储器中。

26.如权利要求22所述的方法，进一步包括经由一个百分比值来表示该目标数量的唯一节点，该百分比值用于应用到每组对应的节点的对应的节点总数，从而使得每组对应的节点能够具有对于该目标数量的唯一节点的一个单独的值，以便存储在被映射到该对应的层级的该给定存储器中。

27.如权利要求19所述的方法，其中，基于该多个存储器的性能排序该多个存储器中的每个存储器以降序被连续地映射到这些层级中的一个对应的层级，并且该多个存储器中的一个性能排序最高的存储器被映射到这些层级中的一个排序最高的层级。

28.如权利要求19所述的方法，其中，这些每图样NFA存储分配设定包括一个第一每图样NFA存储分配设定和第二每图样NFA存储分配设定，这些层级包括一个排序最高的层级和一个排序次高的层级，该第一每图样NFA存储分配设定被配置成用于该排序最高的层级，该第二每图样NFA存储分配设定被配置成用于该排序次高的层级。

29.如权利要求19所述的方法，其中，分布所生成的每个每图样NFA的该组对应的节点的这些节点包括以一种连续方式分布该组对应的节点中的这些节点，该分布包括：

对该组对应的节点中的这些节点的一个第一分布，用于存储在该多个存储器中的一个第一存储器中，该第一存储器被映射到这些层级中的一个排序最高的层级；以及

对该组对应的节点中的这些节点的一个第二分布，基于在前一分布之后在该组对应的节点中剩余的至少一个未分布节点，每个至少一个第二分布用于存储在该多个存储器中的一个给定存储器中，该给定存储器被映射到这些层级中的一个给定的层级，对于该组对应的节点的这些节点的每一次分布，该给定的层级连续地低于该排序最高的层级。

30.如权利要求29所述的方法，其中，如果该给定的层级是这些层级中一个排序最低的层级，则该至少一个第二分布中的一个给定的分布包括在该组对应的节点中的所有剩余的未分布节点。

31.如权利要求29所述的方法，进一步包括将在该第一分布中的节点数目最大化，并且该最大化后的数目可以是由这些每图样NFA存储分配设定中的一个被配置成用于该排序最高的层级的对应的每图样NFA存储分配设定来限制的。

32.如权利要求29所述的方法，进一步包括将在每个至少一个第二分布中的节点数目最大化，并且该最大化后的数目是对于每一次分布由这些每图样NFA存储分配设定中的一个被配置成用于该给定层级的对应的每图样NFA存储分配设定来限制的。

33.如权利要求19所述的方法，进一步包括静态地存储每个每图样NFA的该组对应的节点的这些节点，使得能够用在从网络接收的一个输入流中的多个有效载荷的多个区段来行走每组对应的节点的这些节点，以确定在该输入流中的至少一个正则表达式图样的一次匹配。

34.如权利要求33所述的方法，其中，该行走基于该组对应的节点的匹配这些有效载荷的区段的单独节点来进行，并且该方法进一步包括基于在一组正则表达式图样中的正则表达式图样总数和与该行走相关联的所希望的性能度量来确定这些每图样NFA存储分配设定。

35.如权利要求19所述的方法，进一步包括：

基于选自一组正则表达式图样中的每个图样的至少一个子图样来生成一个统一的确定型有限自动机(DFA)；以及

将该统一的DFA存储在该多个存储器中的一个给定存储器中。

36.如权利要求19所述的方法，其中，该多个存储器包括一个第一存储器、一个第二存储器、和一个第三存储器，并且该第一和第二存储器与该至少一个处理器共同定位在一个芯片上，而该第三存储器是定位在该芯片之外的一个外部存储器并且被映射到这些层级中的一个排序最低的层级。

37.一种非瞬态计算机可读介质，其上编码有一个指令序列，该指令序列在由操作性耦合到映射到在一个存储器层次中的多个层级的多个存储器的一个处理器加载并执行时致使该处理器：

生成至少一个每图样非确定型有限自动机(NFA)，每个每图样NFA是为单个正则表达式图样生成的并且包括一组对应的节点；以及

分布每个每图样NFA的该组对应的节点的节点，以基于所映射的这些层级和为这些层级配置的每图样NFA存储分配设定来存储在该多个存储器中。