Regular expression search operations are employed in various applications including, for example, intrusion detection systems (IDS), virus protections, policy-based routing functions, internet and text search operations, document comparisons, and so on. A regular expression can simply be a word, a phrase or a string of characters. For example, a regular expression including the string “gauss” would match data containing gauss, gaussian, degauss, etc. More complex regular expressions include metacharacters that provide certain rules for performing the match. Some common metacharacters are the wildcard “.”, the alternation symbol “|”, and the character class symbol “[ ]”. Regular expressions can also include quantifiers such as “*” to match 0 or more times, “+” to match 1 or more times, “?” to match 0 or 1 times, {n} to match exactly n times, {n,} to match at least n times, and {n,m} to match at least n times but no more than m times. For example, the regular expression “a.{2}b” will match any input string that includes the character “a” followed exactly 2 instances of any character followed by the character “b” including, for example, the input strings “abbb,” “adgb,” “a7yb,” “aaab,” and so on.
Traditionally, regular expression searches have been performed using software programs executed by one or more processors, for example, associated with a network search engine. For example, one conventional search technique that can be used to search an input string of characters for multiple patterns is the Aho-Corasick (AC) algorithm. The AC algorithm locates all occurrences of a number of patterns in the input string by constructing a finite state machine that embodies the patterns. More specifically, the AC algorithm constructs the finite state machine in three pre-processing stages commonly referred to as the goto stage, the failure stage, and the next stage. In the goto stage, a deterministic finite state automaton (DFA) or search tree is constructed for a given set of patterns. The DFA constructed in the goto stage includes various states for an input string, and transitions between the states based on characters of the input string. Each transition between states in the DFA is based on a single character of the input string. The failure and next stages add additional transitions between the states of the DFA to ensure that a string of length n can be searched in exactly n cycles. More specifically, the failure and next transitions allow the state machine to transition from one branch of the tree to another branch that is the next best (i.e., the longest prefix) match in the DFA. Once the pre-processing stages have been performed, the DFA can then be used to search any target for all of the patterns in the pattern set.
One problem with prior string search engines utilizing the AC algorithm is that they are not well suited for performing wildcard or inexact pattern matching. As a result, some search engines complement the AC search technique with a non-deterministic finite automaton (NFA) engine that is better suited to search input strings for inexact patterns, particularly those that include quantifiers such as “k” to match 0 or more times, “+” to match 1 or more times, “?” to match 0 or 1 times, {n} to match exactly n times, {n,} to match at least n times, and {n,m} to match at least n times but no more than m times.
Employing an NFA engine to search an input string for a regular expression generally involves converting the regular expression into an NFA search tree that includes a number of states interconnected by goto or “success” transitions. Then, to search the input string for the regular expression, a state machine starts at an initial state of the NFA and transitions to one or more states of the NFA according to its goto transitions. If in a given state the input character matches the goto transition, the goto transition is taken to the next state in the string path and a cursor is incremented to point to the next character in the input string. Otherwise, if there is not a character match at a particular state, the state becomes inactive.
For example, FIG. 1 shows an NFA 100 that embodies the regular expression R1=“[a-z][a-z0-9]{5},” which includes a prefix pattern P1 including the character class “[a-z]” followed by a quantified character class “[a-z0-9]{5}.” An input string of characters will match the regular expression R1 if the input string includes a first character that matches the prefix character class [a-z] followed by n={5} characters that match the quantified character class [a-z0-9]. The NFA 100 for R1 includes an initial state or root node S0, intermediate states S1-S5, and a match state. The sequence of states S0-S5-Match are connected by goto transitions representing character matches with an input string, as indicated in FIG. 1. For example, if an input character within the prefix character class [a-z] is received while the state machine is in the initial state S0, the state machine transitions from S0 to S1 along the “[a-z]” goto transition, and the cursor is incremented to the next input character in the input string. Then, if the next input character is within the quantified character class [a-z0-9], the state machine transitions from S1 to S2 along the “[a-z0-9]” goto transition. Then, if the next input character is within the quantified character class [a-z0-9], the state machine transitions from S2 to S3 along the “[a-z0-9]” goto transition, and so on until a match is detected at the match state. Conversely, if at S1-S5 the input character is anything other than a character within the quantified character class [a-z0-9], then no transition occurs and the current state is deactivated. The initial state S0 remains active for the NFA, as indicated by the arrow 101, which matches on the wildcard “.”. Thus, regardless of what the input character is, the root state S0 remains active.
The regular expression R1=“[a-z][a-z0-9]{5}” is considered a complex regular expression because multiple states of the corresponding NFA 100 can be active at the same time. More specifically, because the quantified character class [a-z0-9] overlaps with (i.e., is a superset of) the prefix character class [a-z], each input character that matches the quantified character class also matches the prefix character class, and therefore not only causes the state machine to transition from one of states S1 to S5 to another of states S2-Match but also causes the state machine to activate an additional instance of state S1. The activation of the additional instance of S1 indicates the beginning of another separate and overlapping portion of the input string that can potentially match the regular expression R1. For example, Table 1 depicts a search operation between an input string IN1=“abcdefgh” and the regular expression R1 according to the NFA 100 of FIG. 1.
TABLE 1CycleInput CharacterActive StatesAction1a02b1,03c2,1,04d3,2,1,05e4,3,2,1,06f5,4,3,2,1,0match7g5,4,3,2,1,0match8h5,4,3,2,1,0match
As shown in Table 1, the number of active states in the NFA 100 can quickly escalate because after the match between the first input character “a” and the prefix character class [a-z], each subsequent input character that matches both the prefix character class [a-z] and the quantified character class [a-z0-9] triggers another potentially matching sub-string and counts towards the quantified number {5} of matches of the character class [a-z0-9], which in turn can quickly exhaust counter resources within the NFA engine.
Unfortunately, the available memory to support an NFA engine is limited, and therefore the number of active states that can be maintained by the NFA engine is limited. As a result, information regarding active states may become lost due to unavailable state memory. Moreover, increasing the number of active states for each regular expression search operation may undesirably degrade search performance by overly taxing processing resources during each compare cycle.
Thus, a need exists for an NFA-based search system that minimizes the memory resources devoted to maintaining lists of active states and tracking numerous overlapping sub-string matches.
Like reference numerals refer to corresponding parts throughout the drawing figures.