System and method to traverse a non-deterministic finite automata (NFA) graph generated for regular expression patterns with advanced features

• US 9,507,563 B2
• Filed: 02/21/2014
• Issued: 11/29/2016
• Est. Priority Date: 08/30/2013
• Status: Active Grant

• Current Assignee: Marvell Asia Pte Limited (Marvell Technology Group Limited)
• Original Assignee: Cavium, LLC (Marvell Technology Group Limited)
• Inventors: Billa, Satyanarayana Lakshmipathi, Goyal, Rajan
• Primary Examiner(s): Paliwal, Yogesh
• Application Number:
  US14/186,913
• Publication Number:
  US 20150067836A1
• Time in Patent Office: 1,012 Days
• Field of Search: 726/22
• US Class Current: 1/1
• CPC Class Codes: G06F 13/28 using burst mode transfer, e.g. direct memory access DMA, cycle steal G06F13/32 takes precedence
• CPC Class Codes: G06F 16/90344 by using string matching techniques
• CPC Class Codes: G06F 21/567 using dedicated hardware
• CPC Class Codes: G06F 2205/126 Monitoring of intermediate fill level, i.e. with additional means for monitoring the fill level, e.g. half full flag, almost empty flag
• CPC Class Codes: G06F 2213/2806 Space or buffer allocation for DMA transfers
• CPC Class Codes: G06F 5/14 for overflow or underflow handling, e.g. full or empty flags
• CPC Class Codes: G06F 9/3885 using a plurality of independent parallel functional units
• CPC Class Codes: H04L 41/28 Restricting access to network management systems or functions, e.g. using authorisation function to access network configuration
• CPC Class Codes: H04L 63/1408 by monitoring network traffic monitoring network traffic per se H04L43/00

Abstract

In one embodiment, a method of walking a non-deterministic finite automata (NFA) graph representing a pattern includes extracting a node type and an element from a node of the NFA graph. The method further includes matching a segment of a payload for the element by matching the payload for the element at least zero times, the number of times based on the node type.

Claims

1. A method of walking a non-deterministic finite automata (NFA) graph representing a pattern, the method comprising:

by a processor, extracting a node type, a next node address, and an element from a node of the NFA graph; and

by the processor, matching a segment of a payload with the element by matching the payload with the element at least zero times, a number of the at least zero times based on the node type, wherein extracting the node type, next node address, and the element from the node enable the processor to identify the pattern in the payload with less nodes relative to another NFA graph representing the pattern.

2. The method of claim 1, wherein the node type is at least one of a variable count, fixed count, fixed-variable count , character, case insensitive character, character class, case sensitive string, case insensitive string, marked, split.

3. The method of claim 1, further comprising, by the processor, pushing an entry to a run stack, the entry indicating at least one of the node type, an address of a next node in the graph, a payload offset, a count value, a duplicate bit, a reverse bit.

4. The method of claim 3, wherein pushing the entry to the run stack is based on the node type.

5. The method of claim 4, wherein pushing the entry to the run stack is performed if the node type is variable count, fixed-variable count, or split.

6. The method of claim 1, further comprising, by the processor:

popping a top entry of a run stack;

loading a graph node indicated by the popped top entry; and

matching the segment of the payload with the element, the element indicated in the loaded graph node, at a payload offset indicated in the popped top entry.

7. The method of claim 6, wherein popping the top entry of the run stack is performed after a mismatch of matching the segment of the payload with the element.

8. The method of claim 1, further comprising, by the processor:

popping a top entry of a run stack;

extracting graph node information stored in the popped top entry; and

matching the segment of the payload with the element, the element indicated in the extracted graph node, at a payload offset indicated in the popped top entry.

9. The method of claim 1, wherein the node type of string represents a portion of the pattern of a plurality of values, each value being at least one of a byte, letter, or character.

10. The method of claim 1, wherein matching the segment of the payload with the element associated with the node type of string includes matching at least two values within the segment against respective values of the string stored as the element in the node.

11. The method of claim 10, further comprising:

if the segment partially matches the element and if the length of the payload is shorter than the length of the string stored as the element of the node, loading a next payload of a same flow of the payload and continuing matching remaining values in the string to the values in the next payload.

12. The method of claim 11, further comprising pushing a partial match to a save buffer to be loaded upon loading the next payload of the same flow of the payload.

13. The method of claim 12, wherein pushing the partial match to the save buffer includes storing a current run stack entry being processed in the save buffer;

and further comprising;

upon loading the next payload, copying the stored at least one entry in the save buffer to the run stack.

14. The method of claim 1, wherein matching the segment of the payload with the element associated with the node type of variable count includes matching with the element a variable number of times indicated by a count value extracted from the node.

15. The method of claim 14, wherein the variable number of times are at least zero times, at most a finite number of times, or at most an infinite number of times.

16. The method of claim 1, wherein the node type further indicates that the variable count node is a greedy node, lazy node, possessive node, or all match node.

17. The method of claim 1, wherein matching the segment of the payload with the element if the node type is variable count lazy node includes returning the shortest match found in the payload.

18. The method of claim 1, wherein matching the segment of the payload with the element if the node type is variable count lazy node includes pushing a stack entry to a run stack, the stack entry indicating the variable count lazy node and payload offset, and loading a next node at the next node address in the graph.

19. The method of claim 18, wherein matching the segment of the payload with the element if the node type is variable count lazy node includes, if matching the next node element with the segment is a mismatch, popping the node of the node type of variable count lazy node from the stack entry of the run stack, and matching the element stored in the popped node with the payload segment.

20. The method of claim 19, wherein upon matching the segment of the payload with the element stored in the popped node, reducing a count value of the variable count lazy node, pushing an updated stack entry to the run stack and loading a next node at the next node address stored in the popped entry.

21. The method of claim 18, wherein if the segment of the payload continues in a next payload of a same flow of the first payload, further comprising:

pushing the run stack entry to a save buffer; and

upon loading the next payload, loading the save buffer entries into the run stack.

22. The method of claim 1, wherein matching the segment of the payload with the element if the associated node type is variable count greedy node or variable count possessive node includes returning a longest match found in the payload.

23. The method of claim 1, wherein matching the segment of the payload with the element if the node type is variable count greedy node includes:

fetching at least one segment of the payload,

matching the at least one segment to the element, and

if there is a nomatch and at least one segment matches the element a number of times less than or equal to a variable count in the variable count greedy node, or no more segments of the payload are available;

pushing a run stack entry storing the node type of the node, a payload offset of the at least one segment of the payload, and a number of segments matched, if the number of segments matched indicates the element has been matched less than a maximum number of times,

fetching a next node of the NFA graph indicated by the next node address, and

continuing matching a next segment of the payload indicated by a position after the payload offset with a second element of the next node, wherein if there is a nomatch, popping the run stack entry from the run stack, decrementing a number of segments matched count, pushing the updated run stack entry back to the run stack, and continuing matching the next segment of the payload from the offset stored in the popped entry with the element of a next node stored at the next node address in the popped entry.

24. The method of claim 1, wherein matching the segment of the payload with the element if the node type is variable count possessive node includes continually matching the payload segment to the element until a nomatch or a count of the variable count possessive node indicates the element has been matched a maximum number of times, and then continuing to match the subsequent segment of the payload with the next node stored at the next node address.

25. The method of claim 1, wherein matching the segment of the payload with the element if the node type is variable count all match node includes returning all matches found in the payload.

26. The method of claim 1, wherein matching the segment of the payload with the element if the node type is variable count all match node includes matching the segment to the element, and if it is a match, pushing a stack entry to a run stack, the stack entry indicating the variable count all match node and payload offset with an indication to continue matching the NFA graph, and loading a next node at the next node address, and if it is a nomatch, popping the stack entry from the run stack.

27. The method of claim 1, wherein the node type of fixed count represents a portion of the pattern to match for an element a fixed number of times.

28. The method of claim 27, wherein the element of the node type of fixed count can be character, character class or string.

29. The method of claim 1, wherein matching the segment of the payload with the element associated with the node type of fixed count includes matching at least two values within the segment against a value of the element stored in the node.

30. The method of claim 29, further comprising:

if the segment matches the element and if the length of the payload is shorter than the count of the fixed count node, loading a next payload of a same flow of the payload and continuing matching the remaining values in the element to the values in the next payload.

31. The method of claim 1, wherein the element can be at least one of a character, character class and string.

32. The method of claim 1 wherein the node type of character class represents a portion of the pattern to match an element by employing a Boolean-or operation of at least one value.

33. The method of claim 32, wherein each character class is stored in a memory as a mask, wherein an indicator corresponding to each possible character in the mask is set if the character is part of the character class, and not set if it is not part of the character class.

34. The method of claim 1, wherein upon the successful match, loading, from the next node address extracted from the node, a second node of the NFA graph.

35. The method of claim 1, wherein:

if the node type is variable count, extract a count value from the node, the count value indicates a maximum number of times to match with the element,

if the node type is fixed count, extract a count value from the node, the count value indicates an exact number of times to match with the element,

if the node type is string, extract a count value from the node, the count value indicates a length of the string, and

if the node type is fixed-variable count, extract two count values from the node, a first count value indicates an exact number of times to match with the element and a second count value indicates a maximum number of times to match with the element.

36. The method of claim 1, wherein matching the segment of the payload with the element associated with the node type of marked includes indicating a match is found, and popping any entries in a run stack, or, if indicated in the node, continuing walking, in a reverse direction, a next node at the next address indicated in the node.

37. A system for walking a non-deterministic finite automata (NFA) graph representing a pattern, the system comprising:

a memory; and

a processor, the processor coupled to the memory and configured to extract a node type, next node address, count value, and an element from a node of the NFA graph, the processor further configured to match a segment of a payload for the element by matching the payload for the element at least zero times, a number of the at least zero times based on the node type, wherein extracting the node type, next node address, and the element from the node enable the processor to identify the pattern in the payload with less nodes relative to another NFA graph representing the pattern.

38. The system of claim 37, wherein the node type is at least one of variable count, fixed count, fixed count and variable count, character, case insensitive character, character class, string, case insensitive string, marked and split.

39. The system of claim 37, wherein the processor is further configured to push an entry to a run stack, the entry indicating at least one of the node type, an address of a next node in the graph, a duplicate bit, a reverse bit.

40. The system of claim 39, wherein the processor is further configured to push the entry to the run stack based on the node type.

41. The system of claim 40, wherein the processor is further configured to push the entry to the run stack if the node type is variable count, fixed-variable count, or split.

42. The system of claim 37, wherein the processor is further configured to:

pop a top entry of the run stack;

load a graph node indicated by the popped top entry; and

match the segment of the payload for the element, the element indicated in the loaded graph node, at the payload offset indicated in the popped top entry.

43. The system of claim 42, wherein the processor is further configured to pop the top entry of the run stack after a mismatch of matching the segment of the payload with the element.

44. The system of claim 37, wherein the processor is further configured to:

pop a top entry of the run stack;

extract graph node information stored in the popped top entry; and

match the segment of the payload for the element, the element indicated in the extracted graph node, at the payload offset indicated in the popped top entry.

45. The system of claim 37, wherein the node type of string represents a portion of the pattern of a plurality of values, each value being at least one of a byte, letter, or character.

46. The system of claim 37, wherein the processor is further configured to match the segment of the payload for the element associated with a node type of string by comparing at least two values within the segment against respective values of the string stored as the element in the node.

47. The system of claim 46, wherein the processor is further configured to, if the segment partially matches the element and if the length of the payload is shorter than the length of the string stored as the element of the node, load a next payload of a same flow of the payload and continuing matching remaining values in the string to the values in the next payload.

48. The system of claim 47, wherein the processor is further configured to push a partial match to a save buffer to be loaded upon loading the next payload of the same flow of the payload.

49. The system of claim 48, wherein the processor is further configured to push the partial match to the save buffer by storing a current run stack entry being processed in the save buffer and, upon loading the next payload, copy the stored at least one entry in the save buffer to the run stack.

50. The system of claim 37, wherein the processor is further configured to match with the element a variable number of times indicated by a count value extracted from the node.

51. The system of claim 37, wherein the variable number of times are at least zero times, at most a finite number of times, or at most an infinite number of times.

52. The system of claim 37, wherein the node type further indicates that the node is a greedy node, lazy node, possessive, or all match node.

53. The system of claim 37, wherein the processor is further configured to, if the node type is variable count lazy node, includes returning the shortest match found in the payload.

54. The system of claim 37, wherein the processor is further configured to, if the node type is variable count lazy node, push a stack entry to a run stack, the stack entry indicating the variable count lazy node and payload offset, and load a next node at the next node address in the graph.

55. The system of claim 54, wherein the processor is further configured to, if matching the next node element with the segment is a mismatch, pop the node of the node type of variable count lazy node from the stack entry of the run stack, and matching the element stored in the popped node with the payload segment.

56. The system of claim 55, wherein the processor is further configured to, upon matching the segment of the payload with the element stored in the popped node, reduce a count value of the variable count lazy node, push an updated stack entry to the run stack, and load a next node at the next node address stored in the popped entry.

57. The system of claim 54, wherein the processor is further configured to, if the segment of the payload continues in a next payload of a same flow of the first payload, push the run stack entry to a save buffer, and upon loading the next payload, load the save buffer entries into the run stack.

58. The system of claim 37, wherein the processor is further configured to, if the node type is variable count greedy node or variable count possessive node, return the longest match found in the payload.

59. The system of claim 37, wherein the processor is further configured to, if the node type is variable count greedy node,

fetch at least one segment of the payload,

match the at least one segments to the element,

if there is a nomatch and at least one segment matches the element a number of times less than or equal to a variable count in the variable count greedy node, or no more segments of the payload are available:

push a run stack entry storing the node type of the node, a payload offset of the at least one segment of the payload, and a number of segments matched, if the number of segments matched indicates the element has been matched less than a maximum number of times,

fetch a next node of the NFA graph indicated by the next node address, and

continue matching a next segment of the payload indicated by a position after the payload offset with a second element of the next node, wherein if there is a nomatch, pop the run stack entry from the run stack, decrement a number of segments matched count, pushing the updated run stack entry back to the run stack, and continue matching the next segment of the payload from the offset stored in the popped entry with the element of a next node stored at the next node address in the popped entry.

60. The system of claim 37, wherein the processor is further configured to, if the node type is variable count possessive node, continually match the payload segment to the element until a nomatch or a count of the variable count possessive node indicates the element has been matched a maximum number of times, and then continuing to match the subsequent segment of the payload with the next node stored at the next node address.

61. The system of claim 37, wherein the processor is further configured to, if the node type is variable count all match node, return all matches found in the payload.

62. The system of claim 37, wherein the processor is further configured to, if the node type is variable count all match node, match the segment to the element, and if it is a match, pushing a stack entry to a run stack, the stack entry indicating the variable count all match node and payload offset with an indication to continue matching the NFA graph, and loading a next node at the next node address, and if it is a nomatch, popping the stack entry from the run stack.

63. The system of claim 37, wherein a node type of fixed count represents a pattern to match for an element a fixed number of times.

64. The system of claim 63, wherein an element can be at least one of a character, character class and string.

65. The system of claim 37, wherein the processor is further configured to match the segment of the payload with the element associated with the node type of fixed count by matching at least two values within the segment against a value of the element stored in the node.

66. The system of claim 65, wherein the processor is further configured to, if the segment matches the element and if the length of the payload is shorter than the count of the fixed count node, load a next payload of a same flow of the payload and continue to match the remaining values in the element to the values in the next payload.

67. The system of claim 37, wherein the element can be at least one of a character, character class and string.

68. The system of claim 37, wherein the node type of character class represents a portion of the pattern to match an element by employing a Boolean-or operation of at least one value.

69. The system of claim 68, wherein each character class is stored in a memory as a mask, wherein an indicator corresponding to each possible character in the mask is set if the character is part of the character class, and not set if it is not part of the character class.

70. The system of claim 37, wherein upon the successful match, loading, from the next node extracted from the node, a second node of the NFA graph.

71. The system of claim 37, wherein the processor is further configured to:

if the node type is variable count, extract a count value from the node, the count value indicates a maximum number of times to match with the element,

if the node type is fixed count, extract a count value from the node, the count value indicates an exact number of times to match with the element,

if the node type is string, extract a count value from the node, the count value indicates a length of the string, and

if the node type is fixed-variable count, extract two count values from the node, a first count value indicates an exact number of times to match with the element and a second count value indicates a maximum number of times to match with the element.

72. The system of claim 37, wherein the processor is further configured to match the segment of the payload with the element associated with the node type of marked by indicating a match is found, and popping any entries in a run stack, or, if indicated in the node, continuing walking, in a reverse direction, a next node at the next address indicated in the node.