Multi-Byte Regular Expression Matching With Speculation

Date Added: Oct 2009
Format: PDF

Intrusion prevention systems determine whether incoming traffic matches a database of signatures, where each signature in the database represents an attack or a vulnerability. IPSs need to keep up with ever-increasing line speeds, which leads to the use of custom hardware. A major bottleneck that IPSs face is that they scan incoming packets one byte at a time, which limits their throughput and latency. In this paper, the authors present a method for scanning multiple bytes in parallel using speculation. They break the packet in several chunks, opportunistically scan them in parallel and if the speculation is wrong, correct it later. They present algorithms that apply speculation in single-threaded software running on commodity processors as well as algorithms for parallel hardware.