NFA-Based Pattern Matching for Deep Packet Inspection

Many network security applications in today´s networks are based on deep packet inspection, checking not only the header portion but also the payload portion of a packet. For example, traffic monitoring, layer-7 filtering, and network intrusion detection all require an accurate analysis of packet content in search for predefined patterns to identify specific classes of applications, viruses, attack signatures, etc. Pattern matching is a major task in deep packet inspection. The two most common implementations of Pattern matching are based on Non-deterministic Finite Automata (NFAs) and Deterministic Finite Automata (DFAs), which take the payload of a packet as an input string. In this paper, we propose an efficient NFA-based pattern matching in Binary Content Addressable Memory(BCAM), which uses data search words consisting of 1s and 0s. Our approach can process multiple characters at a time using limited BCAM entries, which makes our approach scalable well. We evaluate our algorithm using patterns provided by Snort, a popular open-source intrusion detection system. The simulation results show that our approach outperforms existing CAM-based and software-based approaches.