Exploratory Studies of New Automata Models and Algorithms for TCAM-based Regular Expression Matching

基于TCAM正则表达式匹配的新自动机模型和算法的探索性研究

• 批准号: 1347953
• 负责人: Eric Torng
• 金额: $ 5万
• 依托单位: Michigan State University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2013
• 资助国家: 美国
• 起止时间: 2013-09-01 至 2015-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1347953&HistoricalAwards=false
• 关键词: Exploratory; Studies; New; Automata; Models

Regular expression matching is the core operation in a wide range of networking and security services (such as malware filtering) on most networking middleboxes and security devices. As each packet is processed by such a device, the packet payload is examined to determine if it matches any of the specified regular expressions, each of which might correspond to a specific security threat. In most regular expression matching solutions, the regular expressions are converted into a finite state automata model which is then used to perform the search. Because each packet must be searched, high speed and low memory regular expression matching solutions are required. Unfortunately, the standard automata models, deterministic finite state automata (DFA) and nondeterministic finite state automata (NFA), are insufficient because neither can achieve both low memory and high speed. This project explores the feasibility of new high speed low memory regular expression matching solutions based on ternary content addressable memory (TCAM). If successful, the result will be a fundamentally new regular expression matching solution that will help make the Internet both faster and more secure.This project will develop new regular expression matching solutions by developing new finite state automata models such as the overlay deterministic finite state automata (ODFA) that account for memory inefficiencies in DFA. Along with developing new automata models, the project will develop new scalable and automated algorithms for efficiently constructing the automata from the input regular expressions as well as efficient algorithms for encoding these automata in TCAM. A key design constraint for the automata models and algorithms will be leveraging the prioritized parallel search and ternary compression capabilities of TCAM to reduce automata size and decrease the time required for each automata lookup.

正则表达式匹配是大多数网络中间箱和安全设备上的各种网络和安全服务（例如恶意软件过滤）中的核心操作。由于每个数据包都是由此设备处理的，因此检查了数据包有效负载，以确定它是否匹配任何指定的正则表达式，每个表达式可能与特定的安全威胁相对应。在大多数正则表达式匹配解决方案中，正则表达式转换为有限状态自动机模型，然后将其用于执行搜索。因为必须搜索每个数据包，因此需要高速和低内存正则表达匹配解决方案。不幸的是，标准自动机型，确定性有限状态自动机（DFA）和非确定有限状态自动机（NFA）不足，因为两者都无法达到低内存和高速。该项目探讨了基于三元内容可寻址内存（TCAM）的新高速低内存正则表达解决方案的可行性。如果成功的话，结果将是一种从根本上进行新的正则表达匹配解决方案，它将有助于使互联网更快且更安全。本项目将通过开发新的有限状态自动机模型（例如覆盖层确定性有限状态自动机（ODFA））来开发新的正则表达匹配解决方案，以说明DFA中效率低下的内存。除了开发新的自动机模型外，该项目还将开发新的可扩展和自动化算法，以有效地从输入正则表达式和有效算法构建自动机以及在TCAM中编码这些自动机的有效算法。自动机模型和算法的关键设计约束将利用TCAM的优先并行搜索和三元压缩功能来降低自动机大小并减少每个自动机查找所需的时间。