Title: A Flexible Wildcard-Pattern Matching Accelerator via Simultaneous Discrete Finite Automata
Authors: Tsai, Hsiang-Jen
Chen, Chien-Chih
Peng, Yin-Chi
Tsao, Ya-Han
Chiang, Yen-Ning
Zhao, Wei-Cheng
Chang, Meng-Fan
Chen, Tien-Fu
Department of Computer Science
Keywords: Deep packet inspection (DPI);discrete finite automata (discrete-FA);network security;simultaneous pattern matching;ternary content addressable memory (TCAM) based search engine;wildcard pattern matching
Issue Date: 1-Dec-2017
Abstract: Regular expression matching becomes indispensable elements of Internet of Things network security. However, traditional ternary content addressable memory (TCAM) search engine is unable to handle patterns with wildcards, as it precisely tracks only one active state with single transition. This paper proposes a promising simultaneous pattern matching methodology for wildcard patterns by two separated engines to represent discrete finite automata. A key preprocessing to encode possible postfix pattern by a unique key ensures that follow-up patterns can accurately traverse all possible matches with limited hardware resources. This approach is practical and scalable for achieving good performance and low space consumption in network security, and it can be applicable to any regular expressions even with multiwildcard patterns. The experimental results demonstrate that this scheme can efficiently and accurately recognize wildcard patterns by simultaneously tracking only two active states. By adopting SRAM TCAM in the proposed architecture, the energy consumption is reduced to around 39%, compared with the energy consumption using a computing system that contains a large memory lookup and comparison overhead.
URI: http://dx.doi.org/10.1109/TVLSI.2017.2671408
ISSN: 1063-8210
DOI: 10.1109/TVLSI.2017.2671408
Volume: 25
Begin Page: 3302
End Page: 3316
Appears in Collections:Articles