GPU Based High Speed Regular Expression Matching Engine

Regular expression (regex) matching is a crucial task in network security. Network applications implement deep packet inspection (DPI) systems by inspecting packet payloads at line rate over large sets of regexes. Because of the poor performance of general CPU in pipelining and parallelism, software-based implementation of a regex matching engine cannot meet the bandwidth requirement of ISP backbone. Hardware-based solutions may get a higher regex matching throughput, but it has high system design cost and low scalability.Nowadays, programmable Graphic Processor Unit (GPU) has evolved into a highly parallel, multithreaded, manycore processor with tremendous computational horsepower and very high memory bandwidth. Compared with hardware-based solutions, a GPU-based regex mathcing engine would get higher performance, better scalablity and lower cost. Aimed at the topic of the performance issues of regex matching engine in networking security applications, this thesis studies the design, implementation and optimization of GPU-based regex matching engine. The main work and contributions of this dissertation are shown as follows:1. Survey on high performance regex matching techniques. This thesis makes a study on the implememtation techniques of high speed regex matching in depth, including software-based solutions, specified hardware-based solutions and the GPU-based solutions. Additionaly, the advantages and disadvantages of all the solutions has been analyzed.2. Design and optimization of a novel GPU-base regex matching engine Gregex. In this thesis, we propose a novel GPU-based regex matching engine Gregex. Two optimization techniques, Coalesced global memory Access by Buffering packets to shared Memory (CAT) and Coalesced global memory Access by Transposing packets Buffer (CAB), are introduced to significantly improve the memory access performance of Gregex. Grgex also use Asynchronous data Transfer with Pinned memory (ATP) technique to improve the overall matching throughput.3. Implementation and evaluation of Gregex. We make a detailed discuss on the implementation of modules in Gregex, and use the regex set in Snort to evaluate Gregex. The experimental results showes that the matching performance of Gregex achieves a significant speedup compared with other implementations.