Work-efficient Parallel Rabin-Karp for GPU Accelerated NIDS

Abstract

The rise in internet data usage has increased the demand for efficient Network Intrusion Detection Systems (NIDS) that can scale with growing bandwidths to maintain security. Packet inspection, relying heavily on pattern matching, is the most time-consuming part of NIDS. While parallel versions of the Aho-Corasick (AC) algorithm, including its failure-less variant, offer maximum parallelism, they suffer from inefficiencies and large transition tables. Addressing these challenges, we propose a parallel work-efficient variation of the Rabin-Karp algorithm. Our approach supports multiple patterns of variable lengths and achieves linear speedup with increasing pattern lengths, overcoming the scalability and performance bottlenecks of existing systems. This research aims to enhance NIDS frameworks by demonstrating the benefits of our parallel Rabin-Karp algorithm in achieving resilient and efficient performance.