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

NeTS：Small：基于语言的深度数据包检测方法：从理论到实践

• 批准号: 1319748
• 负责人: Michela Becchi
• 金额: $ 29.99万
• 依托单位: University of Missouri-Columbia
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2013
• 资助国家: 美国
• 起止时间: 2013-09-01 至 2017-03-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1319748&HistoricalAwards=false
• 关键词: NeTS; Small; Language; Based; Approach

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.

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