Bits filter: a high-performance multiple string pattern matching algorithm for malware detection

Resource type
Thesis type
(Thesis) M.Sc.
Date created
Author: Lin, Dan
Multiple string pattern matching is the key technique of many security applications such as anti-virus scanning and intrusion detection. The growing size of on-line content and increasing network and CPU speed push the need for a fast multi-string search algorithm. The thesis investigates SIMD and parallel bit stream technologies in high performance text processing. A three-pass filtering algorithm called Bits Filter based on these technologies was developed to provide fast calculation and also to minimize the data cache misses. This algorithm is then studied by balancing the tradeoffs and considering various parameters such as text size, pattern set size, filter size and segment size. Comparisons are made with implementations of the Aho-Corasick algorithm extracted from the open-source security applications Snort and ClamAV. Whereas the Aho-Corasick implementations typically require 50-300 cycles per input byte of the text in these studies, the Bits Filter algorithm requires only about 2-7 cycles per byte.
Copyright statement
Copyright is held by the author.
The author has not granted permission for the file to be printed nor for the text to be copied and pasted. If you would like a printable copy of this thesis, please contact
Scholarly level
Member of collection
Attachment Size
etd5835.pdf 657.39 KB