Kangaroo: Speculative Multi-Pattern Matching for Scalable Deep Packet Inspection

Download Now Date Added: Aug 2010
Format: PDF

Multi-pattern matching is a key technique for network security applications like Network Intrusion Detection Systems (NIDSes) and anti-virus scanners, where every packet is inspected against thousands of patterns in real-time. Existing DFA-based research have claimed to achieve high throughput at the expense of extremely high memory cost, so fail to be used in scenarios like high-speed routers where only limited on-chip resources are available. In this paper, the authors present Kangaroo, a scheme that scans multiple bytes in parallel using speculation with a reduced memory cost.