TY - JOUR
T1 - Profiling and accelerating string matching algorithms in three network content security applications
AU - Lin, Po Ching
AU - Li, Zhi Xiang
AU - Lin, Ying-Dar
AU - Lai, Yuan Cheng
AU - Lin, Frank C.
PY - 2006/6
Y1 - 2006/6
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=77955099121&partnerID=8YFLogxK
U2 - 10.1109/COMST.2006.315851
DO - 10.1109/COMST.2006.315851
M3 - Review article
AN - SCOPUS:77955099121
SN - 1553-877X
VL - 8
SP - 24
EP - 37
JO - IEEE Communications Surveys and Tutorials
JF - IEEE Communications Surveys and Tutorials
IS - 2
ER -