Reverse NFA generation and processing

• US 9,203,805 B2
• Filed: 11/23/2011
• Issued: 12/01/2015
• Est. Priority Date: 11/23/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, Satyanarayana Lakshmipathi
• Primary Examiner(s): Arani, Taghi
• Assistant Examiner(s): LYNCH, SHARON S
• Application Number:
  US13/303,885
• Publication Number:
  US 20130133064A1
• Time in Patent Office: 1,469 Days
• Field of Search: 726/14, 726/22
• US Class Current: 1/1
• CPC Class Codes: G06F 16/9024 Graphs; Linked lists G06F16/9027 takes precedence
• CPC Class Codes: H04L 63/0245 Filtering by information in the payload
• CPC Class Codes: H04L 63/0254 Stateful filtering
• CPC Class Codes: H04L 63/1408 by monitoring network traffic monitoring network traffic per se H04L43/00
• CPC Class Codes: H04L 63/1416 Event detection, e.g. attack signature detection

Abstract

In a processor of a security appliance, an input of a sequence of characters is walked through a finite automata graph generated for at least one given pattern. At a marked node of the finite automata graph, if a specific type of the at least one given pattern is matched at the marked node, the input sequence of characters is processed through a reverse non-deterministic finite automata (rNFA) graph generated for the specific type of the at least one given pattern by walking the input sequence of characters backwards through the rNFA beginning from an offset of the input sequence of characters associated with the marked node. Generating the rNFA for a given pattern includes inserting processing nodes for processing an input sequence of patterns to determine a match for the given pattern. In addition, the rNFA is generated from the given type of pattern.

Claims

1. A method comprising:

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

walking an input of a sequence of characters through a deterministic finite automata (DFA) graph generated for at least one given regular expression pattern to enable inspection of packet content, the at least one given regular expression employed to detect a security breach or an intrusion; and

at a marked node of the DFA graph, the marked node being a node that marks a match of the at least one given regular expression pattern;

based on a specific type of the at least one given regular expression pattern matching at the marked node, walking the input sequence of characters through a reverse non-deterministic finite automata (rNFA) graph by walking the input sequence of characters backwards through the rNFA graph beginning from an offset of the input sequence of characters associated with the marked node, the rNFA graph generated for the at least one given regular expression pattern and having at least one processing node inserted therein, the at least one processing node inserted into the rNFA graph based on the specific type of the at least one regular expression pattern; and

based on the specific type of the at least one given regular expression pattern not matching at the marked node, reporting the match of the at least one given regular expression pattern.

2. The method of claim 1 wherein the specific type of the at least one given regular expression pattern includes at least one of the following:

start offset, back reference, capture group, and assertion, or a combination thereof.

3. The method of claim 1 further comprising determining a start offset of the given regular expression pattern upon walking the sequence of characters through the rNFA graph.

4. The method of claim 3 wherein determining includes marking an offset of the last character accepted by the rNFA graph as the start offset of the given regular expression pattern and reporting the start offset.

5. The method of claim 1 wherein the specific type of the at least one given regular expression pattern is a back reference type and further comprising walking the rNFA graph from the offset of the input sequence of characters associated with the marked node and determining whether the given regular expression pattern matched by the DFA graph includes a possible matching back-reference.

6. The method of claim 5 further comprising determining at least one of the following:

a start offset of the possible matching back-reference, end offset of the possible matching back-reference, and length of the possible matching back-reference.

7. The method of claim 6 further comprising matching the possible matching back-reference with an associated capture group of the at least one given regular expression pattern, the associated capture group being determined by the input of the sequence of characters.

8. The method of claim 7 further comprising determining at least one of the following:

a start offset of the associated capture group, end offset of the associated capture group, and length of the associated capture group.

9. The method of claim 7 further comprising matching the possible matching back-reference with at least one other possible matching back-reference, the possible matching back-reference and the at least one other possible matching back-reference associated with a same capture group.

10. The method of claim 9 further comprising determining a non-matching back-reference of the given regular expression pattern in an event the possible matching back-reference does not match with the at least one other possible matching back-reference.

11. The method of claim 5 wherein to determine that the given regular expression pattern is matched by the DFA graph includes matching the possible matching back-reference with an associated capture group by determining at least one of the following:

that a length of the possible matching back-reference and the associated capture group are equivalent and that a character string of the possible matching back-reference and the associated capture group are equivalent.

12. The method of claim 1 further comprising walking the rNFA graph from the offset of the input sequence of characters associated with the marked node and determining whether the given regular expression pattern matched by the DFA graph satisfies an assertion of the given regular expression pattern.

13. The method of claim 12 wherein determining whether the given regular expression pattern satisfies the assertion includes determining a subset of the given regular expression pattern, the subset of the given regular expression pattern corresponding to the assertion of the given regular expression pattern.

14. The method of claim 13 further comprising determining whether the subset of the given regular expression pattern is matched by the rNFA graph.

15. The method of claim 14 further comprising:

based on the assertion being a positive assertion, reporting the assertion is satisfied in an event the subset of the given regular expression pattern is matched by the rNFA graph.

16. The method of claim 14 further comprising:

based on the assertion being a negative assertion, reporting an unsatisfied assertion in an event the subset of the given regular expression pattern is matched by the rNFA graph.

17. The method of claim 1 wherein the rNFA graph is generated for the specific type of the at least one given regular expression pattern.

18. The method of claim 1 wherein the rNFA graph is generated for a portion of the at least one given regular expression pattern.

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

a processor implemented in hardware configured to;

walk an input of a sequence of characters through a deterministic finite automata (DFA) graph generated for at least one given regular expression pattern to enable inspection of packet content, the at least one given regular expression employed to detect a security breach or an intrusion; and

at a marked node of the DFA graph;

based on a specific type of the at least one given regular expression pattern matching at the marked node, walk the input sequence of characters through a reverse non-deterministic finite automata (rNFA) graph by walking the input sequence of characters backwards through the rNFA graph beginning from an offset of the input sequence of characters associated with the marked node, the rNFA graph generated for the at least one given regular expression pattern and having at least one processing node inserted therein, the at least one processing node inserted into the rNFA graph based on the specific type of the at least one regular expression pattern; and

based on the specific type of the at least one given regular expression pattern not matching at the marked node, reporting the match of the at least one given regular expression pattern.

20. The security appliance of claim 19 wherein the specific type of the at least one given regular expression pattern includes at least one of the following:

start offset, back reference, capture group, and assertion.

21. The security appliance of claim 19 wherein the processor is further configured to determine a start offset of the given regular expression pattern upon walking the sequence of characters through the rNFA graph.

22. The security appliance of claim 21 wherein the processor is further configured to mark an offset of the last character accepted by the rNFA graph as the start offset of the given regular expression pattern and reporting the start offset.

23. The security appliance of claim 19 wherein the processor is further configured to walk the rNFA graph from the offset of the input sequence of characters associated with the marked node and determine whether the given regular expression pattern matched by the DFA graph includes a possible matching back-reference.

24. The security appliance of claim 23 wherein the specific type of the at least one given regular expression pattern is a back reference type and the processor is further configured to determine at least one of the following:

a start offset of the possible matching back-reference, end offset of the possible matching back-reference, and length of the possible matching back-reference.

25. The security appliance of claim 24 wherein the processor is further configured to match the possible matching back-reference with an associated capture group of the at least one given regular expression pattern, the associated capture group being determined by the input of the sequence of characters.

26. The security appliance of claim 25 wherein the processor is further configured to determine at least one of the following:

a start offset of the associated capture group, end offset of the associated capture group, and length of the associated capture group.

27. The security appliance of claim 25 wherein the processor is further configured to match the possible matching back-reference with at least one other possible matching back-reference, the possible matching back-reference and the at least one other possible matching back-reference associated with a same capture group.

28. The security appliance of claim 27 wherein the processor is further configured to determine a non-matching back-reference of the given regular expression pattern in an event the possible matching back-reference does not match with the at least one other possible matching back-reference.

29. The security appliance of claim 23 wherein the processor is further configured to determine at least one of the following:

whether a length of the possible matching back-reference and an associated capture group are equivalent and whether a character string of the possible matching back-reference and the associated capture group are equivalent.

30. The security appliance of claim 19 wherein the processor is further configured to walk the rNFA graph from the offset of the input sequence of characters associated with the marked node and determine whether the given regular expression pattern matched by the DFA graph satisfies an assertion of the given regular expression pattern.

31. The security appliance of claim 30 wherein the processor is further configured to determine a subset of the given regular expression pattern, the subset of the given pattern regular expression corresponding to the assertion of the given regular expression pattern.

32. The security appliance of claim 31 wherein the processor is further configured to determine whether the subset of the given regular expression pattern is matched by the rNFA graph.

33. The security appliance of claim 32 wherein the processor is further configured to:

based on the assertion being a positive assertion, report the assertion is satisfied in an event the subset of the given regular expression pattern is matched by the rNFA graph.

34. The security appliance of claim 32 wherein the processor is further configured to:

based on the assertion being a positive assertion, report an unsatisfied assertion in an event the subset of the given regular expression pattern is matched by the rNFA graph.