US 8,897,151 B2Granted

Systematic framework for application protocol field extraction

AssigneeBoard of Trustees of Michigan State University

InventorsXiang-Yang A. Liu, Chad R. Meiners, Eric Torng

Life of this patent

Estimating the term…

Loading patent…

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.

Claims16

Dependent claims

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 is defined as a tuple having nonterminals, terminals, counters, production rules and a start nonterminal, such that the counters are variables with an integer value used to chronicle parsing history of the production rules, and at least one of the production rules includes an action association with a terminal or nonterminal comprising body of the production rule and the action is an expression for updating a value of a counter defined by 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 traversing through a network and extract data elements from the data packets in accordance with the counting automaton, where the field extractor is implemented by an integrated circuit.

1 more element

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 is defined as a tuple having nonterminals, terminals, counters, production rules and a start nonterminal, such that the counters are variable with an integer value used to chronicle parsing history of the production rules and at least one of the production rules includes an action association with a terminal or nonterminal comprising body of the production rule and the action is an expression for updating a value of a counter defined by the grammar;
transforming the extraction specification to an equivalent regular grammar;
and
generating a counting automaton from the regular grammar.

1 more element

Dependencies are inferred from the claim text.

Facts

Application: 13/183,571Filed 15 Jul 2011 · us provisional application
Priority: 16 Jul 2010
Published: US 2012/0191833 A126 Jul 2012
Granted: 25 Nov 2014
Term ends: Not estimatedThe source records don’t support an estimate.

Classification6 codes

H04L 63/1416
By monitoring network traffic: event detection, e.g. attack signature detection
G06N 5/025
Knowledge engineering; Knowledge acquisition: extracting rules from data
G06N 20/00
Machine learning
H04L 45/74591
Address table lookup; Address filtering: using content-addressable memories [CAM]