A factor-searching-based multiple string matching algorithm for intrusion detection
Title | A factor-searching-based multiple string matching algorithm for intrusion detection |
Publication Type | Conference Paper |
Year of Publication | 2014 |
Authors | Yanbing Liu, Qingyun Liu, Ping Liu, Jianlong Tan, Li Guo |
Conference Name | Communications (ICC), 2014 IEEE International Conference on |
Date Published | June |
Keywords | AC, 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. |
DOI | 10.1109/ICC.2014.6883393 |
Citation Key | 6883393 |
- network intrusion detection systems
- URL blacklist
- Time complexity
- synthetic rules
- succinct hash table
- string matching
- space-efficient multiple string matching algorithm BVM
- space-efficient
- space complexity
- Snort
- security of data
- SBOM
- SBDM
- pattern matching
- AC
- multiple string matching
- matching speed
- Intrusion Detection
- huge memory usage
- factor-searching-based multiple string matching algorithm
- factor searching-based algorithms
- ClamAV
- bit-vector
- automata-based multiple string matching algorithms
- automata theory
- automata
- arrays