Computer Sciences Dept.

Cristian Estan

Thumbnail portrait
Multi-Byte Regular Expression Matching with Speculation
Daniel Luchaup, Randy Smith, Cristian Estan, Somesh Jha
RAID, September 2009

Intrusion prevention systems (IPSs) 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 match incoming packets one byte at a time, which limits their throughput and latency. In this paper, we present a method for matching which processes multiple bytes in parallel using speculation. We break the packet in several chunks, opportunistically match them in parallel and if the speculation is wrong, correct it later. We present algorithms that apply speculation in single-threaded software running on commodity processors as well algorithms for parallel hardware. Experimental results show that speculation leads to improvements in latency and throughput in both cases.

Computer Sciences | UW Home