A factor-searching-based multiple string matching algorithm for intrusion detection

• Main Authors: Yanbing Liu, Qingyun Liu, Ping Liu, Jianlong Tan, Li Guo
• Format: Conference Proceeding
• Language: English
• Subjects: Arrays; Automata; Intrusion detection; multiple string matching; Pattern matching; space-efficient; Time complexity
• ISSN: 1550-3607; 1938-1883
• DOI: 10.1109/ICC.2014.6883393

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(rm 2 + Σ pϵP |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.