第 VI 部分:自动机、字典树与语义防火墙¶
我们考察亚微秒级分类背后的算法:带标记的 Aho-Corasick 自动机,IPv4/IPv6 基数字典树,语义 WAF 的字节类分词器,以及带 WEIGH 评分的声明式策略引擎。
单遍多模式匹配¶
作为稠密 DFA 的 Aho-Corasick¶
Sibuna 有两个字面量模式集合:大约四十个机器人签名和大约一百个攻击签名。逐个地把一个字段与 \(N\) 个模式比较,复杂度为 \(O(NM)\);Aho 和 Corasick(1975)的自动机在构建带失败链接的字典树之后,只需以 \(O(M)\) 扫描一遍。Sibuna 在构建时把失败链接折叠进转移表,因此扫描时每个输入字节只需一次表读取,不需要针对模式集合进行分支。自动机位于 sibuna-patterns crate 中:
/// 从 `state`(一个行偏移量)出发,读入 `byte` 后前进一步。
fn step(&self, state: usize, byte: u8) -> usize {
self.table[state + usize::from(self.classes[usize::from(byte)])] as usize
}
pub fn find_first(&self, haystack: &[u8]) -> Option<Match> {
let mut state = 0;
for (index, &byte) in haystack.iter().enumerate() {
state = self.step(state, byte);
if state >= self.first_match {
let id = self.first_output_in(self.match_state(state), self.all_tags)?;
return Some(self.report(id, index + 1));
}
}
None
}
状态以它在一张扁平表中的行偏移量存储,因此一步只是一次加法和一次读取。状态的编号使每个匹配状态都排在所有其他状态之后;于是检测匹配只需与 first_match 比较一次,内层循环中不必再读取第二张表。
自动机的状态预算是一个运行时选项。策略引擎最多预留一个根加上所有签名长度之和,这是字典树状态数的一个安全上界。这样既避免了以往过大的固定表,又为每个字节类保留了稠密的转移。每个模式带有一个小的类别标记(0 到 63,因此一组标记就是一个 64 位字)。大小写折叠使用一张随自动机一起构建的 256 项字节类表:一个字母的大小写形式共用一个类,所有不出现在任何模式中的字节共用一个类,因此表的一行的宽度等于不同模式字节的数量加一,而不是 256。确切的引擎大小,以及与顺序子串搜索的比较,记录在第 VIII 部分中。后者使用相同的模式和“任一匹配”语义。
正则表达式、SIMD 引擎与最终选择¶
为签名阶段权衡过三类方案:
- 回溯式正则表达式(回溯规则集的风格)每个请求要运行数百个模式,每次匹配都要分配内存;它们是最慢的选项,也最容易产生误报。
- SIMD 字面量引擎(Hyperscan、Vectorscan)用基于 shuffle 的半字节掩码(“Teddy”算法)对 16 到 32 字节的数据块进行预过滤,再用自动机验证候选。它们擅长处理带有大型字面量集合的长输入。代价是一个数兆字节的 C++ 依赖、一个编译期的模式数据库、不支持 WebAssembly 目标,而且对于一百字节左右的输入没有优势:扫描整个字段的时间还不到一次缓存未命中。
- 稠密 Aho-Corasick 加小型结构分词器,即 libinjection 一脉的做法,在一张固定表中提供精确的线性时间行为,并且不需要可执行文件之外的任何东西。
Sibuna 的字段很短,因此第三类方案在内存和速度上都胜出;第 VIII 部分记录了 8 KiB 请求体上约每字节 1.56 ns 的成本(语义扫描耗时 12,784.3 ns,见 benchmarks/results/primitives-latest.md 中的 8kb_body_semantic_scan)。这是 SIMD 预过滤唯一可能值得的工作负载,SID 0006 把它列为一个待定事项。
IPv4 和 IPv6 的基数字典树¶
一棵基于 128 位键的二叉字典树同时服务两个地址族:IPv6 前缀按原样插入,IPv4 前缀被映射到 ::ffff:0:0/96 中,因此一个 /24 会成为深度为 120 的路径。节点存放在一个以 u32 为索引的扁平 Vec 中,索引零既表示根也表示“无子节点”,因此一次查找最多是 128 次相互依赖的读取,没有指针追逐。这棵字典树就是 sibuna-cidr crate 中的 PrefixTrie。
如果每次 IPv4 查找都走完映射前缀的 96 层,那么在到达 IPv4 地址的第一个比特之前,就要付出 96 次相互依赖的读取。因此,字典树在初始化时记录深度 96 处的节点,并从那里开始 IPv4 查找:
let (mut node, mut depth, mut best) = if is_ipv4_mapped(key) {
let start = self.ipv4_root;
let value = self.nodes[start as usize].value.as_ref();
(start, IPV4_DEPTH, value.or(self.nodes[0].value.as_ref()))
} else {
(0, 0, self.nodes[0].value.as_ref())
};
分类一个 IPv4 地址耗时 32.0 ns,一个 IPv6 地址耗时 79.3 ns(benchmarks/results/primitives-latest.md 中的 ipv4_cidr_classification 和 ipv6_cidr_classification)。引擎会查询字典树两次:在规则表之前查询终止性的 allow/deny 判定,使集群范围的封禁优先于每条规则;在规则表之后查询 challenge 判定。
语义防火墙¶
关于误报的一课¶
WAF 的第一个版本把一个扁平的子串列表与每个请求头进行匹配。列表中包含 /*,而每个浏览器都会发送 Accept: text/html,...,*/*;q=0.8。于是每个真实的浏览器都被分类为 SQL 注入,并收到 403。这一教训塑造了设计:检测器只能针对 结构 触发;测试套件现在会让一个完整的 Chrome 请求(包括一个含有 select、-- 和撇号的评论正文)通过引擎,并断言它被判定为干净。
单遍收集字节类¶
每个被检查的字段只扫描一遍,收集其中出现了哪些字节类:引号、=、<、shell 分隔符、%、NUL、规范化触发字节和连续空格。每个检测器都查询这些字节类,而不是重新扫描;只有出现了触发字节时,才运行规范化后的第二遍。扫描对每个字节查一次 256 项的表,代码来自 sibuna-policy 的 WAF 模块。四个累加器使 OR 链保持简短;只有当没有任何单个字节已经要求规范化时,才搜索两种字节对(/* 和两个相邻的空格):
pub(crate) fn scan(text: &[u8]) -> Classes {
let (chunks, remainder) = text.as_chunks::<8>();
// 四个累加器让 OR 链保持很短,使各次加载可以背靠背地发出。
let mut lanes = [0u16; 4];
for chunk in chunks {
lanes[0] |= TABLE[usize::from(chunk[0])] | TABLE[usize::from(chunk[4])];
lanes[1] |= TABLE[usize::from(chunk[1])] | TABLE[usize::from(chunk[5])];
lanes[2] |= TABLE[usize::from(chunk[2])] | TABLE[usize::from(chunk[6])];
lanes[3] |= TABLE[usize::from(chunk[3])] | TABLE[usize::from(chunk[7])];
}
let mut bits = lanes[0] | lanes[1] | lanes[2] | lanes[3];
for &byte in remainder {
bits |= TABLE[usize::from(byte)];
}
// 只有当还没有任何单个字节要求规范化时,这些字节对才有意义。
if bits & CANONICAL == 0
&& ((bits & SPACE != 0 && has_pair(text, b' ', b' '))
|| (bits & (SLASH | STAR) == SLASH | STAR && has_pair(text, b'/', b'*')))
{
bits |= CANONICAL;
}
Classes { bits }
}
检测器¶
- 签名。 所有类别的所有强签名都位于同一个带标记的自动机中;命中即为终止性的
deny,名称为waf:sqli、waf:xss、waf:path-traversal或waf:rce。 - SQL 注入。 一个单遍的单词扫描器在关键字表中查找每个字母数字单词(最多七个字节),遇到
or/and时检查是否存在literal = literal形式的恒真式;id=1 or 1=1是终止性的。否则必须出现引号字节,并且证据得分至少为 4,计分项为:引号(1),最多两个关键字(2),注释标记(1),一个=(1)。admin'--本身就是终止性的。“it's a group order from the shop” 得 3 分,可以通过。 - 跨站脚本。 要求出现
<;当一个可以承载脚本的标签与处于属性位置的on<event>=属性同时出现时触发。onboarding=1不算。 - 命令注入。 要求出现分隔符;当
;、|、&&、$(、反引号或换行后面跟着一个已知的命令名时触发。status ok; done | next可以通过。 - 路径遍历。 签名(
../、..%2f、/etc/passwd、id_rsa等),外加 NUL 和%00。
语法中合法地包含引号和星号的结构性请求头(Accept*、Content-Type、Sec-*、If-* 等)会被跳过;路径、查询、User-Agent、其他请求头以及请求体的前 8 KB 会被检查。含有百分号转义、加号、注释起始符或可折叠空白的字段,会被规范化到一个 8 KB 的栈缓冲区中再检查一次,因此 1%27/**/UnIoN/**/SeLeCt 和 %252e%252e/ 都会归结为原始签名。
成本¶
检查成本取决于提交给引擎的字段和字节,而不仅仅是请求的数量。基准测试一章分别报告了 Gate、Shield 和 8 KB 请求体的情形。8 KB 的上界是一个检查限制,并不意味着上传内容的其余部分是安全的。使用 forward-auth 的入口代理必须传递相关的请求信息;被省略的字节无法由这个进程检查。
声明式策略引擎¶
一条规则是若干可选条件的合取(路径模式、User-Agent 模式、最多四个请求头、最多八个 IPv4/IPv6 CIDR 块、一个 JA4 指纹或前缀),带有一个动作 ALLOW、DENY、CHALLENGE 或 WEIGH,可选的按规则设定的难度(以工作比特计)和算法,以及一个有符号的 weight。评估顺序如下:
- 语义 WAF(仅 Shield):违规即为终止性的
deny。 - 信誉字典树:
deny或allow前缀是终止性的。 - 按顺序评估规则:第一个终止性匹配直接返回;
WEIGH匹配累加分数。 - 分数:总分为负时
allow;总分 \(\geq 40\) 时deny;总分 \(\geq 10\) 时challenge,超过阈值的部分每 5 分增加一个工作比特,最多增加六个。 - 静态绕过路径,然后是字典树的
challenge判定,然后是机器人自动机。 - 默认动作,除非策略文件另有规定,否则为
challenge。
内置规则放行 /.well-known/*、/favicon.ico、/robots.txt 和 /__sibuna/*,拒绝 CF-Worker 客户端和 Amazonbot,并对每个 Mozilla User-Agent 发起挑战:浏览器字符串可以随意伪造,准入它会让网关形同虚设。
{
"default_action": "CHALLENGE",
"waf": true,
"thresholds": { "challenge_at": 10, "deny_at": 40, "bits_step": 5 },
"ip_rules": { "10.0.0.0/8": "ALLOW", "2001:db8::/32": "DENY" },
"rules": [
{ "name": "internal-api", "path": "/api/*", "headers": { "X-Api-Key": ".*" },
"action": "ALLOW" },
{ "name": "checkout", "path": "/checkout/*", "action": "CHALLENGE",
"challenge": { "difficulty": 20, "algorithm": "posw" } },
{ "name": "headless", "user_agent": "Headless", "action": "WEIGH", "weight": 30 },
{ "name": "no-language", "headers": { "Accept-Language": "" },
"action": "WEIGH", "weight": -5 }
]
}
逐步追踪:持有有效会话的编码攻击¶
考虑一个持有有效会话的客户端发出的 GET /search?q=%2527%2520OR%25201%253D1。首先,HTTP 解析器在不复制字节的情况下分离路径和查询。接着执行本地限制,然后由 Shield 检查请求。百分号把该字段标记为需要规范化。第一遍解码得到 %27%20OR%201%3D1;第二遍得到 ' OR 1=1。
此时分词器看到一个引号、关键字 OR 和相等的字面量操作数。拒绝是终止性的策略结果。有效会话不会把它变成放行:会话检查只用于解决挑战决定。存储钩子复制一条有界的事件记录;SQL 稍后才执行。当源站连接空闲时,响应路径不必持有引擎快照。