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的优先顺序并行搜索和三元压缩能力来减小自动机的大小并减少每个自动机查找所需的时间。