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

  • 劉 思安

Student thesis: Master's Thesis

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 Award2015 Aug 25
Original languageEnglish
SupervisorYeim-Kuan Chang (Supervisor)

Cite this

Regular Expression Matching Acceleration Algorithm Using Multi-Byte DFA on GPU
思安, 劉. (Author). 2015 Aug 25

Student thesis: Master's Thesis