Fast and Memory Efficient NFA Pattern Matching using GPU
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. KeywordsDeep Packet Inspection; DFA; NFA; GPU; Pattern Matching; Regular expression.