A Flexible Wildcard-Pattern Matching Accelerator via Simultaneous Discrete Finite Automata

Hsiang Jen Tsai*, Chien Chih Chen, Yin Chi Peng, Ya Han Tsao, Yen Ning Chiang, Wei Cheng Zhao, Meng Fan Chang, Tien-Fu Chen

*Corresponding author for this work

Research output: Contribution to journalArticle

1 Scopus citations

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.

Original languageEnglish
Article number7873362
Pages (from-to)3302-3316
Number of pages15
JournalIEEE Transactions on Very Large Scale Integration (VLSI) Systems
Volume25
Issue number12
DOIs
StatePublished - 1 Dec 2017

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

Fingerprint Dive into the research topics of 'A Flexible Wildcard-Pattern Matching Accelerator via Simultaneous Discrete Finite Automata'. Together they form a unique fingerprint.

  • Cite this