HK1208103B - Method and apparatus for processing finite automata - Google Patents

Description

Method and apparatus for processing finite automata

Background of the Invention

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, that is, they perform packet processing to forward packets at line speed. Typically, general-purpose processors are used to process Layer 4-7 network protocols, which require more intelligent processing. While general-purpose processors can perform computationally intensive tasks, they do not provide sufficient performance to process data at line speed.

Content-aware networking requires inspecting the contents of data packets at "wire speed." This content can be analyzed to determine if there are security vulnerabilities or intrusions. A wide range of patterns and rules in the form of regular expressions are applied to ensure that all security vulnerabilities or intrusions are detected. Regular expressions are a compact method for describing patterns within strings. The simplest pattern matched by a regular expression is a single character or string, such as /c/ or /cat/. Regular expressions 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, with an unlimited number of characters between "abc" and "xyz", find the string "abc" followed by the string "xyz". Another example is the regular expression "abc..abc.*xyz", which finds the string "abc" followed by the string "abc" two characters later and followed by the string "xyz" after an unlimited number of characters.

Intrusion Detection System (IDS) applications examine the contents of all individual packets flowing through a network and identify suspicious patterns that may indicate an attempt to break into or compromise a system. An example of a suspicious pattern might be a specific string of text in a packet that is followed 100 characters later by another specific string of text.

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

SUMMARY OF THE INVENTION

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 operatively coupled to at least one memory in a security device operatively coupled to a network, a method may include: traversing a unified deterministic finite automaton (DFA) stored in the at least one memory with a plurality of characters from a payload through the DFA, the unified DFA being generated from a plurality of subpatterns selected from each pattern in a set of one or more regular expression patterns based on at least one heuristic. The method may traverse at least one nondeterministic finite automaton (NFA) stored in the at least one memory with a plurality of characters from the payload through the NFA, the at least one NFA generated for at least one pattern in the set, a portion of the at least one pattern used to generate the at least one NFA, and at least one direction for traversing the plurality of characters through the NFA being based on whether a length of a subpattern selected from the at least one pattern is fixed or variable and a position of the selected subpattern within the at least one pattern.

The method may report a match of the at least one pattern in the payload based on traversing an NFA node of the at least one NFA associated with metadata indicating a final match of the at least one pattern.

The method may associate a transaction identifier for a given walk of the DFA with the at least one NFA used to match the at least one pattern in the payload. The method may report a match of the at least one pattern in the payload based on: traversing a DFA node of the unified DFA having metadata indicating a DFA partial match of the at least one pattern; subsequently traversing at least one NFA node of the at least one NFA having metadata indicating a NFA partial match of the at least one pattern; and

The traversal and subsequent traversals are correlated with the transaction identifier.

The method may report an offset of a character in the payload that matches a first element of the at least one pattern as a starting offset of the at least one pattern in the payload based on: metadata associated with an NFA node of the at least one NFA and indicating a final match of the at least one pattern in the payload; and metadata associated with a DFA node of the unified DFA and indicating at the DFA node (i) a length of the sub-pattern selected for the at least one pattern, and (ii) a sub-pattern end offset of a sub-pattern character in the payload that matches a last element of the sub-pattern selected for the at least one pattern, the at least one processor determining the starting offset based on subtracting the length from the sub-pattern end offset.

The method may: on the basis of correlating multiple partial matching results indicated in metadata associated with multiple nodes of the unified DFA with the at least one NFA of the at least one pattern, report an offset of a character of the payload that matches a first element of the at least one pattern at an NFA node of the at least one NFA as a starting offset of the at least one pattern in the payload.

The method may: report an offset of a character of the payload that matches a first element of the at least one pattern at an NFA node of the at least one NFA as a starting offset of the at least one pattern in the payload based on metadata associated with the NFA node and a final match determined for the at least one pattern in the payload at the NFA node.

The at least one heuristic may include maximizing the number of unique subpatterns selected and the length of each subpattern selected, the length of each subpattern selected having at least a minimum threshold length.

If a first element of the selected sub-pattern is a first element of the at least one sub-pattern and the length of the selected sub-pattern is fixed, the position of the selected sub-pattern may be a starting position of the at least one sub-pattern, the portion of the at least one pattern used to generate the at least one NFA may be the at least one pattern excluding the selected sub-pattern, the at least one NFA may be a single NFA, and the at least one walking direction of the at least one NFA may be a forward walking direction.

The method may transition to walking the at least one NFA in a forward walking direction at a DFA node of the unified DFA associated with the last element of the selected subpattern and metadata indicating a pointer to a starting node of the at least one NFA to the at least one processor. The starting node of the at least one NFA may be associated with a first element of the at least one pattern used to generate the portion of the at least one NFA. A payload starting offset of the at least one NFA may be associated with an offset of a byte after another byte at the ending offset of the selected subpattern, and a match of the selected subpattern is reported, as an ending offset of the selected subpattern, and a leading offset within the payload of a leading character that matches the last element of the selected subpattern at the DFA node, and a length of the selected subpattern.

The method may terminate the walk at an NFA node of the at least one NFA associated with metadata, the NFA node being associated with a last element of the at least one pattern, and reporting a lag offset within the payload of a lag character matched at the NFA node as an end offset of the at least one pattern and a final match of the at least one pattern.

If a first element of the selected sub-pattern is not a first element of the at least one pattern, and a last element of the selected sub-pattern is not a last element of the at least one pattern, the position of the selected sub-pattern may be a middle position of the at least one pattern; and if the length of the selected sub-pattern is fixed, the portion of the at least one pattern used to generate the at least one NFA may include a lag portion and a leading portion of the at least one pattern, the lag portion of the at least one pattern may be the at least one pattern excluding the selected sub-pattern and the leading portion of the at least one pattern, and the leading portion of the at least one pattern may exclude the selected sub-pattern and the lag portion of the at least one pattern. The at least one NFA may include a lag NFA and a leading NFA, the at least one walking direction may include a forward walking direction and a reverse walking direction, the lag NFA may have the forward walking direction, the leading NFA may have the reverse walking direction, the lag part of the at least one pattern is used to generate the lag NFA, and the leading part of the at least one pattern is used to generate the leading NFA.

The method may, at a DFA node of the unified DFA associated with the last element of the selected subpattern and metadata indicating to the at least one processor a pointer to a start node of the lag NFA and a pointer to a start node of the predecessor NFA: convert a walk of the unified DFA to a walk of the lag NFA in the forward walk direction, the start node of the lag NFA being associated with a first element of the lag portion. The method may convert the walk of the lag NFA to a walk of the predecessor NFA in the reverse walk direction, the start node of the predecessor NFA being associated with a last element of the predecessor portion. The method may report an offset within the payload of a character that matches the last element of the selected subpattern at the DFA node as an end offset of the selected subpattern, a match of the selected subpattern, and a length of the selected subpattern.

The method may terminate walking the lag NFA at a lag node of the lag NFA associated with the last element of the at least one pattern and associated with metadata. The method may report a lag offset within the payload of a lag character of the payload that matches the last element at the lag node, and a match of the lag portion of the at least one pattern. The method may terminate walking the leading NFA at a leading node of the leading NFA associated with metadata that is associated with the first element of the at least one pattern, and report a match of the leading portion of the at least one pattern and a leading offset within the payload of a leading character of the payload that matches the first element at the leading node as a starting offset of the at least one pattern, if required by a qualifier associated with the at least one pattern.

If the first element of the selected sub-pattern is not the first element of the at least one pattern, and the last element of the selected sub-pattern is not the last element of the at least one pattern, the position of the selected sub-pattern may be an intermediate position of the at least one pattern, and if the first element of the selected sub-pattern is the first element of the at least one pattern, the position of the selected sub-pattern may be the starting position of the at least one pattern. If the length of the sub-pattern is fixed or variable, the portion of the at least one pattern used to generate the at least one NFA may include a lag portion and an entire portion of the at least one pattern. The lag portion of the at least one pattern may be the at least one pattern excluding a leading portion of the at least one pattern. The leading portion may include the first element of the at least one pattern, the last element of the selected sub-pattern, and all elements of the at least one pattern therebetween. The entire portion of the at least one pattern may be the at least one pattern. If the position of the selected sub-pattern may be the starting position, the leading portion may be the selected sub-pattern. The at least one NFA may include a lag NFA and an umbrella NFA, and the at least one walking direction may include a forward walking direction and a reverse walking direction. The lag NFA may have the forward walking direction. The umbrella NFA may have the reverse walking direction. The lag portion of the at least one pattern may be used to generate the lag NFA, and the entire portion of the at least one pattern may be used to generate the umbrella NFA.

The method may convert a walk of the unified DFA to walking the lag NFA in a forward direction at a DFA node of the unified DFA associated with the last element of the selected subpattern and with metadata indicating a pointer to a start node of the lag NFA to the at least one processor. The start node of the lag NFA may be associated with a first element of the lag portion. The method may report a match of the selected subpattern, an offset within the payload of a character that matches the last element of the selected subpattern at the DFA node as an end offset of the selected subpattern, and a length of the selected subpattern, if the length is fixed.

The method may, at a lag node of the at least one NFA associated with the last element of the at least one pattern and metadata indicating a pointer to a start node of the umbrella NFA to the at least one processor, switch the walk to the lag NFA to a walk in the reverse direction of the umbrella NFA. The start node of the umbrella NFA may be associated with the last element of the at least one pattern. The method may optionally report an offset within the payload of a character that matches the last element of the at least one pattern at the lag node. The method may optionally report a match for the lag portion of the at least one pattern. The method may, at an umbrella node of the umbrella NFA associated with metadata associated with the first element of the at least one pattern, terminate the walk and report a final match for the at least one pattern and, if required by a qualifier associated with the at least one pattern, a starting offset within the payload of a starting character that matches the first element of the at least one pattern at the umbrella node as a starting offset for the at least one pattern.

If the first element of the selected sub-pattern is not the first element of the at least one pattern, and the last element of the selected sub-pattern is not the last element of the at least one pattern, the position of the selected sub-pattern may be a middle position of the at least one pattern, and if the first element of the selected sub-pattern is the first element of the at least one pattern, the position of the selected sub-pattern may be a starting position of the at least one pattern, and if the length of the sub-pattern is fixed or variable, the portion of the at least one pattern used to generate the at least one NFA may include a lag portion and a leading portion of the at least one pattern. The lag portion of the at least one pattern may be the at least one pattern excluding the leading portion of the at least one pattern. The leading portion may include the first element of the at least one pattern, the last element of the selected sub-pattern, and all elements of the at least one pattern therebetween. If the position of the selected sub-pattern may be the starting position, the lag portion may be the selected sub-pattern. The at least one NFA may include a lag NFA and a leading NFA. The at least one walking direction may include a forward walking direction and a reverse walking direction. The lag NFA may have the forward walking direction. The leading NFA may have the reverse walking direction. The lag portion of the at least one pattern may have been used to generate the lag NFA, and the leading portion of the at least one pattern may have been used to generate the leading NFA.

The method may convert a walk of the unified DFA to a walk of the lag NFA in the forward direction at a DFA node of the unified DFA associated with the last element of the selected subpattern and metadata indicating to the at least one processor a pointer to a start node of the lag NFA and a start node of the predecessor NFA. The start node of the lag NFA may be associated with a first element of the lag portion. The method may convert a walk of the unified DFA to a walk of the predecessor NFA in the reverse direction. The start node of the predecessor NFA may be associated with the last element of the selected subpattern. The method may report a match of the selected subpattern, an offset within the payload of a character that matches the last element of the selected subpattern at the DFA node as an end offset of the selected subpattern, and a length of the selected subpattern, if the length is fixed.

The method may terminate walking the lag NFA at a lag node of the at least one NFA associated with the last element of the at least one pattern and the metadata. The method may report a lag offset within the payload of the lag character that matches the last element of the at least one pattern at the lag node, and report a match of the lag portion of the at least one pattern. The method may terminate walking the lead NFA at a lead node of the at least one NFA associated with the first element of the at least one pattern and the metadata, and report a match of the lead portion and a lead offset within the payload of a lead character that matches the first element of the at least one pattern at the lead node.

If a first element of the selected subpattern is not a first element of the at least one pattern, and a last element of the selected subpattern is not a last element of the at least one pattern, the position of the selected subpattern may be an intermediate position of the at least one pattern; and if the length of the selected subpattern is fixed or variable, the at least one NFA may be a single NFA. The at least one walking direction may include a forward walking direction for runtime processing nodes of the single NFA associated with elements of a lag portion of the at least one pattern, and a reverse walking direction for runtime processing nodes of the single NFA associated with all elements of the at least one pattern. The lag portion of the at least one pattern may be the at least one pattern excluding a leading portion of the at least one pattern. The leading portion may include the first element of the at least one pattern, the last element of the selected subpattern, and all elements of the at least one pattern therebetween.

The method may convert walking the unified DFA into walking the single NFA in a forward direction at a DFA node of the unified DFA associated with the last element of the selected subpattern and associated with metadata indicating a pointer to a start node of the single NFA to the at least one processor. The start node may be associated with the element immediately following the last element of the selected subpattern in the at least one pattern. The method may report a match of the selected subpattern, an offset within the payload of a character that matched the last element of the selected subpattern at the DFA node as an end offset of the selected subpattern, and a length of the selected subpattern, if the length is fixed.

The method may use the payload start offset associated with the end offset of the selected sub-pattern at a lag node of the at least one NFA associated with metadata, associated with a last element of the at least one pattern, to switch from walking the unified DFA to walking the single NFA in a reverse walking direction. The method may terminate the walk at a predecessor node of the at least one NFA associated with metadata, associated with the first element of the at least one pattern. The method may report an offset within the payload of a character that matched the first element of the at least one pattern at the predecessor node as a starting offset for the at least one pattern, if required by a qualifier associated with the at least one pattern, and a final match for the at least one pattern.

If a first element of the selected subpattern is not a first element of the at least one pattern, and a last element of the selected subpattern is not a last element of the at least one pattern, the position of the selected subpattern may be an intermediate position of the at least one pattern; and if the length of the selected subpattern is fixed, the at least one NFA may be a single NFA. The at least one walking direction may include a reverse walking direction for multiple runtime processing nodes of the single NFA associated with a leading portion of the at least one pattern, and a forward walking direction for multiple runtime processing nodes of the single NFA associated with all elements of the at least one pattern. The leading portion may be the at least one pattern excluding a lag portion of the at least one pattern. The lag portion may include the first element of the selected subpattern, the last element of the at least one pattern, and all elements of the at least one pattern therebetween.

The method may, at a DFA node of the unified DFA associated with the last element of the selected subpattern and associated with metadata indicating a pointer to a start node of the single NFA to the at least one processor, cause a walk of the unified DFA to switch to walking the single NFA in a reverse direction. The start node may be associated with a last element of the preamble. A payload start offset may be determined by subtracting the length of the selected subpattern from the end offset of the selected subpattern. The method may report a match of the selected subpattern, an offset within the payload of a character that matched the last element of the selected subpattern at the DFA node as an end offset of the selected subpattern, and the length of the selected subpattern.

The method may walk the single NFA in a forward walking direction at a preceding node of the single NFA associated with the first element of the at least one pattern and associated with metadata. The method may terminate the walking at a lag node of the single NFA associated with the last element of the at least one pattern and associated with metadata. The method may report an offset within the payload of a character that matches the last element of the at least one pattern at the lag node and a final match of the at least one pattern.

If a last element of the selected sub-pattern is a last element of the at least one sub-pattern, the position of the selected sub-pattern may be an end position of the at least one sub-pattern, and if the length of the selected sub-pattern is fixed, the portion of the at least one pattern used to generate the at least one NFA may be the at least one pattern excluding the selected sub-pattern, and the at least one walking direction may be a reverse walking direction.

The method may convert a walk of the unified DFA to a walk of the at least one NFA in a reverse direction at a DFA node of the unified DFA corresponding to the last element of the selected subpattern and associated with metadata indicating a pointer to a start node of the at least one NFA to the at least one processor. The start node of the at least one NFA may be associated with a last element of the portion. The method may report a match of the selected subpattern and an offset within the payload of a character that matches the last element of the selected subpattern at the DFA node as an end offset of the selected subpattern. The payload start offset of the at least one NFA may be determined by subtracting the length of the selected subpattern from the end offset of the selected subpattern, if the length is fixed.

The method may, at an NFA node of the at least one NFA associated with metadata, associated with a first element of the portion: terminate the walk, and report a final match of the at least one pattern, and an offset within the payload of a character that matches the first element of the portion at the NFA node as a starting offset of the at least one pattern, if required by a qualifier associated with the at least one pattern.

If a last element of the selected sub-pattern may be a last element of the at least one sub-pattern, the position of the selected sub-pattern may be an end position of the at least one sub-pattern, and if the length of the selected sub-pattern is variable or fixed, the portion of the at least one pattern used to generate the at least one NFA may be the at least one pattern, and the at least one walking direction may be a reverse walking direction.

The method may, at a DFA node of the unified DFA corresponding to the last element of the selected subpattern and associated with metadata indicating a pointer to a start node of the at least one NFA to the at least one processor, switch the walk of the unified DFA to a walk of the at least one NFA in a reverse direction. The start node of the at least one NFA may be associated with the last element of the selected subpattern. The method may report a match of the selected subpattern, an offset within the payload of a character that matches the last element of the selected subpattern at the DFA node as an end offset of the selected subpattern, and a length of the selected subpattern, whereby, if the length is fixed, a payload start offset of the at least one NFA is associated with the end offset of the selected subpattern.

The method may, at an NFA node of the at least one NFA associated with metadata, associated with a first element of the portion: terminate the walk, and report a final match of the at least one pattern, and an offset within the payload of a character that matches the first element of the portion at the NFA node as a starting offset of the at least one pattern, if required by a qualifier associated with the at least one pattern.

The unified DFA and the at least one NFA may be stored as a binary image including the unified DFA and the at least one NFA.

The at least one processor may include a DFA coprocessor and an NFA coprocessor configured as an acceleration unit to offload DFA and NFA runtime processing, respectively.

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

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

BRIEF DESCRIPTION OF THE DRAWINGS

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

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

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

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

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

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

4 is a block diagram of an embodiment for generating a unified DFA and at least one NFA based on the length of a selected sub-pattern being fixed and the position of the selected sub-pattern being the start position of a regular expression pattern.

FIG5 is a block diagram of an embodiment for generating a unified DFA and at least one NFA based on the position of a selected sub-pattern being the middle position of a regular expression pattern and the length of the selected sub-pattern being fixed.

6 is a block diagram of an embodiment for generating a unified DFA and at least one NFA based on the position of a selected sub-pattern being the middle or the beginning of a regular expression pattern and the length of the sub-pattern being fixed or variable.

7 is a block diagram of another embodiment for generating a unified DFA and at least one NFA based on the position of the selected sub-pattern being the middle or the beginning of the regular expression pattern and the length of the selected sub-pattern being fixed or variable.

8 is a block diagram of an embodiment for generating a unified DFA and at least one NFA based on the position of the selected sub-pattern being the middle position of the regular expression pattern and the length of the selected sub-pattern being fixed or variable.

FIG9 is a block diagram of an embodiment for generating a unified DFA and at least one NFA based on the position of the selected sub-pattern being the middle position of the regular expression pattern and the length of the selected sub-pattern being fixed.

FIG10 is a block diagram of an embodiment for generating a unified DFA and at least one NFA based on the position of a selected sub-pattern being the end position of a regular expression pattern and the length of the selected sub-pattern being fixed.

11 is a block diagram of an embodiment for generating a unified DFA and at least one NFA based on the position of a selected sub-pattern being the end position of a regular expression pattern and the length of the selected sub-pattern being variable or fixed.

12 is a block diagram of an example internal structure of a computer optionally within embodiments disclosed herein.

Detailed Description of the Invention

Before describing example embodiments of the present invention in detail, an example network security application in which these embodiments may be implemented using deterministic finite automata (DFA) and nondeterministic finite automata (NFA) is described below to help readers understand the inventive features of the present invention.

FIG1 is a block diagram of an embodiment of a security appliance 102 in which embodiments of the present invention 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 before forwarding 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 (e.g., packet processing operations) for upper layer network protocols (e.g., L4-L7) and enable processing of the upper layer network protocols in received packets to forward the packets at line speed (i.e., the data transfer rate of the network over which data can be transmitted and received). By processing these protocols to forward these 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 (these network interfaces can be physical hardware interfaces) and can execute L2-L7 network protocols on the received packets. The network services processor 100 can then forward the processed packets 101b via network interfaces 103a or 103b to another hop in the network (the final destination) or via another bus (not shown) for further processing by a host processor (not shown). Network protocol processing may include processing of network security protocols such as firewalls, application firewalls, virtual private networks (VPNs) including IP Security (IPSec) and/or Secure Sockets Layer (SSL), intrusion detection systems (IDS), and antivirus (AV).

The network services processor 100 can use multiple processors (i.e., cores) to deliver high application performance. Each of the cores (not shown) can be dedicated to performing data plane or control plane operations. Data plane operations can include packet operations to forward packets. Control plane operations can include processing multiple parts of complex high-level protocols such as Internet Protocol Security (IPSec), Transmission Control Protocol (TCP), and Secure Sockets Layer (SSL). Data plane operations can include processing other parts of these complex high-level protocols.

The network services processor 100 may also include special purpose coprocessors (not shown) that offload cores to enable high throughput for the network services processor 100. For example, the network services processor 100 may include an acceleration unit 106, which may include a hardware-accelerated hyper nondeterministic automaton (HNA) coprocessor 108 for NFA processing and a hardware-accelerated hyper finite automaton (HFA) coprocessor 110 for DFA processing. The HNA 108 and HFA 110 coprocessors may be configured to offload the burden of executing computationally and memory-intensive pattern matching methods from the general purpose cores (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 to accelerate packet processing. Regular expression processing and pattern searching can be used to perform string matching for AV and IDS applications, as well as other applications that 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 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 can be configured to store compiled rule data utilized for lookups and pattern matching in DFA and NFA graph expression searches. The compiled rule data can be stored as a binary image 112 that includes compiled rule data for both the DFA and NFA, or as multiple binary images that separate the DFA compiled rule data from the NFA compiled rule data.

Typical content-aware application processing uses either a DFA or an NFA to identify patterns in the content of received data packets. Both DFA and NFA are finite state machines, i.e., computational models, each of which consists of a set of states, a start state, an input alphabet (the set of all possible symbols), and a transition function. Computation begins in the start state and changes to a new state according to the transition function.

Patterns are typically expressed using regular expressions, which include basic elements such as normal text characters such as A-Z, 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 Kleene asterisk (*). The metacharacters used for concatenation can be used to create multiple character matching patterns from a single character (or substring), while the metacharacters used for alternation (|) can be used to create a regular expression that can match any of two or more substrings. The metacharacter Kleene asterisk (*) allows the pattern to be matched any number of times, including not occurring in the preceding character or string.

Combining different operators and single characters allows to build complex subpatterns of expressions. For example, a subpattern like (th(is|at)*) can match multiple strings like: th, this, that, thisis, thisat, thatis or thatat. Another example of a complex subpattern of an expression can be the one that combines the character class structure [...] which allows to list a list of characters to be searched for. For example, gr[ea]y finds both grey and gray. Other examples of complex subpatterns are the one that can use a dash to indicate a range of characters (e.g. [A-Z]) or the metacharacter "." which matches any character. The elements of the pattern can be basic elements or a combination of one or more basic elements with one or more metacharacters.

The input to a DFA or NFA state machine is typically a (8-bit) byte string, i.e., a letter can be a single byte (a character or symbol) from the input stream (i.e., the received data packet). Each byte in the input stream can generate a transition from one state to another. The states and transition functions of a DFA or NFA state machine can be represented by a graph. Each node in the graph can represent a state, and the arcs in the graph can represent state transitions. The current state of the state machine can be represented by the node identifier of a particular node in the selection graph.

DFA can be used to process regular expressions and find one or more patterns described by regular expressions in the input stream of characters to be characterized as having definite runtime performance. The next state of DFA can be determined from the current state of input characters (or symbols) and DFA, because each DFA state has only one state transition. Like this, the runtime performance of DFA is considered to be definite and can predict behavior from input completely. However, a compromise for determinism is a graph in which the number of nodes (or graph size) can be exponentially increased along 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 a regular expression and find one or more patterns described by the regular expression in an input stream of characters can be characterized as having non-deterministic runtime performance. For example, given an input character (or symbol) and the current state of the NFA, there may be more than one next state of the NFA to be converted to. 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 considered to be non-deterministic because the behavior cannot be fully predicted from the input.

Figures 2A-G illustrate the concept of DFA "graph explosion." Figures 2A, 2B, and 2C respectively illustrate NFA graphs for the patterns ".*a[^\n]," ".*a[^\n][^\n]," and ".*a[^\n][^\n][^\n]," and Figures 2D, 2E, and 2F respectively illustrate DFA graphs for the same patterns. As shown in Figures 2A through 2F and summarized in the table of Figure 2G, the NFA can grow linearly for certain patterns, while the DFA for the same pattern can grow exponentially, 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 by the order of hundreds or thousands of states more. This is an example of "graph explosion," a hallmark characteristic of DFAs.

According to embodiments disclosed herein, content search 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 an input list of patterns (also referred to as features or rules) into a DFA, NFA, or a combination thereof. The DFA and NFA can be binary data structures such as DFA and NFA graphs and tables.

The walker can perform runtime processing, that is, the action of identifying the existence of a pattern in an input stream or matching the pattern with the content in the input stream. The content can be the payload portion of an Internet Protocol (IP) datagram, or any other suitable payload in the input stream. The runtime processing of a DFA or NFA graph can be referred to as walking the DFA or NFA graph with a payload to determine pattern matching. The processor is configured to generate a DFA, NFA, or a combination thereof and can be referred to as a compiler at this time. The processor configured to use the generated DFA, NFA, or a combination thereof to implement runtime processing of a payload can be referred to as a walker at this time. 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 of the present invention may be implemented. As described 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 uses the binary image 112. For example, the compiler 306 may generate a binary image 112 that includes 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, based on at least one heuristic method as further described below, for a DFA, an NFA, or a combination thereof. The compiler 306 may determine rule data that is advantageously suitable for both a DFA and an NFA.

According to embodiments disclosed herein, compiler 306 can generate binary image 112 by processing rule set 310, which can include set 304 of one or more regular expression patterns and optional qualifiers 308. Based on rule set 310, compiler 306 can generate 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 pattern in set 304 of one or more regular expression patterns for use by walker 320 during runtime processing, as well as metadata (not shown) including mapping information for use by walker 320 in transitioning between states (not shown) of unified DFA 312 and states of at least one NFA 314. Unified DFA 312 and at least one NFA 314 can be represented as a graph or in any other suitable form on a data structure basis, and the mapping in the metadata can be represented as one or more tables or in any other suitable form on a data structure basis. According to embodiments disclosed herein, if a sub-pattern selected from a pattern is the pattern, then no NFA is generated for the pattern. According to embodiments disclosed herein, each NFA generated can be used for a specific pattern in a set, and a unified DFA can be generated based on all sub-patterns from all patterns in the set.

Based on the bytes consumed from the payload in the received data packet 101a, the walker 320 walks the unified DFA 312 and the at least one NFA 314 with the payload by transitioning the states of the unified DFA 312 and the at least one NFA. In this way, the walker 320 walks the payload through the unified DFA 312 and the at least one NFA 314.

The rule set 310 may include a set 304 of one or more regular expression patterns and may be in the form of a Perl Compatible Regular Expression (PCRE) script file 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 and more threats have become prevalent on the Internet, the corresponding features/patterns or applications used to identify viruses/attacks have become more complex. For example, feature databases have evolved from having simple string patterns to regular expression (regex) patterns with wildcard characters/ranges/character classes and advanced PCRE features.

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

Due to emerging applications, the starting offset has become more important for processing in deep packet inspection (DPI) systems. Advantageously, the finite automaton only needs to report the presence or absence of a given pattern in the input and the ending offset of the matched pattern in the payload for processing. As described below with reference to Figures 4 to 11, if the qualifier 322 indicates that a starting offset is desired, the compiler 306 can generate the binary image 112 in a manner that enables the walker 320 to report (i.e., declare) the position offset of the payload of the first matching character of the pattern that matches in the payload.

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

The compiler can determine whether the length of a selected potential sub-pattern is fixed or variable. For example, 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 operators can be determined to have a variable length. For example, a complex sub-pattern such as "a.*cd[^\n]{0,10}.*y" can have a length of "cd[^\n]{0,10}", which can have a variable length of 2 to 12, depending on the selected pattern.

According to the embodiments disclosed herein, subpattern selection can be based on at least one heuristic. A subpattern is a collection 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 in order to match bytes or characters from a payload. The elements described above can be single text characters represented by nodes or character classes represented by nodes. The compiler 306 can determine which subpatterns in a pattern are more suitable for an NFA based on whether the subpattern is likely to cause excessive DFA graph explosion as described above with reference to Figures 2A-G. For example, generating a DFA from a subpattern including consecutive text characters will not cause a DFA graph explosion, while a complex subpattern as described above can include multiple operators and multiple characters and thus may cause a DFA graph explosion. For example, a subpattern including wildcard characters or a large character class repeated multiple times (e.g., [^\n]* or [^\n]{16}) can produce too many states in a DFA and therefore can be more advantageously suitable for an NFA.

As disclosed above, the selection of a subpattern from each pattern in the set 304 of one or more regular expressions 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 selected pattern. For example, a pattern such as "ab.*cdef.*mn" can have multiple potential character patterns, such as "ab.*," "cdef," and ".*mn." The compiler can select "cdef" as the subpattern of this pattern because it is the largest subpattern in the pattern "ab.*cdef.*mn" that is unlikely to cause a DFA graph explosion. However, if the subpattern "cdef" has already been selected for another pattern, the compiler can select an alternative subpattern for the pattern "ab.*cdef.*mn." Alternatively, the compiler can replace the subpattern "cdef" with another subpattern of another pattern, thereby being able to select the pattern "cdef" for the pattern "ab.*cdef.*mn."

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

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

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

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 along with an identifier (not shown) of pattern 316 from which subpattern 318 was selected. For example, compiler 306 may calculate a hash value for the selected subpattern for each pattern in set 304. The calculated hash values 324 may be stored in at least one memory 104 in a table or in any other suitable manner. The hashing method used may be any suitable hashing method. The compiler may compare the calculated hash value with a list of hash values for subpatterns selected for other patterns in the set to determine whether the selected subpattern is unique.

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

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

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

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

The at least one heuristic method can include determining a priority for a given sub-pattern of each pattern based on the sub-pattern type of each of the given sub-patterns and the length of the given sub-pattern. The sub-pattern type can be plain text, alternating, single character repeating, or multiple character repeating, and the sub-pattern type can be prioritized from highest to lowest by plain text, alternating, single character repeating, or multiple character repeating. In this way, sub-patterns having text strings of at least a minimum length threshold can be prioritized higher 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 prioritization. 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 is unique and has a length of at least a minimum length threshold, compiler 306 can select a non-unique subpattern as the selected subpattern based on a prioritization. Thus, 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 length threshold. To facilitate the final determination of a subpattern, compiler 306 can perform multiple passes on the pattern and sort the possible subpatterns by length. Thus, compiler subpattern selection for a given pattern in set 304 of one or more regular expressions can be performed within the context of subpattern selection for other patterns in set 304 of one or more regular expressions.

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

According to embodiments disclosed herein, if the payload in a received data packet 101 includes content that matches a sub-pattern 318 selected 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 in the received data packet identifying a position in the received data packet of the last character of the matching sub-pattern as the end offset of the sub-pattern in the payload. If the sub-pattern is a subset of the pattern, the sub-pattern match can be a partial match of the pattern. Thus, walker 320 can continue searching for the remainder of the pattern in the payload 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 data packet 101a.

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

FIG3C is a flowchart (380) of an example embodiment of a method that can be implemented in at least one processor operatively coupled to at least one memory within a security device operatively coupled to a network. A unified DFA (384) can be started (382) by traversing a plurality of characters from a payload through a plurality of nodes of a unified DFA stored in at least one memory, the unified DFA being generated based on at least one heuristic selected from a plurality of subpatterns from each pattern in a set of one or more regular expression patterns. The method can include traversing a plurality of characters from the payload through a plurality of nodes of at least one NFA stored in the at least one memory, the at least one NFA generated for at least one pattern in the set, a portion of the at least one pattern used to generate the at least one NFA, and at least one direction for traversing the plurality of characters through the at least one NFA being based on whether a length of a subpattern selected from the at least one pattern is fixed or variable and a position of the selected subpattern within the at least one pattern (386). Thereafter, in this example embodiment, the method ends (388).

As disclosed above, compiler 306 can generate unified DFA 312 and at least one NFA 314 to enable walker 320 to search for matches to one or more regular expression patterns 304 in received data packet 101a. Compiler 306 can select a subpattern from each pattern in set 304 of one or more regular expression patterns based on at least one heuristic. Unified DFA 312 can be generated using subpatterns 302 selected from all patterns in set 304. Compiler 306 can generate at least one NFA 314 for at least one pattern 316 in set 304. As disclosed below with reference to Figures 4 through 11, the portion of at least one pattern 316 used to generate at least one NFA 314 and at least one walking direction for runtime processing of 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 within the at least one pattern 316.

FIG4 is a block diagram 400 for generating a unified DFA 312 and at least one NFA 314 based on a selected subpattern 404 having a fixed length and a selected location of the subpattern as the starting location of at least one pattern 406. As shown in FIG4 , the first element 408 of the selected subpattern 404 is the first element of the at least one pattern 406. The portion 410 of the at least one pattern 406 used to generate the at least one NFA 402 may be the at least one pattern 406 excluding the selected subpattern 404. The at least one NFA 314 may be a single NFA 402, and the at least one walking direction of the at least one NFA 314 may be a forward walking direction 412. For example, for a given pattern (e.g., "cavium"), the forward walking direction would move an input payload through multiple nodes of the at least one NFA 314 in a walking direction from "c" to "m," while the reverse walking direction would move the input payload in a walking direction from "m" to "c."

4 , compiler 306 may associate DFA node 414 of unified DFA 312 with metadata 418, the DFA node being associated with last element 416 of selected subgraph 404. Metadata 418 may indicate a pointer 420 to start node 422 of single NFA 402 to walker 320, which is configured to walk unified DFA 312 and at least one NFA 314 with payload 426. Metadata 418 may include instructions for translating into walking NFA 402 in forward walking direction 412. Start node 422 of single NFA 402 may be associated with first element 424 of portion 410 of at least one graph 406 used to generate single NFA 402. The metadata 418 may instruct the walker 320 to report a match of the selected sub-pattern 404, a leading offset (of the plurality of offsets 428) within the payload 426 that matches the last element 416 of the selected sub-pattern 404 at the DFA node 414 as an ending offset of the selected sub-pattern, and a length of the selected sub-pattern. The starting offset of the payload for walking the single NFA 402 may be an offset of one byte after the byte at the ending offset in the payload 426. For example, the next character in the payload for starting to walk the single NFA 402 at the start node 422 may be determined to be the byte after the byte at the ending offset in the payload. Since the length of the selected sub-pattern is fixed, the compiler 306 may determine the length of the selected sub-pattern and include it in the metadata 418. The walker 320 may use the length included in the metadata 418 to determine the starting offset of the pattern 406 within the payload 426. For example, if one of the qualifiers 308 requires it, the walker 320 may determine the starting offset by subtracting the length included in the metadata 418 from the determined ending offset.

It should be understood that reporting can be performed in any suitable manner. For example, the walker 320 can report the end offset by declaring the end offset to the network service processor 100, such as by writing to a storage unit, triggering an interrupt, sending or posting a message, etc. Alternatively, the walker 320 can report the end offset or any other offset or matching result-based information by declaring the end offset or other determination results in its own data structure for use in the walker's own process.

4 , the compiler 306 may associate an NFA node 432 of the generated single NFA with metadata 434 indicating to the walker an instruction to terminate the walk because a final match has been identified for the entire pattern 406. The NFA node 432 may be associated with a last element 436 of the at least one pattern 406. The metadata 434 may instruct the walker 320 to report a lag offset (of the plurality of offsets 428) within the payload 426 of a lag character (of the plurality of characters 430) matched at the NFA node 432 as the end offset of the at least one pattern 406 and the final match for the at least one pattern 406.

The walker 320 can associate each walk of a given pattern with a transaction identifier. In this way, the sub-pattern length, payload character offset, and pattern matching results can be reported in conjunction with the corresponding transaction identifier. In an exemplary embodiment, the network services processor 100 can associate the walker result information for a given pattern based on the transaction identifier for use in a walk search for the given pattern.

FIG5 is a block diagram 500 of an embodiment for generating a unified DFA 312 and at least one NFA 314 based on a selected sub-pattern 504 being positioned in the middle of at least one pattern 506 and having a fixed length. According to the example embodiment of FIG5 , the portion of the at least one pattern 506 used to generate the at least one NFA 314 includes a lag portion 508 and a leading portion 510 of the at least one pattern 506. As shown in FIG5 , the lag portion 508 of the at least one pattern 506 may be the at least one pattern 506 excluding the selected sub-pattern 504 and the leading portion 510 of the at least one pattern 506. The leading portion 510 of the at least one pattern 506 excludes the selected sub-pattern 504 and the lag portion 508 of the at least one pattern 506.

5 , the at least one NFA 314 includes a lag NFA 512 and a leading NFA 514. The at least one travel direction includes a forward travel direction 516 and a reverse travel direction 518. The lag NFA 512 can be traveled in the forward travel direction 516, and the leading NFA 514 can be traveled in the reverse travel direction 518. The lag portion 508 of the at least one pattern 506 can be used to generate the lag NFA 512, and the leading portion 510 of the at least one pattern 506 can be used to generate the leading NFA 514.

According to the example embodiment of FIG5 , compiler 306 may associate DFA node 515 of unified DFA 312 with metadata 520, the DFA node having last element 522 of selected subgraph 504. Metadata 520 may indicate to a walker that the walker is configured to walk unified DFA 312 and at least one NFA 314 using a payload, such as payload 426 of FIG4 . Metadata 520 may include a pointer 524 to a start node 526 of lag NFA 512, causing walker 320 to convert instructions to walk lag NFA 512 in a forward walking direction 516 using a payload starting at an offset of one byte after the end offset of payload 426. Start node 526 of lag NFA 512 may be associated with a first element 528 of lag portion 508. The metadata 520 may indicate a pointer 530 to a start node 532 of the preceding NFA 514 and instructions for the walker 320 to convert into walking the preceding NFA 514 in the reverse walking direction 518. The start node 532 of the preceding NFA 514 may be associated with a last element 534 of the leading portion 510. The metadata 520 may instruct the walker 320 to report an offset (from a plurality of offsets 428) within the payload 426 of a character (from a plurality of characters 430) that matches the last element of the selected sub-pattern 522 at the DFA node 515 as an end offset of the selected sub-pattern 504, a match of the selected sub-pattern, and a length of the selected sub-pattern. The walker 320 may use the length included in the metadata 520 to determine the starting offset of the payload for starting the reverse walking at the start node 532 by subtracting the length of the selected sub-pattern in the metadata 520 from the end offset of the selected sub-pattern 504.

5 , the compiler 306 may associate a lag node 536 of the lag NFA 512 with metadata 540, the lag node being associated with the last element 538 of the at least one pattern 506. The metadata 540 may indicate to the walker 320 an instruction to terminate walking the lag NFA 512 and to report a lag offset (from among the plurality of offsets 428) within the payload 426 of a lag character (from among the plurality of characters 430) of the payload 426 that matches the last element 538 at the lag node 536. The metadata 540 may instruct the walker 320 to report a match of the lag portion 508 of the at least one pattern 506.

5 , the compiler 306 may associate the predecessor node 542 of the predecessor NFA 514 with metadata 546, the lag node being associated with the first element 544 of the at least one pattern 506, wherein the metadata indicates to the walker 320 an instruction to terminate walking the predecessor NFA 514. The metadata 546 may instruct the walker 320 to report a match for the predecessor portion 510 of the at least one pattern 506. The metadata 546 may instruct the walker 320 to report a leading offset (from the plurality of offsets 428) within the payload 426 of a leading character (from the plurality of characters 430) of the payload 426 that matches the first element 544 at the predecessor node 542 as the starting offset of the at least one pattern 506, if required by a qualifier associated with the at least one pattern 506 (such as one of the qualifiers 308).

FIG6 is a block diagram 600 of an embodiment for generating a unified DFA 312 and at least one NFA 314 based on the position of the selected sub-pattern being at the middle or beginning of the at least one pattern and the length of the sub-pattern being fixed or variable. According to the example embodiment of FIG6 , the portion of the at least one pattern 606 used to generate the at least one NFA 314 includes a lag portion 608 and an entire portion 610 of the at least one pattern 606. The lag portion 608 of the at least one pattern 606 may be the at least one pattern 606 excluding a leading portion 612 of the at least one pattern 606. The leading portion 612 includes the first element 614 of the at least one pattern 606, the last element 616 of the selected sub-pattern 604, and all elements of the at least one pattern 606 therebetween. The entire portion 610 of the at least one pattern 606 may be the at least one pattern 606.

If a first element 618 of the selected sub-pattern 604 is not a first element 614 of the at least one pattern 606, and a last element 616 of the selected sub-pattern 604 is not a last element 620 of the at least one pattern 606, the position of the selected sub-pattern is a middle position of the at least one pattern 606, and a starting portion 622 precedes the selected sub-pattern 604 in the at least one pattern 606.

If the first element 618 of the selected sub-pattern 604 is the first element 614 of the at least one pattern, the position of the selected sub-pattern is the starting position of the at least one pattern 606. If the position of the selected sub-pattern is the starting position, the starting portion 622 does not exist, and the leading portion 612 is the selected sub-pattern 604.

According to the example embodiment of FIG6 , the at least one NFA includes a hysteresis NFA 624 and an umbrella NFA 626. The at least one walking direction includes a forward walking direction 628 and a reverse walking direction 630. The hysteresis NFA 624 has a forward walking direction 628, and the umbrella NFA 626 has a reverse walking direction 630. The hysteresis portion 608 of the at least one graph 606 can be used by the compiler 306 to generate the hysteresis NFA 624. The entire portion 610 of the at least one graph 606 can be used by the compiler 306 to generate the umbrella NFA 626.

6 , compiler 306 may associate DFA node 632 of unified DFA 312 with metadata 634, the DFA node having last element 616 of selected subgraph 604. Metadata 634 may indicate to walker 320 a pointer 636 to a start node 638 of lag NFA 624 and instructions to walk lag NFA 624 in a forward walking direction 628. Start node 638 of lag NFA 624 may be associated with a first element 640 of lag portion 608. The metadata 634 may instruct the walker 320 to report a match of the selected sub-pattern 604, an offset (of the offsets 428) within the payload 426 of a character (of the characters 430) that matches the last element 616 of the selected sub-pattern 604 at the DFA node as an ending offset of the selected sub-pattern 604, and a length of the selected sub-pattern 604, if the length is fixed.

According to the example embodiment of FIG6 , the compiler 306 may associate a lag node 642 of a lag NFA 624 with metadata 652, the lag node being associated with the last element 620 of the at least one graph 606. The metadata 652 may indicate to the walker 320 a pointer 644 to a start node 646 of an umbrella NFA 626, translating into instructions to walk the umbrella NFA 626 in the reverse walking direction 630. The start node 646 of the umbrella NFA 626 may be associated with the last element 620 of the at least one graph 606. The metadata 652 may instruct the walker to optionally report an offset (from the plurality of offsets 428) within the payload 426 of a character (from the plurality of characters 430) that matches the last element 620 of the at least one graph 606 at the lag node 642, and optionally report a match for the lag portion 608 of the at least one graph 606.

According to the example embodiment of FIG6 , the compiler 306 may associate an umbrella node 648 of the umbrella NFA 626 with metadata 650, the umbrella node being associated with the first element 614 of the at least one pattern 606. The metadata 650 may indicate to the walker 320 an instruction to terminate the walk and report a final match for the at least one pattern 606. The metadata 650 may instruct the walker to report a starting offset (from the plurality of offsets 428) within the payload 426 of a starting character that matches the first element 614 of the at least one pattern 606 at the umbrella node 648 as the starting offset of the at least one pattern 606, if required by one of the qualifiers 308 associated with the at least one pattern 606.

FIG7 is a block diagram 700 of another embodiment for generating a unified DFA 312 and at least one NFA 314 based on the position of a selected sub-pattern 704 being at the middle or starting position of at least one pattern 706 and the length of the selected sub-pattern 704 being fixed or variable. According to the example embodiment of FIG7 , the portion of the at least one pattern used to generate the at least one NFA 314 includes a lag portion 708 and a leading portion 712 of the at least one pattern 706. The lag portion 708 of the at least one pattern 706 may be the at least one pattern 706 excluding the leading portion 712 of the at least one pattern 706. The leading portion 712 includes the first element 714 of the at least one pattern 706, the last element 716 of the selected sub-pattern 704, and all elements of the at least one pattern 706 therebetween. If the position of the selected sub-pattern is at the starting position, the leading portion 712 may be the selected sub-pattern 704.

If a first element 718 of the selected sub-pattern 704 is not a first element 714 of the at least one pattern 706, and a last element 716 of the selected sub-pattern 704 is not a last element 720 of the at least one pattern 706, the position of the selected sub-pattern is a middle position of the at least one pattern 706, and a starting portion 722 is before the selected sub-pattern 704 in the at least one pattern 606.

If the first element 718 of the selected sub-pattern 704 is the first element 714 of the at least one pattern, the position of the selected sub-pattern is the starting position of the at least one pattern 706. If the position of the selected sub-pattern is the starting position, the starting portion 722 does not exist, and the leading portion 712 is the selected sub-pattern 704.

According to the example embodiment of FIG7 , the at least one NFA 314 includes a lag NFA 724 and a leading NFA 726, and the at least one travel direction includes a forward travel direction 728 and a reverse travel direction 730. The lag NFA 724 has a forward travel direction 728. The leading NFA 726 has a reverse travel direction 730. The lag portion 708 of the at least one pattern 706 may be used to generate the lag NFA 724. The leading portion 712 of the at least one pattern 706 may be used to generate the leading NFA 726.

According to the example embodiment of FIG7 , compiler 306 may associate DFA node 732 of unified DFA 312 with metadata 734, which is associated with last element 716 of selected subgraph 704. Metadata 734 may indicate to walker 320 a pointer 736 to start node 738 of lag NFA 724 and may translate into instructions to walk lag NFA 724 in forward walking direction 728. Start node 738 of lag NFA 724 may be associated with first element 740 of lag portion 708. The starting offset of the payload for starting forward walking of lag NFA 724 may be a byte offset after the byte at the end offset of selected subgraph 704. Metadata 734 may indicate to walker 320 a pointer 744 to start node 746 of predecessor NFA 726 and may translate into instructions to walk predecessor NFA 726 in reverse walking direction 730. The starting node 746 of the leading NFA 726 may be associated with a last element 716 of the selected sub-pattern 704. The offset of the payload used to start the reverse walk of the leading NFA 726 may be the ending offset of the selected sub-pattern 704. The metadata 734 may instruct the walker 320 to report a match of the selected sub-pattern 704, an offset (of the offsets 428) within the payload 426 of a character (of the characters 430) that matches the last element 716 of the selected sub-pattern 704 at the DFA node 732 as an ending offset of the selected sub-pattern 704, and a length of the selected sub-pattern 704, if the length is fixed.

7 , the compiler 306 may associate a lag node 742 of the lag NFA 724 with metadata 752, the lag node being associated with the last element 720 of the at least one pattern 706. The metadata 752 may instruct the walker 320 to terminate walking the lag NFA and to report a lag offset (of the offsets 428) within the payload 426 of a lag character (of the characters 430) that matches the last element 720 of the at least one pattern 706 at the lag node 742, and to report a match for the lag portion 708 of the at least one pattern 706.

7 , the compiler 306 may associate a predecessor node 748 of the generated predecessor NFA 724 with metadata 750, the predecessor node being associated with the first element 714 of the at least one pattern 706. The metadata 750 may indicate to the walker 320 an instruction to terminate walking the predecessor NFA 726 and to report a match of the predecessor portion 712 and a predecessor offset (one of the offsets 428) within the payload of a predecessor character (one of the characters 430) that matches the first element 714 of the at least one pattern 706 at the predecessor node 748.

The embodiment of FIG. 7 can be viewed as an optimization of the embodiment of FIG. 6 , as the walker 320 does not need to traverse the NFA in the reverse direction for the lag portion 708 .

FIG8 is a block diagram 800 of one embodiment for generating a unified DFA 312 and at least one NFA 314 based on a selected sub-pattern 804 being positioned in the middle of at least one pattern 806 and having a fixed or variable length. According to the example embodiment of FIG8 , the at least one NFA 314 is a single NFA 854. The at least one walking direction includes a forward walking direction 828 for a plurality of runtime processing nodes associated with a plurality of elements of a lag portion 808 of the at least one pattern 806 of the single NFA 854, and a reverse walking direction 830 for a plurality of runtime processing nodes associated with all elements of the at least one pattern 806 of the single NFA 854. The lag portion 808 of the at least one pattern 806 is the at least one pattern 806 excluding a leading portion 812 of the at least one pattern 806. The leading portion 812 includes a first element 814 of the at least one pattern 806 , a last element 816 of the selected sub-pattern 804 , and all elements of the at least one pattern 806 therebetween.

8 , compiler 306 may associate DFA node 832 of unified DFA 312 with metadata 834, the DFA node being associated with the last element 816 of the selected sub-graph 804. Metadata 834 may indicate to walker 320 a pointer 836 to a start node 856 of a single NFA 854 and may be converted into instructions for walking single NFA 854 in a forward walking direction 828. Start node 856 may be associated with the next element 840 in the at least one graph 806 that immediately follows the last element 816 of the selected sub-graph 804. The metadata 834 may instruct the walker 320 to report a match of the selected sub-pattern 804, an offset (of the offsets 428) within the payload 426 of a character (of the characters 430) that matches the last element 816 of the selected sub-pattern 804 at the DFA node 832 as an ending offset of the selected sub-pattern 804, and a length of the selected sub-pattern 804, if the length is fixed.

8 , the compiler 306 may associate a lag node 842 of a single NFA 854 associated with the last element 820 of the at least one pattern 806 with metadata 852, the metadata indicating to the walker 320 an instruction to convert the single NFA 854 into a walk in the reverse walking direction 830 with a payload starting at the end offset of the selected sub-pattern. The compiler 306 may also associate a predecessor node 848 of the single NFA 854 associated with the first element 814 of the at least one pattern 806 with metadata 850. The metadata 850 may indicate an instruction to the walker 320 to terminate the walk and report an offset (of the offsets 428) within the payload 426 of a character (of the characters 430) that matches the first element 814 of the at least one pattern 806 at the preceding node 848 as the starting offset of the at least one pattern 806 (if required by one of the qualifiers 308 associated with the at least one pattern 806), and a final match of the at least one pattern 806.

FIG9 is a block diagram 900 of one embodiment for generating a unified DFA 312 and at least one NFA 314 based on a selected sub-pattern 904 being positioned in the middle of at least one pattern 906 and having a fixed length. According to the example embodiment of FIG9 , the at least one NFA 314 may be a single NFA 954, and the at least one walking direction includes a reverse walking direction 930 for a plurality of runtime processing nodes associated with a leading portion 912 of the at least one pattern 906 of the single NFA 954, and a forward walking direction 928 for a plurality of runtime processing nodes associated with all elements of the at least one pattern 906 of the single NFA 954. The leading portion 912 may be the at least one pattern 906 excluding a lagging portion 908 of the at least one pattern 906. The lag portion 908 includes a first element 918 of the selected sub-pattern 904, a last element 920 of the at least one pattern 906, and all elements of the at least one pattern 906 therebetween.

According to the example embodiment of FIG9 , compiler 306 may associate DFA node 932 of unified DFA 312 with metadata 956, which is associated with last element 916 of selected subgraph 904. Metadata 956 may indicate to walker 320 a pointer 936 to start node 946 of single NFA 954 and an instruction to walk single NFA 954 in reverse walking direction 930. Start node 946 may be associated with last element 912 of preamble 912. Metadata 956 may instruct walker 320 to report a match for selected subgraph 904. Metadata 956 may instruct walker 320 to report an offset (of offsets 428) within payload 426 of a character (of characters 430) that matches last element 916 of selected subgraph 904 at DFA node 932 as an ending offset for selected subgraph 904, and a length for the selected subgraph. The walker 320 may use the length, if included in the metadata 956 , to determine the payload start offset of the start node 946 by subtracting the length of the selected subpattern in the metadata 956 from the end offset of the selected subpattern.

According to the example embodiment of FIG9 , the compiler 306 may associate a predecessor node 948 of a single NFA 954 with metadata 950, the predecessor node being associated with the first element 914 of the at least one pattern 906. The metadata 950 may indicate to the walker 320 an instruction to convert the single NFA 954 into a forward walk direction 928. The compiler 306 may associate a lag node 942 of the single NFA 954 with metadata 952, the predecessor node being associated with the last element 920 of the at least one pattern 906. The metadata 952 may indicate to the walker 320 an instruction to terminate the walk. The metadata 952 may instruct the walker to report an offset (of the offsets 428) within the payload 426 of a character (of the characters 430) that matches the last element 920 of the at least one pattern 906 at the lag node 942, and a final match of the at least one pattern 906.

FIG10 is a block diagram 1000 of one embodiment for generating a unified DFA 312 and at least one NFA 314 based on the position of a selected sub-pattern 1004 being the end position of at least one pattern 1006 and the length of the selected sub-pattern 1004 being fixed. According to the example embodiment of FIG10 , if the last element 1016 of the selected sub-pattern 1004 can be the last element of the at least one pattern 1016, the position of the selected sub-pattern 1004 can be the end position of the at least one pattern 1006, and the at least one NFA 314 can be a single NFA 1054. If the length of the selected sub-pattern 1004 is fixed, the portion 1012 of the at least one pattern 1006 used to generate the single NFA 1054 can be the at least one pattern 1006 excluding the selected sub-pattern 1004. The at least one walking direction can be a reverse walking direction 1030 for walking the single NFA 1054.

According to the example embodiment of FIG10 , compiler 306 may associate metadata 1052 with DFA node 1032 corresponding to last element 1016 of selected sub-pattern 1004. Metadata 1052 may indicate to walker 320 a pointer 1036 to start node 1046 of single NFA 1054 and an instruction to walk single NFA 1054 in reverse walking direction 1030. Start node 1046 of single NFA 1046 is associated with last element 1034 of portion 1012. Metadata 1052 may instruct walker 320 to report a match of selected sub-pattern 1004, an offset (of offsets 428) within payload 426 of a character (of characters 430) that matches last element 1016 of selected sub-pattern 1004 at DFA node 1032 as an end offset of selected sub-pattern 1004, and a length of selected sub-pattern 1004. The walker 320 may use the length, if included in the metadata 1052 , to determine the payload start offset of the start node 1046 by subtracting the length of the selected sub-pattern 1004 in the metadata 1052 from the end offset of the selected sub-pattern.

10 , the compiler 306 may associate the NFA node 1048 associated with the first element 1014 of the portion 1012 with metadata 1050. The metadata 1050 may indicate to the walker 320 to terminate the walk and report a final match of the at least one pattern 1006, as well as an offset (of the offsets 428) within the payload 426 of the one (of the characters 430) that matched the first element 1014 of the portion 1012 at the NFA node 1048 as the starting offset of the at least one pattern 1006, if required by one of the qualifiers 308 associated with the at least one pattern 1006.

FIG11 is a block diagram 1100 of one embodiment for generating a unified DFA 312 and at least one NFA 314 based on the position of a selected sub-pattern 1104 being the end position of at least one pattern 1106 and the length of the selected sub-pattern 1104 being variable or fixed. According to the example embodiment of FIG11 , if the last element 1116 of the selected sub-pattern 1104 can be the last element of the at least one pattern 1116, the position of the selected sub-pattern 1104 is the end position of the at least one pattern 1106, and the at least one NFA 314 can be a single NFA 1154. If the length of the selected sub-pattern 1104 is fixed or variable, the portion 1112 of the at least one pattern 1106 used to generate the single NFA 1154 can be the at least one pattern 1006. The at least one walking direction can be a reverse walking direction 1130 for walking the single NFA 1154.

11 , compiler 306 may associate DFA node 1132 corresponding to last element 1116 of selected subgraph 1104 with metadata 1152. Metadata 1152 may indicate to walker 320 a pointer 1136 to a start node 1146 of a single NFA 1154 and instructions to walk single NFA 1154 in reverse walking direction 1130. Start node 1146 of single NFA 1154 may be associated with last element 1116 of selected subgraph 1104. The metadata 1152 may instruct the walker 320 to report a match of the selected sub-pattern 1104, an offset (of the offsets 428) within the payload 426 of a character (of the characters 430) that matches the last element 1116 of the selected sub-pattern 1104 at the DFA node 1132 as an ending offset of the selected sub-pattern 1104, and a length of the selected sub-pattern 1104, if the length is fixed.

11 , compiler 306 may associate NFA node 1148 associated with first element 1114 of portion 1112 with metadata 1150. Metadata 1150 may indicate to walker 320 to terminate the walk and report a final match for at least one pattern 1106. Metadata 1152 may indicate to walker 320 to report an offset (of offsets 428) within payload 426 of a character (of characters 430) that matches first element 1114 of portion 1112 at NFA node 1148 as the starting offset for at least one pattern 1106, if required by one of the qualifiers 304 associated with at least one pattern 1106.

Figure 12 is a block diagram of an example of the internal structure of a computer 1200 in which embodiments of the present invention may be implemented. Computer 1200 includes a system bus 1202, where a bus is a collection of hardware lines used to transfer data between components of a computer or processing system. System bus 1202 is essentially a shared pipe that couples the various components of a computer system (e.g., processor, disk storage, memory, input/output ports, network ports, etc.), enabling information to be transferred between these components. Serving upon system bus 1202 is an I/O device interface 1204 for coupling various input and output devices (e.g., keyboard, mouse, display, printer, amplifier, etc.) to computer 1200. A network interface 1206 allows computer 1200 to be coupled to various other devices attached to a network. Memory 1208 provides volatile storage for computer software instructions 1210 and data 1212 that may be used to implement embodiments of the present invention. Disk storage 1214 provides non-volatile storage for computer software instructions 1210 and data 1212 that may be used to implement embodiments of the present invention. Central processor unit 1218 also functions with system bus 1202 and provides for the execution of computer instructions.

A computer program product may be used to configure further example embodiments of the present invention; for example, the control device may be programmed in software for implementing an example embodiment of the present invention. Further embodiments of the present invention may include a non-transient computer-readable medium containing instructions that can be executed by a processor, and when executed, these instructions cause the processor to perform the methods described herein. It should be understood that the elements in the block diagrams and flow charts described herein may be implemented in software, hardware, firmware, or other similar implementations to be determined in the future. In addition, the elements in the block diagrams and flow charts described herein may be combined or separated in software, hardware, or firmware in any manner.

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

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

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

Claims (67)

1. A security device operatively coupled to a network, the security device comprising: At least one memory; At least one processor operatively coupled to the at least one memory, the at least one processor being configured to: The unified DFA is generated by traversing multiple nodes of a unified deterministic finite automaton (DFA) stored in at least one memory using multiple characters from a payload, allowing the multiple characters of the payload to pass through the unified DFA, and by generating the unified DFA from multiple sub-patterns selected from each pattern in a set of one or more regular expression patterns based on at least one heuristic method; and By traversing multiple nodes of at least one nondeterministic finite automaton (NFA) stored in at least one memory with multiple characters from the payload, the multiple characters of the payload are made to walk through the at least one NFA. The at least one NFA generated for at least one pattern in the set, a portion of the at least one pattern used to generate the at least one NFA, and at least one walking direction used to make the multiple characters walk through the at least one NFA are based on the following: whether the length of a sub-pattern selected from the at least one pattern is fixed or variable, and a position of the selected sub-pattern within the at least one pattern. 2. The security device of claim 1, wherein the at least one processor is further configured to report a match of the at least one pattern in the payload based on an NFA node associated with metadata indicating a final match of the at least one pattern, traversing the at least one NFA. 3. The security device of claim 1, wherein the at least one processor is configured to: Associate a transaction identifier for a given walk of the DFA with at least one NFA for matching at least one pattern in the payload; and Report a single match of at least one pattern in the payload based on the following: Traverse a DFA node of the unified DFA that has metadata indicating a partial match of the DFA for at least one pattern; Subsequently, at least one NFA node with metadata indicating a partial NFA match of the at least one pattern is traversed; and This associates the current traversal and subsequent traversals with the transaction identifier. 4. The security device of claim 1, wherein the at least one processor is further configured to report an offset of a character in the payload that matches a first element of the at least one pattern as a starting offset of the at least one pattern in the payload based on the following: Metadata associated with an NFA node of the at least one NFA and indicating a final match of the at least one pattern in the payload; and The at least one processor determines the starting offset based on subtracting the length from the sub-pattern ending offset. This is associated with a DFA node of the unified DFA and indicates at the DFA node (i) a length of the sub-pattern selected for the at least one pattern, and (ii) metadata of a sub-pattern end offset of a sub-pattern character in the payload that matches a last element of the sub-pattern selected for the at least one pattern. 5. The security apparatus of claim 1, wherein the at least one processor is further configured to: based on the correlation between the partial matching results indicated by the metadata associated with the plurality of nodes of the unified DFA and the at least one NFA of the at least one pattern, at an NFA node of the at least one NFA, report an offset of a character in the payload that matches a first element of the at least one pattern as a starting offset of the at least one pattern in the payload. 6. The security apparatus of claim 1, wherein the at least one processor is further configured to: at the NFA node, based on metadata associated with the NFA node and a final match determined for the at least one pattern in the payload, report at the NFA node an offset of a character in the payload that matches a first element of the at least one pattern as a starting offset of the at least one pattern in the payload. 7. The security device of claim 1, wherein the at least one heuristic method comprises maximizing the number of selected unique subpatterns and the length of each selected subpattern, the length of each selected subpattern having at least a minimum threshold length. 8. The safety device of claim 1, wherein if a first element of the selected sub-pattern is a first element of the at least one pattern and the length of the selected sub-pattern is fixed, the position of the selected sub-pattern is a starting position of the at least one pattern, the portion of the at least one pattern used to generate the at least one NFA excludes the at least one pattern of the selected sub-pattern, the at least one NFA is a single NFA, and the at least one traveling direction of the at least one NFA is a forward traveling direction. 9. The safety device of claim 8, wherein the unified DFA comprises: A DFA node is associated with the last element of the selected subpattern and metadata indicating to the at least one processor the following: a pointer to a start node of the at least one NFA; an instruction to turn and walk the at least one NFA in a forward walking direction; the start node of the at least one NFA being associated with a first element of the at least one pattern used to generate the at least one NFA; an offset of a payload start offset of the at least one NFA being associated with an offset of a byte following another byte at the end offset of the selected subpattern; a reported match of the selected subpattern; a leading offset within the payload of a leading character at the DFA node that matches the last element of the selected subpattern as the end offset of the selected subpattern; and a length of the selected subpattern. 10. The safety device of claim 8, wherein the at least one NFA comprises: An NFA node is associated with metadata indicating to the at least one processor the following: an instruction, and a report: terminating the walk, the NFA node being associated with a hysteresis offset within the payload of a hysteresis character matched at the at least one pattern as an end offset of the at least one pattern, and a final match of the at least one pattern. 11. The safety device of claim 1, wherein if a first element of the selected sub-pattern is not a first element of the at least one pattern, and a last element of the selected sub-pattern is not a last element of the at least one pattern, the position of the selected sub-pattern is an intermediate position of the at least one pattern, and if the length of the selected sub-pattern is fixed: The portion of the at least one pattern used to generate the at least one NFA includes a lag portion and a leading portion of the at least one pattern, wherein the lag portion of the at least one pattern excludes the selected sub-pattern and the leading portion of the at least one pattern, and the leading portion of the at least one pattern excludes the selected sub-pattern and the lag portion of the at least one pattern; and The at least one NFA includes a hysteresis NFA and a leading NFA, the at least one walking direction includes a forward walking direction and a reverse walking direction, the hysteresis NFA has the forward walking direction, the leading NFA has the reverse walking direction, the hysteresis portion of the at least one pattern is used to generate the hysteresis NFA, and the leading portion of the at least one pattern is used to generate the leading NFA. 12. The safety device of claim 11, wherein the unified DFA comprises: A DFA node, associated with the last element of the selected subpattern, is associated with metadata indicating to the at least one processor the following: a pointer to a start node of the lag NFA; an instruction to convert to walking the lag NFA in the forward walking direction, the start node of the lag NFA being associated with a first element of the lag portion; a pointer to a start node of the leading NFA; an instruction to convert to walking the leading NFA in the reverse walking direction, the start node of the leading NFA being associated with a last element of the leading portion, and to report an offset within the payload of a character matching the last element of the selected subpattern at the DFA node as an end offset of the selected subpattern, a match of the selected subpattern, and a length of the selected subpattern. 13. The safety device of claim 11, wherein the at least one NFA comprises: A lag node of the lag NFA, associated with the last element of the at least one pattern, is associated with metadata instructing the at least one processor to: terminate walking the lag NFA and report a lag offset within the payload of a lag character of the payload that matches the last element at the lag node, and a match of the lag portion of the at least one pattern; and A leading node of the leading NFA, associated with the first element of the at least one pattern, is associated with metadata indicating to the at least one processor the following: an instruction to terminate walking the leading NFA and reporting a match of the leading portion of the at least one pattern, and a leading offset within the payload of a leading character of the payload that matches the first element at the leading node as a starting offset of the at least one pattern, if a qualifier associated with the at least one pattern is required. 14. The safety device of claim 1, wherein if a first element of the selected sub-pattern is not a first element of the at least one pattern, and a last element of the selected sub-pattern is not a last element of the at least one pattern, the position of the selected sub-pattern is an intermediate position of the at least one pattern, and if the first element of the selected sub-pattern is the first element of the at least one pattern, the position of the selected sub-pattern is a start position of the at least one pattern, and if the length of the sub-pattern is fixed or variable: The portion of the at least one pattern used to generate the at least one NFA includes a lag portion and a whole portion of the at least one pattern. The lag portion of the at least one pattern is the at least one pattern excluding a leading portion of the at least one pattern. The leading portion includes the first element of the at least one pattern, the last element of the selected sub-pattern, and all elements of the at least one pattern therebetween. The whole portion of the at least one pattern is the at least one pattern. If the position of the selected sub-pattern is the start position, the leading portion is the selected sub-pattern. The at least one NFA includes a hysteresis NFA and an umbrella-shaped NFA, the at least one walking direction includes a forward walking direction and a reverse walking direction, the hysteresis NFA has the forward walking direction, the umbrella-shaped NFA has the reverse walking direction, the hysteresis portion of the at least one pattern is used to generate the hysteresis NFA, and the entire portion of the at least one pattern is used to generate the umbrella-shaped NFA. 15. The safety device of claim 14, wherein the unified DFA comprises: A DFA node, associated with the last element of the selected subpattern, is associated with metadata indicating to the at least one processor the following: a pointer to a start node of the hysteresis NFA; an instruction to transition to walking the hysteresis NFA in the forward walking direction, the start node of the hysteresis NFA being associated with a first element of the hysteresis portion; reporting a match of the selected subpattern; an offset within the payload of a character matching the last element of the selected subpattern at the DFA node as an end offset of the selected subpattern; and a length of the selected subpattern, if the length is fixed. 16. The safety device of claim 14, wherein the at least one NFA comprises: A lag node, associated with the last element of the at least one pattern, is associated with metadata indicating to the at least one processor the following: a pointer to a starting node of the umbrella-shaped NFA; an instruction to transition to walking the umbrella-shaped NFA in the reverse walking direction, the starting node of the umbrella-shaped NFA being associated with the last element of the at least one pattern; and optionally reporting an offset within the payload of a character matching the last element of the at least one pattern at the lag node; and optionally reporting a match of the lag portion of the at least one pattern; and An umbrella node of the umbrella NFA, associated with the first element of the at least one pattern, is associated with metadata indicating to the at least one processor the following: an instruction to terminate the walk and report a final match of the at least one pattern, and a starting offset within the payload of a starting character that matches the first element of the at least one pattern at the umbrella node as a starting offset of the at least one pattern, if a qualifier associated with the at least one pattern is required. 17. The safety device of claim 1, wherein if a first element of the selected sub-pattern is not a first element of the at least one pattern, and a last element of the selected sub-pattern is not a last element of the at least one pattern, the position of the selected sub-pattern is an intermediate position of the at least one pattern, and if the first element of the selected sub-pattern is the first element of the at least one pattern, the position of the selected sub-pattern is a start position of the at least one pattern, and if the length of the sub-pattern is fixed or variable: The portion of the at least one pattern used to generate the at least one NFA includes a lag portion and a leading portion of the at least one pattern. The lag portion of the at least one pattern is the at least one pattern excluding the leading portion of the at least one pattern. The leading portion includes the first element of the at least one pattern, the last element of the selected sub-pattern, and all elements of the at least one pattern therebetween. If the position of the selected sub-pattern is the start position, the lag portion is the selected sub-pattern. The at least one NFA includes a hysteresis NFA and a leading NFA, the at least one walking direction includes a forward walking direction and a reverse walking direction, the hysteresis NFA has the forward walking direction, the leading NFA has the reverse walking direction, the hysteresis portion of the at least one pattern is used to generate the hysteresis NFA, and the leading portion of the at least one pattern is used to generate the leading NFA. 18. The safety device of claim 17, wherein the unified DFA comprises: A DFA node, associated with the last element of the selected subpattern, is associated with metadata indicating to the at least one processor the following: a pointer to a start node of the lag NFA; an instruction to transition to walking the lag NFA in the forward walking direction, the start node of the lag NFA being associated with a first element of the lag portion; a pointer to a start node of the leading NFA; an instruction to transition to walking the leading NFA in the reverse walking direction, the start node of the leading NFA being associated with a last element of the selected subpattern, and to report a match of the selected subpattern, and an offset within the payload of a character matching the last element of the selected subpattern at the DFA node as an end offset of the selected subpattern, and a length of the selected subpattern, if the length is fixed. 19. The safety device of claim 17, wherein the at least one NFA comprises: A lag node, associated with the last element of the at least one pattern, is associated with metadata instructing the at least one processor to: terminate walking the lag NFA and report a lag offset within the payload of a lag character matching the last element of the at least one pattern at the lag node, and report a match of the lag portion of the at least one pattern; and A leader node, associated with the first element of the at least one pattern, is associated with metadata indicating to the at least one processor the following: an instruction to terminate walking the leader NFA and to report a match of the leader portion, and a leader offset within the payload of a leader character that matches the first element of the at least one pattern at the leader node. 20. The safety device of claim 1, wherein if a first element of the selected sub-pattern is not a first element of the at least one pattern, and a last element of the selected sub-pattern is not a last element of the at least one pattern, the position of the selected sub-pattern is an intermediate position of the at least one pattern, and if the length of the selected sub-pattern is fixed or variable: The at least one NFA is a single NFA, and the at least one walking direction includes a forward walking direction for multiple runtime processing nodes associated with multiple elements of a lag portion of the at least one pattern for the single NFA, and a reverse walking direction for multiple runtime processing nodes associated with all elements of the at least one pattern for the single NFA, wherein the lag portion of the at least one pattern is the at least one pattern excluding a leading portion of the at least one pattern, the leading portion including the first element of the at least one pattern, the last element of the selected sub-pattern, and all elements of the at least one pattern therebetween. 21. The safety device of claim 20, wherein the unified DFA comprises: A DFA node, associated with the last element of the selected sub-pattern, is associated with metadata indicating to the at least one processor the following: a pointer to a start node of the single NFA; an instruction to transition to walking the single NFA in the forward walking direction, the start node being associated with the next element in the at least one pattern immediately following the last element of the selected sub-pattern; and reporting a match of the selected sub-pattern, an offset within the payload of a character matching the last element of the selected sub-pattern at the DFA node as an end offset of the selected sub-pattern; and a length of the selected sub-pattern, if the length is fixed. 22. The safety device of claim 20, wherein the at least one NFA comprises: A lag node, associated with a last element of the at least one pattern, is associated with metadata instructing the at least one processor to: translate a single NFA into a payload start offset associated with the end offset of the selected sub-pattern and traverse the reverse traversal direction; and A leading node, associated with the first element of the at least one pattern, is associated with metadata indicating to the at least one processor the following: an instruction to terminate the walk and to report an offset within the payload of a character that matches the first element of the at least one pattern at the leading node as a starting offset of the at least one pattern, if a qualifier associated with the at least one pattern is required, and a final match of the at least one pattern. 23. The safety device of claim 1, wherein if a first element of the selected sub-pattern is not a first element of the at least one pattern, and a last element of the selected sub-pattern is not a last element of the at least one pattern, the position of the selected sub-pattern is an intermediate position of the at least one pattern, and if the length of the selected sub-pattern is fixed: The at least one NFA is a single NFA, and the at least one walking direction includes a reverse walking direction for a plurality of runtime processing nodes associated with a leading portion of the single NFA and the at least one pattern, and a forward walking direction for a plurality of runtime processing nodes associated with all elements of the single NFA and the at least one pattern, the leading portion being the at least one pattern excluding a lagging portion of the at least one pattern, the lagging portion including the first element of the selected sub-pattern, the last element of the at least one pattern, and all elements of the at least one pattern therebetween. 24. The safety device of claim 23, wherein the unified DFA comprises: A DFA node, associated with the last element of the selected subpattern, is associated with metadata indicating to the at least one processor the following: a pointer to a start node of the single NFA; an instruction to transition to walking the single NFA in the reverse walking direction, the start node being associated with the last element of the leading portion, determining a payload start offset by subtracting a length of the selected subpattern from the end offset of the selected subpattern, and reporting a match of the selected subpattern, an offset within the payload of a character matching the last element of the selected subpattern at the DFA node as the end offset of the selected subpattern, and the length of the selected subpattern. 25. The safety device of claim 23, wherein the at least one NFA comprises: A leading node, associated with a first element of the at least one pattern, and associated with metadata indicating to the at least one processor the following: an instruction to translate the single NFA into movement in the forward walking direction; and A lag node, associated with the last element of the at least one pattern, is associated with metadata indicating to the at least one processor the following: an instruction to terminate the walk and to report an offset within the payload of a character that matches the last element of the at least one pattern at the lag node, and a last match of the at least one pattern. 26. The safety device of claim 1, wherein if the last element of the selected sub-pattern is the last element of the at least one sub-pattern, the position of the selected sub-pattern is an end position of the at least one sub-pattern, and if the length of the selected sub-pattern is fixed, the portion of the at least one pattern used to generate the at least one NFA excludes the at least one pattern of the selected sub-pattern, and the at least one walking direction is a reverse walking direction. 27. The safety device of claim 26, wherein the unified DFA comprises: A DFA node, corresponding to the last element of the selected subpattern, is associated with metadata indicating to the at least one processor the following: a pointer to a start node of the at least one NFA; an instruction to transition to walking the at least one NFA in a reverse walking direction, the start node of the at least one NFA being associated with the last element of the portion, and to report a match of the selected subpattern, and an offset within the payload of a character matching the last element of the selected subpattern at the DFA node as an end offset of the selected subpattern, and a payload start offset of the at least one NFA determined by subtracting a length of the selected subpattern from the end offset of the selected subpattern, if the length is fixed. 28. The safety device of claim 26, wherein the at least one NFA comprises: An NFA node, associated with a first element of the section, is associated with metadata indicating to the at least one processor the following: termination of the walk, and reporting a final match of the at least one pattern, and an offset within the payload of a character that matches the first element of the section at the NFA node as a starting offset of the at least one pattern, if a qualifier associated with the at least one pattern is required. 29. The safety device of claim 1, wherein if the last element of the selected sub-pattern is the last element of the at least one sub-pattern, the position of the selected sub-pattern is an end position of the at least one sub-pattern, and if the length of the selected sub-pattern is variable or fixed, the portion of the at least one pattern used to generate the at least one NFA is the at least one pattern, and the at least one walking direction is a reverse walking direction. 30. The safety device of claim 29, wherein the unified DFA comprises: A DFA node, corresponding to the last element of the selected subpattern, is associated with metadata indicating to the at least one processor the following: a pointer to a start node of the at least one NFA; an instruction to transition to walking the at least one NFA in a reverse walking direction, the start node of the at least one NFA being associated with the last element of the selected subpattern; reporting a match of the selected subpattern; an offset within the payload of a character matching the last element of the selected subpattern at the DFA node as an end offset of the selected subpattern; and a length of the selected subpattern, if the length is fixed, wherein a payload start offset of the at least one NFA is associated with the end offset of the selected subpattern. 31. The safety device of claim 29, wherein the at least one NFA comprises: An NFA node, associated with a first element of the section, is associated with metadata indicating to the at least one processor the following: termination of the walk, and reporting a final match of the at least one pattern, and an offset within the payload of a character that matches the first element of the section at the NFA node as a starting offset of the at least one pattern, if a qualifier associated with the at least one pattern is required. 32. The security device of claim 1, wherein the unified DFA and the at least one NFA are stored as a binary image including the unified DFA and the at least one NFA. 33. The security device of claim 1, wherein the at least one processor includes a DFA coprocessor and an NFA coprocessor configured as an acceleration unit to separately offload DFA and NFA runtime processing. 34. A method for using finite automata, comprising: In at least one processor operatively coupled to at least one memory in a security device operatively coupled to a network: The unified DFA is generated by traversing multiple nodes of a unified deterministic finite automaton (DFA) stored in at least one memory using multiple characters from a payload, allowing the multiple characters of the payload to pass through the unified DFA, and by generating the unified DFA from multiple sub-patterns selected from each pattern in a set of one or more regular expression patterns based on at least one heuristic method; and By traversing multiple nodes of at least one nondeterministic finite automaton (NFA) stored in at least one memory with multiple characters from the payload, the multiple characters of the payload are made to walk through the at least one NFA. The at least one NFA generated for at least one pattern in the set, a portion of the at least one pattern used to generate the at least one NFA, and at least one walking direction used to make the multiple characters walk through the at least one NFA are based on the following: whether the length of a sub-pattern selected from the at least one pattern is fixed or variable, and a position of the selected sub-pattern within the at least one pattern. 35. The method of claim 34, further comprising reporting a match of the at least one pattern in the payload based on traversing an NFA node associated with metadata indicating a final match of the at least one pattern in the at least one NFA. 36. The method of claim 34, further comprising: Associate a transaction identifier for a given walk of the DFA with at least one NFA for matching at least one pattern in the payload; and Report a single match of at least one pattern in the payload based on the following: Traverse a DFA node of the unified DFA that has metadata indicating a partial match of the DFA for at least one pattern; Subsequently, at least one NFA node with metadata indicating a partial NFA match of the at least one pattern is traversed; and This associates the current traversal and subsequent traversals with the transaction identifier. 37. The method of claim 34, further comprising reporting an offset of a character in the payload that matches a first element of the at least one pattern as a starting offset of the at least one pattern in the payload based on the following: Metadata associated with an NFA node of the at least one NFA and indicating a final match of the at least one pattern in the payload; and The at least one processor determines the starting offset based on subtracting the length from the sub-pattern ending offset. This is associated with a DFA node of the unified DFA and indicates at the DFA node (i) a length of the sub-pattern selected for the at least one pattern, and (ii) metadata of a sub-pattern end offset of a sub-pattern character in the payload that matches a last element of the sub-pattern selected for the at least one pattern. 38. The method of claim 34, further comprising: based on relating multiple partial matching results indicated in the metadata associated with multiple nodes of the unified DFA to the at least one NFA of the at least one pattern, reporting an offset of a character of the payload that matches a first element of the at least one pattern at an NFA node of the at least one NFA as a starting offset of the at least one pattern in the payload. 39. The method of claim 34, further comprising: based on the metadata associated with the NFA node and a final match determined at the NFA node for the at least one pattern in the payload, reporting an offset of a character of the payload that matches a first element of the at least one pattern at an NFA node of the at least one NFA as a starting offset of the at least one pattern in the payload. 40. The method of claim 34, wherein the at least one heuristic method comprises maximizing the number of selected unique subpatterns and the length of each selected subpattern, the length of each selected subpattern having at least a minimum threshold length. 41. The method of claim 34, wherein if a first element of the selected sub-pattern is a first element of the at least one sub-pattern and the length of the selected sub-pattern is fixed, the position of the selected sub-pattern is a start position of the at least one sub-pattern, the portion of the at least one pattern used to generate the at least one NFA excludes the at least one pattern of the selected sub-pattern, the at least one NFA is a single NFA, and the at least one walking direction of the at least one NFA is a forward walking direction. 42. The method of claim 41, further comprising: at a DFA node associated with the last element of the selected sub-pattern and metadata indicating to the at least one processor a pointer to a start node of the at least one NFA: The at least one NFA is transformed into a forward-moving traversal, wherein the starting node of the at least one NFA is associated with a first element of the portion of the at least one pattern used to generate the at least one NFA, and a payload start offset of the at least one NFA is associated with an offset of a byte following the end offset of the selected sub-pattern; and The report includes a match of the selected subpattern, a leading offset within the payload of a leading character that matches the last element of the selected subpattern at the DFA node as the end offset of the selected subpattern, and a length of the selected subpattern. 43. The method of claim 41, further comprising, at one NFA node associated with metadata of the at least one NFA: The walk is terminated when the NFA node is associated with the last element of the at least one pattern; and The report is a hysteresis offset within the payload of a hysteresis character matched at the NFA node, which is used as an end offset of the at least one pattern and a final match of the at least one pattern. 44. The method of claim 34, wherein if a first element of the selected sub-pattern is not a first element of the at least one pattern, and a last element of the selected sub-pattern is not a last element of the at least one pattern, the position of the selected sub-pattern is an intermediate position of the at least one pattern, and if the length of the selected sub-pattern is fixed: The portion of the at least one pattern used to generate the at least one NFA includes a lag portion and a leading portion of the at least one pattern, wherein the lag portion of the at least one pattern excludes the selected sub-pattern and the leading portion of the at least one pattern, and the leading portion of the at least one pattern excludes the selected sub-pattern and the lag portion of the at least one pattern; and The at least one NFA includes a hysteresis NFA and a leading NFA, the at least one walking direction includes a forward walking direction and a reverse walking direction, the hysteresis NFA has the forward walking direction, the leading NFA has the reverse walking direction, the hysteresis portion of the at least one pattern is used to generate the hysteresis NFA, and the leading portion of the at least one pattern is used to generate the leading NFA. 45. The method of claim 34, further comprising: at a DFA node associated with the last element of the selected subpattern and metadata indicating to the at least one processor a pointer to a starting node of a lagging NFA and a pointer to a starting node of a leading NFA: The movement of the unified DFA is transformed into the movement of the lagging NFA in the forward movement direction, and the starting node of the lagging NFA is associated with a first element of the lagging part. Transform the walking of the lagging NFA into walking the leading NFA in the opposite walking direction, wherein the starting node of the leading NFA is associated with a last element of the leading portion; and The report includes an offset within the payload of a character that matches the last element of the selected subpattern at the DFA node as an end offset of the selected subpattern, a match of the selected subpattern, and a length of the selected subpattern. 46. The method of claim 34, wherein the method further comprises: At a lagging node in the lagging NFA that is associated with the last element of at least one pattern and with the metadata: Terminating the walking of the delayed NFA; and Report a hysteresis offset within the payload of a hysteresis character of the payload that matches the last element at the hysteresis node, and a match of the hysteresis portion of the at least one pattern; and At a leading node of the preceding NFA that is associated with the first element of the at least one pattern and with the metadata: Terminating the walking of the leading NFA; and Report a match of the leading portion of the at least one pattern, and a leading offset within the payload of a leading character of the payload that matches the first element at the leading node as a starting offset of the at least one pattern, if a qualifier associated with the at least one pattern is required. 47. The method of claim 34, wherein if a first element of the selected sub-pattern is not a first element of the at least one pattern, and a last element of the selected sub-pattern is not a last element of the at least one pattern, the position of the selected sub-pattern is an intermediate position of the at least one pattern, and if the first element of the selected sub-pattern is the first element of the at least one pattern, the position of the selected sub-pattern is a start position of the at least one pattern, and if the length of the sub-pattern is fixed or variable: The portion of the at least one pattern used to generate the at least one NFA includes a lag portion and a whole portion of the at least one pattern. The lag portion of the at least one pattern is the at least one pattern excluding a leading portion of the at least one pattern. The leading portion includes the first element of the at least one pattern, the last element of the selected sub-pattern, and all elements of the at least one pattern therebetween. The whole portion of the at least one pattern is the at least one pattern. If the position of the selected sub-pattern is the start position, the leading portion is the selected sub-pattern. The at least one NFA includes a hysteresis NFA and an umbrella-shaped NFA, the at least one walking direction includes a forward walking direction and a reverse walking direction, the hysteresis NFA has the forward walking direction, the umbrella-shaped NFA has the reverse walking direction, the hysteresis portion of the at least one pattern is used to generate the hysteresis NFA, and the entire portion of the at least one pattern is used to generate the umbrella-shaped NFA. 48. The method of claim 47, further comprising: at a DFA node of the unified DFA associated with the last element of the selected subpattern and with metadata indicating to the at least one processor a pointer to a starting node of the lagging NFA: This transforms the movement of the unified DFA into movement of the lagging NFA in the forward movement direction, wherein the starting node of the lagging NFA is associated with a first element of the lagging portion; and Report a match of the selected subpattern, an offset within the payload of a character that matches the last element of the selected subpattern at the DFA node as an end offset of the selected subpattern, and a length of the selected subpattern, if the length is fixed. 49. The method of claim 47, wherein the method further comprises: At a lagging node associated with the last element of the at least one NFA and the metadata that indicates a pointer to a starting node of the umbrella-shaped NFA to the at least one processor: The movement of the lagging NFA is transformed into the movement of the umbrella-shaped NFA in the opposite direction, wherein the starting node of the umbrella-shaped NFA is associated with the last element of the at least one pattern; and Optionally, report an offset within the payload of a character that matches the last element of the at least one pattern at the lagging node; and Optionally, a single match of the lagging portion of the at least one pattern can be reported; and At an umbrella node of the umbrella NFA associated with the first element of the at least one pattern and associated with the metadata: Terminate the walk; and Report a final match of the at least one pattern, and a starting offset within the payload of a starting character that matches the first element of the at least one pattern at the umbrella node as a starting offset of the at least one pattern, if a qualifier associated with the at least one pattern is required. 50. The method of claim 34, wherein if a first element of the selected sub-pattern is not a first element of the at least one pattern, and a last element of the selected sub-pattern is not a last element of the at least one pattern, the position of the selected sub-pattern is an intermediate position of the at least one pattern, and if the first element of the selected sub-pattern is the first element of the at least one pattern, the position of the selected sub-pattern is a start position of the at least one pattern, and if the length of the sub-pattern is fixed or variable: The portion of the at least one pattern used to generate the at least one NFA includes a lag portion and a leading portion of the at least one pattern. The lag portion of the at least one pattern is the at least one pattern excluding the leading portion of the at least one pattern. The leading portion includes the first element of the at least one pattern, the last element of the selected sub-pattern, and all elements of the at least one pattern therebetween. If the position of the selected sub-pattern is the start position, the lag portion is the selected sub-pattern. The at least one NFA includes a hysteresis NFA and a leading NFA, the at least one walking direction includes a forward walking direction and a reverse walking direction, the hysteresis NFA has the forward walking direction, the leading NFA has the reverse walking direction, the hysteresis portion of the at least one pattern is used to generate the hysteresis NFA, and the leading portion of the at least one pattern is used to generate the leading NFA. 51. The method of claim 34, further comprising: at a DFA node associated with the last element of the selected subpattern of the unified DFA, and with metadata indicating to the at least one processor a pointer to a starting node of a lagging NFA and a pointer to a starting node of a preceding NFA: This transforms the movement of the unified DFA into movement of the lagging NFA in the forward direction, wherein the starting node of the lagging NFA is associated with a first element of the lagging portion; and This transforms the movement of the unified DFA into movement of the leading NFA in the reverse direction, where the starting node of the leading NFA is associated with the last element of the selected sub-pattern; and Report a match of the selected subpattern, an offset within the payload of a character that matches the last element of the selected subpattern at the DFA node as an end offset of the selected subpattern, and a length of the selected subpattern, if the length is fixed. 52. The method of claim 34, further comprising: At a lagging node associated with the last element of the at least one NFA and with the metadata: The method terminates the walk of the lagging NFA, and further includes reporting a hysteresis offset within the payload of a hysteresis character that matches the last element of the at least one pattern at the hysteresis node, and Report a single match of the lagging portion of at least one pattern; and At at least one leading node of the NFA associated with the first element of the at least one pattern and associated with the metadata: Terminating the walking of the leading NFA; and Report a match of the leading portion, and a leading offset within the payload of a leading character that matches the first element of the at least one pattern at the leading node. 53. The method of claim 34, wherein if a first element of the selected sub-pattern is not a first element of the at least one pattern, and a last element of the selected sub-pattern is not a last element of the at least one pattern, the position of the selected sub-pattern is an intermediate position of the at least one pattern, and if the length of the selected sub-pattern is fixed or variable: The at least one NFA is a single NFA, and the at least one walking direction includes a forward walking direction for multiple runtime processing nodes associated with multiple elements of a lag portion of the at least one pattern for the single NFA, and a reverse walking direction for multiple runtime processing nodes associated with all elements of the at least one pattern for the single NFA, wherein the lag portion of the at least one pattern is the at least one pattern excluding a leading portion of the at least one pattern, the leading portion including the first element of the at least one pattern, the last element of the selected sub-pattern, and all elements of the at least one pattern therebetween. 54. The method of claim 53, further comprising, at a DFA node associated with the last element of the selected sub-pattern of the unified DFA and with metadata indicating to the at least one processor a pointer to a start node of the single NFA: Transforming the movement of the unified DFA into the movement of the single NFA in the forward movement direction, the starting node is associated with the next element of the last element of the selected sub-pattern in the at least one pattern; and Report a match of the selected subpattern, an offset within the payload of a character that matches the last element of the selected subpattern at the DFA node as an end offset of the selected subpattern, and a length of the selected subpattern, if the length is fixed. 55. The method of claim 53, further comprising: At a lag node associated with the last element of the at least one NFA and the metadata associated with the at least one pattern: Using a payload start offset associated with the end offset of the selected subpattern, the movement of the unified DFA is transformed into the movement of the single NFA in the reverse movement direction; and At a leading node of the at least one NFA associated with the first element of the at least one pattern and associated with the metadata: Terminate the walk; and The offset within the payload of a character that matches the first element of the at least one pattern at the leading node is reported as a starting offset of the at least one pattern, if a qualifier associated with the at least one pattern is required, and a final match of the at least one pattern. 56. The method of claim 34, wherein if a first element of the selected sub-pattern is not a first element of the at least one pattern, and a last element of the selected sub-pattern is not a last element of the at least one pattern, the position of the selected sub-pattern is an intermediate position of the at least one pattern, and if the length of the selected sub-pattern is fixed: The at least one NFA is a single NFA, and the at least one walking direction includes a reverse walking direction for a plurality of runtime processing nodes associated with a leading portion of the single NFA and the at least one pattern, and a forward walking direction for a plurality of runtime processing nodes associated with all elements of the single NFA and the at least one pattern, the leading portion being the at least one pattern excluding a lagging portion of the at least one pattern, the lagging portion including the first element of the selected sub-pattern, the last element of the at least one pattern, and all elements of the at least one pattern therebetween. 57. The method of claim 56, further comprising: At a DFA node associated with the last element of the selected sub-pattern in the unified DFA, and with metadata indicating to the at least one processor a pointer to a starting node of the single NFA: The movement of the unified DFA is transformed into movement of the single NFA in the reverse movement direction, the starting node being associated with a last element of the leading portion, and a payload starting offset is determined by subtracting a length of the selected subpattern from the end offset of the selected subpattern; and The report includes a match of the selected subpattern, an offset within the payload of a character that matches the last element of the selected subpattern at the DFA node as the end offset of the selected subpattern, and the length of the selected subpattern. 58. The method of claim 56, further comprising: At a leading node of the single NFA associated with a first element of the at least one pattern and associated with metadata: The single NFA travels in the forward direction; and At a lag node associated with the last element of the at least one pattern in the single NFA, and associated with the metadata: Terminate the walk; and Report an offset within the payload of a character that matches the last element of the at least one pattern at the lagging node, and a final match of the at least one pattern. 59. The method of claim 34, wherein if the last element of the selected sub-pattern is the last element of the at least one sub-pattern, the position of the selected sub-pattern is an end position of the at least one sub-pattern, and if the length of the selected sub-pattern is fixed, the portion of the at least one pattern used to generate the at least one NFA excludes the at least one pattern of the selected sub-pattern, and the at least one walking direction is a reverse walking direction. 60. The method of claim 59, further comprising: At a DFA node corresponding to the last element of the selected sub-pattern in the unified DFA, and associated with metadata indicating a pointer to a start node of the at least one NFA to the at least one processor: Transform the movement of the unified DFA into movement of at least one NFA in the reverse movement direction, wherein the starting node of the at least one NFA is associated with a last element of the portion; and Report a match of the selected subpattern, and an offset within the payload of a character that matches the last element of the selected subpattern at the DFA node as an end offset of the selected subpattern, and a payload start offset of the at least one NFA determined by subtracting a length of the selected subpattern from the end offset of the selected subpattern, if the length is fixed. 61. The method of claim 59, further comprising: At at least one NFA node associated with a first element of that part and with metadata: Terminate the walk; and Report a final match of the at least one pattern, and an offset within the payload of a character that matches the first element of the portion at the NFA node as a starting offset of the at least one pattern, if a qualifier associated with the at least one pattern is required. 62. The method of claim 34, wherein if the last element of the selected sub-pattern is the last element of the at least one sub-pattern, the position of the selected sub-pattern is an end position of the at least one sub-pattern, and if the length of the selected sub-pattern is variable or fixed, the portion of the at least one pattern used to generate the at least one NFA is the at least one pattern, and the at least one walking direction is a reverse walking direction. 63. The method of claim 62, further comprising: At a DFA node in the unified DFA, corresponding to the last element of the selected sub-pattern, and associated with metadata indicating a pointer to a start node of the at least one NFA to the at least one processor: Transform the movement of the unified DFA into movement of at least one NFA in the reverse movement direction, wherein the starting node of the at least one NFA is associated with a last element of the selected subpattern; and The report includes a match of the selected subpattern, an offset within the payload of a character that matches the last element of the selected subpattern at the DFA node as an end offset of the selected subpattern, and a length of the selected subpattern. If the length is fixed, a payload start offset of the at least one NFA is associated with the end offset of the selected subpattern. 64. The method of claim 62, further comprising: At at least one NFA node associated with a first element of that part and with metadata: Terminate the walk; and Report a final match of the at least one pattern, and an offset within the payload of a character that matches the first element of the portion at the NFA node as a starting offset of the at least one pattern, if a qualifier associated with the at least one pattern is required. 65. The method of claim 34, wherein the unified DFA and the at least one NFA are stored as a binary image including the unified DFA and the at least one NFA. 66. The method of claim 34, wherein the at least one processor includes a DFA coprocessor and an NFA coprocessor configured as an acceleration unit to offload DFA and NFA runtime processing, respectively. 67. A non-transient computer-readable medium having a sequence of instructions stored thereon, which, when loaded and executed by a processor, causes the processor to: The unified DFA is generated by traversing multiple nodes of a unified deterministic finite automaton (DFA) stored in at least one memory using multiple characters from a payload, allowing the characters of the payload to pass through the unified DFA, and by multiple sub-patterns selected from each pattern in a set of one or more regular expression patterns based on at least one heuristic method; and By traversing multiple nodes of at least one nondeterministic finite automaton (NFA) stored in at least one memory with multiple characters from the payload, the multiple characters of the payload are made to walk through the at least one NFA. The at least one NFA generated for at least one pattern in the set, a portion of the at least one pattern used to generate the at least one NFA, and at least one walking direction used to make the multiple characters walk through the at least one NFA are based on the following: whether the length of a sub-pattern selected from the at least one pattern is fixed or variable, and a position of the selected sub-pattern within the at least one pattern.