Teddy: An Efficient SIMD-based Literal Matching Engine for Scalable Deep Packet Inspection
Kun Qiu, Harry M. Chang, Yang Hong, Wenjun Zhu, Xiang Wang, Baoqian Li · 2021
Deep Packet Inspection (DPI), which is one of the most important network techniques, has been widely utilized in current networking systems. By comparing the payloads of traffic to an existing signature database, DPI can identify whether traffic or packet is harmful, or belong to which application. The literal matching engine, which plays a key role in DPI, is the primary determinant of the system performance. FDR, an engine that can match a character with multiple literals in only 3 SIMD operations, has been developed. However, FDR has a significant performance drop-off when the signature database is composed of small-scale literal rule sets, whose occupations are larger than 90% in the modern database. In this paper, we have designed Teddy, an engine that is highly optimized for small-scale literal rule sets. Comparing with FDR, Teddy significantly increases the efficiency in small-scale literal rule sets by designing a novel algorithm that can parallelly match up to 64 characters with only 16 SIMD operations. Meanwhile, to evaluate Teddy in real-world DPI systems, we have implemented Teddy in Hyperscan with AVX512 platforms. The evaluation results show that Teddy achieves a maximum of 35.29x performance increases than Aho-corasick (AC), 2.16x performance increases than FDR in most cases.