Hyperscan: A Fast Multi-pattern Regex Matcher for Modern CPUs

Authors: 

Xiang Wang, Yang Hong, and Harry Chang, Intel; KyoungSoo Park, KAIST; Geoff Langdale, branchfree.org; Jiayu Hu and Heqing Zhu, Intel

Abstract: 

Regular expression matching serves as a key functionality of modern network security applications. Unfortunately, it often becomes the performance bottleneck as it involves compute-intensive scan of every byte of packet payload. With trends towards increasing network bandwidth and a large ruleset of complex patterns, the performance requirement gets ever more demanding.

In this paper, we present Hyperscan, a high performance regular expression matcher for commodity server machines. Hyperscan employs two core techniques for efficient pattern matching. First, it exploits graph decomposition that translates regular expression matching into a series of string and finite automata matching. Unlike existing solutions, string matching becomes a part of regular expression matching, eliminating duplicate operations. Decomposed regular expression components also increase the chance of fast DFA matching as they tend to be smaller than the original pattern. Second, Hyperscan accelerates both string and finite automata matching using SIMD operations, which brings substantial throughput improvement. Our evaluation shows that Hyperscan improves the performance of Snort by a factor of 8.7 for a real traffic trace.

NSDI '19 Open Access Sponsored by NetApp

Open Access Media

USENIX is committed to Open Access to the research presented at our events. Papers and proceedings are freely available to everyone once the event begins. Any video, audio, and/or slides that are posted after the event are also free and open to everyone. Support USENIX and our commitment to Open Access.

BibTeX
@inproceedings {227663,
author = {Xiang Wang and Yang Hong and Harry Chang and KyoungSoo Park and Geoff Langdale and Jiayu Hu and Heqing Zhu},
title = {Hyperscan: A Fast Multi-pattern Regex Matcher for Modern {CPUs}},
booktitle = {16th USENIX Symposium on Networked Systems Design and Implementation (NSDI 19)},
year = {2019},
isbn = {978-1-931971-49-2},
address = {Boston, MA},
pages = {631--648},
url = {https://www.usenix.org/conference/nsdi19/presentation/wang-xiang},
publisher = {USENIX Association},
month = feb
}

Presentation Video