RICS-DFA: a space and time-efficient signature matching algorithm with Reduced Input Character Set

摘要: Summary Regular expression matching as a core component of deep packet inspection is widely used in various kinds modern network intrusion detection system, traffic classification monitoring and so on. In these systems, regular expressions are typically converted to deterministic finite automaton (DFA), which takes O(1) scan each input character. However, DFA generally consumes large amount memory. This paper proposes novel, space-efficient time-efficient presentation, called reduced character set (RICS-DFA). A escaping replacing scheme first introduced decrease the size DFA's then reduce space requirement with series optimization techniques. Based on transition rewriting, RICS-DFA constructing algorithm time complexity O(n) presented this paper. For real rule-sets, reduces memory consumption by 68–92%, compared original DFA. Finally, designs scalable engine field-programmable gate array platform state matrix mapped on-chip memories. The throughput executing for rule-sets can achieve 7–50.5 Gbps. Copyright © 2016 John Wiley & Sons, Ltd.