Visible to the public A factor-searching-based multiple string matching algorithm for intrusion detection

TitleA factor-searching-based multiple string matching algorithm for intrusion detection
Publication TypeConference Paper
Year of Publication2014
AuthorsYanbing Liu, Qingyun Liu, Ping Liu, Jianlong Tan, Li Guo
Conference NameCommunications (ICC), 2014 IEEE International Conference on
Date PublishedJune
KeywordsAC, Arrays, Automata, automata theory, automata-based multiple string matching algorithms, bit-vector, ClamAV, factor searching-based algorithms, factor-searching-based multiple string matching algorithm, huge memory usage, Intrusion detection, matching speed, multiple string matching, network intrusion detection systems, Pattern matching, SBDM, SBOM, security of data, Snort, space complexity, space-efficient, space-efficient multiple string matching algorithm BVM, string matching, succinct hash table, synthetic rules, Time complexity, URL blacklist
Abstract

Multiple string matching plays a fundamental role in network intrusion detection systems. Automata-based multiple string matching algorithms like AC, SBDM and SBOM are widely used in practice, but the huge memory usage of automata prevents them from being applied to a large-scale pattern set. Meanwhile, poor cache locality of huge automata degrades the matching speed of algorithms. Here we propose a space-efficient multiple string matching algorithm BVM, which makes use of bit-vector and succinct hash table to replace the automata used in factor-searching-based algorithms. Space complexity of the proposed algorithm is O(rm2 + SpP |p|), that is more space-efficient than the classic automata-based algorithms. Experiments on datasets including Snort, ClamAV, URL blacklist and synthetic rules show that the proposed algorithm significantly reduces memory usage and still runs at a fast matching speed. Above all, BVM costs less than 0.75% of the memory usage of AC, and is capable of matching millions of patterns efficiently.

DOI10.1109/ICC.2014.6883393
Citation Key6883393