Abstract
Abstract In terms of flexibility and scalability, regular expression has been widely adopted in Network Intrusion Detection Systems (NIDS) to represent network attack patterns. To accommodate the increasing number of attack patterns, several recent researches adopt Graphic Processor Units (GPUs) to accelerate the matching process. However, all of them cannot deal with complex regular expressions which have become an important representation in virus database. In this paper, we propose a novel parallel algorithm to accelerate regular expression matching performed on GPUs. We also propose an innovative state machine for complex regular expression matching, the state machine of which is more suitable for performing in the parallel algorithm. The experimental results show that the novel approach not only achieves a significant speedup on performing complex regular expression matching but also are faster on the simple regular expression matching than other GPU approaches.