NETWORK ATTACK DETECTION USING PARTIAL DETERMINISTIC FINITE AUTOMATON PATTERN MATCHING

• US 20080263665A1
• Filed: 04/20/2007
• Published: 10/23/2008
• Est. Priority Date: 04/20/2007
• Status: Active Grant

• Current Assignee: Juniper Networks Incorporated
• Original Assignee: Juniper Networks Incorporated
• Inventors: Rawat, Vipin, Ma, Qingming, Narayanaswamy, Krishna, Shieh, Michael Chuong, Burns, Bryan
• Granted Patent: US 7,904,961 B2
• Time in Patent Office: Days
• US Class Current: 726/23
• CPC Class Codes: G06F 21/552 involving long-term monitoring or reporting
• CPC Class Codes: G06F 21/74 operating in dual or compartmented mode, i.e. at least one secure mode
• CPC Class Codes: G06F 21/76 in application-specific integrated circuits [ASIC] or field-programmable devices, e.g. field-programmable gate arrays [FPGA] or programmable logic devices [PLD]
• CPC Class Codes: G06F 2221/2105 Dual mode as a secondary aspect
• CPC Class Codes: H04L 63/0227 Filtering policies mail message filtering H04L51/212
• CPC Class Codes: H04L 63/1416 Event detection, e.g. attack signature detection

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.

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.

2. The method of claim 1, wherein maintaining a set of pDFA nodes comprises storing the pDFA nodes in a single memory page.

3. The method of claim 1, wherein the symbol pattern is associated with a computer security threat.

4. The method of claim 1, wherein the method further comprises:

receiving network traffic from a first computer network;

extracting at least some of the symbol stream from the network traffic; and

retransmitting the network traffic on a second computer network when the symbol stream does not cause the pDFA or the fDFA to transition to an accepting node.

5. The method of claim 1,

wherein the method further comprises maintaining a table that has entries that identify a corresponding node in the fDFA nodes for each node in the pDFA nodes;

and

wherein identifying a node in the fDFA nodes comprises using the mapping to identify one of the fDFA nodes that corresponds to the current node in the pDFA.

6. The method of claim 1, wherein creating a set of nodes that represent a pDFA comprises:

determining, when the current node of the pDFA nodes specifies a transition for the symbol to the failure node, whether a count of the pDFA nodes exceeds a size threshold; and

identifying one of the fDFA nodes to which the current node of the fDFA node specifies a transition for the symbol; and

creating a new one of the pDFA nodes that corresponds to this one of the fDFA nodes when the count of the pDFA nodes does not exceed the size threshold.

7. The method of claim 6, wherein creating a set of pDFA nodes further comprises:

removing a second node from the set of pDFA nodes when the count of the pDFA nodes exceeds the size threshold and when the visitation level of the one of the pDFA nodes exceeds a visitation level of the second node; and

updating the pDFA nodes such that each one of the pDFA nodes that specified a transition to the second node specifies a transition to the failure node of the pDFA in place of the transition to the second node.

8. The method of claim 1, wherein creating a set of pDFA nodes comprises creating a set of pDFA nodes that are formatted using a bitmap encoding scheme such that each of the pDFA nodes includes a fixed-length bitmap portion and a variable-length list of node indexes,

wherein each of the node indexes indicates a memory location at which another one of the pDFA nodes is stored, and

wherein the bitmap portion comprises a bits associated with different symbols.

9. The method of claim 8, wherein creating a set of pDFA nodes further comprises creating a set of pDFA nodes that are formatted using the bitmap encoding scheme such that when a one of the bits in the bitmap portion of one of the pDFA nodes is associated with a symbol and is set to a first value, the list of node indexes includes a node index associated with the symbol, and when the one of the bits is set to a second value, the list of node indexes does not include a node index associated with the symbol.

10. The method of claim 1, wherein storing the fDFA nodes comprises storing the fDFA nodes in a plurality of memory pages.

11. The method of claim 1, wherein the method further comprises identifying, when the current node of the pDFA nodes specifies a transition for the symbol to a node in the pDFA nodes, the node in the pDFA nodes as a new current node of the pDFA nodes.

12. The method of claim 11, wherein identifying the node in the pDFA nodes as a new current node of the pDFA nodes comprises increasing a visitation level of the new current node of the pDFA nodes and a one of the fDFA nodes that corresponds to the new current node of the pDFA nodes.

13. The method of claim 1, wherein the method further comprises accepting the symbol stream as conforming to the symbol pattern when the current node of the pDFA nodes specifies a transition for the symbol to an accepting node.

14. The method of claim 11, wherein determining whether the current node of the pDFA nodes specifies a transition for the symbol to the failure node comprises determining whether the symbol is a member of a class of symbols defined by a meta-symbol.

15. The method of claim 1,

wherein the set of fDFA nodes is a first set of fDFA nodes;

wherein the symbol pattern is a first symbol pattern;

wherein the method further comprises storing a second set of fDFA nodes that represent a second fDFA, wherein the second fDFA accepts symbol streams that conform to a second symbol pattern;

wherein creating a set of pDFA nodes comprises creating a set of pDFA nodes in which each the pDFA nodes corresponds to a node in the first set of fDFA nodes that has a visitation level that exceeds the visitation threshold and/or corresponds to a node in the second set of fDFA nodes that has a visitation level that exceeds the visitation level; and

wherein the method further comprises;

identifying, when the current node of the pDFA nodes specifies a transition for the symbol to the failure node, a node in the second set of fDFA nodes that corresponds to the current node of the pDFA nodes as a current node of the second set of fDFA nodes; and

accepting the symbol stream as conforming to the second symbol pattern when the current node of the pDFA nodes is the failure node and when the current node of the second fDFA nodes specifies a transition for the symbol to an accepting node.

16. The method of claim 1, wherein creating the set of pDFA nodes comprises:

creating a first set of temporary pDFA nodes, wherein each node in the first set of temporary pDFA nodes has a corresponding node in the first set of fDFA nodes that has a visitation level that exceeds a visitation threshold,

wherein each node in the first set of temporary pDFA nodes specifies a transition for a symbol to a node in the first set of temporary pDFA nodes when the corresponding node in the first set of fDFA nodes specifies a transition for the symbol to a node in the first set of fDFA nodes that has a visitation level that exceeds the visitation threshold,

wherein each node in the first set of temporary pDFA nodes specifies a transition for a symbol to a failure node in the first set of temporary pDFA nodes when the corresponding node in the first set of fDFA nodes specifies a transition for the symbol to a node in the first set of fDFA nodes that has a visitation level that does not exceed the visitation threshold;

creating a second set of temporary pDFA nodes, wherein each node in the second set of temporary pDFA nodes has a corresponding node in the second set of fDFA nodes that has a visitation level that exceeds a visitation threshold,

wherein each node in the second set of temporary pDFA nodes specifies a transition for a symbol to a node in the second set of temporary pDFA nodes when the corresponding node in the second set of fDFA nodes specifies a transition for the symbol to a node in the second set of fDFA nodes that has a visitation level that exceeds the visitation threshold,

wherein each node in the second set of temporary pDFA nodes specifies a transition for a symbol to a failure node in the second set of temporary pDFA nodes when the corresponding node in the second set of fDFA nodes specifies a transition for the symbol to a node in the second set of fDFA nodes that has a visitation level that does not exceed the visitation threshold;

merging the first set of temporary pDFA nodes and the second set of temporary pDFA nodes in order to create the set of pDFA nodes.

17. The method of claim 16, wherein merging the first set of temporary pDFA nodes and the second set of temporary pDFA nodes comprises:

creating a first new node that specifies each of the transitions specified in a node in the first set of temporary pDFA nodes and each of the transitions specified in a node in the second set of temporary pDFA nodes;

identifying a transition specified by the first new node to a node in the first set of temporary pDFA nodes for a symbol;

identifying a transition specified by the first new node to a node in the second set of temporary pDFA nodes for the same symbol;

recursively creating a second new node that a represents a merger of the node in the first set of temporary pDFA nodes and the node in the second set of temporary pDFA nodes; and

specifying a transition in the first new node to the second new node for the symbol.

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.

19. The intermediate network device of claim 18, wherein the memory module stores the set of pDFA nodes within a single memory page.

20. The intermediate network device of claim 18, wherein the symbol pattern is associated with a computer security threat.

21. The intermediate network device of claim 18, wherein the intermediate network device further comprises:

a first network interface that receives network traffic from a first computer network;

an application-layer module that extracts at least some of the symbol stream from the network traffic; and

a second network interface that retransmits the network traffic on a second computer network when the symbol stream does not cause the pDFA or the fDFA to transition to an accepting node.

22. The intermediate network device of claim 18,

wherein the DFA engine determines whether a count of the pDFA nodes exceeds a size threshold;

and

wherein the pDFA update module creates a node in the set pDFA nodes that corresponds to a node in the set of fDFA nodes when a count of the pDFA nodes does not exceed a size threshold and when the node in the set of fDFA nodes becomes the current node of the fDFA.

23. The intermediate network device of claim 22,

wherein the pDFA update module removes a second node from the set of pDFA nodes when the count of the pDFA nodes exceeds the size threshold and when the visitation level of the one of the fDFA nodes exceeds a visitation level of the second node;

and

wherein the pDFA update module updates nodes in the set of pDFA nodes such that each one of the pDFA nodes that specified a transition to the second node specifies a transition to the failure node of the pDFA in place of the transition to the second node.

24. The intermediate network device of claim 18, wherein the memory module stores the pDFA nodes in a plurality of memory pages.

25. The intermediate network device of claim 18, wherein the DFA engine identifies, when the current node of the pDFA nodes specifies a transition for the symbol to a node in the pDFA nodes, the node in the pDFA nodes as a new current node of the pDFA nodes.

26. The intermediate network device of claim 25, wherein the DFA engine increases a visitation level of the new current node of the pDFA nodes and a one of the fDFA nodes that corresponds to the new current node of the pDFA nodes.

27. The intermediate network device of claim 18, wherein the DFA engine accepts the symbol stream as conforming to the symbol pattern when the current node of the pDFA nodes specifies a transition for the symbol to an accepting node.

28. The intermediate network device of claim 18,

wherein the set of fDFA nodes is a first set of fDFA nodes,

wherein the symbol pattern is a first symbol pattern, and

wherein the memory module stores a second set of fDFA nodes that represent a second fDFA, wherein the second fDFA accepts symbol streams that conform to a second symbol pattern;

wherein each node in the pDFA corresponds to a node in the first set of fDFA nodes that has a visitation level that exceeds the visitation threshold and/or corresponds to a node in the second set of fDFA nodes that has a visitation level that exceeds the visitation level;

wherein the DFA engine identifies, when the current node of the pDFA nodes specifies a transition for the symbol to the failure node, a node in the second set of fDFA nodes that corresponds to the current node of the pDFA nodes as a current node of the second set of fDFA nodes; and

wherein the DFA engine accepts the symbol stream as conforming to the second symbol pattern when the current node of the pDFA nodes is the failure node and when the current node of the second fDFA nodes specifies a transition for the symbol to an accepting node.

29. The intermediate network device of claim 28,

wherein the pDFA update module creates the set of pDFA nodes by creating a first set of temporary pDFA nodes, creating a second set of temporary pDFA nodes, and by merging the first set of temporary pDFA nodes and the second set of temporary pDFA nodes to create the set of pDFA nodes,

wherein each node in the first set of temporary pDFA nodes has a corresponding node in the first set of fDFA nodes that has a visitation level that exceeds a visitation threshold,

wherein each node in the first set of temporary pDFA nodes specifies a transition for a symbol to a node in the first set of temporary pDFA nodes when the corresponding node in the first set of fDFA nodes specifies a transition for the symbol to a node in the first set of fDFA nodes that has a visitation level that exceeds the visitation threshold,

wherein each node in the first set of temporary pDFA nodes specifies a transition for a symbol to a failure node in the first set of temporary pDFA nodes when the corresponding node in the first set of fDFA nodes specifies a transition for the symbol to a node in the first set of fDFA nodes that has a visitation level that does not exceed the visitation threshold;

wherein each node in the second set of temporary pDFA nodes has a corresponding node in the second set of fDFA nodes that has a visitation level that exceeds a visitation threshold,

wherein each node in the second set of temporary pDFA nodes specifies a transition for a symbol to a node in the second set of temporary pDFA nodes when the corresponding node in the second set of fDFA nodes specifies a transition for the symbol to a node in the second set of fDFA nodes that has a visitation level that exceeds the visitation threshold, and

wherein each node in the second set of temporary pDFA nodes specifies a transition for a symbol to a failure node in the second set of temporary pDFA nodes when the corresponding node in the second set of fDFA nodes specifies a transition for the symbol to a node in the second set of fDFA nodes that has a visitation level that does not exceed the visitation threshold.

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.

31. The computer-readable medium of claim 30,

wherein the instructions that cause the processor to store a set of fDFA nodes comprise instructions that cause the processor to store the set of fDFA nodes in a plurality of memory pages;

and

wherein the instructions that cause the processor to create the set of pDFA nodes comprise instructions that cause the processor to store the set of pDFA nodes in a single memory page.

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.