HK1214695B - Compilation of finite automata based on memory hierarchy - Google Patents

Description

Compilation of Finite Automata Based on Memory Hierarchy

Technical Field

Embodiments of the present invention relate to compilation of memory-hierarchy based 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 network protocol layers from L3 to L7, 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 through L4-L7 network protocol layers with both access-based 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 these computationally intensive tasks, they lack the performance to process data at line speed.

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

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 a compact method for describing patterns in strings. The simplest pattern matched by a regular expression is a single character or string, such as /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 infinite 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", the next two characters, then the string "abc" and followed by the string "xyz" after the infinite number of characters. Content searches are usually performed using a search algorithm (such as a deterministic finite automaton (DFA) or a non-deterministic finite automaton (NFA) for processing regular expressions).

Overview

Embodiments of the present invention provide a method, apparatus, computer program product, and corresponding system for compilation and runtime processing of finite automata.

According to one embodiment, in at least one processor in a security device operatively coupled to a network, a method may include generating at least one per-pattern nondeterministic finite automaton (NFA). The at least one processor may be operatively coupled to a plurality of memories, the plurality of memories being mapped into a plurality of levels in a memory hierarchy. Each per-pattern NFA may be generated for a single regular expression pattern and may include a set of corresponding nodes. The method may distribute the nodes of the set of corresponding nodes of each per-pattern NFA for storage across the plurality of memories based on the mapped levels and per-pattern NFA storage allocation settings configured for the levels.

The method may include statically storing the nodes of the set of corresponding nodes of each generated per-pattern NFA in the plurality of memories based on the distribution.

Generating the at least one per-pattern NFA may include specifying a transition from a given node to a next node via a next node address associated with the given node and configuring the next node address to identify the next node and a given one of the plurality of memories allocated to the next node for storage.

The method may include configuring each of the per-pattern NFA storage allocation settings for a corresponding one of the hierarchies to represent a target number of unique nodes of the corresponding set of nodes of each per-pattern NFA generated to be distributed for storage in a given memory of the plurality of memories mapped to the corresponding hierarchical level.

The only nodes in the set of corresponding nodes may be arranged in a sequential manner within a given one of the at least one per-pattern NFAs that includes the set of corresponding nodes.

The method may include configuring each per-pattern NFA storage allocation setting for the corresponding level in a manner such that, in the event of generating a per-pattern NFA for each regular expression pattern in a set of regular expression patterns, the given memory is able to provide sufficient storage capacity for storing the target number of unique nodes represented by each generated per-pattern NFA.

The method may include representing the target number of unique nodes via an absolute value. The absolute value may be a common value for each group of corresponding nodes, such that each group of corresponding nodes can have a same value for the target number of unique nodes for storage in the given memory mapped to the corresponding level.

The method may include representing the target number of unique nodes via a percentage value that is applied to the corresponding total number of nodes for each group of corresponding nodes, thereby enabling each group of corresponding nodes to have a separate value for the target number of unique nodes to be stored in the given memory mapped to the corresponding level.

Each memory in the plurality of memories may be mapped to a corresponding one of the tiers in descending order based on the performance ranking of the plurality of memories. A memory with the highest performance ranking in the plurality of memories may be mapped to a highest-ranked one of the tiers.

The per-pattern NFA storage allocation settings may include a first per-pattern NFA storage allocation setting and a second per-pattern NFA storage allocation setting. The tiers may include a highest-ranked tier and a second-highest-ranked tier. The first per-pattern NFA storage allocation setting may be configured for the highest-ranked tier. The second per-pattern NFA storage allocation setting may be configured for the second-highest-ranked tier.

Distributing the nodes of the set of corresponding nodes of each per-graph NFA generated may include distributing them in a continuous manner, the distribution including a first distribution of the nodes of the set of corresponding nodes for storage in a first memory of the plurality of memories. The first memory may be mapped to a highest-ranked level of the hierarchy. The distribution may include a second distribution of the nodes of the set of corresponding nodes based on at least one undistributed node remaining in the set of corresponding nodes. 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 of the hierarchy, the given level being successively lower than the highest-ranked level for each distribution of the nodes of the set of corresponding nodes.

A given one of the at least one second distribution may include all remaining undistributed nodes in the set of corresponding nodes if the given level is the lowest-ranked level among the levels.

The method may include maximizing the number of nodes in the first distribution, and the maximized number may be limited by one of the per-pattern NFA storage allocation settings being configured as a corresponding per-pattern NFA storage allocation setting for the highest-ranked level.

The method may include maximizing the number of nodes in each at least one second distribution, and the maximized number may be limited for each distribution by one of the per-pattern NFA storage allocation settings configured as a corresponding per-pattern NFA storage allocation setting for the given level.

The method may include statically storing the nodes of the set of corresponding nodes of each per-pattern NFA, such that the nodes of each set of corresponding nodes can be walked using multiple segments of multiple payloads in an input stream received from the network to determine a match of at least one regular expression pattern in the input stream.

The walking may be performed based on individual nodes of the set of corresponding nodes matching the segments of the payloads.

The method may further include determining the per-pattern NFA storage allocation settings based on a total number of regular expression patterns in a set of regular expression patterns and a desired performance metric associated with the walk.

The method may include generating a unified deterministic finite automaton (DFA) based on at least one sub-pattern of each pattern selected from a set of regular expression patterns and storing the unified DFA in a given memory of the plurality of memories.

The multiple memories may include a first memory, a second memory, and a third memory, and the first and second memories may be co-located on a chip with the at least one processor, while the third memory may be an external memory located outside the chip and mapped to a lowest-ordered level among the levels.

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

Additionally, yet another example embodiment may include a non-transitory computer-readable medium having stored thereon a sequence 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 exemplary embodiments of the invention, as illustrated in the accompanying drawings, in which like reference characters refer to like parts throughout the different views. The drawings are not necessarily to scale, emphasis instead being placed upon illustrating embodiments of the invention.

FIG1 is a block diagram of one embodiment of a security device in which embodiments disclosed herein may be implemented.

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

3A is another block diagram of one 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 in a security device operatively coupled to a network.

4 is a block diagram of an example embodiment of an environment for a Hyper Nondeterministic Automaton (HNA) coprocessor.

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

5B is a table of an example embodiment of a processing cycle for walking the NFA graph of FIG. 5A with a payload.

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

FIG7 is a block diagram of an example embodiment of an environment for the compiler.

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

9 is a flow diagram of an example embodiment of a method that may be performed in at least one processor operatively coupled to a plurality of memories mapped to a plurality of levels in a memory hierarchy in a security device operatively coupled to a network.

10 is a block diagram of an example embodiment of another node distribution for 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 block diagram of an example internal structure of a computer optionally included within embodiments disclosed herein.

DETAILED DESCRIPTION

Before describing in detail example embodiments of the present invention, an example security application is described directly below to help the reader understand the features of the present invention disclosed herein, in which these embodiments can be implemented and in which typical processing uses deterministic finite automata (DFA) and non-deterministic finite automata (NFA) to help the reader understand the features of the present invention disclosed herein.

FIG1 is a block diagram of an embodiment of a security appliance 102 in which embodiments disclosed herein may be implemented. Security appliance 102 may include a network services processor 100. Security appliance 102 may be a standalone system that switches packets received on one network interface 103a to another network interface 103b and performs various security functions on the received packets before forwarding them. For example, security appliance 102 may be configured to perform security processing on packets 101a received on a wide area network (WAN) 105a or any other suitable network, and then forward the processed packets 101b to a local area network (LAN) 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 OSI reference model defines seven network protocol layers (L1-7). 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 (packet processing operations) for higher-level network protocols (e.g., L4-L7) and enable higher-level network protocol processing within received packets to be executed, thereby forwarding the packets at line speed. By processing these protocols to forward the packets at line speed, the network services processor 100 does not degrade the network data transfer rate. The network services processor 100 can receive packets from network interfaces 103a or 103b, which can be physical hardware interfaces, and can perform L2-L7 network protocol processing on the received packets. The network services processor 100 can subsequently forward the processed packets 101b via network interfaces 103a or 103b to another hop in the network, to 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 layer security (IPSec) and/or secure sockets layer (SSL), intrusion detection systems (IDS), antivirus (AV), or any other suitable network protocols.

The network services processor 100 can use multiple processors (i.e., cores) to provide high application performance. Each core (not shown) can be dedicated to performing data plane operations, control plane operations, or a combination thereof. Data plane operations can include packet operations for forwarding packets. Control plane operations can include processing complex high-level protocol portions, such as IP Security (IPSec), Transmission Control Protocol (TCP), Secure Sockets Layer (SSL), or any other suitable high-level protocol. Data plane operations can include processing other portions of these complex high-level protocols.

The network services processor 100 may also include special purpose coprocessors that can offload cores to achieve high throughput for the network services processor 100. For example, the network services processor 100 may include an acceleration unit 106, which may include a hyper nondeterministic automaton (HNA) coprocessor 108 for hardware-accelerated NFA processing and a hyper finite automaton (HFA) coprocessor 110 for hardware-accelerated DFA processing. The HNA 108 and HFA 110 coprocessors may be configured to offload the heavy burden of executing computationally and memory-intensive pattern matching methods from a general-purpose core (not shown) of the network services processor 100.

The network services processor 100 can perform pattern searching, regular expression processing, content validation, transformation, and security acceleration packet processing. Regular expression processing and pattern searching can be used to perform string matching for AV and IDS applications and other applications that require string matching. A memory controller (not shown) in the network services processor 100 can control access to a memory 104 that is 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 for querying and pattern matching in DFA and NFA graph expression searches. The compiled rule data can be stored as a binary image 112 that 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.

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, that is, each computation model consists of a set of states, a starting state, an input alphabet (the set of all possible symbols), and a transition function. The computation begins in the starting state and changes to a new state depending on the transition function.

The pattern is usually expressed using a regular expression, which includes basic elements, such as normal text characters such as A-Z and 0-9, and metacharacters such as *, ^, and |. The basic element of a regular expression is the symbol (single character) to be matched. The basic elements can be combined with metacharacters that allow concatenation, alternation (|), and the Kleinian star (*). The metacharacters for concatenation can be used to create multiple character matching patterns from a single character (or multiple substrings), while the metacharacters for alternation (|) can be used to create a regular expression that can match any of two or more substrings. The metacharacter Kleinian star (*) allows a pattern to be matched any number of times, including without the preceding character or string.

Combining different operators with multiple single characters allows for the construction of complex expression subpatterns. For example, a subpattern like (th(is|at)*) can match multiple strings, such as th, this, that, thisis, thisat, thatis, or thatat. Another example of a complex subpattern of an expression is a subpattern constructed [...] in conjunction with a character class that allows for a list of characters to be searched for. For example, gr[ea]y finds both grey and gray. Other examples of complex subpatterns are those that use dashes to indicate character ranges, such as [A-Z] or the metacharacter ".", which matches any character. An element of a pattern can be a primitive element or a combination of one or more primitive elements with one or more metacharacters.

The input to a DFA or NFA state machine typically includes multiple segments, such as a string of (8-bit) bytes, that is, an alphabet can be a single byte (a character or symbol) from an input stream (i.e., a received data packet). Each segment (e.g., byte) in the input stream can cause a transition from one state to another. These 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 node in the graph.

Using a DFA to process a regular expression and find one or more patterns described by the regular expression in a character input stream can be characterized as having deterministic runtime performance. The next state of the DFA can be determined from an input character (or symbol) and the current state of the DFA, because each DFA state has only one state transition. Thus, the runtime performance of the DFA is called deterministic, and its behavior can be fully predicted from the input. However, the trade-off of determinism is a graph in which the number of nodes (or graph size) may grow exponentially with the size of the pattern.

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

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

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

The compiler can compile a pattern or a list of pattern inputs (also called 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, i.e., an action for identifying the presence of a pattern in an input stream or matching the pattern with the content in the input stream. The content can be a 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 using 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 herein. A processor configured to implement runtime processing of a payload using the generated DFA, NFA, or a combination thereof can be referred to as a walker herein. 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 the security device 102 of FIG1 , in which embodiments disclosed herein may be implemented. As disclosed with reference to FIG1 , 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, which 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 utilizes the binary image 112. For example, the compiler 306 may generate the binary image 112 including compiled rule data used by the walker 320 to perform a pattern matching method on a received data packet 101a (shown in FIG1 ). According to embodiments disclosed herein, the compiler 306 may generate the binary image 112 by determining compiled rule data for a DFA, NFA, or a combination thereof based on at least one heuristic method, as further described below. The compiler 306 may determine rule data that is advantageously suitable for both a DFA and an NFA.

According to embodiments described herein, compiler 306 may generate binary image 112 by processing a rule set 310, which may include a set of one or more regular expression patterns 304 and optional qualifiers 308. From rule set 310, compiler 306 may generate a unified DFA 312 using subpatterns selected from all of the one or more regular expression patterns and at least one NFA 314 for at least one of the 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 transitioning walker 320 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 in any other suitable form, and the mapping in the metadata can be represented as one or more tables or in any other suitable form, respectively. According to the embodiments disclosed herein, if a sub-pattern selected from a pattern is the pattern, no NFA is generated for the pattern. According to the embodiments disclosed herein, each generated NFA can be used for a specific pattern in the group, and a unified DFA can be generated based on all sub-patterns from all patterns in the group.

The walker 320 walks the unified DFA 312 and the at least one NFA 314 with the payload based on consuming (i.e., processing) segments (e.g., bytes) of the payload from the received data packet 101a by transforming the states of the unified DFA 312 and the at least one NFA. Thus, 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 of one or more regular expression patterns 304 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 signatures/patterns used to identify viruses/attacks or applications have become more complex. For example, signature databases have evolved from having simple string patterns to having regular expression (regex) patterns with wildcards, ranges, character classes, and advanced PCRE signatures.

As shown in FIG3A , optional qualifiers 308 can each be associated with a pattern in the set of regular expression patterns 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 signature options, or other options suitable for processing the pattern associated with the qualifiers. For example, qualifier 322 can indicate whether a starting offset (i.e., the position in the payload of the first matching character of a pattern that matches in the payload) option for the advanced PCRE signature option is desired for pattern 316.

According to embodiments disclosed herein, compiler 306 can generate a unified DFA 312 using subpatterns 302 selected from all patterns in the set of one or more regular expression patterns 304. Compiler 306 can select subpatterns 302 from each pattern in the set of one or more regular expression patterns 304 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, wherein a portion (not shown) of at least one pattern 316 is used to generate the at least one NFA 314, and at least one walk direction for runtime processing (i.e., walking) of the at least one NFA 314 can be determined based on whether the length of the selected subpattern 318 is fixed or variable and the position of the selected subpattern 318 in the at least one pattern 316. Compiler 306 can store the unified DFA 312 and the at least one NFA 314 in the at least one memory 104.

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

According to embodiments disclosed herein, subpattern selection can be based on at least one heuristic. A subpattern is a set of one or more consecutive elements from a pattern, wherein each element from the pattern can be represented by a node in a DFA or NFA graph for the purpose of matching bytes or characters from the payload. As described above, an element can be a single text character represented by a node, or a character class represented by a node. Based on whether a subpattern is likely to cause excessive DFA graph explosion, as described above with reference to Figures 2A-2G, compiler 306 can determine which subpattern in the pattern is better suited for an NFA. For example, generating a DFA from a subpattern that includes consecutive text characters will not cause the DFA graph to explode, while a complex subpattern as described above may include operators and characters and therefore may cause the DFA graph to explode. For example, a subpattern that includes multiple repeated wildcards or larger character classes (e.g., [^\n]* or [^\n]{16}) may result in too many states in the DFA and therefore may be more advantageously suited for an NFA. Thus, compiler 306 may be referred to herein as a "smart compiler."

As disclosed above, selecting a subpattern from each pattern in the set of one or more regular expressions 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 the DFA graph to explode. However, if the subpattern "cdef" has already been selected for another pattern, the compiler can select an alternative subpattern of the pattern "ab.*cdef.*mn." Alternatively, the compiler can replace the subpattern "cdef" with another subpattern for the other pattern, so that the subpattern "cdef" can be selected for the pattern "ab.*cdef.*mn."

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

By maximizing the subpattern length, false positives in NFA processing can be avoided. False positives in NFA processing can result in non-deterministic runtime processing and, therefore, can degrade runtime performance. Additionally, by maximizing the number of unique subpatterns selected, compiler 306 enables a 1:1 conversion of the at least one NFA 314 generated from a subpattern in the unified DFA with a subpattern from the pattern in the unified DFA.

For example, if the selected subpattern is shared by multiple patterns, then a 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 subpattern matches from the unified DFA represent partial matches for each of the multiple patterns. Thus, maximizing the number of unique subpatterns reduces the number of DFA:NFA transitions to 1:N, thereby reducing runtime processing by the walker 320.

To maximize the number of unique subpatterns, compiler 302 may calculate a hash value 326 for selected subpattern 318 and store the calculated hash value 326 in association with an identifier (not shown) of a pattern 316 from which subpattern 318 was selected. For example, compiler 306 may calculate a hash value for each pattern in group 304 for the selected subpattern. The calculated hash values 324 may be stored in the at least one memory 104 as 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 selected subpatterns of other patterns in the group to determine whether the selected subpattern is unique.

If the calculated hash value exists in the list, the compiler can determine whether to (i) replace the sub-pattern with another sub-pattern from the pattern or (ii) replace the sub-pattern selected for the other pattern in the group with an alternative sub-pattern selected from another pattern in the group. The other pattern in the group can be identified based on its 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 sub-patterns considered for replacement so as to maximize the length of the unique sub-pattern being selected as described above. Replacing a selected sub-pattern can include selecting the next longest sub-pattern or the next highest priority sub-pattern identified for a given pattern. For example, potential sub-patterns can be prioritized based on the likelihood of causing a DFA graph explosion or the strength of the expected DFA graph explosion.

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

The at least one heuristic may include accessing a subpattern knowledge base (not shown) associated with historical frequencies of usage indicators, and ignoring a given subpattern from each pattern 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, application- or protocol-specific subpatterns may have a high frequency of usage, such as for Hypertext Transfer Protocol (HTTP) payloads, "carriage return line feeds," or clear traffic such as multiple consecutive zeros from a binary file, or any other frequently used subpattern.

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

The at least one heuristic method can include setting a priority for a given sub-pattern of each of the given sub-patterns based on the sub-pattern type of each of the given sub-patterns and the length of the given sub-patterns. The sub-pattern type can be plain text, alternating, single character repeat, or multiple character repeat, and the order of priority for the sub-pattern type from highest to lowest can be plain text, alternating, single character repeat, and multiple character repeat. Thus, sub-patterns that are text strings having a length of at least a minimum length threshold can be given a higher priority than complex sub-patterns of variable length.

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

If none of the given subpatterns are unique and have a length of at least the minimum length threshold, the compiler 306 can select a non-unique subpattern as the selected subpattern based on the priority setting. Thus, the compiler 306 can select a subpattern from a pattern that is a copy of a subpattern selected from another pattern, rather than selecting a subpattern with a length less than the minimum threshold. To assist in completing subpatterns, the compiler 306 can perform multiple ignores on these patterns and sort possible subpatterns by length. Thus, the compiler's subpattern selection for a given pattern in the set of one or more regular expressions 304 can be performed within the context of subpattern selections for other patterns in the set of one or more regular expressions 304.

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

According to embodiments disclosed herein, if a payload in a received packet 101 includes content that matches a selected sub-pattern 318 from pattern 316, the walker can transition to walking at least one NFA of pattern 318. Walker 320 can report the match of the selected sub-pattern 318 along with an offset identifying the position of the last character of the matching sub-pattern in the received packet as the end offset of the sub-pattern in the payload. A sub-pattern match can be a partial match of the pattern if the sub-pattern is a subset of the pattern. Walker 320 can then continue searching the payload for the remainder of the pattern by walking at least one NFA of the pattern to determine a final match for the pattern. It should be understood that the pattern can traverse one or more payloads in the received 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 in a security device operatively coupled to a network. The method can begin (352) and select a subpattern from each of the 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, a portion of the at least one pattern being used to generate the at least one NFA, and at least one walk direction for runtime processing of the at least one NFA can be determined based on whether the length of the selected subpattern is fixed or variable and the position of the selected subpattern in the at least one pattern (358). The method can store the unified DFA and the at least one NFA in the at least one memory (360). In the example embodiment, the method then ends (362).

As described above, the compiler 306 can generate the unified DFA 312 and the at least one NFA 314 to enable the walker 320 to search for a match to one or more regular expression patterns 304 in the received data packet 101a. The compiler 306 can select a sub-pattern from each of the set of one or more regular expression patterns 304 based on at least one heuristic. The unified DFA 312 can be generated using these sub-patterns 302 selected from all patterns in the set 304. The compiler 306 can generate at least one NFA 314 for at least one pattern 316 in the set 304. The compiler 306 can then be configured to compile the rule set 310 into a binary image 112 that identifies portions of the rule set 310 that are likely best suited for DFA or NFA processing. Thus, binary image 112 may include at least two sections, wherein a first section is used for DFA processing and a second section is used for NFA processing, such as a unified DFA 312 and the at least one NFA 314. As disclosed above, binary image 112 may include compilation rule data for both DFA and NFA, or may be multiple binary images that separate DFA compilation rule data from NFA compilation rule data. For example, NFA compilation rules may be separated from DFA compilation rules and stored in a graphics memory operatively coupled to HNA 108. Memory 104 may be a graphics memory, which may be a plurality of memories, such as graphics memory 456 disclosed below with respect to FIG. 4.

Figure 4 is a block diagram 450 of an example embodiment of an environment for HNA 108 of Figure 1. According to embodiments disclosed herein, HFA 110 may be configured to implement the functionality of walker 320 with respect to DFA processing, and HNA 108 may be configured to implement the functionality of walker 320 with respect to NFA processing.

According to embodiments disclosed herein, the HNA 108 can be configured to read at least one instruction 453 from an instruction queue 454. The instruction queue 454 can be configured to store the at least one instruction 453, which can be sent by a host (not shown) for processing by the HNA 108. The at least one instruction 453 can include at least one task, such as S1 459a, S2 459b, or S3 459c. Each of the at least one tasks can be determined based on a partial match result identified by the HFA coprocessor 110 of FIG. 1 for a given sub-pattern of the sub-patterns 302 of FIG. 3A (being matched in the input stream).

A given job in the at least one 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 of the at least one walking direction corresponding to one of the at least one given nodes. Each of the at least one job may include a result processed by the HFA, thereby enabling the HNA to advance a match corresponding to a given subpattern in a given NFA for a given pattern in the at least one pattern 304. Thus, each job represents a partial match result determined by the HFA coprocessor 110 to advance the match for the given pattern by the HNA coprocessor 108.

The HNA 108 may process the at least one instruction 453 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. The at least one instruction 453 may also include a payload pointer (not shown) pointing to a payload 462, a result buffer pointer (not shown) pointing to a match result buffer 466, a save buffer pointer (not shown) pointing to a save buffer 464, and a run stack pointer (not shown) pointing to a run stack 460.

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

The at least one work of the at least one instruction 453, such as S1 459a, S2 459b, or S3 459c, can be stored in an input stack 458 for processing by the HNA 108. The at least one work of the at least one instruction can each belong to a same given payload, such as payload 462, that is processed by the HFA 110.

The HNA 108 can be configured to load (i.e., extract or retrieve) at least one job, such as job S1 459a, S2 459b, or S3 459c, from the input buffer 458 based on the input buffer pointer. The HNA 108 can push (i.e., store) the at least one job to the run stack 460. The HNA 108 can pop (i.e., read, extract, load, etc.) a given job, such as entry S1 459a, S2 459b, or S3 459c, from the run stack and process the given job. Each of the at least one job (e.g., S1 459a, S2 459b, or S3 459c) can include a payload offset (not shown) to a section (not shown) of the payload 462 and a pointer to a graph 457, which can be a given finite automaton in at least one finite automaton, such as the at least one NFA 314 of FIG. 3A .

HNA 108 can load (i.e., extract) graph 457 from graph memory 456, which can be included in binary image 112 of Figures 1 and 3A, and begin processing graph 457 using a payload segment corresponding to a corresponding payload offset of payload 462. Graph memory 456 can be a plurality of memories. Graph memory 456 can be operatively coupled to HFA 110 and HNA 108. HNA 108 can process graph 457 by walking the nodes of graph 457 with the payload segment. A partially matched path of graph 457 can include at least two nodes of graph 457 that match consecutive segments of the payload with a given pattern used to generate graph 457. A partially matched path can be referred to as a thread or active thread herein.

HNA 108 can process graph 457 using the payload section from payload 462, pushing entries onto/popping out of run stack 460 to maintain and restore its position in graph 457. For example, if a walked node presents multiple options for the next node to be walked, HNA 108 may need to maintain its position in the graph. For example, HNA 108 can walk a node that presents multiple processing path options, such as a fork shown in the graph. According to the embodiments disclosed herein, nodes of a DFA or NFA are associated with a node type. Nodes associated with a separation type can present multiple processing path options. Separation types are further disclosed below with reference to FIG5A.

According to embodiments disclosed herein, HNA 108 can be configured to select a given path from the multiple processing paths and push an entry onto run stack 460. This run stack can allow HNA 108 to return and proceed along an unselected path from the multiple processing paths based on a mismatch (i.e., a negative result) at a node walked along the selected path. Thus, pushing an entry onto run stack 460 can save a location in graph 457 representing an unexplored context. The unexplored context can indicate a given node in graph 457 and a corresponding payload offset, enabling HNA 108 to return to the given node and walk the given node using a given segment of payload 462, as the given segment may be located at a corresponding payload offset in payload 462. Thus, run stack 460 can be used to allow engine 462 to remember and later walk an unexplored path in graph 457. Pushing or storing an entry indicating a given node and a corresponding offset in a given payload may be referred to herein as storing an unexplored context, thread, or inactive thread. Popping, extracting, or loading an entry indicating the given node and the corresponding offset in the given payload so as to walk the given node using a segment located at the corresponding offset in the given payload may be referred to herein as activating a thread. Discarding an entry indicating the given node and the corresponding offset in the given payload may be referred to herein as clearing an entry or deactivating a thread.

In the event that the end of payload 462 is reached while walking a segment of payload 462 using graph 457, run stack 460 can allow HNA 108 to save its position in graph 457. For example, HNA 108 can determine that the payload or a portion of payload 462 partially matches a given pattern and that a current payload offset of payload 462 is an end offset of payload 462. Thus, HNA 108 can determine that only a partial match of the given pattern was found and that the entire payload 462 has been processed. HNA 108 can then save the contents of run stack 460 to save buffer 464 to continue walking with the next payload corresponding to the same stream as processed payload 462. Save buffer 464 can be configured to store at least one run stack entry of run stack 460 in the event that the entire payload 462 has been processed, mirroring an operational state of run stack 460.

Upon finding a final (i.e., complete or full) match for the pattern, the HNA 108 may pop and discard the entry associated with the current job in the run stack 460, such as the job loaded from the input buffer, such as S1 459a, and save the match results (not shown) to the match result buffer 466. Alternatively, the HNA 108 may continue processing the entries associated with the current job in the run stack 460, as all possible matching paths may be meaningful.

Matching result can comprise the node address that is associated with the node of the final matching place of determining this pattern.The node of the final matching place of determining this pattern can be referred to as mark node at this.Node address or other identifier of a final matching position in graph 457, the identifier of matching pattern, the length of matching pattern, or any other suitable matching result or its combination can be included in these matching results.

Upon processing all run stack entries associated with the current job, the HNA 108 may load the next job from the run stack, which was previously loaded from the input buffer 458 (e.g., S2 459b), because the HNA 108 may be configured to sequentially process the jobs of instruction 453. The HNA 108 may then fetch the next graphic (not shown) from the graphic memory 456, walk the next graphic using one or more payload segments from the payload 462, and continue processing additional jobs until the run stack 460 is empty.

Upon finding a mismatch in payload 462 while walking graph 457 with payload 462, HNA 108 may pop an entry associated with the current job (e.g., S1 459a) from run stack 460 and walk the next node using the next segment of payload 462 based on the contents of the popped entry. If run stack 460 does not include an entry associated with the current job, HNA 108 may end the current job and load the next job (e.g., S2 459b) previously loaded from input buffer 458 from run stack 460. HNA 108 may then be configured to walk the next graph based on the loaded next job and continue processing additional jobs until run stack 460 is empty.

5A is a block diagram 500 of an example embodiment of a per-pattern NFA graph 504 that may be used by a walker 320 to match regular expression patterns 502 in an input stream (not shown). As described above, HNA 108 may be configured to implement the functionality of walker 320 with respect to NFA processing.

In this example embodiment, the input stream may include a data packet (not shown) with a payload 542. Regular expression pattern 502 is a pattern "h[^\n]*ab," which specifies that the character "h" is followed by an infinite number of consecutive characters that do not match a newline character (i.e., [^\n]*). The infinite number may be zero or more. Pattern 502 further includes the characters "a" and "b" followed consecutively by an infinite number of characters that do not match a newline character. In this example embodiment, payload 542 includes segments 552a-d (i.e., h, x, a, and b), which have offsets 520a-d (i.e., 0, 1, 2, and 3), respectively, within 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. Furthermore, it should be understood that NFA graph 504 can be a subregion 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 location of the larger payload, resulting in a different offset than in the example embodiment.

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

According to embodiments disclosed herein, the walker 320 can walk segments 522a-d of the payload 542 through the NFA graph 504 one segment at a time to match the regular expression 502 against the input stream. A given segment of the segments 516 used to walk a given node can be determined based on whether its corresponding offset in the offset 518 is a current offset within the payload 542. According to embodiments disclosed herein, the walker 320 can update the current offset by increasing or decreasing 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 increasing or decreasing the current offset, respectively.

Nodes N0 506, N2 510, N3 512, and N4 514 can be configured to match a corresponding element to a given segment of payload 542, while nodes N1 508 and N5 515 can be nodes of a node type that do not indicate matching functionality and therefore are not processed from payload 542. In this example embodiment, node N1 508 is a split node that presents multiple transition 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 implicit assumptions made by walker 306. For example, compiler 306 can generate NFA graph 504 based on an implicit understanding that walker 320 follows a deterministic path, such as implicitly understanding that walker 320 selects an upper ε-path 530a based on walking split node 508. According to embodiments disclosed herein, upper epsilon path 530a may be selected as upper epsilon path 530a representing a lazy path. A lazy path may be a path representing the shortest possible match for an element.

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

The implicit understanding can include configuring the walker 320 to select a given next node from a plurality of next nodes based on node metadata included in a particular entry position within the split node metadata. The compiler 306 can be configured to generate the split node metadata including an indication that the given next node is at the specified entry position. Thus, the compiler 306 can generate the NFA graph 504 using the implicit understanding that a given path, such as the ε path 530a above, will be selected by the walker 320 at the split node N1 508.

Figure 5B is a table 538 of an example embodiment of a processing cycle for walking the NFA graph of Figure 5A with a 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 a current node 530 at a current offset 532 with a segment from payload 542 to determine a match result 534 and determining a walk action 536 based on the match result 534. In this example embodiment, node N0 506 can have a character node type. For example, node NO 506 can be a character node that is configured to match the character "h" in the input stream. In this example embodiment, the walker 320 can walk the starting node N0 506 at the current offset 520a with segment 522a (i.e., "h") in processing cycle 540a.

When segment 522a matches the character "h" at node N0 506, the walker 320 can determine that the match result 534 is a positive match result. As specified by the compiler 306 via 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 increase the current offset from 520a (i.e., "0") to 520b (i.e., "1"). The next node indicated by node N0 506 is the separation node N1 508 in this example embodiment. The walker 320 then takes action 536 of processing cycle 540a, which includes updating the current offset in the payload 542 to "1" and switching to the separation node N1 508. The conversion can include extracting (also referred to herein as loading) the separation node N1 508.

Because split node N1 508 presents multiple conversion path options, such as epsilon paths 530a and 530b, action 536 of processing cycle 540b may include selecting upper epsilon path 530a and extracting node N2 510, which is not associated with payload 542, without consuming (i.e., processing) from payload 542. Because the matching function is not performed by split node N1 508, current offset/segment 532 is unchanged, and thus the payload is not consumed (i.e., processed) for processing cycle 540b.

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

Storing the unexplored context can enable the walker 320 to remember to return to node N3 512 to walk node N3 512 with segment "1" at offset 520b in the payload 542 in the event that a negative match result occurs along the selected partial match path, for example, if the negative match result is determined at node N2 510 or at a node along a path extending from node N2 510. According to embodiments disclosed herein, the unexplored context can be marked with a discard unexplored process (DUP) indicator that indicates whether the walker 320 discards or processes the unexplored context in the event that a final match for the graph 502 is identified along the selected transition path.

For example, upon reaching marked node N5 515 indicating a final (i.e., complete or full) match for pattern 502 in the input stream, the walker 320 may employ the DUP indicator to determine whether to process the unexplored context by walking node N3 512 at offset 520 b with segment “x” in an effort 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 a DUP indicator may 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 desired processing of the stack entry, or to false to indicate desired discarding of the stack entry.

Whether a storage thread is traversed can be determined by the compiler 306. For example, the compiler 306 can control whether to configure a setting corresponding to the metadata of each node to set the DUP indicator. Alternatively, the compiler 306 can configure a global setting included in the global metadata associated with the finite automaton to specify that all storage threads need to be traversed, so that all possible matches can be identified.

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

Storing the untraversed transition path may include pushing an entry into a stack (such as the run stack 460 of FIG. 4 ) 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 may be a value, a pointer, or any other suitable indicator of the next node. The value of the offset may be a value, a pointer, or any other suitable value that identifies the location of the segment 516 in the payload 542.

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

Walker 320 can switch and walk node N3 512 and use segment "x" located at offset 520b in payload 542. Thus, processing cycle 540d shows that match result 534 is positive for processing cycle 540d. Action 536 of processing cycle 540d can include updating the current offset to offset 520c and switching back to split node N1 508, which can be the next node indicated by node N3 512.

Because all arc transitions from split node 508 are ε-transitions, walker 320 can again select one of the multiple path options and not consume (i.e., process) a segment from payload 542, since the current offset has not been updated for processing cycle 540e. In the example embodiment, walker 320 again selects ε-transition path 530a. Walker 320 then stores a thread again by pushing node N3 512 and the current offset, now 520c (i.e., "2"), onto run stack 460. As shown for processing cycle 540f, 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. Because "a" matches at node N2 510, the walker 320 updates the current offset to 520d (i.e., "3") and transitions to node N4 514, which is specified by the node N2 510 metadata (not shown) as configured by the compiler 306. For example, the N2 510 metadata may specify a transition 511 from a given node, such as node N2 510, to a next node, such as 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 the next node and the compiler 306 may distribute the next node to a given memory in the plurality of memories 456 for storage.

Thus, for processing cycle 540g, the walker 320 can extract the next node N4 514 and the next segment 522d (i.e., "b") at offset 520d. Because "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 that indicates a final (i.e., complete or complete) match with the regular expression pattern 542 in the input stream. Thus, for processing cycle 540h, the walker 320 can discontinue walking along the current path and report the final match by storing an entry in the match result buffer 466. The walker 320 can then examine the run stack 460 for stored threads and either discard the stored threads or activate them as indicated by the corresponding DUP indicators. The walker 320 then pops the entry identifying node N3 512 and offset 520 (i.e., "2") and determines, based on the DUP indicator associated with the popped entry, whether to activate the stored thread by walking node N3 512 with segment 522c at offset 520c or to discard the stored thread.

The embodiments disclosed herein can achieve optimized matching performance due to the combined DFA and NFA type processing disclosed above. For example, the embodiments disclosed above can reduce the number of false positives in NFA processing because NFA processing can be based on partial matches identified via DFA processing. Additionally, because the embodiments disclosed herein include per-rule (i.e., per-pattern) NFAs, which can be identified via DFA processing, the embodiments disclosed herein further optimize matching performance.

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

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 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 processor core of a security device 102, as disclosed above with reference to FIG1 . The security device may be configured to execute higher-level protocols for processing packet 101a and may be configured to offload the pattern matching method to the HFA 110 and HNA 108.

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

The HNA 108 can determine that the partial match results 618 c, 618 b, and 618 a form a final (i.e., complete) match for a given regular expression pattern 304 in the input stream. For example, by forwarding 606 the HFA partial match results from the HFA 110 to the HNA 108, either indirectly via the processing core 603 or directly from the HFA 110, each partially matched packet passing through the HFA 110 can enable the HNA 108 to advance the partial match because the walker 320 can use the “hint” or start information from the HFA 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. 4 , input stack 458 may include at least one task, such as S1 459a, S2 459b, or S3 459c in the at least one instruction 453, for processing by HNA 108. The at least one task of the at least one instruction may each belong to the same given payload, such as payload 462, processed by HFA 110. Such "hints" or starting information, which may be based on packets "pre-screened" by HFA 110, may include NFA start nodes and corresponding payload segment offsets for walking a per-pattern NFA, as disclosed above. Walker 320 may then determine a final matching result 610 for packet 101a, which may be forwarded from HNA 108 to processing core 603, and for packet 101a, which may be forwarded 612 as packet 101b in the network, as appropriate.

In addition to such packet pre-screening by HFA 110, which can reduce the number of false positives processed by NFAs, embodiments disclosed herein can further optimize matching performance by distributing the nodes of each per-pattern NFA across multiple memories within a memory hierarchy based on node locality. Since each NFA can be a per-pattern NFA, embodiments disclosed herein can advantageously distribute the nodes of each per-pattern NFA across multiple memories within a hierarchy based on the understanding that the longer a rule (i.e., pattern), the less likely a node generated from the end of the rule will need to be visited (i.e., walked or traversed). By storing each earlier node of the per-pattern NFA in a relatively faster (i.e., higher performance) memory, embodiments disclosed herein can further optimize matching performance. It should be appreciated that because such node distribution can be based on a hierarchy-to-memory mapping, the nodes can advantageously be distributed based on the mapped hierarchy, thereby enabling any suitable distribution that optimizes matching performance.

As disclosed above, the at least one NFA 314 (such as the per-graph NFA 504 of FIG. 5A ) can be stored in at least one memory, such as the memory 104 of FIG. 1 or the graph memory 456 of FIG. 4 . According to embodiments disclosed herein, the matching performance of the walker 320 can be optimized based on the intelligent compiler 306 advantageously distributing the nodes of the per-graph NFA 504 across the at least one memory 456, which may include multiple graph memories in a memory hierarchy.

For example, the matching performance of the walker 320 can be optimized by storing consecutive nodes (e.g., nodes N0 506, N1 508, N2 510, and N3 512 of section 509 of the per-graph NFA 504 of FIG. 5A ) in a faster-performing memory that is mapped to a higher level in the memory hierarchy relative to another memory storing consecutive nodes N4 514 and N5 515 that can be mapped to a lower level in the memory hierarchy. Because NFA 504 is a per-graph NFA generated from a single graph (e.g., graph 502), NFA 504 is separate from other NFAs generated from other graphs, and thus, embodiments disclosed herein can be based on identifying locality in the nodes of the per-graph NFA that does not exist in the nodes of a unified NFA.

Embodiments disclosed herein may 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) may have a higher probability of being traversed than nodes N4 514 and N5 515 because nodes N4 514 and N5 515 are located toward the end of the rule (i.e., pattern) 502 and therefore require more of the payload to be matched in order to be walked (i.e., traversed). Thus, earlier nodes of a per-pattern HFA (e.g., NFA 504) or any other suitable per-pattern NFA graph may be considered "high touch" nodes that may be visited more frequently due to false positives than "low touch" nodes that are visited only in the event of a complete pattern match.

According to embodiments disclosed herein, compiler 306 can distribute the nodes of each per-pattern NFA to memory 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. This understanding can be used to "pre-cache" (i.e., statically store) the nodes of each per-pattern NFA by distributing these nodes to memory in a memory hierarchy, thereby allowing improved matching performance. For example, "high touch" nodes can be distributed to faster memory based on the understanding that "high touch" nodes will be accessed (i.e., walked or traversed) more frequently due to their locality in the per-pattern NFA.

In general, the regular expression access pattern of a unified NFA generated from a set of regular expression patterns can be random, as such access patterns can be based on specific payloads. 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 does not provide performance benefits to the walker, as the next node visited within the unified NFA may not be the cached node.

FIG7 is a block diagram of an embodiment of an environment 700 for compiler 306. As disclosed above, compiler 306 can be referred to as an intelligent compiler, which can be configured to compile rule set 310 into binary image 112 by identifying portions of rule set 310 that are likely best suited for DFA or NFA processing. Thus, binary image 112 can include at least two sections, a first section for DFA processing and a second section for NFA processing, such as unified DFA 312 and at least one NFA 314, as disclosed above with respect to FIG3A. According to embodiments disclosed herein, HNA 108 can be operatively coupled to multiple memories, which can include graph memory 456, as disclosed above with respect to FIG4. According to embodiments disclosed herein, compiler 306 can be configured to determine placement of nodes of unified DFA 312 and at least one NFA 314 in graph memory 456.

According to embodiments disclosed herein, the unified DFA 312 can be statically stored in a given memory of the graph memory 456, while at least one NFA 314 can have nodes distributed across the graph memory 456 and statically stored, as the compiler 306 can target distributing specific NFA nodes for storage in specific memories to optimize walker matching performance. According to embodiments disclosed herein, the graph memory 456 can be in a memory hierarchy 743 that can include a plurality of levels 708a-c. The plurality of levels 708a-c can be mapped to the plurality of graph memories 456 that can include memories 756a-c.

Compiler 306 may map levels 708a-c in any suitable manner, and levels 708a-c may be sorted in descending order 712 such that level 708a may be the highest-ordered level 708a and level 708c may be the lowest-ordered level. Graphics memory 756a-c may include a random access memory (RAM) that may be high-performance memory co-located with an on-chip search memory (OSM) on the network services processor 100. Graphics memory 756a-c may include system memory that may be external and operatively coupled to the network services processor 100.

Based on a mapping based on memory performance (i.e., read and write access times), the RAM memory may be mapped to the highest-ranked tier 708a, the OSM memory may be mapped to the next-highest-ranked tier 708b, and the system memory may 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 memories 756a-c may be formed in any suitable manner. For example, the mapping may be based on the understanding that an application associated with the rule set 310 from which the nodes are distributed to the memories 756a-c may be generated, and therefore the highest-performance memory may not be worthy of being mapped to the highest-ranked tier. Furthermore, 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 may be any suitable number of tiers and memories.

As disclosed above, the locality of nodes in a per-pattern NFA can be exploited by the intelligent compiler 306 by storing NFA nodes generated from earlier portions of a given pattern in faster memory. Additionally, since the probability of a match for a given pattern is already higher due to the partial matching of the given pattern being determined by the DFA processing of the HFA 110, such embodiments are combined 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 the multiple memories to the levels of the memory hierarchy 743. For example, a smaller NFA generated from a pattern of relatively shorter length can have all nodes distributed to a first level and stored in a first memory mapped to the first level, while a larger NFA generated from a pattern of relatively longer length can have a first node partially distributed to the first level and the remaining nodes distributed among the remaining levels. The first level can be a highest-ranked level mapped to the highest-performance memory.

Thus, the earlier nodes of these per-graph NFAs can be stored in the highest performance memory. Because earlier nodes can have a higher probability of being traversed due to false positives, embodiments disclosed herein can enable most false positives to be handled by accessing memories mapped to higher levels in the memory hierarchy 743. According to embodiments disclosed herein, matching performance can be optimized by enabling a relatively higher number of accesses to the memory 756a mapped to the highest-ranked level (e.g., level 708a in the memory hierarchy 743) than to the memory 756c mapped to the lowest-ranked level 708c.

Memory 756a may be the highest performance memory allowing, for example, 1300 million transactions per second, while memory 756b may have a lower performance allowing 150 million transactions per second, and memory 756c may be the lowest performance memory allowing 12 million transactions per second. Additionally, according to embodiments disclosed herein, the amount of such higher performance memory mapped to the higher-ordered tiers may be relatively smaller in size than the lower performance memory, such as memory 756c (which may be a relatively large memory by comparison), mapped to the lowest-ordered tier 708c. For example, memory 756c may be a type of system memory that is external and provides 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 indicate a target number of unique nodes to be distributed from each per-pattern NFA to a corresponding one of the levels 708a-c to store in a given memory mapped to the corresponding level. Compiler 306 can be configured to determine per-pattern NFA distribution settings 710a-c in such a manner that the memory 756a-c mapped to levels 708a-c provides sufficient storage capacity in the event that a per-pattern NFA is generated for each of the one or more patterns in rule set 310.

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

Based on per-graph NFA storage allocation setting 710b configured for level 708b, compiler 306 may distribute a third portion 706a of the set of corresponding nodes 702a of per-graph NFA 714a and a fourth portion 706b of the set of corresponding nodes 702b of per-graph NFA 714b for storage in memory 756b mapped to level 708b. This distribution is a target distribution because the number of nodes in a given set of corresponding nodes may not include the target number because fewer than the target number may have been previously generated or fewer than the target number may remain in the corresponding set for distribution.

In this example embodiment, per-pattern NFA storage allocation 710c can be configured for the lowest-ordered level 708c of the memory hierarchy 743 and can be specified in an infinite number of ways. In this example embodiment, the memory 756c mapped to the lowest-ordered level 708c can be a type of system memory with a relatively large storage capacity. The compiler 306 can then distribute the nodes to the system memory, including distributing any remaining undistributed nodes for each corresponding set of nodes generated for each of the per-pattern NFAs 714a-b for storage in the system memory 756c.

It should be understood that the compiler may inherently understand the hierarchy of memory mappings and thus may dispense with specific hierarchies 708a-c. For example, compiler 306 may configure per-pattern NFA storage allocation settings 710a-c and map these settings directly to memories 756a-c based on its inherent understanding of the hierarchical mapping of each of memories 756a-c in memory hierarchy 743. It should also be understood that the number of per-pattern NFAs, nodes, and distributions shown in FIG7 is for illustrative purposes and may be any suitable number of per-pattern NFAs, nodes, or distributions.

8 is a block diagram 800 of an example embodiment of a node distribution for 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 the one or more patterns 804, and a third NFA 814c is generated for a third pattern 816c in the one or more patterns 804.

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

As shown in FIG8 , the second node portion 804b of the second NFA 814b distributed for storage in the memory 856a mapped to the level 808a can be smaller than the first node portion 804a and the fifth node portion 804c of the first NFA 814a and 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 represented by a per-pattern NFA storage allocation setting (not shown) for the level 808a. Furthermore, since level 808b is the lowest-ordered level in the memory hierarchy 812, the next per-pattern NFA storage allocation setting (not shown) for level 808b can be significantly larger, allowing all undistributed nodes to be distributed for storage in the memory 856a mapped to the level 808b after the distribution to each level above level 808b has occurred. Thus, in this example embodiment, second node portion 806a may include more nodes than sixth node portion 806c because graph 816a may be a longer rule than graph 816c. Additionally, fourth node portion 806b may be empty because graph 816b may be relatively short, wherein the small number of nodes generated for each graph NFA 814b results in all nodes of each graph NFA 814b being distributed to level 808a for storage in memory 856a.

The 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 via first-node metadata that identifies the second node via a next-node address. According to embodiments disclosed herein, the next-node address can be configured by the compiler 306 to include a portion that indicates a given memory in the 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 executed in at least one processor operatively coupled to a plurality of memories mapped to a plurality of levels in a memory hierarchy in a security device operatively coupled to a network. The method can begin (902) and generate at least one per-pattern nondeterministic finite automaton (NFA) (904). Each per-pattern NFA can be generated for a single regular expression pattern and can include a set of corresponding nodes. The method can distribute the nodes of the set of corresponding nodes of each per-pattern NFA to be stored in the plurality of memories based on the mapped levels and the per-pattern NFA storage allocation settings configured for the levels (906) and then end in the example embodiment (908).

FIG10 is a block diagram 1000 of another example embodiment of another node distribution for multiple per-pattern NFAs. In this example embodiment, node distributions 1004 and 1006 are shown for storage in a first memory 1056a and a second memory 1056b. Distribution 1004 for each per-pattern NFA 1014a-c can be based on per-pattern NFA storage allocation settings 1010a and 1010b, which are configured for use with 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-pattern NFA. According to embodiments disclosed herein, distributing the nodes of the set of corresponding nodes of each generated per-pattern NFA may include distributing the nodes in the set of corresponding nodes in a sequential manner, the distribution comprising a first distribution of the nodes in the set of corresponding nodes for storage in a first memory of the plurality of memories. The first memory may be mapped to a highest-ranked level among the hierarchies. The distribution may include a second distribution of the nodes in the set of corresponding nodes after a previous distribution, based on at least one undistributed node remaining in the set of corresponding nodes. 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 among the hierarchies, the given level being successively lower than the highest-ranked level for each distribution.

The method may begin (1102) and set a given level to the highest-ordered level in a memory hierarchy (1104). The method may set a given per-pattern NFA to a 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).

If the given per-pattern NFA is the last per-pattern NFA generated, the method may check whether the given level is the lowest-ordered level (1120), and if the given level is the lowest-ordered level, then in this example embodiment, the method ends (1126). However, if the result of checking whether the given level is the lowest-ordered level (1120) is no, 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 in the at least one NFA generated by 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 result of checking the number of undistributed nodes for the given per-pattern NFA (1108) is non-zero, the method can check whether the given level is the lowest-ordered level (1110). If so, the method can distribute the number of undistributed nodes to a given memory mapped to the given level (1114) and the method can 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 can continue as disclosed above. If not, the method can set the given per-pattern NFA to the next per-pattern NFA generated (1118), and the method can iterate to again check the number of undistributed nodes for the given per-pattern NFA that has been updated to the next per-pattern NFA generated (1108).

If the result of checking whether the given level is the lowest-ordered level (1110) is no, the method can check whether the number of undistributed nodes of the given per-pattern NFA exceeds the number of nodes represented by a per-pattern NFA storage allocation setting configured for the given level (1112). If so, the method can distribute the number of nodes represented by the per-pattern NFA storage allocation setting configured for the given level for storage in the 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 can continue as disclosed above.

If the result of checking whether the given per-pattern NFA is the last per-pattern NFA (1116) is no, the method may set the given per-pattern NFA to the next per-pattern NFA generated (1118), and the method may iterate to again check the number of undistributed nodes of the given per-pattern NFA that has been updated to the next per-pattern NFA generated (1108).

However, if the result of checking whether the number of undistributed nodes of the given per-pattern NFA exceeds the number of nodes represented by a per-pattern NFA storage allocation setting configured for the given level (1112) is no, the method can distribute the number of undistributed nodes to the given memory mapped to the given level (1114) and continue as disclosed above.

According to embodiments disclosed herein, the per-pattern NFA storage allocation setting can represent the target number of unique nodes via an absolute value. The absolute value can be a common value for each group of corresponding nodes, so that each group of corresponding nodes can have the same value for the target number of unique nodes to be stored in a given memory mapped to the corresponding hierarchy. For example, as shown in FIG10 , each of the per-pattern NFAs 1014 a-c has a selected first portion 1004 representing the same number of nodes from the per-pattern NFAs 1014 a-c to be distributed to the memory 1056 a mapped to the hierarchy 1008 a for which the per-pattern 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 for each group of corresponding nodes, thereby enabling each group of corresponding nodes to have a separate value for the target number of unique nodes to be stored in the given memory mapped to the corresponding level. For example, if a number such as 25% is configured for the per-pattern NFA storage allocation setting 1010a, which is configured for level 1008a, then the first portion 1004 will include 25% of the nodes from each of these per-pattern NFAs 1014a-c. Since the number of nodes in each per-pattern NFA 1014a-c can be different, the number of nodes from each of these per-pattern NFAs 1014a-c can be different.

The per-pattern NFA storage allocation settings may include a first per-pattern NFA storage allocation setting and a second per-pattern NFA storage allocation setting. The tiers may include a highest-ranked tier and a second-highest-ranked tier. The first per-pattern NFA storage allocation setting may be configured for the highest-ranked tier. The second per-pattern NFA storage allocation setting may be configured for the second-highest-ranked tier. The first per-pattern NFA storage allocation setting may be smaller than the second per-pattern NFA storage allocation setting. For example, the number of nodes from each per-pattern NFA represented for distribution to the highest-performance memory may be a system memory that is smaller than the number of nodes represented for the lowest-performance memory (e.g., an infinite number may be represented).

Embodiments disclosed herein can maximize the number of nodes in a given distribution, and the maximized number can be limited by one of these per-pattern NFA storage allocation settings configured for a given hierarchy. For example, the number of nodes represented by a per-pattern NFA storage allocation setting can be ten. Thus, each per-pattern NFA that includes ten or more undistributed nodes will have ten nodes distributed. Each per-pattern that includes fewer than ten undistributed nodes will have a corresponding number of undistributed nodes distributed.

Figure 12 is a block diagram of an example of the internal structure of a computer 1200, in which the various embodiments disclosed herein may be implemented. Computer 1200 includes a system bus 1202, where a bus is a set of hardware lines used to transfer data between components of a computer or processing system. System bus 1202 is essentially a shared conduit that connects the various components of a computer system (e.g., processor, disk storage, memory, input/output ports, network ports, etc.), enabling information transfer between these components. Working in conjunction with system bus 1202 is an I/O device interface 1204 for connecting various input and output devices (e.g., keyboard, mouse, display, printer, speakers, etc.) to computer 1200. Network interface 1206 allows computer 1200 to connect to various other devices attached to a network. Memory 1208 provides volatile storage for computer software instructions 1210 and data 1212, which may be used to implement the embodiments disclosed herein. Disk storage 1214 provides non-volatile storage for computer software instructions 1210 and data 1212 that may be used to implement the embodiments disclosed herein. Central processor unit 1218 also works with system bus 1202 and provides execution of computer instructions.

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

It should be understood that the term "herein" can be transferred to an application or patent incorporating teachings presented herein so that the subject matter, definitions, or data are carried forward in 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 any form of computer-readable medium, such as random access memory (RAM), read-only memory (ROM), compact disc read-only memory (CD-ROM), etc. At work, a general or special purpose processor loads and executes the software in a manner well known in the art. It should be understood that, in addition, the block diagrams and flow charts may include more or fewer elements, be arranged or oriented differently, or be represented differently. It should be understood that implementation may refer to block diagrams, flow charts, and/or network diagrams and the number of block diagrams and flow charts that illustrate the execution of embodiments 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 defined in the following claims.

Claims (37)

1. A security device operatively coupled to a network, the security device comprising: Multiple memories mapped to multiple levels in a memory hierarchy, and at least one processor operatively coupled to the multiple memories, the at least one processor being configured to: Generate at least one per-pattern nondeterministic finite automaton (NFA), each per-pattern NFA being generated for a single regular expression pattern and comprising a set of corresponding nodes; and The nodes of the corresponding nodes for each per-pattern NFA generated by the distribution are stored in the plurality of memories based on the mapped levels and the per-pattern NFA storage allocation settings configured for these levels. 2. The security device of claim 1, wherein the at least one processor is further configured to store the nodes corresponding to the group of each generated per-pattern NFA in the plurality of memories. 3. The security apparatus of claim 1, wherein generating the at least one per-pattern NFA includes specifying a translation from a given node to a next node via a next node address associated with the given node, and the next node address is configured to identify the next node and a given memory allocated to one of the plurality of memories for storage by the next node. 4. The security device of claim 1, wherein each of these per-pattern NFA storage allocation settings is configured for a corresponding level among these levels to represent a unique number of nodes corresponding to the target number of nodes for each generated per-pattern NFA, to be distributed for storage in a given memory mapped to the corresponding level in one of the plurality of memories. 5. The security device of claim 4, wherein the unique nodes in the corresponding group are arranged in a continuous manner within a given per-pattern NFA that includes the corresponding group of nodes. 6. The security device of claim 4, wherein each per-pattern NFA storage allocation setting is configured for the corresponding level in such a way that, in an event in which a per-pattern NFA is generated for each regular expression pattern in a set of regular expression patterns, the given memory is able to provide sufficient storage capacity to store the number of unique nodes representing the target number from each generated per-pattern NFA. 7. The security device of claim 4, wherein the target number of unique nodes is represented by an absolute value and is a shared value for each group of corresponding nodes, such that each group of corresponding nodes can have the same value for the target number of unique nodes, so as to be stored in the given memory mapped to the corresponding level. 8. The security device of claim 4, wherein the target number of unique nodes is represented by a percentage value applied to the total number of nodes in each group of corresponding nodes, such that each group of corresponding nodes can have a separate value for the target number of unique nodes for storage in the given memory mapped to the corresponding level. 9. The security device of claim 1, wherein each of the plurality of memories is sequentially mapped to a corresponding level in descending order based on the performance ranking of the plurality of memories, and the memory with the highest performance ranking among the plurality of memories is mapped to the highest-ranking level among the levels. 10. The security device of claim 1, wherein the per-pattern NFA storage allocation settings include a first per-pattern NFA storage allocation setting and a second per-pattern NFA storage allocation setting, the hierarchy includes a highest-ranking hierarchy and a second-highest-ranking hierarchy, the first per-pattern NFA storage allocation setting being configured for the highest-ranking hierarchy, and the second per-pattern NFA storage allocation setting being configured for the second-highest-ranking hierarchy. 11. The security device of claim 1, wherein the nodes of the group corresponding to each per pattern NFA generated by the distribution include the nodes of the group corresponding to the distribution distributed in a continuous manner, the distribution including: A first distribution of these nodes in the corresponding group, used for storage in a first memory among the plurality of memories, the first memory being mapped to the highest-ordering of these levels; and A second distribution of these nodes in the corresponding group of nodes, based on at least one undistributed node remaining in the corresponding group of nodes after the previous distribution, each at least one second distribution is used to store in a given memory of the plurality of memories, the given memory being mapped to a given level of these levels, the given level being successively lower than the highest-ranked level for each distribution of these nodes in the corresponding group of nodes. 12. The security device of claim 11, wherein if the given level is the lowest-ranked level among these levels, then a given distribution in the at least one second distribution includes all remaining undistributed nodes in the corresponding nodes of the group. 13. The security apparatus of claim 11, wherein the at least one processor is further configured to maximize the number of nodes in the first distribution, and the maximized number may be limited by one of these per-pattern NFA storage allocation settings being configured for the corresponding per-pattern NFA storage allocation setting of the highest sorted level. 14. The security apparatus of claim 11, wherein the at least one processor is further configured to maximize the number of nodes in each of the at least one second distribution, and the maximized number may be limited for each distribution by one of these per-pattern NFA storage allocation settings configured for the corresponding per-pattern NFA storage allocation setting for the given level. 15. The security device of claim 1, wherein the nodes of each set of corresponding nodes for each pattern NFA are statically stored such that the nodes of each set of corresponding nodes can be traversed using multiple segments of multiple payloads in an input stream received from the network to determine a single match of at least one regular expression pattern in the input stream. 16. The security apparatus of claim 15, wherein the walk is performed on individual nodes matching the segments of the payloads corresponding to the set of nodes, and the at least one processor is further configured to determine the per-pattern NFA storage allocation settings based on the total number of regular expression patterns in a set of regular expression patterns and the desired performance metric associated with the walk. 17. The security device of claim 1, wherein the at least one processor is further configured to: A unified deterministic finite automaton (DFA) is generated based on at least one subgraph of each graph selected from a set of regular expression graphs; and The unified DFA is stored in one of the multiple memories. 18. The security device of claim 1, wherein the plurality of memories includes a first memory, a second memory, and a third memory, and the first and second memories are located on a chip together with the at least one processor, while the third memory is an external memory located outside the chip and mapped to the lowest-order of these levels. 19. A method for implementing a nondeterministic finite automaton for each drawing, comprising: In at least one processor, the at least one processor is operatively coupled to a plurality of memories, the plurality of memories being mapped to multiple levels in a memory hierarchy of a security device operatively coupled to a network: Generate at least one per-pattern nondeterministic finite automaton (NFA), each per-pattern NFA being generated for a single regular expression pattern and comprising a set of corresponding nodes; and The nodes corresponding to the group of nodes for each pattern NFA are distributed and stored in the plurality of memories based on the mapped levels and the per-pattern NFA storage allocation settings configured for these levels. 20. The method of claim 19, further comprising storing, based on the distribution, the nodes corresponding to the group of each generated per-pattern NFA in the plurality of memories statically. 21. The method of claim 19, wherein generating the at least one per-pattern NFA includes specifying a transition from a given node to a next node via a next node address associated with the given node, and configuring the next node address to identify the next node and a given memory allocated to one of the plurality of memories for storage by the next node. 22. The method of claim 19, further comprising configuring each of these per-pattern NFA storage allocation settings for a corresponding level among these levels to represent a target number of unique nodes corresponding to the group of generated per-pattern NFAs, for distribution for storage in a given memory mapped to the corresponding level in one of the plurality of memories. 23. The method of claim 22, wherein the unique nodes in the corresponding group are arranged in a continuous manner within a given per-pattern NFA that includes the corresponding group of nodes. 24. The method of claim 22, further comprising configuring a storage allocation setting for each per-pattern NFA for the corresponding hierarchy in such a way that, in an event of generating a per-pattern NFA for each regular expression pattern in a set of regular expression patterns, the given memory is able to provide sufficient storage capacity to store the target number of unique nodes represented from each generated per-pattern NFA. 25. The method of claim 22, wherein the target number of unique nodes is represented by an absolute value and is a shared value for each group of corresponding nodes, such that each group of corresponding nodes can have the same value for the target number of unique nodes, so as to be stored in the given memory mapped to the corresponding level. 26. The method of claim 22, further comprising representing the target number of unique nodes via a percentage value, the percentage value being applied to the corresponding total number of nodes for each group of corresponding nodes, such that each group of corresponding nodes can have a separate value for the target number of unique nodes for storage in the given memory mapped to the corresponding level. 27. The method of claim 19, wherein each of the plurality of memories is sequentially mapped to a corresponding level in descending order based on the performance ranking of the plurality of memories, and the memory with the highest performance ranking among the plurality of memories is mapped to the highest-ranking level among the levels. 28. The method of claim 19, wherein the per-pattern NFA storage allocation settings include a first per-pattern NFA storage allocation setting and a second per-pattern NFA storage allocation setting, the hierarchy including a top-ranking hierarchy and a second-ranking hierarchy, the first per-pattern NFA storage allocation setting being configured for the top-ranking hierarchy, and the second per-pattern NFA storage allocation setting being configured for the second-ranking hierarchy. 29. The method of claim 19, wherein the nodes of the group corresponding to each per pattern NFA generated by the distribution include those nodes distributed in a continuous manner, the distribution comprising: A first distribution of these nodes in the corresponding group, used for storage in a first memory among the plurality of memories, the first memory being mapped to the highest-ordering of these levels; and A second distribution of these nodes in the corresponding group of nodes, based on at least one undistributed node remaining in the corresponding group of nodes after the previous distribution, each at least one second distribution is used to store in a given memory of the plurality of memories, the given memory being mapped to a given level of these levels, the given level being successively lower than the highest-ranked level for each distribution of these nodes in the corresponding group of nodes. 30. The method of claim 29, wherein if the given level is the lowest-ranked level among these levels, then a given distribution in the at least one second distribution includes all remaining undistributed nodes in the corresponding nodes of that group. 31. The method of claim 29, further comprising maximizing the number of nodes in the first distribution, wherein the maximized number may be limited by one of these per-pattern NFA storage allocation settings being configured for the corresponding per-pattern NFA storage allocation setting of the highest sorted level. 32. The method of claim 29, further comprising maximizing the number of nodes in each of at least one second distribution, wherein the maximized number is limited for each distribution by a corresponding per-pattern NFA storage allocation setting configured for the given level. 33. The method of claim 19, further comprising statically storing the nodes of the group corresponding to each per pattern NFA, such that the nodes of the group corresponding to each NFA can be traversed using multiple segments of multiple payloads in an input stream received from the network to determine a single match of at least one regular expression pattern in the input stream. 34. The method of claim 33, wherein the walk is performed on individual nodes matching segments of the payloads corresponding to the set of nodes, and the method further comprises determining the per-pattern NFA storage allocation settings based on the total number of regular expression patterns in a set of regular expression patterns and the desired performance metric associated with the walk. 35. The method of claim 19, further comprising: A unified deterministic finite automaton (DFA) is generated based on at least one subgraph of each graph selected from a set of regular expression graphs; and The unified DFA is stored in one of the multiple memories. 36. The method of claim 19, wherein the plurality of memories includes a first memory, a second memory, and a third memory, and the first and second memories are co-located on a chip with the at least one processor, while the third memory is an external memory located outside the chip and mapped to the lowest-order of these levels. 37. A non-transient computer-readable medium having an instruction sequence encoded thereon, the instruction sequence causing the processor, when loaded and executed by a processor operatively coupled to and mapped to multiple memories at multiple levels in a memory hierarchy, to: Generate at least one per-pattern nondeterministic finite automaton (NFA), each per-pattern NFA being generated for a single regular expression pattern and comprising a set of corresponding nodes; and The nodes corresponding to the group of nodes for each pattern NFA are distributed and stored in the plurality of memories based on the mapped levels and the per-pattern NFA storage allocation settings configured for these levels.