Regular Expression (RegEx) matching is the industry standard for Deep Packet Inspection (DPI) because RegExes are significantly more expressive than strings. To achieve high matching speed, we need to convert the RegExes to Deterministic Finite State Automata (DFA). However, DFA has the state explosion problem, that is, the number of DFA states and transitions can be exponential with the number of RegExes. Much work has addressed the DFA state explosion problem; however, none has met all the requirements of fast and automated construction, small memory image, and high matching speed. In this paper, we propose a decompositional approach, with fast and automated construction, small memory image, and high matching speed, to DFA state explosion. The first key idea is to decompose a complex RegEx that cause exponential state increases into a set of simpler RegExes that do not cause exponential state increases, where any character string that matches the complex RegEx also matches all the RegExes in the set of simpler RegExes; that is, the set of strings that match the complex RegEx is a subset of strings that match the set of simpler RegExes. The second key idea is to use a stateful post-processing engine to filter the matches that are actually the matches of the complex RegEx. Given an input string for matching, instead of using the large DFA constructed from the original complex RegEx to perform the matching, we first use the small DFA constructed from the set of simpler RegExes to perform the matching, and then, if the small DFA reports a match, we use the post-processing engine to determine whether it is a true match to the original complex RegEx. Because the pre-processing is simple, automaton construction can be automated and fast, and because most on-line processing is done by a DFA, its matching speed is close to that of a DFA alone. Our experimental results show that our decompositional approach achieves orders of magnitude faster DFA construction (in terms of seconds instead of minutes), 30 times smaller memory image, and 43% faster matching speeds, than state-of-the-art software based RegEx matching algorithms.

Regular expressions are a very common tool for network security applications because they can match precisely and maintain high matching speed even for many simultaneous patterns. Their core feature is efficient representation as an automaton, where much of the interaction between patterns can be pre-computed and aggregated. Many algorithms have been devised to try and improve this pre-computation to not take exponential space while keeping high performance, but none has met all the requirements of fast, automated construction, small memory image, and high matching speed. We present Match Filtering, a technique for de-composing regular expressions into segments that can be matched independently, while a stateful post-processing engine filters these matches to eliminate those that do not correspond to matches of the original regular expression. Using standard CPU instructions, the post-processing engine can more efficiently represent constructs that would require a multiplicative increase in automaton states. Because the pre-processing is simple, automaton construction can be automated and fast, and because most on-line processing is done by a DFA, its matching speed is close to that of a DFA alone. We demonstrate experimentally 30× smaller, fast (seconds, not minutes) automaton construction and 43% faster matching speeds than state-of-the-art software algorithms.

In this paper, we propose FlowSifter, a framework for automated online application protocol field extraction. FlowSifter is based on a new grammar model called Counting Regular Grammars (CRG) and a corresponding automata model called Counting Automata (CA). The CRG and CA models add counters with update functions and transition guards to regular grammars and finite state automata. These additions give CRGs and CAs the ability to parse and extract fields from context sensitive application protocols. These additions also facilitate fast and stackless approximate parsing of recursive structures. These new grammar models enable FlowSifter to generate optimized Layer 7 field extractors from simple extraction specifications. We compare FlowSifter against both BinPAC and UltraPAC, which represent the state-of-the-art field extractors. Our experiments show that when compared to BinPAC parsers, FlowSifter runs more than 21 times faster and uses 49 times less memory. When compared to UltraPAC parsers, FlowSifter extractors run 12 times faster and use 24 times less memory.

Regular expression (RE) matching is a core component of deep packet inspection in modern networking and security devices. In this paper, we propose the first hardware-based RE matching approach that uses ternary content addressable memory (TCAM), which is available as off-the-shelf chips and has been widely deployed in modern networking devices for tasks such as packet classification. We propose three novel techniques to reduce TCAM space and improve RE matching speed: transition sharing, table consolidation, and variable striding. We tested our techniques on eight real-world RE sets, and our results show that small TCAMs can be used to store large deterministic finite automata (DFAs) and achieve potentially high RE matching throughput. For space, we can store each of the corresponding eight DFAs with 25 000 states in a 0.59-Mb TCAM chip. Using a different TCAM encoding scheme that facilitates processing multiple characters per transition, we can achieve potential RE matching throughput of 10-19 Gb/s for each of the eight DFAs using only a single 2.36-Mb TCAM chip.

Packet classification is the key mechanism for enabling many networking and security services. Ternary Content Addressable Memory (TCAM) has been the industrial standard for implementing high-speed packet classification because of its constant classification time. However, TCAM chips have small capacity, high power consumption, high heat generation, and large area size. This paper focuses on the TCAM-based Classifier Compression problem: given a classifier C, we want to construct the smallest possible list of TCAM entries T that implement C. In this paper, we propose the Ternary Unification Framework (TUF) for this compression problem and three concrete compression algorithms within this framework. The framework allows us to find more optimization opportunities and design new TCAM-based classifier compression algorithms. Our experimental results show that the TUF can speed up the prior algorithm TCAM Razor by twenty times or more and leads to new algorithms that improve compression performance over prior algorithms by an average of 13.7% on our largest real life classifiers.

Regular Expression (RegEx) matching is the core operation of various network security devices such as IPSes. Despite much effort, it has remained an unsolved problem to achieve both high speed and low memory requirements.XFA, the state-of-the-art software RegEx matching solution, has two fundamental limitations: (1) XFA construction is hard to automate as it requires manual annotation by human experts, and (2) XFA is hard to implement in ASIC as the program executed upon reaching a state requires much of the complexity of a general purpose CPU. In this paper, we propose HASIC, a History-based Finite Automaton (HFA [11]) based RegEx matching scheme. HASIC can exponentially reduce state explosion by testing, setting, and clearing an auxiliary vector of history bits. Compared with XFA, HASIC advances the state of the art because it can be fully automated and it is ASIC friendly. HASIC only uses three simple bit operations and they are easy to implement in ASIC. We conducted experiments using real-world RegEx sets and various traffic traces. Experimental results show that for packet processing speed, software HFA runs an average of 3.34 times faster than XFA, for automata construction speed HFA is orders of magnitude faster than DFA, and for memory image size HFA is an average of 20 times smaller than DFA.

In this paper, we introduce FlowSifter, a systematic framework for online application protocol field extraction. FlowSifter introduces a new grammar model Counting Regular Grammars (CRG) and a corresponding automata model Counting Automata (CA). The CRG and CA models add counters with update functions and transition guards to regular grammars and finite state automata. These additions give CRGs and CAs the ability to parse and extract fields from context sensitive application protocols. These additions also facilitate fast and stackless approximate parsing of recursive structures. These new grammar models enable FlowSifter to generate optimized Layer 7 field extractors from simple extraction specifications. In our experiments, we compare FlowSifter against both BinPAC and UltraPAC, which are the freely available state of the art field extractors. Our experiments show that when compared to UltraPAC parsers, FlowSifter extractors run 84% faster and use 12% of the memory.

Hash functions are vital in networking. Hash-based algorithms are increasingly deployed in mission-critical, high speed network devices. These devices will need small, quick, hardware hash functions to keep up with Internet growth. There are many hardware hash functions used in this situation, foremost among them CRC-32. We develop parametrized methods for evaluating hash function output quality so as to better compare similar hash functions. We use these methods to explore the quality of candidate hash functions, including CRC-32, H3(with fixed seed), MD5 and others. We also propose optimized building blocks for hardware hash functions based on SP-networks. Given a size budget of 4K gates and only 1 cycle to compute the result, we demonstrate a 128 bit input, 64 bit output hash function built using this framework that ranks highly in our tests.