REVERSE NFA GENERATION AND PROCESSING

• US 20130133064A1
• Filed: 11/23/2011
• Published: 05/23/2013
• 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
• Granted Patent: US 9,203,805 B2
• Time in Patent Office: Days
• US Class Current: 726/22
• 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 finite automata graph generated for at least one given pattern; and

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, processing the input sequence of characters 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.

2. The method of claim 1 further comprising:

at the marked node, reporting a match of the at least one given pattern if the at least one given pattern is not the specific type of the at least one given pattern.

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

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

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

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

6. The method of claim 1 further comprising walking the rNFA from the offset associated with the matched pattern and determining whether the given pattern matched by the finite automata includes a matching back-reference.

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

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

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

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

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

10. The method of claim 9 wherein matching the possible back-reference with the associated capture group includes determining at least one of the following:

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

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

12. The method of claim 11 further comprising determining a non-matching back-reference of the given pattern if the possible back-reference does not match with the at least one other possible back-reference.

13. The method of claim 1 further comprising walking the rNFA from the offset associated with the matched pattern and determining whether the given pattern matched by the finite automata graph satisfies an assertion of the given pattern.

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

15. The method of claim 14 further comprising determining whether the subset of the given pattern is matched by the rNFA.

16. The method of claim 15 further comprising:

if the assertion is a positive assertion, reporting the assertion is satisfied if the subset of the given pattern is matched by the rNFA.

17. The method of claim 15 further comprising:

if the assertion is a negative assertion, reporting an unsatisfied assertion if the subset of the given pattern is matched by the rNFA.

18. A method comprising:

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

generating a reverse non-deterministic finite automata (rNFA) for a given pattern, the rNFA including processing nodes for processing an input sequence of patterns to determine a match for the given pattern, the rNFA being generated from the given type of pattern.

19. The method of claim 18 wherein the given pattern includes at least one of the following:

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

20. The method of claim 18 wherein generating the rNFA includes:

converting a given pattern including a back-reference into a revised pattern, wherein converting includes replacing the back-reference with a capture group corresponding to the back-reference; and

generating the rNFA using the revised pattern.

21. The method of claim 20 wherein generating the rNFA includes determining locations of the given pattern requiring a back-reference match and inserting back-reference processing nodes into the rNFA corresponding to locations associated with a beginning offset of the back-reference and an end offset of the back-reference, the beginning offset and end offset of the back-reference corresponding to offset locations of the revised pattern.

22. The method of claim 21 further comprising:

using the back-reference processing nodes, determining at least one of the following;

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

23. The method of claim 20 wherein generating the rNFA includes determining locations of the given pattern including a capture group associated with the back-reference of the given pattern and inserting capture group processing nodes into the rNFA corresponding to locations associated with a beginning offset of the capture group and an end offset of the capture group, the beginning offset and end offset of the capture group corresponding to offset locations of the revised pattern.

24. The method of claim 23 further comprising:

using the capture group processing nodes, determining at least one of the following;

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

25. The method of claim 24 further comprising:

using the determined results of the processing nodes, determining matches between back-references and associated capture groups within the input sequence of characters, the matches identifying a match of the given pattern within the input sequence of characters.

26. The method of claim 18 wherein generating the rNFA includes converting a given pattern including an assertion into a revised pattern, wherein converting includes removing the assertion.

27. The method of claim 26 further comprising determining a location of the removed assertion of the revised pattern and inserting an assertion processing node in the rNFA corresponding to an offset of the revised pattern associated with the location of the removed assertion.

28. The method of claim 27 further comprising determining a subset pattern of the given pattern corresponding to the removed assertion.

29. The method of claim 28 further comprising:

for the subset pattern, generating a finite automata graph, the finite automata corresponding to a type of assertion; and

linking the generated finite automata graph to the assertion processing node.

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

a processor configured to;

walk an input of a sequence of characters through a finite automata graph generated for at least one given pattern; and

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, process the input sequence of characters 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.

31. The security appliance of claim 30 wherein the processor is further configured to:

at the marked node, report a match of the at least one given pattern if the at least one given pattern is not the specific type of the at least one given pattern.

32. The security appliance of claim 30 wherein the specific type of the at least one given pattern includes at least one of the following:

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

33. The security appliance of claim 30 wherein the processor is further configured to determine the start offset of the given pattern upon walking the sequence of characters through the rNFA graph.

34. The security appliance of claim 33 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 pattern and reporting the start offset.

35. The security appliance of claim 30 wherein the processor is further configured to walk the rNFA from the offset associated with the matched pattern and determine whether the given pattern matched by the finite automata includes a matching back-reference.

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

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

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

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

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

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

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

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

41. The security appliance of claim 40 wherein the processor is further configured to determine a non-matching back-reference of the given pattern if the possible back-reference does not match with the at least one other possible back-reference.

42. The security appliance of claim 30 wherein the processor is further configured to walk the rNFA from the offset associated with the matched pattern and determine whether the given pattern matched by the finite automata graph satisfies an assertion of the given pattern.

43. The security appliance of claim 42 wherein the processor is further configured to determine a subset of the given pattern, the subset of the given pattern corresponding to the assertion of the given pattern.

44. The security appliance of claim 43 wherein the processor is further configured to determine whether the subset of the given pattern is matched by the rNFA.

45. The security appliance of claim 44 wherein the processor is further configured to:

if the assertion is a positive assertion, report the assertion is satisfied if the subset of the given pattern is matched by the rNFA.

46. The security appliance of claim 44 wherein the processor is further configured to:

if the assertion is a positive assertion, report an unsatisfied assertion if the subset of the given pattern is matched by the rNFA.

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

a compiler configured to;

generate a reverse non-deterministic finite automata (rNFA) for a given pattern, the rNFA including processing nodes for processing an input sequence of patterns to determine a match for the given pattern, the rNFA being generated from the given type of pattern.

48. The security appliance of claim 47 wherein the given pattern includes at least one of the following:

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

49. The security appliance of claim 47 wherein the compiler is further configured to:

convert a given pattern including a back-reference into a revised pattern and replace the back-reference with a capture group corresponding to the back-reference in the revised pattern; and

generate the rNFA using the revised pattern.

50. The security appliance of claim 49 wherein the compiler is further configured to determine locations of the given pattern requiring a back-reference match and insert back-reference processing nodes into the rNFA corresponding to locations associated with a beginning offset of the back-reference and an end offset of the back-reference, the beginning offset and end offset of the back-reference corresponding to offset locations of the revised pattern.

51. The security appliance of claim 50 further comprising a processor configured to:

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

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

52. The security appliance of claim 49 wherein the compiler is further configured to determine locations of the given pattern including a capture group associated with the back-reference of the given pattern and insert capture group processing nodes into the rNFA corresponding to locations associated with a beginning offset of the capture group and an end offset of the capture group, the beginning offset and end offset of the capture group corresponding to offset locations of the revised pattern.

53. The security appliance of claim 52 wherein the processor is further configured to:

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

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

54. The security appliance of claim 53 wherein the processor is further configured to:

via the determined results of the processing nodes, determine matches between back-references and associated capture groups within the input sequence of characters, the matches identifying a match of the given pattern within the input sequence of characters.

55. The security appliance of claim 47 wherein the compiler is further configured to convert a given pattern including an assertion into a revised pattern and remove the assertion from the revised pattern.

56. The security appliance of claim 55 wherein the compiler is further configured to determine a location of the removed assertion of the revised pattern and insert an assertion processing node in the rNFA corresponding to an offset of the revised pattern associated with the location of the removed assertion.

57. The security appliance of claim 56 further wherein the compiler is further configured to determine a subset pattern of the given pattern corresponding to the removed assertion.

58. The security appliance of claim 57 wherein the compiler is further configured to:

for the subset pattern, generate a finite automata graph, the finite automata graph corresponding to a type of assertion; and

link the generated finite automata graph to the assertion processing node.