Sibuna 之书 1.0.0-beta.3 文档
语言: 简体中文
English简体中文한국어日本語EspañolDeutschहिन्दीالعربية
本页内容

第 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 比较一次,内层循环中不必再读取第二张表。

一棵字典树:从根经 G 和 GP 到达 GPTBot 匹配状态,经 C 和 Cl 到达 ClaudeBot 匹配状态;虚线表示的失败边从 GP 和 Cl 指回根。
图 9 两个签名的字典树状态和失败边

自动机的状态预算是一个运行时选项。策略引擎最多预留一个根加上所有签名长度之和,这是字典树状态数的一个安全上界。这样既避免了以往过大的固定表,又为每个字节类保留了稠密的转移。每个模式带有一个小的类别标记(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。评估顺序如下:

  1. 语义 WAF(仅 Shield):违规即为终止性的 deny。
  2. 信誉字典树:deny 或 allow 前缀是终止性的。
  3. 按顺序评估规则:第一个终止性匹配直接返回;WEIGH 匹配累加分数。
  4. 分数:总分为负时 allow;总分 \(\geq 40\) 时 deny;总分 \(\geq 10\) 时 challenge,超过阈值的部分每 5 分增加一个工作比特,最多增加六个。
  5. 静态绕过路径,然后是字典树的 challenge 判定,然后是机器人自动机。
  6. 默认动作,除非策略文件另有规定,否则为 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 稍后才执行。当源站连接空闲时,响应路径不必持有引擎快照。