A High-Speed Grammar Aware Application Protocol Parsing Algorithm for Networking and Security Devices




There is an increasing desire to create content aware networks that can improve data delivery by classifying and controlling messages based on content, application, and individual subscribers. There is also a need to improve network security via content-based monitoring and filtering. Building content aware networks requires both advanced application policies specified over application protocol fields, not just host IP addresses and port numbers, and high performance network devices that can parse inter-application message contents to extract the appropriate fields in real-time.


Description of Technology


MSU’s technology provides a systematic online application protocol field extraction framework that can serve as the core of next generation networking devices such as routers, firewalls, and Intrusion Prevention Systems (IPSes).


The technology uses a new grammar model and corresponding automata. These models add counters, counter-update functions, and counter predicates that guard transitions to regular grammars and finite state automata. These additions provide the ability to parse and extract fields from complex application protocols with context-sensitive features such as variable length fields. These additions also facilitate fast and stack-less approximate parsing of the recursive structures, such as balanced parentheses in application protocols, which typically require stacks for precise parsing. With these new grammar models, this technology facilitates network administrators deploying content-based network policies by writing a simple extraction specification that is automatically compiled into a machine readable extractor.


Key Benefits

  • Provides automated framework: Utilizes, as an input, an extraction specification and automatically generates an extractor. Hand-coded extractors often contain errors and are typically hard to update when the required protocol fields change. With an automated framework, network administrators can deploy content-based network policies by writing a simple extraction specification.
  • Powerful and flexible: Parses application protocols with field length descriptors, which are fields that specify the length of another field.
  • Generates fast and compact extractors: High-performance, memory-efficient extractors are generated from complex, multifield policies using selective parsing, which parses only relevant protocol fields that are needed for extracting the specified fields, instead of full parsing and approximate protocol parsing, where the actual parser does not impact the input exactly as specified by the grammar.




The invention has applications for networking companies that provide routers and firewalls, as well as software companies providing Unified Threat Management (UTM).


Patent Status


Patented US 8,897,151




Xiang-Yang Liu, Chad Meiners, Eric Torng


Tech ID




Patent Information:

For Information, Contact:

Raymond Devito
Technology Manager
Michigan State University