Kangaroo: Accelerating String Matching by Running Multiple Collaborative Finite State Machines
- 19 September 2014
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Journal on Selected Areas in Communications
- Vol. 32 (10) , 1
Abstract
String matching is a key technique for network security applications such as network intrusion detection systems and antivirus scanners, where the payload of every packet is inspected against thousands of patterns in real time. As the transmission rate of Internet links is getting higher and higher, the speed of matching engines is required to be faster and faster. Existing deterministic finite automaton (DFA)-based approaches achieve high throughput at the expense of extremely expensive memory cost; therefore, they are not suitable for the scenarios where only limited on-chip memory resources are available. To achieve fast matching speed while controlling memory expense, in this paper, we propose Kangaroo, a compact string matching scheme that scans multiple characters each time by running multiple small-sized finite state machines in parallel. Specifically, Kangaroo processes k consecutive characters mostly in one cycle by accessing k different memories in parallel, where k is a predefined factor that can be tuned based on the requirement of applications. Kangaroo is memory efficient. Experimental evaluations on Snort and ClamAV rule sets show that a tenfold increase in speed can be practically achieved by a single Kangaroo matching engine with a reduced memory cost comparing with the state-of-the-art DFA-based approaches.Keywords
This publication has 19 references indexed in Scilit:
- StriFA: Stride Finite Automata for High-Speed Regular Expression Matching in Network Intrusion Detection SystemsIEEE Systems Journal, 2013
- Differential Encoding of DFAs for Fast Regular Expression MatchingIEEE/ACM Transactions on Networking, 2010
- Surmounting Data Overflow Problems in the Collection of Information for Emerging High-Speed Network SystemsIEEE Systems Journal, 2010
- Parallel Architecture for High Throughput DFA-Based Deep Packet Inspection2010
- Deflating the big bang2008
- A Memory Efficient Multiple Pattern Matching Architecture for Network Security2008
- A hybrid finite automaton for practical deep packet inspection2007
- Fast and memory-efficient regular expression matching for deep packet inspection2006
- Fast and Scalable Pattern Matching for Network Intrusion Detection SystemsIEEE Journal on Selected Areas in Communications, 2006
- Efficient hardware hashing functions for high performance computersIEEE Transactions on Computers, 1997