EFFICIENT APPLICATION IDENTIFICATION WITH NETWORK DEVICES
First Claim
1. A method comprising:
- storing, with a network device, first data that defines a group deterministic finite automata (DFA), wherein the group DFA is formed by a merger of;
(i) an individual non-explosive DFA generated from a corresponding non-explosive regular expression, and (ii) a fingerprint DFA (f-DFA) generated from a corresponding signature fingerprint, wherein the non-explosive regular expression comprises a regular expression determined not to cause state explosion during the merge to form the group DFA, wherein the signature fingerprint comprises a segment of an explosive regular expression that uniquely identifies the explosive regular expression, and wherein the explosive regular expression comprises a regular expression determined to cause state explosion during the merge;
storing, with the network device, second data that defines, for the explosive regular expression, an individual DFA separate from the group DFA, wherein the signature fingerprint uniquely identifies the explosive regular expression from which the individual DFA is generated;
receiving, with a network device, a packet;
traversing, with the network device prior to traversing the individual DFA, the group DFA in order to determine whether the packet includes the segment of the explosive regular expression defined by the signature fingerprint; and
traversing, with the network device, the individual DFA associated with the signature fingerprint based on the determination that the packet includes the segment of the explosive regular expression to identify a network application to which the packet corresponds.
1 Assignment
0 Petitions
Accused Products
Abstract
In general, techniques are described for efficiently implementing application identification within network devices. In particular, a network device includes a control unit that stores data defining a group Deterministic Finite Automata (DFA) and an individual DFA. The group DFA is formed by merging non-explosive DFAs generated from corresponding non-explosive regular expressions (regexs) and fingerprint DFAs (f-DFAs) generated from signature fingerprints extracted from explosive regexs. The non-explosive regexs comprise regexs determined not to cause state explosion during generation of the group DFA, the signature fingerprints comprise segments of explosive regexs that uniquely identifies the explosive regexs, and the explosive regexs comprise regexs determined to cause state explosion during generation of the group DFA. The network device includes an interface that receives a packet and the control unit traverses first the group DFA and then, in some instances, the individual DFAs to more efficiently identify network applications to which packets correspond.
624 Citations
33 Claims
-
1. A method comprising:
-
storing, with a network device, first data that defines a group deterministic finite automata (DFA), wherein the group DFA is formed by a merger of;
(i) an individual non-explosive DFA generated from a corresponding non-explosive regular expression, and (ii) a fingerprint DFA (f-DFA) generated from a corresponding signature fingerprint, wherein the non-explosive regular expression comprises a regular expression determined not to cause state explosion during the merge to form the group DFA, wherein the signature fingerprint comprises a segment of an explosive regular expression that uniquely identifies the explosive regular expression, and wherein the explosive regular expression comprises a regular expression determined to cause state explosion during the merge;storing, with the network device, second data that defines, for the explosive regular expression, an individual DFA separate from the group DFA, wherein the signature fingerprint uniquely identifies the explosive regular expression from which the individual DFA is generated; receiving, with a network device, a packet; traversing, with the network device prior to traversing the individual DFA, the group DFA in order to determine whether the packet includes the segment of the explosive regular expression defined by the signature fingerprint; and traversing, with the network device, the individual DFA associated with the signature fingerprint based on the determination that the packet includes the segment of the explosive regular expression to identify a network application to which the packet corresponds. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 18)
-
-
10. A network device comprising:
-
a control unit that stores first data that defines a group deterministic finite automata (DFA), wherein the group DFA is formed by a merger of;
(i) an individual non-explosive DFA generated from a corresponding non-explosive regular expression, and (ii) a fingerprint DFA (f-DFA) generated from a corresponding signature fingerprint, wherein the non-explosive regular expression comprises a regular expression determined not to cause state explosion during the merge to form the group DFA, wherein the signature fingerprint comprises a segment of an explosive regular expression that uniquely identifies the explosive regular expression, and wherein the explosive regular expression comprises a regular expression determined to cause state explosion during the merge and stores second data that defines, for the explosive regular expression, an individual DFA separate from the group DFA, wherein the signature fingerprint uniquely identifies the explosive regular expression from which the individual DFA is generated; andat least one interface card that receives a packet, wherein the control unit traverses, prior to traversing the individual DFA, the group DFA in order to determine whether the packet includes the segment of the explosive regular expression defined by the signature fingerprint, traverses the individual DFA associated with the signature fingerprint based on the determination that the packet includes the segment of the explosive regular expression to identify a network application to which the packet corresponds. - View Dependent Claims (11, 12, 13, 14, 15, 16, 17)
-
-
19. A computer-readable medium comprising instructions for causing a programmable processor to:
-
store, with a network device, first data that defines a group deterministic finite automata (DFA), wherein the group DFA is formed by a merger of;
(i) an individual non-explosive DFA generated from a corresponding non-explosive regular expression, and (ii) a fingerprint DFA (f-DFA) generated from a corresponding signature fingerprint, wherein the non-explosive regular expression comprises a regular expression determined not to cause state explosion during the merge to form the group DFA, wherein the signature fingerprint comprises a segment of an explosive regular expression that uniquely identifies the explosive regular expression, and wherein the explosive regular expression comprises a regular expression determined to cause state explosion during the merge;store, with the network device, second data that defines, for the explosive regular expression, an individual DFA separate from the group DFA, wherein the signature fingerprint uniquely identifies the explosive regular expression from which the individual DFA is generated; receive, with a network device, a packet; traverse, with the network device prior to traversing the individual DFA, the group DFA in order to determine whether the packet includes the segment of the explosive regular expression defined by the signature fingerprint; and traverse, with the network device, the individual DFA associated with the signature fingerprint based on the determination that the packet includes the segment of the explosive regular expression to identify a network application to which the packet corresponds.
-
-
20. A method comprising:
-
storing, with a computing device, data defining a plurality of regular expressions; determining whether each of the plurality of regular expressions causes state explosion; classifying, with the computing device, each of the plurality of regular expressions as non-explosive or explosive depending on the determination, wherein one of the plurality of regular expression is classified as non-explosive and another one of the plurality the plurality of regular expressions is classified as an explosive regular expression; for each of the explosive regular expressions, extracting, with the computing device, a corresponding signature fingerprint from the explosive regular expressions, wherein the signature fingerprint comprises a segment of the corresponding one of the explosive regular expressions that uniquely identifies the corresponding one of the explosive regular expressions; generating, with the computing device, a non-explosive Deterministic Finite Automata (DFA) from each of the plurality of regular expressions classified as non-explosive; generating, with the computing device, an individual DFA from each of the plurality of regular expressions classified as explosive; generating, with the computing device, a fingerprint DFA (f-DFA) from each of the signature fingerprints extracted from a corresponding one of the plurality of regular expressions classified as explosive; and merging, with the computing device, the non-explosive DFA and the f-DFA to generate a group DFA, wherein the group DFA comprises at least one node that identifies the individual DFAs and thereby links the group DFA to the individual DFA. - View Dependent Claims (21, 22, 23, 24, 25)
-
-
26. A computing device comprising:
-
a control unit that stores data defining a plurality of regular expressions, wherein the control unit includes; a classification module that determines whether each of the plurality of regular expressions causes state explosion and classifies each of the plurality of regular expressions as non-explosive or explosive depending on the determination, wherein one of the plurality of regular expression is classified as non-explosive and another one of the plurality the plurality of regular expressions is classified as an explosive regular expression; a fingerprint extraction module that, for each of the explosive regular expressions, extracts a corresponding signature fingerprint from the explosive regular expressions, wherein the signature fingerprint comprises a segment of the corresponding one of the explosive regular expressions that uniquely identifies the corresponding one of the explosive regular expressions; a Deterministic Finite Automata (DFA) construction module that generates a non-explosive DFA from each of the plurality of regular expressions classified as non-explosive, an individual DFA from each of the plurality of regular expressions classified as explosive, and a fingerprint DFA (f-DFA) from each of the signature fingerprints extracted from a corresponding one of the plurality of regular expressions classified as explosive; and a DFA merge module that merges the non-explosive DFA and the f-DFA to generate a group DFA, wherein the group DFA comprises at least one node that identifies the individual DFAs and thereby links the group DFA to the individual DFA. - View Dependent Claims (27, 28, 29, 30, 31)
-
-
32. A computer-readable medium comprising instructions for causing a programmable processor to:
-
store, with a computing device, data defining a plurality of regular expressions; determine whether each of the plurality of regular expressions causes state explosion; classify, with the computing device, each of the plurality of regular expressions as non-explosive or explosive depending on the determination, wherein one of the plurality of regular expression is classified as non-explosive and another one of the plurality the plurality of regular expressions is classified as an explosive regular expression; for each of the explosive regular expressions, extract, with the computing device, a corresponding signature fingerprint from the explosive regular expressions, wherein the signature fingerprint comprises a segment of the corresponding one of the explosive regular expressions that uniquely identifies the corresponding one of the explosive regular expressions; generate, with the computing device, a non-explosive Deterministic Finite Automata (DFA) from each of the plurality of regular expressions classified as non-explosive; generate, with the computing device, an individual DFA from each of the plurality of regular expressions classified as explosive; generate, with the computing device, a fingerprint DFA (f-DFA) from each of the signature fingerprints extracted from a corresponding one of the plurality of regular expressions classified as explosive; and merge, with the computing device, the non-explosive DFA and the f-DFA to generate a group DFA, wherein the group DFA comprises at least one node that identifies the individual DFAs and thereby links the group DFA to the individual DFA.
-
-
33. A method comprising:
-
storing, with a network device, first data that defines a group deterministic finite automata (DFA), wherein the group DFA is formed by a merger of;
(i) an individual non-explosive DFA generated from a corresponding non-explosive regular expression, and (ii) a fingerprint DFA (f-DFA) generated from a corresponding signature fingerprint, wherein the non-explosive regular expression comprises a regular expression determined not to cause state explosion during the merge to form the group DFA, wherein the signature fingerprint comprises a segment of an explosive regular expression that uniquely identifies the explosive regular expression, and wherein the explosive regular expression comprises a regular expression determined to cause state explosion during the merge;storing, with the network device, second data that defines, for the explosive regular expression, an individual DFA separate from the group DFA, wherein the signature fingerprint uniquely identifies the explosive regular expression from which the individual DFA is generated; receiving, with a network device, a packet; traversing, with the network device prior to traversing the individual DFA, the group DFA in order to determine whether the packet includes the segment of the explosive regular expression defined by the signature fingerprint; and traversing, with the network device, the individual DFA associated with the signature fingerprint based on the determination that the packet includes the segment of the explosive regular expression to identify a pattern identified by the explosive regular expression.
-
Specification