Variable-Stride Multi-Pattern Matching for Scalable Deep Packet Inspection

Accelerating multi-pattern matching is a critical issue in building high-performance deep packet inspection systems. Achieving high-throughputs while reducing both memory-usage and memory-bandwidth needs is inherently difficlut. In this paper, we propose a pattern matching algorithm that achieves high throughput while limiting both memory-usage and memory-bandwidth. We achieve this by moving away from byte-oriented processing of patterns to block-oriented scheme, using an idea from the Winnowing fingerprint algorithm [1]. Each block contains a variable number of characters that can be uniquely identified in both the pattern and in the input stream. Deterministic Finite Automatons (DFAs) built using this scheme are smaller and faster, enabling a variable stride in the stream processing that significantly increases the throughput. We present the algorithm, tradeoffs, optimizations, and implementation details. Performance evaluation is done using the Snort and ClamAV pattern sets. Using our algorithm, a single search engine can easily achieve 10-Gbps throughput at a small storage cost of less than three bytes per patterm character.