Multipattern Matching Algorithm on GPGPU

Abstract: GPU Computing have attracted lots of attention due to their large amount of data processing. The algorithm proposed in this paper is use for exact pattern matching on GPU. Among some famous algorithms, the Aho-Corasick Algorithm match multiple pattern simultaneously. a Traditional Aho-Corasick Algorithm matches the pattern by traversing state machine, known as Deterministic finite automata(DFA).Signature matching is important Technique in virus/worm detection, but Aho-corasick algorithm was developed only for string and virus/worm signature could be in regular expression . In this research work new guidelines are proposed for an efficient GPU adaptation of Aho-corasick algorithm for regular expression matching. Also several technique is introduced to optimization on GPU, including reducing global memory access, storage format for output table. To evaluate performance proposed system will use SNORT virus database. Proposed algorithm Implemented on NVIDIA GTX-680 Graphics card using CUDA.

Keywords: Aho-Corasick, CUDA, Graphics processing Unit, Pattern Matching.