| Modern network security applications, such as network-based intrusion detection systems (NIDS) and firewalls, routinely employ deep packet inspection to identify malicious traffic. In deep packet inspection, the contents of network packets are matched against patterns of malicious traffic to identify attack-carrying packets. The pattern matching algorithms employed for deep packet inspection must satisfy two requirements. First, the algorithms must be fast. Network security applications are often implemented as middle-boxes that reside on high-speed Gbps links, and the algorithms are expected to perform at such speeds. Second, the algorithms must be space-efficient. The middle-boxes that perform pattern matching are often implemented as hardware components, they employ fast but expensive SRAM technology to ensure good performance.;Unfortunately, existing pattern matching algorithms suffer from a fundamental time-space tradeoff. The large majority of patterns are regular expressions, and there are three prior approaches for matching such patterns: deterministic finite automaton (DFAs), non-deterministic finite automaton (NFAs), and recursive backtracking-based approaches. DFAs are fast to operate, but are space-inefficient. NFAs are space efficient, but are slow to operate. Recursive backtracking is fast for benign packets but is vulnerable to attack-carrying packets that can induce algorithmic complexity attacks.;This dissertation proposes novel algorithms for time- and space-efficient pattern matching that also resist known algorithmic complexity attacks. It presents three contributions. First, it introduces NFA-OBDDs, a new data structure that allows time-and space-efficient matching of regular expressions. Second, it presents an extension to NFA-OBDDs that allows them to model submatch extraction, an important feature in real-world patterns used by network security applications. Finally, it presents a technique to efficiently match a non-regular pattern language: regular expressions extended with back-references. This disseration presents experimental results demonstrating that the new algorithms can beat the performance of existing, widely-deployed algorithms (such as Google's RE2 and PCRE) by several orders of magnitude. |
