Hyperscan是Intel联合相关单位开发的一套开源的C++高性能多模式正则匹配库，其实现大量的利用了现代CPU中的SIMD（单指令多数据流）指令来进行优化，通常被用于实现IDS/IPS系统中的DPI模块（例如Snort）。Hyperscan项目是经历了数年的长期开发，其核心技术被发表于NSDI‘19。本文将着重介绍Hyperscan中的SIMD多模字符串匹配算法。
在Hyperscan文中，该SIMD多模字符串匹配算法被称为FDR（纪念罗斯福…)，FDR旨在快速筛选出不需要进行详细匹配的字节流。具体而言，FDR改进了经典的Shift-or匹配算法，将其从单模式串精确匹配拓展到了多模式串模糊匹配（有概率出现假阳性FP），并利用了一系列的SIMD指令，对其性能进行了优化，在改进的Shift-or算法之后，FDR引入了一个验证模块，利用哈希和精确字符串匹配来过滤上一步中可能出现的FP。本文将首先介绍经典的Shift-or匹配算法，然后介绍FDR中的改进的多模Shift-or算法，并对其细节进行一系列的分析，最终介绍验证模块的相关内容。
经典的Shift-or字符串匹配算法
最常见的字符串匹配算法，也既暴力匹配，在遇到匹配失败的字符之后，会重新将模式串退回起始位置，然后将原文前进一个字符再次进行匹配，该操作符合人们的直觉，但会花费一些不必要的时间去匹配一些在前次匹配中已知可以匹配的子串。KMP算法引入了失配指针与next数组的概念，通过计算并存储模式串中部分子串的前缀与后缀的最长公共元素的长度，来缩减失配时所需要的回退的步数，从而减少算法运行的时间。KMP算法的详细过程本文不再赘述，有兴趣的读者可以在互联网上查阅相关资料。
Shift-and算法
在介绍Shift-or算法之前，我们先来介绍Shift-and算法，因为Shift-or算法仅为Shift-and算法的一个优化方案。Shift-and算法，其思想与KMP算法略有相似，都利用了前缀与后缀的关系，但Shift算法通过计算机中并行度较高的位运算，进一步加快了匹配的速度。给定模式串P，输入文本为S，Shift-and算法维护一个字符串集合D，D中记录了P中所有与S串当前已读部分的某个后缀相匹配的P的从头开始的子串，每当从S中读入一个新字符后，算法立即更新D，若D中存在一个串恰好为P，则表示匹配成功。实际应用中，维护一个位数组D来实现这一功能，现将具体流程总结如下：
1. 设P的长度为m，将位数组D表示为D=dm...d1，用D[j]表示dj，初始化D全为0;
2. D[j]=1，当且仅当P1...Pj是S1...Si的某个后缀（此时，S读到i处）；
3. 若D[m]=1，则S匹配P；
4. D的更新规则：当且仅当D[i]=1且Si+1=Pj+1时，D[i+1]=1。
在具体实现中，我们采用如下算式去对D进行位并行更新：D=((D<<1) | 1) & B[S[j]]，其中B为一个位数组的数组，对所有的P中的字符c，B维护如下特性：B[c].i也既B[c]的第i位为1，当且仅当P[i]=c，否则为0。在给出B的定义之后，接下来我会对更新算式进行详细的解释：
- 首先关注更新规则，当且仅当
D[i]=1且Si+1=Pj+1时，D[i+1]=1。对于位数组D，其每一位表示模式串P从开头到该位对应的位置有无对应的匹配，因此，在已知当前位置的匹配情况D[i]，并想要进行上述更新操作时，很显然，我们可以发现D[i]与D[i+1]存在一个左移一位的关系。在更新过程中，D[i]的可能取值为0和1，若D[i]=0，则代表第i位不匹配，根据规则，第i+1位也不可能匹配，此时D[i+1]也应被置为0，该操作可以用一个左移操作被轻松的表示出来，也既更新算式中的D<<1； - 若
D[i\=1，则表示D[i+1]有机会为1，因此我们需要进行进一步的判断（Si+1=Pj+1是否成立？），在进行这个判断之前，假设该判断成立，该假设等价于对D进行左移操作，让D[i]=1这一位被传递到D[i+1]，注意此时前一位会被补0，因此我们对传递之后的D与上1，也既((D<<1) | 1)，从而保证每次传递都能使前序匹配信息不丢失。接下来，我们需要对假设（Si+1=Pj+1成立）进行验证，在这里，借助之前已经计算好的B，如果B[S[j]]的第i+1位为1，则证明假设成立，因此之前接受到上一位传递的1应被保留，反之，则应置为0，这一操作符合与操作的概念，因此，我们用D=((D<<1) | 1) & B[S[j]]来实现这一更新。
优点：位数组的每一位都可以表示一个字符，且位运算在CPU内是高度并行化的，所以，相较于KMP算法，该算法更加高效。现将C++实现贴至下方：
// implementation by bitset
int shift_and_bitset(std::string source, std::string pattern)
{
size_t src_len = source.length(), pat_len = pattern.length();
// assume character set is A-Za-z, 52 chars
std::bitset<64> B[52]; // pat_len should less than or equal to 64
std::bitset<64> D; // the bitset representing the prefix-matching status, initialized as 0x00...
// initialization of B
for (size_t i = 0; i < pat_len; i++)
{
// set the i-bit of B[pattern[i]] as 1
B[pattern[i] - 'A'].set(i, true);
}
for (size_t i = 0; i < src_len; i++)
{
D = (D << 1).set(0, 1) & B[source[i] - 'A'];
if (D[pat_len - 1])
{
return i;
}
}
// return D[pat_len - 1];
return -1;
}
// implementation by pure bitwise calculation
int shift_and_bitwise(std::string source, std::string pattern)
{
size_t src_len = source.length(), pat_len = pattern.length();
unsigned long long mask = 1 << (pat_len - 1);
unsigned long long B[52] = {0};
unsigned long long D = 0;
// initialization of B
for (size_t i = 0; i < pat_len; i++)
{
// set the i-bit of B[pattern[i]] as 1
B[pattern[i] - 'A'] |= (1 << i);
}
for (size_t i = 0; i < src_len; i++)
{
D = (((D << 1)) | 1) & B[source[i] - 'A'];
if (D & (1 << (pat_len - 1)))
{
return i;
}
}
return -1;
}
相较于利用STL中的bitset实现，利用整型变量和位运算的实现更加高效，但是可读性有所降低。
Shift-or算法
Shift-or算法是Shift-and算法的一个优化，仔细思考之下，我们会注意到，在Shift-and算法中，因为逻辑左移默认最低位补0，因此，每次更新都需要进行一次或1的操作来保证最低位的信息不丢失。那么，一个很自然的想法即为：可否用0来表示匹配，用1表示失配？这样即可在每次更新中，省去一次或操作的时间，从而进一步优化算法。事实上，这就是Shift-or算法的由来，相应地，B和D的初始化也要做些修改，既B的每一项除了相应存在字符的位置为0，其余全部置为1；D全部置为1。更新算式也应相应地更改为D=(D<<1) | B[S[j]]。现将C++实现贴至下方：
// an improvement of shift-and, using 0 to indicate a match and 1 to indicate an unmatch
// hence, 1 and 0 in every bitvectors should be swapped, and hence the (OR 0x01) operation is no more required
int shift_or_bitwise(std::string source, std::string pattern)
{
size_t src_len = source.length(), pat_len = pattern.length();
unsigned long long mask = ~(1 << (pat_len - 1));
unsigned long long B[52];
memset(B, ~0, sizeof(unsigned long long) * 52);
unsigned long long D = ~0; // 111..111
// initialization of B
for (size_t i = 0; i < pat_len; i++)
{
// set the i-bit of B[pattern[i]] as 0
B[pattern[i] - 'A'] &= ~(1 << i);
}
for (size_t i = 0; i < src_len; i++)
{
D = (((D << 1))) | B[source[i] - 'A'];
if (!((D >> (pat_len - 1)) & 1))
{
return i;
}
}
return -1;
}
// shift-or implementation by bitset
int shift_or_bitset(std::string source, std::string pattern)
{
size_t src_len = source.length(), pat_len = pattern.length();
// assume character set is A-Za-z, 52 chars
std::bitset<64> B[52]; // pat_len should less than or equal to 64
std::bitset<64> D = std::move(std::bitset<64>{}.set()); // the bitset representing the prefix-matching status, initialized as 0x00...
for (size_t i = 0; i < 52; i++)
{
B[i].set(); // set all to 1
}
// initialization of B
for (size_t i = 0; i < pat_len; i++)
{
// set the i-bit of B[pattern[i]] as 1
B[pattern[i] - 'A'].set(i, false);
}
for (size_t i = 0; i < src_len; i++)
{
D = (D << 1) | B[source[i] - 'A'];
if (!D[pat_len - 1])
{
return i;
}
}
return -1;
}
多模Shift-or匹配算法
诚然，上文中介绍的经典的Shift-or算法具有高效和空间利用率高等的优点，但以下两点限制了我们在Hyperscan中直接使用该算法：1. 经典Shift-or算法只支持单模式串匹配；2. 尽管其大多数操作都由位运算组成，但在模式串长度有限的情况下（大多数情况如此），其实现也无法从SIMD指令中受益。因此，Hyperscan对经典的Shift-or算法进行了一些改进，并据此提出了多模Shift-or匹配算法（Multi-string shift-or matching，MSSM）。本节将对该算法的思想和细节做详细阐述。
数据结构设计
为了支持多模式串匹配，一个符合直觉的想法即是提取不同模式的公共信息，但如何定义所谓“公共信息”决定了匹配的效率与精度。如果公共信息无法完全表示所有模式串，则该算法会退化为一个模糊匹配算法，事实上，这也是FDR的思路之一，即是先利用精度较低（但保证没有假阴性FN）的模糊匹配算法筛选出部分串，再将这些串输出下一处理模块进行精确匹配。因此，出于效率和精度的共同考虑，在MSSM中，一系列模式串通过“模式分组”模块被划分至n个bucket内（id：0 - n-1），然后，将经典Shift-or算法中的D（MSSM中称为st-mask）和B（MSSM中称为sh-mask）的长度扩大n倍（n的典型值为8，即一个字节的长）。举例说明，假设原本sh-mask(‘x’)长度为l，此时，sh-mask中会有l个长为n的位数组，其中第i个长为n的位数组的第j位记录了’x’在bucket-j的所有模式的第i位有没有出现，若出现则为0，否则为1。与经典算法的一个不同之处在于，模式串的字节位置也是从最右侧开始数起的（例：abcd，d为第一位，c为第二位…类似二进制串0b00000001，第一位是1），这使得基于SIMD指令的优化成为了可能（保证了字节序和字符串序相同，从而让移位操作可以被预计算，后续小节会提到）。具体例子可以参照原文中图8。
匹配过程
MSSM的匹配过程与经典算法较为相似，但不同之处在于，在MSSM中，我们需要对sh-mask而非经典算法中的st-mask进行左移。详细的匹配过程见下文：
- 按照上文中所述初始化各个sh-mask；
- 初始化st-mask，具体地，对所有位置大于等于最小模式串长的字节置0，否则置1。例如，若最小模式串长为2，则任意字符的st-mask的第一个字节都应被置为全1。小于最小模式串长的位置，必然无法匹配bucket中的任意串，因此，该操作可以避免在这些位置进行匹配的FP。
- 预左移操作。将计算好的对于输入串的sh-mask按照其字符位置分别进行左移，假设当前字符从左往右数为第i个，则左移偏移量应为(i - 1) * 8。例如，若输入为“aphp”，则有sh-mask(“a”),sh-mask(“p”) « 8, sh-mask(“h”) « 16, sh-mask(“p”) « 24。由于sh-mask中的第i个字节中的每一位表示对应buckets中的模式串们的第i位是否包含当前字符，并且上文中提到“模式串的字节位置也是从最右侧开始数起的”，这保证了左移可以使匹配前进。例如“a”在输入串中为从左往右第一个，从右往左第四个，对“h”在输入串中为从左往右第三个，从左往右第二个，其恰好左移(3 - 1) = 2字节，保证所有进行或操作的有意义的二进制串都一一对齐，并且相互之间没有数据依赖。这种破坏数据依赖的操作，可以增加程序的并行度，直接进行几个串的或即可而无需等待上一步的计算结果再去进行下一步计算。
- 计算完或操作之后，若结果之中有0，则代表有可能匹配的结果，详见原文图9。
False Positive的处理——超级字符
MSSE数据结构所进行的操作，可以被看做一个bucket尺度上的，对其内的模式串进行压缩的操作。该压缩会将部分模式串的信息丢失，进而导致精度损失。具体地，如原文图8所示，bucket中存储的模式串为“ab”与“cd“，但”a“与”c”，“b”与“d”的sh-mask都分别相同。因此，若输入串为“cb”或“ad”，同样会匹配。值得注意的是，短的模式串会引发更高的FP率，因为短串的mask的可用位数会远远少于长串，这将导致mask可承载的信息量下降，从而引发FP率上升的灾难。因此，为了降低FP率，MSSM对常见的8-bit字符进行了改进，引入了一种“超级字符”（super characters，SC）。每一个SC都占m位，其中0到7位是字符本身的ASCII码，8到m-1位为其串中下一个字符的前m-8位的拷贝，如果无下一个字符，则全为0。这种字符携带了部分下一字符的信息，从而在建立和索引sh-mask时，利用前后字符的关系协助其减少FP的出现。
模式分组模块（不是很重要，Pigasus中并未采用）
模式分组模块的设计会影响到MSSE的性能，一个好的分组策略会让绝大多数的正常数据流以一个很低的FP率通过MSSE。模式分组模块的设计基于以下两点：
- 将长度相似的模式串分入一组中，这是因为MSSE只能匹配到长度最短的串们（若可以匹配更长的会导致padding位溢出，导致false negative的出现）；
- 避免一组中有过多过短的模式串。 根据上述要求，我们将模式串们按长度递增顺序排列，并对其按顺序分配id为0到s-1，然后根据文中所属动态规划的状态转移方程计算出最优划分。
验证模块
尽管MSSE采取了许多措施来降低FP率，但始终无法避免，因此，对于输出的潜在的待匹配串，我们需要验证它的真实性。具体地，对每个bucket我们单独建立一个哈希表，该哈希表中存有对应字节位置所可能匹配的模式串们。对所有的模式串，我们用待匹配串与其进行精确匹配来确定最终结果。