Data pattern analysis using optimized deterministic finite automaton
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.
1. An apparatus for data pattern analysis, the apparatus comprising:
memory that stores information regarding a plurality of data patterns, each data pattern associated with an identified type of content;
a communication interface that receives a plurality of incoming data packets sent over a network; and
a processor that executes instructions stored in memory, wherein execution of the instructions by the processor:
inspects the incoming data packets to identify a number of transitions that are present in a state diagram from one deterministic finite automaton (DFA) state of the state diagram at a current node to another DFA state at each of a plurality of child nodes within the network;
dynamically allocates a first data structure for storing a plurality of child DFA states at the current node when the number of transitions is less than a predetermined threshold, wherein the plurality of child DFA states is linked in a chain in the first data structure;
dynamically allocates a second data structure for storing the plurality of child DFA states at the current node when the number of transitions is greater than the predetermined threshold, wherein each of the plurality of child DFA states is directly accessible from the second data structure;
identifies a match to at least one of the stored data patterns based on analyzing each of the incoming data packets by reference to the dynamically allocated data structure; and
prevents at least a portion of data included in the data packets from being sent to a computer based on the identified match.
2. The apparatus of claim 1 , wherein the predetermined threshold is configurable based on received input.
3. The apparatus of claim 1 , wherein each of the child DFA states in the first data structure is directly accessible via a link to an address of the respective child DFA state.
4. The apparatus of claim 1 , wherein each of the child DFA states in the first data structure requires only two pointers comprising a pointer to a parent state and a pointer to a further child state.
5. The apparatus of claim 1 , wherein the second data structure includes a whole data structure for each of the child DFA states.
6. The apparatus of claim 1 , wherein memory further stores at least one routine that is called when a match is identified.
7. The apparatus of claim 1 , wherein each of the incoming data packets is analyzed on a packet-by-packet basis.
8. The apparatus of claim 1 , wherein none of the incoming data packets are stored nor reassembled.
9. A method for data pattern analysis, the method comprising:
storing information in memory regarding a plurality of data patterns, each data pattern associated with an identified type of content;
receiving a plurality of incoming data packets over a network; and
executing instructions stored in memory, wherein execution of the instructions by a processor:
inspects the incoming data packets to identify a number of transitions that are present in a state diagram from one deterministic finite automaton (DFA) state of the state diagram at a current node to another DFA state at each of a plurality of child nodes in the network;
dynamically allocates a first data structure for storing a plurality of child DFA states at the current node when the number of transitions is less than a predetermined threshold, wherein the plurality of child DFA states is linked in a chain in the first data structure;
dynamically allocates a second data structure for storing the plurality of child DFA states at the current node when the number of transitions is greater than the predetermined threshold, wherein each of the plurality of child DFA states is directly accessible from the second data structure;
identifies a match to at least one of the stored data patterns based on analyzing each of the incoming data packets by reference to the dynamically allocated data structure; and
prevent at least a portion of data included in the data packets from being sent to a computer based on the identified match.
10. The method of claim 9 , further comprising configuring the predetermined threshold based on received input.
11. The method of claim 9 , wherein each of the child DFA states in the first data structure is directly accessible via a link to an address of the respective child DFA state.
12. The method of claim 9 , wherein each of the child DFA states in the first data structure requires only two pointers comprising a pointer to a parent state and a pointer to a further child state.
13. The method of claim 9 , wherein the second data structure includes a whole data structure for each of the child DFA states.
14. The method of claim 9 , further comprising storing at least one routine in memory to be called when a match is identified.
15. The method of claim 9 , wherein analyzing each of the incoming data packets comprises analyzing on a packet-by-packet basis.
16. The method of claim 9 , wherein none of the incoming data packets are stored nor reassembled.
17. A non-transitory computer-readable storage medium, having embodied thereon a program executable by a processor to perform a method for data pattern analysis, the method comprising:
storing information regarding a plurality of data patterns, each data pattern associated with an identified type of content;
receiving a plurality of incoming data packets over a network;
inspecting the incoming data packets to identify a number of transitions that are present in a state diagram from one deterministic finite automaton (DFA) state of the state diagram at a current node to another DFA state at each of a plurality of child nodes in the network;
dynamically allocating a first data structure for storing a plurality of DFA child states at the current node when the number of transitions is less than a predetermined threshold, wherein the plurality of child DFA states is linked in a chain in the first data structure;
dynamically allocating a second data structure for storing the plurality of child DFA states at the current node when the number of transitions is greater than the predetermined threshold, wherein each of the plurality of child DFA states is directly accessible from the second data structure;
identifying a match to at least one of the stored data patterns based on analyzing each of the incoming data packets by reference to the dynamically allocated data structure; and
preventing at least a portion of data included in the data packets from being sent to a computer based on the identified match.