RICS-DFA: Reduced Input Character Set DFA for Memory-Efficient Regular Expression Matching

摘要: Regular expression matching as a core component of deep packet inspection (DPI) is widely used in various kinds modern network intrusion detection system (NIDS), traffic classification and monitoring system, etc. In these systems, regular expressions are typically converted to deterministic finite automaton (DFA), the DFA scan check each byte incoming packet’s payload against rule sets judge whether current matched by any sets. If matched, it means contains specific attacks, viruses, so on. However, generally consumes large amount memory. Many recent improvement work mainly focus on how reduce memory requirement. Like previous work, this paper we propose compact, time-efficient novel structure significantly decrease DFA’s space, new called Reduced Input Character Set (RICS-DFA). A character escaping replacing scheme first introduced set size then space requirement with series optimization techniques based RICS-DFA. RICS-DFA constructed transition rewriting. Experimental results real-life rule-sets reveal that compared original DFA, reduces consumption 68 %–92 % while sacrificing trivial speed.