Hyperscan在Suricata中的应用

た入场券 2022-06-09 14:29 342阅读 0赞

## Suricata简介 ##

Hyperscan作为一款高性能的正则表达式匹配库，极适用于部署在IDS/IPS等网络解决方案中。  
Suricata(https://suricata-ids.org)是一款免费、开源、成熟、快速、健壮的网络威胁检测引擎，该引擎能够进行实时入侵检测(IDS)，嵌入式入侵防御(IPS)，网络安全监控(NSM)和离线pcap处理。Suricata与其竞争对手Snort类似，有着相似的设计和规则样式，同样涉及到大量纯字符串及正则表达式匹配。本文重点介绍Hyperscan在Suricata中的应用，主要是单字符串匹配和多字符串匹配的基本原理。  
![hyperscan_with_suricata_0.jpg][]

## Hyperscan的应用 ##

自Suricata(3.1 release)开始，Hyperscan在支持的平台作为其单字符串匹配和多字符串匹配的默认选项。另外也有单正则表达式匹配的试验工作。

### 单字符串匹配 ###

Suricata原先使用BM算法做单字符串匹配，使用Hyperscan后，由Hyperscan中的Noodle引擎替换相关工作。Noodle充分发挥SIMD指令优势，通过对输入数据进行快速的预过滤来实现快速的单字符串匹配，在AVX2、AVX512上能达到更快的效果。预过滤的基本原理其实是使用朴素的shift-and算法。

例如，对单条字符串规则/Hyperscan/的单模式匹配，取字符串前2字节做预过滤，构建2个16字节的掩码：  
![hyperscan_with_suricata_1.jpg][]  
运行时每次读取16字节输入数据，用2次PCMPEQB指令与上述掩码做逐字节比较。假设运行时读到输入数据为“MATCHmyHyperscan”，则2次PCMPEQB的结果为（表中的1实际应为0xFF，为表达简便标记为1）：  
![hyperscan_with_suricata_2.jpg][]  
对上述结果做“shift-and”，即LSHIFT+AND指令，得到用2个字节做预过滤的结果：  
![hyperscan_with_suricata_3.jpg][]  
预过滤结果中出现“1”的位置才是可能产生真实匹配的位置（我们称之为Positive），我们对这些位置进行确认，最终生成一个真实匹配（True Positive），或者发现不是真实匹配（False Positive）。本例中是一个真实匹配。  
对AVX2/AVX512环境，能够得到更好的表现，因为对AVX2可以构建32字节掩码且每次读取32字节输入数据，对AVX512可以构建64字节掩码且每次读取64字节输入数据，完成同样的预过滤目标所需的指令数减少了很多。

### 多字符串匹配 ###

Suricata原先使用AC算法做多字符串匹配，使用Hyperscan后，由Hyperscan中的Teddy/FDR引擎替换相关工作。Teddy通常在轻量级多字符串匹配场景下（2-72条字符串）优先使用，FDR则用来应对极大量字符串的场景。同样，Teddy和FDR使用SIMD指令对输入数据进行快速预过滤，在多字符串匹配场景下，比单字符串匹配有更好的效果。类似的，其预过滤的基本原理是使用朴素的shift-or算法。  
以Teddy为例，Teddy通常情况下使用字符串中的后3字节做预过滤，对多字符串规则，根据每个字符串的后3字节进行分组，分组上限为8或16组，为表达输入数据中每个位置的预过滤结果，前者用1字节（每位各对应一组），后者用2字节。  
例如，对3条字符串规则：

<table style="margin-left:0px; font-style:inherit; font-variant:inherit; font-weight:inherit; font-size:12px; line-height:inherit; vertical-align:baseline; margin-top:0px!important; margin-right:0px!important; margin-bottom:0px!important; padding:0px!important; border:none!important; border-collapse:collapse!important; border-spacing:0px!important; width:auto!important; background:none!important; table-layout:auto!important"> 
 <tbody style="margin:0px; padding:0px; border:0px; font-style:inherit; font-variant:inherit; font-weight:inherit; font-size:undefined; line-height:inherit; vertical-align:baseline"> 
  <tr style="font-style:inherit; font-variant:inherit; font-weight:inherit; font-size:undefined; line-height:inherit; background:0px center; margin:0px!important; padding:0px!important; border:none!important; vertical-align:top!important"> 
   <td style="margin:0px!important; padding:0px!important; border:0px; font-style:inherit; font-variant:inherit; font-weight:inherit; font-size:undefined; line-height:inherit; font-family:Monaco,MonacoRegular,&quot;Courier New&quot;,monospace!important; vertical-align:top!important; background:rgb(223,239,255)!important; color:rgb(84,153,222)!important"> 
    <div style="margin:0px; padding:0px; border:0px; font-style:inherit; font-variant:inherit; font-weight:inherit; vertical-align:baseline; background:0px center; white-space:nowrap; line-height:15px!important"> 
     <div style="margin:0px; padding:0px 5px; border:0px; font-style:inherit; font-variant:inherit; font-weight:inherit!important; font-size:inherit!important; line-height:inherit!important; font-family:inherit; vertical-align:baseline; background:0px center; text-align:center; height:inherit">
       1 
     </div> 
     <div style="margin:0px; padding:0px 5px; border:0px; font-style:inherit; font-variant:inherit; font-weight:inherit!important; font-size:inherit!important; line-height:inherit!important; font-family:inherit; vertical-align:baseline; background:rgb(200,225,250)!important; text-align:center; height:inherit; color:rgb(49,124,197)!important">
       2 
     </div> 
     <div style="margin:0px; padding:0px 5px; border:0px; font-style:inherit; font-variant:inherit; font-weight:inherit!important; font-size:inherit!important; line-height:inherit!important; font-family:inherit; vertical-align:baseline; background:0px center; text-align:center; height:inherit">
       3 
     </div> 
    </div> </td> 
   <td style="margin:0px!important; padding:0px!important; border:0px; font-style:inherit; font-variant:inherit; font-weight:inherit; font-size:undefined; line-height:inherit; font-family:Monaco,MonacoRegular,&quot;Courier New&quot;,monospace!important; vertical-align:top!important; background:0px center; width:720px"> 
    <div style="margin:0px; padding:0px; font-style:inherit; font-variant:inherit; font-weight:inherit; vertical-align:baseline; white-space:pre; overflow:visible; border:none!important; line-height:15px!important; background:none!important"> 
     <div style="margin:0px; padding:0px 5px; border:0px; font-style:inherit; font-variant:inherit; font-family:inherit; vertical-align:baseline; background:0px center; height:inherit; font-weight:inherit!important; font-size:inherit!important; line-height:inherit!important"> 
      <span style="margin:0px; padding:0px; border:0px; font-style:inherit; font-variant:inherit; font-weight:inherit!important; font-size:inherit!important; line-height:inherit!important; font-family:inherit; vertical-align:baseline; height:inherit; color:rgb(0,111,224)!important">/</span> 
      <span style="margin:0px; padding:0px; border:0px; font-style:inherit; font-variant:inherit; font-weight:inherit!important; font-size:inherit!important; line-height:inherit!important; font-family:inherit; vertical-align:baseline; height:inherit; color:rgb(0,45,122)!important">Teddy</span> 
      <span style="margin:0px; padding:0px; border:0px; font-style:inherit; font-variant:inherit; font-weight:inherit!important; font-size:inherit!important; line-height:inherit!important; font-family:inherit; vertical-align:baseline; height:inherit; color:rgb(0,111,224)!important">/</span> 
     </div> 
     <div style="margin:0px; padding:0px 5px; border:0px; font-style:inherit; font-variant:inherit; font-family:inherit; vertical-align:baseline; height:inherit; font-weight:inherit!important; font-size:inherit!important; line-height:inherit!important; background:rgb(247,247,247)!important"> 
      <span style="margin:0px; padding:0px; border:0px; font-style:inherit; font-variant:inherit; font-weight:inherit!important; font-size:inherit!important; line-height:inherit!important; font-family:inherit; vertical-align:baseline; height:inherit; color:rgb(0,111,224)!important">/</span> 
      <span style="margin:0px; padding:0px; border:0px; font-style:inherit; font-variant:inherit; font-weight:inherit!important; font-size:inherit!important; line-height:inherit!important; font-family:inherit; vertical-align:baseline; height:inherit; color:rgb(0,45,122)!important">daddy</span> 
      <span style="margin:0px; padding:0px; border:0px; font-style:inherit; font-variant:inherit; font-weight:inherit!important; font-size:inherit!important; line-height:inherit!important; font-family:inherit; vertical-align:baseline; height:inherit; color:rgb(0,111,224)!important">/</span> 
     </div> 
     <div style="margin:0px; padding:0px 5px; border:0px; font-style:inherit; font-variant:inherit; font-family:inherit; vertical-align:baseline; background:0px center; height:inherit; font-weight:inherit!important; font-size:inherit!important; line-height:inherit!important"> 
      <span style="margin:0px; padding:0px; border:0px; font-style:inherit; font-variant:inherit; font-weight:inherit!important; font-size:inherit!important; line-height:inherit!important; font-family:inherit; vertical-align:baseline; height:inherit; color:rgb(0,111,224)!important">/</span> 
      <span style="margin:0px; padding:0px; border:0px; font-style:inherit; font-variant:inherit; font-weight:inherit!important; font-size:inherit!important; line-height:inherit!important; font-family:inherit; vertical-align:baseline; height:inherit; color:rgb(0,45,122)!important">Hyperscan</span> 
      <span style="margin:0px; padding:0px; border:0px; font-style:inherit; font-variant:inherit; font-weight:inherit!important; font-size:inherit!important; line-height:inherit!important; font-family:inherit; vertical-align:baseline; height:inherit; color:rgb(0,111,224)!important">/</span> 
     </div> 
    </div> </td> 
  </tr> 
 </tbody> 
</table>

根据后3字节分为2组：组0 – “ddy”（0x64, 0x64, 0x79），组1 – “can”（0x63, 0x61, 0x6e）。  
再根据3字节中的6个4位构建出6个16字节掩码，初值全1，每个4位有16种可能取值，对应16字节掩码中的1字节，并在该对应字节的对应位（组）上贡献一个0。6个掩码依次对应最末字节低4位、高4位（绿色），倒数第二字节低4位、高4位（橙色），倒数第三字节低4位、高4位（蓝色）。为简化表达每字节只记录本例中两组对应的两位：  
![hyperscan_with_suricata_4.jpg][]  
运行时每次读取16字节输入数据，并以上述掩码用PSHUFB指令逐字节做映射。假设运行时读到输入数据为“TeddyinHyperscan”（54 65 64 64 79 69 6e 48 79 70 65 72 73 63 61 6e），则6次PSHUFB的结果为：  
![hyperscan_with_suricata_5.jpg][]  
结果中的”0”表示输入数据中每个位置（列）对规则集后3字节是否产生匹配。相同位置只有高4位和低4位均得到相同组的匹配，才是一个完整字节的匹配。对相同颜色的掩码做OR得到：  
![hyperscan_with_suricata_6.jpg][]  
对上述结果做“shift-or”，第一行不变，第二行做LSHIFT左移1字节，第三行做LSHIFT左移2字节，然后做OR得到：  
![hyperscan_with_suricata_7.jpg][]  
此为预过滤的结果，其中的”0”表示在该位置出现与某组连续后3字节的匹配，是可能产生真实匹配的位置（Positive）。我们对这些位置进行确认，最终找出与候选组中哪个字符串产生了真实匹配（True Positive），或者发现不是真实匹配（False Positive）。本例中在位置4对组0的“Teddy”、位置15对组1的“Hyperscan”产生真实匹配。  
同样的，对AVX2环境，我们只需把6个掩码均复制扩大一倍至32字节，且每次读取32字节输入数据；对AVX512环境，把掩码复制扩大至64字节，每次读取64字节输入数据。完成相同过滤目标的指令数也减少了很多。

## 性能数据 ##

测试环境：Intel® Core i7 6700K CPU @ 4.0 GHz  
软件版本：Hyperscan 4.3.1，Suricata 3.1  
规则集：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规则集上获得1.95x性能提升，在ET Pro规则集上获得2.15x性能提升。  
我们同样比较了单独替换多字符串AC算法及单独替换单字符串BM算法的性能，可见替换AC的性能要好于替换BM的性能，而二者性能又都介于原生和全部替换之间。各性能数据如下图所示。  
![hyperscan_with_suricata_8.jpg][]

这是可以预见的结果，因为对多模式匹配的良好支持正是Hyperscan的一大优势。

[hyperscan_with_suricata_0.jpg]: /images/20220609/3e5f8c9d774d43bdac3045fcb317cf67.png
[hyperscan_with_suricata_1.jpg]: /images/20220609/9b9924d82f9f401ba2e45f06e905a0b6.png
[hyperscan_with_suricata_2.jpg]: /images/20220609/67be78f248514b1c9fdc92c46343c6df.png
[hyperscan_with_suricata_3.jpg]: /images/20220609/ac35090263174dd5a567ff69ef9e2ecd.png
[hyperscan_with_suricata_4.jpg]: /images/20220609/33703e803ea34412991b63210c055249.png
[hyperscan_with_suricata_5.jpg]: /images/20220609/29e46e38f2a04dd9b83b4c2032f5584f.png
[hyperscan_with_suricata_6.jpg]: /images/20220609/b683590bd7714ef0b64674bdbe893d29.png
[hyperscan_with_suricata_7.jpg]: /images/20220609/811f65f588184de8981701d46ac56d29.png
[hyperscan_with_suricata_8.jpg]: /images/20220609/c4f79ab904a34ad78a603b09d2b19c2a.png