Generating a non-deterministic finite automata (NFA) graph for regular expression patterns with advanced features

• US 9,563,399 B2
• Filed: 02/21/2014
• Issued: 02/07/2017
• 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: Goyal, Rajan, Billa, Satyanarayana Lakshmipathi
• Primary Examiner(s): Morrison, Jay
• Application Number:
  US14/186,978
• Publication Number:
  US 20150066927A1
• Time in Patent Office: 1,082 Days
• Field of Search: None
• 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 an embodiment, a method of compiling a pattern into a non-deterministic finite automata (NFA) graph includes examining the pattern for a plurality of elements and a plurality of node types. Each node type can correspond with an element. Each element of the pattern can be matched at least zero times. The method further includes generating a plurality of nodes of the NFA graph. Each of the plurality of nodes can be configured to match for one of the plurality of elements. The node can indicate the next node address in the NFA graph, a count value, and/or node type corresponding to the element. The node can also indicate the element representing a character, character class or string. The character can also be a value or a letter.

Claims

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

examining the pattern for a plurality of elements and a plurality of node types, each node type corresponding with an element, each element of the pattern to be matched at least zero times, the element representing a character, character class or string;

generating a plurality of nodes of the NFA graph, each node of the plurality of nodes configured to match with one of the plurality of elements and store the node type corresponding to the element, a next node address in the NFA graph, a count value, and the element, wherein the next node address and the count value are applicable as a function of the node type stored and wherein the plurality of nodes generated enable a graph walk engine to identify the pattern in a payload with less nodes relative to another NFA graph representing the pattern and employed by the graph walk engine to identify the pattern in the payload.

2. The method of claim 1, wherein the plurality of node types includes a variable count node type, fixed count node type, fixed count and variable count node type, character node type, case insensitive character node type, character class node type, case sensitive string node type, case insensitive string node type, marked node type, or split node type and the graph walk engine processes each node as a function of the node storing one of the variable count node type, fixed count node type, fixed count and variable count node type, character node type, case insensitive character node type, character class node type, case sensitive string node type, case insensitive string node type, marked noted type, or split node type.

3. The method of claim 1, wherein the plurality of node types includes a variable count node type and, based on storing the variable count node type, the element is a character, character class index, or string and the next node address and the count value are applicable.

4. The method of claim 1, wherein the plurality of node types includes a fixed count node type and, based on storing the fixed count node type, the element is a character or character class, and the next node address and the count value are applicable.

5. The method of claim 1, wherein the examining includes matching the pattern for at least one of an indication of a variable count node type, a fixed count node type, a fixed-variable count node type, character node type, case insensitive character node type, character class node type, string node type, case insensitive string node type, marked node type, and split node type.

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

7. The method of claim 1, wherein the plurality of node types includes a string node type and the examining includes examining the pattern for the string node type, wherein examining the pattern for the string node type includes determining whether a portion of the pattern indicates consecutive values.

8. The method of claim 7, wherein, based on a determination that the portion of the pattern indicates consecutive values, examining the pattern for the string node type further includes determining whether the consecutive values of the portion of the pattern are without intervening non-string node types.

9. The method of claim 1, wherein the plurality of node types includes a variable count node type and the variable count node type represents a portion of the pattern to match for the element a variable number of times.

10. The method of claim 1, wherein the plurality of node types includes a variable count node type and the examining includes examining the pattern for the variable count node type, and wherein examining the pattern for the variable count node type includes determining whether a portion of the pattern indicates matching for the element a variable number of times.

11. The method of claim 10, wherein the variable number of times is at least one of a finite number of times or an infinite number of times.

12. The method of claim 11, wherein the pattern includes a symbol representing infinity to trigger a determination that the portion of the pattern indicates matching for the element the infinite number of times.

13. The method of claim 11, wherein examining the pattern for the variable count node type further includes determining whether the portion of the pattern indicates matching for the element at least zero times.

14. The method of claim 1, wherein the plurality of node types includes a fixed count node type and the fixed count node type represents a portion of the pattern to match for the element a fixed number of times.

15. The method of claim 1, wherein the plurality of node types includes a fixed-variable count node type and the fixed-variable count node type represents a portion of the pattern to match for the element a fixed number of times followed by a variable number of times.

16. The method of claim 1, wherein the plurality of node types includes a fixed-variable count node type and the examining includes examining the pattern for the fixed-variable count node type, and wherein examining the pattern for the fixed-variable node type includes determining whether a portion of the pattern indicates matching for the element at least one time and at most a finite number of times or an infinite number of times.

17. The method of claim 16, wherein the pattern includes a symbol representing infinity to trigger a determination that the portion of the pattern indicates matching for the element the infinite number of times.

18. The method of claim 1, wherein the plurality of node types includes a character class node type and the character class node type represents a portion of the pattern to match for the element by employing a Boolean-or operation of at least one value.

19. The method of claim 18, further comprising storing a unique character class as a mask, wherein each possible character in the mask is set based on the character being part of the unique character class, and not set based on the character not being part of the unique character class.

20. The method of claim 19, wherein the element of the node includes a character class index corresponding to the unique character class.

21. The method of claim 20, wherein the character class index and a payload segment are employed by the graph walk engine as an index to the mask and in response to the indexed entry being set, the graph walk engine determines the payload is matched to the unique character class.

22. The method of claim 1, wherein the plurality of node types includes a variable count node type and the variable count node type indicates that the node is a greedy node, lazy node, possessive node, or all match node.

23. The method of claim 22, wherein the variable count node type indicating a greedy or possessive node indicates matching for the longest possible match in the payload.

24. The method of claim 22, wherein the variable count node type indicating the lazy node indicates matching for the shortest possible match in the payload.

25. The method of claim 22, wherein the variable count node type indicating the all match node indicates matching for all matches in the payload.

26. The method of claim 1, wherein the examining includes identifying at least one portion of the pattern as a character class node type and corresponding element.

27. The method of claim 26, wherein the examining includes identifying at least two portions of the pattern as a character class node type and corresponding element, and further comprising:

generating a bitmap for each of the portions, wherein each bit of the bitmap represents a value matching the element, and each bitmap is associated with a unique character class index.

28. The method of claim 27, further comprising associating a first portion of the at least two portions and a second portion of the at least two portions with a same bitmap based on the first portion of the at least two portions and the second portion of the at least two portions having a same corresponding element.

29. The method of claim 28, wherein examining the pattern includes examining a plurality of patterns, wherein the first and second portion can be in separate patterns.

30. The method of claim 1, wherein examining the pattern includes finding at least one meta-character, and generating the plurality of nodes includes determining at least one of the node type or the count value based on the at least one meta-character.

31. A computer system for compiling a pattern into a non-deterministic finite automata (NFA) graph, the system comprising:

a memory; and

a processor, the processor coupled to the memory and configured to examine the pattern for a plurality of elements and a plurality of node types, each node type corresponding with an element, each element of the pattern to be matched at least zero times, the element representing a character, character class or string; and

wherein the processor is further configured to generate a plurality of nodes of the NFA graph, each node of the plurality of nodes configured to match with one of the plurality of elements and store the node type corresponding to the element, a next node address in the NFA graph, a count value, and the element, wherein the next node address and the count value are applicable as a function of the node type stored and wherein the plurality of nodes generated enable a graph walk engine to identify the pattern in a payload with less nodes relative to another NFA graph representing the pattern and employed by the graph walk engine to identify the pattern in the payload.

32. The system of claim 31, wherein the plurality of node types includes a variable count node type, fixed count node type, fixed count and variable count node type, character node type, case insensitive character node type, character class node type, case sensitive string node type, case insensitive string node type, marked node type, or split node type and the graph walk engine processes each node as a function of the node storing one of the variable count node type, fixed count node type, fixed count and variable count node type, character node type, case insensitive character node type, character class node type, case sensitive string node type, case insensitive string node type, marked noted type, or split node type.

33. The system of claim 31, wherein the plurality of node types includes a variable count node type and, based on storing the variable count node type, the element is a character, character class index, or string and the next node address and the count value are applicable.

34. The system of claim 31, wherein the plurality of node types includes a fixed count node type and, based on storing the fixed count node type, the element is a character or character class, and the next node address and the count value are applicable.

35. The system of claim 31, wherein the processor is further configured to match the pattern for at least one of an indication of a variable count node type, fixed count node type, fixed-variable count node type, character node type, case insensitive character node type, character class node type, string node type, case insensitive string node type, marked node type, and split node type.

36. The system of claim 31, wherein the plurality of node types includes a string node type and the string node type represents a portion of the pattern of a plurality of values, each value being at least one of a byte, letter, or character.

37. The system of claim 31, wherein the processor is further configured to determine whether a portion of the pattern indicates consecutive values.

38. The system of claim 37, wherein the processor is further configured to determine whether the consecutive values of the portion of the pattern are without intervening non-string node types.

39. The system of claim 31, wherein the plurality of node types includes a variable count node type and the variable count node type represents a portion of the pattern to match for the element a variable number of times.

40. The system of claim 31, wherein the plurality of node types includes a variable count node type and the examining includes examining the pattern for the variable count node type, and wherein examining the pattern for the variable count node type includes determining whether a portion of the pattern indicates matching for the element a variable number of times.

41. The system of claim 40, wherein the variable number of times is at least one of a finite number of times or an infinite number of times.

42. The system of claim 41, wherein the pattern includes a symbol representing infinity to trigger a determination that the portion of the pattern indicates matching for the element the infinite number of times.

43. The system of claim 41, wherein the processor is further configured to determine whether the portion of the pattern indicates matching for the element at least zero times.

44. The system of claim 31, wherein the plurality of node types includes a fixed count node type and the fixed count node type represents a portion of the pattern to match for the element a fixed number of times.

45. The system of claim 31, wherein the plurality of node types includes a fixed-variable count node type and the fixed-variable count node type represents a portion of the pattern to match for the element a fixed number of times followed by a variable number of times.

46. The system of claim 31, wherein the processor is further configured to determine whether a portion of the pattern indicates matching for the element at least one time and at most a finite number of times or an infinite number of times.

47. The system of claim 46, wherein the pattern includes a symbol representing infinity to trigger a determination that the portion of the pattern indicates matching for the element the infinite number of times.

48. The system of claim 31, wherein the plurality of node types includes a character class node type and the character class node type represents a portion of the pattern to match for the element by employing a Boolean-or operation of at least one value.

49. The system of claim 48, wherein the processor is further configured to store a unique character class as a mask, wherein each possible character in the mask is set based on the character being part of the character class, and not set based on the character not being part of the character class.

50. The system of claim 49, wherein the element of the node includes a character class index corresponding to the unique character class.

51. The system of claim 50, wherein the character class index and a payload segment are employed by the graph walk engine as an index to the mask such that in response to the indexed entry being set, the graph walk engine determines the payload is matched to the character class.

52. The system of claim 31, wherein the plurality of node types includes a variable count node type and the variable count node type indicates that the node is a greedy node, lazy node, possessive node, or all match node.

53. The system of claim 52, wherein the variable count node type indicating a greedy or possessive node indicates matching for the longest possible match in the payload.

54. The system of claim 52, wherein the variable count node type indicating the lazy node indicates matching for the shortest possible match in the payload.

55. The system of claim 52, wherein the variable count node type indicating the all match node indicates matching for all matches in the payload.

56. The system of claim 31, wherein the processor is further configured to identify at least one portion of the pattern as a character class node type and corresponding element.

57. The system of claim 56, wherein the processor is further configured to identify at least two portions of the pattern as a character class node type and corresponding element and generate a bitmap for each of the portions, wherein each bit of the bitmap represents a value matching the element, and each bitmap is associated with a unique character class index.

58. The system of claim 57, wherein the processor is further configured to associate a first portion of the at least two portions and a second portion of the at least two portions with a same bitmap based on the first portion of the at least two portions and the second portion of the at least two portions having a same corresponding element.

59. The system of claim 58, wherein the processor is further configured to examine a plurality of patterns, wherein the first and second portion can be in separate patterns.

60. The system of claim 31, wherein the processor is further configured to find at least one meta-character and generate the plurality of nodes by determining at least one of the node type or the count value based on the at least one meta-character.