Optimization of pattern matching circuits for regular expression on FPGA

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

Research output: Contribution to journalArticle

42 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
Number of pages1
JournalIEEE Transactions on Very Large Scale Integration (VLSI) Systems
Volume15
Issue number12
DOIs
Publication statusPublished - 2007 Dec 1

Fingerprint

Pattern matching
Field programmable gate arrays (FPGA)
Networks (circuits)
Intrusion detection
Computer aided design
Hardware

Keywords

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

ASJC Scopus subject areas

  • Software
  • Hardware and Architecture
  • Electrical and Electronic Engineering

Cite this

Optimization of pattern matching circuits for regular expression on FPGA. / Lin, Cheng-Hung; Huang, Chih Tsun; Jiang, Chang Ping; Chang, Shih Chieh.

In: IEEE Transactions on Very Large Scale Integration (VLSI) Systems, Vol. 15, No. 12, 01.12.2007.

Research output: Contribution to journalArticle

@article{87649f76ee96421d84d9ec6e404ed78b,
title = "Optimization of pattern matching circuits for regular expression on FPGA",
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.",
keywords = "Field-programmable gate array (FPGA), Finite automata, Intrusion detection, Pattern matching",
author = "Cheng-Hung Lin and Huang, {Chih Tsun} and Jiang, {Chang Ping} and Chang, {Shih Chieh}",
year = "2007",
month = "12",
day = "1",
doi = "10.1109/TVLSI.2007.909801",
language = "English",
volume = "15",
journal = "IEEE Transactions on Very Large Scale Integration (VLSI) Systems",
issn = "1063-8210",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
number = "12",

}

TY - JOUR

T1 - Optimization of pattern matching circuits for regular expression on FPGA

AU - Lin, Cheng-Hung

AU - Huang, Chih Tsun

AU - Jiang, Chang Ping

AU - Chang, Shih Chieh

PY - 2007/12/1

Y1 - 2007/12/1

N2 - 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.

AB - 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.

KW - Field-programmable gate array (FPGA)

KW - Finite automata

KW - Intrusion detection

KW - Pattern matching

UR - http://www.scopus.com/inward/record.url?scp=36649024135&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=36649024135&partnerID=8YFLogxK

U2 - 10.1109/TVLSI.2007.909801

DO - 10.1109/TVLSI.2007.909801

M3 - Article

AN - SCOPUS:36649024135

VL - 15

JO - IEEE Transactions on Very Large Scale Integration (VLSI) Systems

JF - IEEE Transactions on Very Large Scale Integration (VLSI) Systems

SN - 1063-8210

IS - 12

ER -