Profiling and accelerating string matching algorithms in three network content security applications

Po Ching Lin, Zhi Xiang Li, Ying-Dar Lin, Yuan Cheng Lai, Frank C. Lin

Research output: Contribution to journalReview articlepeer-review

19 Scopus citations

Abstract

The efficiency of string matching algorithms is essential for network content security applications, such as intrusion detection systems, anti-virus systems, and Web content filters. This work reviews typical algorithms and profiles their performance under various situations to study the influence of the number, the length, and the character distribution of the signatures on performance. This profiling can reveal the most efficient algorithm in each situation. A fast verification method for some string matching algorithms is also proposed. This work then analyzes the signature characteristics of three content security applications and replaces their original algorithms with the most efficient ones in the profiling. The improvement for both real and synthetic sample data is observed. For example, an open source anti-virus package, ClamAV, is five times faster after the revision. This work features comprehensive profiling results of typical string matching algorithms and observations of their application on network content security. The results can enlighten the choice of a proper algorithm in practical design.

Original languageEnglish
Pages (from-to)24-37
Number of pages14
JournalIEEE Communications Surveys and Tutorials
Volume8
Issue number2
DOIs
StatePublished - 1 Jun 2006

Fingerprint Dive into the research topics of 'Profiling and accelerating string matching algorithms in three network content security applications'. Together they form a unique fingerprint.

Cite this