DFA-Based Regular Expression Matching on Compressed Traffic

Citations Over Time

Abstract

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. Regular expressions are often used to represent such patterns. They are implemented using finite automata, which take the payload of a packet as an input string. However, existing approaches, both non-deterministic finite automata (NFA) and deterministic finite automata (DFA), do not deal with compressed traffic, which becomes more and more popular in HTTP applications. In this paper, we propose an efficient algorithm for regular expression matching to implement deep packet inspection on compressed traffic. Based on the observations of DFA, we design a scheme to skip most of the matching process in the compressed parts of traffic. To the best of our knowledge, this is the first effort to design an efficient regular expression matching on compressed traffic. We evaluate our algorithm using rule sets provided by Snort, a popular open-source intrusion detection system. The evaluation results show that our approach can reduce the number of state access in the DFA significantly.

Related Papers

• → A hybrid finite automaton for practical deep packet inspection(2007)226 cited
• → An improved DFA for fast regular expression matching(2008)145 cited
• → DFA-Based Regular Expression Matching on Compressed Traffic(2011)7 cited
• → SI-DFA: Sub-expression integrated Deterministic Finite Automata for Deep Packet Inspection(2013)6 cited
• Hardware Accelerators for Regular Expression Matching and Approximate String Matching(2009)