RICS‐DFA: a space and time‐efficient signature matching algorithm with Reduced Input Character Set
Authors:
- 2 December 2016
- journal article
- research article
- Published by Wiley in Concurrency and Computation: Practice and Experience
- Vol. 29 (20)
Abstract
Summary: Regular expression matching as a core component of deep packet inspection is widely used in various kinds of modern network intrusion detection system, traffic classification system, network monitoring system, and so on. In these systems, regular expressions are typically converted to a deterministic finite automaton (DFA), which takes O(1) to scan each input character. However, DFA generally consumes a large amount of memory. This paper proposes a novel, space‐efficient and time‐efficient DFA presentation, called reduced input character set DFA (RICS‐DFA). A character escaping and replacing scheme is first introduced to decrease the size of DFA's character set and then to reduce DFA's space requirement with a series of optimization techniques. Based on transition rewriting, a RICS‐DFA constructing algorithm with time complexity of O(n) is presented in this paper. For real rule‐sets, RICS‐DFA reduces the memory consumption by 68–92%, compared with the original DFA. Finally, this paper designs a scalable RICS‐DFA matching engine on field‐programmable gate array platform in which the reduced state transition matrix is mapped to on‐chip memories. The throughput of executing deep packet inspection for real rule‐sets can achieve 7–50.5 Gbps. Copyright © 2016 John Wiley & Sons, Ltd.Keywords
Funding Information
- National Natural Science Foundation of China (61402475, 61303171)
This publication has 18 references indexed in Scilit:
- A compression approach to reducing power consumption of TCAMs in regular expression matchingComputer Communications, 2015
- Speculative parallel pattern matching using stride-k DFA for deep packet inspectionJournal of Network and Computer Applications, 2015
- Accelerating regular expression matching over compressed HTTP2015
- TFA: A Tunable Finite Automaton for Pattern Matching in Network Intrusion Detection SystemsIEEE Journal on Selected Areas in Communications, 2014
- A fast regular expression matching engine for NIDS applying prediction scheme2014
- RESeED: Regular Expression Search over Encrypted Data in the Cloud2014
- Enhancing Security of the Android Platform via Multi-level Security Model2014
- A-DFAACM Transactions on Architecture and Code Optimization, 2013
- An improved DFA for fast regular expression matchingACM SIGCOMM Computer Communication Review, 2008
- An efficient digital search algorithm by using a double-array structureIEEE Transactions on Software Engineering, 1989