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

Patent metadata

Field	Value
Publication number	US-9563399-B2
Application number	US-201414186978-A
Country	US
Kind code	B2
Filing date	Feb 21, 2014
Priority date	Aug 30, 2013
Publication date	Feb 7, 2017
Grant date	Feb 7, 2017

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.

First claim

What is claimed is:

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.

Assignees

• Cavium Inc

Inventors

• Goyal Rajan
• Billa Satyanarayana Lakshmipathi

Classifications

• H04L41/28

  Restricting access to network management systems or functions, e.g. using authorisation function to access network configuration · CPC title

• G06F5/14 Primary

  for overflow or underflow handling, e.g. full or empty flags · CPC title

• G06F16/90344

  by using string matching techniques · CPC title

• G06F9/3885

  using a plurality of independent parallel functional units · CPC title

• H04L63/1408 Primary

  by monitoring network traffic (monitoring network traffic per se H04L43/00) · CPC title