Hyperscan

Hyperscan是Intel开发并开源的高性能正则表达式匹配库，利用x86向量指令做了极致优化。华为基于鲲鹏平台做了arm指令集适配和优化，并针对实际数据分流业务规则集的弱点做了算法革新（例如短规则旁路混合模型）。

Hyperscan的工作流程有两个主要时期：编译期和运行期。编译期将一条或者一组规则编译成一个只读数据库；运行期不需要读入规则，而是借助编译好的数据库进行匹配。

存在短规则的规则集会导致Hyperscan规则匹配陷入性能瓶颈。研究表明，Suricata开源规则集里表现最差的子集，去除八条单字节规则后，整体匹配性能上升50%，原因主要是短规则参与了太多不必要的向量计算和精确校验。最近版本交付的短规则旁路混合模型将规则集里的短规则用TBL查表指令优化的高速旁路算法绕过主算法流程，用20%的额外开销处理短规则，最终能够取得整体30%+的性能提升。

高速的短规则旁路shuf-and算法是混合模型高效处理规则集里短规则瓶颈的关键。

考虑一个含有8条1字节规则的集合的实例，用以描述短规则旁路shuf-and算法。假设8条短规则分别是{A, B, C, D, c, d, e, f}，先给每条规则分配一个组，分别用不同的位来表达，则规则的组ID分别为{0x1, 0x2, 0x4, 0x8, 0x10, 0x20, 0x40, 0x80}。将整个ASCII表表达为16x16的形式，高4位值相同的字符位于同一行，低4位值相同的字符位于同一列。再向每个规则对应的表项内填入其组ID，如下图所示。

将表内每行的数值按位或，得到上图中第二列所示向量，记为maskHigh；将每列的数值按位或，得到上图中第二行所示向量，记为maskLow。则maskLow和maskHigh如下图所示。

做好上述准备后，在后续匹配过程中，maskLow和maskHigh作为混洗操作的源向量参与运算，而待匹配数据作为控制向量参与运算。

假设待匹配数据中一个16字节数据块为“AgggDd3366666666”，只需要5条指令，即可得到其中所有位置的匹配结果。首先将数据块中每字节的低4位和高4位分别表达为两个控制向量，这需要一个AND操作擦除每字节高4位内容，和一个SHIFT操作将每字节高4位内容移到低4位上。得到两个向量inputLow和inputHigh。

然后做两次混洗操作，得到结果shufLow和shufHigh如下。

将shufLow和shufHigh做AND，得到的就是每个位置的匹配结果。

可以清晰的看出，在偏移量0、4、5分别匹配上了组0x01(A)、组0x08(D)、组0x20(d)。

Hyperscan在十万以下常规数量规则集匹配场景是世界最快，被广泛应用于应用分类、IDP、WAF（Web Application Firewall）等场景。在以Suricata为代表的典型开源方案中，其检测引擎为第一计算热点，集成和优化Hyperscan可有效提升数据分流业务端到端性能。

Hyperscan的关键技术包括：高速预过滤算法；多模式匹配算法；自动机算法。

Hyperscan的适用场景包括：网络安全数据分流，运营商数据精细分流，公安、技侦数据分流，IDP，WAF，大模型应用防火墙等。