Regular Expression Matching Acceleration Algorithm Using Multi-Byte DFA on GPU

Abstract

Regular expression matching plays an important role in Network Intrusion Detection System (NIDS) As the Internet traffic grows rapidly regular expression have been widely used in NIDS due to its flexibility and conciseness Recently graphics processing unit (GPU) is often used to accelerate regular expression matching The classical matching approach for regular expression matching uses deterministic finite automata (DFA) However DFA suffers from the problem of state explosion because it needs a lot of memory space In this thesis we propose a GPU-based approach called Multi-Byte DFA (MB-DFA) which can process multiple characters per cycle in order to accelerate regular expression matching and solve the problem of state explosion In addition we also propose a compression scheme based on default transition Our experimental results show that the proposed MB-DFA can achieve significant reductions in memory usage and the best performance of throughput is 83 Gbps on GPU

Date of Award	2015 Aug 25
Original language	English
Supervisor	Yeim-Kuan Chang (Supervisor)