HK1208104B - A method and computer system of compiling a pattern into a non-deterministic finite automata (nfa) graph - Google Patents

Description

Method and computer system for compiling a pattern into a nondeterministic finite automaton (NFA) graph

Technical Field

Embodiments of the present invention are directed to generating non-deterministic finite automaton (NFA) graphs for regular expression patterns having high-level features.

Background Art

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

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

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

Content-aware networking requires inspection of the contents of data packets at "wire speed". The content can be analyzed to determine if there are security vulnerabilities or intrusions. A large number of patterns and rules in the form of regular expressions are applied to ensure that all security vulnerabilities or intrusions are detected. Regular expressions are a compact method for describing patterns in strings of values/characters/letters. The simplest pattern matched by a regular expression is a single value/character/letter or a string of values/characters/letters, for example, /c/ or /cat/. Regular expressions also include operators and metacharacters with special meanings.

By using metacharacters, regular expressions can be used for more complex searches, such as "abc.*xyz". That is, with an unlimited number of characters between "abc" and "xyz", find the string "abc" followed by the string "xyz". Another example is the regular expression "abc..abc.*xyz;", that is, find the string "abc", followed by two characters, then the string "abc" and followed by the string "xyz" after an unlimited number of characters.

Intrusion detection system (IDS) applications examine the contents of all individual packets flowing through a network and identify suspicious patterns that could indicate an attempt to break into or compromise a system. An example of a suspicious pattern might be a specific string of text within a packet that is followed 100 characters later by another specific string of text. Content searches are typically performed using search algorithms, such as deterministic finite automata (DFA) or nondeterministic finite automata (NFA) for processing regular expressions.

Summary of the Invention

In one embodiment, a method for compiling a pattern into a non-deterministic finite automaton (NFA) graph includes checking the pattern for multiple elements and multiple node types. Each node type corresponds to an element. Each element of the pattern can be matched at least zero times. The method further includes generating multiple nodes of the NFA graph. Each of the multiple nodes can be configured to match one of the multiple elements. The element can indicate the next node address in the NFA graph, a count value, and/or a node type corresponding to the element. The node can also indicate that the element represents a character, a character class, or a string. A character can also be a value or a letter.

In one embodiment, the node type is at least one of: variable count, fixed count, fixed count and variable count, character, case-insensitive character, character class, string, case-insensitive string, tokenized, and separated.

In one embodiment, checking the pattern for the node type may include searching the pattern for indications of at least one of the following node types: variable count node type, fixed count node type, fixed and variable count node types, character class, and string.

In one embodiment, a string node type can represent a pattern of multiple values, letters, characters, or other data types. Performing a string node type check on the pattern can include determining that the pattern indicates multiple consecutive values. Performing a string node type check on the pattern can further include determining that the consecutive values are not interposed between multiple node types. Each value can be a byte, letter, and/or character.

In one embodiment, performing the variable count node type check on the pattern may include determining that the pattern indicates matching the element a variable number of times. Performing the variable count node type check on the pattern may further include determining that the pattern indicates matching the element at least zero times.

In one embodiment, a fixed count node type represents a pattern to be matched a fixed number of times for an element. The fixed count and variable count node types can represent a pattern to be matched a fixed number of times and then a variable number of times for an element. The variable number of times can be a finite number of times or an infinite number of times. Checking the pattern for the fixed count and variable count node types can include determining that the pattern indicates that the element is to be matched at least once and at most a fixed number of times or an infinite number of times. The pattern includes a symbol representing infinity, which is used to trigger a determination that the pattern indicates that the element is to be matched an infinite number of times.

In one embodiment, a character class node type may represent a Boolean OR operation of at least one value. The method may further include storing each character class as a mask. Each possible value/character/letter in the mask may be set if the value/character/letter is part of the character class, and not set if it is not part of the character class. Each node may include a character class index corresponding to a unique character class. The character class number and payload segment may be used as an index into the mask so that if the indexed entry is set, the graph walking engine can determine that the payload matches the character class.

In one embodiment, the variable count node type can further indicate that the node is a greedy node, a lazy node, a possessive node, or a full match node. The greedy match type and the possessive match type's variable count node type can be matched for the longest possible match in the payload. However, after reaching the end of the payload, the possessive match type's node type does not backtrack, while the greedy match type's node type does backtrack. The lazy match type's variable count node type can be matched for the shortest possible match in the payload. The full node match type's variable count node type can be matched for all matches in the payload.

In one embodiment, performing a node type and element check on the pattern includes identifying at least a portion of the pattern as a character class node type and a corresponding element. Performing a node type and element check on the pattern may include identifying at least two portions of the pattern as a character class node type and a corresponding element. The method may further include generating a bitmap for each of the portions. Each bit in the bitmap may represent a value that matches the element. Each bitmap may be associated with a character class index. The method may further include associating the first and second portions with the same bitmap if a first portion of the at least two portions and a second portion of the at least two portions have the same corresponding element. Checking the pattern may include checking multiple patterns. The first and second portions may be in separate patterns.

In one embodiment, a method for compiling a pattern into a non-deterministic finite automaton (NFA) graph may include a pattern determination module configured to perform multiple element and multiple node type checks on the pattern. Each node type corresponds to an element. Each element of the pattern can be matched at least zero times. The system may further include a node generation module configured to generate multiple nodes of the NFA graph. Each node in the multiple nodes can be configured to match one of the multiple elements. The node can indicate the node type corresponding to the element. The node can further indicate the next node address, count value, and the element representation character, character class, or string in the NFA graph. A character can also be a value or a letter.

A variable count node is a node that matches an element a variable number of times, where the number of matches is defined by a range (e.g., zero to five times). A variable count node can have one of four characteristics: lazy, greedy, possessive, or full match. A variable count lazy node is configured to find the shortest possible match for an element within the range. A variable count possessive node is configured to find the longest possible match for an element within the range without backtracking when the end of the payload is reached. A variable count greedy node is configured to find the longest possible match for an element within the range, where backtracking is performed when the end of the payload is reached. A variable count full match node is configured to return all matches in the payload.

A fixed count node matches an element a fixed number of times. Fixed count and variable count patterns can be expressions configured as variable count patterns that match a range, where the range starts with a number greater than zero. For example, a variable count pattern that matches an element 10 to 20 times can be expressed as a fixed count node that matches the element ten times and then a variable count node that matches the element 0 to 10 times. A string node is a node that matches a string (set of characters) in a specific order.

A fixed-variable count node is a node that matches a fixed number of times for an element and then matches a variable number of times for the same element. For example, consider the pattern "b{2, 5}", which matches 2 to 5 times for the character element "b". This pattern can be compiled into a fixed-variable count node with two count values. The first count value indicates the fixed number of times that the element is matched, and the second count value indicates the variable number of times that the element is matched. The second count value can be, for example, a total maximum value (in this example, matching the element five times in total) or the maximum value after the fixed match is completed (in this example, three times in total, or the difference between the maximum variable number of times five times and the first count twice). As described below, the processing of fixed-variable nodes is identical to that of variable count nodes.

A marker node is a node that indicates a match was found for a pattern in the payload. A split node is a node that indicates a choice 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.

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

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

2B is a block diagram illustrating an example embodiment of an environment for the engine (eg, network services processor) of FIG. 2A .

FIG. 3A is a diagram illustrating an example embodiment of an NFA graph.

FIG. 3B is a diagram of an example embodiment of an NFA graph used with the present invention.

FIG. 3C is a diagram illustrating an example embodiment of an NFA graph showing other types of counting nodes that may be used.

FIG. 4A is an example embodiment of an NFA graph used by prior art systems.

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

FIG. 4C is an example embodiment of a conventional graph of the pattern “USPTO” using five separate nodes.

FIG4D 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.

FIG6A is a block diagram illustrating an example embodiment of a compiler processing pattern.

FIG. 6B is a diagram of the compiled NFA graph generated by the pattern of FIG. 6A .

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

FIG8 is a flow chart illustrating an example embodiment of compiling a pattern.

FIG9 is a flow chart illustrating an example embodiment of processing nodes by a graph walking engine.

FIG10 is a block diagram illustrating an example embodiment of a graph walking engine processing nodes of an NFA graph.

FIG11 is a flow chart showing the process of walking the NFA graph used in the present invention.

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

FIG13 is a flow chart showing an example embodiment of processing character nodes.

FIG14 is a flow chart showing an example embodiment of processing a string node by a graph walking engine.

15A and 15B are flow charts illustrating example embodiments of processing fixed count nodes.

FIG16 is a flow chart illustrating an example embodiment of processing a variable count node.

FIG17 is a flow chart illustrating an example embodiment of processing a variable count lazy node.

FIG18 is a flow chart illustrating an example embodiment of processing a variable count greedy node.

FIG19 is a flow chart illustrating an example embodiment of processing a variable count owner node.

FIG20 is a flow chart illustrating an example embodiment of processing a variable count full match node.

FIG. 21 is a table showing an example embodiment of bitmaps/masks used in character classes.

FIG22 is a table showing the format of a character class matching node.

FIG23 is a table showing the format of a string matching node.

FIG24 is a table showing the format of a fixed count matching node.

FIG25 is a table showing the format of a variable count match node.

Figure 26 is a table showing the format of a character class matching stack entry.

FIG27 is a table showing the format of a string matching stack entry.

Figure 28 is a table showing the format of a fixed count match stack entry.

FIG29 is a table showing the format of a variable count match stack entry.

DETAILED DESCRIPTION

What follows is a description of several example embodiments of the invention.

U.S. Application No. 13/303,855 to Goyal et al., “Reverse NFA Generation and Processing,” published as U.S. Publication No. 2013/0133064, and U.S. Application No. 13/168,395 to Goyal et al., “Regular Expression Processing Automaton,” published as U.S. Publication No. 2012/0221497, describe NFA and expression matching concepts. The entire teachings of these applications are incorporated herein by reference.

Perl Compatible Regular Expressions (PCRE) has become the de facto standard for regular expression syntax in security and networking applications. As more applications requiring deep packet inspection have emerged or more threats have become prevalent on the Internet, the corresponding features/patterns or applications for identifying viruses/attacks have also become more complex. Feature databases have evolved from having simple string patterns to regular expression (regex) patterns with wildcard characters/ranges/character classes to advanced PCRE features. Advanced PCRE features specifically refer to features such as starting offsets, backreferences, capture groups, and assertions. Embodiments of the present invention support advanced PCRE features at line rate.

Before describing example embodiments of the present invention in detail, an example network security application in which these embodiments may be implemented using DFA and NFA is described immediately below to help the reader understand the inventive features of the present invention.

FIG1A is a block diagram of an example security appliance 102 including a network services processor 100. Security appliance 102 may be a standalone system that can switch packets received on 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, security appliance 102 may be configured to perform security processing on packets received on a wide area network (WAN) before forwarding the processed packets to a local area network (LAN).

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

The network services processor 100 can schedule and queue work (packet processing operations) for upper-layer network protocols (e.g., L4-L7) and allow upper-layer network protocol processing to be performed on received packets to forward packets at line speed. By processing these protocols to forward packets at line speed, the network services processor does not reduce the network data transfer rate.

The network services processor 100 may include multiple Ethernet media access control interfaces, wherein a standard Reduced Gigabit Media Independent Interface (RGMII) is connected to the off-chip PHY 104a and PHY 104b.

The network services processor 100 may also receive data packets from the Ethernet port (GigE) via the physical interfaces PHY 104a and PHY 104b, perform L2-L7 network protocol processing on the received data packets, and forward the processed data packets via the physical interfaces 104a and 104b to another hop or final destination in the network or via the peripheral component interconnect/peripheral component interconnect extended interface (PCI/PCI-X) bus 106 for further processing by the host processor. The network protocol processing may include processing of network security protocols such as firewalls, application firewalls, virtual private networks (VPNs) including IP Security (IPSec) and/or Secure Sockets Layer (SSL), intrusion detection systems (IDS), and antivirus (AV).

The network services processor 100 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 for Internet services and security applications that allow fast lookups, including string matching as may be required by intrusion detection systems (IDS) or anti-virus (AV) applications or other applications requiring string matching.

According to one embodiment of the present invention, the network service processor 100 can perform pattern searching, regular expression processing, content verification, conversion, and security to accelerate packet processing. Regular expression processing and pattern searching can be used to perform string matching for IDS and AV applications and other applications that require string matching.

A DRAM controller in the network services processor 100 can control access to an external dynamic random access memory (DRAM) 108 coupled to the network services processor 100. DRAM 108 can store data packets received from the PHY interfaces 104a and 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 (DDRII SDRAM) running at up to 800 MHz. DRAM can also store rule data required for lookups and pattern matching in DFA and NFA graph expression searches.

The boot bus 110 can provide the necessary boot code that can be stored in the flash memory 112 and executed by the network services processor 100 when the network services processor 100 is powered on or reset. Application code can 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 large storage device that can be a disk attached through the PCI/PCI-X bus 106.

The miscellaneous I/O interface 116 provides auxiliary interfaces such as a general purpose input/output interface (GPIO), flash memory, an IEEE 802 two-wire managed data input/output (MDIO) interface, a universal asynchronous receiver/transmitter (UART), and a serial interface.

It should be appreciated that the example security appliance 102 may alternatively include a protocol processor 101 ( FIG. 1B ). The protocol processor 101 may include elements of the network services processor 100 with the addition of a content processing accelerator 107 coupled to the processor 101 via a PCI/PCI-X connection 106, and external DRAM 111 coupled to the accelerator 107. The accelerator 107 and DRAM 111 may be used in content search applications, thereby performing all content search operations external to the processor 101.

FIG2A is a block diagram of the network service processor 100 or protocol processor 101 shown in FIG1A and FIG1B , respectively. The network service processor 100 and/or protocol processor 101 use multiple processors (cores) 202 to provide high application performance. Network applications can be classified into data plane and control plane operations. Each core in the core 202 can be dedicated to performing data plane or control plane operations. Data plane operations can include data packet operations to forward data packets. Control plane operations can include multiple parts of processing complex high-level protocols, such as Internet Protocol Security (IPSec), Transmission Control Protocol (TCP) and Secure Sockets Layer (SSL). Data plane operations can include other parts of processing these complex high-level protocols.

Data packets can be received by either interface unit 210a or 210b via an SPI-4.2 or RGM II interface. PCI interface 224 can also receive data packets. Interface units 210a and 210b process the L2 network protocol, which pre-processes received data packets by checking various fields in the L2 network protocol header included in the received data packet. After interface units 210a and 210b have performed L2 network protocol processing, they forward the data packets to packet input unit 214. Packet input unit 214 can pre-process the L3 and L4 network protocol headers included in the received data packet. This pre-processing includes checksum checks on the Transmission Control Protocol (TCP)/User Datagram Protocol (UDP) (L3 network protocols).

The packet input unit 214 may write packet data to a buffer in the level 2 cache 212 or DRAM 108 in a format convenient for 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 distribute packet data across multiple buffers to support large packet input sizes.

The 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 performed by the processor identified by an entry on a work queue. The task may include packet processing operations, such as L4-L7 layer packet processing operations to be performed on a received packet identified by a work queue entry on the work queue. Each individual packet processing operation is a piece of work to be performed by the processor on a received packet stored in memory (L2 cache 212 or DRAM 108). For example, the work may be processing of a received firewall/virtual private network (VPN) packet. The processing of a firewall/VPN packet may include the following individual packet processing operations (pieces of work): (1) defragmentation to reorder fragments within a received packet; (2) IPSec decryption; (3) IPSec encryption; and (4) network address translation (NAT) or TCP sequence number adjustment before forwarding the packet.

The network services processor 100 and/or the 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. The processors 202 and the I/O coprocessor devices may all share the Level 2 cache 212 and the external DRAM memory 108 (of Figures 1A and 1B).

The network services processor 100 and/or the protocol processor 101 may also include special purpose coprocessors that offload the processor 202 to enable the network services processor to achieve high throughput. These special purpose coprocessors include a coprocessor 244 that performs non-deterministic finite automaton (NFA) processing, described in more detail below, and a 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, built-in hardware acceleration for cryptographic algorithms (cryptographic acceleration module) 200, and direct access to local memory via a low-latency memory bus 230. The low-latency direct access path to local memory 118 bypasses the L2 cache 212 and is directly accessible from both the processor (core) 202 and the NFA coprocessor 244.

Before further describing the operations of the content search macros and pattern search for regular expression processing, the other modules in the network services processor 100 will be described. In one example, after the processor 202 has processed a 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 DRAM 108 location used to store the packet.

Each processor 202 is connected to the L2 cache through a consistent memory bus 234. The consistent 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 212 and controller 216.

The free pool allocator (FPA) 236 maintains multiple pointer pools to free memory in the Level 2 cache 212 and DRAM 108. A bandwidth-efficient (last-in, first-out (LIFO)) stack is implemented for each free pointer pool. If a pointer pool is too large to fit within the free pool allocator (FPA) 236, the free pool allocator (FPA) 236 uses the freed memory in the pointer pool to store additional pointers to build a tree/list structure in the Level 2 cache 212 or DRAM 108.

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

The Fetch and Add Unit (FAU) 240 is a 2KB register set that supports read, write, auto-fetch and add, and auto-update operations. The Fetch and Add Unit (FAU) 240 is accessible from both the processor 202 and the packet output unit 218. The registers store highly used values and thus reduce the amount of traffic required to access these values. Registers in the FAU 240 are used to maintain the length of the output queue used to forward processed packets through the packet output unit 218.

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

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

Patterns are typically expressed using regular expressions, which include basic elements such as normal text characters such as A-Z, 0-9, and metacharacters such as *, ^, and | or other values. The basic elements of a regular expression are symbols (single characters) to be matched. These are combined with metacharacters that allow one or more matches of an element (+), alternation (|), or Kleene's asterisk (*), which match an element zero or more times. In one embodiment, metacharacters can be defined by the PCRE pattern standard. Metacharacters used for concatenation are used to create multiple character matching patterns from a single character (or substring), while metacharacters used for alternation (|) are used to create regular expressions that can match any one of two or more substrings. The metacharacter Kleene's asterisk (*) allows a pattern to match any number of times, including matching a preceding character or character class or a string with a preceding character or character class where no payload segment occurs. Combining different operators and single characters allows for the construction of complex expressions. For example, the expression (th(is|at)*) will match the following strings: th, this, that, thisis, thisat, thatis, or thatat. When the metacharacter (?) follows an element, the metacharacter (?) can be the equivalent of {0, 1}. For example, the pattern "zzza?" can match a "zzz" payload or a payload of "zzza".

The character class construct [...] allows for a list of characters to be matched, such as gr[ea]y finds both grey and gray. A dash indicates a range of characters, such as [A-Z] or [0-9]. A character class can further have multiple ranges, for example, [a-zA-Z0-9] would include all letters, lowercase and uppercase, and all digits. The metacharacter "." matches any one character except the newline character. Additionally, the metacharacter "^" indicates every character except the one that follows it. For example, "[^\n]" indicates every character except the "newline" character (where "\n" indicates a newline). Another example is "[^0-9]", which indicates any character except the digits "0" through "9".

Typically, ASCII characters are stored as binary numbers from 0-128 or 0-256 in 7-bit and 8-bit embodiments, respectively. For example, the line feed (or line skip) character can be represented as the number 12 under ASCII. The line feed can then be represented in binary as "000 1010" or "0000 1010" in the 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, ie, an alphabet is a single byte (a character or symbol). Each byte in the input stream generates a transition from one state to another.

The states and transition functions of a DFA or NFA state machine can be represented by a graph, where each node in the graph represents a state and 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.

Use a DFA to process a regular expression and find one or more patterns described by the regular expression in an input stream of characters that are characterized by:

1) Deterministic Runtime Performance: The next state of a 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. Thus, the runtime performance of a DFA is considered deterministic and its behavior is completely predictable from the input.

2) Smaller per-flow context (e.g., state or node pointers) required to support matching across multiple packets: In searching for a pattern spanning the inputs of several packets that make up a flow, the search may stop at one packet and then resume at another. Typically, determining the state to resume the search requires tracking, remembering, or otherwise storing (e.g., as a state pointer or stack entry) all states traversed up to the time the search stopped. However, in a DFA, only the state at the time the search stopped needs to be recorded in order to resume the search. Thus, a characteristic of a DFA is that a smaller per-flow context is required to support pattern matching across multiple input packets, e.g., storing state or node pointers on the order of several bytes.

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

In contrast, the use of an NFA to process regular expressions and find one or more patterns described by the regular expression in an input stream of characters is characterized by:

1) Uncertain Runtime Performance: Given an input character (or symbol) and the current state of the NFA, there may be more than one next state of the NFA to transition to. In other words, the next state of the NFA cannot be uniquely determined from the input and the current state of the NFA. As such, the runtime performance of the NFA is considered uncertain, and its behavior cannot be fully predicted from the input.

2) Large per-flow context (e.g., state or node pointers) required to support matching across multiple packets: As previously mentioned, pattern matching across multiple input packets, where the search stops at one packet and then resumes at another, requires tracking all states traversed up to the point where the search stopped. In an NFA, the more inputs to be matched, the greater the number of current states that need to be tracked. Thus, compared to a DFA, an NFA is characterized by the need for a larger per-flow context to support pattern matching across multiple input packets.

3) Graphs in which the number of nodes (or graph size) typically grows linearly with the size of the graph.

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

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

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

During the processing of payload 262 and graph 257, payload 262 may run out of data before processing is complete. Payload 262 may be a packet or other packetized data from a data stream (or payload stream). The stream may have multiple payloads 262 (e.g., packets), each payload 262 having a sequence within the stream. Each segment of payload 262 is a portion of the payload with a specific granularity, such as, but not limited to, a byte. In one embodiment, this granularity is adjustable or selectable. An example of this situation is when the payload offset of payload 262 begins toward the end of a packet and a partial match is found before the end of the packet. To continue processing, 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 from run stack 260. Then, when engine 252 loads subsequent portions of payload 262 from the packet's data stream, engine 252 can load run stack entries from save buffer 264 and push them into run stack 260 to continue processing. This loading of save buffer entries into the run stack may also be performed by the host processor while submitting instructions to the engine for subsequent packets of the same flow.

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

When a mismatch is found between the payload 262 and the graphics 257, the engine pops and processes the next entry (e.g., the first entry S1) in the run stack 260 associated with the job loaded from the input buffer 258. If there are no entries (e.g., the first entry S1) left in the run stack 260 associated with the job loaded from the input buffer 258, the engine 252 completes the current job and loads the next entry (e.g., S2) from the run stack that was previously loaded from the input buffer 258. The engine 252 can then process the graphics and payload segments corresponding to that entry and continue processing additional jobs until the run stack 260 is empty.

FIG3A is a diagram 300 illustrating an example embodiment of an NFA graph 320 used by systems such as those described in U.S. Application No. 13/303,855, “Reverse NFA Generation and Processing,” published as U.S. Publication No. 2013/0133064 to Goyal et al., and U.S. Application No. 13/168,395, “Regular Expression Processing Automaton,” published as U.S. Publication No. 2012/0221497 to Goyal et al., all of which are incorporated herein by reference. NFA graph 320 is configured to match the pattern “ab{0,5}x.” “b{0,5}” matches anywhere from zero to five times for the ‘b’ in the pattern. Thus, the pattern matches the following payloads: ax, abx, abbx, abbbx, abbbbx, or abbbbx.

NFA graph 320 begins with node N0 302. After loading node N0 302, the graph walking engine is configured to determine whether the first segment (e.g., byte) of the payload matches 'a'. If so, the graph walking engine loads node N1 304 and the next segment of the payload, and if not, the graph walking engine returns a no match.

After loading node N1 304, if the next segment of the payload is 'x', the graph walking engine loads node N7 316, which is a marked node. This marked node indicates that a match was found within the payload, causing the graph walking engine to return a match. If the next segment of the payload is 'b', the graph walking engine loads node N2 306. If the next segment of the payload is anything other than 'x' or 'b', the graph walking engine determines that there is no match in the payload and returns a no match.

After loading node N2 306, if the next segment of the payload is 'x', the graph walking engine loads node N7 316, which is a marked node. This marked node indicates that a match was found within the payload, causing the graph walking engine to return a match. If the next segment of the payload is 'b', the graph walking engine loads node N3 308. If the next segment of the payload is anything other than 'x' or 'b', the graph walking engine determines that there is no match in the payload and returns a no match.

After loading node N3 308, if the next segment of the payload is 'x', the graph walking engine loads node N7 316, which is a marked node. This marked node indicates that a match was found within the payload, causing the graph walking engine to return a match. If the next segment of the payload is 'b', the graph walking engine loads node N4 310. If the next segment of the payload is anything other than 'x' or 'b', the graph walking engine determines that there is no match in the payload and returns a no match.

After loading node N4 310, if the next segment of the payload is 'x', the graph walking engine loads node N7 316, which is a marked node. This marked node indicates that a match was found within the payload, causing the graph walking engine to return a match. If the next segment of the payload is 'b', the graph walking engine loads node N5 312. If the next segment of the payload is anything other than 'x' or 'b', the graph walking engine determines that there is no match in the payload and returns a no match.

After loading node N5 312, if the next segment of the payload is 'x', the graph walking engine loads node N7 316, which is a marked node. This marked node indicates that a match was found within the payload, causing the graph walking engine to return a match. If the next segment of the payload is 'b', the graph walking engine loads node N6 314. If the next segment of the payload is anything other than 'x' or 'b', the graph walking engine determines that there is no match in the payload and returns a no match.

After loading node N6 314, if the next segment of the payload is 'x', the graph walking engine loads node N7 316, which is a marked node. This marked node indicates that a match was found within the payload, causing the graph walking engine to return a match. If the next segment of the payload is anything other than 'x', the graph walking engine determines that there is no match in the payload and returns a no match.

FIG3B illustrates an example embodiment of an NFA graph 370 used in the present invention. NFA graph 370 is configured to match the same pattern "ab{0,5}x" as in FIG3A . As described above, "b{0,5}" matches anywhere from zero to five times for the 'b' in the pattern. Thus, this pattern matches the following payloads: ax, abx, abbx, abbbx, abbbbx, or abbbbbbx.

Node N0 352 is a character node configured to match element 'a'. Node N1 354 is a variable count node configured to match element 'b' anywhere between '0' and '5' times. Variable count nodes can be configured to match a pair of elements any number of times, including an unlimited number of times. Node N2 356 is a character node configured to match element 'x'. Node N3 358 is a marker node configured to indicate the end of the pattern and to signal that a match has been found in the payload.

The graph walking engine loads node N0 352 from the NFA graph 370. The graph walking engine then processes the first segment of the payload. If the payload segment is 'a', the graph walking engine loads node N1 354. Otherwise, the graph walking engine returns a no match.

After loading node N1 354, the graph walking engine interprets the node as a variable count node that matches from 0 to 5 times for the character class 'b'. Starting from this node, the graph walking engine is configured to match this pattern in the payload and then loads the next node (node N2 356). Node N2 356 then determines whether the next segment of the payload is 'x'. If so, the graph walking engine loads node N3 358 (marker node) indicating that the pattern is a match. If not, the graph walking engine returns a mismatch. The following describes the specific details of the graph walking engine using the run stack to walk through the variable count nodes.

NFA graph 370 identifies the same pattern as NFA graph 320 of FIG 3A, but does so with fewer nodes.Thus, NFA graph 370 uses less memory and has reduced complexity.

Figure 3C is a diagram 380 showing an example embodiment of an NFA graph 390 illustrating other types of counting nodes. Fixed counting nodes search the payload segment a fixed number of times for an element, rather than using a range. For example, the pattern "ab{5}x" matches the payload "abbbbbx", but does not match "ax", "abx", "abbx", "abbbx", or "abbbbx". Similarly, variable counting matching patterns that start with a range other than zero can be converted to fixed counting patterns and then to variable counting patterns. For example, "ab{5,10}x" can also be expressed as "ab{5}b{0,5}x". The NFA graph 390 in Figure 3C shows such an equivalent pattern. As described above, this generates node N0 382 for matching against "a", node N1 384 for matching against "b" five times, variable count node N2 386 for matching against "b" from zero to five times, node N3 388 for matching against "x", and a marker node N4 389 to indicate that a match was found.

As an example embodiment of the present invention, each node stores an element, where an element is either a single 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, such as a variable count node storing the maximum (and optionally minimum) number of matches for each element and whether it is a lazy/greedy/possessive/full match type node, and a fixed count node storing the number of matches for each element.

4A is an example embodiment of an NFA graph 440 used by prior art systems. NFA graph 440 is configured to match the pattern "[aA][bB]", which matches payloads including "ab", "aB", "Ab", and "AB".

The graph walking engine first processes node N0 402. If the payload is "a," the graph walking engine loads node N1 404. The graph walking engine then processes the next segment of the payload. If the payload is "b," the graph walking engine loads node N3 408, which is a marked node. If the payload is "B," the graph walking engine loads node N4 410, which is also a marked node. Two marked nodes indicate that the graph walking engine returns a match.

On the other hand, if the graph walking engine processes a payload of "A" when processing node N0 402, the graph walking engine loads node N2 406. The graph walking engine then processes the next segment of the payload. If the payload is "b," the graph walking engine loads node N5 412, which is a marked node. If the payload is "B," the graph walking engine loads node N6 414, which is also a marked node. The two marked nodes indicate that the graph walking engine returns a match.

NFA graph 440 can even increase in complexity with short patterns such as "[aA][bB]". Even if each character class specifies only two values/characters/letters, each additional character class added to the pattern doubles the number of nodes in the graph. Furthermore, a character class can have any number of characters indicated, with more characters increasing the complexity of the graph even further.

In one embodiment, each character class can be stored in a 128-bit or 256-bit map. Each bit in the character class represents its corresponding ASCII value. For example, bit 12 in the bitmap represents the "new line" character. If bit 12 is 1, it means that the character class includes the "new line" character. If bit 12 is 0, the character class does not include the "new line" character. In the same way, each character class can store multiple ASCII values. For example, [^\n] (i.e., a character class with all characters except new line) marks all bits except bit 12 as "1". As another example, the character class [a-z] includes ASCII values 97–122. Therefore, the bitmap for the character class [a-z] will 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 into the character class. For example, when the character class is [a-z], suppose the graphics walking engine processes the letter "r," which has an ASCII value of 114. The graphics walking engine can access bit 114 of the character class and determine if it is set to determine if it matches the character class. This can be expressed as the following logic statement: "if (CharacterClass[PayLoadASCIIValue] == true), return match; else return nomatch," where PayLoadASCIIValue is the ASCII value of the current segment of the payload, or in this case, 114.

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(s). The compiler then assigns a unique number (e.g., an index or identifier) to each character class. For example, the compiler assigns [a-z] an index of 1, [0-9] an index of 2, and [^\n] an index of 3. Even though it appears twice, the character class [a-z] is stored once as a bitmap and can be accessed through its index "1."

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

In the context of an NFA graph, the "Element" field of each node with node type "Character Class" contains the character class number. Additionally, the "Element" field of a node with type "Variable Count" or "Fixed Count" can also contain the index of a character class, causing the graph walking engine to match that character class a variable or fixed number of times, respectively.

In addition, the compiler determines the character classes for all patterns. For example, the compiler may receive pattern one, "[a-z][0-9]", pattern two, "[a-z][^\n]", and pattern three, "[0-9][A-F]". Although patterns one, two, and three have six character classes in total, they only have four unique character classes. Therefore, 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 in the graph can access a character class by accessing its bitmap, regardless of the pattern or patterns in which it appears. This reduces the memory required to store all character classes.

During the walking process, the graph walking engine uses the element indicating the character class (of the node type character class) stored in the node as the first index and the payload segment (e.g., payload byte) as the second index of the specific character class bitmap. This loads specific bits of the two-dimensional matrix, where the bits loaded at the two index positions indicate whether the payload segment (e.g., payload byte) is within the specific character class.

Figure 4B is a diagram 450 showing an example embodiment of an NFA graph 470 with a dense matrix 472 (e.g., a bitmap table) of nodes and corresponding character classes used by the present invention. The NFA graph 470 is configured to match the pattern "[aA][bB]", which matches a payload including "ab", "aB", "Ab", and "AB". In this embodiment, the 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 index 0 to the character class [aA] and index 1 to the character class [bB], and both are stored as bitmaps in a two-dimensional matrix.

The character class matrix 472 shows a display of the character classes [aA] and [bB] at their respective indices. Character class 0 (i.e., [aA]) shows entries for setting "A" and "a," and character class 1 (i.e., [bB]) shows entries for setting "b" and "B." Other graphics using the same character classes can utilize these character classes, and the matrix can further include character classes that are different from other graphics. With respect to FIG. 21 , another example of a character class matrix is shown.

FIG22 is a table 2200 illustrating the format of a character class match node. Table 2200 includes a node type 2202, a match type 2204, an element 2206, a next node address 2208, and a count value 2210. For a character class match node, node type 2202 indicates the character class. Match type 2204 indicates that it is not applicable (e.g., a null value). Element 2206 indicates the character class index used to access the character class in the character class matrix. Next node address 2208 includes the address of the next node in the graph. Count value 2210 is not applicable for a character class match node.

Referring again to FIG. 4B , when reading node N0 452, the graph walking engine determines whether node N0 452 matches any value/character/letter in the specified character class, in this case, "a" or "A," and loads the first segment of the payload. The graph walking engine loads the node type of the node and the element of the node, where the node type indicates that it is a character class and the element of the node indicates that the character class has index 0. The graph walking engine then uses the current segment of the payload as an index into the bitmap (e.g., loading 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, as indicated by the values loaded from the bitmap at these indexed positions, the graph walking engine loads node N1 454 pointed to by the "next node address" stored in node N0 452.

When reading node N1 454, the graph walking engine determines whether node N1 454 matches any value/character/letter in the specified character class, in this case, "b" or "B", and loads the next segment of the payload. The graph walking engine loads the node type of the node and the element of the node, where the node type indicates that it is a character class and the element of the node indicates that the character class has an index of 1. The graph walking engine then uses the current segment of the payload as an index into the bitmap (e.g., loading Matrix[1][PayloadSegmentValue]) to determine whether the payload segment matches the character class. If the current segment of the payload is any value/character/letter in the specified character class, as indicated by the values loaded from the bitmap at these indexed locations, the graph walking engine loads the node pointed to by the "next node address" stored in node N1 454 (i.e., node N2 456). When loading node N2 456, based on the "node type" of node N2 456, the graph walking engine determines whether it is a marked node. The graph walking engine can then return a match.

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

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

Figure 23 is a table 2300 showing the format of a string match node. String node table 2330 includes a node type 2302, a match type 2304, an element 2306, a next node address 2308, and a count value 2310. Node type 2302 indicates "string match." Match type 2304 is not applicable (e.g., null value). Element 2306 indicates the address of string data 2340. Next node address 2308 includes the address of the next node in the graph. Count value 2310 indicates the length of the string.

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

A similar variation of the string node is a case-insensitive string node. In one example embodiment, a modifier preceding the string can indicate a case-insensitive string node in the pattern, such as "{i}abc", which will match the following payloads: "abc", "abC", "aBc", "aBC", "Abc", "AbC", "ABc", and "ABC". One of ordinary skill in the art will recognize that the modifier "{i}" can be any indicated symbol or series of symbols.

To handle case-insensitive string nodes (and case-insensitive character nodes), one of the alphabetic bits is masked before the comparison is performed. For example, the ASCII values for uppercase letters (A-Z) are between 65-90 and between 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. Therefore, only one bit differs between the two binary values (e.g., bit [5], if indexed from the least significant bit starting at 0). For each pair of corresponding case-insensitive alphabetic characters, the mask element and bit [5] in the payload segment (where the least significant bit of each is zero) are compared before the comparison. The comparison returns a match because the values are the same except for bit [5], which only represents the uppercase change. One of ordinary skill in the art will recognize that one or more bits other than bit [5] can be used as mask bits, for example, in other character schemes.

FIG4C is an example embodiment of a conventional graph 475 for the pattern “USPTO” using five separate nodes, each performing a value/character/letter check. Thus, the conventional graph 475 has a first node N0 476 that matches for a ‘U’, a second node N1 477 that matches for a ‘S’, a third node N2 478 that matches for a ‘P’, a third node N3 479 that matches for a ‘T’, a third node N4 480 that matches for an ‘O’, and a marker node N5 481 that indicates a match.

FIG4D shows an example embodiment of a graph 490 using string nodes. Node N0 492 is a string node that includes a pointer to the string "USPTO." Node N0 492 instructs the engine to match against the entire string "USPTO" rather than matching against each individual letter as in FIG4C and then loading the next node.

Figure 24 is a table 2400, which shows the format of a fixed count matching node. For a fixed count node, a node type 2402 indicates a fixed count matching 2402. Match type field 2404 is not applicable to a fixed count node. For a fixed count matching node, an element 2406 can indicate the character to be matched, or it can indicate the character class index to be matched. If the match is successful, then next node address 2408 comprises the address of the next node to be processed. Count value 2410 comprises the fixed number of times that the element is matched.

Figure 25 is a table 2500, which shows the format of a variable count matching node. This node comprises a node type 2502 indicating that a variable count matches. This node further comprises a matching type 2504 indicating whether the variable count node is lazy, greedy, possessive, or fully matched. Element 2506 can comprise the character for which matching is performed, or it can indicate the character class index for which matching is performed. If the match is successful, then next node address 2508 comprises the address of the next node to be processed. Count value 2510 comprises the maximum number of times that the element matches, which comprises special symbols for representing infinity.

Optionally, count value 2510 may also include a second count value for storing the maximum number of times an element must match (if no second count value is provided, it defaults to zero). This can be used to represent range matches. Such a pattern can also be represented by a combination of a fixed count node for matching an element a minimum number of times and a variable count node for matching the remaining number of times.

FIG5 is a diagram 500 illustrating an example embodiment of an NFA graph 510 illustrating an example embodiment of the present invention. NFA graph 510 is configured to detect the pattern "[^\n]*[zZ]b{5}," where [^\n] is a character indicating any value/character/letter except a newline character, and ["zZ"] is a character class indicating either "z" or "Z."

Node N0 502 is a variable count node. A variable count node can be either lazy, greedy, possessive (which is an optimized form of a greedy node), or a full match type node. When compiling a graph from a pattern, the node type is set. The user can indicate in the pattern which match node type the variable count node should be compiled as. Alternatively, depending on the desired graph behavior, the user can also set the compiler to default to any of the four modes. Assume that the graph walking engine processes the payload "yyyZbbbbbzyyyZbbbbb".

If node N0 502 is lazy, the graph walking engine finds the shortest possible path to the next node (node N1 504). That is, the graph walking engine processes the first instance of "z" or "Z" in the payload at node N1 504 rather than at node N0 502, even though node N0 502 elements include finding any payload segments other than line breaks that include "z" or "Z." However, if node N0 502 processes the payload in this manner, it will not utilize the shortest path through the graph.

When processing node N0 according to the variable count lazy node, the graph walking engine pushes the run stack entry of node N0 with zero payload offset to the run stack. After pushing the run stack entry, the graph walking engine extracts the next node N1 504. The graph walking engine extracts the next payload byte ('y') corresponding to the zero payload offset and attempts to match it with the element character class [zZ] of node N1 504. Because this byte does not match this character class, the graph walking engine pops up this run stack entry. Then, the graph walking engine processes the same byte with the popped stack entry containing node N0 502. Byte 'y' matches the character class [^\n], so it achieves a match. Then, the graph engine increments the payload offset by 1 and pushes the run stack entry containing node N0 502.

After pushing the run stack entry, the graph walking engine extracts the next node, N1 504. The graph walking engine extracts the next payload byte, 'y', corresponding to a payload offset of 1, and attempts to match it with the element character class [zZ] of node N1 504. Since the byte does not match the character class, the graph walking engine pops the run stack entry. The graph walking engine then processes the same byte with the popped stack entry containing node N0 502. The byte 'y' matches the character class [^\n], so it matches. The graph walking engine increments the payload offset by 1 and pushes the run stack entry containing node N0 502.

After pushing the run stack entry, the graph walking engine extracts the next node N1 504. The graph walking engine extracts the next payload byte ('y') corresponding to the payload offset of 2 and attempts to match it with the element character class [zZ] of node N1 504. Since the byte does not match the character class, the graph walking engine pops the run stack entry. The graph walking engine then processes the same byte with the popped stack entry containing node N0 502. The byte 'y' matches the character class [^\n], so it matches. The graph walking engine increments the payload offset by 1 and pushes the run stack entry containing node N0 502.

After pushing the run stack entry, the graph walking engine extracts the next node N1 504. The graph walking engine extracts the next payload byte ('Z') corresponding to the payload offset of 3 and attempts to match it with the element character class [zZ] of node N1 504. Since the byte matches the character class, the graph walking engine extracts the next node N2 506.

The graph walking engine then loads fixed-count node N2, which matches five times for 'b'. The graph walking engine then loads the next five segments of the payload, all of which are 'b'. The fixed-count node matches its element, which is also 'b'. After fixed-count node N2 506 matches, the graph walking engine then loads node N3 508, which is a marked node. A marked node indicates a match was found. If the copy bit is '1', the graph walking engine then pops all entries from the run stack and discards them. In this case, it discards the single entry in the run stack containing node N0 502 with a payload offset of 3. The copy bit is a flag bit. Upon reaching a marked node in the NFA graph (e.g., finding a match in the payload), any run stack entry with the copy bit marked (e.g., set to '1') can be popped from the run stack and discarded without further processing. If the copy bit is not marked (e.g., set to '0'), the run stack entry is not discarded upon being popped, but instead is processed to attempt to find additional matches (e.g., for a fully matched node).

With respect to FIG. 17 , handling variable count lazy nodes is described in more detail.

If node N0 502 is greedy, then the graph walking engine finds out the possible longest path to the next node (node N1 504). For example, the first "z" or "Z" in the payload does not necessarily mean processing node N1 504. Suppose that the graph walking engine processes the identical payload of "yyyZbbbbbzyyyZbbbbb". Although lazy node N0 502 returns "yyyZbbbbb" as a match, greedy node N0 502 returns "yyyZbbbbbzyyyZbbbbb". In other words, node N0 502 ignores the first possible match and continues to match the payload to find the longest possible match. In this way, matching the payload requires the graph walking engine to save its steps, for example, by pushing the node and offset of the payload position to the run stack. Like this, if the graph walking engine arrives at the payload end and does not find a match, it can pop up a node from the run stack to backtrack to match a possible match earlier.

In an example embodiment of the present invention, when processing greedy or possessive node N0 502, the graph walking engine loads the bytes of the payload and matches them against the elements until it finds a non-match or it runs out of payload. Because the character class is [^\n], which covers all values/characters/letters in the payload, the graph walking engine runs out of payload. The graph walking engine then pushes the node onto a run stack that includes a set copy bit, a payload offset, and a count indicating the number of bytes consumed when matching the element indicated in the variable count node (i.e., in this case, the count is 19). The graph walking engine then loads character class node N1 504, but since there are no bytes from the payload to consume, it returns a non-match.

The graph walking engine then pops the variable count node from the run stack and decrements the count by 1. The graph walking engine then pushes the node to the run stack including the set copy bit, the payload offset, and a count (18) indicating the number of bytes consumed. The graph walking engine then loads the character class node N1 504. The graph walking engine attempts to consume the 19th byte in the payload, which is a ‘b’, but this does not match the character class [zZ] of node N1 504. The graph walking engine then pops the run stack entry again. This is repeated until the count is reduced to the number of bytes consumed by node N1 504 that is a match, which is when the count is 13. When the count is 13, the variable count node effectively consumes “yyyZbbbbbzyyy”. Node N1 504 then attempts to consume the 14th byte, which is a “Z”, which is a match for the character class [zZ]. The graph walking engine then loads node N2 506. Node N2 consumes the next 5 “b”s in the payload. Then, the graph walking engine loads node N3 508, which is a marked node indicating that a match has been found. After processing marked node N3 508, the graph walking engine pops up and discards all run stack entries whose copy bit is set to 1, and in this case, there is only one such entry in the run stack. Therefore, the greedy node finds the longest match in the payload. Setting/not setting the copy bit is to separate the (marked) run stack entry pushed by the engine during runtime from the initial input buffer entry also present in the run stack, however, this can also be achieved in other ways. With respect to Figure 18, processing variable count greedy nodes is described in more detail.

If node N0 502 is owned, the graph walking engine finds the longest possible path to the next node, node N1 504. For owned nodes, the graph walking engine produces the same results as for greedy nodes above, but performs a more optimized process: as described in more detail with respect to FIG. 19 , it does not backtrack after reaching the end of the payload.

If node N0 502 is a variable count full match node, the graph walking engine finds all possible paths to the next node (node N1 504). The graph walking engine can return multiple matches for a variable count full match node. With respect to FIG. 20 , processing a variable count full match node is described in more detail.

FIG6A 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, which can be respectively divided into a string node (e.g., "ACME"), a variable-count node (e.g., "a*"), a fixed-count and variable-count node (e.g., "b{5,10}" which can be converted to "b{5}b{0,5}"), a fixed-count node (e.g., c{5}), and a character class (e.g., [def]).

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 graph 602, or corresponding graph segments 620, 622, 624, 626, and 628 thereof, and generates nodes 630, 632, 634, 636a-b, and 638 for a compiled NFA graph 640 assembled by graph assembly module 606 based on the graph.

In another embodiment, compiler 604 examines graph 602 element by element and element type rather than individual modules to perform a match for each element and node type.

FIG6B is a diagram 601 of a compiled NFA graph 640 generated by the pattern 602 of FIG6A . The compiled NFA graph 640 begins with a string node 650 that matches the string "ACME". 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 can be lazy, greedy, possessive, or full. Based on the grammar of the pattern, the node can be set to a lazy, greedy, possessive, or full match type. For example, if a metacharacter is followed by a second metacharacter "?", such as in the patterns "*?", "+?", "??", or "{n,m}?", the compiler can create a matching type lazy variable count node. If a metacharacter is followed by a second metacharacter "+", such as in the patterns "*+", "++", "?+", and "{n,m}+", the compiler can create a matching type possessive node. For example, if the metacharacter is followed by a second metacharacter "*", as in the patterns "**", "+*", "?*", and "{n,m}*", the compiler may create a matching type full variable count node.

For example, consider the payload "abbbbbbb". For the "ab*" pattern, a greedy match type variable count node is generated. The result is that the node consumes the entire payload, resulting in the result "abbbbbbb".

Similarly, for the "ab*+" pattern, a possessive match type variable count node is created. The possessive node has similar properties to the greedy node, but is configured not to backtrack after reaching the end of the payload. Again, the result is a variable count possessive node that consumes the entire payload without backtracking, resulting in "abbbbbbb," which is exactly the same as the greedy node.

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

For the "ab**" pattern, a full match type variable count node is created. As a result, all possible matches are found, such as "a", "ab", "abb", "abbb", "abbbb", "abbbbb", "abbbbb", "abbbbbb", and "abbbbbbb".

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

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

The graph can also match character classes that are part of a variable-count node or a fixed-count node. For example, the pattern "[xyz]{0,5}" compiles to a variable-count node that matches the character class [xyz] from zero to five times. For example, "xyzzx" is a payload that matches this pattern.

Fig. 7 is a block diagram 700 showing an example embodiment of compiling a pattern 702. A pattern determination module 703 performs a matching item check on the pattern 702. The matching item includes an element and a node type. If the pattern determination module 703 finds a matching item, it outputs the matching item to a node generation module 708 as an element 704 and a node type 706. If the pattern determination module 703 does not find a matching item, it indicates that the pattern is finished, and the pattern determination module 703 can consume another pattern, or if there are no more patterns, the compilation is completed. The node generation module 708 generates a dense node 710 including an element 704 and a node type 706. The element can be a value/character/letter, a character class, or a string, and the node type can be a value/character/letter, a character class, a variable count, a fixed count, a variable count and a fixed count, a string, or a separation node (for alternation) or a marked node (used as the final node of the graph) for announcing a match.

FIG8 is a flow chart 800 illustrating an example embodiment of compiling a pattern. Compilation begins by checking the pattern for a match, including elements and node types (802). The method then determines whether a match is found (804). If a match is found, the method generates a node indicating the node type and element (806). If not, the method ends (808) and optionally compiles another pattern.

Figure 9 is a flowchart 900 illustrating an example embodiment of a graph walking engine processing a node. The graph walking engine extracts the node type and element from the node (902). As described above, the element can be a value/character/letter, a character class index, or a string value. The graph walking engine then determines whether the node needs to continue matching with the same element (904). The graph walking engine can, for example, track the number of elements it has matched for a variable count node or a fixed count node by using an index or a count variable. If the node type indicates that the element should continue matching, the graph walking engine matches the payload segment with the element (906). The graph walking engine then determines whether the payload segment matches the element (910). If so, it determines that the node needs to continue matching (904). If the node type does not indicate that the node should continue matching, the graph walking engine returns a match or no match for the node (908) and can be used to process the next node in the graph.

If the payload segment does not match the element (910), however, the graphics walking engine returns no match (912).

Figure 10 is a block diagram 1000 illustrating an example embodiment of a graph walking engine processing nodes 1004a-d of an NFA graph 1002. A determination module 1006 receives an NFA graph 1002 including nodes 1004a-d. NFA graph 1002 may include any number of nodes 1004a-d. Furthermore, in one embodiment, determination module 1006 may receive individual nodes 1004a-d. Determination module 1006 outputs a node type 1008 and an element 1010 to a matching module 1011. Based on the node type 1008, matching module 1011 matches one or more payload segments 1014 against the element 1010. Matching module 1011 may receive one or more additional segments 1014 based on the node type 1008, such as variable-count nodes or fixed-count nodes configured to match one or more payload segments. Upon completion of processing, matching module 1011 outputs a match or mismatch 1012. Optionally, matching module 1011 may request determination module 1006 to process the next node of NFA graph 1002. Matching module 1011 may further process earlier or later payload segments and earlier or later nodes of the NFA graph.

FIG11 is a flow chart 1100 illustrating a process for walking an NFA graph used in the present invention. In one embodiment, the elements performing this process may be the same as those described with respect to block diagram 250 shown in FIG2B .

The graphics walk engine 252 includes a plurality of memories that store a run stack 260 for storing the path of the steps through other parts of the graphics and a save buffer/stack 264 for storing a save buffer/stack 264 when the payload is processed with only a partial match, so that when the next payload of the same stream is loaded, the engine can reload the stack entries from the save buffer into the run stack. In one embodiment, the run stack 260 or save buffer 264 can be maintained as a circular buffer in the on-chip memory, and it can overflow to the external system memory, but other stack implementations and memory types can be used. In addition, when the next instruction is fed to the engine to process the subsequent payload of the same stream, the host can copy (move) the entries from the save buffer into the run stack (input buffer).

The run stack 260 pushes stack entries to the head pointer and pops stack entries from the head pointer. The save buffer/stack queues the stack entries at its tail pointer. Because the save buffer/stack 264 queues the entries 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 for the initial run stack (e.g., input from input buffer 258 of Figure 2B). The host may also provide an initial instruction (e.g., from instruction queue 254). The walk instruction contains the following stack-related information: (1) the run stack head pointer; (2) the save stack tail pointer; (3) the number of run stack entries; and (4) the run stack and save stack sizes in terms of the number of entries.

In an example embodiment of the present invention, the run stack entry includes a field indicating a node type field, a copy field, a reverse processing field, a payload offset field, a type specific data field, and an address field. If the node type is "NOP" (for example, no operation (No-op)), the graph walking engine discards the run stack entry and pops out the next run stack entry to be processed. If the node type is extraction (Fetch), the run stack entry does not include node information, and the type specific data field is invalid. If the type is any type (for example, fixed character, variable count, separation node, string node, character class, character, or mark node) except "NOP" or Fetch, the run stack entry itself includes the node information in the type specific data field. The following table has listed possible node types.

The Copy field is used to separate the run stack entries pushed by the graph walk engine during runtime from the initial input buffer entries also present in the same run stack. The Reverse field indicates whether the payload offset should be incremented or decremented after processing the current node. This allows payloads 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 a payload matches when processing a stack entry, the Address field contains the address of the next node to be extracted.

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

The save buffer/stack 264 allows the graphics walking engine to save partial matches, for example, when the graphics walking engine reaches the end of a payload. When a subsequent payload of the same stream is loaded, the engine copies the stack entry from the save buffer/stack 264 to the run stack 260. In another embodiment, after providing the next instruction to the graphics walking engine, the host software of the host device can copy the contents of the save stack to the input stack. In this embodiment, because the graphics walking engine is managed by the host software, it is unaware of the packet stream or subsequent packets in that stream. FIG11 illustrates an example embodiment of a system that uses a run stack and a save stack, however, other implementations are contemplated by those skilled in the art.

The process begins by initiating a graphics walk (1102). The process then determines whether a 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 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 data structure, so the entry popped from the run stack (e.g., run stack 260) is the most recently pushed entry into the run stack (e.g., run stack 260).

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

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

FIG12 is a flowchart 1200 illustrating an example embodiment of processing a node. Flowchart 1200 is an extension of the process a node (1118) of FIG11.

The graph walking engine begins processing the node (1202). The graph walking engine determines whether the node is a dense node (1204). If it is not a dense node, the graph walking engine processes the node as a non-dense NFA node (e.g., a character node, a separation node, or a label node) (1214). The graph walking engine then returns (1224).

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

If the node is not a character node (1206), the graph walking engine determines whether the node is a string node (1208). If so, the graph walking engine processes the node as a string node (1218). Processing string nodes is described in more detail with respect to FIG. 14. The graph walking engine then returns (1224).

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

With respect to FIG12 , if the node is not a fixed-count node ( 1210 ), the graph walking engine determines whether the node is a variable-count node ( 1211 ). If so, the graph walking engine processes the node as a variable-count node ( 1222 ). Processing variable-count nodes is described in further detail with respect to FIG16 . The graph walking engine then returns ( 1224 ). If the graph walking engine determines that the node is a variable-count node ( 1211 ), it returns an error code ( 1226 ).

The graph walking engine may use other embodiments for processing the node. For example, the graph walking engine may determine the type of the node by examining each node type in a different order.

FIG13 is a flow chart 1300 illustrating an example embodiment of processing a character class node. The format of a character class node is described above with respect to FIG22. With respect to FIG13, flow chart 1300 is an extension of the processing of a character class node (1216) described in FIG12.

Figure 26 is table 2600, has shown the example embodiment of the stack entry that is pushed in the context that character class node type is processed.This stack entry comprises the stack entry type 2602 of indication character class coupling, the element 2606 of indication character class index and the next node address 2608 of the next node in indication graph.This stack entry further comprises copy bit 2612, reverse bit 2614 (indication graph whether will walk in reverse) and the offset 2616 of indication next byte with processing in payload.This stack entry further comprises matching type 2604 and count value 2610, and both of these indicate that they are not applicable.The character class stack entry is only queued in the preservation buffer/stack, and is not pushed to the run stack, because it is not necessary to be pushed to the run stack.

With reference to FIG13 , the graphics walking engine begins processing the character class node ( 1302 ). The graphics walking engine loads the character class index from the character class node (e.g., element 2206 in FIG22 ) and uses the character class index to read the bitmap/mask stored in the two-dimensional matrix ( 1304 ). The graphics walking engine then checks to see if there is at least one more byte in the payload to process ( 1306 ).

If there is at least one more byte, the graph walk engine extracts the next byte (or other data size) from the payload (1308). The graph walk engine uses the byte of the payload to access the bit of the bitmap/mask (or other data size) and determines whether the bit is set (1310). If the bit is set, the graph walk engine determines that the byte of the payload matches the character class represented by the node and returns (1312). If the bit is not set (1310), the graph walk engine sets the terminate 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 instead of extracting the next node of the graph.

In other aspects, if the graph walking engine determines that there are no more payloads to process (1306), the graph walking engine pushes the node to a save buffer/stack so that matching can be resumed for subsequent packets of the same flow (1316). The graph walking engine then sets the terminated walk bit in the result to "true" (1314) and then returns (1312).

FIG14 is a flowchart 1400 illustrating an example embodiment of a graph walking engine processing a string node. As described above with respect to FIG23 , the format and string data of a string node are illustrated. With respect to FIG14 , flowchart 1400 is an extension of the string node processing (1218) described with respect to FIG12 .

Figure 27 is a table 2700 showing an example embodiment of a stack entry for a string match 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 run 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 to be processed in the payload. The stack entry further includes a match type 2704 indicating that it is not applicable. For the string match type, the stack entry is queued to the save buffer/stack because it does not need to be pushed to the run stack.

With respect to Figure 14, the graph walking engine begins processing the string node (1402). The graph walking engine loads string data, which includes the length of the string from the node (e.g., count 2310 of string node 2330 of Figure 23), determines the number of available bytes in the payload (or other data size), and determines whether the number of available bytes in the payload is equal to or greater than the length of the string (1404). If so, the graph walking engine sets the "match length" to the "string length" (1406). Alternatively, the graph walking engine sets the "match length" to the number of available payload segments. The "match length" is the number of bytes of the string to be matched with the payload. If the match length is less than the string length (1404), the match length is set to the number of available bytes (1405), so that the string can be partially matched, and continues to match with subsequent data packets.

After setting the match length, (1405 or 1406), the graph 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 Figure 23) (1408). The string data node includes the actual string element to be compared with the payload segment (e.g., element 2316 of string data 2340 of Figure 23). The graph walk engine then compares the number of extracted payload segments with the number of the same string bytes in parallel (1410). The node then determines whether the "match length" bytes of the payload match all the extracted string bytes (1412). If not, the graph 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, the graph walk engine determines whether the match length is the same as the string length (1414).

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

Figures 15A and 15B are flow charts 1500 and 1501 illustrating an example embodiment of processing a fixed count node. The format of a fixed count node was described above with respect to Figure 24. With respect to Figures 15A-B, flow charts 1500 and 1501 are extensions of the processing of a fixed count node (1220) described with respect to Figure 12.

FIG28 is a table 2800 illustrating an example embodiment of a stack entry for a 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 the next node in the graph, and a count value 2810 indicating the remaining count of bytes to be matched. The stack entry further includes a copy bit 2812 indicating whether the node in the run stack is a copy, a reverse bit 2814 indicating whether the graph is to be walked in reverse, and an offset bit 2816 indicating the offset of the next byte to be processed in the payload. The stack entry further includes a match type 2804 indicating that it is not applicable. For a fixed count match type, stack entries are queued to a save buffer/stack because they do not need to be pushed to the run stack.

With respect to FIG15A , the graph walking engine begins processing a fixed count node ( 1502 ). The graph walking engine reads the "count" stored in the node (e.g., count value 2410 in FIG24 ) ( 1504 ). The count stored in the node represents the number of times a character or character class is to be matched with the payload. For example, for the fixed node derived from the partial pattern "b{5}," since the character 'b' is to be matched with the payload five times, the count is 5.

The graph walk engine then determines if there are a "count" number of bytes available in the payload (1506). If so, the graph walk engine sets the match length to "count" (1510). Alternatively, the graph walk engine sets the match length to the number of available payload segments. The "match length" is the number of bytes of the fixed count pattern that are 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 partially matched, and matching continues with subsequent packets of the same flow. After setting the match length (1508 or 1510), the graph walk engine extracts a "match length" number of bytes from the payload (1512).

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

After determining whether the node is a fixed-count character class node or a fixed-count character node (1514) and responding to the determination (1516 and 1518 or 1520, respectively), the graph walk engine determines, with reference to flowchart 1501 of FIG15B, whether the "match length" number of bytes of the payload matches the character or character class (1522). If so, the graph walk engine determines whether the match length is the same as the count of the fixed-count node (1524). If so, the graph walk engine returns (1530). If not, the graph walk engine pushes the stack entry (FIG. 28) to the save buffer/stack so that the remaining "count" bytes of the subsequent payload from the same stream match the remaining fixed-count node element (1526), sets the end-of-walk bit of the result to true (1528), and returns (1530).

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

FIG16 is a flowchart 1600 illustrating an example embodiment of processing a variable count node. The format of a variable count node is described above with respect to FIG25. With respect to FIG16, flowchart 1600 is an extension of the processing of a variable count node (1222) described with respect to FIG12.

Figure 29 is a flow chart 2900 showing an example embodiment of a stack entry for a variable count match type. This 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 the next node in the graph, and a count value 2910 indicating the remaining count of bytes to be matched. This stack entry further includes a copy bit 2912 indicating whether the node in the run stack is a copy, a reverse bit 2914 indicating whether the graph is to be walked in reverse, and an offset bit 2916 indicating the offset of the next byte to be processed in the payload. This stack entry further includes a match type 2904 indicating whether the node is lazy, greedy, possessive, or a fully matched node. This stack entry can be pushed and popped onto the run stack, or, when the payload is exhausted, can be copied from the run stack to a save buffer/stack.

With reference to FIG16 , the graph walking engine begins processing the variable count node ( 1602 ). The graph walking engine loads the match type 2504 of FIG25 and determines whether the node match type is lazy ( 1604 ). If so, it processes the variable count lazy node ( 1614 ), as further explained in FIG17 . The graph walking engine then returns ( 1622 ).

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

If not, the graph walking engine determines whether the node is a possessive match type (1608). If so, it processes the variable count possessed node (1618), which is explained in further detail in Figure 19. The graph walking engine then returns (1622).

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

FIG17 is a flowchart 1700 illustrating an example embodiment of processing a variable-count lazy node. The format of a variable-count node was described above with respect to FIG25 , and the format of a variable-count stack entry was described above with respect to FIG29 . With respect to FIG17 , flowchart 1700 is an extension of the processing of a variable-count lazy node ( 1614 ) described with respect to FIG16 .

The graph walking engine begins processing the variable count lazy node (1702). The graph walking engine determines whether the node is read from a run stack entry (1704). If the node is not read from a run stack entry, this means that the node is being processed for the first time. The graph walking engine determines whether the count (e.g., count value 2510 in FIG. 25 ) is greater than zero, and if it is, it pushes a run stack entry ( FIG. 29 , 2900 ) with all relevant information filled as explained above, with its copy bit set to “1” (e.g., copy bit 2912 in FIG. 29 ) (1706). The graph walking engine then returns (1724). The pushed run stack entry allows the graph walking engine to remember its return path and continue walking to the next node at the next node address (e.g., 2508 in FIG. 25 ). If a match is found when walking the next node path, the copy bit is set to “1” to allow the node to be popped and discarded from the run stack. If no match is found, then when these nodes are popped from the run stack, they can be processed.

If the node was read from a running stack entry (1704), the graph walking engine determines whether there are at least one more byte in the payload to be processed (1708). If there are no more bytes in the payload, the graph walking engine pushes the stack entry (Figure 29, 2900) with the node information to a save buffer/stack (1710), sets the terminated walk bit of the result to "true" (1712), and returns (1724). Pushing the node to the save buffer/stack (1710) saves the progress of the match so that when the graph walking engine processes subsequent packets belonging to the same application flow, it can load the previous match progress from the save buffer/stack and resume the match.

If the payload is not exhausted (i.e., if there is at least one byte of the payload to be processed), the graph walking engine determines whether the variable count node is a character class node or a character node by checking element 2906 of Figure 29 (1714). If the variable count node is a variable count character class node, it uses the character class index stored in element 2906 of Figure 29 in the variable count character class node to read the bitmap/mask (1720). The graph walking engine then extracts a byte from the payload and compares the byte to the corresponding entry in the bitmap/mask by using the byte from the payload as an index into the bitmap/mask (1722). If the entry is set, the graph walking engine determines a match.

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

Determine 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 walk 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), and if the count is greater than zero, pushes a run stack entry (e.g., 2900 of FIG. 29 ) with the copy bit (e.g., copy bit 2912 of FIG. 29 ) set (1706) and returns (1724). If the count is equal to zero, the entry is not pushed into the run stack. Alternatively, the graphics walk engine sets the terminate walk bit in the result to "true" (1712) and returns (1724).

FIG18 is a flowchart 1800 illustrating an example embodiment of processing a variable-count greedy node. The format of a variable-count node was described above with respect to FIG25 , and the format of a variable-count stack entry was described above with respect to FIG29 . With respect to FIG18 , flowchart 1800 is an extension of the processing of a variable-count greedy node (1616) described with respect to FIG16 .

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

If the run stack entry has not been read from the run stack (i.e., the node is being processed for the first time), the graph walk engine determines whether the variable count node is a variable count character class node or a variable count character node by checking element 2506 of Figure 25 (1810). If the variable count node is a variable count character class node, it reads the bitmap/mask corresponding to the character class index stored in the variable count character class node by reading element 2506 of Figure 25 (1814). The graph 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 into the bitmap/mask until there is a mismatch, there are no more available bytes in the payload, or the number of bytes matched equals the count value (2510 of Figure 25) (1816). The graph walk engine then assigns the available count to be stored (2910 of Figure 29) to 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 copies the run stack entry with the bit set to 1 (2900 of FIG. 29 ) ( 1808 ). If the count of the run stack entry is equal to zero, the graphics walk engine does not push the run stack entry. The graphics walk engine then returns ( 1818 ).

If the node is a variable count character node, the graph walking engine extracts bytes from the payload and matches them against 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 ) ( 1812 ). The graph walking engine then allocates the 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 ).

FIG19 is a flowchart 1900 illustrating an example embodiment of processing a variable-count owned node. The format of a variable-count owned node was described above with respect to FIG25 , and the format of a variable-count stack entry was described above with respect to FIG29 . With respect to FIG19 , flowchart 1900 is an extension of the processing of a variable-count owned node (1618) described with respect to FIG16 .

With reference to FIG19 , the graph walking engine begins processing a variable count node ( 1902 ). The graph walking engine determines whether the node is a variable count character class node or a variable count character node ( 1904 ) by examining element 2506 of FIG25 . If the node is a variable count character class node, it reads the bitmap/mask corresponding to the character class index stored in the variable count character class node element ( 2506 of FIG25 ). The graph walking engine then extracts bytes from the payload and compares them to corresponding entries in the bitmap/mask by using the bytes from the payload as indices into the bitmap/mask 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 FIG25 ).

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

After matching the bytes from the payload to the character class or value/character/letter (1916 or 1906, respectively), the graph walking engine determines whether there are any remaining bytes in the payload (1908). If the graph walking engine has exhausted the payload (i.e., no bytes remain) (1908), the graph walking engine pushes the node to the save buffer/stack (1910), sets the terminated walk bit to true (1912), and returns (1918). If the graph walking engine has not exhausted the payload (i.e., there are remaining bytes) (1908), the graph walking engine returns (1918).

FIG20 is a flow chart 2000 illustrating an example embodiment of processing a variable count full match node. The format of a variable count node is described above with respect to FIG25. With respect to FIG20, flow chart 2000 is an extension of the processing of a variable count full match node (1620) described with respect to FIG16.

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

If the node is read from the run stack (2004), the graph walking engine determines whether it has exhausted its payload (e.g., whether there are no bytes remaining in the payload) (2005). If not, or if there are bytes remaining in the payload, the graph walking 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, the graph walking engine reads the bitmap/mask corresponding to the character class index stored in the variable-count character class node (2012). The graph walking 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 into the bitmap/mask (2014).

If the node is a variable count character node, the graph walking engine extracts a byte from the payload and matches it with 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 graphics walk engine decrements a count (i.e., count value 2910 of FIG. 29 ) by 1 (2022). If the count is greater than zero, the graphics walk engine pushes a run stack entry ( FIG. 29 , 2900) with the copy bit ( FIG. 29 , 2912) not set (e.g., set to 0) (2007) and returns (2020). If the count is equal to zero, the graphics walk engine does not push any stack entry and returns (2020). If there is no match, the graphics walk engine sets the terminate walk bit to true (2018) and returns (2020).

If the graph walking engine has run out of payload, or has no payload bytes remaining (2005), the graph walking engine pushes the node to the save buffer/stack (2016). The graph walking engine then sets the terminated walk bit to true (2018) and returns (2020).

FIG21 is a table 2100 showing 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 an ASCII value 2106. In an embodiment implementing a character class table, a memory may store the value of the character class index 2102, the character class definition 2104, or the ASCII value 2106; however, they are shown here to show how these character class definitions relate to the character class matrix and how these indexes can access the character class matrix. FIG21 shows five character class definitions as only one example embodiment. Other embodiments may include different kinds of character classes, and the number of unique character classes may be any number.

The [^\n] character class, assigned character class index 1, is converted to match every character except newline because the "^" operator produces the inverse of whatever follows it, and "\n" indicates a newline. Therefore, every bit in the bitmap/mask is set to "1" except for the ASCII value corresponding to newline, which is 12. Therefore, a node processing a byte with a value of 12 accesses this character class CharacterClassMatrix[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, which is assigned character class index 2, is converted to match every character in the range of 'a' to 'z'. Therefore, in the bitmap/mask corresponding to character class index 2, the values from 97 to 122 are set to "1" and all other values are set to "0". Therefore, the node processing the payload segment representing the ASCII value "c" accesses the character class matrix [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, for this character class, payloads outside the range of 97-122 do not match. For example, if the payload is the number "4", the node accesses the character class matrix [2][52], which has a value of "0", which indicates a mismatch.

The [^a-z] character class assigned character class index 3 is converted to match every value/character/letter except those in the range of 'a' to 'z'. Therefore, in the bitmap/mask corresponding to character class index 3, the values from 97 to 122 are set to "0" and all other values are set to "1". Therefore, the node processing the payload segment representing the ASCII value "c" accesses the character class matrix [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, for this character class, payloads outside the range 97-122 are matches. For example, if the payload is the number "4", the node accesses the character class matrix [3][52], which has a value of "1", which indicates a match.

The [0-9] character class, which is assigned character class index 4, is converted to match every value/character/letter in the range of '0' to '9'. Therefore, in the bitmap/mask corresponding to character class index 4, values from 48 to 57 are set to "1" and all other values are set to "0". Therefore, the node processing the payload segment representing the ASCII value "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, for this character class, payloads in the range 48-57 are matches. 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, which is assigned character class index 5, is converted to match the individual values/characters/letters "A", "B", "C", "a", "b", and "c". Therefore, in the bitmap/mask corresponding to 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". Therefore, the node processing the payload segment representing the ASCII value "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, for this character class, the values 65, 66, 67, 97, 98, and 99 do not match. 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, this character class matrix can be used for any data type or data length.In the above-described embodiment, these payloads are characters, which can be 7 or 8. However, data of any length can be used and it does not necessarily have to be in the form of characters. Other data encodings can be used. Examples of other applications of this type of table 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 invention has been particularly shown and described with reference to example embodiments thereof, it will be understood by those skilled in the art that various changes in form and details may be made therein without departing from the scope of the invention as encompassed by the appended claims.

Claims (50)

1. A method for compiling a drawing into a nondeterministic finite automaton (NFA) diagram, the method comprising: The pattern is checked for multiple elements and various node types. Each node type corresponds to an element that represents a character, character class, or string. Multiple nodes are generated to form an NFA graph. Each of these nodes is configured to match one of the multiple elements and store the node type corresponding to that element, the address of the next node in the NFA graph, a count value, and the element, wherein the address of the next node and the count value are applicable based on the stored node type. 2. The method of claim 1, wherein the node type is one of the following: variable count, fixed count, fixed and variable count, case-sensitive character, case-insensitive character, character class, case-sensitive string, case-insensitive string, marked or separated, wherein a marked node is a node indicating a matching pattern found in the payload, and wherein a separated node is a node indicating a choice between two paths in the pattern. 3. The method of claim 2, wherein if the node type is a variable count, the node further indicates an element type that is a character, character class, or string node. 4. The method of claim 2, wherein if the node type is a fixed count, the node further indicates an element type that is a character, character class, or string node. 5. The method of claim 1, wherein performing the node type check on the pattern comprises matching the pattern against at least one of the following node type indications: variable count node type, fixed count node type, fixed-variable count node type, case-sensitive character node type, case-insensitive character node type, character class node type, string node type, case-insensitive string node type, marker node type, and split node type, wherein the marker node is a node indicating that a match of the pattern has been found in the payload, and wherein the split node is a node indicating a choice between two paths in the pattern. 6. The method of claim 1, wherein the plurality of node types includes a string node type that represents a portion of a pattern of plurality of values. 7. The method of claim 1, wherein the plurality of node types includes a string node type, and wherein performing the string node type check on the pattern includes determining that a portion of the pattern indicates a plurality of consecutive values. 8. The method of claim 1, wherein the plurality of node types includes a variable count node type, the variable count node type representing a portion of the pattern in which a variable number of matches are performed for an element. 9. The method of claim 1, wherein the plurality of node types includes a variable count node type, and wherein performing the variable count node type check on the pattern includes determining that a portion of the pattern indicates a variable number of matches for the element. 10. The method of claim 9, wherein the variable number is a finite number or an infinite number. 11. The method of claim 10, wherein the pattern includes a symbol representing infinity, the symbol being used to trigger determining a portion of the pattern indicating that the element is matched an infinite number of times. 12. The method of claim 1, wherein the plurality of node types includes a fixed-count node type, the fixed-count node type representing a portion of the pattern in which a fixed number of matches are performed for an element. 13. The method of claim 1, wherein the plurality of node types includes a fixed-variable count node type, the fixed-variable count node type representing a portion of the pattern in which an element is matched a fixed number of times and then matched a variable number of times. 14. The method of claim 1, wherein the plurality of node types includes a fixed-variable count node type, and wherein performing the fixed-variable count node type check on the pattern includes determining a portion of the pattern indicating that the element should be matched at least once and at most a finite number of times or an infinite number of times. 15. The method of claim 14, wherein the pattern includes a symbol representing infinity, the symbol being used to trigger determination of a portion of the pattern indicating that the element is matched an infinite number of times. 16. The method of claim 1, wherein the plurality of node types includes a character node type, the character node type representing a portion of the pattern that is matched against an element by using a Boolean OR operation on at least one value. 17. The method of claim 16, further comprising storing each character class as a mask, wherein if each character in the mask is part of the character class, the character is set, and if it is not part of the character class, it is not set. 18. The method of claim 17, wherein the element of the node includes a character class index corresponding to a unique character class. 19. The method of claim 18, wherein the character class index and the payload segment are used as an index of the mask, such that if the indexed entry is set, the payload is determined to match the character class. 20. The method of claim 1, wherein the plurality of node types includes a variable-count node type, the variable-count node type further indicating that the node is a greedy node, a lazy node, a possessive node, or a full-match node, wherein nodes of the variable-count type of greedy matching and possessive matching match match for the longest match in the payload, wherein nodes of the variable-count type of lazy matching match match for the shortest match in the payload, and wherein nodes of the variable-count type of full-match node match match for all matches in the payload. 21. The method of claim 1, wherein the plurality of node types includes a character-type node type, and wherein checking the node type and the element of the pattern includes identifying at least a portion of the pattern as the character-type node type and the corresponding element. 22. The method of claim 21, wherein checking the node type and element of the pattern includes identifying at least two portions of the pattern as a character-type node type and a corresponding element, and further includes: Generate a bitmap for each of these parts, where each bit in the bitmap represents a value that matches the element, and each bitmap is associated with a unique character class index. 23. The method of claim 22, further comprising associating the first and second portions with the same bitmap if the first portion of the at least two portions and the second portion of the at least two portions have the same corresponding element. 24. The method of claim 23, wherein inspecting the drawing includes inspecting a plurality of drawings, wherein the first and second portions are in separate drawings. 25. The method of claim 1, wherein inspecting the pattern includes finding at least one metacharacter, and generating the plurality of nodes includes determining at least one of the node type or the count value based on the at least one metacharacter. 26. A computer system for compiling drawings into nondeterministic finite automata (NFA) graphics, the system comprising: A pattern determination module is configured to perform multiple element and node type checks on the pattern, each node type corresponding to an element representing a character, character class, or string; and A node generation module is configured to generate multiple nodes of an NFA graph. Each of the multiple nodes is configured to match one of the multiple elements and store the node type corresponding to that element, the address of the next node in the NFA graph, a count value, and the element, wherein the address of the next node and the count value are applicable based on the stored node type. 27. The system of claim 26, wherein the node type is one of the following: variable count, fixed count, fixed and variable count, case-sensitive character, case-insensitive character, character class, case-sensitive string, case-insensitive string, marked or separated, wherein a marked node is a node indicating a matching pattern found in the payload, and wherein a separated node is a node indicating a choice between two paths in the pattern. 28. The system of claim 27, wherein if the node type is a variable count, the node further indicates an element type that is a character, character class, or string node. 29. The system of claim 27, wherein if the node type is a fixed count, the node further indicates an element type that is a character, character class, or string node. 30. The system of claim 26, wherein the pattern determination module is further configured to match the pattern against at least one of the following node types: variable count node type, fixed count node type, fixed-variable count node type, case-sensitive character node type, case-insensitive character node type, character class node type, string node type, case-insensitive string node type, marker node type, and split node type, wherein the marker node is a node indicating a matching pattern found in the payload, and wherein the split node is a node indicating a selection between two paths in the pattern. 31. The system of claim 26, wherein the plurality of node types includes a string node type that represents a portion of a pattern of plurality of values. 32. The system of claim 26, wherein the pattern determination module is configured to determine that a portion of the pattern indicates a plurality of consecutive values. 33. The system of claim 26, wherein the plurality of node types includes a variable-count node type, the variable-count node type representing a portion of the pattern in which a variable number of matches are performed for an element. 34. The system of claim 26, wherein the plurality of node types includes a variable-count node type, and wherein the pattern determination module is configured to determine the variable-count node type by determining a portion of the pattern indicating a variable number of matches for the element. 35. The system of claim 34, wherein the variable number of times is a finite number of times or an infinite number of times. 36. The system of claim 35, wherein the pattern includes a symbol representing infinity, the symbol being used to trigger determination of a portion of the pattern indicating that the element is matched an infinite number of times. 37. The system of claim 26, wherein the plurality of node types includes a fixed-count node type, the fixed-count node type representing a portion of the pattern in which a fixed number of matches are performed for an element. 38. The system of claim 26, wherein the plurality of node types includes fixed-count and variable-count node types, the fixed-count and variable-count node types representing a portion of the pattern in which an element is matched a fixed number of times and then matched a variable number of times. 39. The system of claim 26, wherein the pattern determination module is further configured to determine a portion of the pattern indicating that the element is matched at least once and at most a finite number of times or an infinite number of times. 40. The system of claim 39, wherein the pattern includes a symbol representing infinity, the symbol being used to trigger determination of a portion of the pattern indicating that the element is matched an infinite number of times. 41. The system of claim 26, wherein the plurality of node types includes a character-type node type, the character-type node type representing a portion of the pattern that is matched against an element by using a Boolean OR operation on at least one value. 42. The system of claim 41, further comprising a character class storage module configured to store each character class as a mask, wherein if each character in the mask is part of the character class, the character is set, and if it is not part of the character class, it is not set. 43. The system of claim 42, wherein the element of the node includes a character class index corresponding to a unique character class. 44. The system of claim 43, wherein the character class index and the payload segment are used as an index of the mask, such that if the indexed entry is set, the payload is determined to match the character class. 45. The system of claim 26, wherein the plurality of node types includes a variable-count node type, the variable-count node type further indicating that the node is a greedy node, a lazy node, a possessive node, or a full node, wherein nodes of the variable-count type of greedy matching type and possessive matching type match for the longest match in the payload, wherein nodes of the variable-count type of lazy matching type match for the shortest match in the payload, and wherein nodes of the variable-count type of full node matching type match for all matches in the payload. 46. The system of claim 26, wherein the plurality of node types includes a character-type node type, and wherein the pattern determination module is configured to identify at least a portion of the pattern as the character-type node type and the corresponding element. 47. The system of claim 46, wherein the pattern determination module is configured to identify at least two portions of the pattern as a character class node type and corresponding elements and to generate a bitmap for each of these portions, wherein each bit in the bitmap represents a value matching the element, and each bitmap is associated with a unique character class index. 48. The system of claim 47, wherein the pattern determination module is configured to associate the first and second portions with the same bitmap if the first portion of the at least two portions and the second portion of the at least two portions have the same corresponding element. 49. The system of claim 48, wherein the pattern determination module is configured to inspect a plurality of patterns, wherein the first and second portions are in separate patterns. 50. The system of claim 26, wherein the pattern determination module is further configured to find at least one metacharacter, and the node generation module is configured to generate the plurality of nodes by determining at least one of node type or count value based on the at least one metacharacter.