A high-performance memory-efficient pattern matching algorithm and its implementation

Tsern-Huei Lee*, Chia Chi Liang

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

2 Scopus citations

Abstract

Because of its accuracy, pattern matching technique has recently been applied to Internet security applications such as intrusion detection/ prevention, anti-virus, and anti-malware. Among the various pattern matching algorithms, the Aho-Corasick (AC) can match multiple pattern strings simultaneously with worst-case performance guarantee and thus is widely adopted. However, the throughput performance of the original AC may not be satisfactory for high speed environments because only one symbol is processed in an operation cycle. In this paper we present an extension of the AC algorithm where multiple symbols are processed in an operation cycle to improve throughput performance. In our proposed scheme, all pattern strings, and the input text string as well, are divided into K substrings, if K symbols are processed in an operation cycle. Moreover, K pattern search engines are employed to scan the text substrings in parallel. As a result, the throughput performance can be improved by K times. We implemented our proposed pattern matching scheme with Xilinx FPGA and achieved more than 4.5Gbps throughput for K= 4.

Original languageEnglish
Title of host publication2006 IEEE Region 10 Conference, TENCON 2006
PublisherInstitute of Electrical and Electronics Engineers Inc.
ISBN (Print)1424405491, 9781424405497
DOIs
StatePublished - 1 Jan 2006
Event2006 IEEE Region 10 Conference, TENCON 2006 - Hong Kong, China
Duration: 14 Nov 200617 Nov 2006

Publication series

NameIEEE Region 10 Annual International Conference, Proceedings/TENCON
ISSN (Print)2159-3442
ISSN (Electronic)2159-3450

Conference

Conference2006 IEEE Region 10 Conference, TENCON 2006
CountryChina
CityHong Kong
Period14/11/0617/11/06

Fingerprint Dive into the research topics of 'A high-performance memory-efficient pattern matching algorithm and its implementation'. Together they form a unique fingerprint.

Cite this