Deterministic Finite Automata Graph Traversal with Nodal Bit Mapping

• US 20100114973A1
• Filed: 11/24/2008
• Published: 05/06/2010
• Est. Priority Date: 10/31/2008
• Status: Active Grant

• Current Assignee: Marvell Asia Pte Limited (Marvell Technology Group Limited)
• Original Assignee: Cavium, LLC (Marvell Technology Group Limited)
• Inventors: Goyal, Rajan
• Granted Patent: US 8,473,523 B2
• Time in Patent Office: Days
• US Class Current: 707/802
• CPC Class Codes: G06F 16/9024 Graphs; Linked lists G06F16/9027 takes precedence
• CPC Class Codes: G06F 16/90344 by using string matching techniques
• CPC Class Codes: G06F 2221/2145 Inheriting rights or properties, e.g., propagation of permissions or restrictions within a hierarchy
• CPC Class Codes: H04L 63/1416 Event detection, e.g. attack signature detection

Abstract

An apparatus, and corresponding method, for generating a graph used in performing a search for a match of at least one expression in an input stream is presented. The graph includes a number of interconnected nodes connected solely by valid arcs. A valid arc may also include a nodal bit map including structural information of a node to which the valid arc points to. A walker process may utilize the nodal bit map to determine if a memory access is necessary. The nodal bit map reduces the number of external memory access and therefore reduces system run time.

Claims

1. A computer implemented method for generating a bit map for a deterministic finite automata based graph, the method comprising:

analyzing valid arcs in the graph to determine a structural configuration of a current node being pointed to by a valid arc of a prior node;

constructing a respective bit map for each valid arc based on the structural configuration; and

storing the respective bit map of the current node in the valid arc of the prior node.

2. The method of claim 1 wherein determining the structural configuration includes determining valid arcs included within the current node.

3. The method of claim 1 wherein constructing the respective bit map includes:

providing a listing of indicator values, each indicator value being associated with a respective ASCII character, each indicator value providing an indication of whether a valid arc associated with a respective ASCII character exists in the current node;

assigning a negative value to an indicator value if the associated valid arc does not exist in the current node; and

assigning a positive value to an indicator value if the associated valid arc does exist in the current node.

4. The method of claim 3 further including:

traversing the graph with a walker process to search for a match of at least one expression in an input stream;

retrieving the valid arc associated with a current character of the input stream in the prior node;

reading the bit map associated with the valid arc;

determining the indicator value associated with a next character in the input stream; and

accessing a valid arc in the current node associated with the next character if the indicator value is positive.

5. The method of claim 4 further including returning the walker process to a root node, or a designated node associated with the current node, if the indicator value is negative.

6. The method of claim 5 further including storing an address of the root node, or designated node associated with the current node, in the valid arc pointing to the current node.

7. The method of claim 1 wherein constructing the respective bit map further includes:

providing a listing of indicator values, each indicator value being associated with a respective range of ASCII characters, each indicator value providing an indication of whether one valid arc associated with at least one respective ASCII character in the respective range exists in the current node;

assigning a negative value to an indicator value if all valid arcs in the respective range do not exist in the current node; and

assigning a positive value to an indicator value if at least one valid arc in the respective range exists in the current node.

8. The method of claim 7 further including:

traversing the graph with a walker process to search for a match of at least one expression in an input stream;

retrieving the valid arc associated with a current character of the input stream in the prior node;

reading the bit map associated with the valid arc;

determining the indicator value associated with a next character in the input stream; and

accessing an arc in the current node associated with the next character if the indicator value is positive.

9. The method of claim 8 further including returning the walker process to a root node, or a designated node associated with current node, if the indicator value is negative.

10. The method of claim 9 further including storing an address of the root node, or designated node associated with the current node, in the valid arc pointing to the current node.

11. The method of claim 7 wherein constructing the respective bit map further includes defining each respective range as having an equal number of associated ASCII characters.

12. The method of claim 8 wherein reading the bit map further includes dividing an ASCII numerical value associated with the next character by the number of characters included in each range, and determining a location of the indicator value associated with the next character as a function of the division.

13. The method of claim 8 wherein reading the bit map further includes reading a global look-up table to determine a location of the indicator value associated with the next character.

14. The method of claim 13 further including constructing the global look-up table as a function of ASCII characters included in searchable expressions used in creating the deterministic finite automata based graph.

15. The method of claim 14 further including assigning an index, in the nodal bit map, for all ASCII characters, not included in the searchable expressions, in a fixed or invalid value.

16. The method of claim 15 further including determining that the indicator value associated with the next character is negative if the character is associated with an invalid value.

17. The method of claim 14 further including determining that the indicator value in the nodal bit map associated with the next character is negative if the character is associated with a fixed value.

18. The method of claim 14 further including determining a weight of a character, and defining the respective range of the characters as a function of the weight.

19. The method of claim 18 further including defining the weight of the character as a function of a frequency the character appears in searchable expressions, or as a function of prior knowledge of a likelihood of a frequency the character will appear in an input stream.

20. The method of claim 13 further including storing the global look-up table in on-chip cache.

21. The method of claim 1 wherein the graph includes compressed nodes.

22. A system for locating an expression in a searchable deterministic finite automata based graph, the system comprising:

a walker process configured traverse the searchable graph, the graph including a plurality of interconnected nodes, where at least one node includes at least one valid arc; and

a bit map stored in a valid arc, associated with a prior node, the bit map providing structural information of a current node which the valid arc points to.

23. The system of claim 22 wherein the bit map further includes:

a listing of indicator values, each the indicator value being associated with a respective ASCII character, each indicator value providing an indication of whether a valid arc associated with a respective ASCII character exists in the current node;

wherein an indicator value is negative if the associated valid arc does not exist in the current node; and

wherein an indicator value is positive if the associated valid arc does exist in the current node.

24. The system of claim 23 wherein the walker process is further configured to retrieve the valid arc associated with a current character of the input stream in a prior node, the walker process is further configured to read the bit map stored in the valid arc and determine the indicator value associated with a next character in the input stream, wherein the walker process accesses in memory the next valid arc associated with the next character if the indicator value is positive.

25. The system of claim 24 wherein the walker processor is further configured to return to a root node, or a designated node, if the indicator value is negative.

26. The system of claim 25 wherein an address of the root node, or designated node, is stored in the valid arc pointing the current node.

27. The system of claim 22 wherein the respective bit map further includes:

a listing of indicator values, each indicator value being associated with a respective range of ASCII characters, each indicator value providing an indication of whether one valid arc associated with at least one respective ASCII character in the respective range exists in the current node;

wherein an indicator value is negative if all valid arcs in the respective range does not exist in the current node; and

wherein an indicator value is positive if at least one valid arc in the respective range exists in the current node.

28. The system of claim 27 wherein the walker process is further configured to retrieve the valid arc associated with a current character of the input stream in a prior node, the walker process is further configured to read the bit map stored in the valid arc and determine the indicator value associated with a next character in the input stream, wherein the walker process accesses in memory the next valid arc associated with the next character if the indicator value is positive.

29. The system of claim 28 wherein the walker processor is further configured to return to a root node, or a designated node, if the indicator value is negative.

30. The system of claim 29 wherein an address of the root node, or designated node, is stored in the valid arc pointing the current node.

31. The system of claim 28 wherein each respective range of the bit map has an equal number of associated ASCII characters.

32. The system of claim 31 wherein the walker process is further configured to divide an ASCII numerical value associated with the next character by the number of characters included in each range, the walker process further configured to determine a location of the indicator value associated with the next character as a function of the division.

33. The system of claim 27 further including a global look-up table providing location information of the indicator value associated with the next character.

34. The system of claim 33 wherein the global look-up table is organized as a function of ASCII characters included in searchable expressions used in creating the deterministic finite automata based graph.

35. The system of claim 34 wherein the index values, in the nodal bit map, are assigned for all ASCII characters, not included in the searchable expressions, in a fixed or invalid value.

36. The system of claim 35 wherein the walker process is configured to determine that the indicator value in the nodal bit map associated with the next character is negative if the character associated with a fixed value.

37. The system of claim 35 wherein the walker process is configured to determine that the indicator value associated with the next character is negative if the character associated with an invalid value.

38. The system of claim 34 wherein index values are further assigned with a weight of a character, the respective range of the characters defined as a function of the weight.

39. The system of claim 38 wherein the weight of the character is defined as a function of a frequency the character appears in searchable expressions, or as a function of prior knowledge of a likelihood of a frequency the character will appear in an input stream.

40. The system of claim 33 wherein the global look-up table is stored in on-chip cache.

41. The system of claim 22 wherein the graph includes compressed nodes.

42. A computer implemented method for traversing a deterministic finite automata-based graph comprising:

traversing nodes in the graph, with a walker process, to search for an expression in an input stream;

retrieving a valid arc associated with a current character of the input stream in a prior node;

reading a respective bit map of the valid arc;

determining if a next valid arc associated with a next character of the input stream exists in a current node based on a search indication provided by the reading; and

accessing in memory the next valid arc associated with the next character if the search indication is positive.