HK1207179B - Engine architecture for processing finite automata - Google Patents

Description

Engine architecture for processing finite automata

Background Art

The Open Systems Interconnection (OSI) reference model defines seven network protocol layers (L1-L7) for communication over a transmission medium. The upper layers (L4-L7) represent end-to-end communication and the lower layers (L1-L3) represent local communication.

Networked application-aware systems need to process, filter, and switch a range of L3 to L7 network protocol layers, for example, L7 network protocol layers such as Hypertext Transfer Protocol (HTTP) and Simple Mail Transfer Protocol (SMTP), and L4 network protocol layers such as Transmission Control Protocol (TCP). In addition to processing network protocol layers, networked application-aware systems need to protect these protocols at line speed (i.e., the data transfer rate on the physical medium of the network over which data is transmitted and received) through L4-L7 network protocol layers while using access- and content-based security, including firewalls, virtual private networks (VPNs), secure sockets layers (SSL), intrusion detection systems (IDS), Internet Protocol Security (IPSec), antivirus (AV), and anti-spam capabilities.

Network processors are used for high-throughput Layer 2 and Layer 3 network protocol processing, meaning they perform packet processing to forward packets at line speed. Typically, general-purpose processors are used to process Layer 4-7 network protocols, which require more intelligent processing. While general-purpose processors can perform computationally intensive tasks, they lack the performance to process data at line speed.

Intrusion detection system (IDS) applications can examine the content of individual data packets flowing through a network and can identify suspicious patterns that may indicate an attempt to break into or compromise a system. An example of a suspicious pattern might be a specific string of text in a data packet that is followed 100 characters later by another specific string of text. This type of content-aware networking may require inspecting the content of data packets at "wire speed." This content can be analyzed to determine if a security breach or intrusion has occurred.

A large number of patterns and rules in the form of regular expressions (also referred to as regular expression patterns herein) can be applied to ensure that all security holes or intrusions are detected. Regular expressions are compact methods for describing patterns in character strings. The simplest pattern matched by a regular expression is a single character or string, for example, /c/ or /cat/. Regular expressions can also include operators and metacharacters with special meanings. By using metacharacters, regular expressions can be used for more complex searches, such as "abc.*xyz". That is, in the case of an unlimited number of characters between "abc" and "xyz", the string "abc" is found, followed by the string "xyz". Another example is the regular expression "abc..abc.*xyz;", that is, the string "abc" is found, followed by two characters, followed by the string "abc" and followed by the string "xyz" after an unlimited number of characters.

Content searches are typically performed using a search method such as a Deterministic Finite Automaton (DFA) or a Non-Deterministic Finite Automaton (NFA) for processing regular expressions.

Summary of the Invention

The embodiments disclosed herein provide a method, apparatus, and corresponding system for processing an engine architecture of a finite automaton.

According to one embodiment, a security device may be operatively coupled to a network. The security device may include at least one central processing unit (CPU) core and at least one super nondeterministic automaton (HNA) processor operatively coupled to the at least one CPU core. The at least one HNA processor may be dedicated to nondeterministic finite automaton (NFA) processing. The at least one HNA processor may include multiple superclusters. Each supercluster may include multiple clusters. Each cluster in the multiple clusters may include multiple HNA processing units (HPUs). The at least one CPU core may be configured to select at least one supercluster from the multiple superclusters. The at least one HNA processor may include an HNA on-chip instruction queue configured to store at least one HNA instruction. The at least one HNA processor may include an HNA scheduler. The HNA scheduler may be configured to select a given HPU from the multiple HPUs in the multiple clusters in the at least one supercluster and assign the at least one HNA instruction to the given HPU to initiate matching of at least one regular expression pattern in an input stream received from the network.

Each supercluster may further include a supercluster graph memory dedicated to the corresponding supercluster. The supercluster graph memory is accessible to the corresponding plurality of HPUs of the corresponding plurality of clusters of the corresponding supercluster. The supercluster graph memory may be configured to statically store a subset of nodes of the at least one per-pattern NFA. A compiler of the at least one per-pattern NFA may determine the subset of nodes.

Each super cluster may further include at least one super cluster character class storage specific to the corresponding super cluster. Each at least one super cluster character class storage may be configured to statically store a plurality of regular expression pattern character class definitions.

The super-cluster graphics memory and the at least one super-cluster character class memory may be unified.

The corresponding plurality of HPUs of the corresponding plurality of clusters of the corresponding super cluster may share the at least one super cluster character class memory.

Each supercluster may further include at least one supercluster character class memory. Each at least one supercluster character class memory may be exclusive to a given cluster in the corresponding plurality of clusters of the corresponding supercluster and shared by the corresponding plurality of HPUs in the given cluster. Each at least one supercluster character class memory may be configured to statically store a plurality of regular expression pattern character class definitions.

The at least one CPU core may be further configured to select the at least one super cluster of the plurality of super clusters by limiting super cluster selection based on a graph identifier associated with the at least one HNA instruction.

The graph identifier may be associated with a given per-mode NFA of the plurality of per-mode NFAs, and limiting the supercluster selection may include a determination that at least one node of the given per-mode NFA is stored within a supercluster graph memory specific to the selected at least one supercluster.

The HNA scheduler may be configured to select the given HPU from a restricted set of HPUs, the restricted set of HPUs including each of the respective plurality of HPUs of each of the respective plurality of clusters of the selected at least one super cluster. The at least one CPU core may be further configured to select the at least one super cluster from the plurality of super clusters based on a determination that at least one node of the given per-pattern NFA associated with the graph identifier is stored within a super cluster graph memory specific to the selected at least one super cluster.

The HNA scheduler may be further configured to select the given HPU from the HPU restricted set based on a round-robin schedule of a plurality of HPUs in the HPU restricted set.

The HNA scheduler may be further configured to select the given HPU from the HPU limit set based on a momentary loading of each HPU in the HPU limit set.

Each supercluster may further include a supercluster graph memory dedicated to the corresponding supercluster. Each supercluster graph memory may be configured to store at least one node of at least one per-pattern NFA in the plurality of per-pattern NFAs to replicate the at least one node in each supercluster graph memory of each supercluster of the at least one NFA processor.

The at least one CPU core may be further configured to provide the HNA scheduler with an option to select the at least one supercluster based on a determination to replicate a given per-mode NFA in the at least one per-mode NFA associated with the at least one HNA instruction. The HNA scheduler may be further configured to select the at least one supercluster based on the provided option and (i) a first cycle schedule of the plurality of superclusters, (ii) a first transient load of the plurality of superclusters, or (ii) a combination of (i) and (ii). The HNA scheduler may be further configured to select the given HPU from the plurality of HPUs in the plurality of clusters of the at least one supercluster based on a second cycle schedule of the plurality of HPUs in the plurality of clusters of the selected at least one supercluster, a second transient load of the plurality of HPUs in the plurality of clusters of the selected at least one supercluster, or a combination thereof.

The at least one HNA processor may further include an HNA on-chip graph memory accessible to the plurality of HPUs of the plurality of clusters of the plurality of superclusters. The HNA on-chip graph memory may be configured to statically store a subset of nodes of the at least one per-pattern NFA. A compiler of the at least one per-pattern NFA may determine the subset of nodes.

The at least one HNA instruction may be a first at least one HNA instruction, and the security device may further include at least one system memory operatively coupled to the at least one CPU core and the at least one HNA processor. The at least one system memory may be configured to include an HNA off-chip instruction queue for storing a second at least one HNA instruction. The second at least one HNA instruction may be transferred to the HNA on-chip instruction queue of the HNA processor pending transmission. The at least one system memory may further include an HNA off-chip graph memory configured to statically store a subset of nodes of the at least one per-pattern NFA. A compiler for the at least one per-pattern NFA may determine the subset of nodes.

The security device may further include at least one local memory controller (LMC). The at least one LMC may be operatively coupled to the at least one HNA processor and the at least one system memory. A given LMC in the at least one LMC may be configured to enable non-coherent access to the at least one system memory so that the at least one HNA processor accesses the HNA off-chip graphics memory.

The at least one system memory may be further configured to include an HNA packet data memory configured to contiguously store a plurality of payloads, each of the plurality of payloads may have a fixed maximum length. Each of the plurality of payloads may be associated with a given HNA instruction among the first at least one HNA instruction stored in the HNA on-chip instruction queue or the second at least one HNA instruction pending transmission to the HNA on-chip instruction queue.

The at least one system memory may be further configured to include an HNA input stack partition configured to store at least one HNA input stack. Each of the at least one HNA input stack may be configured to store at least one HNA input job for at least one HPU in the plurality of HPUs in the plurality of clusters of the plurality of superclusters. The at least one system memory may be further configured to include an HNA off-chip run-time stack partition configured to store at least one HNA off-chip run-time stack to extend the storage of the at least one on-chip run-time stack. Each of the at least one on-chip run-time stack may be configured to store at least one runtime HNA job for the at least one HPU. The at least one system memory may be further configured to include an HNA off-chip save buffer partition configured to extend the storage of at least one on-chip save buffer. Each on-chip save buffer may be configured to store the at least one runtime HNA job for the at least one HPU based on detecting a payload boundary. The at least one system memory may be further configured to include an HNA off-chip result buffer partition configured to store at least one final match result entry of the at least one regular expression pattern determined by the at least one HPU to match in the input stream. Each of the at least one stored HNA instructions may identify a given HNA input stack of the HNA input stack partition, a given HNA off-chip run stack of the HNA off-chip run stack partition, a given HNA off-chip save buffer of the HNA off-chip save buffer partition, and a given HNA off-chip result buffer of the HNA off-chip result buffer partition.

A given LMC of the at least one LMC may be configured to enable the at least one HNA processor to access the HNA packet data memory, the HNA input stack partition, the HNA off-chip instruction queue, the HNA off-chip run stack partition, the HNA off-chip save buffer partition, and the HNA off-chip result buffer partition through a consistent path, and to enable the at least one HNA processor to access the HNA off-chip graphics memory through a non-uniform path.

Each of the plurality of HPUs in the plurality of clusters of the plurality of superclusters may include a node cache configured to cache one or more nodes from a supercluster graphics memory, an HNA on-chip graphics memory, or an HNA off-chip graphics memory. Each of the plurality of HPUs in the plurality of clusters of the plurality of superclusters may further include a character class cache configured to cache one or more regular expression pattern character class definitions from a supercluster character class memory and a payload buffer configured to store a given payload from an HNA packet data memory. The at least one HNA instruction may include an identifier for a location of the given payload in the HNA packet data memory. Each of the plurality of HPUs in the plurality of clusters of the plurality of superclusters may further include a top-of-stack register configured to store a single HNA job, a running stack configured to store multiple HNA jobs, and a unified memory configured to store first contents of a save stack and second contents of a match result buffer. The first content may include one or more HNA jobs stored in the run stack, and the second content may include one or more final match results. Each of the plurality of HPUs in the plurality of clusters of the plurality of superclusters may further include an HNA processing core operatively coupled to the node cache, the character class cache, the payload buffer, the top-of-stack register, the run stack, and the unified memory. The HNA processing core may be configured to walk at least one per-pattern NFA, wherein a plurality of payload segments are stored in the payload buffer, to determine a match of the at least one regular expression pattern.

Each supercluster may further include a supercluster graph memory dedicated to the corresponding supercluster. The at least one HNA processor may further include an HNA on-chip graph memory shared by the multiple superclusters. The security device may further include at least one system memory configured to include an HNA off-chip graph memory shared by the multiple superclusters. The selected given HPU may be configured to walk multiple nodes of a given pattern NFA in at least one per-pattern NFA according to multiple segments of a payload of the input stream based on the at least one assigned HNA instruction. The walked nodes may be stored in a node cache dedicated to the selected given HPU, the supercluster graph memory, the HNA on-chip graph memory, the HNA off-chip graph memory, or a combination thereof.

The multiple HPUs of the multiple clusters of the selected at least one super cluster may form an HPU resource pool that the HNA scheduler may use to select to enable the matched acceleration.

Another example embodiment disclosed herein includes a super nondeterministic finite automaton (HNA) processor dedicated to nondeterministic finite automaton (NFA) processing. The HNA processor may include multiple superclusters. Each supercluster may include multiple clusters. Each of the multiple clusters may include multiple HNA processing units (HPUs). The HNA processor may further include an HNA on-chip instruction queue configured to store at least one HNA instruction. The multiple HPUs of the multiple clusters of the at least one supercluster may form an HPU resource pool that can be used to allocate the at least one HNA instruction. The HNA processor may further include an HNA scheduler configured to select a given HPU in the formed resource pool and assign the at least one HNA instruction to the selected given HPU to initiate matching of at least one regular expression pattern in an input stream received from a network.

Another example embodiment disclosed herein includes a method corresponding to operations consistent with the embodiments disclosed herein.

Further, yet another example embodiment may include a non-transitory computer-readable medium having stored thereon sequences of instructions that, when loaded and executed by a processor, cause the processor to perform the methods disclosed herein.

BRIEF DESCRIPTION OF THE DRAWINGS

The foregoing will be apparent from the following more particular description of example embodiments of the invention, as illustrated in the accompanying drawings in which like reference characters refer to the same parts throughout the different views. The drawings are not necessarily to scale, emphasis instead being placed upon illustrating embodiments of the invention.

FIG. 1A is a block diagram of an example embodiment of an engine architecture for finite automaton processing.

FIG. 1B is a block diagram of an example embodiment of a hyper-nondeterministic automaton (HNA) processor.

FIG. 1C is a block diagram of an example embodiment of a security device including an example embodiment of an HNA processor.

FIG. 1D is a block diagram of another example embodiment of an HNA processor.

IE is a block diagram of an example embodiment of at least one system memory.

FIG. 1F is a flow chart of an example embodiment of a method.

FIG. 1G is a block diagram of an example embodiment of a security device in which embodiments disclosed herein may be implemented.

2A-2G are example NFA and DFA graphs and tables illustrating the concept of graph explosion.

3A is a block diagram of an embodiment of a security device in which embodiments disclosed herein may be implemented.

3B is a flow diagram of an example embodiment of a method that may be implemented in at least one processor operatively coupled to at least one memory within a security device operatively coupled to a network.

4A is a block diagram of an example embodiment of an HNA processing unit (HPU).

4B is a block diagram of an example embodiment of a context that may be stored or retrieved according to embodiments disclosed herein.

5A is a block diagram of an example embodiment of a per-pattern nondeterministic finite automaton (NFA) graph that a walker may use to match regular expression patterns in an input stream.

5B is a table of an example embodiment of processing cycles for walking the per-mode NFA graph of FIG. 5A according to payload.

6 is a block diagram of an example embodiment of an environment for a walker.

7A is a block diagram of an example embodiment of an environment for a compiler.

7B is a block diagram of an example embodiment of an HNA processing core operatively coupled to multiple memories mapped to multiple levels in a memory hierarchy.

8 is a block diagram of an example embodiment of a node distribution of multiple per-pattern NFAs.

9 is a flow diagram of an example embodiment of a method that may be implemented in at least one processor operatively coupled to memory mapped to multiple levels of a memory hierarchy within a secure device operatively coupled to a network.

10 is a block diagram of an example embodiment of another node distribution of nodes of multiple per-pattern NFAs.

11 is a flow diagram of an example embodiment of a method for distributing nodes of at least one per-pattern NFA.

12 is a flow diagram of another example embodiment of a method that may be implemented in at least one processor operatively coupled to memory mapped to multiple levels of a memory hierarchy within a secure device operatively coupled to a network.

13A is a flow diagram 1300 of an example embodiment of a method that may be implemented in at least one processor operatively coupled to a plurality of memories in a memory hierarchy and a node cache within a security device operatively coupled to a network.

13B is a block diagram of an example embodiment of a payload and segments within the payload with corresponding offsets.

13C is a table of an example embodiment of a processing cycle for walking the per-pattern NFA graph of FIG. 5A according to the payload of FIG. 13B by selecting a lazy path at a split node.

FIG13D is a table that is a continuation of the table in FIG13C.

14 is a block diagram of an example internal structure of an optional computer within embodiments disclosed herein.

DETAILED DESCRIPTION

According to an embodiment of the present disclosure, an engine architecture for finite automaton processing may include a super non-deterministic automaton (HNA) processor that provides hardware acceleration for non-deterministic finite automaton (NFA) processing. The HNA processor may be a coprocessor complementary to a super finite automaton (HFA) coprocessor. The HFA processor may provide hardware acceleration for deterministic finite automaton (DFA) processing. HNA and HFA may be regular expression processors that may be used for deep packet inspection applications, such as intrusion detection/prevention (IDP), packet classification, server load balancing, web switching, storage array network (SAN), firewall load balancing, virus scanning, or any other suitable deep packet inspection applications. HNA and HFA may offload the heavy burden of performing computational and memory-intensive pattern matching processes from a general-purpose central processing unit (CPU).

FIG1A is a block diagram 150 of an example embodiment of an engine architecture for finite automata processing. According to this example embodiment, at least one CPU core 103 can be operatively coupled to at least one HFA processor 110 and at least one HNA processor 108. The operative coupling can include coupling via a bus, an interrupt, a mailbox, one or more circuit elements, a communication path, a communication coupling, or any other suitable manner. At least one HFA processor 110 can be dedicated to DFA processing, and at least one HNA processor 108 can be dedicated to NFA processing. The at least one CPU core 103, the at least one HFA processor 110, and the at least one HNA processor 108 can be configured to share a level 2 cache (L2C) 113.

At least one CPU core 103, at least one HNA processor 108, and at least one HFA processor 110 can each be operatively coupled to L2C 113 via coherent paths 115a, 115b, and 115c, respectively. These paths can be separate coherent memory buses, a single shared coherent memory bus, separate coherent communication channels, a shared coherent communication channel, or any other suitable coherent paths. An L2C memory controller (not shown) can use L2C 113 to maintain memory reference coherence for memory accesses via coherent paths 115a, 115b, and 115c. For example, if at least one HNA processor 108 accesses a given memory location via coherent path 115b, memory reference coherence can be maintained by invalidating a data copy of the contents read from the given memory location by at least one CPU core 103. Invalidating the data copy enables at least one CPU core 103 or at least one HFA processor 110 to obtain the value of the most recent update made by at least one HNA processor 108 to the given memory location.

The example embodiment may further include at least one local memory controller (LMC) 117, which may be operatively coupled to the L2C 113 and configured to manage various accesses, such as reading, writing, loading, storing, or any other suitable access to or from the at least one system memory 151. Thus, access by the at least one CPU core 103, the at least one HNA processor 108, or the at least one HFA processor 110 to a location in the at least one system memory 151 via the coherent paths 115a, 115b, and 115c enables the at least one CPU core 103, the at least one HFA processor 110, and the at least one HNA processor 108 to maintain a common value for the accessed location.

Furthermore, as described below with reference to FIG1B and FIG4A , the at least one HNA processor 108 may include multiple HNA processing units (HPUs), each of which includes at least one HNA processing core. Thus, access via the coherent paths 115 a or 115 b enables each of the at least one CPU core in the at least one CPU core 103 and each of the at least one HNA processing core in each of the HPUs of the at least one HNA processor 108 to maintain memory reference coherency. These HPUs may be concurrent HPUs capable of achieving an overall performance of at least 20 Gbps for the at least one HNA processor 108.

Returning to FIG1A , at least one HFA processor 110 and at least one HNA processor 108 may be operatively coupled to LMC 117 via non-coherent paths 119 a and 119 b, respectively, thereby enabling at least one HFA processor 110 and at least one HNA processor 108 to bypass L2C 113 to reduce memory access latency and thereby improve matching performance. According to embodiments disclosed herein, non-coherent path 119 a may enable HNA processor 108 to directly access at least one system memory 151 via LMC 117, thereby bypassing LC2 113 based on the specific partition or location of at least one system memory 151 accessed by HNA processor 108.

For example, from the perspective of HNA processor 108, if a specific partition or location of at least one system memory 151 includes read-only content, non-coherent path 119a can be used because maintaining access-based consistency is not an issue. Such read-only content can include graph memory content, such as one or more nodes of at least one NFA graph (not shown) that HNA processor 108 can use to match regular expressions in an input stream. Accessing at least one system memory 151 via non-coherent path 119a to bypass L2C 113 can improve matching performance of at least one HNA processor 108 by avoiding delays that would otherwise be incurred to maintain access consistency. Furthermore, because read-only content can advantageously include one or more nodes of at least one NFA graph that may not have temporal or spatial locality, as disclosed below with reference to FIG. 13D , accessing such one or more nodes via non-coherent path 119a can achieve another advantage because such access will not pollute existing contents of L2C 113.

FIG1B is a block diagram 155 of an example embodiment of an HNA processor 108. As disclosed above with reference to FIG1A , the HNA processor 108 can be dedicated to NFA processing. The HNA processor 108 can include multiple superclusters, such as superclusters 121a and 121b. Each supercluster can include multiple clusters, such as clusters 123a and 123b of supercluster 121a and clusters 123c and 123d of supercluster 121b. Each of the multiple clusters 123a-d can include multiple HNA processing units (HPUs), such as HPUs 125a and 125b of cluster 123a, HPUs 125c and 125d of cluster 123b, HPUs 125e and 125f of cluster 123c, and HPUs 125g and 125h of cluster 123d. Each of the HPUs 125a-f can have an architecture as disclosed below with reference to FIG4A . The HNA processor 108 may further include an HNA on-core instruction queue 154 that may be configured to store at least one HNA instruction 153 that may be dispatched to a given one of the HPUs 125a-f.

Dispatching at least one HNA instruction 153 may include writing to a specific doorbell register configured to trigger a given HPU in the plurality of HPUs to begin a graphics walk using information associated with an HNA instruction disclosed below with reference to FIG4A . Dispatching may include triggering an interrupt associated with the given HPU, or dispatching in any other suitable manner.

The HNA on-chip instruction queue 154 can be maintained as a linked list of HNA instruction blocks or in any other suitable manner. Each HNA instruction block can include a programmable number of fixed-length HNA instructions. Software can allocate instruction blocks that can be released by the HPU. An HNA instruction block can be followed by a 64-bit word that can include a next block pointer link. A given HPU can be configured to read the next block pointer once a doorbell count associated with the given HPU indicates that the last HNA instruction in an instruction block contains a valid HNA instruction. The given HPU can read words from the instruction queue, for example, starting with the head pointer, and based on processing the last instruction in the instruction block, the given HPU can use the next block pointer link to traverse to the next instruction block. In this way, when the last HNA instruction in a block is deactivated, the given HPU can automatically release the deactivated memory block back to the management pool. The next block pointer can be the next 64-bit word following the last HNA instruction in the instruction block. The next block pointer may specify a next block pointer (forward chaining) to enable the given HPU to locate the next instruction that may be stored within the at least one system memory 151 .

To insert an HNA instruction into the HNA on-chip instruction queue 154, software may write the HNA instruction to a tail pointer maintained by the software and then write the total number of HNA instructions to be added to the HNA on-chip instruction queue 154 to a given HNA doorbell count register. Writes to the given HNA doorbell count register may be cumulative and reflect the total number of pending HNA instructions. When the given HPU deactivates an instruction, the corresponding HNA doorbell count register may be automatically decremented. The given HPU may be configured to continue processing HNA instructions until all pending requests have been serviced, e.g., until the associated cumulative doorbell count register reaches zero.

According to embodiments disclosed herein, the plurality of HPUs 125a-d of the plurality of clusters 123a and 123b of at least one selected super cluster 121a from the plurality of super clusters 121a and 121b may form an HPU resource pool 127 that may be used to allocate at least one HNA instruction 153. The HNA processor 108 may further include an HNA scheduler 129 that may be configured to select a given HPU (e.g., HPU 125b) from the formed HPU resource pool 127, and the HNA scheduler 129 may allocate the at least one HNA instruction 153 to the selected given HPU 125b to initiate matching of at least one regular expression pattern (not shown) in an input stream (not shown) received from a network (not shown). The plurality of HPUs 125a-d that form the HPU resource pool 127 that the HNA scheduler 129 may select may enable accelerated matching.

It should be understood that HNA components referred to herein as "on-chip" refer to components that can be integrated on a single chip substrate of the HNA processor 108, and that the total numbers shown for superclusters, clusters, or HPUs are for illustrative purposes, and any suitable total number may be used. For example, a first total number of the plurality of superclusters may be at least two, a second total number of the plurality of clusters may be at least two, and a third total number of the plurality of HPUs may be at least ten.

FIG1C is a block diagram 157 of an embodiment of a security device 102 including an example embodiment of an HNA processor 108. The security device 102 can be operatively coupled to a network (not shown). The network can be a wide area network (WAN), a local area network (LAN), a wireless network, or any other suitable network. The security device 102 can include at least one CPU core 103 and at least one HNA processor 108 operatively coupled to the at least one CPU core 103 disclosed above with reference to FIG1A . The at least one HNA processor 108 can be dedicated to nondeterministic finite automaton (NFA) processing.

According to embodiments disclosed herein, at least one HNA processor 108 may include multiple superclusters, such as superclusters 121a and 121b disclosed above. Each supercluster may include multiple clusters, such as clusters 123a and 123b of supercluster 121a and clusters 123c and 123d of supercluster 121b. Each of the multiple clusters 123a-d may include multiple HNA processing units (HPUs), such as HPUs 125a and 125b of cluster 123a, HPUs 125c and 125d of cluster 123b, HPUs 125e and 125f of cluster 123c, and HPUs 125g and 125h of cluster 123d. At least one CPU core 103 may be configured to select at least one supercluster from the multiple superclusters 121a and 121b, such as supercluster 121a, when submitting an instruction to the HNA processor 108.

The at least one HNA processor 108 may include an HNA on-chip instruction queue 154 configured to store at least one HNA instruction 153. The at least one HNA processor 108 may include an HNA scheduler 129. The HNA scheduler 129 may be configured to select a given HPU 125b from the plurality of HPUs 125a-d in the plurality of clusters 123a and 123b of the selected at least one super cluster 121a and assign the at least one HNA instruction 153 to the given HPU 125b to initiate matching of at least one regular expression pattern (not shown) in an input stream (not shown) received from a network (not shown).

FIG1D is a block diagram 158 of another example embodiment of an HNA processor 108. According to this example embodiment, each supercluster may further include a supercluster graph memory 156a specific to the corresponding supercluster. For example, supercluster graph memory 156a may be specific to supercluster 121a. Supercluster graph memory 156a is accessible to the corresponding HPUs of the corresponding clusters of the corresponding supercluster (e.g., the HPUs 125a-d of clusters 123a and 123b) and may be configured to statically store a subset of nodes (not shown) of at least one per-pattern NFA (not shown) (such as per-pattern NFA 314 described below with reference to FIG3A). The subset of nodes may be determined by a compiler (not shown), such as compiler 306 described below with reference to FIG3A, which may determine a node distribution, such as the node distribution described below with reference to FIG7A and FIG8. Supercluster graph memory 156a may be configured to store multiple types of NFA nodes. NFA nodes of different node types may be configured with a given size, thereby enabling multiple nodes of multiple node types to have the same node size.

According to embodiments disclosed herein, each super cluster may further include at least one super cluster character class memory 135 that is specific to the corresponding super cluster. For example, the at least one super cluster character class memory 135 may be specific to the corresponding super cluster 121a. Each at least one super cluster character class memory may be configured to statically store a plurality of regular expression pattern character class definitions (not shown). The stored regular expression pattern character class definitions may be used to match at least one regular expression pattern in an input stream. The at least one super cluster character class memory 135 may be shared by the corresponding plurality of HPUs 125a-d of the corresponding plurality of clusters 123a and 123b of the corresponding super cluster 121a. According to another embodiment, the super cluster graph memory 156a and the at least one super cluster character class memory 135 may be unified.

According to embodiments disclosed herein, each at least one HNA instruction 153 may specify a graph identifier for specifying which per-pattern NFA to use for matching at least one regular expression. According to one embodiment, a compiler (such as compiler 306 of FIG. 3A ) may distribute the nodes of each per-pattern NFA so that the given per-pattern NFA is specific to the given supercluster by storing the nodes of the given per-pattern NFA in a memory specific to the given supercluster.

In this manner, at least one HNA instruction 153 can be assigned based on a unique graph identifier associated with a given per-pattern NFA specified by the at least one HNA instruction 153 to traverse (i.e., walk) payload segments to match at least one regular expression pattern. In this manner, HPU selection can be limited to HPUs of a given supercluster. Within the given supercluster, because the clusters of the given supercluster access a shared unified supercluster graph memory, a given HPU of the given supercluster can be selected based on round-robin scheduling of each HPU of the given cluster, transient loading, a combination of the above, or in any other suitable manner.

For example, the graph identifier can be associated with a given per-pattern NFA in a plurality of per-pattern NFAs, such as NFA 314 of FIG. 3A . Thus, a given set of patterns can share the same graph identifier. For example, all patterns in rule set 310 of FIG. 3A can share the same graph identifier. In some cases, there can be multiple rule sets similar to rule set 310 in the system. In that case, each separate “rule set” can have a unique graph identifier. The graph identifier can be associated with at least one node (not shown) of the given per-pattern NFA and can be stored in a supercluster graph memory 156a that can be specific to a given supercluster 121a of the plurality of superclusters 121a and 121b, such as supercluster graph memory 156a specific to supercluster 121a. The graph identifier can be associated with a set of patterns. At least one CPU core 103 may select a given super cluster 121a of the plurality of super clusters 121a and 121b based on determining that at least one node of a given per-pattern NFA 314 associated with the graph identifier is stored within a super cluster graph memory 156a specific to the given super cluster 121a.

Thus, at least one CPU core 103 may be further configured to select the at least one super cluster (such as super cluster 121a) from the plurality of super clusters 121a and 121b by limiting the super cluster selection based on a graph identifier (not shown) associated with at least one HNA instruction 153. For example, the graph identifier may be associated with a given per-mode NFA from the plurality of per-mode NFAs, and limiting the super cluster selection may include determining that at least one node of the given per-mode NFA is stored within a super cluster graph memory 156a that is dedicated to the at least one super cluster 121a. The at least one CPU core 103 may select at least one super cluster 121a from the plurality of super clusters 121a and 121b based on determining that at least one node of the given per-mode NFA associated with the graph identifier is stored within a super cluster graph memory 156a that is dedicated to the super cluster 121a.

According to embodiments disclosed herein, the HNA scheduler 129 may be configured to select a given HPU, such as HPU 125b in FIG. 1C , from a restricted set of HPUs that may include each of the plurality of HPUs in each of the plurality of clusters selected from the at least one super cluster (e.g., the plurality of HPUs 125a-d in the plurality of clusters 123a and 123b in the plurality of super clusters selected from the super cluster 121a). The HNA scheduler 129 may be configured to select the given HPU 125b from the restricted set of HPUs that may include the HPUs 125a-d based on round-robin scheduling of the HPUs 125a-d in the restricted set of HPUs, instantaneous loading of each of the HPUs 125a-d in the restricted set of HPUs, a combination thereof, or based on any other suitable scheduling strategy.

According to another embodiment disclosed herein, a compiler (such as compiler 306 of FIG. 3A , disclosed below) can replicate one or more nodes of a given per-pattern NFA in at least one per-pattern NFA in multiple supercluster graph memories, each supercluster graph memory being dedicated to a corresponding supercluster. In this manner, at least one HNA instruction 153 can be assigned or scheduled to any HPU in any cluster of any supercluster of the HNA processor 108. The HPU can be selected based on instantaneous load at a particular supercluster (or cluster within a supercluster) or based on the cycle scheduling of the HPUs in the multiple clusters of the multiple superclusters of the HNA processor 108. This may be the case if maximum throughput for each per-pattern NFA is desired. However, according to an alternative exemplary embodiment, when each supercluster graph memory of the multiple superclusters of the HNA processor 108 contains replicated per-pattern NFA nodes, such a configuration can limit the total number of per-pattern NFAs supported by the total number of superclusters of the HNA processor 108.

For example, according to an alternative exemplary embodiment, the compiler 306 may configure each super-cluster graph memory to store at least one node of at least one per-mode NFA in the plurality of per-mode NFAs to replicate the at least one node in each super-cluster graph memory of each super-cluster of the at least one HNA processor. In this manner, the at least one CPU core 103 may provide the HNA scheduler 129 with an option to select the at least one super-cluster based on determining to replicate a given per-mode NFA in the at least one per-mode NFA associated with the at least one HNA instruction.

Thus, instead of at least one CPU core 103 selecting an alternative to at least one super cluster, the HNA scheduler 129 may select at least one super cluster based on the provided option, such as super cluster 121a in FIG1C . For example, if the provided option instructs the HNA scheduler 129 to select at least one super cluster, the HNA scheduler 129 may select the at least one super cluster based on the provided option and (i) a first round-robin schedule of the plurality of super clusters, (ii) a first instantaneous load of the plurality of super clusters, or (ii) a combination of (i) and (ii). The HNA scheduler 129 may then select a given HPU 125b from among the plurality of HPUs 125a-d in the plurality of clusters 123a and 123b of the at least one super cluster 121a selected by the HNA 129 based on a second round-robin scheduling of the plurality of HPUs 125a-d in the plurality of clusters 123a and 123b of the at least one super cluster 121a selected by the HNA 129, a second transient loading of the plurality of HPUs 125a-d in the plurality of clusters 123a and 123b of the at least one super cluster 121a selected by the HNA 129, or a combination thereof.

Returning to FIG. 1D , the at least one HNA processor 129 may further include an HNA on-chip graph memory 156 b accessible to the multiple HPUs of the multiple clusters of the multiple superclusters (e.g., the multiple HPUs 125 a-h of the multiple clusters 123 a-d of the multiple superclusters 121 a and 121 b of FIG. 1C ). The HNA on-chip graph memory 156 b may be configured to statically store a subset of nodes (not shown) of at least one per-pattern NFA (not shown). The subset of nodes may be determined by a compiler (e.g., compiler 306 of FIG. 3A for the at least one per-pattern NFA 314), which may determine a node distribution, such as the node distribution disclosed below with reference to FIG. 7A and FIG. 8 . The HNA on-chip graph memory 156 b may be configured to store multiple types of NFA nodes. NFA nodes of different node types may be configured with a given size, thereby enabling multiple nodes of multiple node types to have the same node size.

1C , the at least one HNA instruction 153 may be a first at least one HNA instruction, and the security device 102 may further include at least one system memory, such as the at least one system memory 151 in FIG. 1A , which may be operatively coupled to the at least one CPU core 103 and the at least one HNA processor 108 .

FIG1E is a block diagram 160 of an example embodiment of at least one system memory 151. According to embodiments disclosed herein, at least one system memory (such as the at least one system memory 151 described above with reference to FIG1A ) can be configured to include an HNA on-chip instruction queue 163 for storing a second at least one HNA instruction (not shown). The second at least one HNA instruction can be transferred to the HNA on-chip instruction queue 154 of the HNA processor 108 pending transmission. The at least one system memory 151 can further include an HNA off-chip graph memory 156 c configured to statically store a subset of nodes (not shown) of at least one per-pattern NFA (not shown). The subset of nodes can be determined by a compiler of the at least one per-pattern NFA (such as compiler 306 of FIG3A for at least one per-pattern NFA 314), which can determine a node distribution, such as the node distribution described below with reference to FIG7A and FIG8 . The HNA off-chip graph memory 156 c can be configured to store multiple types of NFA nodes. NFA nodes of different node types can be configured with a given size, thereby enabling multiple nodes of multiple node types to have the same node size.

According to embodiments disclosed herein, the security device 102 of FIG. 1C may further include an L2C 113, at least one LMC 117, and at least one system memory 151 of FIG. The at least one LMC 117 may be operatively coupled to the at least one HNA processor 108 and the at least one system memory 151. A given LMC of the at least one LMC may be configured to enable access to the at least one system memory 151 so that the at least one HNA processor 108 can access the HNA off-chip graphics memory 156 c. Bypassing the L2C 113 via the non-coherent path 119 a may improve the matching performance of the at least one HNA processor 108 by avoiding delays that would otherwise be incurred by maintaining coherency in accesses to the HNA off-chip graphics memory 156 c via the coherent path 115 b. Because nodes stored in the HNA off-chip graphics memory 156 c may not have temporal or spatial locality and because access to such stored nodes is read-only from the perspective of at least one HNA processor 108, accessing the HNA off-chip graphics memory 156 c via the non-coherent path 119 a may achieve yet another advantage in that such access will not pollute the existing contents of the L2C 113.

Returning to FIG. 1E , the at least one system memory 151 can be further configured to include an HNA packet data memory 165 that can be configured to contiguously store a plurality of payloads. Each of the plurality of payloads can have a fixed maximum length, such as 1536 bytes or any other suitable fixed maximum length. Each of the plurality of payloads can be associated with a given HNA instruction from among the first at least one HNA instruction stored in the HNA on-chip instruction queue 154 or the second at least one HNA instruction that can be stored in the HNA off-chip instruction queue 163 and pending transmission to the HNA on-chip instruction queue 154.

According to embodiments disclosed herein, the at least one system memory 151 may be further configured to include an HNA input stack partition 161 configured to store at least one HNA input stack. Each at least one HNA input stack may be configured to store at least one HNA input job for at least one HPU of the plurality of HPUs of the plurality of clusters of the plurality of superclusters, such as the plurality of HPUs 125a-h of the plurality of clusters 123a-d of the plurality of superclusters 121a and 121b of the HNA processor 108 disclosed above.

The at least one system memory 151 may further include an HNA off-chip runtime stack partition 167 that may be configured to store at least one off-chip runtime stack to extend the storage of the at least one on-chip runtime stack, such as runtime stack 460 disclosed below with reference to FIG4A . Each of the at least one on-chip runtime stacks may be configured to store at least one runtime HNA job for a corresponding HPU, such as HPU 425, as disclosed below with reference to FIG4A .

The at least one system memory 151 may further include an HNA off-chip save buffer partition 169 that may be configured to extend storage of at least one on-chip save buffer, such as save buffer 464 disclosed below with reference to FIG4A . The on-chip save buffer may be configured to store at least one runtime HNA job for a corresponding HPU, such as HPU 425, based on detection of a payload boundary, as disclosed below with reference to FIG4 .

At least one system memory 151 may further include an HNA off-chip result buffer partition 171 that may be configured to store at least one final match result entry of a match result buffer, such as match result buffer 466 disclosed below with reference to FIG. 4A . The at least one final match result may be a final match of at least one regular expression pattern determined by at least one HPU to match in the input stream. Each at least one HNA instruction that may be stored in the HNA on-chip instruction queue 154 or the HNA off-chip instruction queue 163 may identify a given HNA input stack of the HNA input stack partition 161, a given HNA off-chip run stack of the HNA off-chip run stack partition 167, a given HNA off-chip save buffer of the HNA off-chip save buffer partition 169, and a given HNA off-chip result buffer of the HNA off-chip result buffer partition 171.

1A , a given LMC in the at least one LMC 117 may be configured to enable the at least one HNA processor 108 to access the HNA packet data memory 165, the HNA input stack partition 161, the HNA off-chip instruction queue 163, the HNA off-chip run stack partition 167, the HNA off-chip save buffer partition 169, and the HNA off-chip result buffer partition 171 via the coherent path 115 b, and may be configured to enable the at least one HNA processor 108 to access the HNA off-chip graphics memory 156 c via the non-coherent path 119 a.

1E , HNA input stack partition 161 may include HNA jobs that may be new HNA jobs generated by DFA processing. As disclosed above, at least one HNA processor 108 may be complementary to an HFA processor 110 that provides hardware acceleration for deterministic finite automaton (DFA) processing as disclosed below with reference to FIG. 1G .

Figure 1F is a flowchart (180) of an example embodiment of a method. The method may begin (182) and include a plurality of superclusters in at least one HNA processor operatively coupled to at least one CPU core and dedicated to non-deterministic finite automaton (NFA) processing (184). The method may include a plurality of clusters in each supercluster (186). The method may include a plurality of HNA processing units (HPUs) in each of the plurality of clusters (188). The method may select at least one supercluster from the plurality of superclusters (190). The method may select a given HPU from a plurality of HPUs in the plurality of clusters of the selected at least one supercluster (192). The method may assign at least one HNA instruction to the selected given HPU to initiate matching of at least one regular expression pattern in an input stream received from a network (194), and in this example embodiment, the method may then end.

FIG1G is a block diagram of another example embodiment of the security device 102 disclosed above, in which the embodiments disclosed herein may be implemented. The security device 102 may include a network services processor 100. The security device 102 may be a standalone system that can switch packets received on one network interface 107a to another network interface 107b and perform multiple security functions on the received packets before forwarding them. For example, the security device 102 may be configured to perform security processing on packets 101a that may be received on a wide area network (WAN) 105a, or any other suitable network, before forwarding the processed packets 101b to a local area network (LNA) 105b, or any other suitable network.

The network service processor 100 can be configured to process the open systems interconnection (OSI) network L2-L7 layer protocols encapsulated in the received data packets. As is well known to those skilled in the art, the open systems interconnection (OSI) reference model defines seven network protocol layers (L1-L7). The physical layer (L1) represents the actual interface that connects the device to the transmission medium, including the electrical interface and the physical interface. The data link layer (L2) performs data framing. The network layer (L3) formats the data into data packets. The transport layer (L4) handles end-to-end transmission. The session layer (L5) manages communication between devices, for example, whether the communication is half-duplex or full-duplex. The presentation layer (L6) manages data formatting and presentation, for example, syntax, control codes, special graphics and character sets. The application layer (L7) allows communication between multiple users, for example, file transfer and email.

The network services processor 100 can schedule and queue work (e.g., packet processing operations) for higher-level network protocols (e.g., L4-L7) and can perform higher-level network protocol processing on received packets to be executed, thereby forwarding the packets at line speed. By processing these protocols to forward these packets at line speed, the network services processor 100 does not reduce the network data transmission rate. The network services processor 100 can receive packets from a network interface 107a or 107b, which can be a physical hardware interface, and can perform L2-L7 network protocol processing on the received packets. The network services processor 100 can subsequently forward the processed packet 101b through the network interface 107a or 107b to another hop in the network, a final destination, or via another bus (not shown) for further processing by a host processor (not shown). Network protocol processing can include processing of network security protocols such as firewalls, application firewalls, virtual private networks (VPNs) including IP Security (IPSec) and/or Secure Sockets Layer (SSL), intrusion detection systems (IDS) and antivirus (AV), or any other suitable network protocols.

The network services processor 100 can use multiple processors (i.e., cores) (such as the at least one CPU core 103 disclosed above) to produce high application performance. Each of these cores (not shown) can be dedicated to performing data plane operations, control plane operations, or a combination thereof. Data plane operations can include packet operations to forward packets. Control plane operations can include processing multiple parts of complex high-level protocols, such as Internet Protocol Security (IPSec), Transmission Control Protocol (TCP), Secure Sockets Layer (SSL), or any other suitable high-level protocol. Data plane operations can include processing other parts of these complex high-level protocols.

The network services processor 100 may also include special purpose coprocessors that can offload cores to enable high throughput for the network services processor 100. For example, the network services processor 100 may include an acceleration unit 106 that may include an HNA processor 108 for hardware acceleration of NFA processing and an HFA processor 110 for hardware acceleration of DFA processing. The HNA processor 108 and the HFA processor 110 may be coprocessors configured to offload the heavy burden of executing computationally and memory-intensive pattern matching methods from the general purpose cores of the network services processor 100 (such as the at least one CPU core 103 disclosed above).

The network services processor 100 can perform pattern searching, regular expression processing, content validation, transformation, and security to accelerate packet processing. Regular expression processing and pattern searching can be used to perform string matching for AV and IDS applications, as well as other applications that may require string matching. A memory controller (not shown) in the network services processor 100 can control access to a memory 104 operatively coupled to the network services processor 100. The memory 104 can be internal (i.e., on-chip) or external (i.e., off-chip), or a combination thereof, and can be configured to store received packets, such as packet 101a for processing by the network services processor 100. The memory 104 can be configured to store compiled rule data, which is used for lookups and pattern matching in DFA and NFA graph expression searches. The compiled rule data can be stored as a binary image 112, which can include compiled rule data for both DFA and NFA, or multiple binary images that separate DFA compiled rule data from NFA compiled rule data.

As disclosed above, typical content-aware application processing can use either DFA or NFA to identify patterns in the content of received data packets. Both DFA and NFA are finite state machines, i.e., computational models, each of which includes a set of states, a start state, an input alphabet (the set of all possible symbols), and a transition function. The computation begins in the start state and changes to a new state depending on the transition function.

Patterns are typically expressed using regular expressions, which include basic elements such as normal text characters like A-Z and 0-9, and metacharacters like *, ^, and |. The basic element of a regular expression is the symbol (a single character) to be matched. The basic element can be combined with the symbols to allow concatenation, alternation (|), and the Kleene asterisk (*). The metacharacters for concatenation can be used to create multiple character matching patterns from a single character (or substring), while the metacharacters for alternation (|) can be used to create a regular expression that can match any one of two or more substrings. The metacharacter Kleene asterisk (*) allows the pattern to match any number of times, including characters or strings that do not appear before.

Combining different operators with single characters allows building complex subpatterns of expressions. For example, a subpattern like (th(is|at)*) can match multiple strings like: th, this, that, thisis, thisat, thatis, or thatat. Another example of a complex pattern of expression could be one that incorporates a character class construct […] that allows listing a list of characters to be searched for. For example, gr[ea]y looks for both grey and gray. Other examples of complex subpatterns are those that can use dashes to indicate ranges of characters, for example, [A-Z], or "." which can match any character. The elements of a pattern can be basic elements or a combination of one or more basic elements combined with one or more metacharacters.

The input to a DFA or NFA state machine typically includes multiple segments from an input stream (i.e., received data packets), such as strings of (8-bit) bytes, i.e., letters can be single bytes (one character or symbol). Each segment (e.g., byte) in the input stream can produce a transition from one state to another. The states and transition functions of a DFA or NFA state machine can be represented by a node graph. Each node in the graph can represent a state, and the arcs in the graph (also referred to herein as transitions or transition arcs) can represent state transitions. The current state of the state machine can be represented by a node identifier that selects a specific byte in the graph.

Use DFA to process regular expression and find the feature of one or more patterns described by regular expression in the input stream of character and can be characterized in that and has definite running time performance.Because there is only a state transition in every DFA state, the next state of DFA can be determined from the current state of input character (or symbol) and DFA.Like this, the running time performance of DFA is considered to definite and behavior can be fully predicted from input.Yet the compromise of certainty is a graph, and wherein, the quantity (or graph size) of node can be exponentially increased along with the size of pattern.

In contrast, the number of nodes in an NFA graph can be characterized as growing linearly with the size of the pattern. However, using an NFA to process regular expressions and discover one or more patterns described by the regular expression in an input stream of characters can be characterized by having non-deterministic runtime performance. For example, given an input character (or symbol) and the current state of the NFA, there may be more than one next state of the NFA to transition to. Thus, the next state of the NFA cannot be uniquely determined from the input and the current state of the NFA. Thus, when the behavior cannot be fully predicted from the input, the runtime performance of the NFA is considered to be non-deterministic.

Figures 2A to 2G illustrate the concept of a DFA "graph explosion." Figures 2A, 2B, and 2C respectively illustrate NFA graphs for the patterns ".*a[^\n]," ".*a[^\n][^\n]," and ".*a[^\n][^\n][^\n]," and Figures 2D, 2E, and 2F respectively illustrate DFA graphs for the same patterns. As shown in Figures 2A to 2F and summarized in the table of Figure 2G, for certain patterns, while the DFA for the same pattern may grow exponentially, the NFA may grow linearly, causing a graph explosion. As shown, for one or more given patterns, the number of DFA states may be greater than the number of NFA states, typically on the order of several hundred or more or a thousand or more states. This is an example of a "graph explosion," a hallmark characteristic of a DFA.

According to embodiments disclosed herein, content searches may be performed using DFA, NFA, or a combination thereof. According to one embodiment, a runtime processor, a coprocessor, or a combination thereof may be implemented in hardware and may be configured to implement a compiler and a walker.

The compiler can compile a pattern or an input list of patterns (also referred to as signatures or rules) into a DFA, NFA, or a combination thereof. The DFA and NFA can be binary data structures such as DFA and NFA graphs and tables.

The walker can perform runtime processing, that is, the action of identifying the existence of a pattern in an input stream or matching the pattern with the content in the input stream. The content can be the payload portion of an Internet Protocol (IP) datagram, or any other suitable payload in the input stream. The runtime processing of a DFA or NFA graph can be referred to as walking the DFA or NFA graph according to the payload to determine pattern matching. A processor configured to generate a DFA, NFA, or a combination thereof can be referred to as a compiler here. A processor configured to use the generated DFA, NFA, or a combination thereof to implement runtime processing of a payload can be referred to as a walker here. According to the embodiments disclosed herein, the network service processor 100 can be configured to implement a compiler and a walker in the security device 102.

FIG3A is a block diagram of another embodiment of a security device 102 in which embodiments disclosed herein may be implemented. As disclosed with reference to FIG1G , the security device 102 may be operatively coupled to one or more networks and may include a memory 104 and a network services processor 100 that may include an acceleration unit 106. Referring to FIG3A , the network services processor 100 may be configured to implement a compiler 306 that generates a binary image 112 and a walker 320 that uses the binary image 112. For example, the compiler 306 may generate the binary image 112 including compiled rule data that the walker 320 uses to perform a pattern matching method on a received data packet 101a (shown in FIG1G ). According to embodiments disclosed herein, the compiler 306 may generate the binary image 112 by determining compiled rule data for a DFA or NFA based on at least one heuristic method as further described below. The compiler 306 may determine rule data that is advantageously applicable to both the DFA and the NFA.

According to embodiments disclosed herein, compiler 306 may generate binary image 112 by processing rule set 310, which may include a set 304 of one or more regular expression patterns and optional qualifiers 308. From rule set 310, compiler 306 may use subpatterns selected from all of the one or more regular expression patterns to generate a unified DFA 312 and at least one NFA 314 for at least one pattern in the set of one or more regular expression patterns 304 for use by a walker 320 during runtime processing, as well as metadata (not shown) including mapping information for use by the walker 320 in transitioning between states (not shown) of unified DFA 312 and states of at least one NFA 314.

The unified DFA 312 and the at least one NFA 314 can be represented as a graph or any other suitable form on a data structure-by-data structure basis, and the mapping in the metadata can be represented as one or more tables or any other suitable form on a data structure-by-data structure basis. According to the embodiments disclosed herein, if a subpattern selected from a pattern is that pattern, no NFA is generated for that pattern. According to the embodiments disclosed herein, each generated NFA can be used for a specific pattern in a set, and a unified DFA can be generated based on all subpatterns from all patterns in the set.

Based on consuming (i.e., processing) segments, such as bytes from the payload in the received data packet 101a, the walker 320 walks the unified DFA 312 and the at least one NFA 314 according to the payload by transforming the states of the unified DFA 312 and the at least one NFA 314. In this way, the walker 320 walks the payload through the unified DFA 312 and the at least one NFA 314, which may be a per-pattern NFA generated for a single regular expression pattern.

The rule set 310 may include a set 304 of one or more regular expression patterns and may be in the form of Perl Compatible Regular Expressions (PCRE) or any other suitable form. PCRE has become the de facto standard for regular expression syntax in security and networking applications. As more applications requiring deep packet inspection have emerged or more threats have become prevalent on the Internet, the corresponding features/patterns or applications used to identify viruses/attacks have become more complex. For example, feature databases have evolved from having simple string patterns to having regular expression (regex) patterns with wildcard characters/ranges/character classes and advanced PCRE features.

As shown in FIG3A , optional qualifiers 308 can each be associated with a pattern in regular expression pattern set 304. For example, optional qualifier 322 can be associated with pattern 316. Optional qualifiers 308 can each be one or more qualifiers that specify desired customization, advanced PCRE feature options, or other suitable options for processing the pattern associated with the qualifier. For example, qualifier 322 can indicate whether the starting offset (i.e., the position in the payload of the first matching character of the pattern to be matched) option in the advanced PCRE feature options for pattern 316 is desired.

According to embodiments disclosed herein, compiler 306 can generate a unified DFA 312 using subpatterns 302 selected from all patterns in a set 304 of one or more regular expression patterns. Compiler 306 can select subpatterns 302 from each pattern in the set 304 of one or more regular expression patterns based on at least one heuristic, as described further below. Compiler 306 can also generate at least one NFA 314 for at least one pattern 316 in the set. Compiler 306 can determine a portion (not shown) of the at least one pattern 316 used to generate the at least one NFA 314 and at least one direction of runtime processing (i.e., walking) of the at least one NFA 314 based on whether the length of the selected subpattern 318 is fixed or variable and the position of the selected subpattern 318 within the at least one pattern 316. Compiler 306 can store unified DFA 312 and at least one NFA 314 in at least one memory 104.

The compiler can determine whether the length of a selected potential subpattern is fixed or variable. For example, a subpattern such as "cdef" can be determined to have a fixed length of 4 because "cdef" is a string, while a complex subpattern including operators can be determined to have a variable length. For example, a complex subpattern such as "a.*cd[^\n]{0,10}.*y" can have a length of "cd[^\n]{0,10}", which can have a variable length of 2 to 12, depending on the selected pattern.

According to the embodiments disclosed herein, sub-pattern selection can be based on at least one heuristic. A sub-pattern is a set of one or more consecutive elements from a pattern, wherein, in order to match bytes or characters from a payload, each element from the pattern can be represented by a node in a DFA or NFA graph. The elements described above can be single text characters represented by a node or character classes represented by a node. The compiler 306 can determine which sub-patterns in a pattern are more suitable for an NFA based on whether the sub-pattern is likely to cause excessive DFA graph explosions as described above with reference to Figures 2A to 2G. For example, generating a DFA from a sub-pattern including consecutive text characters will not cause a DFA graph explosion, while a complex sub-pattern as described above can include multiple operators and multiple characters and thus may cause a DFA graph explosion. For example, a sub-pattern including wildcard characters or a large character class repeated multiple times (e.g., [^\n]* or [^\n]{16}) can generate too many states in a DFA and therefore can be more advantageously applied to an NFA. In this way, the compiler 306 can be referred to as a "smart compiler" herein.

As disclosed above, the selection of a subpattern from each pattern in one or more regular expression sets 304 can be based on at least one heuristic. According to one embodiment, the at least one heuristic can include maximizing the number of unique subpatterns selected and the length of each subpattern selected. For example, a pattern such as "ab.*cdef.*mn" can have multiple potential subpatterns, such as "ab.*", "cdef", and ".*mn". The compiler can select "cdef" as the subpattern of the pattern because it is the largest subpattern in the pattern "ab.*cdef.*mn" that is unlikely to cause a DFA graph explosion. However, if the subpattern "cdef" has already been selected for another pattern, the compiler can select an alternative subpattern for the pattern "ab.*cdef.*mn". Alternatively, the compiler can replace the subpattern "cdef" with another subpattern of other patterns, thereby being able to select the pattern "cdef" for the pattern "ab.*cdef.*mn".

In this manner, compiler 306 can select subpatterns for pattern 304 based on the context of the possible subpatterns of each pattern in pattern 304, thereby maximizing the number of unique subpatterns selected and the length of each subpattern selected. In this manner, compiler 306 can generate unified DFA 312 from selected subpatterns 302 that minimizes the number of false positives (i.e., no match or partial match) in pattern matching in at least one NFA 314 by increasing the probability of a pattern match in at least one NFA 314.

By maximizing the subpattern length, false positives in NFA processing can be avoided. False positives in NFA processing can cause non-deterministic runtime processing and, therefore, degrade runtime performance. Further, by maximizing the number of unique subpatterns selected, compiler 306 can achieve a 1:1 conversion between the unified DFA and at least one NFA 314 generated from the pattern in the set, given a match of the subpattern (from the pattern) in the unified DFA.

For example, if multiple patterns share the selected subpattern, the walker of the unified DFA will need to transition to multiple at least one NFA, because each at least one NFA is a per-pattern NFA, and a subpattern match from the unified DFA means a partial match for each of the multiple patterns. Thus, maximizing the number of unique subpatterns reduces the number of DFA:NFA1:N transitions, thereby reducing the runtime processing performed by the walker 320.

In order to maximize the number of unique subpatterns, compiler 302 may calculate a hash value 326 for the selected subpattern 318 and store the calculated hash value 326 in association with an identifier (not shown) of pattern 316 from which subpattern 318 was selected. For example, compiler 306 may calculate a hash value for the selected subpattern for each pattern in set 304. The calculated hash values 324 may be stored in at least one memory 104 in a table or in any other suitable manner. The hashing method used may be any suitable hashing method. The compiler may compare the calculated hash value with a list of hash values for subpatterns selected for other patterns in the set to determine whether the selected subpattern is unique.

If the calculated hash value is found in the list, the compiler can determine whether to replace (i) the selected subpattern with another subpattern from the pattern or (ii) the subpattern selected for another pattern in the set with an alternative subpattern selected from other patterns in the set. Other patterns in the set can be identified based on their association with the calculated hash value in the list. Determining whether to replace (i) or (ii) can be based on comparing the lengths of the subpatterns being considered for replacement so as to maximize the length of the selected unique subpattern as described above. Replacing the selected subpattern can include selecting the next longest subpattern identified for a given pattern, or the next subpattern with the second highest priority. For example, the priority of potential subpatterns can be determined based on the likelihood of causing a DFA explosion or an expected DFA explosion magnitude.

According to embodiments disclosed herein, at least one heuristic may include identifying subpatterns of each pattern and ignoring a given subpattern of the identified subpatterns of each pattern if the given subpattern has a length less than a minimum threshold. For example, to reduce false positives in at least one NFA, the compiler may ignore subpatterns having a length less than the minimum threshold because such subpatterns may cause a higher probability of false positives in the at least one NFA.

The at least one heuristic may include accessing a knowledge base (not shown) of subpatterns associated with historical frequencies of usage indicators and disregarding a given subpattern from each identified subpattern if the historical frequency of usage indicators for the given subpattern in the accessed knowledge base is greater than or equal to a frequency usage threshold. For example, a particular usage or protocol specific subpattern may have a high frequency of usage, such as for Hypertext Transfer Protocol (HTTP) payloads, "carriage return line feed," or flow zeros (e.g., multiple consecutive zeros from a binary file), or any other frequently used subpattern.

The at least one heuristic can include identifying subpatterns for each pattern and for each pattern, maximizing the number of consecutive text characters in a subpattern selected by selecting a given subpattern from the identified subpatterns based on the given subpattern having the greatest number of consecutive text characters and based on the given subpattern being unique among all subpatterns selected for the one or more sets of regular expressions. As disclosed above, maximizing the length of the selected subpattern can enable a higher probability of a match in the at least one NFA.

The at least one heuristic method can include prioritizing a given subpattern of each pattern based on the subpattern type of each subpattern in the given subpattern and the length of the given subpattern. The subpattern type can be plain text, alternating, single character repetition, or multiple character repetition, and the subpattern type can be prioritized from highest to lowest to be plain text, alternating, single character repetition, and multiple character repetition. In this way, a subpattern having a text string of at least a minimum length threshold length can be prioritized higher than a complex subpattern of variable length.

The compiler 306 can prioritize a sub-pattern of a longer length over another sub-pattern of a shorter length. The compiler 306 can select a unique sub-pattern as the selected sub-pattern based on the prioritization. As described above, the selected unique sub-pattern can have a length of at least a minimum length threshold.

If none of the given subpatterns is unique and has a length that is at least the minimum length threshold, the compiler 306 can select the non-unique subpattern as the selected subpattern based on the prioritization. Thus, the compiler 306 can select a subpattern from a pattern that is a duplicate of a subpattern selected from another pattern rather than selecting a subpattern having a length less than the minimum threshold. To facilitate the final determination of the subpattern, the compiler 306 can ignore the pattern multiple times and sort the possible subpatterns by length. Thus, the compiler subpattern selection for a given pattern in the set of one or more regular expressions 304 can be performed in the context of subpattern selection for other patterns in the set of one or more regular expressions 304.

As described above, qualifier 322 can indicate that it is desired to report a starting offset. However, the starting offset may not be easily discernible. For example, given a payload such as "axycamb", it may be difficult to find the starting offset in a payload matching pattern such as "a.*b" or "a.*d" because two patterns can match, "axycamb" and "amb". Thus, it may be necessary to track the offsets of the two instances of "a" in the payload according to the potential starting offsets. According to the embodiments disclosed herein, there is no need to track the potential starting offsets because the starting offset is not determined until it is determined that a match for the entire pattern has been found in the payload. Determining that a match for the entire pattern can be found using matching is generated by a unified DFA, at least one NFA, or a combination thereof.

According to embodiments disclosed herein, if the payload in the received data packet 101 includes content that matches a subpattern 318 selected from the pattern 316, the walker may transition to walking at least one NFA of the pattern 318. The walker 320 may report a match of the selected subpattern 318 and an offset identifying the position in the received data packet of the last character that matched the subpattern as the end offset of the subpattern in the payload. If the subpattern is a subset of the pattern, the subpattern match may be a partial match of the pattern. Thus, the walker 320 may continue searching for the remainder of the pattern in the payload by walking at least one NFA for the pattern to determine a final match for the pattern. It should be understood that the pattern may traverse one or more payloads in the received data packet 101a.

FIG3B is a flowchart (350) of an example embodiment of a method that can be implemented in at least one processor operatively coupled to at least one memory within a security device operatively coupled to a network. The method can begin (352) and select a subpattern from each pattern in a set of one or more regular expression patterns based on at least one heuristic (354). The method can generate a unified deterministic finite automaton (DFA) (356) using the subpatterns selected from all patterns in the set. The method can generate at least one nondeterministic finite automaton (NFA) for at least one pattern in the set, and determine a portion of the at least one pattern for generating at least one NFA and at least one direction of run-time processing of the at least one NFA based on whether the length of the selected subpattern is fixed or variable and the position of the selected subpattern within the at least one pattern (358). The method can store the unified DFA and the generated at least one NFA in at least one memory (360). Thereafter, in this example embodiment, the method ends (362).

As disclosed above, compiler 306 can generate unified DFA 312 and at least one NFA 314 to enable walker 320 to search for matches to one or more regular expression patterns 304 in received data packet 101a. Compiler 306 can select subpatterns from each pattern in set 304 of one or more regular expression patterns based on at least one heuristic. Unified DFA 312 can be generated using subpatterns 302 selected from all patterns in set 304. Compiler 306 can generate at least one NFA 314 for at least one pattern 316 in set 304. Thus, compiler 306 can be configured to compile rule set 310 into binary image 112 that identifies portions of rule set 310 that may be most suitable for DFA or NFA processing. Thus, binary image 112 can include at least two portions, a first portion for DFA processing and a second portion for NFA processing, such as unified DFA 312 and at least one NFA 314.

As disclosed above, binary image 112 may include compiled rule data for both DFA and NFA, or may be multiple binary images that separate DFA compiled rule data from NFA compiled rule data. For example, NFA compiled rules may be separated from DFA compiled rules and stored in a graphics memory operatively coupled to at least one HNA processor 108. Memory 104 may be a single graphics memory or may be multiple memories, such as the super cluster graphics memory 156a, HNA on-chip graphics memory 156b, and HNA off-chip graphics memory 156c disclosed above with reference to FIG1D and FIG1E.

As disclosed above, the HNA processor 108 and the HFA processor 110 can be coprocessors configured to offload the heavy burden of executing computationally and memory-intensive pattern matching methods from the general-purpose cores of the network services processor 100 (such as the at least one CPU core 103 disclosed above). Thus, the HFA processor 110 can be configured to implement the functionality of the walker 320 related to DFA processing, and the at least one HNA processor 108 can be configured to implement the functionality of the walker 320 related to NFA processing. As disclosed above, the at least one HNA processor 108 can include multiple superclusters. Each supercluster can include multiple clusters. Each of the multiple clusters can include multiple HNA processing units (HPUs).

FIG4A is a block diagram of an example embodiment of an HNA processing unit (HPU) 425. According to embodiments disclosed herein, at least one HNA instruction 153 may be assigned to the HPU 425 from the HNA on-chip instruction queue 154. The at least one HNA instruction 153 may include at least one HNA task (not shown), which may be determined based on a partial match result identified by the HFA processor 110 of FIG1G for a given sub-pattern in the sub-pattern 302 of FIG3A that is matched in the input stream.

According to this example embodiment, the HPU 425 may include an HNA processing core 408. The HNA processing core 408 may be operatively coupled to a node cache 451, which is further disclosed below with reference to FIG. 7B , FIG. 12 , and FIG. 13A to FIG. 13D . The HNA processing core 408 may be operatively coupled to a character class cache 454, a payload buffer 462, a top-of-stack register 470, and a run stack 460, as well as a match result buffer 466 and a save buffer 464, which may be configured as unified memory. The HNA processing core 408 may be configured to walk at least one per-pattern NFA, wherein payload segments are stored in the payload buffer 462, to determine matches for at least one regular expression pattern. Thus, each HPU in the plurality of HPUs 125a-f of the plurality of clusters 123a-d of the plurality of superclusters 121a and 121b may further include an HNA processing core 408 operatively coupled to a node cache 451, a character class cache 454, a payload buffer 462, a top-of-stack register 470, and a run stack 460, as well as a match result buffer 466 and a save buffer 464 that may be configured as a unified memory. The run stack 460, the save buffer 464, and the result write buffer 466 may include ECC protection (single error correction/double error detection).

Each of the plurality of HPUs 125a-f of the plurality of clusters 123a-d of the plurality of superclusters 121a and 121b may include a node cache 451 that may be configured to cache one or more nodes from the supercluster graph memory 156a, the HNA on-chip graph memory 156b, or the HNA off-chip graph memory 156c as disclosed below with reference to FIG7B . Each of the plurality of HPUs 125a-f of the plurality of clusters 123a-d of the plurality of superclusters 121a and 121b may further include a character class cache 454 that may be configured to cache one or more regular expression pattern character class definitions from the supercluster character class memory 135. Each of the plurality of HPUs 125a-f in the plurality of clusters 123a-d in the plurality of superclusters 121a and 121b may further include a payload buffer 462 configured to store a given payload from the HNA packet data memory 165. At least one HNA instruction 153 from the HNA on-chip instruction queue 154 may include an identifier for a location within the given payload in the HNA packet data memory 165. Each of the plurality of HPUs 125a-f in the plurality of clusters 123a-d in the plurality of superclusters 121a and 121b may further include a top-of-stack register 470 configured to store a single HNA job. The run stack 460 may be configured to store multiple HNA jobs, and the unified memory may be configured to store a first content of a save stack 464 and a second content of a match result buffer 466. The first content may include one or more HNA jobs stored in the run stack 460, and the second content may include one or more final match results. HNA work may also be referred to herein interchangeably as context or unexplored context.

A given HNA job in the at least one HNA job may indicate a given NFA in the at least one NFA 314, at least one given node in the given NFA, at least one given offset in a given payload, and at least one walking direction, each at least one walking direction corresponding to one of the at least one given nodes. Each of the at least one HNA jobs may include the results of processing performed by the HFA processor 110, thereby enabling the at least one HNA processor 108 to advance a match for a given subpattern in a given NFA for a given pattern in the at least one pattern 304. Thus, each HNA job represents a partial match result determined by the HFA coprocessor 110, thereby advancing a match for a given pattern by the at least one HNA processor 108 via the assigned HPU 425. The assigned HPU may include an HNA processing core 408.

The HNA processing core 408 may process the at least one HNA instruction 153 by reading at least one pointer (not shown) or other suitable instruction information stored therein. The at least one pointer may include an input buffer pointer (not shown) pointing to an input buffer 458 within the input stack partition 161 of the at least one system memory 151. The at least one HNA instruction 153 may also include a payload pointer (not shown) pointing to a payload (not shown) stored in the HNA packet data memory 165 of the at least one system memory 151, and may extract the payload to the payload buffer 462 of the HPU 425. The at least one HNA instruction 153 may further include a result buffer pointer (not shown) pointing to a given result buffer in the HNA off-chip result buffer partition 171 to enable the HNA processing core 408 of the HPU 425 to transfer at least one match result entry stored in the match result buffer 466 of the HPU 425. The at least one HNA instruction 153 may further include a save buffer pointer (not shown) pointing to a given save buffer in the at least one HNA off-chip save buffer partition 171 of the system memory 151 to enable the HNA processing core 408 to transfer at least one save buffer entry from the save buffer 464 of the HPU 425. The at least one HNA instruction 153 may further include a run stack pointer (not shown) pointing to a given run stack in the at least one HNA off-chip run stack partition 167 of the system memory 151 to enable the HNA processing core 408 to transfer at least one run stack entry from or to the run stack 460 of the HPU 425.

Although input buffer 458, run stack 460, and save buffer 464 may or may not exhibit the last-in, first-out (LIFO) characteristic of a stack, input buffer 458, run stack 460, and save buffer 464 may be referred to as an input stack, a run stack, and a save stack, respectively, herein. Input buffer 458, run stack 460, and save buffer 464 may be located in the same or different physical buffers. If located in the same physical buffer, the entries of input stack 458, run stack 460, and save stack 464 may be different based on the field settings of the entries, or in any other suitable manner. Input stack 458 and run stack 460 may be located in the same physical buffer, which may be on-chip, and save stack 464 may be located in another physical buffer, which may be off-chip.

The at least one HNA work of the at least one HNA instruction 153 may be stored in the input stack 458 for processing by the HNA processing core 408. The at least one HNA work of the at least one HNA instruction may each belong to the same given payload, such as a payload transferred to the payload buffer 462 for processing by the HNA processor 110.

The HNA processing core 408 can be configured to load (i.e., extract or retrieve) at least one HNA job from the input buffer 458 based on the input buffer pointer. The HNA processing core 408 can push (i.e., store) the at least one HNA job to the run stack 460. The HNA processing core 408 can pop (i.e., read, extract, load, etc.) a given HNA job from the run stack 460 and process the given HNA job. Each of the at least one HNA job can include a payload offset to a segment (not shown) of a payload stored in the payload buffer 462 and a pointer to a graph (not shown), which can be at least one finite automaton (e.g., the at least one NFA 314 of FIG. 3A ).

The HNA processing core 408 may load (i.e., extract) a graph that may distribute nodes in any one or more of the supercluster memory 156a, the HNA on-core graphics memory 156b, or the HNA off-chip graphics memory 156c, and may begin traversing the extracted nodes using payload segments corresponding to corresponding payload offsets of the payload in the payload buffer 462. A partially matching path of the graph may include at least two nodes of the graph that have consecutive segments of the payload matching a given pattern used to generate the graph. The partially matching path may be referred to herein as a thread or active thread.

As the HNA processing core 408 can use the payload segment from the payload buffer 462 to process the graph, entries are pushed and popped onto the run stack 460 or pushed or popped from the run stack to save and restore their positions in the graph. For example, if a node that has been walked presents multiple options for the next node to be walked, the HNA processing core 408 may need to save its position in the graph. For example, the HNA processing core 408 can walk nodes that present multiple processing path options, such as forked roads represented by a graph. According to the embodiments disclosed herein, nodes of a DFA or NFA can be associated with a node type. Nodes associated with a separation type can present multiple processing path options. Separation node types are further disclosed below with reference to FIG. 5A .

According to the embodiment disclosed herein, HNA processing core 408 can be configured to select a given path in the multiple processing paths and push an entry to run stack 460. Based on the mismatch (i.e., negation) result at the node that has been walked along the selected path, the run stack can enable HNA processing core 408 to return and continue along the unselected path in the multiple processing paths. In this way, pushing the entry on run stack 460 can save the position of the context that represents the unexplored context in the graph. The unexplored context can indicate a given node of the graph and the corresponding payload offset so that HNA processing core 408 can return to the given node and walk the given node according to a given segment of the payload from payload buffer 462, because the given segment can be located at the corresponding payload offset in the payload. In this way, run stack 460 can be used to enable HNA processing core 408 to remember and later walk the unexplored path of the graph. Pushing or storing the entry indicating the corresponding offset in a given node and a given payload can be referred to as storing unexplored context, thread, or inactive thread. Popping, extracting, or loading an entry indicating a given node and a corresponding offset in a given payload so as to walk the given node according to the segment located at the corresponding offset in the given payload may be referred to herein as activating a thread. Discarding an entry indicating a given node and a corresponding offset in a given payload may be referred to herein as flushing an entry or deactivating a thread.

When walking payload segments in a graph format, upon reaching the boundary of a payload in payload buffer 462, save buffer 464 enables HNA processing core 408 to save its position in the graph. For example, HNA processing core 408 may determine that a payload or a portion of a payload in payload buffer 462 partially matches a given pattern and determine the payload's current payload offset as the payload's end offset. Thus, HNA processing core 408 may determine that only a partial match of the given pattern was found and that the entire payload was processed. In this manner, HNA processing core 408 may save the contents of run stack 460 to save buffer 464 to continue walking the next payload corresponding to the same stream as the processed payload. Save buffer 464 may be configured to store at least one run stack entry of run stack 460, thereby reflecting the operational status of run stack 460 when the entire payload is processed.

Upon finding a final (i.e., entire or complete) match for the pattern, the HNA may pop and discard the entry associated with the current HNA work (e.g., the HNA loaded from the input buffer) in the run stack 460 and save the match results (not shown) to the match result buffer 466. Alternatively, when all possible matching paths may be of interest, the HNA processing core 408 may continue processing the entries associated with the current HNA work in the run stack 460.

The matching result may include a node address associated with the node where the final match of the determined pattern is located. The node where the final match of the determined pattern is located may be referred to as a marked node herein. The node address, or other identifier of the final matching position in the graph, an identifier of the matching pattern, the length of the matching pattern, or any other suitable matching result or combination thereof may be included in the matching result.

Upon processing all run stack entries associated with the current HNA job, the HNA processing core 408 may load the next HNA job that has been previously loaded from the input buffer 458 from the run stack 460, because the HNA processing core 408 may be configured to sequentially process the HNA jobs of at least one HNA instruction 153. Thus, the HNA processing core 408 may fetch the next graphic (not shown) from the supercluster graphic memory 156a, the HNA on-chip graphic memory 156b, or the HNA off-chip graphic memory 156c and walk the next graphic based on one or more payload segments from the next payload identified by the next HNA job, and continue processing additional HNA jobs until the run stack 460 is empty.

Upon discovering a payload mismatch while walking the graph based on the payload, the HNA processing core 408 may pop the entry associated with the current HNA job from the running stack 460 and walk the next node based on the next segment of the next payload based on the contents of the popped entry. If the running stack 460 does not include an entry associated with the current HNA job, the HNA processing core 408 may complete the current HNA job and load the next HNA job previously loaded from the input buffer 458 from the running stack 460. In this manner, the HNA processing core 408 may be configured to walk another next graph based on the loaded next HNA job and continue processing additional jobs until the running stack 460 is empty.

Embodiments disclosed herein may utilize a top-of-stack register 470 to improve matching performance. The top-of-stack register 470 may be interchangeably referred to herein as a supplemental memory 470, a TOS register 470, or a TOS 470. The top-of-stack register 470 may be a first memory operatively coupled to a second memory, such as a run stack 460. The HNA processing core 408 of the HPU 425 may be operatively coupled to the top-of-stack register 470 and the run stack 460. The top-of-stack register 470 may be configured to store HNA work (i.e., context) for multiple nodes of a given finite automaton in at least one finite automaton, which may be pushed by the HNA processing core 408 for walking the given node, such as stack entries (also interchangeably referred to as context or unexplored context). For example, a context may be pushed or popped for walking a given node. The context may identify a given node and an offset for a segment in the payload of an input stream received from the network. The context enables the HNA processing core 408 to walk through the given node identified by the context based on the segment identified by the offset.

The top-of-stack register 470 may be associated with context state information that may include validity state information (also interchangeably referred to as a validity indicator). The validity state may indicate a valid or invalid state for the top-of-stack register 470. The valid state may indicate that the top-of-stack register 470 stores a pending context. A pending context may be a stored context that has not yet been processed by the HNA processing core 408.

The invalid state may indicate that the top-of-stack register 470 does not store a pending context, e.g., the entry stored in the top-of-stack register 470 has been popped by the HNA processing core 408 to walk a given node according to the segment or has otherwise been discarded by the HNA processing core 408. Thus, the HNA processing core 408 may use the context state information to discern whether the top-of-stack register 470 has a pending context.

According to embodiments disclosed herein, the validity status may be implemented as a bit of the top-of-stack register 470, a multi-bit field of the top-of-stack register 470, an indicator stored separately from the top-of-stack register 470, or in any other suitable manner that conveys status regarding whether the top-of-stack register 470 register stores a pending context.

HNA processing core 408 uses operation stack 460 to preserve context, as the state of the node of NFA graph in the node process of walking NFA graph.The access (that is, read/write) of TOS 470 registers can be many times faster than operation stack 460.Compared with ECC protected memory, for this memory, push or pop operation can carry out three, four or more clock cycles, if execute on TOS 470 registers, then push or pop operation can carry out a clock cycle.TOS 470 registers can keep separate with the stack entry that pushes recently and can be pushed to the entry and exit of operation stack 460 by TOS 470 registers earlier.The entry and exit that pushes recently is remained in TOS 470 registers and can improve walking performance, because the entry and exit that pushes recently may be the entry and exit that most frequently accesses, that is, before pushing another entry and exit, probably pop out the entry and exit that pushes recently.

Storing the context (e.g., by pushing a first context) may include storing a determination to access the TOS 470 registers without accessing the runtime stack 460 or to access both the TOS 470 registers and the runtime stack 460 based on context state information associated with the TOS 470 registers. The determination to access the TOS 470 registers without accessing the runtime stack 460 may be based on the context state information indicating an invalid state of the TOS 470 registers. The determination to access both the TOS 470 registers and the runtime stack 460 may be based on the context state information indicating a valid state of the TOS 470 registers.

The TOS stack 470 may be configured with a single entry for storing a single context (i.e., HNA work), and the run stack 460 may be configured with multiple entries for storing multiple contexts. When the HNA processing core 408 pops a context (i.e., a stack entry), for example, to retrieve a stored context, a check may be performed as to whether the context state information indicates a valid or invalid state for the TOS 470 registers. If the context state information indicates a valid state, the most recently pushed context may be popped 478 from the TOS 470 registers, and when the TOS 470 registers no longer store a pending context, the context state information may be updated to indicate the current invalid state of the TOS 470 registers.

However, if the examination determines that the context state information indicates an invalid state, the pending context may instead be popped 480 (i.e., retrieved) from the run stack 460. Thus, based on the invalid state associated with the TOS 470 register of the context state information, the pending context may be retrieved from the run stack 460, and the pending context stored by the run stack 460 may not be written to the TOS 470 register.

4B is a block diagram 4400 of an example embodiment of a context 4401 (i.e., HNA operation) that can be stored or retrieved, such as by pushing or popping a stack entry, according to embodiments disclosed herein. Context 4401 may include multiple fields 4402-4418. The multiple fields may include a context entry type field 4402 that may be based on one of multiple node types. Context entry type field 4402 may indicate which fields of the multiple fields 4402-4418 are relevant for a node type.

Context 4401 may further include a match type field 4404 that may be related based on context entry type field 4402. Match type field 4404 may be based on node type and may be used to determine whether a given node is configured to match a single instance or multiple consecutive instances of a given element in a data stream received from the network.

Context 4401 may further include an element field 4408 that may be relevant regardless of context entry type field 4402 and may identify a given element for matching at a given node.

Context 4401 may further include a next node address field 4410 that may be relevant regardless of the context entry type field and may identify the next node associated with a given node. For example, based on a positive match at a given node, the next node for walking the next segment may be identified by next node address field 4410.

Context 4401 may further include a count field 4412 that may be related based on context entry type field 4402. Count field 4412 may identify a count value of the number of consecutive instances remaining for matching a given element identified by element field 4408 at a given node.

Context 4401 may further include a discard unexplored context (DUP) field 4414 that may be relevant regardless of the context entry type field 4402 and that may identify whether to discard context 4401 or walk to the next node identified by the next node address field 4410 when a complete match of at least one regular expression is detected in the input stream.

Context 4401 may further include a reverse walking direction field 4416 that may be relevant regardless of context entry type field 4402 and may identify reverse or forward walking direction.

Context 4401 may further include an offset field 4418 that may be relevant regardless of context entry type field 4402 and may identify an offset of a payload segment in the input stream for matching with a specific element. The specific element may be identified based on context entry type field 4402.

Pushing a context may include configuring a stack entry including a context 4401, and the stack entry may be stored on the stack of the runtime stack 460 of FIG. 4A as disclosed above. A first subset of the fields of context 4401 may be configured based on given metadata associated with a given node, obtained based on having previously extracted the given node, such as a match type field 4404, an element field 4408, and a next node address field 4410. A second subset of the fields of context 4401 may be configured by the HNA processing core 408 based on runtime information about the walk, such as the current walk direction or count value maintained for the given node. For example, this second subset may include a reverse walk direction field 4416, a count field 4412, and a discard unexplored context (DUP) field 4414.

The HNA processing core 408 may interpret the context 4401 based on a context state setting (not shown) included in the context entry type field 4402. The context state setting may indicate whether the context 4401 is complete or incomplete. Based on the context state setting of the context entry type field 4402 of the context 4401 of the popped stack entry indicating whether the context 4401 is incomplete, the HNA processing core 408 may be configured to extract the next node identified by the next node address field 4410 and continue walking based on the metadata stored in the next node and the current runtime configuration (e.g., walking direction), rather than continuing walking based on the field configuration of the context 4401 of the popped stack entry.

FIG5A is a block diagram 500 of an example embodiment of a per-pattern NFA graph 504 that the walker 320 can use to match regular expression patterns 502 in an input stream (not shown). As disclosed above, at least one HNA processor 108 can be configured to implement NFA processing-related functionality of the walker 320, and the at least one HNA processor 108 can include multiple superclusters. Each supercluster can include multiple clusters. Each cluster in the multiple clusters can include multiple HNA processing units (HPUs), each of which can include an HNA processing core 408 as disclosed above with reference to FIG4A. Thus, at least one HNA processing core 408 of at least one HPU 425 can implement NFA processing-related functionality of the walker 320 based on the scheduling of HNA instructions by the HNA scheduler 129.

In an example embodiment of a per-pattern NFA graph 504 that can be used by walker 320, an input stream can include a data packet (not shown) with a payload 542. Regular expression pattern 502 is the pattern "h[^\n]*ab" that specifies the character "h" followed by an unlimited number of consecutive characters that do not match a newline character (i.e., [^\n]*). The unlimited number can be zero or more. Pattern 502 further includes the characters "a" and "b" followed by an unlimited number of consecutive characters that do not match a newline character. In this example embodiment, payload 542 includes segments 522a-d (i.e., h, x, a, and b) with corresponding offsets 520a-d (i.e., 0, 1, 2, and 3) in payload 542.

It should be understood that regular expression pattern 502, NFA graph 504, payload 542, segments 522a-d, and offsets 520a-d represent examples for illustrative purposes, and that the systems, methods, and corresponding apparatus disclosed herein can be applied to any suitable regular expression pattern, NFA graph, payload, segment, and offset. Further, it should be understood that NFA graph 504 can be a sub-portion of a larger NFA graph (not shown). Additionally, payload 542 can be a portion of a larger payload (not shown) and the portion can be at the beginning, end, or any other position of the larger payload, thereby resulting in offsets that differ from those in the example embodiment.

In this example embodiment, NFA graph 504 is a per-pattern NFA graph configured to match regular expression pattern 502 with an input stream. For example, NFA graph 504 may include a graph of multiple nodes generated by compiler 306, such as nodes N0 506, N1 508, N2 510, N3 512, N4 514, and N5 515. Node N0 506 may represent the starting node of pattern 502, and node N5 515 may represent the marking node of pattern 502. Marked node N5 515 may be associated with an indicator (not shown) reflecting the final (i.e., entire or complete) match of pattern 502 matched with the input stream. In this way, walker 302 may determine that pattern 502 matches in the input stream based on traversing marked node N5 515 and detecting the indicator. The indicator may be a (not shown) tag or field setting of metadata associated with the marked node or any other suitable indicator.

According to embodiments disclosed herein, the walker 320 can walk the NFA graph 504 one segment at a time from segments 522a-d of the payload 542 to match the regular expression pattern 502 to the input stream. A given segment from segments 516 to be used to walk a given node can be determined based on the corresponding offset of the given segment in offset 518 to the current offset within the payload 542. According to embodiments disclosed herein, the walker 320 can update the current offset by incrementing or decrementing the current offset. For example, the walker 320 can walk the NFA graph 504 in a forward or reverse direction and, therefore, can walk segments from the payload 542 in a forward 543 or reverse 546 direction by incrementing or decrementing the offset, respectively.

Nodes N0 506, N2 510, N3 512, and N4 514 can be configured to match corresponding elements to a given segment of payload 542, while nodes N1 508 and N5 515 can be nodes of a node type indicating no matching functionality and, therefore, will not be processed from payload 542. In this example embodiment, node N1 508 is a split node that presents multiple conversion path options to walker 320. For example, walking split node N1 508 presents ε-paths 530a and 530b. According to embodiments disclosed herein, walker 320 can select a given path from the multiple paths 530a and 530b based on an implicit setting in a mutual agreement with walker 306. For example, compiler 306 can generate NFA graph 504 based on walker 320's implicit understanding of following deterministic paths, such as based on walker 320's implicit understanding that upper ε-path 530a will be selected based on walking split node 508. According to embodiments disclosed herein, upper epsilon path 530a may be selected such that upper epsilon path 530a represents a lazy path. The lazy path may be a path representing the shortest possible element match.

According to embodiments disclosed herein, the split node 508 may be associated with split node metadata (not shown) that presents the multiple path options. For example, in this example embodiment, the split node metadata may indicate multiple next nodes, such as nodes N2 510 and N3 512, either directly or indirectly. If the multiple next nodes are indicated directly, the metadata may include absolute addresses or indicators to the next nodes N2 510 and N3 512. If the multiple next nodes are indicated indirectly, the metadata may include an index or offset that can be used to resolve the absolute addresses of the next nodes N2 510 and N3 512 or indicators of the next nodes N2 510 and N3 512. Alternatively, other suitable forms of next node addresses that directly or indirectly indicate the multiple next nodes may be used.

This implicit understanding can include configuring the walker 320 to select a next given node from the plurality of next nodes based on the node metadata included in the specific entry position within the split node metadata. The compiler 306 can be configured to generate the split node metadata including an indication of the next given node at the specified entry position. In this way, the compiler 306 generating the NFA graph 504 can use the implicit understanding of the walker 320 to select a given path (such as the upper epsilon path 530a) at the split node N1 508.

5B is a table 538 of an example embodiment of a processing cycle for walking the per-mode NFA of FIG. 5A according to payload 542. It should be understood that a processing cycle may include one or more clock cycles.

As shown in table 538, processing cycles 540a-h can include walking the current node 530 according to the segment at the current offset 532 from the payload 542 to determine a match result 534 and a walker action 536 based on the match result 534. In this example embodiment, node N0 506 can have a character node type. For example, node N0 506 can be a character node configured to match the character "h" in the input stream. In this example embodiment, the walker 320 can walk the starting node N0 506 according to the segment 522a (i.e., "h") at the current offset 520a in processing cycle 540a.

When segment 522a matches "h" at start node N0 506, the walker 320 can determine that the match result 534 is a positive match result. As specified by the compiler 306 through metadata (not shown) associated with the start node N0 506, the walker 320 can walk in the forward direction and extract the next node indicated by the metadata associated with node N0 506 and increment the current offset from 520a (i.e., "0") to 520b (i.e., "1"). In this example embodiment, the next node indicated by node N0 506 is the separation node N1 508. As such, the walker 320 takes action 536 in processing cycle 540a, which includes updating the current offset to "1" in the payload 542 and switching to the separation node N1 508. The switching can include extracting (also referred to herein as loading) the separation node N1 508.

When split node N1 508 presents multiple conversion path options, such as epsilon paths 530a and 530b, action 536 in processing cycle 540b may include selecting upper epsilon path 530a and extracting node N2 510 that is not associated with payload 542 without being consumed (i.e., processed) from payload 542. Since split node N1 508 does not perform a matching function, current offset/segment 532 is not changed, and therefore, no payload is consumed (i.e., processed) in processing cycle 540b.

Because split node N1 508 presents multiple path options, action 536 may include storing the unexplored context, such as by storing the indirect or direct identifier of node N3 512 and the current offset 520b (i.e., "1"). The selected transition path may be referred to herein as the current or active thread, and each stored transition path that has not been traversed may be referred to herein as a stored thread. The corresponding node identifier and offset in the payload may identify each thread. In this manner, the unexplored context may identify the unexplored thread (i.e., path).

In the event of a negative match result along the selected partially matched path, for example, if a negative match result is determined at node N2 510 or multiple nodes along the path extending from node N2 510, storing the unexplored context may enable the walker 320 to remember to return to node N3 512 to walk node N3 512 according to the segment at offset 520b "1" in the payload 542. According to embodiments disclosed herein, in the event that a final match for the pattern 502 is identified along the selected transition path, the unexplored context may be marked with a discard unexplored processing (DUP) indicator that indicates to the walker 320 whether to discard or process the unexplored context.

For example, upon reaching marked node N5 515 indicating a final (i.e., complete or entire) match of pattern 502 in the input stream, the walker 320 can utilize the DUP indicator to determine whether to process the unexplored context by walking node N3 512 according to segment “x” at offset 520 b to determine another path of the NFA graph 504 that matches pattern 502, or whether to discard the unexplored context. Marking the unexplored context with the DUP indicator can include marking the unexplored context in any suitable manner, such as by setting a bit or field associated with the unexplored context to true to indicate a desire to process the stack entry, or to false to indicate a desire to discard the stack entry.

Compiler 306 can determine whether to traverse the storage thread. For example, compiler 306 can control whether to set the DUP indicator by configuring a setting in the corresponding metadata of each node. Alternatively, compiler 306 can configure a global setting included in the global metadata associated with the finite automaton that specifies a thread to traverse all storage, thereby being able to identify all possible matches.

In this example embodiment, selection of the ε transition path 530a results in a match failure being detected at node N2 510 or at a subsequent node of the current thread (e.g., node N4 514). Thus, if a match failure is detected, the storage thread for the ε transition path 530b may be traversed. Alternatively, if specified by the compiler 306, the ε transition path 530b may be traversed regardless of whether traversing the ε transition path 530b results in a match failure being detected.

Storing the untraversed transition path can include storing the entry on a stack, such as the run stack 460 of FIG4A , by storing an identifier of the next node N3 513 in association with an indication of the current offset 522 b in the entry. The identifier of the next node N3 513 can be a value, a pointer, or any other suitable indicator of the next node. The offset value can be a numeric value, a pointer, or any other suitable value that identifies the location of the segment 516 within the payload 542.

According to this example embodiment, based on selecting the upper path (i.e., ε-transition path 530a), in processing cycle 540c, walker 320 may extract node N2 510 and attempt to match segment 522b (i.e., "x") at current offset 520b (i.e., "1") with element "a" of node N2 510. Since "x" does not match element "a" at node N2 510, action 536 in processing cycle 540c may include popping an entry from run stack 460. The popped entry 544b may be the most recently pushed entry, such as, in this example embodiment, stored entry 544a indicating node N3 512 and offset 520b (i.e., "1").

The walker 320 can then transition and walk node N3 512 based on segment "x" located at offset 520b in the payload 542. Thus, processing cycle 540d indicates that the match result 534 is positive in processing cycle 540d. Action 536 in processing cycle 540d can include updating the current offset to offset 520c and transitioning back to the split node N1 508, which can be the next node indicated by node N3 512.

Since all arcs transitioning from the split node 508 are ε transitions, when the current offset is not updated in processing cycle 540e, the walker 320 can again select one of the multiple path options and not consume (i.e., process) segments from the payload 542. In this example embodiment, the walker 320 again selects the ε transition path 530a. As such, the walker 320 again stores the thread on the run stack 460 by pushing node N3 512 and the current offset, which is now 520c (i.e., "2"). As shown in processing cycle 540f, the walker 320 extracts node N2 510 and matches segment 522c (i.e., "a") at offset 520c (i.e., "2") with element "a" of node N2 510. Since "a" matches at node N2 510, the walker 320 updates the current offset to 520d (i.e., "3") and transitions to node N4 514 as specified by the node N2 510 metadata (not shown) configured by the compiler 306. For example, the node N2 510 metadata may specify a transition 511 from a given node (e.g., node N2 510) to a next node (e.g., node N4 514) via a next node address (not shown) associated with the given node N2 510. According to embodiments disclosed herein, the next node address may be configured to identify a next node and a given memory of a plurality of memories, such as the super cluster graph memory 156a, the HNA on-chip graph memory 156b, or the HNA off-chip graph memory 156c, to which the compiler 306 distributes the next node for storage.

Thus, in processing cycle 540g, the walker 320 can extract the next node N4 514 and the next segment 522d (i.e., "b") at offset 520d. Since "b" matches at node N4 514, the walker 320 can transition to the next node N5 515. Node N5 515 is a marked node associated with an indicator representing the final (i.e., complete or entire) match of the regular expression pattern 542 in the input stream. Therefore, in processing cycle 540h, the walker 320 can interrupt walking along the current path and report the final match by storing an entry in the match results buffer 466. The walker 320 may then perform a store thread check on the run stack 460 and either discard the store threads or activate them as indicated by the corresponding DUP indicators. Thus, the walker 320 pops the entry identifying the node N3 512 and the offset 520 (i.e., “2”) and determines whether to activate the store thread by walking the node N3 512 according to the segment 522 c at the offset 520 c or discard the store thread according to the DUP indicator associated with the popped entry.

Due to the combined DFA and NFA processing disclosed above, the embodiments disclosed herein can optimize matching performance. For example, because the NFA can be based on partial matches identified by DFA processing, the embodiments disclosed above can reduce the number of false positives in NFA processing. Furthermore, because the embodiments disclosed herein include per-rule (i.e., per-pattern) NFAs that can be identified by DFA processing, the embodiments disclosed herein further optimize matching performance.

As disclosed above, DFA 312 is a unified DFA, and each of at least one NFA 314 is a per-pattern NFA. HFA processor 110 causes the payload to walk through the unified DFA 312, which can be considered as a first parsing block that marks the starting point of a pattern (intermediate match) and provides a starting point to at least one NFA 314 that can continue to walk from the mark to determine the final match. For example, based on the partial match results determined by processing a segment of the payload of the input stream through the unified DFA 312, walker 320 can determine that a given number of rules (i.e., patterns) in rule set 310 need to be further processed, and when each of at least one NFA 314 is a per-pattern NFA, HFA processor 110 can generate a pattern matching result that can be converted into a given number of NFA walks.

FIG6 is a block diagram 600 of an example embodiment of an environment 600 for a walker 320. An input stream of packets 101a may be received 602 and may include packets 616a-f, which may be packets from different streams, such as a first stream 614a and a second stream 614b. For example, packets P1 616a, P4 616d, and P6 616f may be packets in the first stream 614a, while packets P2 616b, P3 616c, and P5 616e may belong to the second stream 614b. A processing core 603 may be a general-purpose processing core of the security device 102, such as the at least one CPU core 103 described above with reference to FIG1A and FIG1G, that may be configured to perform high-level protocol processing of the packets 101a and to offload pattern matching methods to the HFA processor 110 and at least one HNA processor 108.

The data packet 101a may be forwarded 604 to the HFA processor 110, and the walker 320 may determine partial matches for the regular expression pattern 304 in the input stream by walking segments of the data packet 101a through a unified DFA (such as the unified DFA 312 of FIG. 3A ). The walker 320 may be configured to forward 606 partial match results, which may identify offsets of the segments of the data packet 101a and nodes of a per-pattern NFA (such as the at least one NFA 314), so that the partial matches may be advanced by a given HPU of a given cluster of a given supercluster of at least one HNA processor 108 that may walk the at least one NFA 314 based on the partial match results processed by the DFA of the HFA processor 110, as these match results may be forwarded 608 to the at least one HNA processor 108 along with corresponding data packets in the data packet 101a.

A given HPU of a given cluster of a given supercluster of at least one HNA processor 108 may be able to determine partial matches 618 c, 618 b, and 618 a that form a final (i.e., complete) match to a given regular expression pattern in the input stream 304. For example, by forwarding 606 the HFA partial match results from the HFA processor 110 to the at least one HNA processor 108, either indirectly via the processing core 603 or directly from the HFA processor 110, each packet partially matched by the HFA processor 110 may enable a given HPU of a given cluster of a given supercluster of at least one HNA processor 108 to advance the partial match because the walker 320 may use the “hint” or starting information from the HFA processor 110 to walk segments of the packet 101 a through the at least one NFA 314.

For example, as disclosed above with reference to FIG. 4A , the input stack 458 may include at least one HNA task of at least one HNA instruction 153 for processing by the HNA processing core 408 of the selected HPU 425 assigned the at least one HNA instruction 153. Each at least one HNA task of the at least one HNA instruction 153 may pertain to the same given payload being processed by the HFA processor 110. Such "hints" or starting information, which may be based on "pre-screening" of packets performed by the HFA processor 110, may include an NFA starting node with a corresponding offset of the payload segment for walking the per-pattern NFA as disclosed above. In this manner, the walker 320 may determine a final matching result 610 for the packet 101a that may be forwarded from the at least one HNA processor 108 to the processing core 603, and the packet 101a may then be appropriately forwarded 612 in the network similarly to the packet 101b.

In addition to such packet pre-screening by the HFA processor 110, which can reduce the number of false positives processed by the NFA, the embodiments disclosed herein can further optimize matching performance by distributing the nodes of each per-pattern NFA to multiple memories in a memory hierarchy based on node locality. Since each NFA can be a per-pattern NFA, the embodiments disclosed herein can advantageously distribute the nodes of each per-pattern NFA to multiple memories in a hierarchy based on the understanding that the longer the rule (i.e., pattern), the less likely it is to access (i.e., walk or traverse) nodes generated from the portion at the end of the rule (i.e., pattern). By storing the earlier nodes of each per-pattern NFA in relatively faster (i.e., higher performance) memory, the embodiments disclosed herein can further optimize matching performance. It should be understood that because such node distribution can be based on a hierarchy of memory maps, the nodes can be advantageously distributed based on the mapped hierarchy, thereby enabling any suitable distribution that optimizes the matching performance to be utilized.

As disclosed above, at least one NFA 314 (such as per-mode NFA 504 in FIG. 5A ) can be stored in at least one memory, such as supercluster graph memory 156 a, HNA on-chip graph memory 156 b, or HNA off-chip graph memory 156 c. According to embodiments disclosed herein, the matching performance of the walker 320 can be optimized based on the intelligent compiler 306 distributing the nodes of the per-mode NFA 504 across at least one memory, which can include multiple graph memories (such as supercluster graph memory 156 a, HNA on-chip graph memory 156 b, or HNA off-chip graph memory 156 c). These graph memories can be arranged in a memory hierarchy. Supercluster graph memory 156 a, HNA on-chip graph memory 156 b, or HNA off-chip graph memory 156 c can be static memory preloaded for each per-mode NFA, allowing for faster processing. Based on the different access times of the multiple graph memories, application performance can reach search rates exceeding 20+ Gbps.

The matching performance of the walker 320 can be optimized based on storing consecutive nodes, such as nodes N0 506, N1 508, N2 510, and N3 512 of portion 509 of the per-pattern NFA 504 of FIG. 5A , in a faster-performing memory that is mapped to a higher level relative to another memory that stores consecutive nodes N4 514 and N5 515, which can be mapped to a lower level in the memory hierarchy. Because NFA 504 is a per-pattern NFA generated from a single pattern (such as pattern 502), NFA 504 is separate from other NFAs generated from other patterns, and therefore, embodiments disclosed herein can be based on the identified locality of nodes of the per-pattern NFA that is not present for nodes of the unified NFA.

Embodiments disclosed herein can be based on the understanding that earlier nodes (e.g., nodes N0 506, N1 508, N2 510, and N3 512) of a per-pattern NFA graph (e.g., per-pattern NFA graph 504) can have a higher probability of being traversed than nodes N4 514 and N5 515 because nodes N4 514 and N5 515 are located towards the end of rule (i.e., pattern) 502 and, therefore, require matching more portions of the payload in order to be walked (i.e., traversed). As such, earlier nodes of a per-pattern NFA (e.g., NFA 504) or any other suitable per-pattern NFA graph can be considered "high touch" nodes that are visited more frequently due to false positives than "low touch" nodes, which are more likely to be visited only in the event of a complete match of the pattern.

According to embodiments disclosed herein, compiler 306 can distribute the nodes in each per-pattern NFA to multiple memories in a hierarchy based on an understanding of which nodes in each per-pattern NFA are considered "high touch" nodes and which nodes are considered "low touch" nodes. Such understanding can be used to "pre-cache" (i.e., statically store) the nodes of each per-pattern NFA by distributing them to multiple memories in a memory hierarchy, thereby improving matching performance. For example, "high touch" nodes can be distributed to faster memories based on the understanding that these "high touch" nodes can be accessed (i.e., walked or traversed) more frequently due to their locality within the per-pattern NFA.

Typically, the regular expression access patterns generated by a unified NFA based on a set of regular expression patterns can be random because such patterns can be based on a specific payload. Therefore, the history of regular expression access patterns cannot be used to predict future regular expression access patterns. For example, caching the most recently traversed nodes of a unified NFA may not provide a performance benefit to the walker because the next node visited within the unified NFA may not be the cached node.

FIG7A is a block diagram of an embodiment of an environment 700 for a compiler 306. As disclosed above, the compiler 306 may be referred to herein as an intelligent compiler that may be configured to compile a rule set 310 into a binary image 112 by identifying portions of the rule set 310 that may be most suitable for DFA or NFA processing. Thus, the binary image 112 may include at least two portions, a first portion for DFA processing and a second portion for NFA processing, such as the unified DFA 312 and at least one NFA 314 disclosed above with reference to FIG3A. According to embodiments disclosed herein, at least one HNA processor 108 may be operatively coupled to a plurality of memories, which may include a plurality of graphics memories, such as the supercluster graphics memory 156 a, the HNA on-chip graphics memory 156 b, or the HNA off-chip graphics memory 156 c disclosed above. According to embodiments disclosed herein, compiler 306 may be configured to determine locations of nodes of unified DFA 312 and at least one NFA 314 in a graph memory, such as supercluster graph memory 156a, HNA on-chip graph memory 156b, or HNA off-chip graph memory 156c.

According to embodiments disclosed herein, unified DFA 312 may be statically stored in a given memory in a DFA graph memory, while at least one NFA 314 may have distributed nodes and statically stored them across these graph memories, such as supercluster graph memory 156a, HNA on-chip graph memory 156b, or HNA off-chip graph memory 156c, because compiler 306 can determine the distribution target of a specific NFA to store in a specific memory to optimize walker matching performance. According to embodiments disclosed herein, graph memory, such as supercluster graph memory 156a, HNA on-chip graph memory 156b, or HNA off-chip graph memory 156c, may be in a memory hierarchy 743, which may include multiple levels 708a-c. The multiple levels 708a-c may be mapped to the multiple graph memories, which may include memories 756a-c, which may be supercluster graph memory 156a, HNA on-chip graph memory 156b, and HNA off-chip graph memory 156c, respectively.

Compiler 306 can map levels 708a-c in any suitable manner and can rank levels 708a-c in descending order 712 such that level 708a can be the highest ranked level 708a and level 708c can be the lowest ranked level. Graphics memory 756a-c can include random access memory (RAM), which can be the highest performance memory, and can be co-located with on-chip search memory (OSM) on the network services processor 100. Graphics memory 756a-c can include HNA off-chip graphics memory 156c, which can be included in at least one system memory 151, which can be external and operatively coupled to the network services processor 100.

Based on the mapping based on the performance of the memory (i.e., read and write access time), RAM memory can be mapped to the highest-ranked tier 708a, OSM can be mapped to the second-highest-ranked tier 708b, and system memory can be mapped to the lowest-ranked tier 708c. However, it should be understood that the mapping between the multiple tiers 708a-c and the graphics memory 756a-c can be performed in any suitable manner. For example, the mapping can be based on an understanding of the application associated with the rule set 310, from which the nodes distributed to the memories 756a-c can be generated, so that the highest-performance memory is not mapped to the highest-ranked tier. Further, it should be understood that the number of tiers in the memory hierarchy 743 and the number of graphics memories 756a-c shown are for illustrative purposes and can be any suitable number of tiers and memories.

As disclosed above, by storing NFA nodes generated from earlier portions of a given pattern in faster memory, the intelligent compiler 306 can exploit the locality of nodes in the per-pattern NFA. Further, since the probability of a match for a given pattern is already higher since the DFA processing of the HFA processor 110 determined a partial match for the given pattern, such embodiments combine to optimize matching performance.

For example, as disclosed above, DFA processing can be used to reduce the number of false positives found by NFA processing. Since each NFA can be a per-pattern NFA, the nodes of each per-pattern NFA can be advantageously distributed across the multiple memories based on the mapping of multiple memories to levels of the memory hierarchy 743. For example, a smaller NFA generated from a pattern of relatively short length can distribute all nodes to a first level and store them in a first memory mapped to the first level, while a larger NFA generated from a pattern of relatively long length can distribute the first portion of the nodes to the first level and the remaining portion among the remaining levels. The first level can be mapped to the highest-ranked level of the highest-performance memory.

Thus, the earlier nodes of the per-pattern NFA can be stored in the highest-performing memory. Since the earlier nodes may have a higher probability of being traversed due to false positives, the embodiments disclosed herein can handle most false positives by accessing memory mapped to higher levels in the memory hierarchy 743. According to the embodiments disclosed herein, matching performance can be optimized by making the number of accesses to memory 756a mapped to the highest-ranked level (e.g., level 708a in the memory hierarchy 743) relatively high compared to the number of accesses to memory 756c mapped to the lowest-ranked level 708c.

Memory 756a may be the highest performance memory capable of supporting, for example, 1.3 billion transactions per second, while memory 756b may have a lower performance capable of supporting 150 million transactions per second, and memory 756c may have the lowest performance memory capable of supporting 12 million transactions per second. Further, according to embodiments disclosed herein, such higher performance memory mapped to a higher-ranked tier may have a relatively smaller storage size than lower performance memory (such as memory 756c) mapped to the lowest-ranked tier 708c, which may be a relatively large memory. For example, memory 756c may be HNA off-chip graphics memory 156c included within at least one system memory 151, which may be external and provide a relatively large amount of storage capacity limited by the amount of physically attached memory.

According to embodiments disclosed herein, per-pattern NFA storage allocation settings 710a-c can be configured for levels 708a-c. Per-pattern NFA storage allocation settings 710a-c can represent a target number of unique nodes to be distributed from each per-pattern NFA to the corresponding level of the levels 708a-c for storage within a given memory mapped to the corresponding level. When generating a per-pattern NFA for each of one or more patterns in the rule set 310, the compiler 306 can be configured to determine the per-pattern NFA storage allocation settings 710a-c in a manner that enables the memory 756a-c mapped to the levels 708a-c to provide sufficient storage capacity.

The per-pattern NFA storage allocation settings 710a-c can represent a target number of unique nodes in the node set of each per-pattern NFA to be distributed to the corresponding level for storage in a given memory mapped to the corresponding level. For example, based on the per-pattern NFA storage allocation setting 710a configured for level 708a, the compiler 306 can distribute a first portion 704a of the corresponding node set 702a of the per-pattern NFA 714a and a second portion 704b of the corresponding node set 702b of the per-pattern NFA 714b for storage in the memory 756a mapped to the level 708a.

Based on the per-pattern NFA storage allocation setting 710b configured for level 708b, compiler 306 may distribute third portion 706a of corresponding point set 702a of per-pattern NFA 714a and fourth portion 706b of corresponding node set 702b of per-pattern NFA 714b for storage within memory 756b mapped to level 708b. This distribution is a target distribution because the number of nodes in a given corresponding node set may not include a target number, such as less than a target number that may have been generated or less than a target number that may be maintained within the corresponding set for distribution.

In this example embodiment, the per-mode NFA storage allocation setting 710c can be configured for the lowest-ranked level 708c of the memory hierarchy 743 and can be specified in a manner that represents an infinite number. In this example embodiment, the memory 756c mapped to the lowest-ranked level 708c can be an HNA off-chip graph memory 156c included in at least one system memory 151, which has a relatively large amount of memory. In this way, the compiler 306 can distribute nodes to the system memory, including distributing any remaining undistributed nodes in each corresponding point set generated for each of the per-mode NFAs 714a-b for storage within the system memory 756c.

It should be understood that the compiler can inherently understand the hierarchy-to-memory mapping and, as such, can exclude certain hierarchies 708a-c. For example, compiler 306 can configure per-pattern NFA storage allocation settings 710a-c and map these settings directly to memories 756a-c based on inherent knowledge of the hierarchy mapping for each of memories 756a-c in memory hierarchy 743. It should also be understood that the per-pattern NFAs, nodes per-pattern NFAs, and number of distributions shown in FIG7A are for illustrative purposes and can be any suitable per-pattern NFAs, nodes, or number of distributions.

FIG7B is a block diagram 721 of an example embodiment of an HNA processing core 408 operatively coupled to a plurality of memories 756 a-c, which can be mapped to tiers 708 a-c in the memory hierarchy 743 of FIG7A and the node cache 451 of FIG4A . Memory 756 a can be the fastest performing memory relative to memories 756 b and 756 c. Memory 756 a can be mapped to the highest-ranked tier 708 a in the memory hierarchy 743. Memory 756 c can be the lowest performing memory relative to the other memories 708 a and 708 b also operatively coupled to the HNA processing core 408.

The highest-ranked memory 756a may be the first memory co-located on chip 722 with the HNA processing core 408. Memory 756b may be the second-highest-ranked memory, which is the second memory co-located on chip 722 with the HNA processing core 408. Relative to the other memories 756b and 756c operatively coupled to the HNA processing core 408, the highest-ranked memory 756a may be the highest-performance memory. The highest-performance memory 756a may have the fastest read and write access times. Memory 756c may be the lowest-performance memory, which may be the largest memory, such as external memory not co-located on chip with the HNA processing core 408.

Corresponding level node transaction sizes 723a-c can be associated with each of the levels 708a-c. Each corresponding level node transaction size can represent the maximum number of nodes that can be fetched from a given memory mapped to the corresponding level for read accesses to the given memory. For example, level node transaction size 723a can be associated with the highest level 708a. Since memory 756a is at the highest level 708a, level node transaction size 723a can represent the maximum number of nodes that can be fetched from memory 756a. Similarly, since memory 756b is at the second highest level 708b, level node transaction size 723b can represent the maximum number of nodes that can be fetched from memory 756b, and since memory 756c is at the next lowest level 708c, level node transaction size 723c can represent the maximum number of nodes that can be fetched from memory 756c.

8 is a block diagram 800 of an example embodiment of a node distribution of multiple per-pattern NFAs. In this example embodiment, a first NFA 814a is generated for a pattern 816a in one or more patterns 804, a second NFA 814b is generated for a second pattern 816b in one or more patterns 804, and a third NFA 814c is generated for a third pattern 816c in one or more patterns 804.

A first portion of node 804a of first per-pattern NFA 814a is distributed to level 808a, which is mapped to first memory 856a in memory hierarchy 812, and a second portion of node 806a is distributed to second level 808b, which is mapped to second memory 856b. In this example embodiment, level 808a is the highest-ranked level, and level 808b is the lowest-ranked level. A third portion of node 804b of second per-pattern NFA 814b is distributed to level 808a, which is mapped to first memory 856a in memory hierarchy 812, and a fourth portion of node 806b is distributed to second level 808b, which is mapped to second memory 856b. A fifth portion of node 804c of third per-pattern NFA 814c is distributed to level 808a mapped to first memory 856a in memory hierarchy 812, and a sixth portion of node 806c is distributed to second level 808b mapped to second memory 856b.

As shown in FIG8 , the second node portion 804b of the second NFA 814b that is distributed for storage within the memory 856a mapped to the level 808a can be smaller than the first and first node portions 804a and the fifth node portion 804c of the third NFA 814c, respectively. This can be the case, for example, if the number of nodes per-pattern NFA 814b is smaller than the number of unique target nodes indicated by the per-NFA storage allocation setting (not shown) of the level 808a. Furthermore, since level 808b is the lowest-ranked level in the memory hierarchy 812, the next per-pattern NFA storage allocation setting (not shown) of level 808b can be significantly larger, thereby enabling all undistributed nodes to be distributed for storage within the memory 856a mapped to the level 808b after being distributed to each level higher than level 808b. Thus, in this example embodiment, second node portion 806a may include more nodes than sixth portion 806c because pattern 816a may be a longer rule than pattern 816c. Further, fourth node portion 806b may be empty because pattern 816b may be relatively short, having few nodes generated for per-pattern NFA 814b, thereby causing all nodes of per-pattern NFA 814b to be distributed to level 808a for storage within memory 856a.

Compiler 306 can distribute the nodes of each per-pattern NFA as part of generating each per-pattern NFA. As disclosed above, a transition from a first node to a second node in an NFA can be specified by first-node metadata that identifies the second node via a next-node address. According to embodiments disclosed herein, compiler 306 can configure the next-node address to include a portion indicating a given memory in a plurality of memories to which the second node has been distributed for storage.

FIG9 is a flow chart of an example embodiment of a method 900 that can be implemented in at least one processor that is operatively coupled to a plurality of levels of memory mapped to a memory hierarchy within a security device that is operatively coupled to a network. The method can begin (902) and generate at least one non-deterministic finite automaton (NFA) (904). Each per-pattern NFA can be generated for a single regular expression pattern and can include a corresponding set of nodes. In this example embodiment, the method can distribute the nodes in the corresponding set of nodes of each per-pattern NFA for storage within a plurality of memories based on the mapped levels and the per-pattern NFA storage allocation configured for these levels (908), and thereafter, the method ends (908).

FIG10 is a block diagram 1000 of another example embodiment of a node distribution for multiple per-pattern NFAs. In this example embodiment, node distributions 1004 and 1006 are shown for nodes stored in a first memory 1056a and a second memory 1056b. The distribution 1004 for each per-pattern NFA 1014a-c can be based on per-pattern NFA storage allocations 1010a and 1010b configured for levels 1008a and 1008b, respectively. In this example embodiment, levels 1008a and 1008b are mapped to first memory 1056a and second memory 1056b, respectively.

Figure 11 is a flowchart 1100 of an example embodiment of a method for distributing nodes of at least one per-mode NFA. According to embodiments disclosed herein, distributing the nodes in the corresponding node set of each generated per-mode NFA may include distributing the nodes in the corresponding node set in a sequential manner including a first distribution of the nodes in the corresponding node set for storage in a first memory of a plurality of memories. The first memory may be mapped to a highest-ranked level in a hierarchy. Based on at least one undistributed node remaining in the corresponding node set after a previous distribution, the distribution may include at least one second distribution of the nodes in the corresponding node set. Each at least one second distribution may be for storage in a given memory of the plurality of memories. The given memory may be mapped to a given level in the hierarchy, each distribution being successively lower than the highest-ranked level.

The sequential manner may include distributing nodes from a plurality of nodes of a given per-pattern NFA in the at least one per-pattern NFA, the nodes representing a given number of consecutive elements of a given regular expression pattern for which the given per-pattern NFA was generated. Further, according to embodiments disclosed herein, each at least one second distribution includes distributing at least one next node identified by a next node address included in metadata associated with at least one previous node in an immediately preceding second distribution.

The method may start (1102) and set a given level to the highest-ranked level in a memory hierarchy (1104). The method may set a given per-pattern NFA to be the first per-pattern NFA in at least one NFA generated from a set of one or more regular expression patterns (1106). The method may check the number of undistributed nodes of the given per-pattern NFA (1108). If the number of undistributed nodes of the given per-pattern NFA is zero, the method may check whether the given per-pattern NFA is the last NFA generated from the set of one or more regular expression patterns (1116).

In this example embodiment, if the given per-pattern NFA is the last per-pattern NFA generated, the method may check whether the given level is the lowest-ranked level (1120), and if the given level is the lowest-ranked level, then the method ends (1126). However, if the check (1120) as to whether the given level is the lowest-ranked level is false, the method may set the given level to the next successively lower level (1124) and again set the given per-pattern NFA to the first per-pattern NFA of at least one NFA generated from the set of one or more regular expression patterns (1106) and continue checking the number of undistributed nodes of the given per-pattern NFA (1108). If the number of undistributed nodes of the given per-pattern NFA is zero, then the method may continue as disclosed above.

If the check (1108) of the number of undistributed nodes for the given per-pattern NFA is non-zero, the method may check whether the given level is the lowest-ranked level (1110). If so, the method may distribute the number of undistributed nodes to a given memory mapped to the given level (1114), and the method may check whether the given per-pattern NFA is the last NFA generated from the set of one or more regular expression patterns (1116). If so, the method may continue as disclosed above. If not, the method may set the given per-pattern NFA to the next per-pattern NFA generated (1118), and the method may iteratively check the number of undistributed nodes for the given per-pattern NFA again (1108), with the given per-pattern NFA being updated to become the next per-pattern NFA generated.

If the check (1110) of whether the given level is the lowest-ranked level is false, the method may check whether the number of undistributed nodes of the given per-pattern NFA exceeds the number of nodes indicated by the per-pattern NFA storage allocation setting configured for the given level (1112). If so, the method may distribute the number of undistributed nodes indicated by the per-pattern NFA storage allocation setting configured for the given level for storage in a given memory mapped to the given level (1122), and check whether the given per-pattern NFA is the last NFA generated from the set of one or more regular expression patterns (1116). If so, the method may continue as disclosed above.

If the check (1116) as to whether the given per-pattern NFA is the last per-pattern NFA generated is false, the method may set the given per-pattern NFA to be the next per-pattern NFA generated (1118), and the method may iteratively check the number of undistributed nodes of the given per-pattern NFA again (1108), the given per-pattern NFA being updated to be the next per-pattern NFA generated.

However, if the check (1112) as to whether the number of undistributed nodes for the given per-mode NFA exceeds the number of nodes represented by the per-mode NFA storage allocation setting configured for the given level is false, the method may distribute that number of undistributed nodes to the given memory mapped to the given level (1114) and proceed as disclosed above.

According to embodiments disclosed herein, a per-mode NFA storage allocation setting can represent a target number of unique nodes by an absolute value. This absolute value can be a common value for each corresponding set of nodes, which enables each corresponding set of nodes to have the same value for the target number of unique nodes to be stored within a given memory mapped to a corresponding level. For example, as shown in FIG10 , each of the per-mode NFAs 1014 a-c has a first portion 1004 selected to represent the same number of nodes from each of the per-mode NFAs 1014 a-c to be distributed to the memory 1056 a mapped to the level 1008 a for which the per-mode storage allocation setting 1010 a is configured.

Alternatively, the target number of unique nodes can be represented by a percentage value applied to the corresponding total number of nodes in each corresponding node set, which enables each corresponding node set to have a separate value for the target number of unique nodes stored within a given memory mapped to the corresponding hierarchy. For example, if a number such as 25% is configured for per-mode NFA storage allocation setting 1010a (which is configured for hierarchy 1008a), then first portion 1004 will include 25% of the nodes from per-mode NFAs 1014a-c. Since the number of nodes in each per-mode NFA 1014a-c can be different, the number of nodes from each of per-mode NFAs 1014a-c can be different.

The per-mode NFA storage allocation setting may include a first per-mode NFA storage allocation setting and a second per-mode NFA storage allocation setting. The tiers may include a highest-ranked tier and a second-highest-ranked tier. The first per-mode NFA storage allocation setting may be configured for the highest-ranked tier. The second per-mode NFA storage allocation setting may be configured for the second-highest-ranked tier. The first per-mode NFA storage allocation setting may be less than the second per-mode NFA storage allocation setting. For example, the number of nodes represented from each per-mode NFA for distribution to the highest-performance memory may be less than the number of nodes represented for the lowest-performance memory (e.g., system memory), which may represent an unlimited number of nodes.

Embodiments disclosed herein can maximize the number of nodes in a given distribution, with the maximized number being limited by the corresponding per-mode NFA storage allocation setting in the per-mode NFA storage allocation setting configured for a given hierarchy. For example, the number of nodes represented by the per-mode NFA storage allocation setting can be ten. Thus, each per-mode NFA that includes ten or more undistributed nodes will distribute ten nodes. Each per-mode NFA that includes ten undistributed nodes will distribute a corresponding number of nodes in the undistributed number.

As disclosed above, a walker (such as walker 320 of FIG. 3A ) can be configured to walk nodes of a segment of a payload of an input stream through a unified DFA (such as the same DFA 312 of FIG. 3A ) and at least one per-pattern NFA (such as per-pattern NFA 314 of FIG. 3A ) in an attempt to match regular expression patterns in the input stream. During the compilation phase, a compiler (such as compiler 306 of FIG. 3A ) can generate the unified DFA 312 and the at least one per-pattern NFA 314. The nodes of the unified DFA 312 and the at least one per-pattern NFA 314 can be stored in a plurality of memories in a memory hierarchy, such as the plurality of memories 756 a-c in the memory hierarchy 743 of FIG. 7A .

10 and 11 , the corresponding node sets of each per-pattern NFA generated by compiler 306 can be distributed and stored in one or more of the plurality of memories 756a-c based on the node distribution determined for each corresponding set by compiler 306. As disclosed above, compiler 306 can determine each node distribution based on the hierarchies (e.g., hierarchies 708a-c of FIG. 7A ) mapped to the plurality of memories 756a-c and the per-pattern NFA storage allocation settings (e.g., 710a-c) configured for the hierarchies 708a-c.

Thus, the walker 320 can be configured to walk the nodes in the corresponding node set of the per-pattern NFA 314, which can be distributed and stored in one or more of the plurality of memories 756a-c according to the levels 708a-c mapped to the plurality of memories 756a-c and the per-pattern NFA storage allocation settings 710a-c configured for the levels 708a-c based on the node distribution determined by the compiler 306. As disclosed above with reference to FIG6, the walker 320 can be configured to walk the corresponding node set of the per-pattern NFA 314 based on partial matches of corresponding regular expression patterns in the input stream as determined by the walker 320 during the walking of the unified DFA 312.

FIG12 is a flowchart 1200 of another example embodiment of a method that can be implemented in at least one processor operatively coupled to a plurality of levels of memory mapped to a memory hierarchy within a security device operatively coupled to a network. The method can begin (1202) and walk a node in a corresponding set of nodes of a given per-pattern NFA in at least one per-pattern NFA generated for a corresponding regular expression pattern based on a segment of a payload of an input stream. The corresponding set of nodes can be distributed and stored in one or more of the plurality of memories based on a node distribution determined based on the levels mapped to the plurality of memories and a per-pattern NFA storage allocation setting configured for the levels (1204). Thereafter, in this example embodiment, the method ends (1206).

The walker 320 can be configured to walk from the given node in the corresponding node set to the next node with a positive match of a given segment at a given node based on (i) the payload and (ii) the next node address associated with the given node. The next node address can be configured to identify the given memory in which the next node is stored in the given memory and multiple memories (such as multiple memories 756a-c of Figure 7A). For example, turning to the example embodiment of Figure 5A, the walker 320 can walk node N4 514 based on the positive match of the segment 522c at node N2 510, because node N2 510 can be configured to match the given segment at the given offset in the payload with the character element 'a'. The metadata (not shown) associated with node N2 510 can identify the next node (such as node N4 514) so as to traverse (i.e., walk) based on the positive match of the given segment at the given offset with the character element 'a'.

For example, the metadata associated with node N2 510 may include a next node address, which is an address of node N4 514 or a pointer or index or any other suitable identifier for identifying the next node N4 514, so as to be traversed based on a positive match at node N2 510. The metadata associated with node N2 510 may further identify a given memory in the plurality of memories storing the next node N4 514. The given memory may be identified in any suitable manner, such as by configuring a specific bit of the memory in conjunction with or as part of a next node address (not shown) of the next node 514. Thus, the walker 320 may be configured to extract the next node N4 514 from the given memory identified by the next node address associated with the given node N2 510, so as to walk the next node N4 514 according to the next segment at the next offset (e.g., the next segment 522d at the next offset 520d in FIG. 5A ).

Next node N4 514 can be cached in the node cache. Return to Fig. 4 A, the example embodiment of HPU 425 includes the node cache 451 that can be operatively coupled to HNA processing core 408. The size of node cache 451 can be used for storing at least a threshold number of nodes. In this way, HNA processing core 408 can cache one or more nodes (up to a threshold number of nodes) in node cache 451. As disclosed above, HNA processing core 408 can be configured to be used for implementing the various aspects of NFA processing of walker 320. In this way, walker 320 can retrieve next node N4 514 from a given memory in node cache 451 or the multiple memories 756a-c based on whether the extraction (that is, read access) of next node N4 514 causes cache miss. According to the embodiment disclosed here, the entry in node cache 451 can be replaced based on a cycle or least recently used (LRU) replacement strategy. Walker 320 may be configured to maintain an index of one or more entries in node cache 451 for use in implementing a round-robin or LRU replacement strategy.

If the fetching of node N4 514 results in a cache miss, the HNA processing core 408 may fetch node N4 514 from the given memory that statically stores node N4 514 and also cache node N4 514 in the node cache 451. Based on the hierarchical node transaction size associated with the given memory hierarchy, the HNA processing core 408 may cache additional nodes from the given memory. Node N4 514 and any additional cached nodes may be arranged in a contiguous manner within the corresponding per-mode NFA. For example, based on the hierarchical node transaction size associated with the given memory hierarchy, the HNA processing core 408 may cache node N5 515 and node N4 514, arranged in a contiguous manner, together within the per-mode NFA 504.

According to embodiments disclosed herein, a corresponding hierarchy node transaction size (not shown) can be associated with each of the hierarchies 708a-c. Each corresponding hierarchy node transaction size can represent a maximum number of nodes to be fetched from a given memory mapped to the corresponding hierarchy for a read access to the given memory. For example, the hierarchy node transaction size associated with the highest-ranked hierarchy can have a maximum number of nodes, i.e., one or two nodes. According to embodiments disclosed herein, the highest-ranked hierarchy in the hierarchy can be associated with the smallest hierarchy node transaction size among the hierarchy node transaction sizes associated with the hierarchy.

The hierarchical node transaction size can be expressed in any suitable manner, such as by directly specifying the maximum number of nodes, or by specifying a number of bits that can be a multiple of the size of the maximum number of nodes represented. According to embodiments disclosed herein, the node cache 451 can be organized into multiple rows. The size of each row can be determined based on the node bit size, and each row can include additional bits for use by the HNA processing core 408. Each row can be the smallest quantum (i.e., granularity) of transactions from each of the multiple memories.

According to embodiments disclosed herein, the highest-ranked memory can be a memory co-located on-chip with the HNA processing core 408. The highest-ranked memory can be the memory with the highest performance relative to the other memories in the plurality of memories. The highest-performance memory can have the fastest read and write access times. The transaction size (e.g., the quantum size of data read from the highest-performance memory) can be one or two rows, which can include one or two nodes, respectively.

In contrast, the lowest-ranked tier can be mapped to the lowest-performing memory in the plurality of memories. The lowest-performing memory can be the slowest-performing memory with relatively longer read and write access times than the other memories in the plurality of memories. For example, the slowest-performing memory can be the largest memory, such as external memory that is not located on-chip with the HNA processing core 408. In this way, the number of read accesses to such memory can be reduced by having a larger transaction size (e.g., four rows) per read access.

According to embodiments disclosed herein, the hierarchical node transaction size associated with the lowest-ranked tier can be configured to evict and replace one or more rows from the node cache 451 with one or more rows extracted from the corresponding memory mapped to the lowest-ranked tier. The one or more rows can be determined based on one or more rows storing a threshold number of nodes. Thus, if the corresponding tier is the lowest-ranked tier among the tiers, the corresponding hierarchical node transaction size can enable the HNA processing core 408 to cache a threshold number of nodes from a given memory. Thus, if the corresponding tier is the lowest-ranked tier among the tiers, the HNA processing core 408 can be configured to evict a threshold number of nodes cached in the node cache 451.

According to embodiments disclosed herein, the node cache 451 can be configured to cache a threshold number of nodes. The threshold number of nodes can be the maximum number of nodes that can be read based on a maximum transaction size among all transaction sizes associated with the plurality of memories. For example, the maximum transaction size among all transaction sizes of the plurality of memories can be a given transaction size associated with the lowest-ranked tier that can be mapped to, for example, an external memory that is not co-located on-chip with the HNA processing core 408.

Caching the one or more nodes in the node cache 451 may be based on a cache miss of a given node in the one or more nodes read from a given memory in the plurality of memories and a corresponding level node transaction size associated with a corresponding level in the hierarchy mapped to the given memory. The corresponding level node transaction size associated with the corresponding level may represent a maximum number of nodes that may be fetched from the given memory mapped to the corresponding level for a read access to the given memory.

HNA processing core 408 can be configured to use LRU or cyclic replacement strategy to evict one or more nodes of institute's cache from node cache 451.According to the embodiment disclosed herein, if the corresponding level that is mapped to given memory is higher than the lowest level in the level, then the total number of one or more cached nodes that can be evicted based on the level determination.For example, if the level is associated with a level node transaction size of 1, the total number of cached nodes that the node cache evicts is 1, and the entry that can be evicted based on LRU or cyclic replacement strategy is determined.Total being 1 is for illustrative purposes, and it should be understood that any suitable level node transaction size can be used.

13A is a flowchart 1300 of an example embodiment of a method that can be implemented in at least one processor operatively coupled to a plurality of memories in a memory hierarchy and a node cache within a security device operatively coupled to a network. The method can begin (1302) and store a plurality of nodes of at least one finite automaton in a plurality of memories (1304). The method can cache one or more nodes in a given memory in a plurality of memories at a level in the memory hierarchy in the node cache (1306) based on a cache miss for a given node in the one or more nodes and a level node transaction size associated with the level. Thereafter, in this example embodiment, the method ends (1308).

Figure 13B is a block diagram 1341 of an example embodiment of a payload 1342 and a segment 1316 in the payload 1342 with a corresponding offset 1318. In an example embodiment, the nodes in the per-pattern NFA graph 504 of Figure 5A can be walked based on the payload 1342 of Figure 13B. For example, the walker 320 can attempt to match the segment 1316 of the payload 1342 at the node in the per-pattern NFA graph 504 to attempt to match the payload 1342 to the regular expression pattern 502 of Figure 5A.

Multiple nodes in the per-pattern NFA graph 504 can be stored in multiple memories, such as memories 756a-c of FIG. 7A . One or more of the multiple nodes (e.g., nodes N0 506, N1 508, N2 510, and N3 512 in the per-pattern NFA graph 504) can be stored in a given memory (e.g., the highest-performing memory 756a of FIG. 7A ) at a level (e.g., the highest-ranked level 708a) in a memory hierarchy (e.g., the memory hierarchy 743). As disclosed below with reference to FIG. 13C and FIG. 13D , based on a cache miss for a given node (e.g., node N0 506) and a hierarchical node transaction size 723a associated with the level 708a, nodes N0 506, N1 508, N2 510, and N3 512 can be cached in a node cache (e.g., the node cache 451 of FIG. 4A ).

As shown in FIG13B , payload 1342 includes segments 1322a-n (i.e., h, y, x, etc.) with corresponding offsets 1320a-n (i.e., 0, 1, 2, etc.). Walker 320 can walk one segment of segments 1322a-n of payload 1342 at a time through NFA graph 504 to match regular expression pattern 502 with input stream. A given segment of segments 1322a-n to be used to walk a given node can be determined based on the corresponding offset of the given segment of offsets 1320a-n to the current offset within payload 1342. As disclosed above with reference to FIG5A , walker 320 can update the current offset by incrementing or decrementing the current offset. Walker 320 can be configured to select upper ε-path 530a based on traversing separating node N1 508 because upper ε-path 530a represents a lazy path.

13C is a table 1338a of an example embodiment of a processing cycle of walking the per-mode NFA graph 504 of FIG. 5A according to the payload of FIG. 13B by selecting a lazy path at the split node N1 508 .

FIG13D is a table 1338b, which is a continuation of table 1338a of FIG13C. As shown in tables 1338a and 1338b, processing cycles 1340a-mm may include walking the current node 1330 according to the segment at the current offset 1332 to determine a matching result 1334 and a walker action 1336 based on the matching result 1334. In this example embodiment, the walker 320 may walk the starting node N0 506 according to the segment 1322a (i.e., "h") at the current offset 1320a during processing cycle 1340a. As disclosed above with reference to FIG6, the starting node N0 506 and the current offset 1320a may be specified based on the matching result generated by the DFA processing performed by the HFA processor 110.

When segment 1322a matches the character "h" at node N0 506 in each pattern NFA graph 504, the NFA processing performed by the HNA processing core 408 produces a determination by the walker 320 that the match result 1334 is a positive match result. As specified by the compiler 306 through metadata (not shown) associated with the starting node N0 506, the walker 320 can walk in the forward direction and extract the next node indicated by the metadata associated with node N0 506 and can increment the current offset from 1320a (i.e., "0") to 1320b (i.e., "1"). In this example embodiment, the next node indicated by node N0 506 is the separation node N1 508. As such, the walker 320 takes action 1336 for processing cycle 1340a, which includes updating the current offset to "1" in the payload 1342 and transitioning to the separation node N1 508. The transition can include extracting (also referred to herein as loading) the separation node N1 508.

When split node N1 508 presents multiple conversion path options, such as epsilon paths 530a and 530b, actions 1336 for processing cycle 1340b may include selecting upper epsilon path 530a and extracting node N2 510 that is not associated with payload 1342 without being consumed (i.e., processed) from payload 1342. Since split node N1 508 does not perform a matching function, current offset/segment 1332 is not changed, and therefore, no payload is consumed (i.e., processed) in processing cycle 1340b.

Because the split node N1 508 presents multiple path options, action 1336 can include storing unexplored context, such as by storing an indirect or direct identifier and current offset 1320b (i.e., "1") for node N3 512. In the event of a negative match result along the selected partially matched path, for example, if a negative match result is determined at node N2 510 or multiple nodes along the path extending from node N2 510, storing the unexplored context can enable the walker 320 to remember to return to node N3 512 to walk node N3 512 according to the segment at offset 1320b "1" in the payload 1342.

In this example embodiment, selection of the ε-transition path 530a may result in a detected match failure at node N2 510 or at a subsequent node of the current thread (e.g., node N4 514). For example, based on selection of the upper path (i.e., ε-transition path 530a), in processing cycle 1340c, the walker 320 may extract node N2 510 and attempt to match segment 1322b (i.e., "y") at the current offset 1320b (i.e., "1") with element "a" of node N2 510. Because "y" does not match element "a" at node N2 510, action 1336 in processing cycle 1340c may include popping an entry from the run stack 460 of FIG. 4A.

The entry popped may be the most recently pushed entry, such as the stored entry pushed in processing cycle 1340b indicating node N3 512 and offset 1320b (i.e., "1") in this example embodiment. Thus, if a match failure is detected, the threads stored for the epsilon transition path 530b may be traversed, as is the case illustrated in processing cycles 1340d, 1340g, 1340j, 1340m, 1340p, 1340s, 1340w, 1340z, 1340cc, 1340ff, and 1340ii. Storing untraversed transition paths may include storing an entry on a stack, such as the run stack 460 of FIG. 4A, by storing an entry including an identifier of a next node associated with an indication of the current offset.

In processing cycle 1340d, the walker 320 may also transition and walk node N3 512 based on segment "y" located at offset 1320b in payload 1342. Thus, since the element associated with node N3 512 indicates a positive match for a segment that is not a line break, processing cycle 1340d shows that match result 1334 is positive in processing cycle 1340d. Action 1336 in processing cycle 1340d may include updating the current offset to offset 1320c and transitioning back to separate node N1 508, which may be the next node indicated by node N3 512.

Since all arcs transitioning from the split node 508 are ε transitions, when the current offset is not updated in processing cycle 1340e, the walker 320 can again select one of the multiple path options and not consume (i.e., process) segments from the payload 1342. In this example embodiment, the walker 320 again selects the ε transition path 530a. As such, the walker 320 again stores the thread on the run stack 460 by pushing node N3 512 and the current offset, which is now 1320c (i.e., "2"). As shown in processing cycle 1340f, the walker 320 extracts node N2 510 and attempts to match segment 1322c (i.e., "x") at offset 1320c (i.e., "2") with element "a" of node N2 510.

Since "x" does not match at node N2 510, the walker 320 may again pop an entry from the run stack 460. The popped entry may be the most recently pushed entry, such as the storage entry pushed in processing cycle 1340e indicating node N3 512 and offset 1320c (i.e., "2") in this example embodiment. Thus, the walker 320 may transition and walk node N3 512 again in processing cycle 1340f based on segment "x" located at offset 1320c in payload 1342. Thus, since "x" is not a newline character, processing cycle 1340g shows that the match result 1334 is positive, and action 1336 in processing cycle 1340g may include updating the current offset to offset 1320d (i.e., "3") and transitioning back to the split node N1 508, which may be the next node indicated by the metadata associated with node N3 512.

The walker 320 may continue walking segments of the payload 1342 through the per-pattern NFA 504 as indicated by subsequent processing cycles 1340i-mm shown in Tables 1338a and 1338b of Figures 13C and 13D, respectively, until reaching marker node N5 515. As shown in processing cycle 1340mm of Table 1338b, the walker 320 traverses marker node N5 515, which may be associated with metadata indicating a final (i.e., complete or entire) match of the regular expression pattern 502 in the input stream.

In this example embodiment, walking the payload 1342 through the per-pattern NFA graph 504 may include identifying a mismatch at node N3 512, selecting a lazy path at the split node N1 508 by selecting the upper epsilon path 530a, and traversing node N2 510. Based on the mismatch at node N2 520, node N3 512 may be traversed again, and so on, until a match at node N2 520 is determined. For example, as shown with respect to processing cycles 1340b-d, 1340e-g, 1340h-j, 1340k-m, 1340n-p, and 1340q-s, nodes N1 508, N2 510, and N3 512 are traversed under both temporal and spatial locality until a positive match is determined at node N2 510 in processing cycle 1340u, and as shown in processing cycles 1340x-z, 1340aa-cc, 1340dd-ff, and 1340gg-ii, until a positive match is determined at node N2 510 in processing cycle 1340kk. Thus, most of the processing cycles of Tables 1338a and 1338b show that walker 320 can traverse nodes N1 508, N2 510, and N3 512 under both temporal and spatial locality.

According to embodiments disclosed herein, using a node cache (such as node cache 451 of FIG. 4A ) to walk segments of an input stream through a finite automaton can further optimize the performance of the walk. For example, as disclosed above with reference to FIG. 7A , the matching performance of the walker 320 can be optimized by storing consecutive nodes, such as nodes N0 506, N1 508, N2 510, and N3 512 of portion 509 of the per-pattern NFA 504 of FIG. 5A , in a faster-performing memory that can be located at a higher-ranked level relative to another memory that can store consecutive nodes N4 514 and N5 515.

As disclosed above, earlier nodes (e.g., nodes N0 506, N1 508, N2 510, and N3 512 included in portion 509 of per-mode NFA 504 of FIG. 5A ) can be stored in the highest-performance memory that can be located at the highest-ranked level. For example, nodes N0 506, N1 508, N2 510, and N3 512 included in portion 509 can be stored in memory 756a of FIG. 7A , which can be located at the highest-ranked level (e.g., level 708a in memory hierarchy 743). According to embodiments disclosed herein, nodes N0 506, N1 508, N2 510, and N3 512 included in portion 509 can be stored in memory 756a based on per-mode NFA storage allocation setting 710a that can be configured for level 708a.

In this example embodiment, the level node transaction size associated with the highest-ranked level 708a (e.g., level node transaction size 723a of FIG. 7B ) can represent four nodes in this example embodiment. For example, the level node transaction size 723a can include reading one or more rows from memory 756a. For example, data stored at one or more addresses of memory 756a can be read based on a read access, and four nodes can be read (i.e., retrieved, loaded, or extracted) from memory 756a. Thus, the level node transaction size 723a indicates that four nodes can be read from memory 756a at the highest-ranked level 708a when four nodes can be read based on a single read access that causes the four nodes to be read. For example, the number of nodes read per transaction (i.e., read access) can be determined based on the number of nodes stored per row in a given memory and the number of rows (i.e., addresses) read from a given memory at a given level. In the example embodiment of FIG. 7B , memory 756 b may be associated with level node transaction size 723 b , and memory 756 c may be associated with level node transaction size 723 c .

In the example embodiment, traversing node N0 506 in processing cycle 1340a will cause a cache miss because node N0 506 is not already cached in node cache 451. As a result, since hierarchical node transaction size 723a represents four nodes in this example embodiment, four nodes, namely, nodes N0 506, N1 508, N2 510, and N3 512, may be brought from memory 756a to node cache 451.

As a result, the walker 320 can access nodes N1 508, N2 510, and N3 512 from the node cache 451 until processing cycle 1340v, in which the walker 320 traverses node N4 514 according to segment 1322g (i.e., "q") at offset 1320g (i.e., "8") in the payload 1342 based on the positive match at node N2 510 determined in processing cycle 1340u. In this way, the node cache 451 can be advantageously utilized to further optimize walking performance by caching multiple nodes in the per-pattern NFA that have temporal and spatial locality relationships with the per-pattern NFA (such as nodes N1 508, N2 510, and N3 512 in this example embodiment). For an NFA generated from multiple patterns, such node temporal and spatial locality relationships within the per-pattern NFA will not exist. Because the embodiments disclosed herein may be based on an NFA generated as a per-pattern NFA, optimizations that the node cache 451 can implement are provided.

Thus, in addition to reducing the number of false positives in NFA processing performed by the HFA processor 110, embodiments disclosed herein can further optimize matching performance by caching nodes during the walking of the nodes of each per-pattern NFA, which distributes the nodes across multiple memories in the memory hierarchy based on node locality within the corresponding per-pattern NFA. As disclosed above, embodiments disclosed herein can advantageously distribute the nodes of each per-pattern NFA across multiple memories in the memory hierarchy based on the understanding that the longer the rule (i.e., pattern), the less likely it is to access (i.e., walk or traverse) the nodes generated from the portion at the end of the rule (i.e., pattern). Further, according to embodiments disclosed herein, the size of the node cache can be advantageously determined based on the maximum transaction size granularity of the multiple memories to further optimize matching performance by reducing the number of accesses to slower performing memories. In addition, the embodiments disclosed herein regarding hierarchical node transaction size further optimize matching performance by being able to efficiently utilize a limited number of entries in the node cache and by being able to determine the total number of cached nodes based on a given transaction (i.e., read access) size associated with a level.

Figure 14 is a block diagram of an example embodiment of the internal structure of a computer 1400 in which the various embodiments disclosed herein may be implemented. Computer 1400 includes a system bus 1402, where a bus is a collection of hardware lines used to transfer data between components of a computer or processing system. System bus 1402 is essentially a shared pipe that couples the various components of a computer system (e.g., processor, disk storage, memory, input/output ports, network ports, etc.), enabling information to be transferred between these components. Operatively coupled to system bus 1402 is an I/O device interface 1404 for coupling various input and output devices (e.g., keyboard, mouse, display, printer, speakers, etc.) to computer 1400. A network interface 1406 allows computer 1400 to be coupled to various other devices attached to a network. Memory 1408 provides volatile storage for computer software instructions 1410 and data 1412 that may be used to implement the embodiments disclosed herein. Disk storage 1414 provides non-volatile storage for computer software instructions 1410 and data 1412 that may be used to implement the embodiments disclosed herein. A central processing unit 1418 is also operatively coupled to system bus 1402 and provides for executing computer instructions.

Further embodiments disclosed herein may be configured using a computer program product; for example, a controller may be programmed in software for implementing the example embodiments disclosed herein. Further embodiments disclosed herein may include a non-transitory computer-readable medium containing instructions that can be executed by a processor, and when executed, these instructions cause the processor to perform the methods disclosed herein. It should be understood that the elements in the block diagrams and flow charts described herein may be implemented in software, hardware, firmware, or other similar implementations to be determined in the future. In addition, the elements in the block diagrams and flow charts described herein may be combined or separated in software, hardware, or firmware in any manner.

It should be understood that the term "herein" may be translated into an application or patent incorporating the teachings introduced herein, such that the subject matter, definitions, or data form the incorporated application or patent.

If implemented in software, the software can be written in any language that can support the example embodiments disclosed herein. The software can be stored in the form of a computer-readable medium, such as a random access memory (RAM), a read-only memory (ROM), a compact disc read-only memory (CD-ROM), etc. In operation, a general-purpose or special-purpose processor loads and executes the software in a manner well understood in the art. It should be further understood that these block diagrams and flow charts may include more or fewer elements that are differently arranged or oriented, or differently presented. It should be understood that an implementation may specify the number of block diagrams, flow charts, and/or network diagrams and block diagrams and flow charts that illustrate the execution of an embodiment of the present invention.

While the invention has been particularly shown and described with reference to example embodiments thereof, it will be understood by those skilled in the art that various changes in form and details may be made therein without departing from the scope of the invention as encompassed by the appended claims.

Claims (45)

1. A security device operatively coupled to a network, the security device comprising: At least one central processing unit (CPU) core; and At least one hyper-nondeterministic finite automaton (HNA) processor, operatively coupled to the at least one CPU core and dedicated to nondeterministic finite automaton (NFA) processing, the at least one HNA processor comprising: Multiple super clusters, each super cluster comprising multiple clusters, each of the multiple clusters comprising multiple HNA processing units (HPUs), the at least one CPU core being configured to select at least one super cluster among the multiple super clusters; An on-chip instruction queue for an HNA is configured to store at least one HNA instruction; and An HNA scheduler is configured to select a given HPU from among the plurality of HPUs of the selected at least one supercluster and assign the at least one HNA instruction to the selected given HPU to initiate a match on at least one regular expression pattern in an input stream received from the network. 2. The security device of claim 1, wherein each supercluster further includes a supercluster graphics memory dedicated to the respective supercluster, the supercluster graphics memory being accessible to the respective plurality of HPUs of the respective plurality of clusters of the respective supercluster and configured to statically store a subset of nodes of at least one per-mode NFA, the subset of nodes being determined by a compiler of the at least one per-mode NFA. 3. The safety device as described in claim 2, wherein: Each supercluster further includes at least one supercluster character class memory dedicated to the corresponding supercluster, and each at least one supercluster character class memory is configured to statically store multiple regular expression pattern character class definitions. 4. The security device as claimed in claim 3, wherein the supercluster graphics memory and the at least one supercluster character class memory are unified. 5. The security device as claimed in claim 3, wherein the corresponding plurality of HPUs of the corresponding plurality of clusters of the corresponding supercluster share the at least one supercluster character class memory. 6. The safety device as claimed in claim 1, wherein: Each supercluster further includes at least one supercluster character class memory, each of which is dedicated to a given cluster among a plurality of clusters of a given supercluster and shared by a plurality of HPUs of that given cluster, each of which is configured to statically store a plurality of regular expression pattern character class definitions. 7. The security device of claim 1, wherein the at least one CPU core is further configured to select the at least one supercluster among the plurality of superclusters by restricting supercluster selection based on a graphical identifier associated with the at least one HNA instruction. 8. The security device of claim 7, wherein the graphical identifier is associated with a given per-mode NFA among a plurality of per-mode NFAs, and limiting the selection of the supercluster includes determining that at least one node of the given per-mode NFA is stored in a supercluster graphical memory dedicated to the selected at least one supercluster. 9. The safety device as claimed in claim 7, wherein: This graphical identifier is associated with a given per-mode NFA among a plurality of per-mode NFAs; The HNA scheduler is configured to select the given HPU from a set of HPU restrictions, the set of HPU restrictions including each of the respective plurality of HPUs in each of the respective plurality of clusters in the selected at least one supercluster; and the at least one CPU core is further configured to select the at least one supercluster from the plurality of superclusters based on a determination that at least one node of the given per-mode NFA associated with the graph identifier is stored in a supercluster graph memory dedicated to the selected at least one supercluster. 10. The security device of claim 9, wherein the HNA scheduler is further configured to select the given HPU from the HPU limit set based on a single round-robin scheduling of a plurality of HPUs in the HPU limit set. 11. The security device of claim 9, wherein the HNA scheduler is further configured to select the given HPU from the HPU limit set based on the instantaneous loading of each HPU in the HPU limit set. 12. The safety device as claimed in claim 1, wherein: Each supercluster further includes a dedicated supercluster graphics memory; and Each supercluster graphics memory is configured to store at least one node of at least one per-mode NFA among a plurality of per-mode NFAs to replicate the at least one node in each supercluster graphics memory of the at least one HNA processor for each supercluster. 13. The safety device as claimed in claim 12, wherein: The at least one CPU core is further configured to provide the HAN scheduler with options to select the at least one supercluster based on determining that a given per-mode NFA in at least one per-mode NFA associated with the at least one HNA instruction is replicated; and The HNA scheduler is further configured to be used for: The at least one supercluster is selected based on the provided option and (i) a first round-robin scheduling of the plurality of superclusters, (ii) a first instantaneous loading of the plurality of superclusters, or (iii) a combination of (i) and (ii); and The given HPU is selected from the plurality of HPUs of the plurality of clusters of the selected at least one super cluster based on a second round scheduling of the plurality of HPUs of the plurality of clusters of the selected at least one super cluster, a second instantaneous loading of the plurality of HPUs of the plurality of clusters of the selected at least one super cluster, or a combination thereof. 14. The security device of claim 1, wherein the at least one HNA processor further includes an HNA on-chip graphics memory accessible to the plurality of HPUs of the plurality of superclusters, the HNA on-chip graphics memory being configured to statically store a subset of nodes of at least one per-mode NFA, the subset of nodes being determined by a compiler of the at least one per-mode NFA. 15. The security device of claim 1, wherein the at least one HNA command is a first at least one HNA command, and the security device further comprises: At least one system memory, operatively coupled to the at least one CPU core and the at least one HNA processor, the at least one system memory being configured to include: An external instruction queue for storing at least one second HNA instruction to be transferred to the on-chip instruction queue of the HNA processor; and An HNA chip-external graphics memory is configured to statically store a subset of nodes of at least one per-mode NFA, the subset of nodes being determined by a compiler of the at least one per-mode NFA. 16. The safety device of claim 15, further comprising: At least one local memory controller (LMC), wherein the at least one LMC is operatively coupled to the at least one HNA processor and the at least one system memory, and a given LMC of the at least one LMC is configured to enable non-coherent access to the at least one system memory so that the at least one HNA processor can access the HNA off-chip graphics memory. 17. The security device of claim 15, wherein the at least one system memory is further configured to include an HNA data packet memory configured to continuously store a plurality of payloads, each of the plurality of payloads having a fixed maximum length and associated with a given HNA instruction of either the first at least one HNA instruction stored in the HNA on-chip instruction queue or the second at least one HNA instruction to be transmitted to the HNA on-chip instruction queue. 18. The security device of claim 17, further comprising at least one LMC, wherein the at least one system memory is further configured to include: An HNA input stack partition is configured to store at least one HNA input stack, each of the at least one HNA input stack being configured to store at least one HNA input job for at least one HPU of at least one of the plurality of HPUs of the plurality of super clusters; An off-chip runtime stack partition is configured to store at least one off-chip runtime stack to extend the storage of at least one on-chip runtime stack, each of the at least one on-chip runtime stack being configured to store at least one runtime HNA job for the at least one HPU. An external HNA save buffer partition is configured to expand the storage of at least one on-chip save buffer, each of the at least one on-chip save buffer being configured to store at least one runtime HNA operation for the at least one HPU based on the detection of a payload boundary; and An external HNA result buffer partition is configured to store at least one final matching result entry of the at least one regular expression pattern determined by the at least one HPU for matching in the input stream, wherein each of the at least one stored HNA instruction identifies the following: a given HNA input stack of the HNA input stack partition, a given HNA external run stack of the HNA external run stack partition, a given HNA external save buffer of the HNA external save buffer partition, and a given HNA external result buffer of the HNA external result buffer partition. 19. The safety device of claim 18, further comprising at least one LMC, wherein a given LMC of the at least one LMC is configured to: This enables the at least one HNA processor to access the HNA data packet memory, HNA input stack partition, HNA off-chip instruction queue, HNA off-chip execution stack partition, HNA off-chip save buffer partition, and HNA off-chip result buffer partition via a consistent path; and This enables the at least one HNA processor to access the external graphics memory of the HNA chip via a non-uniform path. 20. The security device of claim 1, wherein each HPU in the plurality of HPUs of the plurality of superclusters comprises: A node cache is configured to cache one or more nodes from a supercluster graphics memory, an on-chip graphics memory, or an off-chip graphics memory. A character class cache is configured to cache one or more regular expression pattern character class definitions from a supercluster character class store; A payload buffer is configured to store a given payload from an HNA packet data memory, wherein the at least one HNA instruction includes an identifier for a location in the given payload within the HNA packet data memory; A stack top register is configured to store a single HNA operation; A runtime stack is configured to store multiple HNA jobs; A unified memory is configured to store a first content of a save stack and a second content of a match result buffer, the first content including one or more HNA jobs stored in the run stack, and the second content including one or more final match results; and An HNA processing kernel, operatively coupled to the node cache, character class cache, payload buffer, stack top register, run stack, and unified memory, is configured to traverse at least one per-pattern NFA based on multiple payload segments stored in the payload buffer to determine a match of the at least one regular expression pattern. 21. The safety device as claimed in claim 1, wherein: Each supercluster further includes a supercluster graphics memory dedicated to the respective supercluster. The at least one HNA processor further includes an on-chip HNA graphics memory shared by the multiple superclusters; The security device further includes at least one system memory configured to include an external graphics memory (HNA) shared by the multiple superclusters; and The selected given HPU is configured to traverse multiple nodes of at least one per-mode NFA based on multiple segments of a payload of the input stream according to the assigned at least one HNA instruction, wherein the traversed nodes stored in a node cache are proprietary to the selected given HPU, the supercluster graphics memory, the HNA on-chip graphics memory, the HNA off-chip graphics memory, or a combination thereof. 22. The security apparatus of claim 1, wherein the plurality of HPUs of the plurality of clusters of the selected at least one super cluster form an HPU resource pool, the HPU resource pool being available to the HNA scheduler for selection to achieve the matching acceleration. 23. A hyper-nondeterministic finite automaton (HNA) processor specifically for processing nondeterministic finite automata (NFAs), the HNA processor comprising: Multiple superclusters, each supercluster comprising multiple clusters, each of which comprises multiple HNA processing units (HPUs); and An on-chip instruction queue for HNA is configured to store at least one HNA instruction, wherein the plurality of HPUs of at least one selected supercluster in the plurality of superclusters form an HPU resource pool available for allocation of the at least one HNA instruction; and An HNA scheduler is configured to select a given HPU from the formed resource pool and assign at least one HNA instruction to the selected given HPU to initiate a match on at least one regular expression pattern in an input stream received from a network. 24. A method for processing finite automata, comprising: Operabically coupling at least one hyper-nondeterministic finite automaton (HNA) processor to at least one CPU core, the at least one HNA processor being dedicated to nondeterministic finite automaton (NFA) processing; and The at least one HNA processor is configured to include: Multiple super clusters, each super cluster comprising multiple clusters, each of the multiple clusters comprising multiple HNA processing units (HPUs), the at least one CPU core being configured to select at least one super cluster among the multiple super clusters; An on-chip instruction queue for an HNA is configured to store at least one HNA instruction; and An HNA scheduler is configured to select a given HPU from among the plurality of HPUs of the selected at least one supercluster and assign the at least one HNA instruction to the selected given HPU to initiate a match on at least one regular expression pattern in an input stream received from the network. 25. The method of claim 24, wherein each supercluster further includes a supercluster graphics memory dedicated to the respective supercluster, the supercluster graphics memory being accessible to the respective plurality of HPUs of the respective plurality of clusters of the respective supercluster and configured to statically store a subset of nodes of at least one per-mode NFA, the subset of nodes being determined by a compiler of the at least one per-mode NFA. 26. The method of claim 25, wherein: Each supercluster further includes at least one supercluster character class memory dedicated to the corresponding supercluster, and each at least one supercluster character class memory is configured to statically store multiple regular expression pattern character class definitions. 27. The method of claim 26, wherein the supercluster graphics memory and the at least one supercluster character class memory are unified. 28. The method of claim 26, wherein the corresponding plurality of HPUs of the corresponding plurality of clusters of the corresponding supercluster share the at least one supercluster character class memory. 29. The method of claim 24, wherein: Each supercluster further includes at least one supercluster character class memory, each of which is dedicated to a given cluster among a plurality of clusters of a given supercluster and shared by a plurality of HPUs of that given cluster, each of which is configured to statically store a plurality of regular expression pattern character class definitions. 30. The method of claim 24, wherein the at least one CPU core is further configured to select the at least one supercluster from the plurality of superclusters by restricting supercluster selection based on a graphical identifier associated with the at least one HNA instruction. 31. The method of claim 30, wherein the graph identifier is associated with a given per-mode NFA among a plurality of per-mode NFAs, and limiting the supercluster selection includes determining that at least one node of the given per-mode NFA is stored in a supercluster graph memory dedicated to the selected at least one supercluster. 32. The method of claim 30, wherein: This graphical identifier is associated with a given per-mode NFA among a plurality of per-mode NFAs; The HNA scheduler is configured to select the given HPU from a set of HPU restrictions, the set of HPU restrictions including each of the respective plurality of HPUs in each of the respective plurality of clusters in the selected at least one supercluster; and the at least one CPU core is further configured to select the at least one supercluster from the plurality of superclusters based on a determination that at least one node of the given per-mode NFA associated with the graph identifier is stored in a supercluster graph memory dedicated to the selected at least one supercluster. 33. The method of claim 32, wherein the HNA scheduler is further configured to select the given HPU from the HPU limit set based on a single round-robin scheduling of a plurality of HPUs in the HPU limit set. 34. The method of claim 32, wherein the HNA scheduler is further configured to select the given HPU from the HPU limit set based on the instantaneous loading of each HPU in the HPU limit set. 35. The method of claim 24, wherein: Each supercluster further includes a dedicated supercluster graphics memory; and Each supercluster graphics memory is configured to store at least one node of at least one per-mode NFA among a plurality of per-mode NFAs to replicate the at least one node in each supercluster graphics memory of the at least one HNA processor for each supercluster. 36. The method of claim 35, wherein: The at least one CPU core is further configured to provide the HNA scheduler with options to select the at least one supercluster based on the determination that a given per-mode NFA in at least one per-mode NFA associated with the at least one HNA instruction is replicated; and the HNA scheduler is further configured to: The at least one supercluster is selected based on the provided option and (i) a first round-robin scheduling of the plurality of superclusters, (ii) a first instantaneous loading of the plurality of superclusters, or (iii) a combination of (i) and (ii); and The given HPU is selected from the multiple HPUs of the selected at least one super cluster based on a second-cycle scheduling of the multiple HPUs of the multiple clusters of the selected at least one super cluster, an instantaneous loading of the multiple HPUs of the multiple clusters of the selected at least one super cluster, or a combination thereof. 37. The method of claim 24, wherein the at least one HNA processor further includes an HNA on-chip graphics memory accessible to the plurality of HPUs of the plurality of superclusters, the HNA on-chip graphics memory being configured to statically store a subset of nodes of at least one per-mode NFA, the subset of nodes being determined by a compiler of the at least one per-mode NFA. 38. The method of claim 24, wherein the at least one HNA instruction is a first at least one HNA instruction, and the method further comprises: At least one system memory, operatively coupled to the at least one CPU core and the at least one HNA processor, the at least one system memory being configured to include: An external instruction queue for storing at least one second HNA instruction to be transferred to the on-chip instruction queue of the HNA processor; and An HNA chip-external graphics memory is configured to statically store a subset of nodes of at least one per-mode NFA, the subset of nodes being determined by a compiler of the at least one per-mode NFA. 39. The method of claim 38, further comprising: At least one local memory controller (LMC), wherein the at least one LMC is operatively coupled to the at least one HNA processor and the at least one system memory, and a given LMC of the at least one LMC is configured to enable non-coherent access to the at least one system memory so that the at least one HNA processor can access the HNA off-chip graphics memory. 40. The method of claim 38, wherein the at least one system memory is further configured to include an HNA packet data memory configured to continuously store a plurality of payloads, each of the plurality of payloads having a fixed maximum length and associated with a given HNA instruction of either the first at least one HNA instruction stored in the HNA on-chip instruction queue or the second at least one HNA instruction to be transmitted to the HNA on-chip instruction queue. 41. The method of claim 40, further comprising at least one LMC, wherein the at least one system memory is further configured to include: An HNA input stack partition is configured to store at least one HNA input stack, and each at least one HNA input stack is configured to store at least one HNA input job for at least one HPU of at least one of the plurality of HPUs of the plurality of super clusters; An off-chip runtime stack partition is configured to store at least one off-chip runtime stack to extend the storage of at least one on-chip runtime stack, each of the at least one on-chip runtime stacks being configured to store at least one runtime HNA job for the at least one HPU; An external HNA save buffer partition is configured to expand the storage of at least one on-chip save buffer, each of the at least one on-chip save buffers being configured to store at least one runtime HNA operation for the at least one HPU based on the detection of a payload boundary; and An external HNA result buffer partition is configured to store at least one final matching result entry of the at least one regular expression pattern determined by the at least one HPU for matching in the input stream, wherein each of the at least one stored HNA instruction identifies the following: a given HNA input stack of the HNA input stack partition, a given HNA external run stack of the HNA external run stack partition, a given HNA external save buffer of the HNA external save buffer partition, and a given HNA external result buffer of the HNA external result buffer partition. 42. The method of claim 41, further comprising at least one LMC, wherein a given LMC of the at least one LMC is configured to: This enables the at least one HNA processor to access the HNA data packet memory, HNA input stack partition, HNA off-chip instruction queue partition, HNA off-chip execution stack partition, HNA off-chip save buffer partition, and HNA off-chip result buffer partition via a consistent path; and This enables the at least one HNA processor to access the external graphics memory of the HNA chip via a non-uniform path. 43. The method of claim 24, wherein each HPU in the plurality of HPUs of the plurality of superclusters comprises: A node cache is configured to cache one or more nodes from a supercluster graphics memory, an on-chip graphics memory, or an off-chip graphics memory. A character class cache is configured to cache one or more regular expression pattern character class definitions from a supercluster character class store; A payload buffer is configured to store a given payload from an HNA packet data memory, wherein the at least one HNA instruction includes an identifier for a location in the given payload within the HNA packet data memory; A stack top register is configured to store a single HNA operation; A runtime stack is configured to store multiple HNA jobs; A unified memory is configured to store a first content of a save stack and a second content of a match result buffer, the first content including one or more HNA jobs stored in the run stack, and the second content including one or more final match results; and An HNA processing kernel, operatively coupled to the node cache, character class cache, payload buffer, stack top register, run stack, and unified memory, is configured to traverse at least one per-pattern NFA based on multiple payload segments stored in the payload buffer to determine a match of the at least one regular expression pattern. 44. The method of claim 24, wherein: Each supercluster further includes a supercluster graphics memory dedicated to the respective supercluster. The at least one HNA processor further includes an on-chip HNA graphics memory shared by the multiple superclusters; The method further includes at least one system memory configured to include an external graphics memory shared by the plurality of superclusters; and The selected given HPU is configured to traverse multiple nodes of at least one per-mode NFA based on multiple segments of a payload of the input stream according to the assigned at least one HNA instruction, wherein the traversed nodes stored in a node cache are proprietary to the selected given HPU, the supercluster graphics memory, the HNA on-chip graphics memory, the HNA off-chip graphics memory, or a combination thereof. 45. The method of claim 24, wherein the plurality of HPUs of the plurality of super clusters form an HPU resource pool, the HPU resource pool being available to the HNA scheduler for selection to achieve the matching acceleration.