Data pattern analysis using optimized deterministic finite automaton

• US 7,991,723 B1
• Filed: 07/16/2007
• Issued: 08/02/2011
• Est. Priority Date: 07/16/2007
• Status: Active Grant

• Current Assignee: Quest Software, Inc.
• Original Assignee: SonicWALL, Inc. (SonicWall Holdings Ltd.)
• Inventors: Brady, Justin Michael, Dubrovsky, Aleksandr, Yanovsky, Boris, Yanovsky, Roman
• Primary Examiner(s): Gaffin; Jeffrey A
• Assistant Examiner(s): Kennedy; Adrian L
• Application Number:
  US11/778,546
• Time in Patent Office: 1,478 Days
• Field of Search: 706/45, 706/47, 706/48
• US Class Current: 706/45
• CPC Class Codes: G06F 16/9024 Graphs; Linked lists G06F16/9027 takes precedence
• CPC Class Codes: G06F 21/552 involving long-term monitoring or reporting
• CPC Class Codes: G06N 5/00 Computing arrangements using knowledge-based models
• CPC Class Codes: G06N 5/02 Knowledge representation; Symbolic representation
• CPC Class Codes: H04L 63/02 for separating internal from external traffic, e.g. firewalls
• CPC Class Codes: H04L 63/1416 Event detection, e.g. attack signature detection

Abstract

Techniques for data pattern analysis using deterministic finite automaton are described herein. In one embodiment, a number of transitions from a current node to one or more subsequent nodes representing one or more sequences of data patterns is determined, where each of the current node and subsequent nodes is associated with a deterministic finite automaton (DFA) state. A data structure is dynamically allocated for each of the subsequent nodes for storing information associated with each of the subsequent nodes, where data structures for the subsequent nodes are allocated in an array maintained by a data structure corresponding to the current node if the number of transitions is greater than a predetermined threshold. Other methods and apparatuses are also described.

Claims

1. A computer-implemented method to optimize data pattern analysis, comprising:

determining a number of possible transitions from a current node to one or more subsequent nodes representing one or more sequences of data patterns, each of the current node and subsequent nodes being associated with a deterministic finite automaton (DFA) state;

dynamically allocating a data structure for each of the subsequent nodes for storing information associated with each of the subsequent nodes, wherein data structures for the subsequent nodes are allocated in a logical array maintained by a data structure corresponding to the current node if the number of possible transitions is greater than a predetermined threshold to improve performance; and

determining whether each of the subsequent nodes includes a single child node, wherein the data structures for the subsequent nodes are allocated in an array maintained by a data structure corresponding to the current node if each of the subsequent nodes includes a single child node.

2. The method of claim 1, wherein each element of the logical array is directly accessible from the data structure corresponding to the current node.

3. The method of claim 1, wherein if the number of transitions is less than or equal to a predetermined threshold, the data structures for the subsequent nodes are allocated in a chain manner with a reference maintained by the data structure corresponding to the current node to reduce memory usage.

4. The method of claim 3, wherein the data structures for the subsequent nodes are allocated in a linked-list manner, wherein each of the data structures includes a first reference pointer linked to a previous data structure and a second reference pointer linked to a next data structure.

5. The method of claim 1, further comprising allocating an array for storing matched data for the subsequent nodes and accessible by the data structure of the current node, each element of the array corresponding to one subsequent node.

6. A machine-readable medium having instructions stored therein, which when executed by a processor, cause the processor to perform a method to optimize data pattern analysis, the method comprises:

determining a number of possible transitions from a current node to one or more subsequent nodes representing one or more sequences of data patterns, each of the current node and subsequent nodes being associated with a deterministic finite automaton (DFA) state;

dynamically allocating a data structure for each of the subsequent nodes for storing information associated with each of the subsequent nodes, wherein data structures for the subsequent nodes are allocated in a logical array maintained by a data structure corresponding to the current node if the number of possible transitions is greater than a predetermined threshold to improve performance; and

determining whether each of the subsequent nodes includes a single child node, wherein the data structures for the subsequent nodes are allocated in an array maintained by a data structure corresponding to the current node if each of the subsequent nodes includes a single child node.

7. The machine-readable medium of claim 6, wherein each element of the logical array is directly accessible from the data structure corresponding to the current node.

8. The machine-readable medium of claim 6, wherein if the number of transitions is less than or equal to a predetermined threshold, the data structures for the subsequent nodes are allocated in a chain manner with a reference maintained by the data structure corresponding to the current node to reduce memory usage.

9. The machine-readable medium of claim 8, wherein the data structures for the subsequent nodes are allocated in a linked-list manner, wherein each of the data structures includes a first reference pointer linked to a previous data structure and a second reference pointer linked to a next data structure.

10. The machine-readable medium of claim 6, wherein the method further comprises allocating an array for storing matched data for the subsequent nodes and accessible by the data structure of the current node, each element of the array corresponding to one subsequent node.

11. A data processing system, comprising:

a processor;

a memory for storing instructions, which when executed from the memory, cause the processor to

determine a number of possible transitions from a current node to one or more subsequent nodes representing one or more sequences of data patterns, each of the current node and subsequent nodes being associated with a deterministic finite automaton (DFA) state,

dynamically allocate a data structure for each of the subsequent nodes for storing information associated with each of the subsequent nodes, wherein data structures for the subsequent nodes are allocated in a logical array maintained by a data structure corresponding to the current node if the number of possible transitions is greater than a predetermined threshold to improve performance, and

determine whether each of the subsequent nodes includes a single child node, wherein the data structures for the subsequent nodes are allocated in an array maintained by a data structure corresponding to the current node if each of the subsequent nodes includes a single child node.

12. A computer-implemented method to optimize data pattern analysis, comprising:

determining a relationship of each of one or more child nodes transitioned from a root parent node, the relationship including a distance between each of the child nodes and the root parent node, the root parent node and child nodes representing one or more sequences of data patterns, wherein each of the root parent node and child nodes is associated with a deterministic finite automaton (DFA) state; and

dynamically allocating a data structure for each of the child nodes for storing information associated with each of the child nodes, wherein a data structure for a child node is allocated either in an array or in a linked-list manner dependent upon the relationship between the child node and the root parent node, wherein the data structure for the child node is allocated in an array if a distance between the child node and the root parent node is less than a predetermined threshold.

13. The method of claim 12, wherein the distance between the child node and the root parent node is represented by a number of intermediate nodes between the child node and the root parent node.

14. A machine-readable medium having instructions stored therein which when executed by a machine, cause the machine to perform a method to optimize data pattern analysis, the method comprising:

determining a relationship of each of one or more child nodes transitioned from a root parent node, the relationship including a distance between each of the child nodes and the root parent node, the root parent node and child nodes representing one or more sequences of data patterns, wherein each of the root parent node and child nodes is associated with a deterministic finite automaton (DFA) state; and

dynamically allocating a data structure for each of the child nodes for storing information associated with each of the child nodes, wherein a data structure for a child node is allocated either in an array or in a linked-list manner dependent upon the relationship between the child node and the root parent node, wherein the data structure for the child node is allocated in an array if a distance between the child node and the root parent node is less than a predetermined threshold.

15. The machine-readable medium of claim 14, wherein the distance between the child node and the root parent node is represented by a number of intermediate nodes between the child node and the root parent node.