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

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.