Deep packet inspection is at the core of several established and emerging networking applications, such as network intrusion detection and content-aware routing. Due to their expressive power, in recent years regular expressions have been adopted in pattern-sets used for these applications in both industry and academia. Existing high-performance regular expression matching engines are based on finite automata, and are implemented using either logic- or memory-based designs. The former allow peak performance on single packet flows with relatively simple logic, but are not scalable to large numbers of flows; the latter offer scalability in the number of flows at the cost of algorithmic and design complexity. Despite the rich body of work in the area, providing worst-case guarantees is still challenging in the presence of complex regular expressions that include repetitions of wildcards and large character sets. Moreover, existing solutions assume that packets are inspected in-order and after data decompression.
This project will develop a language abstraction, data structures, and algorithms for line rate deep packet inspection. In particular, the project will consider open problems in regular expression-based deep packet inspection, namely: (i) handling of complex patterns containing repetitions of wildcards and large character sets, and (ii) inspection of out-of-order packets and compressed traffic. A language-based approach to deep packet inspection will be introduced in order to handle the regular expressions? complexity. This project will integrate concepts from automata theory, practices in data structure and algorithm design, analysis of the requirements of networking applications, and system architecture considerations.
The previous work performed by the PI on high speed regular expression matching has attracted the attention of several companies. The PI will leverage these contacts to facilitate the transfer of the proposed research. The PI has added two computer architecture courses to the undergraduate and graduate Electrical and Computer Engineering curriculum at University of Missouri (MU); she will introduce a new networking systems course, which will cover the knowledge generated by this research. The PI will leverage the MU Undergraduate Research Program to involve undergraduate students in the proposed work, which will allow students to work at the intersection of three domains: algorithm and data structure design, system architecture and networking applications. The results of this research will be disseminated through publications and presentations, and by releasing open-source software modules on the PI?s Lab website.
