Finite automata processing based on a top of stack (TOS) memory

• US 9,904,630 B2
• Filed: 01/31/2014
• Issued: 02/27/2018
• 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): Patel, Ashok
• Assistant Examiner(s): Almamun, Abdullah
• Application Number:
  US14/169,967
• Publication Number:
  US 20150220454A1
• Time in Patent Office: 1,488 Days
• Field of Search: None
• CPC Class Codes: G06F 12/0891 using clearing, invalidating or resetting means
• CPC Class Codes: G06F 12/145 the protection being virtual, e.g. for virtual blocks or segments before a translation mechanism
• CPC Class Codes: H04L 63/1425 Traffic logging, e.g. anomaly detection
• CPC Class Codes: H04L 63/20 for managing network security; network security policies in general filtering policies H04L63/0227

Abstract

A method, and corresponding apparatus and system are provided for optimizing matching of at least one regular expression pattern in an input stream by storing a context for walking a given node, of a plurality of nodes of a given finite automaton of at least one finite automaton, the store including a store determination, based on context state information associated with a first memory, for accessing the first memory and not a second memory or the first memory and the second memory. Further, to retrieve a pending context, the retrieval may include a retrieve determination, based on the context state information associated with the first memory, for accessing the first memory and not the second memory or the second memory and not the first memory. The first memory may have read and write access times that are faster relative to the second memory.

Claims

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

a first memory;

a second memory operatively coupled to the first memory; and

at least one processor operatively coupled to the first memory and the second memory and to improve match performance of the at least one processor, the at least one processor is configured to make a determination, based on context state information associated with the first memory, for whether to access (i) the first memory and not the second memory or (ii) the first memory and the second memory, and store a context in the first or second memory for walking a given node, of a plurality of nodes of a given finite automaton of at least one finite automaton for matching at least one regular expression pattern, wherein the context state information associated with the first memory includes a validity state, the validity state indicating a valid or invalid state of the first memory.

2. The security appliance of claim 1, wherein the context identifies the given node and an offset, of a segment in a payload of an input stream received from the network, to enable the at least one processor to walk the given node with the segment, based on retrieving the context stored.

3. The security appliance of claim 1, wherein the valid state indicates that the first memory has a pending context stored and the invalid state indicates that the first memory has no pending context stored.

4. The security appliance of claim 1, wherein the determination for accessing (i) the first memory and not the second memory, is based on the validity state indicating the invalid state, and the determination for accessing (ii) the first memory and the second memory, is based on the validity state indicating the valid state.

5. The security appliance of claim 1, wherein based on the determination to (i) access the first memory and not the second memory, the at least one processor is further configured to:

access the first memory to store the context in the first memory; and

update the context state information associated with the first memory.

6. The security appliance of claim 5, wherein to update the context state information associated with the first memory, the at least one processor is further configured to change a validity state included in the context state information from an invalid state to a valid state to indicate that the first memory has a pending context stored.

7. The security appliance of claim 1, wherein based on the determination to (ii) access the first memory and the second memory, the at least one processor is further configured to:

access the first memory to retrieve a pending context stored in the first memory;

access the second memory to store the pending context retrieved;

access the first memory to store the context in the first memory; and

preserve the context state information associated with the first memory.

8. The security appliance of claim 1, wherein the first memory is a register and a first field of the register is configured to store the context state information and a second field of the register is configured to store the context.

9. The security appliance of claim 1, wherein first read and write access times of the first memory are faster relative to second read and write access times of the second memory.

10. The security appliance of claim 1, wherein:

the first memory is configured with a single entry for storing a single context;

the second memory is configured with multiple entries for storing multiple contexts; and

the second memory is maintained as a circular buffer.

11. The security appliance of claim 10, wherein the second memory is configured to store a head pointer for the circular buffer and based on the determination to (ii) access the first memory and the second memory, the at least one processor is further configured to:

access the first memory to retrieve a pending context stored in the first memory;

access the second memory to store the pending context retrieved based on the head pointer;

access the first memory to store the context in the first memory; and

preserve the context state information associated with the first memory.

12. The security appliance of claim 11, wherein to store the pending context retrieved based on the head pointer, the at least one processor is further configured to:

update the head pointer; and

store the pending context retrieved in an empty context entry of the second memory, the empty context entry being addressed by the head pointer updated.

13. The security appliance of claim 1, wherein the context includes a plurality of fields and the plurality of fields includes:

a context entry type field that is based on a node type, of a plurality of node types, of the given node, the context entry type field signifying which fields, of the plurality of fields, are relevant for the node type;

a match type field that is relevant based on the context entry type field, the match type field being based on the node type and used to determine whether the given node is configured to match a single instance or multiple consecutive instances of a given element in an input stream received from the network;

an element field that is relevant regardless of the context entry type field and identifies the given element for matching at the given node;

a next node address field that is relevant regardless of the context entry type field and identifies a next node;

a count field that is relevant based on the context entry type field and identifies a count value, indicating a number of consecutive instances remaining for positively matching to the given element or having been positively matched to the given element, at the given node, based on the context entry type field;

a discard unexplored context (DUP) field that is relevant regardless of the context entry type field and identifies whether to discard the context or walk the next node based on the context, in an event a complete match of at least one regular expression is detected in the input stream;

a reverse walk direction field that is relevant regardless of the context entry type field and identifies a reverse or forward direction of walking; and

an offset field that is relevant regardless of the context entry type field and identifies an offset of a segment of a payload in the input stream for matching to the given element at the given node or to a next element at the next node, based on the context entry type field, the next element identified via metadata associated with the next node.

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

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

a first memory;

a second memory operatively coupled to the first memory; and

at least one processor operatively coupled to the first memory and the second memory and to improve match performance of the at least one processor, the at least one processor is configured to make a determination, based on context state information associated with the first memory, for whether to access (i) the first memory and not the second memory or (ii) the first memory and the second memory, and store a context in the first or second memory for walking a given node, of a plurality of nodes of a given finite automaton of at least one finite automaton for matching at least one regular expression pattern, wherein the determination is a store determination, and the at least one processor is further configured to retrieve a pending context, the retrieval including a retrieve determination, based on the context state information associated with the first memory, for accessing (iii) the first memory and not the second memory or (iv) the second memory and not the first memory.

16. The security appliance of claim 15, wherein the context state information associated with the first memory includes a validity state, the validity state indicating a valid or invalid state of the first memory.

17. The security appliance of claim 16, wherein the valid state indicates that the first memory has the pending context stored and the invalid state indicates that the first memory has no pending context stored.

18. The security appliance of claim 16, wherein the retrieve determination for accessing (iii) the first memory and not the second memory, is based on the validity state indicating the valid state, and the retrieve determination for accessing (iv) the second memory and not the first memory, is based on the validity state indicating the invalid state.

19. The security appliance of claim 15, wherein based on the retrieve determination to (iii) access the first memory and not the second memory, the at least one processor is further configured to:

access the first memory to retrieve the pending context from the first memory; and

update the context state information associated with the first memory.

20. The security appliance of claim 19, wherein to update the context state information associated with the first memory, the at least one processor is further configured to change a validity state included in the context state information from a valid state to an invalid state to indicate that the first memory has no pending context stored.

21. The security appliance of claim 15, wherein based on the retrieve determination to (iv) access the second memory and not the first memory, the at least one processor is further configured to:

access the second memory to retrieve the pending context; and

preserve the context state information associated with the first memory.

22. The security appliance of claim 21, wherein the second memory is maintained as a circular buffer and is configured to store a head pointer, and to access the second memory to retrieve the pending context the at least one processor is further configured to retrieve the pending context based on the head pointer.

23. The security appliance of claim 22, wherein to retrieve the pending context based on the head pointer, the at least one processor is further configured to:

retrieve the pending context from a current entry location of the second memory addressed via the head pointer; and

update the head pointer to address a next entry location of the second memory immediately subsequent to the current entry location.

24. A method comprising:

operatively coupling a first memory and a second memory; and

operatively coupling at least one processor to the first memory and the second memory, and to improve match performance of the at least one processor, the at least one processor is configured to make a determination, based on context state information associated with the first memory, for whether to access (i) the first memory and not the second memory or (ii) the first memory and the second memory, and store a context in the first or second memory for walking a given node, of a plurality of nodes of a given finite automaton of at least one finite automaton for matching at least one regular expression pattern, wherein the context state information associated with the first memory includes a validity state, the validity state indicating a valid or invalid state of the first memory.

25. The method of claim 24, wherein the context identifies the given node and an offset, of a segment in a payload of an input stream received from the network, to enable the at least one processor to walk the given node with the segment, based on retrieving the context stored.

26. The method of claim 24, wherein the valid state indicates that the first memory has a pending context stored and the invalid state indicates that the first memory has no pending context stored.

27. The method of claim 24, wherein the determination for accessing (i) the first memory and not the second memory, is based on the validity state indicating the invalid state, and the determination for accessing (ii) the first memory and the second memory, is based on the validity state indicating the valid state.

28. The method of claim 24, wherein based on the determination to (i) access the first memory and not the second memory, the at least one processor is further configured to:

access the first memory to store the context in the first memory; and

update the context state information associated with the first memory.

29. The method of claim 28, wherein to update the context state information associated with the first memory, the at least one processor is further configured to change a validity state included in the context state information from an invalid state to a valid state to indicate that the first memory has a pending context stored.

30. The method of claim 24, wherein based on the determination to (ii) access the first memory and the second memory, the at least one processor is further configured to:

access the first memory to retrieve a pending context stored in the first memory;

access the second memory to store the pending context retrieved;

access the first memory to store the context in the first memory; and

preserve the context state information associated with the first memory.

31. The method of claim 24, wherein the first memory is a register and a first field of the register is configured to store the context state information and a second field of the register is configured to store the context.

32. The method of claim 24, wherein first read and write access times of the first memory are faster relative to second read and write access times of the second memory.

33. The method of claim 24, wherein:

the first memory is configured with a single entry for storing a single context;

the second memory is configured with multiple entries for storing multiple contexts; and

the second memory is maintained as a circular buffer.

34. The method of claim 33, wherein the second memory is configured to store a head pointer for the circular buffer and based on the determination to (ii) access the first memory and the second memory, the at least one processor is further configured to:

access the first memory to retrieve a pending context stored in the first memory;

access the second memory to store the pending context retrieved based on the head pointer;

access the first memory to store the context in the first memory; and

preserve the context state information associated with the first memory.

35. The method of claim 34, wherein to store the pending context retrieved based on the head pointer, the at least one processor is further configured to:

update the head pointer; and

store the pending context retrieved in an empty context entry of the second memory, the empty context entry being addressed by the head pointer updated.

36. The method of claim 24, wherein the context includes a plurality of fields and the plurality of fields includes:

a context entry type field that is based on a node type, of a plurality of node types, of the given node, the context entry type field signifying which fields, of the plurality of fields, are relevant for the node type;

a match type field that is relevant based on the context entry type field, the match type field being based on the node type and used to determine whether the given node is configured to match a single instance or multiple consecutive instances of a given element in an input stream received from the network;

an element field that is relevant regardless of the context entry type field and identifies the given element for matching at the given node;

a next node address field that is relevant regardless of the context entry type field and identifies a next node;

a count field that is relevant based on the context entry type field and identifies a count value, indicating a number of consecutive instances remaining for positively matching to the given element or having been positively matched to the given element, at the given node, based on the context entry type;

a discard unexplored context (DUP) field that is relevant regardless of the context entry type field and identifies whether to discard the context or walk the next node based on the context, in an event a complete match of at least one regular expression is detected in the input stream;

a reverse walk direction field that is relevant regardless of the context entry type field and identifies a reverse or forward direction of walking; and

an offset field that is relevant regardless of the context entry type field and identifies an offset of a segment of a payload in the input stream for matching to the given element at the given node or to a next element a the next node, based on the context entry type field, the next element identified via metadata associated with the next node.

37. The method of claim 24, 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.

38. A method comprising:

operatively coupling a first memory and a second memory; and

operatively coupling at least one processor to the first memory and the second memory, and to improve match performance of the at least one processor, the at least one processor is configured to make a determination, based on context state information associated with the first memory, for whether to access (i) the first memory and not the second memory or (ii) the first memory and the second memory, and store a context in the first or second memory for walking a given node, of a plurality of nodes of a given finite automaton of at least one finite automaton for matching at least one regular expression pattern, wherein the determination is a store determination, and the at least one processor is further configured to retrieve a pending context, the retrieval including a retrieve determination, based on the context state information associated with the first memory, for accessing (iii) the first memory and not the second memory or (iv) the second memory and not the first memory.

39. The method of claim 38, wherein the context state information associated with the first memory includes a validity state, the validity state indicating a valid or invalid state of the first memory.

40. The method of claim 38, wherein the valid state indicates that the first memory has the pending context stored and the invalid state indicates that the first memory has no pending context stored.

41. The method of claim 40, wherein the retrieve determination for accessing (iii) the first memory and not the second memory, is based on the validity state indicating the valid state, and the retrieve determination for accessing (iv) the second memory and not the first memory, is based on the validity state indicating the invalid state.

42. The method of claim 38, wherein based on the retrieve determination to (iii) access the first memory and not the second memory, the at least one processor is further configured to:

access the first memory to retrieve the pending context from the first memory; and

update the context state information associated with the first memory.

43. The method of claim 42, wherein to update the context state information associated with the first memory, the at least one processor is further configured to change a validity state included in the context state information from a valid state to an invalid state to indicate that the first memory has no pending context stored.

44. The method of claim 38, wherein based on the retrieve determination to (iv) access the second memory and not the first memory, the at least one processor is further configured to:

access the second memory to retrieve the pending context; and

preserve the context state information associated with the first memory.

45. The method of claim 44, wherein the second memory is maintained as a circular buffer and is configured to store a head pointer, and to access the second memory to retrieve the pending context the at least one processor is further configured to retrieve the pending context based on the head pointer.

46. The method of claim 45, wherein to retrieve the pending context based on the head pointer, the at least one processor is further configured to:

retrieve the pending context from a current entry location of the second memory addressed via the head pointer; and

update the head pointer to address a next entry location of the second memory immediately subsequent to the current entry location.

47. A non-transitory computer-readable medium having encoded thereon a sequence of instructions which, when executed by at least one processor, improve match performance of the at least one processor by causing the at least one processor to:

make a determination, based on context state information associated with the first memory, for whether to access (i) the first memory and not the second memory or (ii) the first memory and the second memory; and

store a context in a first or second memory for walking a given node, of a plurality of nodes of a given finite automaton of at least one finite automaton for matching at least one regular expression pattern, wherein the context state information associated with the first memory includes a validity state, the validity state indicating a valid or invalid state of the first memory.

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

a first memory;

a second memory operatively coupled to the first memory; and

at least one processor operatively coupled to the first memory and the second memory and to improve match performance of the at least one processor, the at least one processor is configured to make a determination, based on context state information associated with the first memory, for whether to access (i) the first memory and not the second memory or (ii) the first memory and the second memory, and store a context in the first or second memory for walking a given node, of a plurality of nodes of a given finite automaton of at least one finite automaton for matching at least one regular expression pattern, wherein based on the determination to (ii) access the first memory and the second memory, the at least one processor is further configured to;

access the first memory to retrieve a pending context stored in the first memory;

access the second memory to store the pending context retrieved;

access the first memory to store the context in the first memory; and

preserve the context state information associated with the first memory.

49. A method comprising:

operatively coupling a first memory and a second memory; and

operatively coupling at least one processor to the first memory and the second memory, and to improve match performance of the at least one processor, the at least one processor is configured to make a determination, based on context state information associated with the first memory, for whether to access (i) the first memory and not the second memory or (ii) the first memory and the second memory, and store a context in the first or second memory for walking a given node, of a plurality of nodes of a given finite automaton of at least one finite automaton for matching at least one regular expression pattern, wherein based on the determination to (ii) access the first memory and the second memory, the at least one processor is further configured to;

access the first memory to retrieve a pending context stored in the first memory;

access the second memory to store the pending context retrieved;

access the first memory to store the context in the first memory; and

preserve the context state information associated with the first memory.

50. A non-transitory computer-readable medium having encoded thereon a sequence of instructions which, when executed by at least one processor, improve match performance of the at least one processor by causing the at least one processor to:

make a determination, based on context state information associated with the first memory, for whether to access (i) the first memory and not the second memory or (ii) the first memory and the second memory; and

store a context in a first or second memory for walking a given node, of a plurality of nodes of a given finite automaton of at least one finite automaton for matching at least one regular expression pattern, wherein based on the determination to (ii) access the first memory and the second memory, the at least one processor is further caused to;

access the first memory to retrieve a pending context stored in the first memory;

access the second memory to store the pending context retrieved;

access the first memory to store the context in the first memory; and

preserve the context state information associated with the first memory.