SYSTEMATIC FRAMEWORK FOR APPLICATION PROTOCOL FIELD EXTRACTION

• US 20120191833A1
• Filed: 07/15/2011
• Published: 07/26/2012
• Est. Priority Date: 07/16/2010
• Status: Active Grant

• Current Assignee: The Board of Trustees of Michigan State University (Michigan State University)
• Original Assignee: The Board of Trustees of Michigan State University (Michigan State University)
• Inventors: Liu, Xiang-Yang A., Torng, Eric, Meiners, Chad R.
• Granted Patent: US 8,897,151 B2
• Time in Patent Office: Days
• US Class Current: 709/223
• CPC Class Codes: G06N 20/00 Machine learning
• CPC Class Codes: G06N 5/025 Extracting rules from data
• CPC Class Codes: H04L 45/74591 using content-addressable memories [CAM]
• CPC Class Codes: H04L 63/1416 Event detection, e.g. attack signature detection

Abstract

A computer-implemented system is provided for implementing application protocol field extraction. The system includes: an automata generator configured to receive the extraction specification that specifies data elements to be extracted from data packets and generate a counting automaton; and a field extractor configured to receive a data flow and operates to extract data elements from the data packets in accordance with the counting automaton. The extraction specification is expressed in terms of a context-free grammar, where the grammar defines grammatical structures of data packets transmitted in accordance with an application protocol and includes counters used to chronicle parsing history of production rules comprising the grammar.

Claims

1. A computer-implemented system for application protocol field extraction, comprising:

an extraction specification that specifies data elements to be extracted from data packets and is expressed in terms of a context-free grammar, where the grammar defines grammatical structures of data packets transmitted in accordance with an application protocol and includes a counter used to chronicle parsing history of production rules comprising the grammar;

an automata generator configured to receive the extraction specification and generate a counting automaton; and

a field extractor configured to receive a data flow comprised of a plurality of data packets and operable to extract data elements from the data packets in accordance with the counting automaton.

2. The system of claim 1 wherein the context-free grammar is defined as a tuple having nonterminals, terminals, counters, production rules and a start nonterminal, where the counters are used to chronicle parsing history of the production rules.

3. The system of claim 2 wherein the production rules are in the form of <

predicate>

;

<

nonterminal>

→

<

body>

, such that the body is an ordered sequence of terminals and nonterminals and each predicate is expressed in terms of at least one counter.

4. The system of claim 2 wherein at least one of the production rules includes an action association with a terminal or nonterminal comprising the body of the production rule and the action is an expression for updating a value of a counter.

5. The system of claim 2 further comprises a grammar optimizer configured to receive the extraction specification which is incomplete in relation to the context-free grammar and operable to translate the extraction specification to a complete extraction specification using the context-free grammar.

6. The system of claim 5 wherein the grammar optimizer transforms the complete extraction specification to an equivalent regular grammar.

7. The system of claim 5 wherein the grammar optimizer transforms the complete extraction specification by identifying production rules from the extraction specification having nonterminals as either normal or non-normal;

replacing each of the production rules identified as normal with a regular rule using decomposition methods;

approximating a regular rule for each of the production rules identified as non-normal; and

concatenating the regular rules to form a regular grammar.

8. The system of claim 2 wherein the automata generator generates the counting automaton by setting an initial state of the counting automaton to the start nonterminal of the regular grammar;

setting states of the counting automaton equal to set of nonterminals in the regular grammar; and

, for each state, assigning transition functions by identifying a set of production rules having a head whose predicate is satisfied by each possible counter configuration and constructing a given state from regular expressions taken from the body of each rule in the identified set of productions rules, where the decision for the given state is corresponding action taken from the body of each rule in the identified set of production rules.

9. The method of claim 1 wherein the field extractor, for a given data packet, outputs location information for data elements contained in the data packet that satisfy one or more regular expression from the extraction specification.

10. A computer-implemented method for generating a counting automaton for use by a field extractor, comprising:

receiving an extraction specification that specifies data elements to be extracted from data packets and is expressed in terms of a context-free grammar, where the context-free grammar defines grammatical structures of data packets transmitted in accordance with an application protocol and includes counters that chronicle parsing history of production rules comprising the grammar;

transforming the extraction specification to an equivalent regular grammar; and

generating a counting automaton from the regular grammar.

11. The method of claim 10 further comprises receiving an extraction specification that specifies data elements to be extracted from data packets but is incomplete in relation to the context-free grammar and translating the incomplete extraction specification to a complete extraction specification using the context-free grammar.

12. The method of claim 10 wherein the context-free grammar is defined as a tuple having nonterminals, terminals, counters, production rules and a start nonterminal, where the counters are used to chronicle parsing history of the production rules.

13. The method of of claim 12 wherein the production rules are in the form of <

predicate>

;

<

nonterminal>

→

<

body>

, such that the body is an ordered sequence of terminals and nonterminals and each predicate is expressed in terms of at least one counter.

14. The system of claim 12 wherein at least one of the production rules includes an action association with a terminal or nonterminal comprising the body of the production rule and the action is an expression for updating a value of a counter.

15. The method of claim 12 wherein transforming the extraction specification further comprises

identifying production rules from the extraction specification having nonterminals as either normal or non-normal;

replacing each of the production rules identified as normal with a regular rule using decomposition methods;

approximating a regular rule for each of the production rules identified as non-normal; and

concatenating the regular rules to form a regular grammar.

16. The method of claim 15 wherein identifying production rules further comprises classifying a production rule as normal when the production rule is regular or, for production rules having a given nonterminal, X, as its head, the given nonterminal is a last symbol in a body of the production rule and, for every nonterminal, Y, that is reachable from the given nonterminal, Y is normal and the given nonterminal, X, is not reachable from Y.

17. The method of claim 16 wherein approximating a regular rule further comprises identifying start and end terminals for a given production rule, X, identified as non-normal and replacing the given production rule, X, with the following rules

(cnt=0):

X→

ε

(cnt≧

0);

X→

start(cnt;

=cnt+1) X

(cnt>

0);

X→

stop(cnt;

=cnt−

1) X

(cnt>

0);

X→

otherX

where X is the given production rule identified as non-normal, the cnt is a new counter, start is a start terminal, end is a end terminal and the remaining terminals are denoted by other.

18. The method of claim 15 further comprises eliminating any of the regular rules without terminal symbols from the regular grammar.

19. The method of claim 12 wherein generating a counting automaton further comprises setting an initial state of the counting automaton to the start nonterminal of the regular grammar;

setting states of the counting automaton equal to set of nonterminals in the regular grammar; and

, for each state, assigning transition functions by identifying a set of production rules having a head whose predicate is satisfied by each possible counter configuration and constructing a given state from regular expressions taken from the body of each rule in the identified set of productions rules, where the decision for the given state is corresponding action taken from the body of each rule in the identified set of production rules.