Optimization of pattern matching circuits for regular expression on FPGA

Cheng Hung Lin*, Chih Tsun Huang, Chang Ping Jiang, Shih Chieh Chang

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

47 Citations (Scopus)

Abstract

Regular expressions are widely used in the network intrusion detection system (NIDS) to represent attack patterns. Previously, many hardware architectures have been proposed to accelerate regular expression matching using field-programmable gate array (FPGA) because FPGAs allow updating of new attack patterns. Because of the increasing number of attacks, we need to accommodate a large number of regular expressions on FPGAs. Although the minimization of logic equations has been studied intensively in the area of computer-aided design (CAD), the minimization of multiple regular expressions has been largely neglected. This paper presents a novel sharing architecture allowing our algorithm to extract and share common subregular expressions. Experimental results show that our sharing scheme significantly reduces the area of pattern matching circuits for regular expression.

Original languageEnglish
Pages (from-to)1303-1310
Number of pages8
JournalIEEE Transactions on Very Large Scale Integration (VLSI) Systems
Volume15
Issue number12
DOIs
Publication statusPublished - 2007 Dec
Externally publishedYes

Keywords

  • Field-programmable gate array (FPGA)
  • Finite automata
  • Intrusion detection
  • Pattern matching

ASJC Scopus subject areas

  • Software
  • Hardware and Architecture
  • Electrical and Electronic Engineering

Fingerprint

Dive into the research topics of 'Optimization of pattern matching circuits for regular expression on FPGA'. Together they form a unique fingerprint.

Cite this