Improving deep packet inspection through extended automata

Date: 
Thursday, November 13, 2008 - 3:05pm

UCSB COMPUTER SCIENCE DEPARTMENT PRESENTS:
MONDAY, NOVEMBER 24, 2008
3:30 – 4:30
Computer Science Conference Room, Harold Frank Hall Rm. 1132

HOST: KEVIN ALMEROTH

SPEAKER: CRISTIAN ESTAN
Faculty, University of Wisconsin-Madison Computer Science

Title: Improving deep packet inspection through extended automata

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.

Bio:

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, INFOCOM, ICDE,
IMC, etc. His work is supported by multiple grants from NSF including a
CAREER grant and gifts from Cisco Systems.