Reverse NFA Generation And Processing

• US 20160021123A1
• Filed: 09/24/2015
• Published: 01/21/2016
• Est. Priority Date: 11/23/2011
• Status: Abandoned Application

• Current Assignee: Cavium, LLC (Marvell Technology Group Limited)
• Original Assignee: Cavium, LLC (Marvell Technology Group Limited)
• Inventors: Goyal, Rajan, Billa, Satyanarayana Lakshmipathi
• Application Number:
  US14/863,816
• Publication Number:
  US 20160021123A1
• Time in Patent Office: Days
• 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;

walking a sequence of characters through a finite automata graph generated for at least one given regular expression pattern to enable recognition of the at least one given regular expression pattern in the sequence of characters; and

at a marked node of the finite automata 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 sequence of characters backwards through a reverse non-deterministic finite automata (rNFA) graph beginning from an offset of the 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 based on the specific type of the at least one regular expression pattern.

2. The method of claim 1 further comprising reporting a match of the at least one given regular expression pattern based on the specific type of the at least one given regular expression pattern not matching at the marked node.

3. The method of claim 1 further comprising determining a start offset of the given regular expression pattern based on walking the sequence of characters through the rNFA graph in an event the specific type includes a start offset type.

4. The method of claim 3 wherein determining includes marking an offset of a 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 further comprising walking the rNFA graph from the offset of the sequence of characters associated with the marked node and determining whether the given regular expression pattern matched by the finite automata includes a possible matching back-reference in an event the specific type includes a back reference type.

6. The method of claim 5 further comprising matching the possible matching back-reference with an associated capture group of the at least one given regular expression pattern, in an event the specific type further includes a capture group type, the associated capture group being determined by the sequence of characters.

7. The method of claim 5 wherein in an event the specific type further includes a capture group type, to determine that the given regular expression pattern is matched by the finite automata 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 a length of the associated capture group are equivalent and that a character string of the possible matching back-reference and the associated capture group are equivalent.

8. The method of claim 5 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.

9. The method of claim 8 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.

10. The method of claim 1 further comprising walking the rNFA graph from the offset of the sequence of characters associated with the marked node and determining whether the given regular expression pattern matched by the finite automata graph satisfies an assertion of the given regular expression pattern in an event the specific type includes an assertion type.

11. The method of claim 10 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.

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

13. The method of claim 12 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.

14. The method of claim 12 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.

15. The method of claim 1 wherein walking the sequence of characters through the finite automata graph includes walking the sequence of characters through a deterministic finite automata (DFA) graph generated for the least one given regular expression pattern, and at a marked node of the DFA graph, based on matching the specific type of the at least one given regular expression pattern at the marked node, walking the sequence of characters through the rNFA graph generated for the specific type of the at least one given regular expression pattern.

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

17. The method of claim 1 wherein the at least one processing node includes at least one back-reference processing node and further comprising:

using the at least one back-reference processing node to determining at least one of the following;

a start offset of a back-reference corresponding to a first offset of the sequence of characters, an end offset of the back-reference corresponding to a second offset of the sequence of characters, and a length of the back-reference within the sequence of characters.

18. The method of claim 1 wherein the at least one processing node includes at least one capture group processing node and further comprising:

using the at least one capture group processing node to determine at least one of the following;

a start offset of a capture group corresponding to a first offset of the sequence of characters, an end offset of the capture group corresponding to a second offset of the sequence of characters, and a length of the capture group within the sequence of characters.

19. The method of claim 1 further comprising:

using determined results of the at least one processing node to determine matches between back-references and associated capture groups within the sequence of characters, the matches identifying a match of the given regular expression pattern within the sequence of characters.

20. An apparatus comprising:

a processor implemented in hardware configured to;

walk a sequence of characters through a finite automata graph generated for at least one given regular expression pattern to enable recognition of the at least one given regular expression pattern in the sequence of characters; and

at a marked node of the finite automata graph, based on a specific type of the at least one given regular expression pattern matching at the marked node, walk the sequence of characters backwards through a reverse non-deterministic finite automata (rNFA) graph beginning from an offset of the 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 based on the specific type of the at least one regular expression pattern.

21. The apparatus of claim 20 wherein the processor is further configured to report a match of the at least one given regular expression pattern based on the specific type of the at least one given regular expression pattern not matching at the marked node.

22. The apparatus of claim 20 wherein the processor is further configured to determine a start offset of the given regular expression pattern based on walking the sequence of characters through the rNFA graph in an event the specific type includes a start offset type.

23. The apparatus of claim 22 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.

24. The apparatus of claim 20 wherein the processor is further configured to walk the rNFA graph from the offset of the sequence of characters associated with the marked node and determine whether the given regular expression pattern matched by the finite automata includes a possible matching back-reference in an event the specific type includes a back reference type.

25. The apparatus 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 sequence of characters.

26. The apparatus of claim 24 wherein the processor is further configured to determine at least one of the following:

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

27. The apparatus of claim 24 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 apparatus 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 apparatus of claim 20 wherein the processor is further configured to walk the rNFA graph from the offset of the sequence of characters associated with the marked node and determine whether the given regular expression pattern matched by the finite automata graph satisfies an assertion of the given regular expression pattern.

30. The apparatus of claim 29 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.

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

32. The apparatus of claim 31 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.

33. The apparatus of claim 31 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.

34. The apparatus of claim 20 wherein the at least one processing node includes at least one back-reference processing node and the processor is further configured to:

via the at least one back-reference processing node, determine at least one of the following;

a start offset of a back-reference corresponding to a first offset of the sequence of characters, an end offset of the back-reference corresponding to a second offset of the sequence of characters, and a length of the back-reference within the sequence of characters.

35. The apparatus of claim 20 wherein the at least one processing node includes at least one capture group processing node and the processor is further configured to:

via the at least one capture group processing node, determine at least one of the following;

a start offset of a capture group corresponding to a first offset of the sequence of characters, an end offset of the capture group corresponding to a second offset of the sequence of characters, and a length of the capture group within the sequence of characters.

36. The apparatus of claim 20 wherein the processor is further configured to:

via determined results of the at least one processing node, determine matches between back-references and associated capture groups within the sequence of characters, the matches identifying a match of the given regular expression pattern within the sequence of characters.