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

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