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

Tsern-Huei Lee*, Chia Chi Liang

*此作品的通信作者

研究成果: Conference contribution同行評審

2 引文 斯高帕斯(Scopus)

摘要

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.

原文English
主出版物標題2006 IEEE Region 10 Conference, TENCON 2006
發行者Institute of Electrical and Electronics Engineers Inc.
ISBN(列印)1424405491, 9781424405497
DOIs
出版狀態Published - 1 一月 2006
事件2006 IEEE Region 10 Conference, TENCON 2006 - Hong Kong, China
持續時間: 14 十一月 200617 十一月 2006

出版系列

名字IEEE Region 10 Annual International Conference, Proceedings/TENCON
ISSN(列印)2159-3442
ISSN(電子)2159-3450

Conference

Conference2006 IEEE Region 10 Conference, TENCON 2006
國家/地區China
城市Hong Kong
期間14/11/0617/11/06

指紋

深入研究「A high-performance memory-efficient pattern matching algorithm and its implementation」主題。共同形成了獨特的指紋。

引用此