HK1211718A1 - System and method to traverse nfa generated for regular expression patterns - Google Patents

Abstract

In one embodiment, a method of walking a non-deterministic finite automata (NFA) graph representing a pattern includes extracting a node type and an element from a node of the NFA graph. The method further includes matching a segment of a payload for the element by matching the payload for the element at least zero times, the number of times based on the node type.

Description

System and method for traversing non-deterministic finite automata (NFA) generated for regular expression patterns with high-level features

Background

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

Networking application aware systems need to process, filter and switch the range of L3 to L7 network protocol layers, e.g., 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 handling network protocol layers, networking application aware systems need to protect these protocols simultaneously through access and content based security through L4-L7 network protocol layers including firewalls, Virtual Private Networks (VPNs), Secure Sockets Layer (SSL), Intrusion Detection Systems (IDS), internet protocol security (IPSec), wire-speed anti-virus (AV) and anti-spam functions. Line speed is the data transfer rate on the physical medium of the network over which data is transmitted and received.

Network processors are available for high throughput L2 and L3 network protocol processing, i.e., performing packet processing to forward packets at wire speed. Typically, a general purpose processor is used to process L4-L7 network protocols that require more intelligent processing. While general purpose processors may perform computationally intensive tasks, there is insufficient performance for processing data so that it can be forwarded at wire speed.

Content aware networking requires inspection of the content of a data packet at "line speed". The content may be analyzed to determine if a security breach or intrusion exists. A number of patterns and rules in the form of regular expressions are applied to ensure that all security breaches or intrusions are detected. Regular expressions are compact methods for describing patterns in a value/character/letter string. The simplest pattern matched by a regular expression is a single value/character/letter or a string of values/characters/letters, e.g.,/c/or/cat/. Regular expressions also include operators and meta-characters with special meaning.

By using meta-characters, regular expressions can be used for more complex searches, such as "abc. That is, in the case of an unlimited number of characters between "abc" and "xyz", the character string "abc" is found, followed by the character string "xyz". Another example is the regular expression "abc.. xyz; ", i.e., find the string" abc ", followed by two characters, then the string" abc "and followed by the string" xyz "after an infinite number of characters.

Intrusion Detection System (IDS) applications examine the contents of all individual data packets flowing through the network and identify suspicious patterns that may indicate an attempt to break into or threaten the system. One example of a suspicious pattern may be a particular text string in a data packet that follows 100 characters by another particular text string.

Content searches are typically performed using search algorithms such as Deterministic Finite Automata (DFA) or non-deterministic finite automata (NFA) for processing regular expressions.

SUMMARY

In one embodiment, a payload segment (also referred to as a segment of the payload) is the portion of the payload that is checked for matching with the indicated element in the NFA graph node. The payload segment may be a value, character, letter, byte, or other data size. The payload segment may have any granularity (e.g., size). For example, a payload segment may be one byte, multiple bytes, less than one byte, or even any number of bits. The engine may handle the smallest granularity (e.g., one byte, or any amount of data), but it may also handle more than the smallest granularity. In one embodiment, the payload segment may be a payload byte.

In one embodiment, a method of walking a non-deterministic finite automata (NFA) graph representing a pattern may comprise: extracting a node type, a next node address, a count value, and an element from a node of the NFA graph; and matching a segment of a payload against the element by matching the payload at least zero times with the element. The number of times may be based on the node type.

In one embodiment, the node type may be at least one of: variable count, fixed count and variable count, character, case-insensitive character, character class, character string, case-insensitive character string, tagged or split.

In one embodiment, the method may further comprise pushing an entry to a run stack. The entry may indicate the node type, the address of the next node in the graph, a copy bit, an inverse bit, a payload offset bit, a match type, or a count value. Pushing the entry to the run stack may be based on the node type. Pushing the entry to the running stack may be performed if the node type is variable count, fixed-variable count, or split. The method may further comprise: popping a top entry of the run stack, loading a graph node indicated by the popped top entry, and matching the segment of the payload with the element. At one payload offset indicated in the popped top entry, the element may be indicated in the loaded graph node. Popping the top entry of the run stack is performed after a mismatch that matches the segment of the payload with the element.

In one embodiment, the method comprises: popping the top entry of the running stack, extracting graph node information stored by the popped top entry, and matching the segment of the payload with the element. At one payload offset indicated in the popped top entry, the element may be indicated in the extracted graph node. Popping the top entry of the run stack may be performed after a mismatch that matches the segment of the payload with the element.

In one embodiment, a string node type may represent a pattern of multiple values. Each value may be at least one of a byte, a letter, or a character. Matching the segment of the payload against the element associated with the string node type may include matching (e.g., in parallel) at least two values within the segment against corresponding values of a string stored as the element in the node. If the segment partially matches the element, and if the length of the payload is shorter than the length of the string of the element stored as the node, the method may include loading a next payload of the same stream of the payload and continuing to match the remaining values in the string with values in the next payload. The method may further include pushing a partial match to a save buffer to be loaded after loading the next payload. Pushing the partial match to the save buffer may include: storing a current running stack entry being processed in the save buffer, and copying at least one entry stored in the save buffer to the running stack after the next payload is loaded. If the node is read from the run stack entry, the method may further include reducing the number of segments stored in the run stack and pushing the run stack entry to the run stack if the number of segments stored in the run stack entry is greater than zero. Matching the segment of the payload with the element if the node type is a variable count leading node may include: at least one segment of the payload is fetched and matched against the element until there is no match, and if the payload is exhausted, the stack entry is pushed to the save buffer and a terminate walk value is set.

In one embodiment, matching the segment of the payload against the element having a variable count node type may include matching the element a variable number of times indicated by the node. The variable number may be at least zero, at most a finite number, or at most an infinite number. The node type may further indicate that the variable count node is a greedy node, a lazy node, a leading node, or a full match node.

In one embodiment, matching the segment of the payload to the element if the node type is a variable count lazy node may include returning the shortest match found in the payload. Matching the segment of the payload against the element if the node type is a variable count lazy node may comprise: the segment is matched to the element and if the segment matches, the next node in the graph at the next node address is loaded and if the segment does not match, a mismatch is returned. Matching the segment of the payload against the variable count lazy node may comprise: if the segments match, the stack entry is pushed to the running stack and the next node in the graph at the next node address is loaded. The stack entry may indicate the variable count lazy node and the payload offset. Matching the segment of the payload to the element if the node type is a variable count lazy node comprises: if matching the next node element to the segment is a mismatch, popping the node of the variable count lazy node's node type from the stack entry of the running stack and matching the element stored in the popped node to the payload segment. After matching the segment of the payload with the element stored in the popped node, the method may include: decrementing a count value of the variable count lazy node, pushing an updated stack entry to the running stack, and loading a next node at the next node address stored in the popped entry. If the segment of the payload continues within a next payload of the same flow as the first payload, the method further includes pushing the run stack entry to a save buffer and loading subsequent buffer entries into the run stack after loading the next payload.

In one embodiment, matching the segment of the payload to the element if the node type is a variable count greedy node or a variable count leading node comprises returning the longest match found in the payload.

In one embodiment, matching the segment of the payload with the element if the node type is a variable count greedy node may include extracting at least one segment of the payload. The method may further comprise matching the at least one segment with the element. If there is a mismatch and matching the element is less than or equal to the number of variable counts in the variable count greedy node, or there are no more segments available in the payload, the method may include: pushing a running stack entry storing the node type for the node, a payload offset for at least one segment of the payload, and the number of segments matched if the number of segments matched indicates that the element has been matched less than a maximum number of times, extracting a next node of the NFA graph indicated by the next node address, and continuing to match a next segment of the payload indicated by a position following the payload offset with a second element of the next node, wherein if there is a mismatch, popping the run stack entry from the run stack, decrementing the number of segment match counts, pushing the updated run stack entry back to the run stack, and continuing to match the next segment of the payload from the offset stored in the popped entry with the element of the next node stored at the next node address stored in the popped entry.

The method may further comprise: if a match is determined, an entry is pushed to a running stack indicating the payload offset of the segment, and if the count of the variable count greedy node is reached, the next node is loaded. The method may further comprise: if the count of the variable count greedy node is not reached, a subsequent segment of the payload is determined to match the element. The method may further comprise: if a mismatch is determined, an entry is popped from a running stack and it is determined that the segment of the payload at the payload offset indicated in the node of the popped entry matches the element indicated in the node of the popped entry.

In one embodiment, the method may further comprise: if the node type is a variable count greedy node, then the segment of the payload is matched for the element by: extracting at least one segment of the payload and matching the at least one segment with the element until there is a mismatch, wherein the at least one segment matches the element a number of times equal to the variable count in the variable count greedy node or no more segments are available in the payload, and then pushing a running stack entry if the count of the stack entry is greater than zero. The method may further comprise: if the node is read from the stack entry, the variable count of the stack entry is decremented, and if the variable count is greater than zero, a running stack entry is pushed.

In one embodiment, the method may further comprise: if the node type is a variable count leading node, matching the segment of the payload with the element by: the payload segment is continuously matched to the element until there is no match or the count of the variable count leading node indicates the maximum number of times the element has been matched, and then subsequent segments of the payload continue to be matched to the next node stored at the next node address. If the payload including the payload segment is exhausted, the method includes pushing the node, count, and payload offset to a save buffer, and after loading a next payload segment from the same stream of the payload segment, loading the node, count, and payload offset from the save buffer and continuing to match the segment of the next payload segment to the element.

In one embodiment, matching the segment of the payload to the element if the node type is a variable count full match node may include returning all matches found in the payload. Matching the segment of the payload for the element may further include, if the node type is a variable count full match node: the segment is matched to the element and if it matches, the node is pushed to the running stack and if it does not match, a mismatch is returned. The stack entry may indicate the variable count full match node and payload offset with an indication to continue matching the NFA graph. Pushing the run stack entry may include setting the copy value to false. If the segment of the payload is not available, matching the segment of the payload may include pushing the node to the save buffer and setting a stop-walk value to true.

In one embodiment, matching the segment of the payload against the element if the node type is a variable count full match node may include matching the segment against the element and, if a byte match, storing the match and indicating to continue matching the NFA graph if a match is found.

In one embodiment, matching the segment of the payload with the element if the node type is a variable count full match node comprises: the segment is matched to the element and if it matches, the node is pushed to the running stack and if it does not match, a mismatch is returned. Pushing the run stack entry includes setting the copy value to false. If the segment of the payload is not available, the method includes: matching the segment of the payload includes pushing the node to the save buffer and setting a stop walk value to true.

In one embodiment, a fixed count node type represents a pattern to be matched a fixed number of times for an element. If the length of the payload is shorter than the count of the fixed count node, the method may include loading a next payload and continuing to match the remaining values in the element with values in the next payload. The method may further include pushing a partial match to a save buffer to be loaded after loading the next payload. Pushing the partial match to the save buffer may include: at least one entry from a running stack is stored in the save buffer, and the at least one entry stored in the save buffer is copied to the running stack upon loading the next payload. The element of the fixed-count node type may be a character, a character class, or a character string. Matching the segment of the payload with the element associated with the fixed-count node type includes matching at least two values within the segment against one value of the element stored in the node. If the segment matches the element, and if the length of the payload is shorter than the count of the fixed-count node, the method includes loading a next payload of the same flow of the payload and continuing to match the remaining value in the element to the value in the next payload.

In one embodiment, the element may be at least one of a character, a character class, and a character string. The character class may represent a boolean or operation of at least one value. Each character class may be stored in memory as a mask, wherein if each possible character in the mask is part of a character class, an indicator corresponding to that character is set, and if it is not part of a character class, it is not set. The method may further include matching a segment of the payload by using the segment of the payload as an index to the mask such that if the indexed entry is set, the graphics walking engine determines that the payload segment matches the character class. Each character class may be stored in memory as a two-dimensional matrix. The two-dimensional matrix may be accessed by a first index associated with the character class and a second index associated with the character value. Matching a segment of the payload against the element if the node type is a character class may include: the two-dimensional matrix is accessed with a first index that is the character class index indicated in the element of the node and a second index that is the segment of the payload, and a match is issued if the entry is set and a mismatch is issued if the entry is not set.

In one embodiment, the method may comprise: upon a successful match, a second node of the NFA graph is loaded from the next node address extracted from the node.

In one embodiment, the count value may indicate a maximum number of matches for the element. If the node type is a fixed count, the count value may indicate the exact number of matches for the element. If the node type is a string, the count value may indicate the length of the string.

The method may further comprise: if the node type is a variable count, extracting a count value from the node, wherein the count value indicates a maximum number of matches with the element, if the node type is a fixed count, extracting a count value from the node, the count value indicating an exact number of matches with the element, if the node type is a string, extracting a count value from the node, the count value indicating a length of the string, and if the node type is a fixed-variable count, extracting two count values from the node, a first count value indicating an exact number of matches with the element and a second count value indicating a maximum number of matches with the element.

In one embodiment, the method may comprise: the segment of the payload is matched against the element associated with the marker node type by: indicating that a match is found and popping any entry in a running stack, or, if indicated in the node, continuing to walk the next node in the reverse direction at the next address indicated in the node.

In one embodiment, matching the segment of the payload with the element associated with the node type being a fixed-variable count node type may include matching the element a fixed number of times indicated by a fixed count value extracted from the node and a variable number of times indicated by a variable count value extracted from the node. The variable number may be at least zero, at most a finite number, or at most an infinite number. The fixed number of times may be an indication of one time. The fixed number of times may be zero times, such that elements of the fixed-variable count node type are matched to variable count nodes.

In one embodiment, matching the segment of the payload to the element if the node type is a fixed-variable count lazy node may comprise: the segment is matched to the element and if the segment matches, the next node in the graph at the next node address is loaded and if the segment does not match, a mismatch is returned. Matching the segment of the payload with the element if the node type is fixable-variable count lazy node may include pushing a stack entry to a running stack, the stack entry indicating the variable count lazy node and payload offset, and a next node loaded in the graph at the next node address. Matching the segment of the payload to the element if the node type is a variable count lazy node may include: pushing a stack entry to the running stack if the segments match, the stack entry indicating the variable count lazy node and a payload offset, loading a next node in the graph at the next node address, and returning a mismatch if the segments do not match.

In one embodiment, a system for walking a non-deterministic finite automata (NFA) graph representing a pattern may comprise: the NFA graph includes a determination module configured to extract a node type, a next node address, a count value, and an element from a node of the NFA graph, and a matching module configured to match a segment of a payload against the element by matching the payload to the element at least zero times, the times based on the node type.

A variable count node is a node that matches a variable number of times for an element, the number of times being bounded by a range (e.g., zero to five times). The variable-count node may have one of four characteristics: lazy, greedy, collage, or full match. The variable count lazy node is configured to find the shortest possible element match within the range. The variable count lazy or leading node is configured to find the longest possible element match within the range. The variable count full match node is configured to return all matches in the payload.

The fixed count node matches a fixed amount of times for an element. The fixed count and variable count patterns may be expressions of a variable count pattern configured to match against a range, where the range begins with a number above zero. For example, a variable count pattern that matches 10 to 20 times for an element may be expressed as a fixed count node that matches ten times for the element and then a variable count node that matches 0 to 10 times for the element. A string node is a node that matches against a string (character set) in a specific order.

A marker node is a node that indicates that a match of the pattern was found in the payload. A split node is a node that indicates a selection between two paths in the graph.

Brief description of the drawings

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

Fig. 1A and 1B are block diagrams of an example security apparatus including a network services processor.

Fig. 2A is a block diagram of a network service processor, or protocol processor, shown in fig. 1A and 1B, respectively.

FIG. 2B is a block diagram illustrating an example embodiment of an environment of the engine (e.g., network service processor) of FIG. 2A.

Fig. 3A is an illustration of an example embodiment of an NFA graph.

Fig. 3B is an illustration of an example embodiment of an NFA graph used by the present invention.

Fig. 3C is an illustration of an example embodiment of an NFA graph showing other types of counting nodes that may be used.

Fig. 4A is an exemplary embodiment of an NFA graph used by a prior art system.

Fig. 4B is a diagram illustrating an example embodiment of an NFA graph used by the present invention.

Fig. 4C is an exemplary embodiment of a conventional graph of the pattern "USPTO" using five separate nodes.

FIG. 4D illustrates an example embodiment of a graph using string nodes.

Fig. 5 is a diagram illustrating an example embodiment of an NFA graph illustrating an example embodiment of the present invention.

FIG. 6A is a block diagram illustrating an example embodiment of a compiler processing scheme.

FIG. 6B is an illustration of a compiled NFA graph produced by the pattern of FIG. 6A.

FIG. 7 is a block diagram illustrating an example embodiment of compiling a pattern.

FIG. 8 is a flow diagram illustrating an example embodiment of compiling a pattern.

FIG. 9 is a flow diagram illustrating an example embodiment of a graphical walk engine processing a node.

FIG. 10 is a block diagram illustrating an example embodiment of a graph walk engine processing nodes of an NFA graph.

Fig. 11 is a flow chart illustrating a process of walking the NFA graph used in the present invention.

FIG. 12 is a flow chart illustrating an example embodiment of processing a node.

FIG. 13 is a flowchart illustrating an example embodiment of handling a node for a character class.

FIG. 14 is a flowchart illustrating an example embodiment of a graph walk engine processing a string node.

Fig. 15A and 15B are flow diagrams illustrating example embodiments of processing a fixed-count node.

FIG. 16 is a flow diagram illustrating an example embodiment of processing a variable count node.

FIG. 17 is a flowchart illustrating an example embodiment of processing a variable count lazy node.

FIG. 18 is a flowchart illustrating an example embodiment of processing a variable count greedy node.

FIG. 19 is a flowchart illustrating an example embodiment of processing a variable count leader node.

FIG. 20 is a flowchart illustrating an example embodiment of processing a variable count full match node.

FIG. 21 is a table illustrating an example embodiment of a bitmap/mask used in a character class.

FIG. 22 is a table showing the format of character class matching nodes.

Fig. 23 is a table showing the format of a string matching node.

FIG. 24 is a table illustrating the format of fixed count matching nodes.

FIG. 25 is a table illustrating a format of variable count matching nodes.

FIG. 26 is a table illustrating the format of a character class match stack entry.

FIG. 27 is a table illustrating the format of a string matching stack entry.

FIG. 28 is a table illustrating the format of a fixed count matching stack entry.

FIG. 29 is a table illustrating a format of a variable count matching stack entry.

Detailed description of the invention

The following is a description of various example embodiments of the invention.

Us 13/303,855 application "Reverse NFA generation and Processing (Reverse NFA generation and Processing)" by Goyal et al, published as us publication No. 2013/0133064, and us 13/168,395 application "Regular Expression Processing Automaton (Regular Expression Processing)" by Goyal et al, published as us publication No. 2012/0221497, describe NFA and Expression matching concepts. The entire teachings of the above application are incorporated herein by reference.

perl-compatible regular expressions (PCREs) have become a popular standard for the convention of regular expression syntax in security and networking applications. As more applications require deep packet inspection have emerged or more threats become prevalent in the internet, the corresponding features/patterns or applications for identifying viruses/attacks have also become more complex. Feature databases have evolved from regular expression (regex) patterns with simple string patterns to with wildcard characters/ranges/character classes to advanced PCRE features. Advanced PCRE features specifically refer to features such as start offset, back reference, capture group, and assertion. Embodiments of the present invention support advanced PCRE features at line speed.

Before describing in detail exemplary embodiments of the present invention, an exemplary network security application in which the embodiments may be implemented using DFAs and NFAs is described immediately below to assist the reader in understanding the inventive features of the present invention.

Fig. 1A is a block diagram of an example security device 102 that includes a network services processor 100. The security device 102 may be a stand-alone system that can switch packets received at one ethernet port (Gig E) to another ethernet port (Gig E) and perform multiple security functions on the received packets before forwarding them. For example, the security device 102 may be used to perform security processing on packets received over a wide area network before forwarding the processed packets to a local area network.

The network service processor 100 processes the open systems interconnection network L2-L7 layer protocol encapsulated in the received packet. As is well known to those skilled in the art, the Open Systems Interconnection (OSI) reference model defines seven layers of network protocol layers (L1-7). The physical layer (L1) represents the actual interface that connects the device to the transmission medium, including electrical and physical interfaces. The data link layer (L2) performs data framing. The network layer (L3) formats the data into packets. The transport layer (L4) handles end-to-end transport. The session layer (L5) manages communication between devices, e.g., whether the communication is half-duplex or full-duplex. The presentation layer (L6) manages data formatting and presentation, such as syntax, control codes, special graphics and character sets. The application layer (L7) allows communication between multiple users, such as file transfers and e-mail.

The network service processor 100 may schedule and arrange work (packet processing operations) for upper network protocols (e.g., L4-L7) and allow processing of the upper network protocols in received packets to be executed in order to forward the packets at wire speed. By processing these protocols to forward these packets at wire speed, the network services processor does not slow down the network data transfer rate.

Network services processor 100 may include multiple ethernet media access control interfaces, with a standard Reduced Gigabit Media Independent Interface (RGMII) connected to off-chip PHYs 104a, 104 b.

The network services processor 100 may also receive data packets from an ethernet port (Gig E) through the physical interface PHY104a, 104b and perform L2-L7 network protocol processing on the received data packets and forward the processed data packets through the physical interface 104a, 104b to another hop or final destination in the network or through a peripheral component interconnect/peripheral component interconnect extended interface (PCI/PCI-X) bus 106 for further processing by the host processor. 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 anti-virus (AV).

The network services processor 100 may also include a memory controller, such as Dynamic Random Access Memory (DRAM) and double data rate synchronous dynamic random access memory (DDR SDRAM), for controlling the external local memory 108. In some embodiments, the external local memory 118 is a low latency memory.

The external local memory 118 may be used to allow fast-lookup internet services and security applications, including string matching as may be required by Intrusion Detection System (IDS) or anti-virus (AV) applications or other applications requiring string matching.

According to one embodiment of the invention, the network services processor 100 may perform pattern searching, regular expression processing, content verification, transformation, and security to speed up packet processing. Regular expression processing and pattern searching may be used to perform string matching for IDS and AV applications, as well as other applications that require string matching.

A DRAM controller in network services processor 100 may control access to an external Dynamic Random Access Memory (DRAM)108 coupled to network services processor 100. The DRAM108 may store data packets received from the PHY interfaces 104a, 104b or the PCI/PCI-X interface 106 for processing by the network services processor 100. In one embodiment, the DRAM interface supports 64 or 128 bit double data rate II synchronous dynamic random access memory (DDR II SDRAM) operating up to 800 MHz. The DRAM may also store rule data needed for DFA and NFA graph expression searches to find and pattern match.

Boot bus 110 may provide the necessary boot code that may be stored within flash memory 112 and executed by network service processor 100 when network service processor 100 is powered on or reset. Application code may also be loaded into the network services processor 100 through the boot bus 110 from a device 114 that implements the compact flash standard, or from another mass storage device that may be a disk attached through the PCI/PCI-X bus 106.

Miscellaneous I/O interfaces 116 provide auxiliary interfaces such as general purpose input/output interfaces (GPIOs), flash memory, IEEE802 two-wire management interface (MDIO), universal asynchronous receiver/transmitter (UART), and serial interfaces.

It should be appreciated that the example security apparatus 102 may alternatively include the protocol processor 101 (fig. 1B). The protocol processor 101 may comprise elements of the network services processor 100 with the addition of a content processing accelerator 107, coupled to the processor 101 through a PCI/PCI-X connection 106, and an external DRAM111 coupled to the accelerator 107. The accelerator 107 and DRAM111 may be used in a content search application so that all content search operations are performed outside the processor 101.

Fig. 2A is a block diagram of the network service processor 100 or the protocol processor 101 shown in fig. 1A and 1B, respectively. Network services processor 100, and/or protocol processor 101, provides high application performance using multiple processors (cores) 202. Network applications can be classified into data plane and control plane operations. Each of cores 202 may be dedicated to performing data plane or control plane operations. The data plane operations may include packet operations to forward packets. The control plane operations may include processing portions of complex higher layer protocols, such as internet protocol security (IPSec), Transmission Control Protocol (TCP), and Secure Sockets Layer (SSL). The data plane operations may include processing other portions of these complex higher layer protocols.

The data packet may be received by either of interface units 210a, 210b over the SPI-4.2 or RGM II interface. PCI interface 224 may also receive data packets. The interface units 210a, 210b process the L2 network protocol, which preprocesses the received data packets as follows: fields in the L2 network protocol header included in the received packet are examined. After the interface units 210a, 210b have performed the L2 network protocol processing, the packet is forwarded to the packet input unit 214. The packet input unit 214 may perform preprocessing of the network protocol headers of L3 and L4 included in the received packet. This preprocessing includes checksum checking for Transmission Control Protocol (TCP)/User Datagram Protocol (UDP) (L3 network protocol).

The packet input unit 214 may write packet data into a buffer in the level 2 cache 212 or DRAM108 in a format convenient to higher level software executing in the at least one processor 202 for further processing of higher level network protocols. The packet input unit 214 may also support programmable buffer sizes and may allocate packet data across multiple buffers to support large packet input sizes.

A packet order/work (POW) module (unit) 228 may queue and schedule work (packet processing operations) for the processor 202. Work is defined as any task to be executed by the processor that is identified by an entry on the work queue. The task may include packet processing operations, e.g., layer L4-L7 packet processing operations for received packets to be performed on identified by work queue entries on the work queue. Each individual packet processing operation is a copy of the work that the processor has to perform on the received packet stored in memory (L2 cache 212 or DRAM 108). For example, the job may be the processing of received firewall/Virtual Private Network (VPN) packets. The processing of the firewall/VPN packet may include the following individual packet processing operations (multiple jobs): (1) defragmentation to reorder the fragmentation within the received data packet; (2) IPSec deciphering; (3) IPSec encrypting; and (4) Network Address Translation (NAT) or TCP sequence number adjustment before forwarding the packet.

Network services processor 100, and/or protocol processor 101 may also include a memory subsystem. The memory subsystem may include a level 1 data cache 204 in each processor 202, an instruction cache in each processor 202, a level 2 cache 212, a DRAM controller 216 for external DRAM memory, and an interface 230 for external local memory 118 (e.g., ddr sdram). The memory subsystem is architected to support multiple processors and is tuned to achieve the high throughput and low latency required for memory intensive content networking applications. Both the processor 202 and the I/O coprocessor device may share a level 2 cache 212 and the external DRAM memory 108 (of FIGS. 1A and 1B).

Network services processor 100 and/or protocol processor 101 may also include an off-load processor 202 to enable the network services processor to implement a high-throughput special-purpose coprocessor. These special purpose coprocessors include coprocessor 244 that performs non-deterministic finite automata (NFA) processing as described in more detail below and compression/decompression coprocessor 208 that performs compression and decompression.

Each processor 202 may be a dual-issue superscalar processor with an instruction cache 206, a level 1 data cache 204, a built-in hardware acceleration for cryptographic algorithms (cryptographic acceleration module) 200, in which local memory is accessed directly through a low latency memory bus 230. The low latency direct access path to local memory 118 bypasses L2 cache 212 and may be accessed directly from both processor (core) 202 and NFA coprocessor 244.

Before describing in further detail the operation of content search macros and pattern search for regular expression processing, other modules in the network service processor 100 will be described. In one example, after the processor 202 has processed the packet, the packet output unit (PKO)218 reads the packet data from the L2 cache or DRAM, performs L4 network protocol post-processing (e.g., generates a TCP/UDP checksum), forwards the packet through the interface units 210a, 210b, and releases the L2 cache 212 or DRAM108 location for storing the packet.

Each processor 202 is coupled to the L2 cache through a coherent memory bus 234. The coherent memory bus 234, 384 bits wide in one embodiment, is the communication channel for all memory and I/O transactions between the processor 202, the I/O bridge (IOB)232, and the level 2 cache and controller 212.

Free Pool Allocator (FPA)236 maintains a plurality of pointer pools to free memory in level 2 cache 212 and DRAM 108. A bandwidth efficient (last in, first out (LIFO)) stack is implemented for each free pointer pool. If the pool of pointers is too large to fit within Free Pool Allocator (FPA)236, Free Pool Allocator (FPA)236 builds a tree/list structure in level 2 cache 212 or DRAM108 using the free memory in the pool of pointers for storing additional pointers.

An I/O bridge (IOB)232 manages overall protocol and arbitration and provides consistent I/O partitioning. The IOB232 includes a bridge 238 and a FAU 240. The bridge 238 includes a plurality of buffer queues for storing information to be transferred between the I/O bus, the coherent memory bus, the packet input unit 214, and the packet output unit 218.

The Fetch and Add Unit (FAU)240 is a 2KB register bank that supports read, write, auto fetch and add, and auto update operations. An extract and add unit (FAU)240 may be accessed from processor 202 and packet output unit 218. The registers store highly used values and thus reduce the amount of access to these values. Registers in the FAU240 are used to maintain the length of the output queue for forwarding processed packets through the packet output unit 218.

The PCI interface controller 224 has a DMA engine that allows the processor 202 to move data asynchronously in both directions between local memory and remote (PCI) memory in the network services processor.

Typically, content aware application processing uses either Deterministic Finite Automata (DFA) or non-deterministic finite automata (NFA) to identify patterns in the content of received data packets. Both DFA and NFA are finite state machines, i.e., computational models, each of which includes a set of states, a starting state, an input letter (all possible set of symbols), and a transfer function. The calculation starts in the starting state and changes to a new state according to the transfer function.

Patterns are typically expressed using regular expressions that include basic elements, e.g., normal text characters such as A-Z, 0-9, and meta characters or other values such as ^ and | or other values. The basic element of a regular expression is the symbol (single character) to be matched. These are combined with meta-characters that allow one or more of the elements (+), alternate (|), Kleene asterisk (#), to match the elements zero or more times. In one embodiment, the meta-character may be defined by the PCRE pattern standard. The meta-characters used for concatenation are used to create multiple character matching patterns from a single character (or sub-string), while the meta-characters used for alternating (|) are used to create regular expressions that can match any of two or more sub-strings. The meta character Kleene asterisk (×) allows pattern matching any number of times, including no matching of a preceding character or class of characters or string of characters of the payload segment with a preceding character or class of characters. Combining different operators and single characters allows complex expressions to be constructed. For example, the expression (th (is | at)) will match the following string: th, this, that, thisis, thisat, thatis or thatat. When a meta character (. For example, the pattern "zzza? "may match with" zzz "payload or with payload" zzza ".

The character class structure [ say ] allows listing of the characters to be matched, e.g., gr [ ea ] y finds both grey and gray. Dashes indicate a range of characters, such as [ A-Z ] or [0-9 ]. The character class may further have a plurality of ranges, for example, [ a-zA-Z0-9] will include all letters, lower and upper case letters, and all numbers. A meta character "matches any one of the characters except for a line feed character. Further, the meta character "^" indicates each character except the following one character. For example, "[ \\ n ]" indicates each character except the "line feed" character (where "\ n" indicates line feed). Another example is "[. lamda.0-9 ]", which indicates any character other than the numbers "0" to "9".

Typically, ASCII characters are stored in 7-bit and 8-bit embodiments as binary numbers from 0-128 or 0-256, respectively. For example, a line feed (or skip) character may be represented as a number 12 in ASCII. The wrapping may then be represented in binary as "0001010" or "00001010" in 7-bit and 8-bit embodiments, respectively. However, this is not optimal for storing character classes.

The input to a DFA or NFA state machine is typically a string of (8-bit) bytes, i.e., the letter is a single byte (one character or symbol). Each byte in the input stream produces a transition from one state to another.

The states and transition functions of a DFA or NFA state machine may be represented by a graph, where each node in the graph represents a state and the arcs in the graph represent state transitions. The current state of the state machine is represented by a node identifier that selects a particular graph node.

Processing the regular expression using DFA and finding one or more patterns in the input stream of characters described by the regular expression is characterized by:

1) determined run-time performance: the next state of the DFA can be determined from the input character (or symbol) and the current state of the DFA. In other words, there is only one state transition per DFA state. In this way, the runtime performance of the DFA is considered deterministic and behavior can be predicted entirely from the inputs.

2) The smaller per-flow context (e.g., state or node pointer) needed to support matching across multiple packets: in a pattern of searching across the inputs of several packets that make up a stream, the search may stop at one packet and then resume at another packet. Typically, determining the state to resume the search requires tracking, remembering, or otherwise storing (e.g., as a state pointer or stack entry) all of the states traversed until the search stopped. However, in DFA, in order to resume the search, it is only necessary to record the state when the search was stopped. As such, DFA features a need for a smaller per-flow context to support pattern matching across multiple incoming data packets, e.g., storing state or node pointers on the order of several bytes.

3) A graph in which the number of nodes (or graph size) may grow exponentially with the size of the graph.

In contrast, processing a regular expression using NFA and finding one or more patterns described by the regular expression in an input stream of characters is characterized by:

1) non-deterministic run-time performance: given the current state of the input character (or symbol) and the NFA, there may be more than one next state of the NFA to transition to. In other words, the next state of the NFA cannot be determined uniquely from the input and current state of the NFA. As such, the runtime performance of the NFA is considered uncertain and behavior cannot be predicted from the input completely.

2) The larger per-flow context (e.g., state or node pointer) needed to support matching across multiple packets: as previously described, pattern matching across multiple incoming data packets, where the search stops at one data packet and then resumes at another data packet, requires tracking all states traversed until the search stopped. In NFA, the more inputs are matched, the greater the number of current states that need to be tracked. Thus, it can be said that NFA is characterized by the need for a larger per-flow context to support pattern matching across multiple incoming data packets as compared to DFA.

3) Where the number of nodes (or graph size) generally grows linearly with the size of the graph.

Fig. 2B is a block diagram 250 illustrating an example embodiment of an environment of an engine 252 (e.g., a network services processor, such as an NFA engine) of fig. 2A. The engine 252 is operatively coupled to read one or more instructions 253 from an instruction queue 254. Instruction queue 254 stores instructions sent by the host to be processed by engine 252. Engine 252 processes instruction 253 by reading the pointer stored therein. The pointers in the instructions 253 include a pointer to an entry of the input buffer 258 (which may be referred to as an input stack even though it does not have the LIFO properties of the stack), a pointer to the payload 262, a pointer to the match result buffer 266, a pointer to the save buffer 264 (which may be referred to as a save stack even though it does not have the LIFO properties of the stack), and a pointer to the run stack 260.

The engine 252 loads one or more entries from the pointer into the input buffer 258 (e.g., S1, S2, and/or S3). The engine then pushes one or more entries from the input buffer 258 to the run stack 260. In this example, the engine may push entries S1, S2, and S3 to the run stack 260. The engine 252 then pops the first entry on the run stack (e.g., S1) and begins processing it. In one embodiment, the running stack is a last-in-first-out (LIFO) stack. Each entry (e.g., S1, S2, and S3) from the input buffer 258 includes a payload offset and a pointer to the graph 257. The engine may then load the graphics 257 from graphics memory 256 and begin processing the graphics using the payload segments corresponding to the offsets of the payload 262.

As engine 252 processes graph 257 using the payload segments from payload 262, it may push and pop entries to run stack 260. When it is desired to save its location in the graph, engine 252 pushes the entry to run stack 260. When a graph presents multiple processing paths, engine 252 needs to save its location in the graph. Engine 252 may traverse one of these paths and, in the event of a mismatch, may return to running the node and payload indicated in the stack 260 entry to traverse the other path or paths. Separate nodes or variable count nodes in graph 257 may present such multiple paths in the graph.

In processing payload 262 and graph 257, payload 262 may run out of data before processing is complete. The payload 262 may be a packet or other packet data from a data stream (or payload stream). The stream may have multiple payloads 262 (e.g., packets), each payload 262 having an order in the stream. Each segment of payload 262 is a portion of the payload having a particular granularity, such as, but not limited to, one byte. In one embodiment, the granularity is adjustable or optional. An example of this is when the payload offset of payload 262 begins towards the end of the packet and a partial match is found before the end of the packet. To continue the work, engine 252 saves the current stack entry into save buffer 264. Thus, when the payload is exhausted, save buffer 264 stores one or more run stack entries of run stack 260. Then, when engine 252 loads a subsequent portion of payload 262 from the data stream of packets, engine 252 may load the run stack entries from save buffer 264 and push them into run stack 260 to continue the job. This loading of the save buffer entries into the run stack may also be performed by the host processor while committing the instructions to the engine for subsequent packets of the same flow.

When a match of payload 262 to graph 257 is found, unless engine 252 is configured to return all matches, it pops up and may discard all entries within run stack 260 associated with work loaded from input buffer 258 (e.g., first entry S1). Engine 252 then saves the results (e.g., match location and length) in match results 266 memory. The engine 252 may then load the next entry from the run stack that has been previously loaded from the input buffer 258 (e.g., S2). Engine 252 may then process the graphics and payload segments corresponding to that entry and continue processing additional work until run stack 260 is empty.

When a mismatch of payload 262 to graph 257 is found, the engine pops up and processes the next entry in run stack 260 associated with the work loaded from input buffer 258 (e.g., first entry S1). If no entry remains within the run stack 260 associated with the work loaded from the input buffer 258 (e.g., first order S1), the engine 252 completes the current work and loads the next entry from the run stack that has been previously loaded from the input buffer 258 (e.g., S2). Engine 252 may then process the graphics and payload segments corresponding to that entry and continue processing additional work until run stack 260 is empty.

FIG. 3A is a diagram 300 illustrating an example embodiment of an NFA graph 320 used by the system described in U.S. application 13/303,855, "Reverse NFA Generation and Processing" (published as US publication 2013/0133064), such as Goyal et al, and Goyal (Goyal) et al, US 13/168,395 application, "Regular Expression Processing Automaton" (published as US 2012/0221497). The entire teachings of the above application are incorporated herein by reference. The NFA graph 320 is configured to match the pattern "ab {0,5} x". "b {0,5 }" matches anywhere from zero to five times for 'b' in the pattern. Thus, the pattern matches the following payloads: ax, abx, abbx, abbbx, abbbbx, or abbbbx.

NFA graph 320 begins with node N0302. After node N0302 is loaded, the graph walk engine is configured to determine if the first segment (e.g., byte) of the payload matches 'a'. If there is a match, the graph walk engine loads node N1304 and the next segment of the payload, and if there is no match, the graph walk engine returns a no match.

After loading node N1304, if the next segment of the payload is 'x', the graph walk engine loads node N7316 as a labeled node. The marker node indicates that a match was found within the payload, causing the graph walk engine to return a match. If the next segment of the payload is 'b', the graph walk engine loads node N2306. If the next segment of the payload is anything other than 'x' or 'b', the graphics walking engine determines that there is no match in the payload and returns a mismatch.

After loading node N2306, if the next segment of the payload is 'x', the graph walk engine loads node N7316 as a labeled node. The marker node indicates that a match was found within the payload, causing the graph walk engine to return a match. If the next segment of the payload is 'b', the graph walk engine loads node N3308. If the next segment of the payload is anything other than 'x' or 'b', the graphics walking engine determines that there is no match in the payload and returns a mismatch.

After loading node N3308, if the next segment of the payload is 'x', the graph walk engine loads node N7316 as a labeled node. The marker node indicates that a match was found within the payload, causing the graph walk engine to return a match. If the next segment of the payload is 'b', the graph walk engine loads node N4310. If the next segment of the payload is anything other than 'x' or 'b', the graphics walking engine determines that there is no match in the payload and returns a mismatch.

After node N4310 is loaded, if the next segment of the payload is 'x', the graph walk engine loads node N7316 as a labeled node. The marker node indicates that a match was found within the payload, causing the graph walk engine to return a match. If the next segment of the payload is 'b', the graph walk engine loads node N5312. If the next segment of the payload is anything other than 'x' or 'b', the graphics walking engine determines that there is no match in the payload and returns a mismatch.

After node N5312 is loaded, if the next segment of the payload is 'x', the graph walk engine loads node N7316 as a labeled node. The marker node indicates that a match was found within the payload, causing the graph walk engine to return a match. If the next segment of the payload is 'b', the graph walk engine loads node N6314. If the next segment of the payload is anything other than 'x' or 'b', the graphics walking engine determines that there is no match in the payload and returns a mismatch.

After loading node N6314, if the next segment of the payload is 'x', the graph walk engine loads node N7316 as a labeled node. The marker node indicates that a match was found within the payload, causing the graph walk engine to return a match. If the next segment of the payload is anything but 'x', the graphics walk engine determines that there is no match in the payload and returns a mismatch.

Fig. 3B is an illustration of an example embodiment of an NFA graph 370 used in the present invention. The NFA graph 370 is configured to match the same pattern "ab {0,5} x" as in fig. 3A. As described above, "b {0,5 }" matches anywhere from zero to five times for 'b' in the pattern. Thus, the pattern matches the following payload: ax, abx, abbx, abbbx, abbbbx, or abbbbx.

Node N0352 is a character node configured for matching against element 'a'. Node N1354 is a variable count node configured to match anywhere from '0' and '5' times for element 'b'. The variable count node may be configured to match an element any number of times, including an infinite number of times. Node N2356 is a character node configured for matching against element 'x'. Node N3358 is a marker node configured to indicate the end of the pattern and signal that a match has been found in the payload.

The graph walk engine loads node N0352 from NFA graph 370. The graphics walking engine then processes the first segment of the payload. If the payload segment is 'a', the graph walk engine loads node N1354. Otherwise, the graphical walk engine returns a mismatch.

When node N1354 is loaded, the graph walk engine interprets the node as a variable count node that matches from 0 to 5 times for the character class 'b'. From this node, the graph walk engine is configured to match against such patterns in the payload, and then load the next node (node N2356). Node N2356 then determines if the next segment of the payload is 'x'. If so, the graph walk engine loads node 3358 (marker node) indicating the pattern is a match. If not, the graphical walk engine returns a mismatch. Specific details of the graph walk engine walking through variable count nodes using the run stack are described below.

NFA graph 370 identifies the same pattern as NFA graph 320 of fig. 3A, however, with fewer nodes to do so. Thus, NFA graph 370 uses less memory and has reduced complexity.

Fig. 3C is a diagram 380 illustrating an example embodiment of an NFA graph 390 showing other types of counting nodes. Instead of using a range, the fixed-count node searches the payload segment for an element a fixed number of times. For example, the pattern "ab {5} x" matches the payload "abbbbx", but does not match "ax", "abx", "abbx", "abbbx", or "abbbbbx". Likewise, a variable count match pattern starting with a range other than zero may be converted to a fixed count pattern and then to a variable count pattern. For example, "ab {5,10} x" may also be expressed as "ab {5} b {0,5} x". This equivalent pattern is shown by NFA graph 390 in fig. 3C. As described above, this generates node N0382 for matching "a", node N1384 for matching "b" five times, variable count node N2386 for matching "b" from zero to five times, node N3388 for matching "x", and marker node N4389 for indicating that a match was found.

As an example embodiment of the present invention, each node stores one element, where the element is either a separate value/character/letter, a character class ID (e.g., a character class index), or a string. Each node further stores its node type and any other information required by the node type, e.g. a variable count node stores the maximum (and optionally minimum) number of matches for each element and whether it is a lazy/greedy/leadership full match type node, a fixed count node stores the number of matches for each element.

Fig. 4A is an exemplary embodiment of an NFA graph 440 used by a prior art system. The NFA graph 440 is configured to match a "[ aA ] [ bB ]" pattern, which matches payloads including "aB", "aB", "Ab", and "AB".

The graph walk engine first processes node N0402. If the payload is "a," the graphics walk engine loads node N1404. The graphics walk engine then processes the next segment of the payload. If the payload is "b", the graph walk engine loads node N3408, which is a marked node. If the payload is "B", the graph walk engine loads node N4410, which is also a marker node. The two marker nodes instruct the graph walk engine to return a match.

On the other hand, if the graphics walk engine processes the payload for "a" when processing Node N0402, then the graphics walk engine loads Node 2406. The graphics walk engine then processes the next segment of the payload. If the payload is "b", the graph walk engine loads node N5412, which is a marker node. If the payload is "B", the graph walk engine loads node N6414, which is also a marker node. The two marker nodes instruct the graph walk engine to return a match.

The NFA pattern 440 may even be increased in complexity with short patterns such as "[ aA ] [ bB ]". Even if each character class only specifies two values/characters/letters, each additional character class added to the pattern doubles the number of nodes in the graph. Further, the character class may have any number of characters indicated, the more characters, the more complexity that even further adds to the graph.

In one embodiment, each character class may be stored in a 128-bit or 256-bit bitmap. Each bit in a character class represents its corresponding ASCII value. For example, the 12 th bit in the bitmap represents a "line feed" character. If bit 12 is a 1, it means that the character class includes a "line feed" character. If bit 12 is 0, the character class does not include a "line feed" character. In the same way, each character class may store multiple ASCII values. For example, [. sup./n ] (i.e., a character class having all characters except line feed) marks all bits except the 12 th bit as "1". As another example, the character class [ a-z ] includes ASCII values of 97-122. Thus, the bitmap for the character class [ a-z ] would have bits 97-122 set to "1" and all other bits set to "0".

When the graphics walking engine matches a payload segment to a character class, it can use the ASCII value of the payload as an index to the character class. For example, when the character class is [ a-z ], assume that the graphics walk engine processes the letter "r", which has an ASCII value of 114. The graphics walking engine may access bit 114 of the character class and determine whether it is set to determine whether it matches the character class. This can be expressed in the following logical statement: "if (CharacterClass [ PayLoadASCIIValue ] ═ true), return match; else return match ", where PayLoadASCIIValue is the ASCII value of the current segment of the payload, or 114 in this case.

A given pattern may also include multiple character classes. For example, the pattern "[ a-z ] [0-9] [ ^ n ] [ a-z ]" has four character classes, but only three unique character classes (i.e., [ a-z ], [0-9], and [ ^ n ]), because [ a-z ] is a repeating character class. Therefore, the compiler first determines the number of unique character classes present in the pattern or patterns. The compiler then assigns a unique number (e.g., index or identifier) to each character class. For example, the compiler assigns [ a-z ] an index of 1, an index of 2 for [0-9], and an index of 3 for [ \\ n ]. Even if it occurs twice, the character class [ a-z ] is stored once as a bitmap and can be accessed through its index "1".

The compiler stores the character classes as a two-dimensional matrix that can be accessed as two indices of input. The first index identifies a character class and the second index identifies a value within that character class.

In the context of NFA graphics, the "element" field of each node of the node type ═ character class "contains the character class number. In addition, the "element" field of a node of the "variable count" or "fixed count" type may also be an index of a character class, such that the graphical walk engine matches a variable number of times or a fixed number of times, respectively, for the character class.

In addition, the compiler determines the character class of all patterns. For example, the compiler may receive Pattern one "[ a-z ] [0-9 ]", Pattern two "[ a-z ] [ < lambda >/n ]", and Pattern three "[ 0-9] [ A-F ]". While patterns one, two and three have six character classes in total, they have only four unique character classes. Thus, the compiler assigns index 1 to [ a-z ], index 2 to [0-9], index 3 to [ ^ n ], and index 4 to [ A-F ]. Any node of the graph may access the character class by accessing a bitmap of the character class regardless of the pattern or patterns in which it appears. This reduces the memory required to store all character classes.

During the walk, the graph walk engine uses elements stored in the nodes that indicate the character class (of the node type character class) as a first index and uses the payload segment (e.g., payload bytes) as a second index of the specific character class bitmap. This loads a specific bit of the two-dimensional matrix, where the bit loaded at the position of the two indices indicates whether the payload segment (e.g., payload byte) is within a particular character class.

Fig. 4B is a diagram 450 illustrating an example embodiment of an NFA graph 470 with dense nodes and corresponding character class matrices 472 (e.g., bit-maps) used by the present invention. The NFA graphic 470 is configured to match a pattern "[ aA ] [ bB ]", which matches a payload comprising "aB", "aB", "Ab", and "AB". In the present embodiment, NFA graph 470 utilizes character classes within the nodes of the graph to reduce the number of nodes in the graph and reduce the complexity of the graph. The compiler determines whether the pattern includes two unique character classes ([ aA ] and [ bB ]). The compiler assigns an index 0 for the character class [ aA ] and an index 1 for the character class [ bB ], and both are stored as bitmaps in a two-dimensional matrix.

The character class matrix 472 shows the presentation of the character classes [ aA ] and [ bB ] at their respective indices. Character class 0 (i.e., [ aA ]) shows an entry for setting "a" and "a", and character class 1 (i.e., [ bB ]) shows an entry for setting "B" and "B". Other graphics using the same character class may utilize those character classes, and the matrix may further include character classes different from other graphics. With respect to FIG. 21, another example of a character class matrix is shown.

FIG. 22 is a table 2200 showing the format of character class matching nodes. Table 2200 includes node type 2202, match type 2204, element 2206, next node address 2208, and count 2210. For character class matching nodes, node type 2202 indicates the character class. The match type 2204 indicates that it is not applicable (e.g., null). Element 2206 indicates a character class index for accessing a character class in the character class matrix. The next node address 2208 includes the address of the next node in the graph. The count value 2210 is not applicable to character class matching nodes.

Referring again to fig. 4B, when reading node N0452, the graphics walk engine determines whether node N0452 matches for any value/character/letter in the specified character class, which in this case is "a" or "a," and loads the first segment of the payload. The graph walking engine loads a node type of the node and an element of the node, wherein the node type indicates that the node is a character class, and the element of the node indicates that the character class has an index of 0. The graphics walking engine then uses the current segment of the payload as an index to the bitmap (e.g., load Matrix [0] [ PayloadSegmentValue ]) to determine whether the payload segment matches the character class. If the first segment of the payload is any value/character/letter in the specified character class, the graphical walk engine loads the node N1454 pointed to by the "next node address" stored in node N0452, as indicated by the value loaded from the bitmap at the location of the indices.

When reading node N1454, the graph walk engine determines whether node N1454 matches for any value/character/letter in the specified character class, which in this case is "B" or "B", and loads the next segment of the payload. The graph walking engine loads a node type of the node and an element of the node, wherein the node type indicates that the node is a character class, and the element of the node indicates that the character class has an index of 1. The graphics walking engine then uses the current segment of the payload as an index to the bitmap (e.g., load Matrix [1] [ PayloadSegmentValue ]) to determine whether the payload segment matches a character class. If the current segment of the payload is any value/character/letter in the specified character class, the graphical walk engine loads the node pointed to by the "next node address" stored in node N1454 (i.e., node N2456), as indicated by the value loaded from the bitmap at the location of these indices. When node N2456 is loaded, the graph walk engine determines whether it is a marker node based on the "node type" of node N2456. The graphics walking engine may then return a match.

The NFA graph 470 has reduced complexity and reduced size. Further, the number of values/characters/letters in each character class does not increase or decrease the size of the NFA graph 470. Further, increasing the number of different character classes in the graph linearly increases the size of the NFA graph 470, rather than increasing the number of values/characters/letters in the character classes by a multiple.

In addition to character classes, another node type is a string node, according to an example embodiment of the present invention. A string node is a node that matches for consecutive values/letters/characters.

Fig. 23 is a table 2300 illustrating the format of string matching nodes. String node table 2330 includes node type 2302, match type 2304, element 2306, next node address 2308, and count value 2310. Node type 2302 indicates "string match". Match type 2304 does not apply (e.g., null). Element 2306 indicates the address of string data 2340. The next node address 2308 includes the address of the next node in the graph. The count value 2310 indicates the length of the character string.

String data 2340 indicated by the address of the string data of element 2306 of string node 2330 includes node type 2312, match type 2314, element 2316, next node address 2318, and count value 2320. The node type 2312 indicates that it is "string data". Element 2316 indicates a character in a string. Match type 2314, next node address 2318, and count 2320 are all not applicable.

A similar variant of a string node is a string node that does not distinguish between sizes. In one example embodiment, the modifiers preceding the string may indicate case-insensitive string nodes in the pattern, such as "{ i } abc", which will match the following payloads: "Abc", "abC", "aBc", "aBC", "Abc", and "Abc". One of ordinary skill in the art will recognize that the modifier "{ i }" may be any indicated symbol or series of symbols.

To handle case-insensitive character string nodes (and case-insensitive character nodes), one of the bits of the alphabet is masked prior to the comparison. For example, the capital letters (A-Z) have ASCII values between 65-90 and 97-122. The binary representation of 'a' (e.g., 97 decimal) is 1100001, while the binary representation of 'a' (e.g., 65 decimal) is 1000001. Thus, between two binary values, only one bit is different (e.g., bit [5], if indexed from the least significant bit starting from 0). For each pair of corresponding case-insensitive alphabetical characters, the mask element is compared to a bit [5] within the payload segment (where the least significant bit of each is zero). This comparison returns a match because the values are identical except for bit [5] which represents only an uppercase change. One of ordinary skill in the art will recognize that one or more bits other than bit [5] may be used as mask bits in other character schemes, for example.

Fig. 4C is an exemplary embodiment of a conventional graph 475 using the pattern "USPTO" of five separate nodes, each node undergoing a value/character/letter check. Thus, the regular graph 475 has a first node N01476 matching for 'U', a second node N01477 matching for 'S', a third node N02478 matching for 'P', a third node N3489 matching for 'T', a third node N4480 matching for 'O', and a marker node N5481 indicating a match.

Fig. 4D illustrates an example embodiment of a graph 490 using string nodes. Node N0492 is a string node that includes a pointer to the string "USPTO". Node N0492 instructs the engine to match against the entire string "USPTO" instead of each individual letter as per fig. 4C and then load the next node.

FIG. 24 is a table 2400 illustrating the format of fixed count matching nodes. For fixed count nodes, node type 2402 indicates that the fixed count matches 2402. The match type field 2404 is not applicable to fixed-count nodes. For a fixed count matching node, element 2406 may indicate the character for which the match is made, or it may indicate the character class index for which the match is made. If the match is successful, the next node address 2408 contains the address of the next node to be processed. The count value 2410 contains a fixed number of times element matching is performed.

FIG. 25 is a table 2500 illustrating the format of variable count matching nodes. The node includes a node type 2502 indicating a variable count match. The node further includes a match type 2504 that indicates whether the variable count node is a lazy, greedy, collator, or full match node. Element 2506 may contain the character for which the match is made, or it may indicate the character class index for which the match is made. If the match is successful, the next node address 2508 includes the address of the next node to be processed. The count value 2510 includes the maximum number of times element matching is performed, which includes a special symbol for representing infinity.

Optionally, the count value 2510 may also contain a second count value for storing the maximum number of times an element must match (default to zero if no second count value is provided). This can be used to indicate range matching. Such patterns may also be represented by a combination of a fixed count node that performs element matching a minimum number of times and then a variable count node that performs matching the remaining number of times.

Fig. 5 is a diagram 500 illustrating an example embodiment of an NFA graph 510 illustrating an example embodiment of the invention. NFA graph 510 is configured to detect a graph "[ \\ n ] × [ zZ ] b {5 }", where [ \\ n ] is a character indicating any value/character/letter except a line feed character, and [ "zZ" ] is a character class representing either "Z" or "Z".

Node N0502 is a variable count node. The variable count nodes may be either lazy, greedy, collator (which is an optimized form of greedy nodes), or fully matched type nodes. When a graph is compiled from a pattern, the node type is set. The user may indicate in the pattern which matching node type the variable count node should be compiled into. Alternatively, the user may also set the compiler to default to any of the four modes, depending on the desired graphical behavior. Assume that the graphics walking engine processes the payload "yyzbbbbbbbbbzyyzbbbbb".

If node N0502 is lazy, the graph walk engine finds the shortest path possible to the next node (node N1504). That is, the graph walk engine processes the first instance of "Z" or "Z" in the payload at node N1504 rather than at node N0502, even though the node N0502 element includes finding any payload segment other than a line feed, which includes "Z" or "Z". However, if node N0502 processes the payload in such a way, it will not utilize the shortest path through the graph.

When node N0 is processed by the variable count lazy node, the graphics walk engine pushes the running stack entry for node N0 with zero payload offset to the running stack. After pushing the run stack entry, the graph walk engine fetches the next node N1504. The graphics walk engine extracts the next payload byte ('y') corresponding to zero payload offset and attempts to match it with the element character class [ zZ ] of node N1504. Since the byte does not match the character class, the graphics walk engine pops up the run stack entry. The graphics walking engine then processes the same byte with the popped stack entry containing node N0502. Byte 'y' matches the character class [ ^ n ] so it achieves matching. The graphics engine then offsets the payload by increment 1 and pushes the running stack entry containing node N0502.

After pushing the run stack entry, the graph walk engine fetches the next node N1504. The graphics walk engine extracts the next payload byte, 'y', corresponding to the 1 payload offset and attempts to match it to the element character class [ zZ ] of node N1504. Since the byte does not match the character class, the graphics walk engine pops up the run stack entry. The graphics walking engine then processes the same byte with the popped stack entry containing node N0502. Byte 'y' matches the character class [ ^ n ] so it achieves matching. The graphics walking engine offsets the payload by increment 1 and pushes the running stack entry containing node N0502.

After pushing the run stack entry, the graph walk engine fetches the next node N1504. The graphics walk engine extracts the next payload byte ('y') corresponding to the 2 payload offset and attempts to match it to the element character class [ zZ ] of node N1504. Since the byte does not match the character class, the graphics walk engine pops up the run stack entry. The graphics walking engine then processes the same byte with the popped stack entry containing node N0502. Byte 'y' matches the character class [ ^ n ] so it achieves matching. The graphics walking engine offsets the payload by increment 1 and pushes the running stack entry containing node N0502.

After pushing the run stack entry, the graph walk engine fetches the next node N1504. The graphics walk engine extracts the next payload byte ('Z') corresponding to the 3 payload offset and attempts to match it to the element character class [ zZ ] of node N1504. Since the byte matches the character class, the graph walk engine extracts the next node N2506.

The graph walk engine then loads the fixed count node N2, which is matched five times for 'b'. The graphical walk engine loads the next five segments of the payload, all of which are 'b', and the fixed count node matches its element, which is also 'b'. After the fixed count node N2506 matches, the graph walk engine then loads node N3508 as the labeled node. The marker node indicates that a match was found. Then, if the copy bit is '1', the graphics walk engine pops all entries in the running stack and discards them, in which case it discards a single entry in the running stack containing node N0502 with payload offset 3. The copy bit is a flag bit that, when reached at a marker node in the NFA graph (e.g., to find a match in the payload), can pop any running stack entry marking the copy bit (e.g., set to '1') off the running stack and discard it without further processing. If the copy bit is not marked (e.g., set to '0'), then the running stack entry is not discarded when popped, but rather is processed to attempt to find additional (e.g., for a full match node) matches.

Processing the variable count lazy nodes is described in more detail with respect to FIG. 17.

If node N0502 is greedy, the graph walk engine finds the longest path possible to the next node (node N1504). For example, the first "Z" or "Z" in the payload does not necessarily mean processing node N1504. Assume that the graphics walking engine processes the same payload of "yyzbbbbbbbzyyzbbb". While the lazy node N0502 returns "yyzbbbb" as a match, the greedy node N0502 returns "yyzbbbbbbbbbbbyzyzbbbb". In other words, node N0502 ignores the first possible match and continues to match the payload to find the longest possible match. Matching the payload in such a manner requires the graphics walking engine to save its steps, for example, by pushing the nodes and offsets of the payload location to the running stack. Thus, if the graphics walking engine reaches the end of the payload without finding a match, it can pop nodes off the running stack to backtrack to match a possible match earlier.

In an example embodiment of the invention, in processing the greedy or leading node N0502, the graphics walking engine loads bytes of the payload and matches them against the element until it finds a non-match or it runs out of payload. Because the character class is [ < lambda >/n ], which covers all values/characters/letters in the payload, the graphics walking engine runs out of the payload. The graph walk engine then pushes the node to a running stack that includes the copy bit that was set, the payload offset, and a count that indicates the number of bytes consumed when matching the element indicated within the variable count node (i.e., in this case, the count is 19). The graph walk engine then loads the character class node N1504, but it returns a non-match since there are no bytes from the payload to consume.

The graphics walk engine then pops the variable count node off the running stack and decrements the count by 1. The graph walk engine then pushes the node to a running stack that includes the copy bit set, the payload offset, and a count (18) indicating the number of bytes consumed. The graph walk engine then loads the character class node N1502. The graphics walk engine attempts to consume the 19 th byte in the payload, which is 'b', but this does not match the character class [ zZ ] of node N1504. The graphics walk engine then pops up the run stack entry again. This is repeated until the count is reduced to the number of bytes consumed by node N1504, which is when the count is 13, which is a match. When the count is 13, the variable-count node effectively consumes "yyZbbbbbzyyy". Node N1504 then attempts to consume the 14 th byte, which is "Z", which is a match for the character class [ zZ ]. The graph walk engine then loads node N2506. Node N2 consumes the next 5 "b" s in the payload. The graph walk engine then loads node N3508, which is a tagged node indicating that a match was found. After processing marker node N3508, the graphics walk engine pops up and discards all running stack entries with the copy bit set to 1, and in this case there is only one such entry in the running stack. Thus, the greedy node finds the longest match in the payload. The set/unset copy bit is to separate the (marked) running stack entry pushed by the engine during runtime from the initial input buffer entry also present in the running stack, however, this may also be accomplished in other ways. Processing the variable count greedy node is described in more detail with respect to FIG. 18.

If node N0502 is leading, the graph walk engine finds the longest path possible to the next node (node N1504). For the leading nodes, the graph walk engine produces the same results for the greedy nodes described above, but performs the following more optimized process: as described in more detail with respect to fig. 19, no trace back occurs when the end of the payload is reached.

If node N0502 is a variable count full match node, the graph walk engine finds all possible paths to the next node (node N1504). The graph walk engine may return multiple matches for a variable count full match node. Processing the variable count full match nodes is described in more detail with respect to FIG. 20.

FIG. 6A is a block diagram 600 illustrating an example embodiment of a compiler 604 processing a pattern 602. In this example, the pattern 602 is "ACMEa b {5,10} c {5} [ def ]". The pattern 602 includes pattern segments 620, 622, 624, 626, and 628 that may be divided into a string node (e.g., "ACME"), a variable count node (e.g., "a"), a fixed count and a variable count node (e.g., "b {5,10 }", which may be converted to "b {5} b {0,5 }"), a fixed count node (e.g., c {5}), and a character class (e.g., [ def ]), respectively.

Compiler 604 includes a string detection module 610, a variable count detection module 612, a fixed count detection module 614, a fixed count and variable count detection module 616, and a character class detection module 618. Each module 610, 612, 614, 616, and 618 receives the pattern 602, or a corresponding pattern segment 620, 622, 624, 626, and 628 therein, and generates nodes 630, 632, 634, 636a-b, 638 based on the pattern for a compiled NFA graph 640 assembled by the graph assembly module 606.

In another embodiment, compiler 604 performs element and element type checks on pattern 602 instead of individual module checks to match for each element and node type.

FIG. 6B is an illustration 601 of a compiled NFA graph 640 produced by the pattern 602 of FIG. 6A. The NFA graph 640 is compiled starting with a string node 650 that matches against the string "ACME". The graph 640 then has a next variable count node 652 configured to match an infinite number of times against the element "a". Variable-count nodes may be either lazy, greedy, collared, or all. Based on the syntax of the pattern, the node may be set to lazy, greedy, collared, or full match type. For example, if a meta character is followed by a second meta character "? ", as in the pattern"? "," +? ","? Is there a "or" { n, m }? ", the compiler may create a matching type lazy variable count node. If a meta character is followed by a second meta character "+", such as the patterns "+", "? Plus "and" { n, m } + ", the compiler may create a matching type leader node. For example, if a meta-character is followed by a second meta-character ", such as a pattern" + ","? And "{ n, m }", the compiler may create matching type fully variable count nodes.

For example, consider the payload "abbbbbb". For the "ab" pattern, greedy matching type variable count nodes are generated. The result is that the node consumes the entire payload, making the result "abbbbbb".

Similarly, for an "ab +" pattern, a leadership match type variable count node is created. The leading node has similar characteristics as the greedy node and is then configured to not backtrack when the end of the payload is reached. Again, the result is that the variable count leader node consumes the entire payload here and does not go back, making the result "abbbbbb", which is exactly the same as a greedy node.

For "ab? "Pattern, create lazy matching type variable count node. As a result, the variable count node consumes the shortest possible match, which is "a".

For "ab x" patterns, full-match type variable-count nodes are created. As a result, all possible matches are found, so that "a", "ab", "abb", "abbb", "abbbb", "abbbbbb", and "abbbbbb" are found.

In other embodiments, various symbols may be used to indicate the type of match, for example, by designating a special character as a prefix or suffix of a pattern. In other embodiments, the settings of the compiler generating the graph 640 may set the matching type of the node.

Graph 640 then has a fixed count node 654a and a variable count node 654b, which are based on "b {5,10 }" pattern segments logically divided into b {5} and "b {0,5 }". The fixed count node 654a matches five times for "b". Variable count node 654b matches anywhere from zero to five times for "b". The graph 640 then has a fixed count node 656 that matches five times for "c" in the payload. The character class node 658 matches for the element [ def ], which is any of the characters "d", "e", or "f".

The graph may also be matched against character classes that are part of a variable-count node or a fixed-count node. For example, the pattern "[ xyz ] {0,5 }" is compiled into a variable count node that matches from zero to five times for the character class [ xyz ]. For example, "xyzzx" is the payload that matches the pattern.

FIG. 7 is a block diagram 700 illustrating an example embodiment of compiling a pattern 702. The pattern determination module 703 performs a matching term check on the pattern 702. The matching items include element and node types. If the pattern determination module 703 finds a match, it outputs the match as an element 704 and a node type 706 to the node generation module 708. If the pattern determination module 703 does not find a match, it indicates that the pattern is over, and the pattern determination module 703 may consume another pattern or, if there are no more patterns, complete the compilation. The node generation module 708 generates dense nodes 710 that include elements 704, which may be values/characters/letters, character classes, or character strings, and node types 706, which may be values/characters/letters, character classes, variable counts, fixed counts, variable and fixed counts, character strings, or split nodes (for alternation) or labeled nodes (used as final nodes of the graph) for declaring a match.

FIG. 8 is a flow diagram 800 illustrating an example embodiment of compiling a pattern. The compilation begins with a pattern being subjected to a match check, the match including an element and a node type (802). The method then determines whether a match is found (804). If found, the method generates a node indicating the node type and element (806) if not found, the method ends (808) and optionally compiles another pattern.

FIG. 9 is a flow diagram 900 illustrating an example embodiment of a graph walk engine processing a node. The graphical walk engine extracts node types and elements from the nodes (902). As described above, the element may be a value/character/letter, a character class index, or a string value. The graph walk engine then determines if the node needs to continue matching with the same element (904). The graphical walk engine may track the number of elements it has matched against a variable count node or a fixed count node, for example, by using an index or a count variable. If the node type indicates that matching continues for the element, the graph walk engine matches the payload segment with the element (906). The graphics walking engine then determines whether the payload segment matches the element (910). If so, it is determined that the node needs to proceed with the match (904). If the node type does not indicate to proceed with matching, the graph walk engine returns a match or no match for the node (908) and is available to process the next node in the graph.

If the payload segment does not match the element (910), however, the graphics walk engine returns a mismatch (912).

FIG. 10 is a block diagram 1000 illustrating an example embodiment of a graph walk engine processing nodes 1004a-d of an NFA graph 1002. The determination module 1006 receives the NFA graph 1002 that includes nodes 1004 a-d. The NFA graph 1002 may include any number of nodes 1004 a-d. Further, in one embodiment, the determination module 1006 may receive the individual nodes 1004 a-d. The determination module 1006 outputs the node type 1008 and the element 1010 to the matching module 1011. Based on the node type 1008, the matching module 1011 matches one or more payload segments 1014 against the element 1010. The matching module 1011 may receive one or more additional segments 1014 based on the node type 1008, such as a variable count node or a fixed count node configured to match one or more payload segments. When the processing is completed, the matching module 1011 outputs a match or no match 1012. Alternatively, the matching module 1011 may request the determining module 1006 to process the next node of the NFA graph 1002. The matching module 1011 may further process earlier or later payload segments and earlier or later nodes of the NFA graph.

Fig. 11 is a flow chart 1100 illustrating a process for walking the NFA graph used in the present invention. In one embodiment, the elements performing this process may be the elements described with respect to block diagram 250 shown in FIG. 2B.

Graphics walking engine 252 includes a plurality of memories that store a run stack 260 for saving paths that step through other portions of the graphics and a save buffer/stack 264 for storing a save buffer/stack 264 when the payload is processed with only partial match completions, so that the engine can reload the stack entries from the save buffer into the run stack when the next payload of the same flow is loaded. In one embodiment, the run stack 260 or save buffer 264 may be maintained as a circular buffer in on-chip memory, and it may overflow to external system memory, although other stack implementations and memory types may be used. Also, the host may copy (move) the entry from the save buffer into the run stack (input buffer) when the next instruction is fed to the engine to process the subsequent payload of the same stream.

The run stack 260 pushes the stack entry to the head pointer and pops the stack entry off the head pointer. The save buffer/stack queues the stack entry at its tail pointer. Because the save buffer/stack 264 queues the entry at its tail pointer (e.g., LILO), it is structured as a queue. A host coupled to the processor provides at least one populated entry (e.g., input from the input buffer 258 of fig. 2) for the initial run stack. The host may also provide initial instructions (e.g., from instruction queue 254). The walk instruction contains the following stack-related information: (1) operating a stack head pointer; (2) saving a stack tail pointer; (3) the number of stack entries to run; and (4) run stack and save stack size by number of entries.

In an example embodiment of the present invention, the run stack entry includes fields indicating a node type field, a copy field, a reverse process field, a payload offset field, a type specific data field, and an address field. If the node type is a "NOP" (e.g., No operation (No-op)), the graphics walk engine discards the run stack entry and pops up the next run stack entry to be processed. If the node type is Fetch (Fetch), the run stack entry does not contain node information and the type specific data field is invalid. If the type is any type other than "NOP" or Fetch (e.g., fixed character, variable count, split node, string node, character class, character, or tag node), the run stack entry itself contains node information in the type-specific data field. The following table lists possible node types.

The copy field is used to separate the run stack entries pushed by the graphics walk engine during runtime from the initial input buffer entries that also exist in the same run stack. The reverse field indicates whether the payload should be offset by an increment or decrement after processing the current node. This allows the payload to be processed in both the forward and reverse directions. The offset field indicates the location of the payload being processed by the current node. If the node type is extract, the address field contains the starting node address. Alternatively, if the payloads match when processing the stack entry, the address field contains the address of the next node to be fetched.

Pushing the run stack entry into the run stack 260 allows the graphics walking engine to process other NFA nodes or another branch of the NFA graph while being able to return to the node recorded within the run stack 260 if no match is found in that branch.

Save buffer/stack 264 allows the graphics walking engine to save a partial match, for example, if the graphics walking engine reaches the end of the payload. After loading the subsequent payload of the same flow, the engine copies the stack entry from save buffer/stack 264 into run stack 260. In another embodiment, the host software of the host device may copy the contents of the save stack to the input stack after the next instruction is provided to the graphics walking engine. In this embodiment, since the graphics walking engine is managed by the host software, it is unaware of the packet flow or subsequent packets in the flow. FIG. 11 illustrates an example embodiment of implementing the system using a run stack and a save stack, however, other implementations may be envisioned by one of ordinary skill in the art.

The process begins with initiating a graphical walk (1102). The process then determines if the run stack (e.g., run stack 260) is empty (1104). If the run stack (e.g., run stack 260) is empty, the process returns (1122). In response to an instruction 253 from the host, a run stack (e.g., run stack 260) entry may be pushed from the input buffer 258. If the run stack (e.g., run stack 260) is not empty (e.g., has at least one entry), the graphics walk engine (e.g., engine 252) pops up the run stack (e.g., run stack 260) to load the next stack entry (1106). The run stack (e.g., run stack 260) is a last-in-first-out (LIFO) data structure, so the entry popped from the run stack (e.g., run stack 260) is the last entry pushed into the run stack (e.g., run stack 260).

The graphics walk engine then determines whether the running stack entry stores node information (1108). If so, the graphics walk engine reads node information from the popped run stack entry (1110). If not, the graphics walk engine extracts the node from the memory address indicated by the popped run stack entry (1112).

The graphical walk engine then sets the "end walk" bit (also referred to as the "done" bit) in the result to false (1114). The graph walk engine then processes the node indicated by the run stack entry (1118), as explained in more detail with respect to FIG. 12. With respect to FIG. 11, the graphical walk engine then determines whether the stop walk bit is assigned TRUE (TRUE) within the node being processed (1120). If not, the graph walk engine extracts the node indicated at the "next node address" field of the current node (1116). If so, the graphics walking engine determines if the running stack is empty (1104).

FIG. 12 is a flow diagram 1200 illustrating an example embodiment of processing a node. Flow diagram 1200 is an extension of the process 1118 performed on the node of fig. 11.

The graphics walk engine begins processing nodes (1202). The graph walk engine determines whether the graph walk engine is a dense node (1204). If it is not a dense node, the graph walk engine processes the node by a non-dense NFA node (e.g., a character node, a split node, or a marker node) (1214). The graphics walking engine then returns 1224.

If the node is a dense graph node (1204), the graph walk engine determines if the node is a character-like node (1206). If so, the graph walk engine processes the character class node (1216). Processing the character-like nodes is described in more detail with respect to FIG. 13. The graphics walking engine then returns 1224.

If the node is not a character class node (1206), the graph walk engine determines if the node is a string node (1208). If so, the graph walk engine processes the node as a string node (1218). With respect to FIG. 14, processing string nodes is described in more detail. The graphics walking engine then returns 1224.

If the node is not a string node (1208), the graph walk engine determines if the node is a fixed count node (1210). If so, it processes the fixed-count node (1220). Processing the fixed-count nodes is described in further detail with respect to FIG. 15. The graphics walking engine then returns 1224.

With respect to FIG. 12, if the node is not a fixed count node (1210), the graph walk engine determines if the node is a variable count node (1211). If so, the graph walk engine processes the node according to the variable count node (1222). Processing the variable count node is described in further detail with respect to FIG. 16. The graphics walking engine then returns 1224. If the graph walk engine determines that the node is a variable count node (1211), it returns an error code (1226).

Other embodiments of processing the node may be used by the graphical walk engine. For example, the graph walk engine may determine the type of each node by examining the node types in a different order.

FIG. 13 is a flow diagram 1300 illustrating an example embodiment of processing a node of a character class. With respect to fig. 22, the format of the character-like node is described above. With respect to FIG. 13, flow diagram 1300 is an extension of the processing of the character class node (1216) described in FIG. 12.

FIG. 26 is a table 2600 illustrating an example embodiment of a stack entry pushed in the context of handling a node type for a character class. The stack entry includes a stack entry type 2602 indicating a character class match, an element 2606 indicating an index of the character class, and a next node address 2608 indicating a next node in the graph. The stack entry further includes a copy bit 2612, a reverse bit 2614 indicating whether the graph is to be walked in reverse, and an offset bit 2616 indicating the offset of the next byte for processing in the payload. The stack entry further includes a match type 2604 and a count value 2610, both of which indicate that they are not applicable. The character class stack entry is only queued into the save buffer/stack and is not pushed to the run stack because there is no need to push it into the run stack.

With respect to FIG. 13, the graph walk engine begins processing the character class nodes (1302). The graphics walk engine loads a character class index from a character class node (e.g., element 2206 of fig. 22) and uses the character class index to read the bitmap/mask stored in the two-dimensional matrix (1304). The graphics walk engine then checks if there is at least one more byte in the payload to process (1306).

If there is at least one more byte, the graphics walk engine extracts the next byte (or other data size) from the payload (1308). The graphics walk engine uses the bytes of the payload to access the bits (or other data size) of the bitmap/mask and determine whether to set the bits (1310). If the bit is set, the graph walk engine determines that the bytes of the payload match the character class represented by the node and returns (1312). If the bit is not set (1310), the graphical walk engine sets the end walk bit in the result to true (1314) and then returns (1312). The terminate walk bit indicates that the current graph walk did not find a match and indicates that the engine should abort the current graph walk thread rather than fetch the next node of the graph.

In other aspects, if the graphics walk engine determines that there are no more payloads to process (1306), the graphics walk engine pushes the nodes to a save buffer/stack so that a match can be restored for subsequent packets of the same flow (1316). The graphical walk engine then sets the end walk bit in the result to true (1314) and then returns (1312).

FIG. 14 is a flowchart 1400 illustrating an example embodiment of a graphical walk engine processing a string node. As described above, with respect to fig. 23, the format of the character string node and the character string data are illustrated. With respect to fig. 14, flowchart 1400 is an extension of the processing of string nodes (1218) described with respect to fig. 12.

FIG. 27 is a table 2700 illustrating an example embodiment of a stack entry for a string matching type. The stack entry includes a stack entry type 2702 indicating a string match, an element 2706 indicating the address of the remaining string data, a next node address 2708 indicating the next node in the graph, and a count value 2710 indicating the remaining length of the string to be processed. The stack entry further includes a copy bit 2712 indicating whether the entry in the running stack is a copy, a reverse bit 2714 indicating whether the graph is to be walked in reverse, and an offset bit 2716 indicating the offset of the next byte for processing in the payload. The stack entry further includes a match type 2704 indicating that it is not applicable. For string match types, the stack entries are queued to the save buffer/stack because they do not need to be pushed to the run stack.

With respect to FIG. 14, the graph walk engine begins processing string nodes (1402). The graphical walk engine loads string data that includes the length of the string from the node (e.g., count 2310 of string node 2330 of fig. 23), determines the number of bytes (or other data size) available in the payload, and determines whether the number of bytes available in the payload is equal to or greater than the length of the string (1404). If so, the graphics walk engine sets the "match length" to the "string length" (1406). In another manner, the graphics walking engine sets the "match length" to the number of available payload segments (1404). The "matching length" is the number of bytes of the string to be matched to the payload. If the match length is less than the string length (1404), the match length is set to the number of available bytes so that the string can be a partial match and the match with subsequent packets can proceed.

After setting the match length (1404 or 1406), the graphics walk engine extracts a number of bytes from the payload, where the number of bytes is the match length, and also extracts a string data node (e.g., string data 2340 of fig. 23) (1408). The string data node includes the actual string elements (e.g., elements 2314 of string data 2340 of fig. 23) to be compared to the payload segment. The graphics walk engine then compares the number of extracted payload segments in parallel with the number of identical string bytes (1410). The node then determines if the "match length" byte of the payload matches all of the extracted string bytes (1412). If not, the graphical walk engine sets the end walk bit of the result to true (1418) and returns (1420). If the bytes of the payload match the bytes of the string (1412), the graphics walk engine determines if the match length is the same as the string length (1414).

If the match length and string length are the same (1414), the graphics walk engine returns (1420). If the match length and string length are not the same (1414), the graphics walk engine pushes the stack entry containing the remaining length of the string (FIG. 27) to the save buffer/stack so that the remaining "string length" bytes of the subsequent payload from the same flow can be matched with the "remaining string data" along with the information described above with respect to FIG. 27 (1416), sets the end walk bit of the result to true (1418) and returns (1420).

Fig. 15A and 15B are flowcharts 1500 and 1501 illustrating an example embodiment of processing a fixed-count node. With respect to fig. 24, the format of the fixed-count node is described above. 15A-B, flowcharts 1500 and 1501 are extensions of the process for fixed count nodes (1220) described with respect to FIG. 12.

FIG. 28 is a table 2800 illustrating an example embodiment of a stack entry of the fixed count match type. The stack entry includes a stack entry type 2802 indicating a fixed count match, an element 2806 indicating a character or character class index, a next node address 2808 indicating a next node in the graph, and a count value 2810 indicating a remaining count of bytes to be matched. The stack entry further includes a copy bit 2812 indicating whether a node in the running stack is a copy, a reverse bit 2814 indicating whether the graph is to walk in reverse, and an offset bit 2816 indicating the offset of the next byte for processing in the payload. The stack entry further includes a match type 2804 indicating that it is not applicable. For the fixed count match type, the stack entries are queued to the save buffer/stack because they do not need to be pushed to the running stack.

With respect to FIG. 15A, the graph walk engine begins processing the fixed count nodes (1502). The graph walk engine reads the "count" (e.g., count value 2410 of fig. 24) stored in the node (1504). The count stored in the node represents the number of times a character or class of characters is to be matched with the payload. For example, for a fixed node that originates from the partial pattern "b {5 }", the count is 5 because the character 'b' is to match the payload 5 times.

The graphics walk engine then determines whether there is an available byte "count" number in the payload (1506). If so, the graphics walk engine sets the match length to "count" (1510). Otherwise, the graphics walking engine sets the match length to the number of available payload segments (1508). The "matching length" is the number of bytes of the fixed count pattern to be matched with the payload. If the match length is less than the count of the fixed count node (1508), the match length is set to the number of available bytes so that the fixed count node can be a partial match and continue with the match with subsequent packets of the same flow. After setting the match length (1508 or 1510), the graphics walking engine extracts the "match length" number of bytes from the payload (1512).

The graph walk engine then determines whether the node is a fixed count character class node or a fixed count character node, for example, by reading data in element 2406 of FIG. 24, which indicates the number of characters or indices in the character class (1514). If it is a fixed count character class node (1514), the graphics walk engine reads the character class bitmap/mask using the character class index extracted from the fixed character class node (e.g., element 2406 of FIG. 24) (1516). The graphics walk engine then attempts to match the "match length" number of payload segments in parallel with the corresponding entries in the mask (1518). Character class node matching is performed in the same manner as described above in the context of character class nodes. If the node is a fixed count number character node (1514), the graph walk engine matches (1520) a "match length" number of payload segments in parallel with the element stored in the node (e.g., element 2406 of FIG. 24).

After determining whether the node is a fixed count character class node or a fixed count character node (1514) and in response to this determination (1516 and 1518 or 1520, respectively), referring to flowchart 1501 of FIG. 15B, the graph walk engine determines whether the "match length" number of bytes of the payload match the character or character class (1522). If so, the graph walk engine determines if the match length is the same as the count of the fixed count node (1524). If so, the graphics walk engine returns 1530. If not, the graphics walk engine pushes the stack entry (FIG. 28) to the save buffer/stack, matching the remaining "count" bytes of the subsequent payload from the same stream with the remaining fixed count node elements (1526), sets the end walk bit of the result to true (1528) and returns (1530).

If the "match length" number of bytes of the payload does not match a character of the character class (1522), the graphical walk engine sets the end walk bit of the result to true (1528) and returns (1530).

FIG. 16 is a flow chart 1600 illustrating an example embodiment of processing a variable count node. With respect to fig. 25, the format of the variable count node is described above. With respect to fig. 16, flowchart 1600 is an extension of the process for variable count node (1222) described with respect to fig. 12.

FIG. 29 is a flowchart 2900 illustrating an example embodiment of a stack entry for a variable count match type. The stack entry includes a stack entry type 2902 indicating a variable count match, an element 2906 indicating a character or character class index, a next node address 2908 indicating a next node in the graph, and a count value 2910 indicating the remaining count of bytes to match. The stack entry further includes a copy bit 2912 indicating whether the node in the running stack is a copy, a reverse bit 2914 indicating whether the graph is to be run in reverse, and an offset bit 2916 indicating the offset of the next byte for processing in the payload. The stack entry further includes a match type 2904 that indicates whether the node is a lazy, greedy, collator, or fully-matched node. The stack entry may be pushed and popped to the running stack, or in the event the payload is exhausted, it may be copied from the running stack to the save buffer/stack.

With respect to FIG. 16, the graph walk engine begins processing the variable count nodes (1602). The graph walk engine loads the match type 2504 of FIG. 25 and determines if the node match type is lazy (1604). If so, it processes the variable count lazy node (1614), which is explained in further detail in FIG. 17. The graphics walking engine then returns 1622.

If not, the graph walk engine determines whether the node match type is greedy (1606). If so, it processes the variable count greedy node (1616), which is explained in further detail in FIG. 18. The graphics walking engine then returns 1622.

If not, the graph walk engine determines if the node is of a leadership match type (1608). If so, it processes the variable count leader node (1618), which is explained in further detail in FIG. 19. The graphics walking engine then returns 1622.

If not, the graph walk engine determines whether the node match type is a "full" or "full match" node and processes the node according to the variable count full match node (1620), which is explained in further detail in FIG. 20. The graphics walking engine then returns 1622.

FIG. 17 is a flowchart 1700 illustrating an example embodiment of processing a variable count lazy node. The format of the variable count node is described above with respect to fig. 25, and the format of the variable count stack entry is described above with respect to fig. 29. With respect to FIG. 17, a flow diagram 1700 is an extension of the processing of the variable count lazy node (1614) described with respect to FIG. 16.

The graphical walk engine begins processing the variable count lazy nodes (1702). The graphics walking engine determines if the node is read from a running stack entry (1704). If the node is not read from a run stack entry, meaning the node was processed for the first time, the graph walk engine determines if the count (e.g., count value 2510 of FIG. 25) is greater than zero and if so, it pushes the run stack entry (FIG. 29, 2900) with its copy bit set to "1" (e.g., copy bit 2912 of FIG. 29) with all relevant information populated as explained above (1706). The graphical walk engine then returns (1724). The pushed run stack entry allows the graphics walk engine to remember its return path and continue walking to the next node at the next node address (e.g., 2508 of fig. 25). Setting the copy bit to "1" allows nodes to be popped and dropped from the running stack if a match is found when the next node path is walked. If no match is found, the nodes may be processed as they are popped from the run stack.

If the node is read 1704 from the running stack entry, the graphics walk engine determines 1708 if there is at least one more byte in the payload to process. If there are no more bytes of the payload (1708), the graphics walk engine pushes the stack entry (FIG. 29, 2900) with node information to the save buffer/stack (1710), sets the end walk bit of the result to TRUE (1712), and returns (1724). Pushing the nodes to the save buffer/stack (1710) saves the progress of the match so that when the graphics walk engine processes subsequent packets belonging to the same application stream, it can load the previous match progress from the save buffer/stack and restore the match.

If the payload is not exhausted (i.e., if there is at least one byte of the payload pending) (1708), the graph walk engine determines whether the variable count node is a character class node or a character node by examining element 2906 of FIG. 29 (1714). If the variable count node is a variable count character class node (1714), it reads the bitmap/mask using the character class index stored in element 2906 of FIG. 29 in the variable count character class node (1720). The graphics walk engine then extracts a byte from the payload and compares the byte with the corresponding entry in the bitmap/mask by using the byte from the payload as an index to the bitmap/mask (1722). If the entry is set, the graphics walk engine determines a match.

On the other hand, if the variable count node is a variable count character node (1714), the graph walk engine extracts one byte from the payload and matches it to the element 2906 stored in the node of FIG. 29 (1716).

Determining whether the node is a variable count character class node or a variable count character node (1714) and in response to the determination (1720 and 1722 or 1716, respectively), the graphics walking engine determines whether the byte matches the element (1718). If so, the graphics walk engine decrements the count (e.g., count value 2910 of FIG. 29) by 1(1705), pushes the run stack entry (e.g., 2900 of FIG. 29) with the copy bit set (e.g., copy bit 2912 of FIG. 29) if the count is greater than zero (1706), and returns (1724). If the count is equal to zero, the entry is not pushed onto the run stack. Otherwise, the graphical walk engine sets the end walk bit in the result to true (1712) and returns (1724).

FIG. 18 is a flow diagram 1800 illustrating an example embodiment of processing a variable count greedy node. The format of the variable count node is described above with respect to fig. 25, and the format of the variable count stack entry is described above with respect to fig. 29. With respect to FIG. 18, a flow diagram 1800 is an extension of the processing 1616 of the variable count greedy node described with respect to FIG. 16.

The graph walk engine begins processing variable count greedy nodes (1802). The graph walk engine determines whether the node is read from a running stack entry (1804). If so, the graphics walk engine decrements the count (e.g., count value 2910 of FIG. 29) by 1(1806) in the run stack entry. Then, if the count (e.g., count value 2910 of FIG. 29) is greater than zero, it pushes the run stack entry to the run stack with the copy bit set (1808). The graphics walking engine then returns (1818).

If the run stack entry is not read from the run stack (i.e., the node is processed for the first time) (1804), the graph walk engine determines whether the variable count node is a variable count character class node or a variable count character node by examining element 2506 of FIG. 25 (1810). If the variable count node is a variable count character class node (1810), it reads the bitmap/mask corresponding to the character class index stored in the variable count character class node by reading element 2506 of FIG. 25 (1814). The graphics walk engine then extracts one byte from the payload and compares the byte with the corresponding entry in the bitmap/mask by using the byte from the payload as an index into the bitmap/mask until there is a mismatch or no more bytes available in the payload, or the number of matched bytes equals the count value (2510 of FIG. 25) (1816). The graphics walk engine then allocates the available count (2910 of fig. 29) to be stored in the run stack entry as the number of bytes matched by the available count node (1817). Then, if the count of the run stack entry is greater than zero, the graphics walk engine sets the copy bit to the run stack entry of 1 (2900 of FIG. 29) (1808). If the running stack entry's count is equal to zero, the graphics walking engine does not push the running stack entry. The graphics walking engine then returns (1818).

If the node is a variable count number character node (1810), the graph walk engine extracts bytes from the payload and matches them with the characters stored by the node element (2506 of FIG. 25) until it fails, runs out of payload, or the number of bytes matched equals the count (2510 of FIG. 25). The graphics walk engine then allocates a count value to be stored (e.g., count value 2910 of FIG. 29) in the run stack entry as the number of bytes matched by the available count node (1817).

FIG. 19 is a flowchart 1900 illustrating an example embodiment of processing a variable count leader node. The format of the variable count node is described above with respect to fig. 25, and the format of the variable count stack entry is described above with respect to fig. 29. With respect to fig. 19, a flow diagram 1900 is an extension of the processing for the variable count leader node (1618) described with respect to fig. 16.

With respect to FIG. 19, the graph walk engine begins processing the variable count nodes (1902). The graph walk engine determines if the node is a variable count character class node or a variable count character node by examining element 2506 of fig. 25 (1904). If the node is a variable count character class node (1904), it reads the bitmap/mask corresponding to the character class index stored in the variable count character class node element (2506 of FIG. 25). The graphics walk engine then extracts the bytes from the payload and compares them with the corresponding entries in the bitmap/mask by using the bytes from the payload as an index into the bitmap/mask until there is a mismatch, either no more bytes available in the payload or the number of matched bytes equals the count (2510 of FIG. 25).

If the node is a variable-count-number node (1904), the graph-walk engine extracts a byte from the payload and compares it to the element stored in the node (2506 of FIG. 25), and continues to match bytes until there is a mismatch, there are no more bytes available in the payload, or the number of bytes matched equals the count (2510 of FIG. 25) (1906).

After matching the bytes from the payload to a character class or value/character/letter (1916 or 1906, respectively), the graphics walk engine determines if there are bytes remaining in the payload (1908). If the graphics walk engine has exhausted the payload (i.e., no bytes remaining) (1908), the graphics walk engine pushes the node to the save buffer/stack (1910), sets the terminate walk bit to true (1912), and returns (1918). If the graphics walk engine is not running out of payload (i.e., has remaining bytes) (1908), the graphics walk engine returns (1918).

FIG. 20 is a flowchart 2000 illustrating an example embodiment of processing a variable count full match node. With respect to fig. 25, the format of the variable count node is described above. With respect to fig. 20, flowchart 2000 is an extension of the processing (1620) of the variable count full match node described with respect to fig. 16.

The graphical walk engine begins processing the variable count nodes (2002). The graph walk engine determines whether the node is read from a running stack entry (2004). If the node is not reading from the run stack (2004), it pushes the run stack entry (FIG. 29, 2900) with the copy bit (FIG. 29, 2912) unset (e.g., set to 0) (2007). The graphics walking engine then returns (2020).

If the node is read from the running stack, (2004), the graphics walk engine determines if it runs out of payload (e.g., if there are no remaining bytes in the payload) (2005). If not, or if there are bytes remaining in the payload, the graph walk engine determines whether the variable count node is a variable count character class node or a variable count character node by examining element 2906 of FIG. 29 (2006).

If the node is a variable count character class node (2006), the graph walk engine reads a bitmap/mask corresponding to the character class index stored in the variable count character class node (2012). The graphics walk engine then extracts one byte from the payload and compares the byte with the corresponding entry in the bitmap/mask by using the byte from the payload as an index to the bitmap/mask (2014).

If the node is a variable-meter node (2006), the graph-walk engine extracts one byte from the payload and matches it to the value/character/letter stored in the node (2008).

After matching a byte from the payload to a character class or character (2014 or 2008, respectively), the graphics walk engine determines whether the byte matches the character class or character (2010). If there is a match (2010), the graphical walk engine decrements the count (i.e., count value 2910 of FIG. 29) by 1 (2022). If the count is greater than zero, the graphics walk engine pushes 2007 the run stack entry (FIG. 29, 2900) with the copy bit (FIG. 29, 2912) unset (e.g., set to 0) and returns 2020. If the count is equal to zero, the graphics walking engine does not push any stack entries and returns (2020). If there is no match, the graphical walk engine sets the end walk bit to true (2018) and returns (2020).

If the graphics walk engine has exhausted the payload, or has no remaining payload bytes (2005), the graphics walk engine pushes the node to the save buffer/stack (2016). The graphical walk engine then sets the terminate walk bit to true (2018) and returns (2020).

Fig. 21 is a table 2100 illustrating an example embodiment of a bitmap/mask used in a character class. Table 2100 shows a character class index 2102, a character class definition 2104, and ASCII values 2106. In embodiments implementing a character class table, the memory may store values for the character class index 2102, the character class definitions 2104, or the ASCII values 2106; however, they are shown here to demonstrate how the character class definitions relate to the character class matrix and how the indices can access the character class matrix. FIG. 21 illustrates five character class definitions as just one example embodiment. Other embodiments may include different kinds of character classes, and the number of unique character classes may be any number.

The [ < Lambda >/n ] character class conversion assigned with character class index 1 matches every character except for line wrapping because the "< Lambda >" operator produces the reciprocal of anything that follows it, and "\ n" indicates line wrapping. Thus, each bit in the bitmap/mask is set to "1", which is 12 except for the ASCII value corresponding to the line feed. Thus, a node processing bytes with a value of 12 accesses this matrix of character classes [1] [12], where "1" is the character class index and "12" is the value of the payload to the character class. Since the value at this position in the table is "0", the payload does not match. However, any other payload loaded into CharacterClassMatrix [1] [ PayloadByte ] produces a match.

The [ a-z ] character class assigned with the character class index 2 is converted to match each character in the range of 'a' to 'z'. Thus, in the bitmap/mask corresponding to the character class index 2, the values from 97 to 122 are set to "1" and all other values are set to "0". Thus, a node processing a payload segment representing an ASCII value of "c" accesses CharacterClassMatrix [2] [99], where "2" is the character class index and "99" is the value of the payload. Since the value at this position in the table is "1", the payload matches the character class. However, payloads outside the 97-122 range do not match for this character class. For example, if the payload is the number "4", the node accesses CharacterClassMatrix [2] [52], which has a value of 0, which indicates a mismatch.

The [ ^ a-z ] character class conversion assigned with the character class index 3 matches each value/character/letter except those in the range of 'a' to 'z'. Thus, in the bitmap/mask corresponding to the character class index 3, the values from 97 to 122 are set to "0" and all other values are set to "1". Thus, a node processing a payload segment representing an ASCII value of "c" accesses CharacterClassMatrix [3] [99], where "3" is the character class index and "99" is the value of the payload. Since the value at this position in the table is "0," the payload does not match the character class. However, payloads outside the range of 97-122 are matches for this character class. For example, if the payload is the number "4", the node accesses CharacterClassMatrix [3] [52], which has a value of 1, which indicates a match.

The [0-9] character class assigned with the character class index 4 is converted to match each value/character/letter in the range of '0' to '9'. Thus, in the bitmap/mask corresponding to the character class index 4, the values from 48 to 57 are set to "1" and all other values are set to "0". Thus, a node processing a payload segment representing an ASCII value of "D" accesses CharacterClassMatrix [4] [68], where "4" is the character class index and "68" is the value of the payload. Since the value at this position in the table is "0," the payload does not match the character class. However, payloads in the range of 48-57 are matches for this character class. For example, if the payload is the number "4", the node accesses CharacterClassMatrix [4] [52], which has a value of 1, which indicates a match.

The [ ABCabc ] character class assigned the character class index 5 is converted to match the individual values/characters/letters "a", "B", "C", "a", "B", and "C". Thus, in the bitmap/mask corresponding to the character class index 5, the values from 65, 66, 67, 97, 98, and 99 are set to "1" and all other values are set to "0". Thus, a node processing a payload segment representing an ASCII value of "c" accesses CharacterClassMatrix [5] [99], where "5" is the character class index and "99" is the value of the payload. Since the value at this position in the table is "1", the payload matches the character class. However, the values of 65, 66, 67, 97, 98, and 99 do not match for this character class. For example, if the payload is the number "4", the node accesses CharacterClassMatrix [5] [52], which has a value of 0, which indicates a mismatch.

In one embodiment, the character class matrix may be used for any data type or data length. In the above embodiments, these payloads are characters, which may be 7 bits or 8 bits. However, any length of data may be used and it need not necessarily be in the form of characters. Other data encodings may be used. Examples of other applications for such tables are video processing, audio processing, binary search, or any pattern search application.

The teachings of all patents, published applications and references cited herein are incorporated by reference in their entirety.

While the present invention has been particularly shown and described with reference to exemplary 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 encompassed by the appended claims.

Claims (72)

1. A method of walking a non-deterministic finite automata (NFA) pattern representing a pattern, the method comprising:

extracting a node type, a next node address, and an element from a node of the NFA graph; and

matching a segment of a payload to the element by matching the payload to the element at least zero times, the times being based on the node type.

2. The method of claim 1, wherein the node type is at least one of: variable count, fixed-variable count, character, case-insensitive character, character class, case-insensitive string, tagged, disjoint.

3. The method of claim 1, further comprising pushing an entry to a running stack, the entry indicating at least one of: the node type, the address of the next node in the graph, a payload offset, a count value, a copy bit, an inverse bit.

4. The method of claim 3, wherein pushing the entry to the run stack is based on the node type.

5. The method of claim 4, wherein pushing the entry to the run stack is performed if the node type is variable count, fixed-variable count, or split.

6. The method of claim 1, further comprising:

popping a top entry of a running stack;

loading a graph node indicated by the popped top entry; and

the segment of the payload is matched to the element at a payload offset indicated in the popped top entry, the element being indicated in the loaded graph node.

7. The method of claim 6, wherein popping the top entry of the run stack is performed after a mismatch that matches the segment of the payload with the element.

8. The method of claim 1, further comprising:

popping a top entry of a running stack;

extracting the graph node information stored in the popped top item; and

matching the segment of the payload with the element at a payload offset indicated in the popped top entry, the element being indicated in the extracted graph node.

9. The method of claim 1, wherein the string node type represents a portion of a pattern of values, each value being at least one of a byte, a letter, or a character.

10. The method of claim 1, wherein matching the segment of the payload with the element associated with the string node type comprises matching at least two values within the segment with corresponding values of a string stored as the element in the node.

11. The method of claim 10, further comprising:

if the segment partially matches the element, and if the length of the payload is shorter than the length of the string of the element stored as the node, then the next payload of the same stream of the payload is loaded and the remaining values in the string continue to match the values in the next payload.

12. The method of claim 11, further comprising pushing a partial match to a save buffer to be loaded when the next payload of the same stream of the payload is loaded.

13. The method of claim 12, wherein pushing the partial match to the save buffer comprises storing a current running stack entry being processed in the save buffer; and further comprising:

copying at least one entry stored in the save buffer to the run stack after the next payload is loaded.

14. The method of claim 1, wherein matching the segment of the payload with the element associated with the variable count node type comprises matching the element a variable number of times indicated by a count value extracted from the node.

15. The method of claim 14, wherein the variable number of times is at least zero, at most a finite number, or at most an infinite number.

16. The method of claim 1, wherein the node type further indicates that the variable count node is a greedy node, lazy node, leadership node, or full match node.

17. The method of claim 1, wherein matching the segment of the payload with the element if the node type is a variable count lazy node comprises returning the shortest match found in the payload.

18. The method of claim 1, wherein matching the segment of the payload with the element if the node type is a variable count lazy node comprises pushing a stack entry to a running stack, the stack entry indicating the variable count lazy node and payload offset, and a next node loaded in the graph at the next node address.

19. The method of claim 18, wherein matching the segment of the payload with the element if the node type is a variable count lazy node comprises: if matching the next node element to the segment is a mismatch, popping the node of the variable count lazy node's node type from the stack entry of the running stack and matching the element stored in the popped node to the payload segment.

20. The method of claim 19, wherein upon matching the segment of the payload with the element stored in the popped node, decrementing a count value of the variable count lazy node, pushing an updated stack entry to the running stack and loading the next node at the next node address stored in the popped entry.

21. The method of claim 18, wherein if the segment of the payload continues within a next payload of the same flow of the first payload, further comprising:

pushing the running stack entry to a save buffer; and

the save buffer entries are loaded into the run stack after the next payload is loaded.

22. The method of claim 1, wherein matching the segment of the payload with the element if the associated node type is a variable count greedy node or a variable count leading node comprises returning a longest match found in the payload.

23. The method of claim 1, wherein matching the segment of the payload with the element if the node type is a variable count greedy node comprises:

at least one segment of the payload is extracted,

matching the at least one segment with the element, and

if there is a mismatch and at least one segment matches the element less than or equal to the number of times a variable count in the variable count greedy node, or there are no more segments in the payload available:

if the number of segments matched indicates that the element has been matched less than the maximum number of times, pushing a run stack entry storing the node type of the node, the payload offset of the at least one segment of the payload, and the number of segments matched,

extracting a next node of the NFA graph indicated by the next node address, an

Continuing to match a next segment of the payload indicated by a position following the payload offset of the payload with a second element of the next node, wherein, if there is a mismatch, popping the run stack entry from the run stack, decrementing the number of segment match counts, pushing the updated run stack entry back to the run stack, and continuing to match the next segment of the payload from the offset stored in the popped entry with an element of the next node stored at the next node address stored in the popped entry.

24. The method of claim 1, wherein matching the segment of the payload to the element if the node type is a variable count leading node comprises successively matching the payload segment to the element until no match or a count of the variable count leading node indicates a maximum number of times the element has been matched, and then continuing to match subsequent segments of the payload to a next node stored at the next node address.

25. The method of claim 1, wherein matching the segment of the payload with the element if the node type is a variable count full match node comprises returning all matches found in the payload.

26. The method of claim 1, wherein matching the segment of the payload with the element if the node type is a variable count full match node comprises matching the segment with the element and, if it matches, pushing a stack entry to a running stack, the stack entry indicating the variable count full match node and payload offset with an indication to continue matching the NFA graph, and loading a next node at the next node address and, if it does not match, popping the stack entry from the running stack.

27. The method of claim 1, wherein the fixed count node type represents a portion of the pattern to be matched a fixed number of times for an element.

28. The method of claim 27, wherein the element of the fixed-count node type may be a character, a character class, or a character string.

29. The method of claim 1, wherein matching the segment of the payload with the element associated with the fixed-count node type comprises matching at least two values within the segment with one value of the element stored in the node.

30. The method of claim 29, further comprising:

if the segment matches the element, and if the length of the payload is shorter than the count of the fixed count node, then the next payload of the same flow of the payload is loaded and the remaining values in the element continue to be matched to the values in the next payload.

31. The method of claim 1, wherein the element can be at least one of a character, a character class, and a character string.

32. The method of claim 1, wherein the character class node type represents a portion of the pattern to be matched to an element by a boolean or operation using at least one value.

33. The method of claim 32, wherein each character class is stored as a mask in a memory, wherein if each possible character in the mask is part of the character class, an indicator corresponding to the character is set, and if it is not part of the character class, it is not set.

34. The method of claim 1, wherein upon a successful match, a second node of the NFA graph is loaded from the next node address extracted from the node.

35. The method of claim 1, wherein:

if the node type is a variable count, extracting a count value from the node, the count value indicating a maximum number of matches with the element,

if the node type is a fixed count, a count value is extracted from the node, the count value indicating the exact number of times the element is matched,

if the node type is a string, extracting a count value from the node, the count value indicating the length of the string, an

If the node type is a fixed-variable count, two count values are extracted from the node, a first count value indicating the exact number of matches with the element and a second count value indicating the maximum number of matches with the element.

36. The method of claim 1, wherein matching the segment of the payload with the element associated with the marked node type comprises indicating that a match was found and popping any entry in a running stack or, if indicated in the node, continuing to walk a next node in a reverse direction at the next address indicated in the node.

37. A system for walking non-deterministic finite automata (NFA) patterns representing patterns, the system comprising:

a determining module configured to extract a node type, a next node address, a count value, and an element from nodes of the NFA graph; and

a matching module configured to match a segment of a payload against the element by matching the payload against the element at least zero times, the times being based on the node type.

38. The system of claim 37, wherein the node type is at least one of: variable count, fixed count and variable count, characters, case-insensitive characters, character classes, character strings, case-insensitive character strings, labeled and separated.

39. The system of claim 37, wherein the matching module is further configured to push an entry to a running stack, the entry indicating at least one of: the node type, the address of the next node in the graph, a copy bit, an inverse bit.

40. The system of claim 39, wherein the matching module is further configured to push the entry to the run stack based on the node type.

41. The system of claim 40, wherein the matching module is further configured to push the entry to the running stack if the node type is variable count, fixed-variable count, or split.

42. The system of claim 37, wherein the matching module is further configured to:

popping a top entry of the run stack;

loading a graph node indicated by the popped top entry; and

the segment of the payload is matched for the element at the payload offset indicated in the popped top entry, the element being indicated in the loaded graph node.

43. The system of claim 42, wherein the matching module is further configured to pop the top entry of the run stack after a mismatch that matches the segment of the payload with the element.

44. The system of claim 37, wherein the matching module is further configured to:

popping a top entry of the run stack;

extracting the graph node information stored in the popped top item; and

the segment of the payload is matched for the element at the payload offset indicated in the popped top entry, the element being indicated in the extracted graph node.

45. The system of claim 37, wherein the string node type represents a portion of a pattern of values, each value being at least one of a byte, a letter, or a character.

46. The system of claim 37, wherein the matching module is further configured to match the segment of the payload against the element associated with the string node type by comparing at least two values within the segment with corresponding values of a string stored as the element in the node.

47. The system of claim 46, wherein the matching module is further configured to, if the segment matches the element, and if the length of the payload is shorter than the length of the string of the element stored as the node, load a next payload of the same stream of the payload and continue matching remaining values in the string with values in the next payload.

48. The system of claim 47, wherein the matching module is further configured to push a partial match to a save buffer to be loaded after loading the next payload of the same stream of the payload.

49. The system of claim 48, wherein the matching module is further configured to push the partial match to the save buffer by storing a current running stack entry being processed in the save buffer, at least one entry stored in the save buffer being copied to the running stack upon loading the next payload.

50. The system of claim 37, wherein the matching module is further configured to match the element a variable number of times indicated by a count value extracted from the node.

51. The system of claim 37, wherein the variable number of times is at least zero, a maximum finite number of times, or a maximum infinite number of times.

52. The system of claim 37, wherein the node type further indicates that the node is a greedy node, lazy node, leadership node, or full match node.

53. The system of claim 37, wherein the matching module is further configured to, if the node type is a variable count lazy node, include returning the shortest match found in the payload.

54. The system of claim 37, wherein the matching module is further configured to push a stack entry to a running stack if the node type is a variable count lazy node, the stack entry indicating the variable count lazy node and payload offset, and a next node loaded in the graph at the next node address.

55. The method of claim 54 wherein the matching module is further configured to pop the node of the variable count lazy node's node type from the stack entry of the running stack if matching the next node element to the segment is a mismatch and match the element stored in the popped node to the payload segment.

56. The system of claim 55, wherein the matching module is further configured to, upon matching the segment of the payload with the element stored in the popped node, decrement a count value of the variable count lazy node, push an updated stack entry to the running stack, and load a next node at the next node address stored in the popped entry.

57. The system of claim 54, wherein the matching module is further configured to push the running stack entries to a save buffer if the segment of the payload continues within a next payload of the same flow of the first payload and to load the save buffer entries into the running stack upon loading the next payload.

58. The system of claim 37, wherein the matching module is further configured to return the longest match found in the payload if the node type is a variable count greedy node or a variable count leader node.

59. The system of claim 37, wherein the matching module is further configured to, if the node type is a variable count greedy node,

at least one segment of the payload is extracted,

matching the at least one segment with the element,

if there is a mismatch and at least one segment matches the element less than or equal to the number of times a variable count in the variable count greedy node, or the payload has no more segments available:

if the number of segments matched indicates that the element has been matched less than the maximum number of times, pushing a run stack entry storing the node type of the node, the payload offset of the at least one segment of the payload, and the number of segments matched,

extracting a next node of the NFA graph indicated by the next node address, an

Continuing to match a next segment of the payload indicated by a position following the payload offset of the payload with a second element of the next node, wherein, if there is a mismatch, popping the run stack entry from the run stack, decrementing the number of segment match counts, pushing the updated run stack entry back to the run stack, and continuing to match the next segment of the payload from the offset stored in the popped entry with an element of the next node stored at the next node address stored in the popped entry.

60. The system of claim 37, wherein the matching module is further configured to, if the node type is a variable count leading node, match the segment of the payload to the element comprises successively matching the payload segment to the element until a mismatch or count of the variable count leading node indicates that the element has been matched a maximum number of times, and then continuing to match subsequent segments of the payload to the next node stored at the next node address.

61. The system of claim 37, wherein the matching module is further configured to return all matches found in the payload if the node type is a variable count full match node.

62. The system of claim 37, wherein the matching module is further configured to match the segment to the element if the node type is a variable count full match node and, if it matches, push a stack entry to a running stack, the stack entry indicating the variable count full match node and payload offset with an indication to continue matching the NFA graph, and load a next node at the next node address and, if it does not match, pop the stack entry from the running stack.

63. The system of claim 37, wherein a fixed count node type represents a pattern to be matched a fixed number of times for an element.

64. The system of claim 63, wherein an element can be at least one of a character, a character class, and a character string.

65. The system of claim 37, wherein the matching module is further configured to match the segment of the payload with the element associated with the fixed-count node type by matching at least two values within the segment with one value of the element stored in the node.

66. The system of claim 65, wherein the matching module is further configured to, if the segment partially matches the element and if the length of the payload is shorter than the count of the fixed count node, load a next payload of the same stream of the payload and continue matching remaining values in the string with values in the next payload.

67. The system of claim 37, wherein the element can be at least one of a character, a character class, and a character string.

68. The system of claim 37, wherein the character class node type represents a portion of the pattern to which an element is to be matched by a boolean or operation using at least one value.

69. The system of claim 68, wherein each character class is stored in a memory as a mask, wherein if each possible character in the mask is part of the character class, an indicator corresponding to the character is set, and if it is not part of the character class, it is not set.

70. The system of claim 37, wherein upon a successful match, a second node of the NFA graph is loaded from the next node address extracted from the node.

71. The system of claim 37, wherein the matching module is further configured to:

if the node type is a variable count, a count value is extracted from the node, the count value indicating a maximum number of matches with the element,

if the node type is a fixed count, a count value is extracted from the node, the count value indicating the exact number of times the element is matched,

if the node type is a string, extracting a count value from the node, the count value indicating the length of the string, an

If the node type is a fixed-variable count, two count values are extracted from the node, a first count value indicating the exact number of matches with the element and a second count value indicating the maximum number of matches with the element.

72. The system of claim 37, wherein the matching module is further configured to match the segment of the payload with the element associated with the marked node type by indicating that a match was found and pop any entry in a running stack or, if indicated in the node, continue walking a next node at the next address indicated in the node in a reverse direction.