標題: An Efficient and Scalable Pattern Matching Scheme for Network Security Applications
作者: Lee, Tsern-Huei
Huang, Nai-Lun
電信工程研究所
Institute of Communications Engineering
公開日期: 2008
摘要: 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 various famous pattern matching algorithms, the Aho-Corasick (AC) can match multiple pattern strings simultaneously with worst-case performance guarantee and is adopted in both Clam AntiVirus (ClamAV) and Snort intrusion detection open sources. The AC algorithm is based on finite automaton which can be implemented straightforwardly with a two-dimensional state transition table. However, the memory requirement prohibits such an implementation when the total length of the pattern strings is large. The ClamAV implementation limits the depth of the finite automaton and combines with linked lists to reduce memory requirement. The banded-row format is adopted to compress the state transition table and used as an alternative pattern matching machine in Snort. In this paper we present a novel implementation which requires small memory space and achieves high throughput performance. Compared with the banded-row format, our proposed scheme achieves 39.7% reduction in memory requirement for 5,000 patterns randomly selected from ClamAV signatures. Besides, the processing time of our proposed scheme is, on the average, 83.9% of that of the banded-row format for scanning various types of files. Compared with the ClamAV implementation with the same 5,000 patterns and files, our proposed scheme requires slightly more memory space but achieves 80.6% reduction in processing time on the average.
URI: http://hdl.handle.net/11536/3508
ISBN: 978-1-4244-2389-7
ISSN: 1095-2055
期刊: 2008 PROCEEDINGS OF 17TH INTERNATIONAL CONFERENCE ON COMPUTER COMMUNICATIONS AND NETWORKS, VOLS 1 AND 2
起始頁: 951
結束頁: 957
Appears in Collections:Conferences Paper