NETWORK ATTACK DETECTION USING PARTIAL DETERMINISTIC FINITE AUTOMATON PATTERN MATCHING
First Claim
1. A method comprising:
- storing a set of full deterministic finite automaton (fDFA) nodes, wherein the fDFA nodes represent a full deterministic finite automaton fDFA that accepts symbol streams that conform to a symbol pattern;
creating a set of pDFA nodes, wherein the pDFA nodes represent a partial deterministic finite automaton (pDFA),wherein each of the pDFA nodes has a corresponding node in the fDFA nodes that has a visitation level that exceeds a visitation threshold,wherein each node in the pDFA nodes specifies a transition for a symbol to a node in the pDFA nodes when the corresponding node in the fDFA nodes specifies a transition for the symbol to a node in the fDFA nodes that has a visitation level that exceeds the visitation threshold, andwherein each node in the pDFA nodes specifies a transition for a symbol to a failure node in the pDFA nodes when the corresponding node in the fDFA nodes specifies a transition for the symbol to a node in the fDFA nodes that has a visitation level that does not exceed the visitation threshold;
receiving a symbol in a symbol stream;
determining whether a current node of the pDFA nodes is a failure node;
determining, when the current node of the pDFA nodes is not the failure node, whether the current node of the pDFA nodes specifies a transition for the symbol to the failure node;
identifying, when the current node of the pDFA nodes specifies a transition for the symbol to the failure node, a node in the fDFA nodes that corresponds to the current node of the pDFA nodes as a current node of the fDFA nodes; and
detecting a computer security threat when the current node of the pDFA nodes is the failure node and when the current node of the fDFA nodes specifies a transition for the symbol to an accepting node.
1 Assignment
0 Petitions
Accused Products
Abstract
This disclosure describes techniques for determining whether network traffic contains one or more computer security threats. In order to determine whether a symbol stream conforms to the symbol pattern, a security device stores a full deterministic finite automaton (fDFA) that accepts streams of symbols that conform to the symbol pattern. The security device also creates a partial deterministic finite automaton (pDFA) that includes nodes that correspond to the nodes in the fDFA that have the highest visitation levels. The security device processes each symbol in the symbol stream using the pDFA until a symbol causes the pDFA to transition to a failure node or to an accepting node. If the symbol causes the pDFA to transition to the failure node, the security device processes the symbol and subsequent symbols in the symbol stream using the fDFA.
-
Citations
32 Claims
-
1. A method comprising:
-
storing a set of full deterministic finite automaton (fDFA) nodes, wherein the fDFA nodes represent a full deterministic finite automaton fDFA that accepts symbol streams that conform to a symbol pattern; creating a set of pDFA nodes, wherein the pDFA nodes represent a partial deterministic finite automaton (pDFA), wherein each of the pDFA nodes has a corresponding node in the fDFA nodes that has a visitation level that exceeds a visitation threshold, wherein each node in the pDFA nodes specifies a transition for a symbol to a node in the pDFA nodes when the corresponding node in the fDFA nodes specifies a transition for the symbol to a node in the fDFA nodes that has a visitation level that exceeds the visitation threshold, and wherein each node in the pDFA nodes specifies a transition for a symbol to a failure node in the pDFA nodes when the corresponding node in the fDFA nodes specifies a transition for the symbol to a node in the fDFA nodes that has a visitation level that does not exceed the visitation threshold; receiving a symbol in a symbol stream; determining whether a current node of the pDFA nodes is a failure node; determining, when the current node of the pDFA nodes is not the failure node, whether the current node of the pDFA nodes specifies a transition for the symbol to the failure node; identifying, when the current node of the pDFA nodes specifies a transition for the symbol to the failure node, a node in the fDFA nodes that corresponds to the current node of the pDFA nodes as a current node of the fDFA nodes; and detecting a computer security threat when the current node of the pDFA nodes is the failure node and when the current node of the fDFA nodes specifies a transition for the symbol to an accepting node. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17)
-
-
18. An intermediate network device comprising:
-
a memory module that stores a set of full deterministic finite automaton (fDFA) nodes, wherein the fDFA nodes represent a full deterministic finite automaton (fDFA) that accepts strings of symbols that conform to a symbol pattern; a pDFA update module that creates a set of pDFA nodes, wherein the pDFA nodes represent a partial deterministic finite automaton (pDFA), wherein each of the pDFA nodes has a corresponding node in the fDFA nodes that has a visitation level that exceeds a visitation threshold, wherein each node in the pDFA nodes specifies a transition for a symbol to a node in the pDFA nodes when the corresponding node in the fDFA nodes specifies a transition for the symbol to a node in the fDFA nodes that has a visitation level that exceeds the visitation threshold, and wherein each node in the pDFA nodes specifies a transition for a symbol to a failure node in the pDFA nodes when the corresponding node in the fDFA nodes specifies a transition for the symbol to a node in the fDFA nodes that has a visitation level that does not exceed the visitation threshold; a DFA engine that receives a symbol in a symbol stream;
determines whether a current node of the pDFA nodes is a failure node;
determines, when the current node of the pDFA nodes is not the failure node, whether the current node of the pDFA nodes specifies a transition for the symbol to the failure node;
identifies, when the current node of the pDFA nodes specifies a transition for the symbol to the failure node, a node in the fDFA nodes that corresponds to the current node of the pDFA nodes as a current node of the fDFA nodes; and
detects a computer security threat when the current node of the pDFA nodes is the failure node and when the current node of the fDFA nodes specifies a transition for the symbol to an accepting node. - View Dependent Claims (19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29)
-
-
30. A computer-readable medium comprising instructions, when executed the instructions causing a processor to:
-
store a set of full deterministic finite automaton (fDFA) nodes, wherein the fDFA nodes represent a full deterministic finite automaton fDFA that accepts symbol streams that conform to a symbol pattern; create a set of pDFA nodes, wherein the pDFA nodes represent a partial deterministic finite automaton (pDFA), wherein each of the pDFA nodes has a corresponding node in the fDFA nodes that has a visitation level that exceeds a visitation threshold, wherein each node in the pDFA nodes specifies a transition for a symbol to a node in the pDFA nodes when the corresponding node in the fDFA nodes specifies a transition for the symbol to a node in the fDFA nodes that has a visitation level that exceeds the visitation threshold, and wherein each node in the pDFA nodes specifies a transition for a symbol to a failure node in the pDFA nodes when the corresponding node in the fDFA nodes specifies a transition for the symbol to a node in the fDFA nodes that has a visitation level that does not exceed the visitation threshold; receive a symbol in a symbol stream; determine whether a current node of the pDFA nodes is a failure node; determine, when the current node of the pDFA nodes is not the failure node, whether the current node of the pDFA nodes specifies a transition for the symbol to the failure node; identify, when the current node of the pDFA nodes specifies a transition for the symbol to the failure node, a node in the fDFA nodes that corresponds to the current node of the pDFA nodes as a current node of the fDFA nodes; and detect a computer security threat when the current node of the pDFA nodes is the failure node and when the current node of the fDFA nodes specifies a transition for the symbol to an accepting node. - View Dependent Claims (31)
-
-
32. A method comprising:
-
storing a set of full deterministic finite automaton (fDFA) nodes, wherein the fDFA nodes represent a full deterministic finite automaton fDFA that accepts symbol streams that conform to a symbol pattern; creating a set of pDFA nodes, wherein the pDFA nodes represent a partial deterministic finite automaton (pDFA), wherein each of the pDFA nodes has a corresponding node in the fDFA nodes that has a visitation level that exceeds a visitation threshold, wherein each node in the pDFA nodes specifies a transition for a symbol to a failure node in the pDFA nodes when the corresponding node in the fDFA nodes specifies a transition for the symbol to a node in the fDFA nodes that has a visitation level that does not exceed the visitation threshold; receiving a symbol in a symbol stream; and detecting a computer security threat using the pDFA nodes and the fDFA nodes.
-
Specification