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

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

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.