Home // INNOV 2016, The Fifth International Conference on Communications, Computation, Networks and Technologies // View article

Fast and Memory Efficient NFA Pattern Matching using GPU

Authors:
Yeim-Kuan Chang
Yu-Hao Tseng

Keywords: Deep Packet Inspection; DFA; NFA; GPU; Pattern Matching; Regular expression

Abstract:
Network intrusion detection system (NIDS) is mainly designed to monitor the malicious packets spreading on the Internet. With pre-defined virus signatures called patterns, NIDS can find out whether these pre-defined patterns exist in the packet’s payload. GPU can be useful to effectively accelerate pattern matching process due to abundant parallel hardware threads. In this paper, we propose a constrained NFA (CNFA) scheme to store complex regular expressions in limited memory of GPU effectively. CNFA is constructed from the original NFA based on the subset construction algorithm that converts NFA to DFA. Compared to original NFA and DFA, CNFA imposes a constraint that each state can only have at most two transitions (self-loop and non-self-loop) for each character. Based on our experimental results, CNFA can achieve the performance of about 100 Gbps for one of the tested rule sets on GPU. Also, CNFA only needs 18% of memory needed in iNFAnt. In addition, CNFA can be used for more complex rule sets that is not possible to be implemented in iNFAnt.

Pages: 7 to 12

Copyright: Copyright (c) IARIA, 2016

Publication date: August 21, 2016

Published in: conference

ISSN: 2326-9286

ISBN: 978-1-61208-503-6

Location: Rome, Italy

Dates: from August 21, 2016 to August 25, 2016