Signature Matching in Network Processing Using SIMD/GPU Architectures

Abstract

Deep packet inspection is becoming prevalent for modern network processing systems. They inspect packet payloads for a variety of reasons, including intrusion detection, traffic policing, and load balancing. The focus of this paper is deep packet inspection in intrusion detection/prevention systems (IPSes). The performance critical operation in these systems is signature matching: matching payloads against signatures of vulnerabilities. Increasing network speeds of today?s networks and the transition from simple string-based signatures to complex regular expressions has rapidly increased the performance requirement of signature matching.To meet these requirements, solutions range from hardware-centric ASIC/FPGA implementations to software implementations using high-performance microprocessors. In this paper, we propose a programmable SIMD architecture design for IPSes and develop a prototype implementation on an Nvidia G80 GPU. We first present a detailed architectural and microarchitectural analysis of signature matching. Our analysis shows that signature matching is well suited for SIMD processing because of regular control flow and parallelism available at the packet level. We examine the conventional approach of using deterministic finite automata (DFAs) and a new approach called extended finite automata (XFAs) which require far less memory than DFAs, but require scratch memory and small amounts of computation in each state. We then describe a SIMD design to implement DFAs and XFAs. Using a SIMD architecture provides flexibility, programmability, and design productivity which ASICs lack, while being area and power efficient which superscalar processors lack. Finally, we develop a prototype implementation using the G80 GPU as an example SIMD implementation. This system out-performs a Pentium4 by up to 9X and shows SIMD systems are a promising candidate for signature matching.