Bolt: Scalable and Cost-Efficient Multistring Pattern Matching With Programmable Switches
- 2 September 2022
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE/ACM Transactions on Networking
- Vol. 31 (2) , 846-861
Abstract
Multi-string pattern matching is a crucial building block for many network security applications and thus of great importance. Since every byte of a packet has to be inspected by a large set of patterns, it often becomes a bottleneck of these applications and dominates the performance of an entire system. Many existing studies have been devoted to alleviating this performance bottleneck either by algorithm optimization or hardware acceleration. However, neither one provides the desired scalability and costs that keep pace with the drastic increase in network bandwidth and traffic today. To address these issues, in this paper, we present, a scalable and cost-efficient multi-string pattern matching system leveraging the capability of emerging programmable switches. combines the following techniques: (1) an efficient state encoding scheme to fit a large number of strings into the limited memory on a programmable switch; (2) a variable $k$ -stride transition mechanism to increase the throughput significantly with the same level of memory cost; and (3) a compact pattern2rule mapping method to accommodate multiple co-existing strings in one rule. We implement a prototype of and make its source code publicly available. Extensive evaluations demonstrate that can provide multi-hundred Gbps throughput and scales well with various pattern sets and workloads.Keywords
Funding Information
- National Key Research and Development Program of China (2018YFB1800405)
- National Science Foundation of China (61772307)
- Beijing Postdoctoral Science Foundation
This publication has 76 references indexed in Scilit:
- Practical regular expression matching free of scalability and performance barriersComputer Communications, 2014
- An efficient multicharacter transition string-matching engine based on the aho-corasick algorithmACM Transactions on Architecture and Code Optimization, 2013
- A-DFAACM Transactions on Architecture and Code Optimization, 2013
- MS-DFA: Multiple-Stride Pattern Matching for Scalable Deep Packet InspectionThe Computer Journal, 2010
- Z3: An Efficient SMT Solver2008
- Memory efficient string matching algorithm for network intrusion management systemTsinghua Science and Technology, 2007
- A fast string-matching algorithm for network processor-based intrusion detection systemACM Transactions on Embedded Computing Systems, 2004
- Fast string searchingSoftware: Practice and Experience, 1991
- A fast string searching algorithmCommunications of the ACM, 1977
- Fast Pattern Matching in StringsSIAM Journal on Computing, 1977