Harry: A Scalable SIMD-based Multi-literal Pattern Matching Engine for Deep Packet Inspection
Authors:
- 17 May 2023
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 1-10
Abstract
Deep Packet Inspection (DPI) is a significant network security technique. It examines traffic workloads by searching for specific rules. Since every byte of packets needs to be examined by many literal rules, multi-literal matching becomes the performance bottleneck of DPI. FDR, the fastest multi-literal matching engine on CPUs, takes advantage of Single-Instruction-Multiple-Data (SIMD) to alleviate this bottleneck and achieves a performance boost over the widely-used Aho-Corasick (AC) algorithm. However, FDR does not deeply exploit the data-level parallelism of SIMD and its SIMD vector utilization is only 50%. Besides, limited by certain SIMD shift instructions, it cannot benefit from advanced SIMD instruction sets. To overcome these issues, we propose Harry, a scalable and SIMD-based multi-literal matching engine. Harry adopts a column-vector-based matching algorithm to improve the data-level parallelism and SIMD vector utilization. To support the algorithm, it takes two encoding methods to compress the mask table. Also, it utilizes shuffle instruction to implement shift. We implement Harry on commodity CPU and evaluate it with real network traffic and DPI rules. Our evaluation shows that Harry reaches a throughput of 30∼70Gbit/s, up to 52x that of AC and 2.09x of FDR. It has been successfully deployed in Hyperscan.Keywords
Funding Information
- National Natural Science Foundation of China
This publication has 26 references indexed in Scilit:
- Scalable Algorithms for NFA Multi-Striding and NFA-Based Deep Packet Inspection on GPUsIEEE/ACM Transactions on Networking, 2015
- On-the-Fly Principled Speculation for FSM ParallelizationACM SIGPLAN Notices, 2015
- Independent comparison of popular DPI tools for traffic classificationComputer Networks, 2015
- Kangaroo: Accelerating String Matching by Running Multiple Collaborative Finite State MachinesIEEE Journal on Selected Areas in Communications, 2014
- A-DFAACM Transactions on Architecture and Code Optimization, 2013
- Kargus2012
- MS-DFA: Multiple-Stride Pattern Matching for Scalable Deep Packet InspectionThe Computer Journal, 2010
- iNFAntACM SIGCOMM Computer Communication Review, 2010
- Generating realistic workloads for network intrusion detection systems2004
- Shift-or string matching with super-alphabetsInformation Processing Letters, 2003