Deterministic memory-efficient string matching algorithms for intrusion detection
Nathan Tuck, Timothy Sherwood, Brad Calder et al. · IEEE Conference on Computer Communications (INFOCOM) · 2005
Intrusion detection systems (IDSs) have become widely recognized as powerful tools for identifying, deterring and deflecting malicious attacks over the network. Essential to almost every intrusion detection system is the ability to search through packets and identify content that matches known attacks. Space and time efficient string matching algorithms are therefore important for identifying these packets at line rate. We examine string matching algorithms and their use for intrusion detection, in particular, we focus our efforts on providing worst-case performance that is amenable to hardware implementation. We contribute modifications to the Aho-Corasick string-matching algorithm that drastically reduce the amount of memory required and improve its performance on hardware implementations. We also show that these modifications do not drastically affect software performance on commodity processors, and therefore may be worth considering in these cases as well.
Cited by 395 works. doi:10.1109/infcom.2004.1354682
Authors
References
- Efficient string matching
- Snort - Lightweight Intrusion Detection for Networks
- A fast string searching algorithm
- Small forwarding tables for fast routing lookups
- GLIMPSE: a tool to search through entire file systems
- A string matching algorithm fast on the average
- Survey and taxonomy of IP address lookup algorithms
- Deep packet inspection using parallel bloom filters
- A FAST ALGORITHM FOR MULTI-PATTERN SEARCHING
- Tree bitmap