Method and apparatus for processing of finite automata

• US 9,419,943 B2
• Filed: 12/30/2013
• Issued: 08/16/2016
• Est. Priority Date: 12/30/2013
• 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, Dikshit, Abhishek
• Primary Examiner(s): Starks, Wilbert L
• Application Number:
  US14/143,586
• Publication Number:
  US 20150186786A1
• Time in Patent Office: 960 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: G06F 21/564 by virus signature recognition
• CPC Class Codes: G06N 5/04 Inference or reasoning models
• CPC Class Codes: H04L 63/0227 Filtering policies mail message filtering H04L51/212

Abstract

A method, and corresponding apparatus and system are provided for optimizing matching at least one regular expression pattern in an input stream by walking at least one finite automaton in a speculative manner. The speculative manner may include walking at least two nodes of a given finite automaton, of the at least one finite automaton, in parallel, with a segment, at a given offset within a payload of a packet in the input stream. The walking may include determining a match result for the segment, at the given offset within the payload, at each node of the at least two nodes. The walking may further include determining at least one subsequent action for walking the given finite automaton, based on an aggregation of each match result determined.

Claims

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

at least one memory configured to store at least one finite automaton including a plurality of nodes generated from at least one regular expression pattern;

at least one processor operatively coupled to the at least one memory and configured to walk the at least one finite automaton, with segments of an input stream received via the network, to match the at least one regular expression pattern in the input stream, the walk including;

walking at least two nodes of a given finite automaton, of the at least one finite automaton, in parallel, with a segment, at a given offset within a payload, of a packet in the input stream, to optimize performance of run time processing of the at least one processor for identifying an existence of the at least one regular expression pattern in the input stream;

determining a match result for the segment, at the given offset within the payload, at each node of the at least two nodes; and

determining at least one subsequent action for walking the given finite automaton, based on an aggregation of each match result determined.

2. The security appliance of claim 1, wherein the at least one finite automaton includes a deterministic finite automaton (DFA) and at least one non-deterministic finite automaton (NFA), the given finite automaton being a given NFA of the at least one NFA.

3. The security appliance of claim 1, wherein the match result for the segment is determined, at each node of the at least two nodes, within a same processing cycle of the at least one processor.

4. The security appliance of claim 1, wherein the at least two nodes include an element node and a parallel node, the element node configured to match a single instance of a first element in the payload, the first element being a first character or first character class, the parallel node being one of:

(i) a variable count node configured to match a variable number of consecutive instances of a second element in the payload, the second element being a second character or second character class, or (ii) a speculative node, the speculative node configured to match the variable number of consecutive instances of the second element in the payload based on transition arcs from and to a split node.

5. The security appliance of claim 4, wherein the variable count node is an aggregation of:

the split node, the split node configured to advance the walk, independent of the payload and without consuming from the payload, to the element node and the speculative node, via epsilon transition arcs and, in parallel, walk the element and speculative nodes, with the segment at the given offset; and

the speculative node, the speculative node configured to advance the walk back to the split node, and consume the segment by updating the given offset, based on a positive match with the second element at the speculative node.

6. The security appliance of claim 4, wherein the given finite automaton is an NFA graph, the NFA graph including a transition from the variable count node to the element node, the variable count node preceding the element node in the NFA graph.

7. The security appliance of claim 4, wherein the variable count node is lazy type node associated with metadata identifying, either directly or indirectly, the element node, to advance the walk to the element node based on a single matching instance, of the variable number of consecutive instances, of the second element in the payload.

8. The security appliance of claim 7, wherein the metadata associated with the variable count lazy node includes a count for tracking a total number of consecutive instances of the second element matching in the payload to enable a comparison of the total number to the variable number.

9. The security appliance of claim 4, wherein based on the parallel node being the speculative node, the given finite automaton includes a split node, of the plurality of nodes, the element node and the speculative node being identified based on metadata associated with the split node, the split node being configured to:

advance, independent of the payload and without consuming from the payload, the walk to the element and speculative nodes, via epsilon transition arcs and, in parallel, walk the element and speculative nodes, with the segment at the given offset, based on a speculative processing indicator included in the metadata associated with the split node.

10. The security appliance of claim 9, wherein the element and speculative nodes are not walked in parallel based on the speculative processing indicator not being included in the metadata associated with the split node.

11. The security appliance of claim 10, wherein the walk of the speculative node with the segment, at the given offset, is based on a negative match result for the segment, at the given offset, at the element node.

12. The security appliance of claim 11, wherein the walk of the speculative node with the segment, at the given offset, is further based on storing and retrieving of unexplored context, the unexplored context identifying, either directly or indirectly, the speculative node and the given offset.

13. The security appliance of claim 12, wherein the storing of the unexplored context includes:

storing the unexplored context in a stack entry; and

pushing the stack entry onto a stack, and retrieving the unexplored context includes popping the stack entry from the stack.

14. The security appliance of claim 13, wherein the speculative node is configured to advance the walk to the split node based on a positive match with the second element at the speculative node.

15. The security appliance of claim 1, wherein based on the aggregation including a negative match result at each node, of the at least two nodes walked in parallel, the at least one subsequent action includes:

discontinuing the walk of a given path, at each of the at least two nodes walked in parallel, the given path partially matching the at least one regular expression pattern in the given finite automaton;

walking a next node, of the plurality of nodes, with a next segment, at a next given offset within the payload, based on sensing unexplored context; and

terminating the walk based on not sensing the unexplored context.

16. The security appliance of claim 15, wherein the unexplored context identifies, either directly or indirectly, the next node and the next given offset, to advance the walk along another path, partially matching the at least one regular expression pattern in the given finite automaton, at the next node with the next segment.

17. The security appliance of claim 16, wherein the sensing of the unexplored context includes:

determining a non-empty status of a stack; and

popping a stack entry from the stack, the stack entry including the unexplored context and being a most recently pushed entry onto the stack.

18. The security appliance of claim 1, wherein the at least two nodes include an element node and a parallel node, and based on the aggregation including:

a positive match result for the segment at the element node; and

the positive match result or a negative match result for the segment at the parallel node, the at least one subsequent action includes;

updating the given offset to produce a next offset;

identifying a next node, of the plurality of nodes, based on metadata associated with the element node;

walking the next node identified with a next segment, at the next offset within the payload;

determining a next match result for the next segment at the next node identified; and

determining at least one next subsequent action for walking the given finite automaton based on the next match result determined.

19. The security appliance of claim 18, wherein based on the positive match result for the segment at the parallel node, the at least one subsequent action further includes:

storing an unexplored context in a stack entry; and

pushing the stack entry onto a stack, the unexplored context identifying, either directly or indirectly, the parallel node and the given offset.

20. The security appliance of claim 19, wherein based on the next match result being the negative match result, the at least one next subsequent action includes:

walking the parallel node with the segment, at the given offset within the payload, based on sensing unexplored context; and

terminating the walk based on not sensing the unexplored context.

21. The security appliance of claim 20, wherein the sensing of the unexplored context includes:

determining a non-empty status of a stack; and

popping a stack entry from the stack, the stack entry including the unexplored context and being a most recently pushed entry onto the stack.

22. The security appliance of claim 18, wherein updating the given offset to produce the next offset includes:

incrementing the given offset based on a direction of the walk being a forward direction; and

decrementing the given offset based on the direction of the walk being a reverse direction.

23. The security appliance of claim 1, wherein the at least two nodes walked in parallel include an element node and a parallel node and based on the aggregation including a negative match result for the segment at the element node and a positive match result for the segment at the parallel node, the at least one subsequent action includes:

updating the given offset to produce a next offset; and

walking the element node and the parallel node, in parallel, with a next segment at the next offset.

24. The security appliance of claim 23, wherein updating the given offset to produce the next offset includes:

incrementing the given offset based on a direction of the walk being a forward direction; and

decrementing the given offset based on the direction of the walk being a reverse direction.

25. The security appliance of claim 1, wherein walking the at least two nodes, in parallel, optimizes performance of the match by:

obviating storing and retrieving context, needed if the at least two nodes are not walked in parallel, to advance the walk from a first node of the at least two nodes to a second node of the at least two nodes, with the segment, at the given offset, based on a negative match result of the segment, at the given offset.

26. A method comprising:

storing at least one finite automaton including a plurality of nodes generated from at least one regular expression pattern in at least one memory; and

operatively coupling the at least one memory to at least one processor, the at least one processor configured to walk the at least one finite automaton, with segments of an input stream received via a hardware network interface operatively coupled to the network, to match for the at least one regular expression pattern in the input stream, the walk including;

walking at least two nodes of a given finite automaton, of the at least one finite automaton, in parallel, with a segment, at a given offset within a payload, of a packet in the input stream, to optimize performance of run time processing of the at least one processor for identifying an existence of the at least one regular expression pattern in the input stream;

determining a match result for the segment, at the given offset within the payload, at each node of the at least two nodes; and

determining at least one subsequent action for walking the given finite automaton, based on an aggregation of each match result determined.

27. The method of claim 26, wherein the at least one finite automaton includes a deterministic finite automaton (DFA) and at least one non-deterministic finite automaton (NFA), the given finite automaton being a given NFA of the at least one NFA.

28. The method of claim 26, wherein the determining, at each node of the at least two nodes, is within a same processing cycle of the at least one processor.

29. The method of claim 26, wherein the at least two nodes include an element node and a parallel node, the element node configured to match a single instance of a first element in the payload, the first element being a first character or first character class, the parallel node being one of:

(i) a variable count node configured to match a variable number of consecutive instances of a second element in the payload, the second element being a second character or second character class, or (ii) a speculative node, the speculative node configured to match the variable number of consecutive instances of the second element in the payload based on transition arcs from and to a split node.

30. The method of claim 29, wherein the given finite automaton is an NFA graph, the NFA graph including a transition arc from the variable element node to the element node, the variable element node preceding the element node in the NFA graph.

31. The method of claim 29, wherein the variable count node is a variable count lazy node associated with metadata identifying, either directly or indirectly, the element node, to advance the walk to the element node based on a single matching instance, of the variable number of consecutive instances, of the second element in the payload.

32. The method of claim 31, wherein the metadata associated with the variable count lazy node includes a count for tracking a total number of consecutive instances of the second element matching in the payload to enable a comparison of the total number to the variable number.

33. The method of claim 29, wherein based on the parallel node being the speculative node, the given finite automaton includes a split node, of the plurality of nodes, the element node and the speculative node being identified based on metadata associated with the split node, the split node being configured to:

advance, independent of the payload and without consuming from the payload, the walk to the element and speculative nodes, via epsilon transition arcs and, in parallel, walk the element and speculative nodes, with the segment at the given offset, based on a speculative processing indicator included in the metadata associated with the split node.

34. The method of claim 33, wherein the element and speculative nodes are not walked in parallel based on the speculative processing indicator not being included in the metadata associated with the split node.

35. The method of claim 34, wherein the walk of the speculative node with the segment, at the given offset, is based on a negative match result for the segment, at the given offset, at the element node.

36. The method of claim 35, wherein the walk of the speculative node with the segment, at the given offset, is further based on storing and retrieving of unexplored context, the unexplored context identifying, either directly or indirectly, the speculative node and the given offset.

37. The method of claim 36, wherein the storing of the unexplored context includes:

storing the unexplored context in a stack entry; and

pushing the stack entry onto a stack, and retrieving the unexplored context includes popping the stack entry from the stack.

38. The method of claim 37, wherein the speculative node is configured to advance the walk to the split node based on a positive match with the second element at the speculative node.

39. The method of claim 29, wherein the variable count node is an aggregation of:

the split node, the split node configured to advance the walk, independent of the payload and without consuming from the payload, to the element node and the speculative node, via epsilon transition arcs and, in parallel, walk the element and speculative nodes, with the segment at the given offset; and

the speculative node, the speculative node configured to advance the walk back to the split node, and consume the segment by updating the given offset, based on a positive match with the second element at the speculative node.

40. The method of claim 26, wherein based on the aggregation including a negative match result at each node, of the at least two nodes walked in parallel, the at least one subsequent action includes:

discontinuing the walk of a given path, at each of the at least two nodes walked in parallel, the given path partially matching the at least one regular expression pattern in the given finite automaton;

walking a next node, of the plurality of nodes, with a next segment, at a next given offset within the payload, based on sensing unexplored context; and

terminating the walk based on not sensing the unexplored context.

41. The method of claim 40, wherein the unexplored context identifies, either directly or indirectly, the next node and the next given offset, to advance the walk along another path, partially matching the at least one regular expression pattern in the given finite automaton, at the next node with the next segment.

42. The method of claim 41, wherein the sensing of the unexplored context includes:

determining a non-empty status of a stack; and

popping a stack entry from the stack, the stack entry including the unexplored context and being a most recently pushed entry onto the stack.

43. The method of claim 26, wherein the at least two nodes include an element node and a parallel node, and based on the aggregation including:

a positive match result for the segment at the element node; and

the positive match result or a negative match result for the segment at the parallel node, the at least one subsequent action includes;

updating the given offset to produce a next offset;

identifying a next node, of the plurality of nodes, based on metadata associated with the element node;

walking the next node identified with a next segment, at the next offset within the payload;

determining a next match result for the next segment at the next node identified; and

determining at least one next subsequent action for walking the given finite automaton based on the next match result determined.

44. The method of claim 43, wherein based on the positive match result for the segment at the parallel node, the at least one subsequent action further includes:

storing an unexplored context in a stack entry; and

pushing the stack entry onto a stack, the unexplored context identifying, either directly or indirectly, the parallel node and the given offset.

45. The method of claim 44, wherein based on the next match result being the negative match result, the at least one next subsequent action includes:

walking the parallel node with the segment, at the given offset within the payload, based on sensing unexplored context; and

terminating the walk based on not sensing the unexplored context.

46. The method of claim 45, wherein the sensing of the unexplored context includes:

determining a non-empty status of a stack; and

popping a stack entry from the stack, the stack entry including the unexplored context and being a most recently pushed entry onto the stack.

47. The method of claim 46, wherein updating the given offset to produce the next offset includes:

incrementing the given offset based on a direction of the walk being a forward direction; and

decrementing the given offset based on the direction of the walk being a reverse direction.

48. The method of claim 26, wherein the at least two nodes walked in parallel include an element node and a parallel node and based on the aggregation including a negative match result for the segment at the element node and a positive match result for the segment at the parallel node, the at least one subsequent action includes:

updating the given offset to produce a next offset; and

walking the element node and the parallel node, in parallel, with a next segment at the next offset.

49. The method of claim 48, wherein updating the given offset to produce the next offset includes:

incrementing the given offset based on a direction of the walk being a forward direction; and

decrementing the given offset based on the direction of the walk being a reverse direction.

50. The method of claim 26, wherein walking the at least two nodes, in parallel, optimizes performance of the match by:

obviating storing and retrieving context, needed if the at least two nodes are not walked in parallel, to advance the walk from a first node of the at least two nodes to a second node of the at least two nodes, with the segment, at the given offset, based on a negative match result of the segment, at the given offset.

51. A non-transitory computer-readable medium having encoded thereon a sequence of instructions which, when executed by at least one processor, causes the at least one processor to:

walk at least one finite automaton, including a plurality of nodes generated from at least one regular expression pattern, with segments of an input stream, to match for the at least one regular expression pattern in the input stream, the walk including;

walking at least two nodes of a given finite automaton, of the at least one finite automaton, in parallel, with a segment, at a given offset within a payload, of a packet in the input stream, to optimize performance of run time processing of the at least one processor for identifying an existence of the at least one regular expression pattern in the input stream;

determining a match result for the segment, at the given offset within the payload, at each node of the at least two nodes; and

determining at least one subsequent action for walking the given finite automaton, based on an aggregation of each match result determined.