正在刊行长文 · Essay
2026-08-30所有内容
随机比特 · Random Bits

5120 字节的崩溃输入,自动缩到只剩 3 个字符

2026-08-30AI Engineering / Systemsrbits.uk
5120 字节的崩溃输入,自动缩到只剩 3 个字符

本地缩减收据的起点是 5120 字节,终点是 ASCII BUG,只有 3 字节。它仍会产生原来的 SIGABRT,并输出精确标记 CRASH_ID=BUG-42。严格缩减过程评估并缓存了 62 个唯一候选,其中 22 次删除被接受。

这不是未知漏洞被自动定位。原输入是人工构造的 5 KiB 教学夹具,BUG 是预先放入的崩溃触发串;字符 X 单独出现时,只会产生退出码 2 的校验错误。实验要验证的不是缩减比例,而是失败身份如何决定最终答案。

失败判定决定删除结果

ddmin 可以理解为反复撕掉输入的一块,再按下同一个测试按钮。这次本地循环采用开放书稿代码所展示的补集删除形式。它遍历当前粒度的各个补集,候选删除后仍被判为目标 FAIL,才保留这次缩减;该粒度没有任何补集仍为 FAIL 时,才提高粒度继续尝试。相同候选会被缓存,避免重复执行。

这里的按钮就是 oracle,也就是失败判定器。它不能只回答成功或失败,还要保留第三种 UNRESOLVED。不同崩溃、超时、非法候选或基础设施异常都不应冒充原故障。本地循环还显式要求空输入为 PASS、原输入为 FAIL

62 是严格缩减过程实际评估并缓存的唯一候选数,不是 62 个下降步骤,也不包含终点后的逐字节检查。一次删除被接受,只证明删除后的候选仍会产生 BUG 严格失败。要到终点再对 BUG 逐字节复核,才能得到一最小结论,而两者都不能证明被删部分与故障根因无关。

缓存还隐含一个前提,即同一候选必须稳定地得到同一结果。如果崩溃受随机种子、并发时序或外部环境影响,同一份输入可能在 PASSFAILUNRESOLVED 之间漂移。此时应先固定环境或引入重复判定,再决定是否复用缓存。

实验脚本、原始日志和结构化结果均已保留。完整运行包含 29 项断言,覆盖输入构造、两条缩减结果、失败身份、一最小检查和资源上限;29/29 通过,连续两次运行得到相同结果。

严格失败判定下,人工构造的 5120 字节输入缩到 BUG 三字节,并通过逐字节一最小检查

缩减收据记录候选评估、接受缩减与终点检查,不是性能基准。

字节级一最小性的保证范围

终点为 BUG 后,实验分别删除 B、U、G,得到 UGBGBU;三者都不再触发严格 FAIL。这证明 BUG 相对于当前字节位置和严格判定器是 1-minimal(一最小),也就是任意再删一个保留字节,目标失败就消失。

一最小不等于全局最短、唯一答案或故障根因。算法没有穷举所有组合,另一条缩减路径也可能得到不同局部极小结果。TSE 2002 论文指出,字符删除会让语法敏感输入产生许多无效候选,并提出用语法排除无效输入。在此思路上,工程实现还可按输入结构改用行、token、AST 节点或其他语法单元。

BUG 候选的证明里,“字节位置”也很重要。两个值相同的 A 位于不同偏移时,仍是两个不同的删除单元。对 BUG 的逐字节检查证明 B、U、G 各自不可再单独删除,并未遍历所有重新排列或组合。

更短结果可能属于另一种错误

同一循环换成“任何非零退出都算 FAIL”的宽泛判定后,5120 字节被缩到一个字符 X。它虽然更短,却只返回 exit 2 与 VALIDATION_ERROR,没有任何信号;严格判定器会把它归为 UNRESOLVED,因为原来的 SIGABRT 身份已经丢失。

同一补集删除循环因严格与宽泛失败判定不同,分别得到 BUG 三字节原崩溃与 X 一字节校验错误

更短不等于保留了同一次失败。

缩减器只会忠实地优化判定器;失败身份定义错了,输入越短,答案可能越错。

生产判定可组合异常类型、稳定栈顶、sanitizer 类别、错误码、构建 ID 与配置摘要,但需要在区分不同故障和容忍无关波动之间校准。偶发失败应先固定版本、环境与随机性,再决定是否缓存;否则一次偶然结果可能污染后续搜索。

复用这套方法时,应先把“同一次失败”写成稳定的三态判定,再按输入结构选择字节、行、token 或 AST 节点等删除单元,最后对终点逐个删除以复核一最小。失败身份不稳定,就不应启用缓存;核心不变量没有断言,再短的结果也不能直接交付。

算法性质依据 ISSTA 2000 原论文TSE 2002 扩展论文。本地补集删除循环改编自 The Fuzzing Book 固定版本的 MIT 代码;书稿内容另采用 CC BY-NC-SA 4.0,正文和配图保持独立表达。

随机比特公众号二维码
公众号 · 随机比特
从 AI 工具热闹里拆工程真相

写边界、控制面、上下文、成本与安全。