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.

Authors

Publication Details

Journal
arXiv (Cornell University)
Published
2026-11-16
DOI
https://doi.org/10.48550/arxiv.2611.20969
Primary Topic
Software Testing and Debugging Techniques
Type
preprint
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
preprint

AutoDiDact: Input Reduction over Inferred Structure

Rahul Gopinath, Aarush Kumbhakern
arXiv (Cornell University)
Software Testing and Debugging Techniques
preprint

AutoDiDact: Input Reduction over Inferred Structure

Rahul Gopinath, Aarush Kumbhakern
preprint en

Abstract

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.

arXiv (Cornell University)
Software Testing and Debugging Techniques
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon