Improving deep packet inspection through extended automata

Speaker: Prof. Cristian Estan, University of Wisconsin Host: Prof. Ramesh Govindan Abstract:
Deep packet inspection is playing an increasingly important role in novel network services. Regular expressions are the language of choice for writing signatures used in deep packet inspection, but standard signature matching solutions are not suitable for high-speed environments. Deterministic finite automata (DFAs) are fast but combining the DFAs for multiple signatures often leads to state space explosion. Non-deterministic finite automata (NFAs) are small but matching can be slow for large signature sets. This talk presents a new solution that simultaneously addresses these problems. Extended finite automata (XFAs) augment deterministic finite automata (DFAs) with finite auxiliary variables and simple instructions that manipulate them. The introduction of auxiliary variables allows us to eliminate state space explosion. In experiments with signature sets used for intrusion prevention by Snort and Cisco Systems, XFAs simultaneously reduce memory and run time by more than an order of magnitude when compared to earlier solutions. Biography:
Cristian Estan has been an assistant professor in the Computer Sciences Department at University of Wisconsin-Madison since Fall 2004. His Ph.D. is from University of California, San Diego (adviser George Varghese). His research focuses on network security, network traffic measurement, and network traffic analysis. It has resulted in publications in top conferences in networking, security, systems, and databases: SIGCOMM, IEEE Security and Privacy (Oakland), OSDI, SIGMETRICS, ICDE, IMC, etc. His work is supported by multiple grants from NSF including a CAREER grant and gifts from Cisco Systems.

Location: Charles Lee Powell Hall (PHE) - 223

Audiences: Everyone Is Invited

Contact: CS Colloquia