Optimization of regular expression pattern matching circuits on FPGA

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

Research output: Chapter in Book/Report/Conference proceedingConference contribution

50 Citations (Scopus)

Abstract

Regular expressions are widely used in Network Intrusion Detection System (NIDS) to represent patterns of network attacks. Since traditional software-only NIDS cannot catch up to the speed advance of networks, many previous works propose hardware architectures on FPGA to accelerate attack detection. The challenge of hardware implementation is to accommodate the regular expressions to FPGAs of the large number of attacks. Although the minimization of logic equations has been studied intensively in the CAD area, the minimization of multiple regular expressions has been largely neglected. This paper presents a novel architecture allowing our algorithm to extract and share common sub-regular expressions. Experimental results show that our sharing scheme significantly reduces the area of regular expression circuits.

Original languageEnglish
Title of host publicationProceedings - Design, Automation and Test in Europe, DATE'06
DOIs
Publication statusPublished - 2006 Dec 1
EventDesign, Automation and Test in Europe, DATE'06 - Munich, Germany
Duration: 2006 Mar 62006 Mar 10

Publication series

NameProceedings -Design, Automation and Test in Europe, DATE
Volume2
ISSN (Print)1530-1591

Other

OtherDesign, Automation and Test in Europe, DATE'06
CountryGermany
CityMunich
Period06/3/606/3/10

Fingerprint

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

ASJC Scopus subject areas

  • Engineering(all)

Cite this

Lin, C-H., Huang, C. T., Jiang, C. P., & Chang, S. C. (2006). Optimization of regular expression pattern matching circuits on FPGA. In Proceedings - Design, Automation and Test in Europe, DATE'06 [1657107] (Proceedings -Design, Automation and Test in Europe, DATE; Vol. 2). https://doi.org/10.1109/DATE.2004.1269064

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

Proceedings - Design, Automation and Test in Europe, DATE'06. 2006. 1657107 (Proceedings -Design, Automation and Test in Europe, DATE; Vol. 2).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Lin, C-H, Huang, CT, Jiang, CP & Chang, SC 2006, Optimization of regular expression pattern matching circuits on FPGA. in Proceedings - Design, Automation and Test in Europe, DATE'06., 1657107, Proceedings -Design, Automation and Test in Europe, DATE, vol. 2, Design, Automation and Test in Europe, DATE'06, Munich, Germany, 06/3/6. https://doi.org/10.1109/DATE.2004.1269064
Lin C-H, Huang CT, Jiang CP, Chang SC. Optimization of regular expression pattern matching circuits on FPGA. In Proceedings - Design, Automation and Test in Europe, DATE'06. 2006. 1657107. (Proceedings -Design, Automation and Test in Europe, DATE). https://doi.org/10.1109/DATE.2004.1269064
Lin, Cheng-Hung ; Huang, Chih Tsun ; Jiang, Chang Ping ; Chang, Shih Chieh. / Optimization of regular expression pattern matching circuits on FPGA. Proceedings - Design, Automation and Test in Europe, DATE'06. 2006. (Proceedings -Design, Automation and Test in Europe, DATE).
@inproceedings{d3efd3810c004c9183ac377425338e4a,
title = "Optimization of regular expression pattern matching circuits on FPGA",
abstract = "Regular expressions are widely used in Network Intrusion Detection System (NIDS) to represent patterns of network attacks. Since traditional software-only NIDS cannot catch up to the speed advance of networks, many previous works propose hardware architectures on FPGA to accelerate attack detection. The challenge of hardware implementation is to accommodate the regular expressions to FPGAs of the large number of attacks. Although the minimization of logic equations has been studied intensively in the CAD area, the minimization of multiple regular expressions has been largely neglected. This paper presents a novel architecture allowing our algorithm to extract and share common sub-regular expressions. Experimental results show that our sharing scheme significantly reduces the area of regular expression circuits.",
author = "Cheng-Hung Lin and Huang, {Chih Tsun} and Jiang, {Chang Ping} and Chang, {Shih Chieh}",
year = "2006",
month = "12",
day = "1",
doi = "10.1109/DATE.2004.1269064",
language = "English",
isbn = "0769520855",
series = "Proceedings -Design, Automation and Test in Europe, DATE",
booktitle = "Proceedings - Design, Automation and Test in Europe, DATE'06",

}

TY - GEN

T1 - Optimization of regular expression pattern matching circuits on FPGA

AU - Lin, Cheng-Hung

AU - Huang, Chih Tsun

AU - Jiang, Chang Ping

AU - Chang, Shih Chieh

PY - 2006/12/1

Y1 - 2006/12/1

N2 - Regular expressions are widely used in Network Intrusion Detection System (NIDS) to represent patterns of network attacks. Since traditional software-only NIDS cannot catch up to the speed advance of networks, many previous works propose hardware architectures on FPGA to accelerate attack detection. The challenge of hardware implementation is to accommodate the regular expressions to FPGAs of the large number of attacks. Although the minimization of logic equations has been studied intensively in the CAD area, the minimization of multiple regular expressions has been largely neglected. This paper presents a novel architecture allowing our algorithm to extract and share common sub-regular expressions. Experimental results show that our sharing scheme significantly reduces the area of regular expression circuits.

AB - Regular expressions are widely used in Network Intrusion Detection System (NIDS) to represent patterns of network attacks. Since traditional software-only NIDS cannot catch up to the speed advance of networks, many previous works propose hardware architectures on FPGA to accelerate attack detection. The challenge of hardware implementation is to accommodate the regular expressions to FPGAs of the large number of attacks. Although the minimization of logic equations has been studied intensively in the CAD area, the minimization of multiple regular expressions has been largely neglected. This paper presents a novel architecture allowing our algorithm to extract and share common sub-regular expressions. Experimental results show that our sharing scheme significantly reduces the area of regular expression circuits.

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

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

U2 - 10.1109/DATE.2004.1269064

DO - 10.1109/DATE.2004.1269064

M3 - Conference contribution

AN - SCOPUS:34047137188

SN - 0769520855

T3 - Proceedings -Design, Automation and Test in Europe, DATE

BT - Proceedings - Design, Automation and Test in Europe, DATE'06

ER -