Fast and Memory Efficient NFA Pattern Matching using GPU

Abstract

With the rapid development of networks a large number of malicious packets such as virus and malware are spreading in recent years Network intrusion detection system (NIDS) is mainly designed for monitoring whether there are some malicious packets over the Internet The technique of pattern matching plays an important role because we often use it to protect our systems With pre-defined virus signatures called patterns NIDS can find out whether these pre-defined patterns exist in the payload of packets Finite state automata (FSA) such as NFA and DFA are one of pattern matching techniques in NIDS Because processing a large amount of network packets only on a single thread cannot satisfy our high-speed demand we need hardware to accelerate the performance of pattern matching GPU can be used to effectively accelerate the performance of pattern matching because abundant parallel hardware threads are supported In this thesis we propose a new NFA-based method to store more complex regular expressions in limited memory of GPU effectively The proposed constrained NFA (CNFA) is constructed from the original NFA based on the method used in the subset construction algorithm that converts NFA to DFA Compared to original NFA and DFA the proposed CNFA imposes a constraint that each state can only have at most two transitions for each character namely self-loop and non-self-loop transitions Based on our experimental results the proposed CNFA can achieve the performance of about 100 Gbps at the best case on GPU Also the proposed CNFA only needs 18% of memory usage used in iNFAnt In addition the proposed CNFA can be used for more complex rule sets that is not possible to be implemented in iNFAnt

Date of Award	2014 Aug 15
Original language	English
Supervisor	Yeim-Kuan Chang (Supervisor)