jsongrep如何防御查询爆炸:有界DFA编译与查询引擎安全设计剖析
jsongrep如何防御查询爆炸:有界DFA编译与查询引擎安全设计剖析
jsongrep 是一个面向 JSON、YAML、TOML 等序列化格式的路径查询工具(命令行程序 jg + Rust 库)。它的查询语言本质上是一个正则表达式作用于文档路径:查询先编译成 NFA,再经子集构造(subset construction)确定化为 DFA 来执行。而子集构造在最坏情况下会指数级膨胀——一条很短的"恶意"查询就可能让编译过程消耗无界的时间与内存。本文剖析 jsongrep 如何用"有界 DFA 编译 + 状态预算 + 属性测试"三层设计防御这种查询爆炸(query explosion),以及这套思路对构建任何"把用户输入编译成自动机"的系统有什么借鉴意义。
先认识 jsongrep:正则路径查询语言
对新手来说,jsongrep 的用法非常直观:查询就是"路径上的正则表达式"。
几个典型查询,熟悉正则的话会立刻上手(语法详见 README.md 的 Query Syntax 一节):
| 查询 | 含义 |
|---|---|
**.name |
任意深度的 name 字段(Kleene 星) |
users[*].email |
数组通配:所有用户邮箱 |
(error|warn).* |
析取:error 或 warn 下的任意字段 |
(* | [*])*.foo |
同时穿过对象和数组,任意深度找 foo |
关键区别在于执行模型:jq 这类工具描述"如何变换数据",而 jsongrep 描述"要匹配哪些路径",查询先编译成 DFA,再对整个文档做确定性遍历。这意味着安全性问题主要发生在编译期——文档再大,执行期也只是沿着固定状态机走一遍,成本与文档大小线性相关。
为什么会出现"查询爆炸"?
编译流水线分三步(实现见 src/query/dfa.rs 模块头注释与 src/query/nfa.rs):
- 符号提取:从查询 AST 中收集字段名、索引、区间,构造有限字母表;
- NFA 构造:用 Glushkov 构造法把查询转成无 ε 转移的 NFA(状态数与查询长度成线性关系,这一步是安全的);
- 确定化:子集构造把 NFA 转成 DFA——DFA 的一个状态 = NFA 的一组状态,其数量在最坏情况下随查询长度指数增长。
经典的爆炸样本长这样:
(a|b)*.a.(a|b).(a|b)...(a|b) # 每多一个 (a|b) 尾巴,状态数翻倍
源码里的测试用例(src/query/dfa.rs)给出了精确数字:8 个 (a|b) 尾巴的查询会确定化出 513 个状态;如果再来 20 个尾巴,就是 2^29 级别——一条几十字符的字符串就能把进程内存吃光。这就是"查询爆炸",性质上等价于正则引擎里臭名昭著的 ReDoS,只是发生在编译期而非执行期。
对 CLI 用户这不算大事(你自己写查询),但对两类场景是真实的攻击面:
- 网络服务把查询字符串透传给
jsongrep库编译; - 浏览器 Playground(WASM 构建)在浏览器主线程上运行任意用户输入的查询。
核心防线:有界 DFA 编译与状态预算
jsongrep 的解法很直接:给确定化过程设一个状态预算,超预算立即干净地报错,而不是硬算。相关 API 都在 src/query/dfa.rs:
| API | 用途 |
|---|---|
QueryDFA::from_query_bounded(query, max_states) |
带预算编译 AST,超预算返回 StateLimitExceeded |
QueryDFA::from_query_str_bounded(str, max_states) |
字符串一步到 DFA,"不可信查询字符串的安全入口" |
QueryDFA::from_query_bounded_ignore_case(...) |
大小写不敏感变体 |
QueryCompileError |
统一错误类型:Parse(_) 或 StateLimit(_) |
超预算时用户看到的错误信息是明确且可行动的(src/query/dfa.rs):
query is too complex: DFA construction would exceed 262144 states;
simplify repetitions/alternations in the query
实现上,预算检查就嵌在子集构造的工作队列循环里:每创建一个新 DFA 状态前先比较计数器,new_dfa_state >= max_states 立刻返回错误(src/query/dfa.rs)。几个值得注意的工程细节:
- 预算语义精确:预算
n表示"最多允许 n 个状态",源码测试验证了边界行为——513 状态的查询在预算 513 下成功、512 下失败(src/query/dfa.rs);预算为 0 恒失败(空查询也至少有一个起始状态); - 预算之外仍有限:确定化是超线性的,但符号提取、区间离散化、NFA 构造都是查询长度的多项式,因此文档建议调用方同时限制查询字符串长度,双保险;
- 有界与无界等价:在预算内的查询,有界编译结果与无界版本行为完全一致(有专门测试保证),也就是说安全防线不影响正常查询——现实查询通常只需要几十个状态,离预算还差几个数量级。
产品层默认值:jg 用 2^18,Playground 用 2^16
API 只是能力,默认值才构成安全。jsongrep 在两个入口各自选了合适的预算:
命令行 jg(src/main.rs):
const DEFAULT_MAX_DFA_STATES: usize = 1 << 18; // 262144 个状态
注释把取舍写得很清楚:2^18 让最坏情况的编译在约 1 秒内中止(而不是无界烧资源),同时又比任何现实查询所需的"几十个状态"高出好几个数量级,不会误伤正常用户。
WASM Playground(playground/wasm/src/lib.rs)把预算收紧到 2^16,原因是浏览器场景更脆弱:查询在浏览器主线程上编译,指数爆炸不会拖垮服务器,但会直接冻死用户标签页:
let dfa = QueryDFA::from_query_str_bounded(query, 1 << 16)
.map_err(|e| e.to_string())?;
两个数字的差(2^18 vs 2^16)恰好体现了一个原则:状态预算应该按部署环境的风险与代价来定,而不是一个"看起来够大"的常数。这一整套变更在 CHANGELOG.md 中有明确记录("Bounded DFA compilation for untrusted queries" 一节)。
纵深防御的其他组成部分
有界编译不是孤军奋战,整个查询引擎的"拒绝坏输入"体系还包括:
1. 解析层:坏语法干净报错,未实现功能显式拒绝
查询文法由 pest 定义(src/query/grammar/query.pest)。解析失败走 QueryParseError;曾经 /regex/ 语法能解析通过却在 DFA 构造期 panic,现在解析器直接以 UnsupportedFeature 拒绝,从 CLI、库、WASM 三个入口都拿不到 panic 路径(见 CHANGELOG.md Fixed 一节)。
2. 属性测试:用随机输入守住整个输入空间
test 文件用 proptest 做属性测试:每次运行生成数百个随机查询字符串(偏向 DSL 字母表 a b . | * ? [ ] ( ) : " / 以提高覆盖深度),验证三条性质——
- 任意输入解析永不 panic;
- 每个解析成功的查询都能编译成 DFA 且不 panic;
Query的 Display 输出可以再次解析并收敛到不动点(防止显示/重解析漂移出语义)。
这类测试的价值在于:单元测试覆盖你想到的输入,属性测试覆盖你没想到的输入——而安全缺陷恰恰藏在后者里。
3. 执行期同样有界
即便编译通过,执行侧也提供了 find_limited(找到 N 个匹配即停)和 for_each_match(可提前 Break 的流式遍历),CLI 侧对应 -m/--max-count 参数——大文档上"存在性检查"只付出到第一个匹配为止的工作量(src/query/dfa.rs)。
安全与性能是同一件事
这套设计还带来一个附带收益:可预期的最坏耗时本身就是性能承诺。jsongrep 用 Criterion 对 190 MB GeoJSON 等真实数据做了端到端基准测试,对比 jaq、jql、jmespath、jsonpath-rust 等工具(方法论见 benches/README.md):
从图中可以看到,在多数查询类型上 jsongrep(尤其 jsongrep 与 jsonpath_rust 组)耗时集中在最低区间。"编译有界 + 执行线性"的组合,意味着它的延迟上界是可证明的:编译 ≤ 预算成本,执行 ∝ 文档规模。这对把它嵌入服务链路的用户是重要的工程属性。
在自己的项目里应用这套模式
如果你的系统也有"把用户输入编译成自动机/解释器"的环节(正则、模板、DSL、查询语言),jsongrep 给出的清单可以直接照抄:
- 识别爆炸点:确定化、展开、递归下降求值——哪一步最坏情况超线性?
- 设预算并在循环体内检查:在构造过程的每次"扩张"处计数,超限返回专门的错误类型(如
StateLimitExceeded),而不是超时杀进程; - 按环境差异化默认值:CLI 2^18、浏览器 2^16 的差异说明预算应与故障代价挂钩;
- 错误信息要可行动:告诉用户"查询太复杂,请简化重复/交替",而不是一句 opaque 的失败;
- 用属性测试守住边界:随机输入 + "永不 panic" 性质,比逐条手写用例更能兜底;
- 限制输入长度作为第二道闸:预算约束的是编译产物,字符串长度约束的是编译输入,两者独立且都便宜。
小结
jsongrep 对查询爆炸的防御可以概括为三句话:编译期用状态预算把指数最坏情况截断成干净错误;部署层按环境给出差异化的默认预算;测试层用属性测试保证"坏输入永远拿不到 panic"。 源码入口推荐从这里读起:src/query/dfa.rs(有界编译与 QueryDFA)、src/query/nfa.rs(Glushkov 构造)、src/main.rs(CLI 预算常量)、playground/wasm/src/lib.rs(WASM 预算)、tests/properties.rs(属性测试)。对新手而言,它也是一个很好的范本:安全设计不必是事后补丁,而是从 API 命名(from_query_bounded 与 from_query 并列存在并明确标注取舍)到默认值的一体化表达。

