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

on YouTube ↗24m

" summary

Hyperscan decomposes complex regexes into string fragments and small FA components using graph analyses (dominant path, region, max‑flow/min‑cut), compiles tens of thousands of rules in under a second, and implements graph decomposition plus SIMD‑accelerated shift/bitset DFA engines. It replaces two‑stage manual prefilt ers to avoid duplicate scans, yields about 3x–13x component speedups and an 8.7× Snort throughput improvement on real traces, and is production‑deployed in 40+ commercial products and many cloud servers.

AI-written summary · about

" chapters (17)

1. 0:00Intro
2. 0:24Networking Applications with Regex Matching
3. 3:16Contributions
4. 4:05Wide Adoption of Hyperscan
5. 4:43Decomposition-based Matching
6. 6:40Key Issues with Regex Decomposition
7. 7:06Graph-based Regex Decomposition
8. 9:14Effectiveness of Graph Analysis on Real-world Rules
9. 9:44Quality of Automatically Extracted Keywords
10. 10:43How to Accelerate Pattern Matching Algorithms?
11. 11:15Multi-string Pattern Matching Overview
12. 12:51Multi-string Shift-or Matching
13. 15:42Other Subsystems
14. 16:12Evaluation of Hyperscan
15. 17:19Repex Matching Performance
16. 17:45Real-world DPI Application - Snort
17. 18:33Conclusion

" related talks

• 18mLearning-Enhanced High-Throughput Pattern Matching Based on Programmable Data PlaneMingwei Xu, Qing Li, Yong Jiang, Zili Meng, Guanglin Duan, Yucheng Huang, Zhengxin Zhang, Dan Zhao, Dirk Kutscher, Ruoyu Li · USENIX ATC '25
• 59mCatching Malware En Masse: DNS and IP StyleDhia Mahjoub, Thibault Reuille, Andree Toonk · Black Hat USA 2014
• 58mHunting Malware with Suricata MetadataJosh Stroschein · Security Onion Conference 2021
• 16mSequence Abstractions for Flexible, Line-Rate Network MonitoringDavid Walker, Ryan Beckett, Ratul Mahajan, Xiaoqi Chen, Andrew Johnson · 21st USENIX Symposium on Networked Systems Design and Implementation (NSDI '24)
• 16mIMap: Fast and Scalable In-Network Scanning with Programmable SwitchesMingwei Xu, Guanyu Li, Menghao Zhang, Cheng Guo, Han Bao, Hongxin Hu, Fenghua Li · 19th USENIX Symposium on Networked Systems Design and Implementation (NSDI '22)
• 44mNetsec is Dead(?): Modern Network Fingerprinting for...Vlad Iliushin · BSidesSF 2025
• 24mImproving Internet-Wide Scanning with Dynamic ScanningAlexandre Dulaunoy · FIRSTCON21 Virtual Edition 2.0
• 41mInternet Spelunking: IPv6 Scanning and Device FingerprintingPiotr Kijewski, Dave De Coster · 34th Annual FIRST Conference 2022