NeTS: Small: A Language-Based Approach to Deep Packet Inspection: from Theory to Practice

深度数据包检测是几个已建立和新兴网络应用的核心，如网络入侵检测和内容感知路由。由于正则表达式的表达能力，近年来，正则表达式已被工业界和学术界用于这些应用程序的模式集所采用。现有的高性能正则表达式匹配引擎是基于有限自动机，并使用基于逻辑或存储器的设计实现。前者允许单包流的峰值性能与相对简单的逻辑，但不能扩展到大量的流;后者提供的可扩展性，在算法和设计复杂性的成本流的数量。尽管在该领域已经有了大量的工作，但在存在复杂正则表达式（包括重复的通配符和大型字符集）的情况下，提供最坏情况的保证仍然具有挑战性。此外，现有的解决方案假设分组在数据解压缩之后按顺序被检查。该项目将开发用于线速深度包检测的语言抽象、数据结构和算法。特别是，该项目将考虑基于正则表达式的深度数据包检测中的开放问题，即：（i）处理包含通配符和大字符集重复的复杂模式，以及（ii）检查无序数据包和压缩流量。将引入一种基于语言的深度数据包检测方法，以处理正则表达式？复杂性这个项目将整合自动机理论的概念，数据结构和算法设计的实践，网络应用程序的需求分析，以及系统架构的考虑。PI之前在高速正则表达式匹配方面的工作已经吸引了几家公司的注意。 主要研究者将利用这些联系来促进拟议研究的转移。PI在密苏里州大学（MU）的本科生和研究生电气和计算机工程课程中增加了两门计算机体系结构课程;她将介绍一门新的网络系统课程，该课程将涵盖本研究产生的知识。PI将利用MU本科生研究计划，让本科生参与拟议的工作，这将允许学生在三个领域的交叉点工作：算法和数据结构设计，系统架构和网络应用。这项研究的结果将通过出版物和演示文稿传播，并通过发布开源软件模块的PI？实验室网站。

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.