Hyperscan is a high performance regular expression matching library from Intel that runs on x86 platforms and offers support for Perl Compatible Regular Expressions (PCRE) syntax, simultaneous matching of groups of regular expressions, and streaming operations. It is released as open source software under a BSD license. Hyperscan presents a flexible C API and a number of different modes of operation to ensure its applicability in real networking scenarios. Moreover, a focus on efficient algorithms and the use of Intel® Streaming SIMD Extensions (Intel® SSE) enables Hyperscan to achieve high matching performance. It is suitable for usage scenarios such as deep packet inspection (DPI), intrusion detection systems (IDS), intrusion prevention system (IPS), and firewalls, and has been deployed in network security solutions worldwide. Hyperscan has also been integrated into widely used open-source IDS and IPS products like Snort* and Suricata*.
An open source version of the library is available at https://github.com/intel/hyperscan. Intel has an upgraded library version that is available through your Intel sales representative.
Under the Hood
Hyperscan’s workflow can be divided into two parts: compile time and run-time.
Compile time
Hyperscan comes with a regular expression compiler written in C++. As shown in Figure 1, it takes regular expressions as input. Depending on the Intel® architecture platform features available, user-defined modes and pattern features, Hyperscan generates a corresponding pattern database through a complex graph analysis and optimization process. The generated database can also be serialized and stored in memory for later use by the runtime.
Figure 1: Hyperscan compilation process
Figure 2: Hyperscan run-time
Run-time
The Hyperscan run-time is developed in C. Figure 2 shows a high-level block diagram of the main components of the run-time. You need to pre-allocate a scratch space for temporary information used during scanning, and then use the compiled database to call Hyperscan's scan APIs to trigger internal matching engines (nondeterministic finite automaton (NFA), deterministic finite automaton (DFA), and so on) to match the corpus. Hyperscan accelerates these engines with the help of single instruction, multiple data (SIMD) instructions provided by the Intel processor, and matches are delivered to the user application for processing via a user-provided callback function. Since the Hyperscan pattern database is read-only, users can share the database between multiple CPU cores or multiple threads to enhance matching scalability.
Features
Versatile Functionality
Hyperscan supports cross-compilation for multiple Intel processors, with specific optimizations for different instruction sets. It has no operating system restrictions, supports both virtual machine and container scenarios, covers most PCRE syntax, and supports complex expressions that include syntaxes such as ". *" and "[^>] *". Different modes of operation (streaming, block, and vectored) are available to meet the requirements of different scenarios. If requested through the use of a per-pattern flag, Hyperscan can find the starting and ending positions of the matching data in the input stream. For more information, see the current version of the Hyperscan Developer Reference Guide.
Large-scale Matching
Depending on complexity, Hyperscan can support matching a large set of rules. Unlike most regular matching engines, Hyperscan supports multi-pattern matching. After you specify a unique ID for each rule, Hyperscan is able to compile the rules into a database and output all the current matching rule IDs during the matching process.
Figure 3: Data scattered in different units in time order
Streaming mode
Hyperscan supports three modes of operation: block mode, streaming mode, and vectored mode. Block mode is the most straightforward, where a single contiguous block of data is scanned, with matches returned to the caller as they are found. Streaming mode is designed for cross-packet matching in networking scenarios where the data to be scanned is broken up into multiple packets. In streaming mode, Hyperscan can save the match state for the current data block and use it as the initial match state when a new data block arrives. As shown in Figure 3, streaming mode guarantees the consistency of the final matches regardless of how the “xxxxabcxxxxxxxdefx“ data is split into packets over time. In addition, Hyperscan can compress the saved match state to reduce the application’s memory footprint. Streaming mode operation provides a simple way to scan data that arrives over a period of time without requiring you to buffer and rescan packets or limit scanning to a fixed window of historical data. Finally, there is vectored mode, which offers scanning in sequence of a set of data blocks that are not contiguous in memory.
High Performance and Scalability
Hyperscan requires the Intel® Streaming SIMD Extensions 3 instruction set at a minimum and makes use of SIMD instructions to accelerate matching performance. Below, we provide a brief summary of a publicly-available performance demo, Performance Analysis of Hyperscan with hsbench.
We use three different pattern sets for this analysis.
- Snort Literals is a set of 3,316 literal patterns extracted from the sample ruleset included with the Snort* 3 network intrusion detection system.
- Snort PCREs is a set of 847 regular expressions that was also extracted from the sample ruleset that includes Snort 3, taken from rules targeted at HTTP traffic.
- Teakettle 2500 is a set of 2,500 synthetic patterns generated with a script that produces regular expressions of limited complexity. We tested these pattern sets on alexa200.db, a large traffic sample constructed from a PCAP capture of an automated Web browser browsing a subset of the top sites listed on Alexa*.
These pattern sets and corpora are available at https://01.org/blogs/jpviiret/2017/performance-analysis-hyperscan-hsbench.
Figure 4 shows Hyperscan's matching performance (Gbps) in block mode on the Intel® Xeon® processor E5-2699 v4 @ 2.20 GHz.
Figure 4: Hyperscan performance in block mode on different rule sets.
Figure 4 shows that Hyperscan can achieve good single core performance using different rule sets. Moreover, it has high scalability, in which its matching performance grows almost linearly as the number of cores in use increases.
Integration of Hyperscan and the DPDK
Figure 5: Performance of Hyperscan and Data Plane Development Kit integration
The Data Plane Development Kit (DPDK) enables high speed network packet processing and forwarding, and is widely applied in the industry. Hyperscan and DPDK can be integrated into a high-performance DPI solution. Figure 5 shows the performance data of the integrated solution. In the test, we used real patterns and HTTP traffic as input. The integration of Hyperscan and DPDK delivers high performance, and at larger packets sizes the performance can reach wire speed in this test.
Summary
Hyperscan provides a flexible, easy to use library that enables you to match large numbers of patterns simultaneously with high performance and good scalability, as well as providing unique functionality for network packets processing. The integration of Hyperscan and the DPDK also provides mature and efficient solutions for DPI, IDS, IPS and other related products.
About the Author
Xiang Wang is a software engineer working on Hyperscan at Intel. His major areas of focus include automata theory and regular expression matching. He works on a pattern matching engine optimized by Intel architecture that is at the core of DPI, IDS, IPS, and firewalls in the network security domain.