A SIMD instruction executes the same operation on multiple data in parallel.
A SIMD operation is performed on multiple lanes of two SIMD registers independently, and the results are stored in the third register. Modern CPU supports a number of SIMD instructions that can work on specialized vector registers (SSE, AVX, etc.). The latest AVX512 instructions support up to 512-bit operations simultaneously.
一次 SIMD 操作是對(duì)兩個(gè) SIMD 寄存器的多個(gè)通道獨(dú)立進(jìn)行，然后結(jié)果存儲(chǔ)在第三個(gè)寄存器中?，F(xiàn)代 CPU 支持可以在專(zhuān)用向量寄存器（SSE、AVX 等）上運(yùn)行的 SIMD 指令。最新的 AVX512 指令最多可同時(shí)支持 512 位操作。
Hyperscan 超掃描算法：用于現(xiàn)代CPU的“快速-多模式”正則表達(dá)式匹配器
Hyperscan: A Fast Multi-pattern Regex Matcher for Modern CPUs
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 re-quirement 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 through-put improvement.?
Our evaluation shows that Hyperscan improves the performance of Snort by a factor of 8.7 for a real traffic trace.
Deep packet inspection (DPI) provides the fundamental functionality for many middlebox applications that deal with L7 protocols, such as intrusion detection systems (IDS)。
Despite continued efforts, the performance of regex matching on a commodity server still remains impractical to directly serve today’s large network bandwidth. Instead, the de-facto best practice of high-performance DPI generally employs multi-string pattern matching as a pre-condition for expensive regex matching.?
This hybrid approach (or prefiltering) is attractive as multi-string matching is known to outperform multi-regex matching by two orders of magnitude , and most input traffic is innocent, making it more efficient to defer a rigorous check. For example, popular IDSes like Snort and Suricata specify a string pattern per each regex for prefiltering, and launch the corresponding regex matching only if the string is found in the input stream.
盡管一直在努力，商品服務(wù)器上的正則表達(dá)式匹配的性能仍然不適合直接服務(wù)于當(dāng)今的大網(wǎng)絡(luò)帶寬。相反，高性能DPI的實(shí)際最佳實(shí)踐，通常采用多字符串模式匹配作為昂貴的正則表達(dá)式匹配的先決條件。
這種混合方法（或預(yù)過(guò)濾）很有吸引力，因?yàn)楸娝苤?b>多字符串匹配的性能比多正則表達(dá)式匹配高出兩個(gè)數(shù)量級(jí)，而且大多數(shù)輸入流量都是無(wú)辜的，這使得推遲嚴(yán)格檢查更加有效。例如，像Snort和Suricata這樣的流行IDSes，為每個(gè)正則表達(dá)式指定一個(gè)用于預(yù)過(guò)濾的字符串模式，并且，只有在輸入流中找到字符串時(shí)，才啟動(dòng)相應(yīng)的正則表達(dá)式匹配。
However, the current prefilter-based matching has a number of limitations.?
First, string keywords are often defined manually by humans. Manual choice does not scale as the ruleset expands over time, and improper keywords would waste CPU cycles on redundant regex matching.?
Second, string matching and regex matching are executed as two separate tasks, with the former leveraged only as a trigger for the latter. This results in duplicate matching of the string keywords when the corresponding regex matching is executed.?
Third, current regex matching typically translates an entire regex into a single finite automaton (FA). If the number of deterministic finite automaton (DFA) states becomes too large, one must resort to a slower non-deterministic finite automaton (NFA) for matching of the whole regex.
然而，當(dāng)前基于前置濾波器的匹配有許多限制。
首先，字符串關(guān)鍵字，通常由人手工定義。手動(dòng)選擇不會(huì)隨著規(guī)則集隨著時(shí)間的推移而擴(kuò)展，不正確的關(guān)鍵字，會(huì)在冗余的正則表達(dá)式匹配上浪費(fèi)CPU周期。
其次，字符串匹配和正則表達(dá)式匹配，作為兩個(gè)獨(dú)立的任務(wù)執(zhí)行，前者僅作為后者的觸發(fā)器。當(dāng)執(zhí)行相應(yīng)的正則表達(dá)式匹配時(shí)，這會(huì)導(dǎo)致字符串關(guān)鍵字的重復(fù)匹配。
第三，當(dāng)前正則表達(dá)式匹配，通常將整個(gè)正則表達(dá)式轉(zhuǎn)換為單個(gè)有限自動(dòng)機(jī)（FA）。如果確定型有窮自動(dòng)機(jī)（DFA）狀態(tài)的數(shù)目過(guò)大，則必須使用較慢的非確定型有窮自動(dòng)機(jī)（NFA）來(lái)匹配整個(gè)正則表達(dá)式。
Hyperscan, a high performance regex matching system that exploits regex decomposition as the first principle. Regex decomposition splits a regex pattern into a series of disjoint string and FA components。
This translates regex matching into a sequence of decomposed subregex matching whose execution and matching order is controlled by fast string matching.
超掃描，一個(gè)高性能正則表達(dá)式匹配系統(tǒng)，利用正則表達(dá)式分解作為第一原則。正則表達(dá)式分解將正則表達(dá)式模式拆分為一系列不相交的字符串和FA組件。
這將正則表達(dá)式匹配轉(zhuǎn)換為分解的子正則表達(dá)式匹配序列，其執(zhí)行和匹配順序由快速字符串匹配控制。
This design brings a number of benefits.?
First, our regex decomposition identifies string components automatically by performing rigorous structural analyses on the NFA graph of a regex. Our algorithm ensures that the extracted strings are pre-requisite for the rest of regex matching.
Second, string matching is run as a part of regex matching rather than being employed only as a trigger. Unlike the prefilter-based design, Hyperscan keeps track of the state of string matching throughout regex matching and avoids any redundant operations.?
Third, FA component matching is executed only when all relevant string and FA components are matched. This eliminates unnecessary FA component matching, which allows efficient CPU utilization.?
Finally, most decomposed FA components tend to be small, so they are more likely to be able to be converted to a DFA and benefit from fast DFA matching.
這種設(shè)計(jì)帶來(lái)了許多好處。
首先，正則表達(dá)式分解，通過(guò)對(duì)正則表達(dá)式的NFA圖，執(zhí)行嚴(yán)格的結(jié)構(gòu)分析，來(lái)自動(dòng)識(shí)別字符串組件。算法確保提取的字符串是正則表達(dá)式匹配其余部分的先決條件。
其次，字符串匹配，作為正則表達(dá)式匹配的一部分運(yùn)行，而不是僅作為觸發(fā)器使用。與基于前置過(guò)濾器的設(shè)計(jì)不同，Hypercan在整個(gè)正則表達(dá)式匹配過(guò)程中，跟蹤字符串匹配的狀態(tài)，并避免任何冗余操作。
第三，F(xiàn)A組件匹配，僅在匹配所有相關(guān)字符串和FA組件時(shí)執(zhí)行。這消除了不必要的FA組件匹配，從而允許高效的CPU利用率。
最后，大多數(shù)分解的FA組件往往很小，因此它們更有可能轉(zhuǎn)換為DFA，并受益于快速的DFA匹配。
Beyond the benefits of regex decomposition, Hyperscan also brings a significant performance boost with single-instruction-multiple-data (SIMD)?accelerated pattern matching algorithms.
Source code at https://github.com/intel/hyperscan
參考資料：
https://github.com/intel/hyperscan
Hyperscan is a high-performance multiple regex matching library. It follows the regular expression syntax of the commonly-used libpcre library, but is a standalone library with its own C API.
Hyperscan uses hybrid automata techniques to allow simultaneous matching of large numbers (up to tens of thousands) of regular expressions and for the matching of regular expressions across streams of data.
Hyperscan is typically used in a DPI library stack.
https://www.usenix.org/sites/default/files/conference/protected-files/nsdi19_slides_wang_xiang.pdf
https://www.youtube.com/watch?v=Le67mP-jIa8
https://www.usenix.org/conference/nsdi19/presentation/wang-xiang
https://www.usenix.org/system/files/nsdi19-wang-xiang.pdf
http://intel.github.io/hyperscan/dev-reference/getting_started.html#very-quick-start
