Hardware-Accelerated Regular Expression Matching with Overlap Handling on IBM PowerEN Processor

Programmable hardware accelerators for regular expression (RegX) matching are evolving into increasingly complex stream processors, which involve multiple state machines that operate in parallel, and specialized post-processors that can process instructions dispatched by the state machines. To improve the speed and the storage-efficiency, complex RegXs are decomposed into simpler subexpressions, where each subexpression can fire one or more instructions. Although the impact of RegX decompositions on the storage efficiency is well-known, little has been done to address the correctness and completeness. We show that RegX decompositions can result in false positives if overlaps between subexpressions are not taken into account. We describe formal methods to recognize various types of subexpression overlaps that can arise in RegX decompositions. We also describe efficient post-processing techniques to eliminate the associated false positives. To enable efficient mapping of the decomposed RegXs to the post-processors, we propose integer programming based register allocation methods. Our methods pack narrow variables to reduce the register and instruction usage, and take advantage of multi-register reset instructions to reduce the number of instructions that must be executed in parallel. Experiments on six RegX sets obtained from network intrusion detection systems demonstrate orders of magnitude improvement in the storage efficiency over state-of-the-art.

A copy of this Research Report can be obtained by contacting: kat@zurich.ibm.com

A longer version of this report has been published in: 2013 IEEE 27th International Symposium on Parallel & Distributed Processing "IPDPS," (IEEE, May 2013) 1254-1265