Method and apparatus for optimizing finite automata processing

• US 9,602,532 B2
• Filed: 01/31/2014
• Issued: 03/21/2017
• Est. Priority Date: 01/31/2014
• 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): Holmes, Michael B
• Application Number:
  US14/169,830
• Publication Number:
  US 20150220845A1
• Time in Patent Office: 1,145 Days
• Field of Search: 706/48
• US Class Current: 1/1
• CPC Class Codes: H04L 63/1441 Countermeasures against malicious traffic countermeasures against attacks on cryptographic mechanisms H04L9/002

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 iteratively walking at least two nodes of a given finite automaton, of the at least one finite automaton, in parallel, with a segment, at a current offset within a payload, of a packet in the input stream, based on positively matching the segment at a given node of the at least two nodes walked in parallel, the current offset being updated to a next offset per iteration.

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 iteratively walking at least two nodes of a given finite automaton, of the at least one finite automaton, in parallel, with a segment, at a current offset within a payload, of a packet in the input stream, based on positively matching the segment at a given node of the at least two nodes walked in parallel, the current offset being updated to a next offset per iteration.

2. The security appliance of claim 1, wherein iteratively walking further includes, per iteration:

walking the at least two nodes, in parallel, with the segment, at the current offset within the payload, within a same processing cycle of the at least one processor.

3. The security appliance of claim 1, wherein the at least two nodes include an element node configured to match a single instance of an element in the payload, and wherein iteratively walking further includes, per iteration:

storing a context identifying the next offset and a next node of the given finite automaton based on positively matching the segment, at the current offset in the payload, at the given node and the element node, the element node associated with metadata identifying the element and the next node.

4. The security appliance of claim 3, further comprising at least one stack operatively coupled to the at least one processor and wherein:

storing the context includes storing the context in a stack entry and pushing the stack entry onto the at least one stack.

5. The security appliance of claim 1, wherein the given node is a variable count greedy (VCG) node configured to match a threshold number of consecutive instances of an element in the payload and wherein positively matching the segment at the VCG node is based on positively matching the segment to the element.

6. The security appliance of claim 5, wherein positively matching the segment at the VCG node includes incrementing a count value associated with the VCG node and is further based on the count value incremented being less than or equal to the threshold number and wherein the method further includes negatively matching the segment at the VCG node based on negatively matching the segment to the element or determining that the threshold number has been exceeded.

7. The security appliance of claim 1, wherein the given node of the at least two nodes is associated with metadata and iteratively walking of the at least two nodes, in parallel, is further based on the metadata of the given node including a speculative processing indicator.

8. The security appliance of claim 1, wherein the at least two nodes walked in parallel include an element node and a VCG node, the given node being the VCG node, and wherein the VCG node is configured to match a variable number of consecutive instances of a first element in the payload and the element node is configured to match a single instance of a second element in the payload.

9. The security appliance of claim 8, wherein the VCG node is associated with metadata identifying, either directly or indirectly, the element node, the variable number of consecutive instances, and the first element.

10. The security appliance of claim 9, wherein the metadata associated with the VCG node further includes a count value for tracking a total number of consecutive instances of the first element matching in the payload to enable a comparison of the total number to the variable number.

11. The security appliance of claim 8, wherein the first element is one of a first character or first character class and the second element is one of a second character or second character class.

12. The security appliance of claim 8, wherein the given finite automaton is a non-deterministic finite automaton (NFA) graph and the NFA graph includes a transition from the VCG node to the element node, the VCG node preceding the element node in the NFA graph.

13. The security appliance of claim 8, wherein based on negatively matching the segment, at the current offset in the payload, at the VCG node, and positively matching the segment, at the current offset in the payload, at the element node, the walk further includes:

discontinuing iteratively walking;

updating the current offset to the next offset; and

walking a next node with a next segment at the next offset in the payload.

14. The security appliance of claim 13, wherein updating the current offset includes incrementing or decrementing the current offset based on a forward or reverse direction of the walk, respectively.

15. The security appliance of claim 8, further comprising at least one stack operatively coupled to the at least one processor and wherein, based on negatively matching the segment at the VCG node and the element node, the walk further includes:

discontinuing iteratively walking;

popping a stack entry from the stack at least one stack, based on a non-empty status of the at least one stack, the stack entry being a most recently pushed entry onto the stack, and advancing the walk to a next node with a next segment based on the stack entry popped; and

terminating the walk based on an empty status of the at least one stack.

16. The security appliance of claim 1, wherein the current offset is updated to the next offset by incrementing or decrementing the current offset.

17. The security appliance of claim 16, wherein the current offset is incremented based on a forward walk direction of walking and decremented based on a reverse walk direction of walking.

18. 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.

19. 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 a network, to match for the at least one regular expression pattern in the input stream, the walk including iteratively walking at least two nodes of a given finite automaton, of the at least one finite automaton, in parallel, with a segment, at a current offset within a payload, of a packet in the input stream, based on positively matching the segment at a given node of the at least two nodes walked in parallel, the current offset being updated to a next offset per iteration.

20. The method of claim 19, wherein iteratively walking further includes, per iteration:

walking the at least two nodes, in parallel, with the segment, at the current offset within the payload, within a same processing cycle of the at least one processor.

21. The method of claim 19, wherein the at least two nodes include an element node configured to match a single instance of an element in the payload, and wherein iteratively walking further includes, per iteration:

storing a context identifying the next offset and a next node of the given finite automaton based on positively matching the segment, at the current offset in the payload, at the given node and the element node, the element node associated with metadata identifying the element and the next node.

22. The method of claim 21, wherein the security appliance further comprises at least one stack and the method further includes operatively coupling the at least one processor to the at least one stack and wherein storing the context includes storing the context in a stack entry and pushing the stack entry onto the at least one stack.

23. The method of claim 19, wherein the given node is a variable count greedy (VCG) node configured to match a threshold number of consecutive instances of an element in the payload and wherein positively matching the segment at the VCG node is based on positively matching the segment to the element.

24. The method of claim 23, wherein positively matching the segment at the VCG node includes incrementing a count value associated with the VCG node and is further based on the count value incremented being less than or equal to the threshold number and wherein the method further includes negatively matching the segment at the VCG node based on negatively matching the segment to the element or determining that the threshold number has been exceeded.

25. The method of claim 19, further including associating the given node of the at least two nodes with metadata and wherein iteratively walking of the at least two nodes, in parallel, is further based on the metadata of the given node including a speculative processing indicator.

26. The method of claim 19, wherein the at least two nodes walked in parallel include an element node and a VCG node, the given node being the VCG node, and wherein the VCG node is configured to match a variable number of consecutive instances of a first element in the payload and the element node is configured to match a single instance of a second element in the payload.

27. The method of claim 26, further including associating the VCG node with metadata identifying, either directly or indirectly, the element node, the variable number of consecutive instances, and the first element.

28. The method of claim 27, wherein the metadata associated with the VCG node further includes a count value for tracking a total number of consecutive instances of the first element matching in the payload to enable a comparison of the total number to the variable number.

29. The method of claim 26, wherein the first element is one of a first character or first character class and the second element is one of a second character or second character class.

30. The method of claim 26, wherein the given finite automaton is a non-deterministic finite automaton (NFA) graph and the NFA graph includes a transition from the VCG node to the element node, the VCG node preceding the element node in the NFA graph.

31. The method of claim 26, wherein based on negatively matching the segment, at the current offset in the payload, at the VCG node, and positively matching the segment, at the current offset in the payload, at the element node, the walk further includes:

discontinuing iteratively walking;

updating the current offset to the next offset; and

walking a next node with a next segment at the next offset in the payload.

32. The method of claim 31, wherein updating the current offset includes incrementing or decrementing the current offset based on a forward or reverse direction of the walk, respectively.

33. The method of claim 26, wherein the security appliance further comprises at least one stack and the method further includes operatively coupling to the at least one processor to the at least one stack and wherein, based on negatively matching the segment at the VCG node and the element node, the walk further includes:

discontinuing iteratively walking;

popping a stack entry from the stack at least one stack, based on a non-empty status of the at least one stack, the stack entry being a most recently pushed entry onto the stack, and advancing the walk to a next node with a next segment based on the stack entry popped; and

terminating the walk based on an empty status of the at least one stack.

34. The method of claim 19, wherein the current offset is updated to the next offset by incrementing or decrementing the current offset.

35. The method of claim 34, wherein the current offset is incremented based on a forward walk direction of walking and decremented based on a reverse walk direction of the walking.

36. The method of claim 19, 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.

37. 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 the at least one regular expression pattern in the input stream, the walk including iteratively walking at least two nodes of a given finite automaton, of the at least one finite automaton, in parallel, with a segment, at a current offset within a payload, of a packet in the input stream, based on positively matching the segment at a given node of the at least two nodes walked in parallel, the current offset being updated to a next offset per iteration.