Regular expression processing automaton

• US 9,398,033 B2
• Filed: 06/24/2011
• Issued: 07/19/2016
• Est. Priority Date: 02/25/2011
• Status: Active Grant

• Current Assignee: Marvell Asia Pte Limited (Marvell Technology Group Limited)
• Original Assignee: Cavium, LLC (Marvell Technology Group Limited)
• Inventors: Goyal, Rajan, Billa, Lakshmipathi
• Primary Examiner(s): Hill, Stanley K
• Assistant Examiner(s): FINK, THOMAS ANDREW
• Application Number:
  US13/168,395
• Publication Number:
  US 20120221497A1
• Time in Patent Office: 1,852 Days
• US Class Current: 1/1
• CPC Class Codes: H04L 63/1416 Event detection, e.g. attack signature detection
• CPC Class Codes: H04L 63/168 above the transport layer
• CPC Class Codes: H04L 69/12 Protocol engines

Abstract

A method and corresponding apparatus are provided implementing a stage one of run time processing using Deterministic Finite Automata (DFA) and implementing a stage two of run time processing using Non-Deterministic Finite Automata (NFA) to find the existence of a pattern in a payload, such as the payload portion of an Internet Protocol (IP) datagram, or an input stream.

Claims

1. A method comprising:

in a processor of a security appliance coupled to a network;

generating an initial NFA for a set of patterns;

generating an initial DFA for the set of patterns, the initial DFA generated having states representing a subset of the set of patterns and having at least one end-state, where each end-state maps to one or more states of the initial NFA for the set of patterns and represents a transition from processing the set of patterns as DFA to processing the set of patterns as NFA;

adding states to the initial DFA, extending from the at least one end-state, to form an extended DFA for the set of patterns;

mapping at least one of the added DFA states to one or more states of the NFA to form an end-state of the extended DFA, which when processed, transitions run time processing for finding the set of patterns in an input stream from DFA to NFA so that the portion of the set of patterns is found using DFA while a remaining portion of the set of patterns is found using the NFA; and

in an event at least one pattern of the set of patterns has an overlapping pattern prefix with at least one other pattern of the set of patterns, the method further comprising;

stripping from the at least one pattern the overlapping pattern prefix to form a stripped portion and stripped pattern based on at least one stripping criteria and dropping the at least one pattern from the set of patterns to find in the input stream in an event the at least one pattern in its entirety falls within any one of the at least one stripping criteria; and

generating a reverse NFA for the stripped portion, wherein generating the initial DFA includes generating an initial DFA for the stripped pattern and the at least one other pattern and adding states to the initial DFA includes adding states to the initial DFA to form an extended DFA for the stripped pattern and the at least one other pattern.

2. The method of claim 1 wherein generating the initial DFA includes generating a number of states of the initial DFA as a function of a number of states of the NFA.

3. The method of claim 1 wherein generating the initial DFA includes generating the initial DFA having a number of states equal to a fraction of a number of states of the NFA.

4. The method of claim 1 wherein mapping includes replacing a mapping between the at least one end-state of the initial DFA and the one or more states of the NFA with a mapping between the end-state of the extended DFA and the one or more states of the NFA.

5. The method of claim 1 wherein adding states to the initial DFA includes converting states of the NFA into states added to the initial DFA to form the extended DFA.

6. The method of claim 5 wherein converting states of the NFA further includes mapping the converted NFA states to new start states of the NFA and a subset of the states of the NFA, the new start state of the NFA and the subset of the states of the NFA forming a truncated NFA.

7. The method of claim 6 wherein the truncated NFA is formed by converting starting states of the NFA into extended DFA states.

8. The method of claim 1 wherein:

the reverse NFA enables finding of the stripped portion in an event the stripped pattern is found in the input stream.

9. The method of claim 1 wherein the at least one stripping criteria includes any one of:

a character class of a size greater than a predefined number repeatedly concatenated, wherein the character class is repeatedly concatenated with a repetition of at least 1, or a character class of a size greater than the predefined number repeated using a closure.

10. The method of claim 1 wherein generating the reverse NFA includes generating the reverse NFA for the stripped portion in an event the length of the stripped pattern represented by the states of the initial DFA is calculable.

11. The method of claim 1 further comprising:

performing stage one of run time processing with the extended DFA to find the portion of the set of patterns in the input stream;

transitioning from stage one to stage two of run time processing when a state of the extended DFA transitions, on a character of the input stream, to the end-state of the extended DFA; and

continuing with stage two of run time processing at the one or more states of the NFA mapped to the end-state of the extended DFA to find the remaining portion of the set of patterns in the input stream.

12. The method of claim 11 further comprising:

transitioning from stage two to stage one of run time processing, on a character of the input stream associated with another pattern in the input stream; and

transitioning from stage one to stage two of run time processing when a state of the extended DFA transitions, on a character of the input stream, to the end-state of the extended DFA; and

continuing with stage two of run time processing at the one or more states of the NFA mapped to the end-state of the extended DFA to find the remaining portion of the another pattern in the input stream.

13. The method of claim 11 wherein performing stage one of run time processing includes in a first pass of the input stream, finishing stage one of run time processing and noting each end-state of the extended DFA reached along with corresponding offsets of the input stream;

and

wherein continuing with stage two of run time processing includes in a second pass of the input stream, starting stage two of run time processing at one or more NFA start-states mapped to each end-state noted in the first pass and starting processing of the input stream at the offsets noted in the first pass.

14. The method of claim 13 further comprising:

performing stage one of run time processing with the extended DFA to find portions of patterns in the input stream;

transitioning from stage one to stage two of run time processing after processing the input stream in stage one of run time processing;

on a single pass of the input stream, continuing with stage two of run time processing at the start-state NFA mapped to the end-state of the extended DFA starting with a lowest offset in the input stream of one of the found portions of patterns and upon reaching another offset in the input stream corresponding to another one of the found portions of patterns, beginning a new thread of stage two run time processing at the start-state NFA mapped to the end-state of the extended DFA corresponding to the offset of the another one of the found portions of patterns.

15. The method of claim 13 wherein continuing with stage two of run time processing includes traversing the input payload N-times, N corresponding to a number of the found portions of patterns in the input stream from stage one processing.

16. The method of claim 11 further comprising:

transitioning from stage two processing to stage three processing with the reverse NFA to find the overlapping pattern prefix of the at least one pattern, the reverse NFA generated by reversing a concatenation operator during creation of the NFA.

17. The method of claim 16 wherein stage two and stage three processing may occur in parallel, sequence, or any order.

36. The method of claim 1 wherein:

the initial DFA has a number of states limited by a first state watermark and less than a number of states of a complete DFA having states representing the set of patterns, completely; and

a number of DFA states of the extended DFA is limited by a second state watermark, the states added to satisfy one or more following conditions;

i) reduce a number of instances the set of patterns transition from being processed as DFA to being processed as NFA, ii) reduce a number of states of the NFA to track when the set of patterns transition from being processed as DFA to being processed as NFA, and iii) a number of states of the extended DFA is less than the number of states of the complete DFA, the extended DFA representing a portion of the set of patterns to be processed as DFA, the portion of the set of patterns being of at least a predefined size.

18. A security appliance coupled to a network, the security appliance comprising:

a compiler configured to;

generate an initial NFA for a set of patterns;

generate an initial DFA for the set of patterns, the initial DFA generated having states representing a subset of the set of patterns and having at least one end-state, where each end-state maps to one or more states of the initial NFA for the set of patterns and represents a change from processing the set of patterns as DFA to processing the set of patterns as NFA;

add states to the initial DFA, extending from the at least one end-state, to form an extended DFA for the set of patterns; and

map at least one of the DFA states added to one or more states of the NFA to form an end-state of the extended DFA, which when processed, transitions run time processing for finding the set of patterns in an input stream from DFA to NFA so that the portion of the set of patterns is found using DFA while a remaining portion of the set of patterns is found using the NFA; and

in an event at least one pattern of the set of patterns has an overlapping pattern prefix with at least one other pattern of the set of patterns, the compiler is further configured to;

strip from the at least one pattern the overlapping pattern prefix to form a stripped portion and stripped pattern based on at least one stripping criteria and drop the at least one pattern from the set of patterns to find in the input stream in an event the at least one pattern in its entirety falls within any one of the at least one stripping criteria; and

generate a reverse NFA for the stripped portion, wherein generating the initial DFA includes generating an initial DFA for the stripped pattern and the at least one other pattern and adding states to the initial DFA includes adding states to the initial DFA to form an extended DFA for the stripped pattern and the at least one other pattern.

19. The security appliance of claim 18 wherein the compiler is further configured to generate a number of states of the initial DFA as a function of a number of states of the NFA.

20. The security appliance of claim 18 wherein the compiler is further configured to generate the initial DFA having a number of states equal to a fraction of a number of states of the NFA.

21. The security appliance of claim 18 wherein the compiler is further configured to replace a mapping between the at least one end-state of the initial DFA and the one or more states of the NFA with a mapping between the end-state of the extended DFA and the one or more states of the NFA.

22. The security appliance of claim 18 wherein the compiler is further configured to add states to the initial DFA by converting states of the NFA into states added to the initial DFA to form the extended DFA.

23. The security appliance of claim 22 wherein the compiler is further configured to convert states of the NFA by mapping the converted NFA states to new start states of the NFA and a subset of the states of the NFA, the new start state of the NFA and the subset of the states of the NFA forming a truncated NFA.

24. The security appliance of claim 23 wherein the compiler is further configured to form the truncated NFA by converting starting states of the NFA into extended DFA states.

25. The security appliance of claim 18 wherein:

the reverse NFA enables finding of the stripped portion in an event the stripped pattern is found in the input stream.

26. The security appliance of claim 18 wherein the at least one stripping criteria includes any one of:

a character class of a size greater than a predefined number repeatedly concatenated, wherein the character class is repeatedly concatenated with a repetition of at least 1, or a character class of a size greater than the predefined number repeated using a closure.

27. The security appliance of claim 25 wherein the compiler is further configured to generate the reverse NFA for the stripped portion in an event the length of the stripped pattern represented by the states of the initial DFA is calculable.

28. The security appliance of claim 18 further comprising a processor including:

a stage one engine configured to;

perform stage one of run time processing with the extended DFA to find the portion of the set of patterns in the input stream;

transition from stage one to stage two of run time processing when a state of the extended DFA transitions, on a character of the input stream, to the end-state of the extended DFA; and

a stage two engine configured to;

continue with stage two of run time processing at the one or more states of the NFA mapped to the end-state of the extended DFA to find the remaining portion of the set of patterns in the input stream.

29. The security appliance of claim 28 wherein the stage two engine is further configured to transition from stage two to stage one of run time processing, on a character of the input stream associated with another pattern in the input stream;

and

the stage one engine is further configured to;

transition from stage one to stage two of run time processing when a state of the extended DFA transitions, on a character of the input stream for the another pattern, to the end-state of the extended DFA.

30. The security appliance of claim 29 wherein the stage two engine is further configured to:

continue with stage two of run time processing at the one or more states of the NFA mapped to the end-state of the extended DFA to find the remaining portion of the another pattern in the input stream.

31. The security appliance of claim 28 wherein the stage one engine is further configured to perform stage one of run time processing in a first pass of the input stream, finish stage one of run time processing and note each end-state of the extended DFA reached along with corresponding offsets of the input stream;

and

the stage two engine is further configured to continue with stage two of run time processing in a second pass of the input stream, start stage two of run time processing at one or more NFA start-states mapped to each end-state noted in the first pass and start processing of the input stream at the offsets noted in the first pass.

32. The security appliance of claim 31 wherein:

the stage one engine is further configured to perform stage one of run time processing with the extended DFA to find portions of patterns in the input stream and transition from stage one to stage two of run time processing after processing the input stream in stage one of run time processing; and

the stage two engine is further configured to;

on a single pass of the input stream, continue with stage two of run time processing at the start-state NFA mapped to the end-state of the extended DFA corresponding to a lowest offset in the input stream of one of the found portions of patterns and upon reaching another offset in the input stream corresponding to another one of the found portions of patterns, begin a new thread of state two run time processing at the start-state NFA mapped to the end-state of the extended DFA corresponding to the offset of the another one of the found portions of patterns.

33. The security appliance of claim 31 wherein the stage two engine is configured to continue with stage two of run time processing by traversing the input payload N-times in the NFA, N corresponding to a number of the found portions of patterns in the input stream from stage one processing.

34. The security appliance of claim 28 further comprising a stage three engine configured to, for a set of patterns, where at least one pattern has an overlapping pattern prefix with at least one other pattern of the set of patterns:

transitioning from stage two processing to stage three of run time processing with the reverse NFA to find the overlapping pattern prefix of the at least one pattern, the reverse NFA generated by reversing a concatenation operator during creation of the NFA.

35. The security appliance of claim 34 wherein stage two and stage three run time processing may occur in parallel, sequence, or any order.

37. The security appliance of claim 18 wherein:

the initial DFA has a number of states limited by a first state watermark and less than a number of states of a complete DFA having states representing the set of patterns, completely; and

a number of DFA states of the extended DFA is limited by a second state watermark, the states added to satisfy one or more following conditions;

i) reduce a number of instances the set of patterns transition from being processed as DFA to being processed as NFA, ii) reduce a number of states of the NFA to track when the set of patterns transition from being processed as DFA to being processed as NFA, and iii) a number of states of the extended DFA is less than the number of states of the complete DFA, the extended DFA representing a portion of the set of patterns to be processed as DFA, the portion of the set of patterns being of at least a predefined size.