US 8,554,698 B2 · Configuring state machines used to order and select matching operations for determining whether an input string matches any of at least one regular expression using lookahead finite automata based regular expression detection

Abstract

State machines are used to order and select matching operations for determining whether an input string matches any of at least one regular expression by (1) accepting the set of regular expression(s), and (2) for each of the regular expression(s) of the set accepted, (A) identifying any look-ahead type strings within the given regular expression, (B) identifying any sequential type strings within the given regular expression, (C) partitioning the regular expression based on any identified simple strings, any identified look-ahead type variable strings, and any sequential type variable strings to generate partitioned parts, (D) reordering the partitioned parts of the regular expression using optimization policies to generate reordered partitioned parts, and (E) configuring nodes of a state machine corresponding to the given regular expression. Once configured, the state machines check for a match between the input string accepted and the regular expression using the configured nodes of the state machine.

Drawings

Drawings are temporarily unavailable. Open the PDF at USPTO

Drawings

Claims22

Dependent claims

A computer-implemented method for configuring state machines used to order and select matching operations for determining whether an input string matches any of at least one regular expression, the computer-implemented method comprising:

a) accepting the set of at least one regular expression;
and
b) for each of the at least one regular expression of the set accepted,
1) identifying any look-ahead type strings within the given regular expression,
2) identifying any sequential type strings within the given regular expression,
3) partitioning the regular expression based on any identified simple strings, any identified look-ahead type variable strings, and any sequential type variable strings to generate partitioned parts of the given regular expression,
4) reordering the partitioned parts of the given regular expression using optimization policies to generate reordered partitioned parts of the regular expression, and
5) configuring nodes of a state machine corresponding to the given regular expression, by recording configured information of the nodes on a tangible storage medium, using
A) an order of the reordered partitioned parts of the regular expression, and
B) a string type of the partitioned parts of the regular expression,
wherein the optimization policies used to reorder the partitioned parts of the regular expression include a rule for placing a sequential type string part before an adjacent look-ahead type string part.

8 more elements

a) accepting the set of at least one regular expression;
and
b) for each of the at least one regular expression of the set accepted,
1) identifying any look-ahead type strings within the given regular expression,
2) identifying any sequential type strings within the given regular expression,
3) partitioning the regular expression based on any identified simple strings, any identified look-ahead type variable strings, and any sequential type variable strings to generate partitioned parts of the given regular expression,
4) reordering the partitioned parts of the given regular expression using optimization policies to generate reordered partitioned parts of the regular expression, and
5) configuring nodes of a state machine corresponding to the given regular expression, by recording configured information of the nodes on a tangible storage medium, using
A) an order of the reordered partitioned parts of the regular expression, and
B) a string type of the partitioned parts of the regular expression,
wherein the elements of the state machine include a plurality of ordered nodes, and
wherein the act of configuring the nodes of the state machine using (A) the reordered partitioned parts of the regular expression, and (B) a string type of the partitioned parts of the regular expression includes, for each of the reordered partitioned parts of the regular expression
i) assigning one of the plurality of nodes to the given reordered partition part,
ii) when the given reordered partition part is a normal simple string, then defining a node including information for a simple string detection,
iii) when the given reordered partition part is a short simple string, then defining a node including information for a short simple string detection module,
iii) when the given reordered partition part is a look-ahead type variable string, then defining a node including information for a frequently appearing repetition detection module, a timestamp lookup module, or a character lookup module, and
iv) when the given reordered partition part is a sequential type variable string, then defining a node including information for a repetition detection module.

14 more elements

a) accepting the set of at least one regular expression;
b) for each of the at least one regular expression of the set accepted,
1) identifying any look-ahead type strings within the given regular expression,
2) identifying any sequential type strings within the given regular expression,
3) partitioning the regular expression based on any identified simple strings, any identified look-ahead type variable strings, and any sequential type variable strings to generate partitioned parts of the given regular expression,
4) reordering the partitioned parts of the given regular expression using optimization policies to generate reordered partitioned parts of the regular expression, and
5) configuring nodes of a state machine corresponding to the given regular expression, by recording configured information of the nodes on a tangible storage medium, using
A) an order of the reordered partitioned parts of the regular expression, and
B) a string type of the partitioned parts of the regular expression;
c) accepting an input string;
and
d) for each of the at least one regular expression, checking for a match between the input string accepted and the given regular expression using the configured nodes of the state machine corresponding to the given regular expression.

9 more elements

Apparatus for configuring state machines used to order and select matching operations for determining whether an input string matches any of at least one regular expression, the apparatus comprising:

a) at least one processor;
and
b) a storage device storing processor-executable instructions which, when executed by the at least one processor, perform a method including
1) accepting the set of at least one regular expression, and
2) for each of the at least one regular expression of the set accepted,
A) identifying any look-ahead type strings within the given regular expression,
B) identifying any sequential type strings within the given regular expression,
C) partitioning the regular expression based on any identified simple strings, any identified look-ahead type variable strings, and any sequential type variable strings to generate partitioned parts of the given regular expression,
D) reordering the partitioned parts of the given regular expression using optimization policies to generate reordered partitioned parts of the regular expression, and
E) configuring nodes of a state machine corresponding to the given regular expression, by recording configured information of the nodes on a tangible storage medium, using
i) an order of the reordered partitioned parts of the regular expression, and
ii) a string type of the partitioned parts of the regular expression,
wherein the elements of the state machine include a plurality of ordered nodes, and
wherein the act of configuring the nodes of the state machine using (A) the reordered partitioned parts of the regular expression, and (B) a string type of the partitioned parts of the regular expression includes, for each of the reordered partitioned parts of the regular expression
i) assigning one of the plurality of nodes to the given reordered partition part,
ii) when the given reordered partition part is a normal simple string, then defining a node including information for a simple string detection,
iii) when the given reordered partition part is a short simple string, then defining a node including information for a short simple string detection module,
iii) when the given reordered partition part is a look-ahead type variable string, then defining a node including information for a frequently appearing repetition detection module, a timestamp lookup module, or a character lookup module, and
iv) when the given reordered partition part is a sequential type variable string, then defining a node including information for a repetition detection module.

16 more elements

Dependencies are inferred from the claim text.

Description12,921 words

Summary1,798 words

#§1.1 Field of the Invention

#The present invention concerns matching an arbitrary length string with one of a number of known regular expressions, and/or configuring state machines for this purpose. Such matching may be used for network intrusion detection and prevention.

#§1.2 Background Information

Brief description of the drawings14 figures

#FIGS. 2A-2F illustrate a set of regular expressions being transformed according to a LaFA representation consistent with the present invention.

#FIG. 3A is a matrix depicting the depth and the detection complexity of example components, while FIG. 3B is a matrix illustrating a string classification scheme that may be used by embodiments consistent with the present invention.

Detailed description10,719 words

#The present invention may involve novel methods, apparatus, message formats, and/or data structures for determining whether or not an arbitrary-length bit string matches one or more of a number of known regular expressions, as well as generating a data structure (e.g., a LaFA state machine) used in such a determination. The following description is presented to enable one skilled in the art to make and use the invention, and is provided in the context of particular applications and their requirements. Thus, the following description of embodiments consistent with the present invention provides illustration and description, but is not intended to be exhaustive or to limit the present invention to the precise form disclosed. Various modifications to the disclosed embodiments will be apparent to those skilled in the art, and the general principles set forth below may be applied to other embodiments and applications. For example, although a series of acts may be described with reference to a flow diagram, the order of acts may differ in other implementations when the performance of one act is not dependent on the completion of another act. Further, non-dependent acts may be performed in parallel. No element, act or instruction used in the description should be construed as critical or essential to the present invention unless explicitly described as such. Also, as used herein, the article “a” is intended to include one or more items. Where only one item is intended, the term “one” or similar language is used. Thus, the present invention is not intended to be limited to the embodiments shown and the inventors regard their invention as any patentable subject matter described.

#FIG. 1 is a bubble diagram illustrating general operations of configuring and querying a LaFA state machine for determining a possible match between an arbitrary-length input string and a regular expression(s) belonging to a set of one or more regular expression(s). Specifically, the proposed LaFA state machine configuration operations 120 are performed first using a set of one or more regular expressions 110. Once the operations 120 are completed, a highly optimized and scalable LaFA state machine data structure 130 results. The LaFA state machine data structure 130 is configured such that an arbitrary-length input string may be checked against the set of one or more regular expressions 110. More specifically, given an input string(s) 150, the configured LaFA state machine data structure 130 may be used by input string(s) to regular expression(s) match determination operations 140. If a match is determined by such operations 140, then the LaFA system may return a list of matching RegEx(es) 160.

#The proposed LaFA system is a finite automata state machine optimized for scalable RegEx detection. The LaFA system is used for representing a set of n RegExes, R={r1, r2, . . . rn}, which can also be called a RegEx Database. For instance, this set of RegExes can be a set of Snort signatures, or Bro or Linux Layer 7 rules. An associated LaFA RegEx detection system can be queried with an input I, such as a network packet. The system may return a match along with a list of matching RegExes if input I matches one or more of the RegExes in R. Otherwise, a “no match” result is returned.

Facts

Application

12/906,307Filed 18 Oct 2010 · us provisional application

Priority

17 Oct 2009

Published

US 2011/0093484 A121 Apr 2011

Granted

8 Oct 2013

Term ends

22 Oct 2031

Estimated · how

20 years from earliest known nonprovisional domestic filing plus recorded patent term adjustment, including 369 days of adjustment. Maintenance-fee lapses, terminal disclaimers and statutory extensions have not been checked. The continuity chain may be incomplete; this is not an enforceability determination.

Classification2 codes

G06F 16/90344
Query processing: by using string matching techniques
G06F
Computing and data processing

Timeline

17 Oct 2009Priority claimedParent application 61/252,651
18 Oct 2010Application filedUS 12/906,307
21 Oct 2010Assigned to Polytechnic Institute of New York Universityassignment of assignor's interest
21 Apr 2011PublishedUS 2011/0093484 A1
8 Oct 2013GrantedUS 8,554,698 B2
12 Oct 2026TodayWithin its term
22 Oct 2031Term endsEstimated, includes 369 days of adjustment

Configuring state machines used to order and select matching operations for determining whether an input string matches any of at least one regular expression using lookahead finite automata based regular expression detection

Life of this patent

Configuring state machines used to order and select matching operations for determining whether an input string matches any of at least one regular expression using lookahead finite automata based regular expression detection

Life of this patent

Life of this patent

Abstract

Drawings

Drawings

Claims22

Description12,921 words

Drawings

Classification2 codes

Life of this patent

Description12,921 words