跳到正文
研踪PaperTrail
← 研踪 PaperTrail

arXiv:2611.20969 · v1

AutoDiDact: Input Reduction over Inferred Structure

首次提交 2026-11-16 20:08
版本更新 2026-11-16 20:08
雷达观测 2026-11-17 17:11
arXiv ↗PDF ↗

摘要

Delta debugging reduces a failing input by deleting chunks of it, keeping a deletion only if an oracle confirms the failure persists. It chunks the input based only on its length, so its deletions cut through units such as identifiers and delimited groups, wasting calls and leaving outputs large. Current state-of-the-art structural reducers avoid this by supplying grammars or built-in format knowledge. We show that structured reduction needs neither: a neutral word and delimiter pairs suffice, and both can be inferred from the failing input by asking only what delta debugging already asks its oracle: does the failure persist? A neutral word, such as a space, preserves the failure when inserted between such units but not inside them, so it splits the input into tokens. A delimiter pair is two tokens that preserve the failure only when added or removed together, so the span they bound can be reduced as a unit. We formalize both, state when the oracle can reveal them, and learn each with a bounded number of calls. AutoDiDact reduces the resulting tree of spans by hierarchical delta debugging (HDD) and shrinks each token across its occurrences. AutoDiDact finds a neutral word in 75 of 125 inputs from 18 format families. On these, it returns outputs 83% smaller than byte-level delta debugging with 37% fewer calls on geometric mean, inference included. The savings grow with input size, to 98% and 87% on inputs of at least 10 KiB. Without a grammar, AutoDiDact matches grammar-based HDD in output size at 3.85 times its calls, and uses 54% fewer calls than C-Reduce's language-agnostic mode. Because it needs only the oracle, AutoDiDact can minimize whatever a fuzzer finds, malformed inputs included.

作者备注:33 pages, including appendices. Replication package: https://doi.org/10.5281/zenodo.24164465

AI 论文解读

基于摘要 · 非全文审阅

此版本尚未生成 AI 解读。解读由后台任务生成并按论文版本保存,登录后共享已有结果。

版本差异

目前只收录了一个版本。收录下一版后,可以对照标题、作者、分类和摘要。

观测到的版本

相邻记录可能跳过中间版本;首次发现 v2 及以上也会标为版本更新。

v1 · 2026-11-16 20:08 · 最新观测版本

AutoDiDact: Input Reduction over Inferred Structure

Delta debugging reduces a failing input by deleting chunks of it, keeping a deletion only if an oracle confirms the failure persists. It chunks the input based only on its length, so its deletions cut through units such as identifiers and delimited groups, wasting calls and leaving outputs large. Current state-of-the-art structural reducers avoid this by supplying grammars or built-in format knowledge. We show that structured reduction needs neither: a neutral word and delimiter pairs suffice, and both can be inferred from the failing input by asking only what delta debugging already asks its oracle: does the failure persist? A neutral word, such as a space, preserves the failure when inserted between such units but not inside them, so it splits the input into tokens. A delimiter pair is two tokens that preserve the failure only when added or removed together, so the span they bound can be reduced as a unit. We formalize both, state when the oracle can reveal them, and learn each with a bounded number of calls. AutoDiDact reduces the resulting tree of spans by hierarchical delta debugging (HDD) and shrinks each token across its occurrences. AutoDiDact finds a neutral word in 75 of 125 inputs from 18 format families. On these, it returns outputs 83% smaller than byte-level delta debugging with 37% fewer calls on geometric mean, inference included. The savings grow with input size, to 98% and 87% on inputs of at least 10 KiB. Without a grammar, AutoDiDact matches grammar-based HDD in output size at 3.85 times its calls, and uses 54% fewer calls than C-Reduce's language-agnostic mode. Because it needs only the oracle, AutoDiDact can minimize whatever a fuzzer finds, malformed inputs included.

查看此版本解读 →查看此版本原文 ↗