Hyperscan在Suricata中的应用

Suricata简介

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

Hyperscan的应用

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

单字符串匹配

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

例如,对单条字符串规则/Hyperscan/的单模式匹配,取字符串前2字节做预过滤,构建2个16字节的掩码:

运行时每次读取16字节输入数据,用2次PCMPEQB指令与上述掩码做逐字节比较。假设运行时读到输入数据为“MATCHmyHyperscan”,则2次PCMPEQB的结果为(表中的1实际应为0xFF,为表达简便标记为1):

对上述结果做“shift-and”,即LSHIFT+AND指令,得到用2个字节做预过滤的结果:

预过滤结果中出现“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条字符串规则:

根据后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位(蓝色)。为简化表达每字节只记录本例中两组对应的两位:

运行时每次读取16字节输入数据,并以上述掩码用PSHUFB指令逐字节做映射。假设运行时读到输入数据为“TeddyinHyperscan”(54 65 64 64 79 69 6e 48 79 70 65 72 73 63 61 6e),则6次PSHUFB的结果为:

结果中的”0”表示输入数据中每个位置(列)对规则集后3字节是否产生匹配。相同位置只有高4位和低4位均得到相同组的匹配,才是一个完整字节的匹配。对相同颜色的掩码做OR得到:

对上述结果做“shift-or”,第一行不变,第二行做LSHIFT左移1字节,第三行做LSHIFT左移2字节,然后做OR得到:

此为预过滤的结果,其中的”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的一大优势。

原文:DPDK开源社区

发表评论

电子邮件地址不会被公开。 必填项已用*标注