Hyperscan在Suricata中的應(yīng)用【轉(zhuǎn)】

Suricata簡介

Hyperscan作為一款高性能的正則表達(dá)式匹配庫，極適用于部署在IDS/IPS等網(wǎng)絡(luò)解決方案中蝇更。
Suricata(https://suricata-ids.org)是一款免費、開源严蓖、成熟鳞绕、快速、健壯的網(wǎng)絡(luò)威脅檢測引擎胳泉，該引擎能夠進(jìn)行實時入侵檢測(IDS)拐叉，嵌入式入侵防御(IPS)，網(wǎng)絡(luò)安全監(jiān)控(NSM)和離線pcap處理扇商。Suricata與其競爭對手Snort類似凤瘦，有著相似的設(shè)計和規(guī)則樣式，同樣涉及到大量純字符串及正則表達(dá)式匹配案铺。本文重點介紹Hyperscan在Suricata中的應(yīng)用蔬芥，主要是單字符串匹配和多字符串匹配的基本原理。

image

Hyperscan的應(yīng)用

自Suricata(3.1 release)開始控汉，Hyperscan在支持的平臺作為其單字符串匹配和多字符串匹配的默認(rèn)選項笔诵。另外也有單正則表達(dá)式匹配的試驗工作。

單字符串匹配

Suricata原先使用BM算法做單字符串匹配姑子，使用Hyperscan后乎婿，由Hyperscan中的Noodle引擎替換相關(guān)工作。Noodle充分發(fā)揮SIMD指令優(yōu)勢街佑，通過對輸入數(shù)據(jù)進(jìn)行快速的預(yù)過濾來實現(xiàn)快速的單字符串匹配谢翎，在AVX2、AVX512上能達(dá)到更快的效果沐旨。預(yù)過濾的基本原理其實是使用樸素的shift-and算法森逮。

例如，對單條字符串規(guī)則/Hyperscan/的單模式匹配磁携，取字符串前2字節(jié)做預(yù)過濾吊宋，構(gòu)建2個16字節(jié)的掩碼：

image

運行時每次讀取16字節(jié)輸入數(shù)據(jù)，用2次PCMPEQB指令與上述掩碼做逐字節(jié)比較颜武。假設(shè)運行時讀到輸入數(shù)據(jù)為“MATCHmyHyperscan”璃搜，則2次PCMPEQB的結(jié)果為（表中的1實際應(yīng)為0xFF，為表達(dá)簡便標(biāo)記為1）：

image

對上述結(jié)果做“shift-and”鳞上，即LSHIFT+AND指令这吻，得到用2個字節(jié)做預(yù)過濾的結(jié)果：

image

預(yù)過濾結(jié)果中出現(xiàn)“1”的位置才是可能產(chǎn)生真實匹配的位置（我們稱之為Positive），我們對這些位置進(jìn)行確認(rèn)篙议，最終生成一個真實匹配（True Positive）唾糯，或者發(fā)現(xiàn)不是真實匹配（False Positive）怠硼。本例中是一個真實匹配。
對AVX2/AVX512環(huán)境移怯，能夠得到更好的表現(xiàn)香璃，因為對AVX2可以構(gòu)建32字節(jié)掩碼且每次讀取32字節(jié)輸入數(shù)據(jù)，對AVX512可以構(gòu)建64字節(jié)掩碼且每次讀取64字節(jié)輸入數(shù)據(jù)舟误，完成同樣的預(yù)過濾目標(biāo)所需的指令數(shù)減少了很多葡秒。

多字符串匹配

Suricata原先使用AC算法做多字符串匹配，使用Hyperscan后嵌溢，由Hyperscan中的Teddy/FDR引擎替換相關(guān)工作眯牧。Teddy通常在輕量級多字符串匹配場景下（2-72條字符串）優(yōu)先使用，F(xiàn)DR則用來應(yīng)對極大量字符串的場景赖草。同樣学少，Teddy和FDR使用SIMD指令對輸入數(shù)據(jù)進(jìn)行快速預(yù)過濾，在多字符串匹配場景下秧骑，比單字符串匹配有更好的效果版确。類似的，其預(yù)過濾的基本原理是使用樸素的shift-or算法乎折。
以Teddy為例阀坏，Teddy通常情況下使用字符串中的后3字節(jié)做預(yù)過濾，對多字符串規(guī)則笆檀，根據(jù)每個字符串的后3字節(jié)進(jìn)行分組忌堂，分組上限為8或16組，為表達(dá)輸入數(shù)據(jù)中每個位置的預(yù)過濾結(jié)果酗洒，前者用1字節(jié)（每位各對應(yīng)一組）士修，后者用2字節(jié)。
例如樱衷，對3條字符串規(guī)則：

/Teddy/

/daddy/

/Hyperscan/

根據(jù)后3字節(jié)分為2組：組0 – “ddy”（0x64, 0x64, 0x79）棋嘲，組1 – “can”（0x63, 0x61, 0x6e）。
再根據(jù)3字節(jié)中的6個4位構(gòu)建出6個16字節(jié)掩碼矩桂，初值全1沸移，每個4位有16種可能取值，對應(yīng)16字節(jié)掩碼中的1字節(jié)侄榴，并在該對應(yīng)字節(jié)的對應(yīng)位（組）上貢獻(xiàn)一個0雹锣。6個掩碼依次對應(yīng)最末字節(jié)低4位、高4位（綠色）癞蚕，倒數(shù)第二字節(jié)低4位蕊爵、高4位（橙色），倒數(shù)第三字節(jié)低4位桦山、高4位（藍(lán)色）攒射。為簡化表達(dá)每字節(jié)只記錄本例中兩組對應(yīng)的兩位：

image

運行時每次讀取16字節(jié)輸入數(shù)據(jù)醋旦，并以上述掩碼用PSHUFB指令逐字節(jié)做映射。假設(shè)運行時讀到輸入數(shù)據(jù)為“TeddyinHyperscan”（54 65 64 64 79 69 6e 48 79 70 65 72 73 63 61 6e）会放，則6次PSHUFB的結(jié)果為：

image

結(jié)果中的”0”表示輸入數(shù)據(jù)中每個位置（列）對規(guī)則集后3字節(jié)是否產(chǎn)生匹配饲齐。相同位置只有高4位和低4位均得到相同組的匹配，才是一個完整字節(jié)的匹配咧最。對相同顏色的掩碼做OR得到：

image

對上述結(jié)果做“shift-or”捂人，第一行不變，第二行做LSHIFT左移1字節(jié)窗市，第三行做LSHIFT左移2字節(jié)先慷，然后做OR得到：

image

此為預(yù)過濾的結(jié)果饮笛，其中的”0”表示在該位置出現(xiàn)與某組連續(xù)后3字節(jié)的匹配咨察，是可能產(chǎn)生真實匹配的位置（Positive）。我們對這些位置進(jìn)行確認(rèn)福青，最終找出與候選組中哪個字符串產(chǎn)生了真實匹配（True Positive）摄狱，或者發(fā)現(xiàn)不是真實匹配（False Positive）。本例中在位置4對組0的“Teddy”无午、位置15對組1的“Hyperscan”產(chǎn)生真實匹配媒役。
同樣的，對AVX2環(huán)境宪迟，我們只需把6個掩碼均復(fù)制擴大一倍至32字節(jié)酣衷，且每次讀取32字節(jié)輸入數(shù)據(jù)；對AVX512環(huán)境次泽，把掩碼復(fù)制擴大至64字節(jié)穿仪，每次讀取64字節(jié)輸入數(shù)據(jù)。完成相同過濾目標(biāo)的指令數(shù)也減少了很多意荤。

性能數(shù)據(jù)

測試環(huán)境：Intel? Core i7 6700K CPU @ 4.0 GHz
軟件版本：Hyperscan 4.3.1啊片，Suricata 3.1
規(guī)則集：Emerging Threats public set (“emerging-all-20161102.rules”)
ET Pro set (“etpro-all-20161102.rules”)
輸入PCAP文件：Alexa Top 100 browsing PCAP file
測試中我們衡量的是全部處理時間，包括編譯和運行玖像。原生的Suricata使用AC算法做多字符串匹配(MPM)和BM算法做單字符串匹配(SPM)紫谷，使用Hyperscan全部替換后，在Emerging Threats規(guī)則集上獲得1.95x性能提升捐寥，在ET Pro規(guī)則集上獲得2.15x性能提升笤昨。
我們同樣比較了單獨替換多字符串AC算法及單獨替換單字符串BM算法的性能，可見替換AC的性能要好于替換BM的性能握恳，而二者性能又都介于原生和全部替換之間咬腋。各性能數(shù)據(jù)如下圖所示。

image

這是可以預(yù)見的結(jié)果睡互，因為對多模式匹配的良好支持正是Hyperscan的一大優(yōu)勢根竿。