Piranha: Fast and Memory-Efficient Pattern Matching for Intrusion Detection

Network Intrusion Detection Systems (NIDS) provide an important security function to help defend against network attacks. As network speeds and detection workloads increase, it is important for NIDSes to be highly efficient. Most NIDSes need to check for thousands of known attack patterns in every packet, making pattern matching the most expensive part of signature-based NIDSes in terms of processing and memory resources. This paper describes Piranha, a new algorithm for pattern matching tailored specifically for intrusion detection. Piranha is based on the observation that if the rarest substring of a pattern does not appear, then the whole pattern will definitely not match. Our experimental results, based on traces that represent typical NIDS workloads, indicate that Piranha can enhance the performance of a NIDS by 11% to 28% in terms of processing time and by 18% to 73% in terms of memory usage compared to existing NIDS pattern matching algorithms.