標題: A high-performance memory-efficient pattern matching algorithm and its implementation
作者: Lee, Tsern-Huei
Liang, Chia-Chi
電信工程研究所
Institute of Communications Engineering
公開日期: 2006
摘要: 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.
URI: http://hdl.handle.net/11536/17170
ISBN: 978-1-4244-0548-0
ISSN: 0886-1420
期刊: TENCON 2006 - 2006 IEEE REGION 10 CONFERENCE, VOLS 1-4
起始頁: 512
結束頁: 515
Appears in Collections:Conferences Paper