Traversal with arc configuration information

• US 9,495,479 B2
• Filed: 10/17/2014
• Issued: 11/15/2016
• 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
• Primary Examiner(s): Beausoliel, Jr., Robert
• Assistant Examiner(s): Pham, Michael
• Application Number:
  US14/516,807
• Publication Number:
  US 20150066991A1
• Time in Patent Office: 760 Days
• Field of Search: 707/798
• US Class Current: 1/1
• 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 comprising:

by a processor, given a current node and an arc pointing from the current node to a next node, analyzing arcs in a data structure to determine which of the arcs are valid arcs pointing from the next node;

by the processor, constructing arc configuration information associated with the next node, the arc configuration information limited to only arc configuration information of the next node and representing each valid arc pointing from the next node; and

by the processor, storing the arc configuration information associated with the next node, enabling the arc configuration information to be evaluated and each of the valid arcs pointing from the next node to be identified from the evaluation of the arc configuration information without the next node being read to reduce memory accesses and processing time of the processor.

2. The method of claim 1, wherein storing the arc configuration information includes storing the arc configuration information in the arc pointing from the current node to the next node.

3. The method of claim 1, wherein storing the arc configuration information includes storing the arc configuration information in a table accessed via an identifier of the next node.

4. The method of claim 1, wherein the data structure is an automata graph.

5. The method of claim 1, wherein the arc configuration information comprises a bit map.

6. The method of claim 1, wherein constructing the arc configuration information associated with the next node includes:

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

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

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

7. The method of claim 6, further including:

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

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

reading the arc configuration information associated with the next node;

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

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

8. The method of claim 1, wherein constructing the arc configuration information associated with the next node further includes:

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

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

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

9. The method of claim 8, further including:

traversing the data structure 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 current node;

reading the arc configuration information associated with the next node;

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

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

10. The method of claim 8, wherein constructing the arc configuration information associated with the next node further includes defining each respective range as having an equal number of associated characters.

11. The method of claim 10, wherein reading the arc configuration information associated with the next node further includes dividing a 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.

12. The method of claim 10, wherein reading the arc configuration information associated with the next node further includes reading a global look-up table to determine a location of the indicator value associated with the next character.

13. A system for locating an expression in a data structure, the system comprising:

a processor executing a walker process configured to traverse the data structure, the data structure including a plurality of interconnected nodes, wherein at least one node includes at least one valid arc; and

stored arc configuration information associated with a next node, the at least one valid arc associated with a current node and pointing from the current node to the next node, the arc configuration information limited to only arc configuration information of the next node and representing each valid arc pointing from the next node, the stored arc configuration information enabling each of the valid arcs pointing from the next node to be identified by the processor without the next node being read to reduce memory accesses and processing time of the processor.

14. The system of claim 13, wherein the stored arc configuration information is stored in the at least one valid arc associated with the current node and pointing from the current node to the next node.

15. The system of claim 13, wherein the stored arc configuration information is stored in a table accessed via an identifier of the next node.

16. The system of claim 13, wherein the data structure is an automata graph.

17. The system of claim 13, wherein the stored arc configuration information includes:

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

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

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

18. The system of claim 17, wherein the walker process is further configured to:

retrieve the at least one valid arc pointing from the current node to the next node and associated with a current character of an input stream;

read the stored arc configuration information associated with the next node; 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.

19. The system of claim 13, wherein the stored arc configuration information includes:

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

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

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

20. The system of claim 19, wherein the walker process is further configured to:

retrieve the at least one valid arc pointing from the current node to the next node and associated with a current character of an input stream;

read the stored arc configuration information associated with the next node; 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.

21. The system of claim 20, wherein each respective range of the stored arc configuration information has an equal number of associated characters.

22. The system of claim 21, wherein the walker process is further configured to:

divide a numerical value associated with the next character by the number of characters included in each range; and

determine a location of the indicator value associated with the next character as a function of the division.

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

24. The system of claim 13, wherein the stored arc configuration information comprises a bit map.

25. A computer implemented method for traversing a data structure comprising:

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

retrieving an arc associated with a current character of the input stream, the arc pointing from a current node to a next node;

reading arc configuration information associated with the next node, the arc configuration information limited to only arc configuration information of the next node and representing each valid arc pointing from the next node;

determining if a next valid arc associated with a next character of the input stream exists in the next 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.

26. A computer implemented method for traversing a data structure comprising:

traversing nodes in the data structure with a processor coupled to a memory and configured to traverse the nodes based on arc configuration information associated with a next node and stored in the memory, the arc configuration information limited to only arc configuration information of the next node and representing each valid arc pointing from the next node, to search for an expression in an input stream, each valid arc associated with a current character of the input stream.

27. The computer implemented method of claim 26, further comprising:

determining if a next valid arc associated with a next character of the input stream exists in the next node based on an indicator value included in the arc configuration information; and

accessing in memory the next valid arc associated with the next character based on the indicator value.

28. The computer implemented method of claim 26, wherein the arc configuration information comprises a bit map.

29. The computer implemented method of claim 28, wherein each bit in the bit map represents a 1-to-1 mapping of a given arc to an indicator value representing validity of the given arc.

30. The computer implemented method of claim 29, wherein each bit in the bit map represents an N-to-1 mapping of multiple given arcs to an indicator value representing validity of the multiple given arcs.