A Graphics Processing Unit Based Multi-string Matching Algorithm for Anti-virus Systems.

Abstract: String matching is a fundamental problem in computer science. Multi-string matching plays an important role in pattern recognition, search engine, virus prevention, intrusion detection and others. Aho-Corasick (AC) algorithm is a widely used multi-string matching algorithm. In this paper, we present a space compacting method for AC automata based on node grouping and implement AC algorithm on GPU platform using CUDA (Computer Unified Device Architecture). We accelerate the anti-virus systems by our approach. We conduct several experiments, and our algorithm has at least 10 times of speedup of the algorithm on CPUs. [Copyright &y& Elsevier]