betaFeedback

WorksComputer Science

AutoDiDact: Input Reduction over Inferred Structure

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.

Introduction

Delta debugging [41] reduces a failing input by deleting chunks of it, keeping a deletion only when an oracle confirms the failure persists. Byte-level delta debugging chunks the input based only on its length, blind to its structure. A chunk that cuts through a unit such as an identifier or splits a pair of parentheses is rejected, wasting a call. A whole unit is deleted only when a chunk happens to align with it, and edits that must touch separate places at once, such as removing both parentheses of a pair, are never tried. On a 95.4 KiB C program from our benchmark that crashes GCC 4.3.0 (Table 2), byte-level delta debugging spends 232,803 calls and stops at 45,061 bytes, not counting whitespace: no single byte can be removed, yet the output is far from small.

Structural reducers edit whole units, using format knowledge supplied in advance. Hierarchical delta debugging (HDD) [26] and Perses [33] obtain units from a grammar. Such a grammar may be unavailable, even for a widely used language [30] or a specified format [10], and one that exists may not cover the dialects and extensions an input uses [27, 29]. Other reducers build format knowledge into the tool. C-Reduce [31] transforms C and C++ with the Clang front end, and for other formats, its --not-c mode keeps generic passes, such as deleting lines, C tokens, or bracket pairs from a fixed list, with or without their contents. This fixed list cannot pair an XML start tag <name> with its end tag </name>, since the names vary with the input.

We show that structured reduction needs neither a grammar nor built-in format knowledge: a neutral word and delimiter pairs suffice. Both can be inferred from the failing input by asking only what delta debugging already asks its oracle, without a lexer, example corpus, or syntax oracle. A neutral word, such as a space, preserves the failure when inserted between units but not inside them, so the offsets where it is accepted split the input into tokens. Each delimiter pair, such as matching parentheses or an XML start and end tag, encloses a span. Its delimiters are coupled: they preserve the failure when added or removed together but not either one alone. We implement this approach in AutoDiDACT, which applies HDD to the inferred tokens and spans, deleting whole spans or only their delimiters, and then shortens each distinct token at all its occurrences. The reducer keeps an edit only if the oracle confirms that the failure persists. Incorrect structure may leave a larger output or require more calls. On the GCC input, AutoDiDACT reaches 151 bytes in 3,023 calls, inference included.

When no neutral word is found, reduction works on bytes, and when no pairs are found, on flat tokens. Because the inferred structure comes from the oracle, it reflects what the failure depends on. In a JavaScript test that crashes an instrumented library, the imported module path "../instrumented/lodash/hasPath.js" stays one token, while the printed test title 'SynTest Test Suite', where a space is accepted at every offset, splits into single characters.

We evaluate AutoDiDACT on 125 inputs from 18 format families. Inference finds a space as the neutral word on every text input and abstains on all but one binary input. Given a neutral word, AutoDiDACT returns outputs 83% smaller than byte-level delta debugging with 37% fewer calls on geometric mean, inference included. The savings grow with input size: on inputs of at least 10 KiB they reach 98% and 87%, respectively, while below 1 KiB outputs are still 30% smaller for 1.79× the calls. Even without a grammar, AutoDiDACT matches grammar-based HDD in output size, at 0.96× on 50 inputs, for 3.85× the calls, or 1.53× excluding inference. Against C-Reduce’s language-agnostic mode, it uses 54% fewer calls. Its outputs are 30% smaller overall, driven by XML, and 1.23× C-Reduce’s on the other families. Inference finds 97.7% of the token boundaries that a standard lexer finds. It makes 11.6% of AutoDiDACT’s calls overall and 8.9% on inputs of at least 10 KiB.

AutoDiDACT parses nothing, so it runs on malformed and binary inputs alike. Fuzzers such as AFL [40] and libFuzzer [23] minimize the crashing inputs they find at the byte level, since they cannot assume an input format. With AutoDiDACT, a fuzzer can carry a general minimizer that works on any input.

Contributions:

  • The observation that a neutral word and delimiter pairs, both learnable from the failure oracle, suffice for structured reduction without a grammar or built-in format knowledge.

  • Formal definitions of neutral words and delimiter pairs as oracle behavior, the conditions under which the oracle reveals them, and bounded, sampling-based learners that infer them or abstain, together with a tokenizer that predicts boundary verdicts from earlier probes and tests likely boundaries together.

  • Laminar reduction, HDD over inferred tokens and spans, with a tree construction in which kk stray delimiters change the number of spans by at most kk.

  • An empirical evaluation on 125 inputs from 18 format families against byte-level delta debugging, HDD, and C-Reduce, with a released benchmark of oracles, pinned target builds, our implementation AutoDiDACT, and experiment scripts.

Input Reduction

Given a failing input SS, an input reducer deletes atoms, here bytes, while preserving the failure. An oracle Ψ\Psi returns Ψ(s)=✓\Psi(s) = \checkmark if candidate ss triggers the failure and Ψ(s)=X\Psi(s) = \mathrm{X} otherwise, and a reducer keeps a deletion only if the result is accepted. We measure cost in oracle calls and in wall time, since calls differ in cost: one may run several target processes.

Ideally, a reducer would return a global minimum: an accepted subsequence of smallest size. Without assumptions about Ψ\Psi, finding one can require exponentially many oracle calls [41].

Reducers therefore settle for local minimality. An input is 1-minimal over a given sequence of units, such as atoms or tokens, if no single unit can be deleted while preserving the failure.

Running example. Consider a C compiler that crashes on any call to a function named trace, but only after the call parses and type-checks. Suppose a reported function body contains the statements int count = 0; if (count > 100) { trace(count); }. To keep the example small, we reduce only these 49 bytes and keep the rest of the function fixed, with void trace(int); declared. The oracle compiles the function with the candidate in place and accepts it if the compiler crashes. It rejects a candidate that does not parse or type-check, just as it rejects one that compiles without crashing, so the reducer cannot tell the two apart. For the measurements below, we simulate the crash: the oracle accepts a candidate that type-checks and contains a call to trace.

Delta debugging. Delta debugging [41] deletes chunks of the input, keeping each deletion the oracle accepts. We use drdd [20] (Algorithm B.2), a variant of the original ddmin algorithm that defers its restarts. It sweeps the input with chunks of halving size ss, from half the input down to two units. Each sweep cuts the input into chunks of ss units, the last possibly shorter, and tries deleting each in turn, from left to right, keeping every accepted deletion. A closing scan then tries deleting each unit alone, repeating until a scan deletes nothing. The result is 1-minimal over the chosen units, so the choice of units determines both where the cuts fall and what the result guarantees.

In the byte-level run, the sweeps with 24- and 12-byte chunks delete nothing, since no candidate compiles. With 6-byte chunks (Figure 1), the sweep successfully deletes > 100, leaving (count).

Third drdd sweep over the running example

Figure 1. The third drdd sweep over the running example, in 6-byte chunks of its bytes and 3-token chunks of its tokens. Boxes are units, underlines are chunks, red squiggles split an identifier, and ␣ is a space.

Avoiding bad divisions. Byte-counted cuts fall inside identifiers. Five of the nine chunks at s=6s = 6 split count or trace. Deleting one leaves a broken or undeclared name, such as unt from deleting int co, which the compiler rejects before reaching the crash, each at the cost of a compilation. Byte-level drdd issues 111 queries, of which only 8 are accepted and 103 do not compile, and ends at the 36-byte int count=0;if(count){trace(count);}. However, if given the token boundaries of a C lexer, drdd can instead count tokens when forming chunks. Every candidate then keeps or deletes whole tokens, never splitting an identifier, and the result is 1-minimal over tokens. On the example, this takes 58 queries and ends at the 34-byte int count=0;if(100){trace(count);}.

Tokens alone still waste queries. With 3-token chunks, the chunk if ( separates ( from its ), and deleting it leaves an unbalanced condition that does not compile. If the reducer also knew that parentheses and braces enclose spans, it could delete a whole span, or unwrap it by deleting both its delimiters in one query. Given these spans as well as the tokens, a span or unwrap drdd (§ 3) deletes the if and its condition and unwraps the braces, reaching the 25-byte int count=0;trace(count); in 47 queries. One relation remains: count must be spelled alike at its declaration and remaining use, so no deletion inside one occurrence alone is accepted. Shortening both at once, as shrinking does (§ 3), reaches the 17-byte int t=0;trace(t); in 15 more queries.

These counts assume the structure is given. This section describes reduction over tokens and spans, and § 4 infers both from the failing input and its oracle.

Reduction over Laminar Structure

Reduction takes the failing input SS, its oracle, and two kinds of structure. The tokens partition SS into nonempty, contiguous pieces, and each delimiter pair is an opening and a closing token. a symmetric delimiter, such as a quote, both are the same token. Reduction runs in two stages: laminar reduction deletes tokens and the spans that pairs enclose, and shrinking shortens tokens.

Building the tree. The tree (Figure 2) matches opening delimiters with closing ones. Some delimiters may have no match: failing inputs are often malformed, comments and strings contain delimiters, and pair learning may admit a wrong pair. We want each such stray delimiter to change the number of spans by at most one. A stack that matches each close with the latest unmatched open lacks this property: in { /* (1 */ trace(count); }, the parenthesis in the comment is still open when the closing brace arrives, so the brace span is lost, and with it every span enclosing it. We therefore choose as spans a largest laminar set of matched pairs [16], leaving unmatched delimiters, like that parenthesis, as ordinary tokens. Finding it is Dyck edit distance restricted to deletions [1, 5]. Inserting or deleting kk delimiters changes the number of spans by at most kk, and admitting a further pair never reduces it. A stack first matches the unambiguous pairs, and a cubic interval dynamic program then matches the rest exactly (Section B.1, Algorithm B.1). With the parentheses and braces of the running example as pairs (Figure 2), the root holds the declaration’s tokens, if, spaces, and two spans, (count > 100) and { trace(count); }, which holds the span (count).

The running example’s tokens as boxes, and the spans of its parentheses and braces as frames colored by depth

Figure 2. The running example’s tokens as boxes, and the spans of its parentheses and braces as frames colored by depth. The root holds the unframed tokens and the two outer spans.

Reducing a node. At each node, a delta debugging reducer deletes tokens and child spans, keeping the node’s own delimiters and everything outside it fixed. Laminar drdd uses drdd. For example, deleting if (count > 100) at the root leaves int count = 0; { trace(count); }, which still crashes. Once a non-root node is reduced, two edits try to remove its delimiters while keeping some of its contents. The node is first hoisted: its nearest descendant spans of the same pair are tried in its place, one query each, and the first one accepted replaces it, following Picireny’s hoisting [34]. A node that is not hoisted is then unwrapped by deleting both its delimiters in one query. Unwrapping the braces of { trace(count); } results in trace(count);.

Traversal and guarantees. Laminar reduction (Algorithm B.3) is HDD* [26] over the constructed tree: it reduces nodes level by level from the root, descends only into surviving spans, and repeats until a traversal changes nothing. It reduces each node separately, where HDD reduces a whole level at once.

For any tokens and pairs, laminar reduction guarantees that it (1) preserves the failure, (2) terminates after at most ∣S∣|S| traversals that change the input, since each deletes a nonempty token, and (3) ends with every node 1-minimal over its items and every remaining span’s hoists and unwrapping rejected.

Each traversal runs drdd’s closing scan once per node, so it makes at most three queries per item for the sweeps and the scan and two per span to hoist or unwrap it, and by (2) laminar reduction makes O(∣S∣2)O(|S|^2) queries, as drdd does in its own worst case.

Shrinking tokens. After laminar reduction, shrinking (Algorithm B.4) runs one pass of drdd that shortens each distinct multi-atom token by deleting from all of its occurrences at once, which turns int count=0; trace(count); into int t=0; trace(t);.

1-minimality. Like HDD* [26], laminar reduction ends 1-minimal over nodes by (3). It is not 1-minimal over atoms, since it never deletes a lone delimiter or part of a token. Shrinking may also re-enable a deletion that laminar reduction rejected. Repeating drdd’s closing scan over atoms until it deletes nothing makes any output 1-minimal over atoms, at one query or more per remaining atom. AutoDiDact does not run this scan, and § 7.1 reports what it adds.

Inferring the Structure

The oracle answers only yes or no for a whole input, so we read structure from how its verdict changes under edits of the failing input: insertions reveal tokens, and paired edits reveal delimiters.

Oracle-Relative Structure

Tokens and delimiter pairs follow one pattern of oracle verdicts: an edit that respects the structure preserves the failure, while controls, minimal variants that break the structure, lose it. Only this contrast shows that a word separates or a pair matches: accepting both edits, as inside a comment, or rejecting both reveals nothing. Neither definition mentions a format or needs SS to be well formed.

Tokens. We seek a word that the failure treats as a separator: inserted between units, it preserves the failure, and inserted inside one, it does not. With such a word, one query per offset locates every boundary. Lexers often discard such a separator, like whitespace, between tokens. In the running example, inserting a space between trace and ( gives trace (count);, which still crashes. Inserting a byte absent from the input, such as @, gives trace@(count);, which is rejected, as is tr ace(count);, with a space inside the identifier. Spaces at any number of token boundaries, in any amount, compile and crash. We take this contrast as the definition of neutral words.

Let N=∣S∣N = |S| for the failing input SS, and number each internal offset gg by the count of atoms before it, so that 0<g<N0 < g < N. For a word uu, we write S⊕gu=S[0:g]⋅u⋅S[g:N]S \mathbin{\oplus_g} u = S[0:g] \mathbin{\cdot} u \mathbin{\cdot} S[g:N] for SS with uu inserted at gg. Fix a control atom κ\kappa that is as rare in SS as possible, so it is unlikely to be neutral. An offset gg is selective for a word ww if the oracle accepts S⊕gwS \mathbin{\oplus_g} w but rejects both controls S⊕gκS \mathbin{\oplus_g} \kappa and S⊕gκ∣w∣S \mathbin{\oplus_g} \kappa^{|w|}, the latter with ∣w∣|w| copies of κ\kappa. Selectivity rules out regions the oracle ignores and regions where any text of the right length suffices. A nonempty word ww is neutral for SS if, for some nonempty set GG of selective offsets, the oracle accepts SS with cg≥0c_g \ge0 copies of ww inserted at each g∈Gg \in G, for every choice of the counts cgc_g. Neutrality asks more than one accepted insertion: copies must be accepted in any amount and at all offsets of GG at once, as a separator’s are. Given a neutral word ww, the token boundaries of SS are the offsets accepting a single insertion of it,

Bw(S)={g:0<g<N, Ψ(S⊕gw)=✓},(1)B_w(S) = \{g : 0 < g < N,\ \Psi(S \mathbin{\oplus_g} w) = \checkmark\}, \tag*{(1)}

and these boundaries cut SS into its tokens. Every selective offset is a token boundary, and offsets that the failure ignores, such as those inside a comment, are token boundaries without being selective. In the running example, the space is neutral, and the tokens are the C tokens and the spaces.

An input may have several neutral words, such as a space and a newline in C, and their boundaries can differ: inside a string literal, a space may be accepted where a newline is not. If the oracle sees its input only through a lexer that discards ww between tokens and rejects κ\kappa there, every lexical boundary is a token boundary, and a lexical token is split exactly where the failure does not need it whole (Section A.1), as with the JavaScript test title of § 1. Any separator such a lexer discards thus recovers the lexical boundaries, and finding one is a matter of inference (§ 4.2).

Spans. Parsers need brackets to match: adding or removing an open and close together can keep them matched, and adding or removing only one does not. In the running example, wrapping count gives the accepted trace((count));, and adding only one parenthesis, as in trace((count); or trace(count));, is rejected. Again we take this contrast as the definition. Because delimiters are tokens, a pair can be any two tokens that the failure needs matched, not only bracket characters: begin and end, a quotation mark with itself, or the <name and </name that open an XML start and end tag, whose names vary with the input and so escape any fixed list of brackets. The candidates thus narrow from every substring of SS to its distinct tokens. Write S=t1⋯tnS=t_1\cdots t_n for its tokens. For tokens ◃\triangleleft and ▹\triangleright, a matching of a token sequence xx pairs positions i<ji<j with xi=◃x_i=\triangleleft and xj=▹x_j=\triangleright, using each position at most once, so that any two pairs are nested or disjoint. Let ν(x)\nu(x) be the size of a largest matching and δ(x)\delta(x) the number of positions holding ◃\triangleleft or ▹\triangleright. Then xx is matched if a largest matching leaves no delimiter out, that is,

x matched ⟺ 2ν(x)=δ(x) ⟺ {∣x∣◃ is evenif ◃=▹,∣x∣◃=∣x∣▹ ∧ ∀y⊑x: ∣y∣◃≥∣y∣▹otherwise.(2)x\ \text{matched}\ \Longleftrightarrow\ 2\nu(x)=\delta(x)\ \Longleftrightarrow\ \begin{cases} |x|_{\triangleleft}\ \text{is even} & \text{if }\triangleleft=\triangleright,\\ |x|_{\triangleleft}=|x|_{\triangleright}\ \land\ \forall y\sqsubseteq x:\ |y|_{\triangleleft}\ge|y|_{\triangleright} & \text{otherwise}. \end{cases} \tag*{(2)}

where ∣y∣t|y|_t counts the occurrences of a token tt in yy, and y⊑xy\sqsubseteq x ranges over the prefixes of xx. The difference δ(x)−2ν(x)\delta(x)-2\nu(x) counts stray delimiters, which the tree of § 3 minimizes over all pairs at once. The spans of (◃,▹)(\triangleleft,\triangleright) are the intervals ta⋯tbt_a\cdots t_b with a<ba<b, ta=◃t_a=\triangleleft, tb=▹t_b=\triangleright, and a matched interior ta+1⋯tb−1t_{a+1}\cdots t_{b-1}, which for a symmetric delimiter holds none of it, since quotes do not nest. We write a span as ◃m▹\triangleleft m\triangleright, with opening delimiter ◃\triangleleft, interior mm, and closing delimiter ▹\triangleright. Each row below replaces a span, leaving the rest of SS fixed, by a paired edit, which adds or removes ◃\triangleleft and ▹\triangleright together, and by two controls, each off by one delimiter, an ◃\triangleleft in one and a ▹\triangleright in the other:

wrap:◃ ◃m▹ ▹against◃ ◃m▹  and  ◃m▹ ▹,empty or delete:◃▹  or the empty stringagainst▹  and  ◃,repeat:◃m▹ ◃m▹against◃m▹ ◃m  and  ◃m▹m▹.(3)\begin{aligned} \text{wrap:}\quad&\triangleleft\ \triangleleft m\triangleright\ \triangleright&&\text{against}\quad\triangleleft\ \triangleleft m\triangleright\ \text{ and }\ \triangleleft m\triangleright\ \triangleright,\\ \text{empty or delete:}\quad&\triangleleft\triangleright\ \text{ or the empty string} &&\text{against}\quad\triangleright\ \text{ and }\ \triangleleft,\\ \text{repeat:}\quad&\triangleleft m\triangleright\ \triangleleft m\triangleright&&\text{against}\quad\triangleleft m\triangleright\ \triangleleft m\ \text{ and }\ \triangleleft m\triangleright m\triangleright. \tag*{(3)} \end{aligned}

The span couples if, in some row, the oracle accepts the paired edit and rejects both controls, telling balanced delimiters from unbalanced ones. The pair (◃,▹)(\triangleleft,\triangleright) is a delimiter pair of SS if at least two of its spans couple, since one coupled span could be a coincidence. Parentheses that the oracle ignores, as in a comment, are not a delimiter pair. Suppose the oracle, like a parser, rejects every unmatched input, and that SS is matched. Every paired edit then keeps SS matched, and every control does not, since one delimiter more or fewer makes δ\delta odd, so every control is rejected. A parser’s pair is thus a delimiter pair once two of its spans survive a paired edit (Section A.2). For the same reason, deleting or unwrapping a span keeps the delimiters matched, and spans spare reduction the doomed deletion of one delimiter alone (§ 2). Nor must SS be matched: coupling is judged span by span, and the tree of § 3 leaves stray delimiters as ordinary tokens.

What the learners admit. The learners of § 4.2 and § 4.4 admit a word or pair on finite evidence for these definitions. Neutral-word discovery admits a word that is selective at observed offsets and passes a few reuse tests, each inserting copies of it at some of those offsets. A neutral word passes these tests within its set GG. Pair learning admits a pair once it observes coupling at two candidate intervals, pooling the spans of a family of pairs that differ only in a name, such as XML tags. Two further checks guard admission: an entropy guard vetoes a word confirmed on weak evidence in a repetitive input, and a pair is tested only if duplicating either delimiter of a representative pair is rejected.

What queries cannot show. Both learners generalize from finitely many queries, which cannot rule out a different verdict on an untested edit or name. The definitions also leave four cases open. A neutral word need not separate anything: a digit is neutral when lengthening a number keeps the failure. Genuine delimiters yield no witness when every paired edit destroys the failure. Tokens that must appear together without enclosing anything, such as ? and : in C, can also couple. If the control kk is accepted at every sampled offset, none is selective, and discovery abstains.

Neutral-Word Discovery

Neutral-word discovery (Algorithm 1) proposes repeated substrings, observes where each is selective, and tests the most promising for reuse. It judges neutrality from a sample of offsets, and the evidence a sample provides depends only on the sample size. If a word rejects pp of the offsets where it is selective, kk such offsets drawn uniformly at random all accept it with probability at most (1−p)k(1-p)^k, however long SS is. The implementation therefore uses a fixed budget of 300 calls, with 16 reserved for confirmation. The bound assumes uniform sampling, and SCHEDULE skews it toward varied contexts, so the bound only motivates the budget.

Algorithm 1 Discover a neutral word

Input: Failing input SS, oracle Ψ\Psi Output: An admitted word, or ⊥\bot to abstain

Before any query would exceed 300 calls in total, return ⊥\bot.

  1. sources ←\leftarrow first 40 words of CANDIDATES(SS), and WW ←\leftarrow the first 24

  2. if W=∅W = \varnothing then return ⊥\bot

  3. κ\kappa ←\leftarrow the lowest byte from 1 to 255 absent from SS, or else the rarest byte of SS, lowest on ties

  4. DD ←\leftarrow OBSERVE(SS, Ψ\Psi, WW, κ\kappa, SCHEDULE(SS, sources), 284)

  5. if D=∅D = \varnothing then return ⊥\bot

  6. ranked ←\leftarrow words ui∈Wu_i \in W with si>0s_i > 0 and ei≥0e_i \ge0 ((C.1)), stably by decreasing eie_i

  7. refuted ←∅\leftarrow\varnothing

  8. while ranked ≠∅\ne\varnothing do

  9. Remove from ranked its first word ww whose root ρ(w)∉\rho(w) \notin refuted, or else its first word

  10. A←A \leftarrow SITES(ww, DD), and T←T \leftarrow REFINESITES(ww, AA)

  11. Test REUSETESTS(ww, TT) in order, stopping at the first rejection

  12. if all reuse tests accepted then return ⊥\bot if ∣A∣<3|A| < 3 and H(S)<2/3H(S) < 2/3, else ww

  13. if a reuse test rejected then refuted ←\leftarrow refuted ∪{ρ(w)}\cup\{\rho(w)\}

  14. return ⊥\bot

Candidates. A separator tends to recur beside varied tokens. In the running example, the space occurs 10 times, after 7 distinct atoms and before 10. CANDIDATES therefore proposes maximal repeats: substrings that occur at least twice, with at least two distinct atoms before them and two distinct atoms after them. Non-separators such as (count also qualify, but ount does not, since it always follows c. A candidate with ff occurrences, dℓd_\ell distinct atoms before, and drd_r after ranks by min⁡(dℓ,dr)f\min(d_\ell,d_r)\sqrt{f}, with shorter words first on ties. The space thus ranks first at 710≈227\sqrt{10} \approx22, well ahead of 0 at 33≈5.23\sqrt{3} \approx5.2. The top 40 candidates steer where SCHEDULE samples offsets, and the top 24 of them form the tested words WW. An offset where κ\kappa is rejected costs one query per tested word, so with 24 words the observation budget covers about ten such offsets. The other 16 only steer sampling, at no cost. Both limits are hand-picked. The root ρ(u)\rho(u) is the shortest word whose repetitions form uu, and words with the same root form a family, such as one and two spaces.

Assumptions. Discovery finds a neutral word only if it occurs in SS as a maximal repeat among the top 24 candidates. It cannot learn a word that SS does not repeat, such as a space in minified code, and then abstains, so reduction proceeds over bytes. Formats without a recurring separator, such as most binary formats, account for all 50 abstentions in our benchmark (§ 7.3).

Observation and scoring. At each offset that SCHEDULE picks, OBSERVE first inserts the control κ\kappa. If κ\kappa is accepted, the offset reveals nothing. Otherwise, it inserts each word of WW and credits the words that are selective there. A word’s score sis_i averages its credit, weighting offsets that credit few families more, since an offset that credits many says little about any one. Its adjusted score eie_i subtracts a rank penalty, so later candidates need more evidence. Scores filter and order candidates for confirmation.

Confirmation. Selectivity shows only that one copy is accepted at one offset, and a neutral word must also preserve the failure with any number of copies at the offsets of GG together. In the running example, adding three more spaces after int gives int___count = 0;, which still crashes. Such a query is a reuse test, inserting copies of the word at one site or at several together. In score order, discovery confirms the first word that passes its reuse tests. Each word gets at most five tests, at up to four accepted offsets, favoring distinct contexts (Section C.1). A rejection refutes reuse at those sites, and discovery tries other families first. Passing cannot rule out non-neutral words or interactions at untested sites. On the running example, the space ranks first and is confirmed in 5 calls after 284 observation calls.

Abstention. Neutral-word discovery abstains when no word passes confirmation within its 300 calls. It also abstains on weak evidence in repetitive inputs, where a word may pass only by lengthening padding: if fewer than three selective sites support the confirmed word and H(S)<2/3H(S) < 2/3. Here H(S)H(S) is the entropy of the atoms of SS, normalized by its maximum for their number of distinct values, and zero when fewer than two distinct atoms occur.

Tokenization

Given the neutral word ww, tokenization finds the token boundaries Bw(S)B_w(S) (1). Probing each internal offset gg alone, by querying S⊕gwS \oplus_g w, finds them exactly, at one query per offset. The default tokenizer (Algorithm 2) saves queries in two ways: it predicts verdicts from those it has already settled on the same input, and it tests several likely boundaries with one query.

Algorithm 2 Tokenize with boundary prediction and pooling

Input: Failing input SS, neutral word ww, oracle Ψ\Psi

Output: The tokens of SS

Every verdict that the oracle answers or implies trains Estimate.

  1. V←V \leftarrow empty verdict map, and R←R \leftarrow empty pool

  2. for g=1,…,N−1g = 1, \ldots, N - 1 do

  3. p^g←Estimate⁡(g,V)\hat{p}_g \leftarrow\operatorname{Estimate}(g,V)

  4. if p^g≥0.98\hat{p}_g \ge0.98 or p^g≤0.02\hat{p}_g \le0.02 then

  5. V[g]←V[g] \leftarrow ✓ if p^g≥0.98\hat{p}_g \ge0.98, else X  predict

  6. else if p^g<1/2\hat{p}_g < 1/2 then

  7. TestPool⁡(R)\operatorname{TestPool}(R), then V[g]←Ψ(S⊕gw)V[g] \leftarrow\Psi(S \oplus_g w)  probe alone

  8. else

  9. Add gg to RR, and V[g]←V[g] \leftarrow ✓  tentative boundary

  10. if ∏h∈Rp^h≤1/2\prod_{h \in R} \hat{p}_h \le1/2 then TestPool⁡(R)\operatorname{TestPool}(R)

  11. TestPool⁡(R)\operatorname{TestPool}(R)

  12. return the substrings of SS between consecutive offsets of {0,N}∪{g:V[g]=✓}\{0,N\} \cup\{g : V[g] = \checkmark\}

Prediction. Inputs repeat local patterns, and so do verdicts. In the running example, the offsets inside count have the same atoms around them at all three occurrences, as does the offset between ( and count at two. Estimate predicts an offset’s verdict from the settled verdicts of offsets that resemble it in the atoms around them, the verdicts next to them, or the share of boundaries nearby. Each kind of resemblance is a context. Estimate combines the boundary rates of an offset’s 14 contexts into p^\hat{p}, the estimated chance that the offset is a boundary. It trusts a context more when more settled offsets share it, and learns on each input which contexts predict well (Section C.2). The tokenizer predicts the verdict at fixed cutoffs p^≥0.98\hat{p} \ge0.98 or p^≤0.02\hat{p} \le0.02. The contexts and cutoffs are hand-picked and shared across formats.

Pooling. A neutral word can appear at many offsets at once, so the tokenizer tests likely boundaries together: one query inserts ww at every offset of a pool. In the running example, trace_(_count_)_; still crashes, settling the four offsets between the tokens of trace(count); in one query. A rejected pool holds at least one non-boundary, which binary splitting finds (Section C.2), as in adaptive group testing [8]. Pooling assumes, beyond what neutrality guarantees, that a pool is exactly when each of its insertions alone would be. Where this fails, a rejected pool of boundaries yields a false non-boundary, merging two tokens.

What to query. A query tells the most when its outcome is a coin flip and the least when it is nearly certain (Section C.2). The tokenizer therefore predicts nearly certain verdicts, and probes a likely non-boundary, with p^<1/2\hat{p} < 1/2, alone, since a pool containing it would probably be rejected. It adds each likely boundary to the pool instead, and tests the pool once the estimated chance that all its offsets are boundaries, ∏p^\prod\hat{p}, falls to one half.

What prediction affects. The thresholds give no error guarantee. A wrong prediction can only merge tokens, hiding a delimiter, or split a token that exhaustive probing keeps whole, changing the inferred pairs, output size, and oracle cost. The resulting tokens are then frozen for pair learning and reduction. § 7.3 measures them against exhaustive probing and against real lexers.

Pair Learning

§ 4.1 showed that (count) couples. In the running example, so does (count > 100), the other span of the parentheses. Pair learning (Algorithm 3) finds such pairs on its own. It proposes hypotheses, each a single pair or a family of related pairs, such as XML tags, together with candidate intervals where they might delimit spans. It ranks hypotheses without queries, skips unpromising ones, and admits a hypothesis once two of its candidate intervals couple, as the parentheses do.

Algorithm 3 Learn delimiter pairs

Input: Input S=t1⋯tnS = t_1 \cdots t_n with frozen tokens, word ww, oracle Ψ\Psi Output: Inferred delimiter pairs PP

  1. P←∅P \gets\varnothing, and Z←∅Z \gets\varnothing — admitted intervals

  2. for kind∈(stacked,symmetric)kind \in(\text{stacked},\text{symmetric}) do

  3. Q←Hypotheses⁡(S,w,kind,Z)Q \gets\operatorname{Hypotheses}(S,w,kind,Z), and streak←0streak \gets0

  4. for each (H,U,p)∈Q(H,U,p) \in Q do

  5. if streak=4streak = 4 then break

  6. A←{(a,b)∈U:a,b lie in the same region of Z}A \gets\{(a,b) \in U : a,b \text{ lie in the same region of } Z\}, and π←2+⌊p⌋\pi\gets2 + \lfloor p \rfloor

  7. if HH reuses a token of PP, ∣U∣−∣A∣>π|U| - |A| > \pi, no interval in UU encloses a non-blank token, or not Sensitive⁡(H)\operatorname{Sensitive}(H) then continue — screens

  8. if Test⁡(A,π)\operatorname{Test}(A,\pi) then P←P∪HP \gets P \cup H, Z←Z∪AZ \gets Z \cup A, and streak←0streak \gets0 else streak←streak+1streak \gets streak + 1

  9. return PP

Hypotheses. Delimiters are non-blank tokens, those not made only of copies of ww. A hypothesis is stacked if its opening and closing delimiters differ, so that a stack can match them like brackets, and symmetric if a token pairs with itself, like a quotation mark. Every two distinct tokens that each occur at least twice form a stacked single pair, in whichever orientation balances better, and every token occurring at least four times forms a symmetric one. An affix family is a set of pairs whose delimiters share a name ν\nu and differ only in a fixed prefix or suffix, such as <ν<\nu and </ν</\nu for XML tags. It pools evidence from names too rare to propose alone. Formally, it groups the pairs (aν,bν)(a\nu,b\nu) or (νa,νb)(\nu a,\nu b) over at least two names ν\nu, in either orientation, for any distinct nonempty affixes a,ba,b. Hypotheses ranks each kind and keeps its K=256K = 256 best, a hand-picked cap that binds on most inputs. The stacked list is tested first, and the symmetric list is built from the intervals admitted so far.

Assumptions. Pair learning can admit a pair only if tokenization kept its delimiters as tokens, the pair is proposed as above, and its hypothesis ranks among the top of its kind. A pair occurring only once can be learned only through an affix family. In the running example, the braces occur once each, so pair learning never proposes them.

Candidate intervals. Each hypothesis proposes intervals UU for coupling tests. For a stacked hypothesis, a stack matches each closing delimiter with the opening delimiter on top of the stack if it has the same name, and each match is a candidate interval, such as (count > 100) and (count) in the running example. Admitted intervals divide the input into regions, each directly inside one interval. Within each region, a symmetric hypothesis pairs its occurrences in order: the first with the second, the third with the fourth, and so on (Section C.3). In f('a'); g("it's"); h('b');, the apostrophe in it's is alone inside gg’s admitted parentheses, so it pairs with nothing, while over the input it would pair with the quote opening 'b'. Candidate intervals need not be spans: family matching can leave stray delimiters inside one, and in-order pairing ignores nested regions.

Ranking. In the running example, the two ( and two ) occur in balanced order, which only two of their six orders achieve. Delimiters that the failure needs matched are balanced like this far more often than chance. Each hypothesis therefore gets a prior pp, the surprise of its balance, meaning the negative log probability that a random shuffle of its occurrences leaves no more closing delimiters unmatched than the input does. For the parentheses, p=log⁡3p = \log3. A family adds the surprise of its names, and a symmetric hypothesis counts the regions holding an odd number of its occurrences (Section C.3). Every prior is capped at log⁡(1+∣U∣)\log(1 + |U|), and only hypotheses with at least two candidate intervals are eligible. Stacked hypotheses rank by pp, and symmetric ones by p+log⁡(1+∣U∣)p + \log(1 + |U|), which favors tokens with more sites to test. The prior only orders hypotheses and sets each one’s testing allowance π=2+⌊p⌋\pi= 2 + \lfloor p \rfloor, so that more surprising hypotheses get more tries.

Screens. Before spending coupling queries, Algorithm 3 screens out any hypothesis that (1) reuses an admitted delimiter, (2) has more than π\pi intervals that cross admitted ones, or (3) has no interval enclosing a non-blank token. These screens cost no queries. Screen (3) can discard a useful pair, since even an empty span may be worth unwrapping. A survivor must also be sensitive: duplicating either delimiter of a representative pair must be rejected (Section C.3).

Confirmation. Test seeks two witnesses, intervals that couple, among the intervals that cross no admitted one. It tries intervals of varied contexts and lengths, giving up after π\pi intervals without a witness, or 2π2\pi in all (Algorithm C.3). On each interval, Coupled tries the rows of (3) in order and succeeds at the first that couples, since a genuine span can fail some rows. Four consecutive failed hypotheses stop the current kind, and screened hypotheses do not count toward that streak.

Once a hypothesis is admitted, it pairs join PP, and its intervals that cross no admitted one are admitted too, tested or not. A family’s two witnesses may come from one name, so its other names are admitted by extrapolation, and the newly admitted intervals can suppress later hypotheses.

Query Bounds

Every stage’s query count is bounded in the input size NN. Neutral-word discovery makes at most 300 queries. Exhaustive tokenization makes N−1N - 1, and prediction and pooling usually make fewer, with O(N)O(N) queries even in the worst case at the fixed thresholds (Section C.2). Pair learning tests at most KK hypotheses of each kind, each with at most 2+2π2 + 2\pi queries, and π≥2+ln⁡(1+N)\pi\ge2 + \ln(1 + N), so it makes O(Klog⁡N)O(K \log N) queries (Section C.3). Laminar reduction makes O(N2)O(N^2) (§ 3), and shrinking, one drdd pass per distinct token, makes at most quadratically many in the tokens’ total length. The whole pipeline thus makes O(N2)O(N^2) queries in the worst case, the order of drdd itself. Candidate generation, ranking, prediction, and tree construction make none.

Evaluation

We evaluate AutoDiDACT on 125 failing inputs from 18 format families against byte-level drdd, HDD, and C-Reduce. The most important question for a new reducer is whether it improves upon the baseline. Hence, we ask:

RQ1: How does AutoDiDACT compare with byte-level drdd in output size and calls?

counts a family’s inputs, and the benchmark has 125 in all. ICE denotes an internal compiler error, and control denotes behavior preservation. In the word column, ␣ is a space, 10 B is the sequence returned on one ASN.1 input, and – denotes abstention.

With inferred structure, AutoDiDact can tackle structured inputs. But how good is that structure? Is it competitive with reducers that have format knowledge? Hence, we ask:

RQ2: How does AutoDiDact compare with the format-aware HDD and C-Reduce?

Finally, AutoDiDact rests on structure learned from the oracle alone, so we ask what that inference recovers and what it costs.

RQ3: What structure does inference recover from the failing input and its oracle alone, and at what cost? An answer tells us whether a failure oracle can stand in for the lexer and grammar that structural reducers need.

Inputs and Oracles

To cover a range of formats, we evaluate on 125 failing inputs from 18 format families (Table 1): 74 text-based and 51 binary, of 16 to 224,151 bytes. Of these, 113 reproduce failures, and 12 are controls that must preserve a program’s behavior.

Family#SizeOracleWordFamily#SizeOracleWord
Text-based inputsBinary inputs
c103.0 – 121.7 KiBICE, control␣asn16500 B – 1.2 KiBMagma fault10 B
crashjs10644 B – 1.3 KiBAPI exception␣binutils10683 B – 21.0 KiBsignal, allocator–
graphviz22.1 – 161.7 KiBsanitizer␣ffmpeg10468 B – 150.7 KiBsanitizer–
lua2889 B – 1.2 KiBassertion␣fonts8200 B – 65.0 KiBsanitizer–
pdf54.4 – 15.2 KiBMagma fault␣parquet466.8 – 110.3 KiBsanitizer–
python5212 B – 1.1 KiBinterpreter failure␣pcap373 – 205 Bsanitizer–
smt102.4 – 218.9 KiBassertion␣png2218 – 708 BMagma fault–
sql1051 – 538 Berror, wrong result␣tiff8409 B – 9.4 KiBMagma fault–
xml103.7 – 107.0 KiBdifferential␣All51
yaml1016 – 177 Bparse control␣
All74

Table 1. Benchmark families and neutral-word discovery outcomes

The inputs come from existing collections and bug reports. C, JavaScript, Python, and SMT-LIB inputs come from RedBench [18], CrashJS [28], GTR [12], and ddSMT [17]. Binutils, FFmpeg, font, Parquet, and libpcap inputs come from upstream reports and the OSS-Fuzz [32] and FuzzBench [25] archives, Graphviz and LuaJIT from upstream reports, SQL from upstream reports and SQLFlex [2], XML from [43], and ASN.1, PDF, PNG, and TIFF from Magma’s proofs of concept [11]. We keep at most ten inputs per family, spread across failure groups and sizes, stratifying JavaScript by project and C compiler failures by crashing source file, after dropping four near-duplicates: inputs of one failure group whose normalized compression distance [7] is at most 0.12.

Each oracle fixes its target versions and accepts a candidate that reproduces the recorded outcome. For most families, this is a signal, sanitizer report, assertion, diagnostic, or stack signature. For ASN.1, PDF, PNG, and TIFF, it is a recorded Magma [11] fault, and for SQL, an internal error or wrong result. For XML, BaseX must disagree with Saxon on a fixed query at affected revisions and agree at fixed ones. The controls must compile two Csmith [39] programs with sanitizers, run them, and keep their checksums, or keep the libyaml event streams of ten YAML test-suite inputs [37]. All reducers share each input’s oracle, which rejects timeouts. Inference sees only the oracle’s verdicts on raw bytes. Every original input passes its oracle before a run, and every output after.

Comparators

We compare AutoDiDact, with one set of parameters for every family, against three reducers: byte-level drdd, HDD, and C-Reduce. Where discovery abstains, it reduces exactly as drdd does, so RQ1 and RQ2 use the 75 inputs with a returned word, from 50 failure groups.

HDD. We run a pinned Picireny [13, 14] to a fixpoint. It implements HDD* with ddmin at each level, caching, pruning, and hoisting [34], over parse trees from grammars-v4 grammars [3] under ANTLR 4.13.2. A grammar exists for 50 inputs from eight families: C, JavaScript, Graphviz, Lua, Python, XML, and the SQLite and SMT-LIB 2 inputs of SQL and SMT. The C grammar alone is 18,234 bytes. We keep C’s and Python’s hidden tokens, which preserve directives and indentation, and patch Python’s synthetic token text so that unparsing preserves the source.

C-Reduce. We run a pinned C-Reduce [31] as creduce --not-c --n 1 --tidy on all 75 returned-word inputs, the C inputs included, so that every format gets the same passes, and let it run to its own fixpoint. This mode drops the Clang-based passes and keeps generic ones over lines, C tokens, and a fixed list of bracket pairs, plus integer reduction and peephole edits.

Measurement

Output size. We count non-whitespace bytes, since HDD spaces the tokens it unparses and C-Reduce reformats. For AutoDiDact against drdd, both of which only delete, this changes the mean size ratio by under one percent.

Calls. We count oracle executions. Every reducer’s oracle caches recent verdicts, and the counts exclude rechecks of inputs whose verdict is known: the checks of original and final inputs, C-Reduce’s initial sanity check, and Picire’s assertion at the start of each ddmin round.

Wall time. Measured on one core of an AMD Ryzen AI 9 HX PRO 370 under Fedora 44, it covers inference or reduction, oracle execution, and each stage’s startup and shutdown. HDD’s includes generating its parser. Since setup costs differ across tools, comparisons emphasize calls.

Results

We answer the three questions in order, charging inference in full throughout. Table 3 summarizes the comparisons of RQ1 and RQ2.

ReducerAll 50 inputs: SizeAll 50 inputs: Smaller/largerAll 50 inputs: CallsAll 50 inputs: Reduction callsWithout XML: SizeWithout XML: Calls
AutoDiDact0.1049/00.370.150.180.51
C-Reduce (--not-c)0.1943/71.06–0.150.94
HDD (Picireny)0.1147/30.10–0.210.20

Table 3. Reducers relative to drdd. On HDD’s 50 inputs, AutoDiDact’s outputs are 90% smaller than drdd’s with 63% fewer calls, 0.96× HDD’s at 3.85× the calls, and smaller than C-Reduce’s with 65% fewer calls

RQ1: Comparison with Byte-Level Delta Debugging

We compare AutoDiDact with byte-level drdd on the 75 inputs with a returned word, charging all inference to AutoDiDact. Against drdd, AutoDiDact returns outputs 83% smaller with 37% fewer calls on geometric mean, inference included. Its outputs are smaller on 60 of 75 inputs, equal on 14, and larger on one, and it uses fewer calls on 36. These results include AutoDiDact’s final shrinking pass, which reduces 55 of the 75 laminar outputs further, by 16% on geometric mean, for 11% more calls. Table 2 gives each input’s outputs, calls, and time, and Table D.1 itemizes AutoDiDact’s by stage.

Input size. The savings grow with input size (Figure 3). On the 26 inputs of at least 10 KiB, outputs are 98% smaller and calls 87% fewer, with 23 outputs smaller and 22 runs cheaper. Between 1 and 10 KiB, outputs are 69% smaller for 7% fewer calls. Below 1 KiB, outputs are 30% smaller, and calls rise 1.79×, with fewer calls on 5 of 34 inputs. In wall time, AutoDiDact takes 0.25× drdd’s time at 10 KiB and above and 0.89× overall, and longer on smaller inputs.

AutoDiDact’s advantage over drdd

Figure 3. AutoDiDact’s advantage over drdd grows with input size: points fall further below the diagonal as drdd’s outputs and calls grow. On the 75 returned-word inputs, AutoDiDact’s output is smaller on 60 and larger on one. It makes fewer calls on 22 of the 26 inputs of at least 10 KiB, but on only 5 of the 34 below 1 KiB. Left: output size in non-whitespace bytes. Right: calls, including all inference. Axes are logarithmic. Points below the dashed diagonal, where the two are equal, favor AutoDiDact, and colors and marks distinguish families.

1-minimality over atoms. Laminar reduction’s output is 1-minimal over nodes, and drdd’s over atoms. Running drdd’s closing atom scan on AutoDiDact’s output makes it 1-minimal over atoms too: the scan shrinks 28 of 75 outputs, leaves outputs 0.17× drdd’s on geometric mean, and adds 11% to the calls, which stay 30% fewer than drdd’s.

CaseInputAutoDiDact OutputAutoDiDact CallsAutoDiDact Timedrdd Outputdrdd Callsdrdd TimeHDD OutputHDD CallsHDD TimeC-Reduce OutputC-Reduce CallsC-Reduce Time
asn1
asn1-aah055-nested58011262333 s16445517 s–––5793,2804 m
c
023,6234573,0327 m8242,6794 m4815,21924 m39913,85623 m
103,0712812,1264 m5281,8593 m2771,5153 m2244,3197 m
tree-ssa-structalias_c_4773_96K97,6581513,0233 m45,061232,8032.0 h1821,9023 m1328,1743 m
tree-vect-transform_c_6496_55K55,9231145,6584 m13,940146,9791.6 h1117,04611 m985,9933 m
fold-const_c_8943_23K23,1711012,44774 s9,62042,49312 m1521,1782 m1265,7912 m
recog_c_1990_63K63,5091382,5332 m31,646156,70061 m10751378 s652,79570 s
simplify-rtx_c_4922_43K43,7201353,02991 s17,30866,09325 m1461,1162 m764,5862 m
gimple_c_2343_122K124,59314210,30213 m31,151284,2083.2 h19414,34242 m9112,5378 m
emit-rtl_c_1950_75K76,2631552,6903 m35,434188,6611.7 h1852,1346 m1356,5073 m
ira-emit_c_371_17K16,4241993,11077 s8,91438,22311 m3153,4678 m22915,3646 m
crashjs
71,0121591,7825 m3331,9666 m1262522 m1272,0166 m
108301131,4415 m3322,2467 m1513632 m1341,5245 m
commander-47781661,4344 m3131,0623 m2497574 m2085,16315 m
commander-311,0551561,3714 m2971,1853 m2093942 m1843,47310 m
javascript-algorithms-57452201,5355 m4971,6375 m3546023 m2402,6908 m
javascript-algorithms-148142521,2334 m3311,0454 m2043132 m1941,8976 m
moment-18001811,5219 m4341,69411 m1304055 m1441,9437 m
moment-171,3401881,76810 m4832,00012 m2227077 m2072,2678 m
express-1644981,1824 m2101,1854 m12218687 s1071,8886 m
express-489031171,3364 m1819043 m2202812 m2122,8729 m
graphviz
issue-1436165,5832,27057,9403.2 h12,949137,3144.2 h1,6145,51216 m516,78110 m
issue-27232,141901,01147 s2571,46155 s897222 m852,04871 s
lua
luajit-9131,248721,32552 s3201,93428 s11430859 s581,78949 s
luajit-11168893772,38558 s3771,99142 s3573,5298 m38910,0873 m
pdf
pdf-fuzzer-aah05215,4211181,4192 m11868833 s–––1133,0532 m
pdf-fuzzer-jch20715,505767229 s71113.5 s–––11524615 s
pdfimages-jch207-kw64,54331,10724 s3631.1 s–––354120 s
pdftoppm-aah05215,4951391,57686 s12070125 s–––1112,7022 m
pdftoppm-jch20715,5327944,7332 m7993,9292 m–––32,7942 m
python
ackermann4831231,1132 m2161,07386 s1421,1175 m782,7844 m
alloc1,1253042,3733 m4661,8562 m4262,1247 m2207,72910 m
dict2651351,23290 s14876554 s1501,0874 m923,4765 m
rmorеf3831701,05283 s21193566 s2251,0144 m1825,3287 m
recursion2125981564 s11348434 s744612 m621,3142 m
smt
btor2-bug-16966-26302,4358628,63244 s1,9917,91429 s–––71937,28911 m
btor2-bug-21435-4013,5461,0589,56451 s2,88711,44544 s–––1,18562,06318 m
btor2-bug-16965-1039,7731,49531,3073 m7,59138,4283 m–––95794,13729 m
btor2-bug-19025-69863,7952,772185,32456 m2,00128,10154 m–––1,925491,14553.3 h
btor4-bug-29933-667495,3371,36430,5257 m11,02778,1797 m–––65592,02626 m
btor4-bug-1428-13899162,928712144,59567 m61,394444,4041.6 h–––40755,0251.7 h
btor4-bug-29800-10218224,15170897,58343 m32,617158,74723 m–––449170,15858 m
smlib384a0443,6961722,0973 m4,72317,82616 m2239453 m1578,7428 m
smlib46f14a43,3231722,1263 m3,94314,51313 m2239453 m1578,7428 m
smlibf957ea43,9371511,8413 m3,55611,4559 m2348343 m1578,7638 m
sql
postgresql-1839827712679721 s21875118 s–––1011,86668 s
mysql-1124605382081,4862 m3681,33364 s–––1975,2915 m
sqlite-b17914e5755032332,30032 s3751,16416 s21084618 s1775,6893 m
sqlflex-sqlite-79128645797.9 s1013104.1 s591105.3 s3578624 s
sqlflex-sqlite-165163385049.9 s1353875.2 s41614.5 s3582425 s
sqlflex-sqlite-256104695547.7 s902183.0 s451265.8 s4179125 s
sqlflex-sqlite-62253364329.5 s421191.6 s39584.4 s3542215 s
sqlflex-sqlite-686179586408.7 s1084175.6 s631125.4 s3848317 s
sqlflex-sqlite-80851364309.5 s421171.6 s39604.5 s3042015 s
sqlflex-sqlite-909144836919.5 s1064195.6 s711435.9 s781,53443 s

Table 2. Reduction results for the 75 inputs with a returned word. Sizes are in bytes, without whitespace. AutoDiDact’s calls and time include its inference, but the stage in Table D.1, and HDD’s and C-Reduce’s exclude validation queries. Dashes mark inputs a reducer did not run on. Each output and call count is shaded by its ratio to the smallest in its row: 1× 10× 100× 1000×.

CaseInputAutoDiDact OutputAutoDiDact CallsAutoDiDact Timedrdd Outputdrdd Callsdrdd TimeHDD OutputHDD CallsHDD TimeC-Reduce OutputC-Reduce CallsC-Reduce Time
xml
1.23,974661,32286 s1,0794,11078 s299615 s787,6333 m
3.23,8351491,5802 m1,0353,89675 s11836027 s1,4168,9763 m
4.13,9331402,3082 m8113,49181 s11759553 s21412,0714 m
5.24,0521301,57195 s1,0043,91978 s10418421 s14110,7373 m
071d221-1101,759153,8878 m19,966108,33654 m152814 s28,960142,28477 m
2d4ec80-1108,560634,2213 m19,980108,24435 m478016 s19,437125,68163 m
327c8af-1103,527604,1684 m19,576106,65741 m4823733 s4,426137,32554 m
4c99b96-1104,930623,99314 m20,000108,47157 m10626048 s27,401131,56782 m
8ede045-1106,398604,0653 m19,841108,61636 m4523232 s26,684209,0831.8 h
f053486-1109,614335,23013 m19,381107,77176 m152014 s28,116135,2871.7 h
yaml
9J7A16111380.3 s11410.1 s–––11422.1 s
9FMG36153960.8 s15870.2 s–––152164.8 s
G4RS1771536821.3 s1534070.8 s–––1534237.5 s
FBC91481307021.4 s1304210.8 s–––1301,02916 s
6JQW44213840.7 s21490.1 s–––211854.9 s
96L663464150.8 s46920.2 s–––462325.2 s
3GZX108945351.0 s942720.5 s–––943826.8 s
ZH7C16101360.3 s10440.1 s–––101143.4 s
6FWR2092020.4 s9410.1 s–––9683.8 s
NAT486355821.1 s351890.4 s–––3550611 s

Table 2 (PDF p. 14). Reduction results for the 75 inputs with a returned word (continued)

Every row covers the same 50 inputs, the returned-word inputs with a grammar that HDD reduces, so the reducers also compare with each other through drdd. Ratios are geometric means of reducer / drdd. Ratios below 1 beat drdd. Size counts non-whitespace bytes. Smaller/larger counts inputs on which the reducer’s output is strictly smaller or larger than drdd’s. AutoDiDact’s calls include its inference, and its reduction calls leave it out. The tools’ calls exclude their validation queries.

Against drdd, AutoDiDact’s outputs are 83% smaller with 37% fewer calls, inference included, and 98% smaller with 87% fewer calls on inputs of at least 10 KiB. Below 1 KiB, it makes 1.79×1.79 \times drdd’s calls.

RQ2: Inferred Structure against Format Knowledge

We compare AutoDiDact with HDD, which is given a grammar, and with C-Reduce’s language-agnostic mode, which has a fixed list of bracket pairs and a C lexer built in (Table 3 and Figure 4).

Scatter plots comparing AutoDiDact with HDD and C-Reduce

Figure 4. Without a grammar, AutoDiDact matches HDD’s output sizes at more calls, and it needs fewer calls than C-Reduce. Top: against HDD on its 50 inputs, size points straddle the diagonal, smaller on 28, and call points lie mostly above it, fewer on only 6. Bottom: against C-Reduce’s --not-c mode on its 75 inputs, call points lie mostly below the diagonal, fewer on 59, XML’s size points lie far below it, and the other families’ lie slightly above. Left: output size in non-whitespace bytes. Right: calls, AutoDiDact’s including all inference and HDD’s and C-Reduce’s excluding their validation queries. Axes are logarithmic. Points below the dashed diagonal, where the two are equal, favor AutoDiDact, and colors and marks distinguish families.

HDD. On the 50 inputs with a grammar, AutoDiDact’s outputs are 0.96×0.96 \times HDD’s on geometric mean, smaller on 28 inputs, with a median ratio of 0.92. drdd’s outputs are 9.2×9.2 \times HDD’s on the same inputs. AutoDiDact makes 3.85×3.85 \times HDD’s calls, fewer on 6 inputs, and 1.53×1.53 \times for reduction alone. On XML, AutoDiDact makes 21.18×21.18 \times HDD’s calls for outputs 1.29×1.29 \times as large. Without XML, its outputs are 0.89×0.89 \times HDD’s at 2.51×2.51 \times the calls, and without the 2 Python inputs that ANTLR parses only by recovering from syntax errors, 0.97×0.97 \times at 4.06×4.06 \times.

C-Reduce. Against C-Reduce’s --not-c mode, AutoDiDact uses 54% fewer calls, fewer on 59 of 75, or 0.19×0.19 \times C-Reduce’s for reduction alone, and its outputs are 30% smaller on geometric mean. On XML, C-Reduce leaves most large inputs at tens of kilobytes, and AutoDiDact’s are 0.02×0.02 \times C-Reduce’s. On other families, AutoDiDact’s outputs are 1.23×1.23 \times C-Reduce’s at 0.63×0.63 \times the calls. Overall, AutoDiDact’s are smaller on 26, equal on 11, and larger on 38, with a median ratio of 1.03.

Exact is the share of a family’s inferred tokens equal to a lexical token. Space, Quoted, and Other are the shares strictly inside a lexical token that is a whitespace run, a quoted literal, or any other token. Merged counts inferred tokens that join whole lexical tokens, and Straddling those that cross a lexical boundary with an end inside a lexical token. Recall is the share of the lexer’s token boundaries that the inferred tokens recover. The lexers are the grammars-v4 ANTLR 4 lexers, except Python’s tokenize module and PyYAML’s scanner. Lexical tokens keep every byte: hidden tokens such as comments stay, and skipped text becomes whitespace runs, line breaks, and single characters.

Whitespace. Counting whitespace, AutoDiDact’s outputs are 0.56×0.56 \times C-Reduce’s and 0.85×0.85 \times HDD’s.

AutoDiDact’s outputs are 0.96×0.96 \times HDD’s at 3.85×3.85 \times HDD’s calls, or 1.53×1.53 \times excluding inference. Against C-Reduce’s language-agnostic mode, it makes 54% fewer calls, and its outputs are 30% smaller overall and 1.23×1.23 \times C-Reduce’s outside XML.

RQ3: What Inference Recovers, at What Cost

We check the inferred tokens against real lexers and the pairs against each format’s delimiters, and give each learner’s cost.

The neutral word. Neutral-word discovery returns a single space on all 74 text-based inputs, across ten families. It abstains on 50 of the 51 binary inputs and returns a 10-byte sequence on one ASN.1 input. In a budget ablation on 37 inputs, every text input finds the space from 200 calls on, and 300 calls is the smallest budget that reproduces every main-run outcome.

Discovery spends nearly its whole budget whether it finds a word or abstains: 278 calls on text inputs and 284 on binary ones, taking 11.0 s, all on geometric mean. An abstention costs 284–289 calls before drdd, adding 2.9% to the pooled calls of the abstaining inputs and 18.2% per input on geometric mean, and outweighing the reduction itself on 12 small inputs, by up to 6.9×.

Tokens. On the 69 returned-word inputs from the nine families with a lexer (Table 4), 99.2% of inferred tokens lie within one lexical token, 45.9% matching one exactly, and they recover 97.7% of the lexer’s token boundaries. Of the inferred tokens strictly inside a lexical token, 42.9% lie in quoted literals, such as XML attribute values and Graphviz strings, and 16.3% in whitespace runs. Most of the rest lie in SMT symbols and XML text. 12,492 inferred tokens cross a lexical boundary, 99.6% of them joining whole lexical tokens and 99.7% in XML, Python, and YAML.

FamilyInputsTokens LexicalTokens InferredInferred tokens (%) ExactInferred tokens (%) SpaceInferred tokens (%) QuotedInferred tokens (%) OtherCrossing MergedCrossing StraddlingRecall (%)
c10287,893320,84288.39.30.61.8130>99.9
crashjs102,5264,34251.59.323.615.411099.6
graphviz225,489131,76013.239.146.31.431099.9
lua21,0261,34170.618.71.29.500100.0
python59971,13268.417.17.00.0632287.9
smt10332,269480,20361.5<0.1<0.138.501>99.9
sql101,0071,08989.85.20.94.000100.0
xml10147,295546,15814.98.550.623.712,334987.4
yaml1019121454.74.723.45.124280.7
All69798,6931,487,08145.98.722.921.712,4484497.7

Table 4. AutoDiDact’s inferred tokens against each family’s standard lexer, on the 69 returned-word inputs with a lexer. 99.2% of inferred tokens lie within one lexical token

Tokenization cost. Probing every internal gap alone makes up to one call per gap. With prediction and pooling, tokenization makes 52,943 calls for 2,102,563 gaps, 2.5% as many. This share falls with input size (Figure 6), from 38.9% below 1 KiB to 2.1% at 10 KiB and above. On the largest input, of 224,151 bytes, tokenization makes 454 calls, 0.2% of its gaps.

Tokenization’s calls per gap fall sharply with size

Figure 6. Tokenization’s calls per gap fall sharply with size, becoming negligible for large inputs. Calls fall from 38.9% of gaps below 1 KiB to 2.1% at 10 KiB and above. The plot gives these calls as a percentage of internal gaps on each of the 75 returned-word inputs, against input size, with a logistic fit in log size.

Prediction accuracy. On 20 inputs from 11 families, we also probed every gap alone with the same word (Table 5). In each family, we chose the inputs with the smallest and the largest share of

FamilyCaseGapsPredicted (%)CallsExhaustiveMissedExtraAgreement (%)
asn1asn1...055-nested57972.912552920096.55
c103,07069.35142,58284498.31
csimp...c_4922_43K43,71998.845336,09904099.91
crashjsjava...orithms-1481365.72477503099.63
crashjsexpress-164334.134157900100.00
graphvizissue-27232,14091.21201,75314797.76
lualuajit-9131,24758.54441,1241299.76
lualuajit-111688883.99660200100.00
pdfpdf-fuzzer-jch20715,50499.11214,88508099.48
pdfpdfi...jch207-kw64,54274.24804,07902499.47
pythonalloc1,12455.23507911899.20
pythonrecursion21128.910914401294.31
smtbtor...16966-26302,43492.51612,11300100.00
smtbtor...-19025-69863,79499.526556,08300100.00
sqlmysql-11246053765.915542000100.00
sqlsqlf...sqlite-808504.0394500100.00
xml4.13,93272.45333,73100100.00
xml8ede045-1106,39793.33,09597,25012199.99
yaml6FWR195.3171400100.00
yamlNAT48558.8235700100.00
All251,72894.47,579223,6304625899.88

Table 5. The default tokenizer against exhaustive probing on 20 selected inputs. It makes 3.4% of exhaustive probing’s calls and agrees with it at 99.88% of gaps.

Gaps counts internal offsets, and Predicted is the share of them whose verdict the default tokenizer predicted without a query. Calls and Exhaustive count the oracle calls of the default tokenizer and of probing every gap alone. Missed and Extra count the boundaries the default tokenizer omits or adds relative to exhaustive probing, over all gaps, and Agreement is the share of gaps on which both agree. The total pools gaps.

among those estimated to take under an hour to probe exhaustively. Where only one qualified, we used it. On these inputs, the default tokenizer makes 7,579 calls where exhaustive probing makes 223,630, 3.4% as many, and the two agree at 99.88% of the 251,728 gaps, from 94.3% to 100% per input, and on every gap of the SMT, SQL, and YAML inputs. Of the 304 disagreements, 298 are mispredictions, and the other six lie at gaps settled by pooling. Most are extra boundaries, which exhaustive probing rejects: in a C preprocessor directive, between the adjacent minus signs of C decrements, in Graphviz’s numeric identifiers, in Python indentation, and in PDF keywords.

Pairs. Pair learning admits 4,478 pairs on 59 of the 75 inputs, nearly all the format’s own delimiters. Apart from tags, 96 of the 109 pairs are brackets and quotes: parentheses on every C, Python, SMT, and SQL input, braces, brackets, and quotes in C, JavaScript, and Graphviz, and quotes in Lua and Python. On XML, affix families recover 4,369 start- and end-tag pairs. The conditional operator ? . . . : is admitted on six C inputs, and the seven others are not delimiters of the format. Where no pair is admitted, as on ASN.1, PDF, and most YAML inputs, reduction proceeds over flat tokens.

Pair learning is the cheapest stage. It makes 5,841 calls over all 75 inputs, a median of 71 per input and at most 255, and takes a median of 7.7 s per input.

Where the calls go. Inference makes 11.6% of AutoDiDact’s calls: tokenization 7.7%, discovery 3.1%, and pair learning 0.8%. Its share falls with input size (Figure 5), from 50.1% below 1 KiB to 8.9% at 10 KiB and above. Discovery’s and pair learning’s calls stay nearly constant, and tokenization’s grow roughly with the square root of input size.

Inference’s share of calls falls with input size

Figure 5. Inference’s share of calls falls with input size, from 50.1% below 1 KiB to 8.9% at 10 KiB and above. Discovery and pair learning make nearly constant calls, and tokenization’s grow roughly with the square root of size. Reduction includes shrinking. The dashed line marks one call per gap.

Discovery finds a space on every text input. Inferred tokens recover 97.7% of the lexer’s token boundaries, and pair learning admits the formats’ brackets, quotes, and XML tags. Inference makes 11.6% of AutoDiDact’s calls, and 8.9% at 10 KiB and above.

Discussion

Competitive without a grammar. AutoDiDact receives only what drdd receives, a failing input and its oracle. From these alone, it returns outputs 83% smaller than drdd’s with 37% fewer calls, and this gain makes it competitive with grammar-aware reducers. On the inputs with a grammar, drdd’s outputs are 9.2×9.2 \times HDD’s, and AutoDiDact’s are 0.96×0.96 \times. Against C-Reduce, which builds in a C lexer and a list of bracket pairs, AutoDiDact makes 54% fewer calls for outputs 30% smaller. The inferred structure is small: for the GCC input of § 1, the word and pair tables take 99 bytes, against 18,234 bytes for the C grammar HDD needs. The price is calls against HDD, 3.85×3.85 \times HDD’s in all and 1.53×1.53 \times for reduction alone, so learning the structure accounts for most of the difference. The grammar helps HDD most on XML, whose tokens AutoDiDact must find by probing.

Tolerating errors. A grammar-aware reducer needs a grammar for the format and a parse of the input. HDD ran on only 50 of the 75 inputs, since no grammar was at hand for ASN.1, PDF, YAML, or the other SQL and SMT dialects, and ANTLR parsed 2 Python inputs only by recovering from syntax errors. Failing inputs are often malformed, and AutoDiDact parses nothing. A stray delimiter changes the span count by at most one (§ 3). AutoDiDact thus ran on all 75 returned-word inputs, including a binary ASN.1 input. In this respect, inferred structure goes beyond a grammar.

A minimizer for any fuzzer. Fuzzers minimize the crashing inputs they find at the byte level, as afl-tmin [40] and libFuzzer’s -minimize_crash [23] do, because they cannot assume the target’s input format. With inferred structure, a fuzzer can carry a general minimizer that works on any input. It needs nothing beyond the oracle the fuzzer already has, and where discovery abstains, it falls back to bytes after at most 300 calls.

Inferred against built-in knowledge. Because the structure comes from the oracle, it can also exceed a fixed description of the format: C-Reduce’s bracket list cannot pair XML tags, but affix families learn them. On the other families, C-Reduce also makes changes that no deletion can, through integer reduction and peephole edits, and inferred tokens could guide such edits as they guide shrinking. Ignoring whitespace in these comparisons is conservative, since counting it favors AutoDiDact (§ 7.2).

Why the savings over drdd grow with size. On large inputs, drdd stops at large 1-minimal outputs, such as the GCC input’s 45,061 bytes. Deleting or unwrapping whole spans gets past them. Below 1 KiB, drdd needs only 414 calls on geometric mean, not much more than discovery’s fixed budget, so inference rarely pays for itself. Inference queries also run on the whole input, so inference weighs more in wall time than in calls. With the closing atom scan, AutoDiDact’s calls stay below drdd’s, so the comparison also holds when both outputs are 1-minimal over atoms.

What the oracle reveals. Inference sees only the structure that the failure makes visible. Inferred tokens split a lexical token where the failure does not need it whole, as Section A.1 predicts: a whitespace run accepts the neutral word anywhere, and a comment may split into single bytes because insertions there do not matter. They cross lexical tokens where a lexer places boundaries that the neutral word cannot reach, such as after < in an XML tag or before indentation in Python and YAML. Coupling likewise follows the failure: the conditional operator ? . . . : is admitted because the compiler accepts its halves only together. A genuine pair may yield no witness when every paired edit destroys the failure. An abstention likewise leaves open whether useful structure exists. Such partial structure is safe to use, since the oracle checks every edit during reduction: it guides reduction without having to be a correct lexer or parser. Where the evidence is insufficient, discovery abstains at bounded cost, and reduction falls back to bytes.

Where inference is cheap. Tokenization’s share of calls falls with input size, consistent with larger inputs repeating more contexts. Pair learning would stay a small fraction of all calls even at ten times its cost, which leaves room for a learner that tests more hypotheses or other relations. The remaining overheads are discovery’s fixed budget, which small inputs cannot repay, and tokenizing inputs with little repetition, such as the large XML inputs. Both belong to the current learners, which are one way to infer the targets of § 4.1. Other learners could do better: a word learned on one input of a format could serve the next, and better prediction would cut tokenization further. How cheaply an oracle can reveal structure remains open.

Related Work

Delta debugging. ddmin [41] tests subsets and complements of supplied units, drdd [20] changes its restart schedule while keeping 1-minimality, and ProbDD [35] chooses deletions with a probabilistic model. Our inference supplies units and nesting to any such reducer.

Reduction with format knowledge. HDD [26] reduces a parse tree level by level, as Picire [13, 14] does for ANTLR grammars, with hoisting [34]. Perses [33] uses grammar rules for syntax-preserving deletions and replacements, GTR [12] learns tree transformations from a corpus, and T-Rec [36] reduces within tokens using a language’s lexical syntax. C-Reduce [31] deletes or unwraps brackets from a fixed list among other passes, and Shrink Ray [24] pairs generic passes with format-specific ones. Each obtains units and hierarchy from a grammar, a lexer, a corpus, or built-in knowledge. We obtain them from the failing input and its oracle.

LLM-assisted reduction. LPR [42] alternates a generic reducer with transformations that a large language model proposes, and Yang et al. [38] prompt a model to write a reducer for each failing input. Model queries add cost to every reduction, and the cost grows when a fuzzing campaign yields thousands of inputs. With AutoDiDact reducing them, a model’s effort can go to selecting which inputs to reduce and which failures to investigate.

Grammar inference. GLADE [6] generalizes seed inputs with membership queries, Arvada [19] and TreeVada [4] merge nodes of trees over example inputs, Kedavra [22] infers grammars incrementally, and Crucio [21] scales inference to C, confirming token boundaries by inserting a space after checking that the parser ignores spaces. V-Star [15] is closest to pair learning: it infers call and return tokens from nesting patterns and learns a visibly pushdown grammar. Our coupling tests share its coordinated edits and rejected controls without requiring a visibly pushdown language. These learners assume a parser oracle and positive examples and seek a grammar of the whole language. We have one failing input and a failure oracle, which tests failure preservation and may accept malformed inputs. We discover the separator, learn only the relations reduction uses, abstain when evidence is weak, and check every edit.

Threats to Validity

Internal validity. All reducers use the same oracle for each input, and original and final inputs are checked, though a shared symptom need not identify the same fault. One run per input and reducer cannot separate nondeterminism from the methods’ effects. Parameters are fixed across families but were chosen on these inputs, and the budget ablation covers selected inputs and one parameter.

External validity. The 125 inputs cover 18 families, at most ten per family, largely from existing reproducer collections, some already reduced. They are not independent samples of defects, and other inputs may behave differently. Every text input yielded a space and one binary input another word, so evidence for other words and for binary formats is limited. The comparisons cover one configuration each of HDD and C-Reduce, on cohorts set by discovery and the available grammars, and do not isolate the effects of nesting, hoisting, unwrapping, shrinking, and traversal order.

Construct validity. Agreement with a lexer depends on its conventions for hidden tokens and skipped text, and agreement with exhaustive probing measures fidelity to probing on inputs chosen for affordable probing. Coupling witnesses establish only the contrasts tested. Oracle calls have unequal costs, and wall times come from one machine without repeated trials, so we report both. Byte counts may differ from debugging effort, and ignoring whitespace discounts it in Python and YAML. Per-input results, medians, and win counts expose variation that geometric means hide.

Conclusion

The most widely used fuzzers, such as AFL [9, 40] and libFuzzer [23], know nothing of their targets’ input formats. Yet they must reduce what they find, from corpus seeds to crashing inputs, and their minimizers have so far worked on bytes. This paper removes that limit. A neutral word and delimiter pairs, inferred from an input and its oracle alone, give structured reduction without a grammar. Reduction over them returns outputs 83% smaller than byte-level drdd’s with 37% fewer calls, matches grammar-based HDD in output size, and uses 54% fewer calls than C-Reduce’s --not-c mode. Because AutoDiDACT parses nothing and checks every edit, it accepts whatever a fuzzer finds, malformed inputs included, with any property the fuzzer can check, from a crash to a seed’s coverage. Grammar-agnostic fuzzers can now carry a structure-aware minimizer, for smaller seeds that are cheaper to run and smaller crash inputs that are quicker to diagnose.

AI Use

We used Codex (OpenAI) and Claude Code (Anthropic) primarily to acquire and build benchmark targets, implement and validate oracle wrappers, and write experiment and analysis scripts, including table and figure generators. We also used them for localized implementation cleanup, documentation, debugging, and validation tests, to search for related literature, and to check the paper’s algorithms, arguments, and numerical claims against the implementation and saved results.

Data-Availability Statement

A replication package and prebuilt image are available at doi:10.5281/zenodo.24164465. The package contains the implementation source, benchmark inputs and oracles, experiment and analysis scripts, and saved results.

References

Structural Arguments

The following arguments support § 4.1; Sections B to D give reduction algorithms, inference details, and supplementary results.

Tokens under a Lexer

Let Ψ=F∘L\Psi= F \circ L and let Λ(S)\Lambda(S) be the internal lexical boundaries. Assume that LL erases arbitrary copies of ww inserted at any subset of Λ(S)\Lambda(S), while inserting either control, κ\kappa or κ∣w∣\kappa^{|w|}, there is rejected. Erasure preserves L(S)L(S), so every lexical boundary is selective and, when Λ(S)≠∅\Lambda(S) \ne\varnothing, ww is neutral with G=Λ(S)G = \Lambda(S). By (1),

Bw(S)=Λ(S)∪{g∉Λ(S):F(L(S⊕gw))=✓}.(4)B_w(S) = \Lambda(S) \cup\{g \notin\Lambda(S) : F(L(S \oplus_g w)) = \checkmark\}. \tag*{(4)}

Exhaustive probing therefore refines the lexical partition; prediction and pooling need not. Erasure ensures composition at lexical boundaries, but not at extra boundaries within tokens, where insertions can interact.

Delimiter Pairs under a Parser

Assume that SS is matched for (◃,▹)(\triangleleft, \triangleright) and the oracle rejects every unmatched input. The paired edits of (3), span deletion, and unwrapping preserve matchedness: for distinct delimiters, each replacement and the original span have equal opening and closing counts and no prefix with more closes than opens, preserving matchedness in the walk of (2). For symmetric delimiters, each edit changes the count by an even number. Each control instead changes the total delimiter parity and is rejected. Coupling therefore reduces to acceptance of a paired edit; matchedness alone does not ensure that acceptance.

Reduction Algorithms and Guarantees

Assume a deterministic Boolean oracle. Queries count requests before caching and hence also bound oracle executions.

Matching and Tree Construction

Stability. For fixed admitted pairs, let m(S)m(S) be the largest matching size. Deleting delimiter ii removes at most one pair from a largest matching; every matching of the shorter sequence is also valid before deletion. Hence m(S)−1≤m(S∖{i})≤m(S)m(S) - 1 \le m(S \setminus\{i\}) \le m(S). Insertion reverses this argument, so kk inserted or deleted delimiters change the size by at most kk. Admitting another pair enlarges the feasible set and cannot decrease m(S)m(S). These bounds concern span counts, not identities.

Construction. Some largest matching contains all pairs made by the stack pass of Algorithm B.1. When it pairs adjacent unmatched delimiters, an optimal matching can add their pair if neither is used, or swap it for the existing pair if one is used. Pairing both elsewhere would cross unless a token serves both roles, so two-sided tokens are skipped; for a symmetric pair, the two partners can instead pair with each other. The pass is linear and complete on well-nested input without two-sided tokens. An O(m3)O(m^3) interval program matches the remaining delimiters r1,…,rmr_1,\ldots,r_m. Let μ(i,j)\mu(i,j) be the largest matching size on ri,…,rj−1r_i,\ldots,r_{j-1}, with μ(i,j)=0\mu(i,j)=0 for j−i≤1j-i\le1; otherwise,

μ(i,j)=max⁡(μ(i+1,j), max⁡i<k<j(ri,rk) admitted(1+μ(i+1,k)+μ(k+1,j))).(5)\mu(i,j) = \max\left(\mu(i+1,j),\ \max_{\substack{i<k<j\\(r_i,r_k)\ \text{admitted}}} \left(1+\mu(i+1,k)+\mu(k+1,j)\right)\right). \tag*{(5)}

since rir_i is unpaired or paired with some rkr_k, separating the inside and following intervals. Traceback skips rir_i on ties; otherwise it takes the least maximizing kk and recurses inside and after that pair.

Algorithm B.1 TREE: match delimiters into spans

Input: Tokens t1⋯tnt_1 \cdots t_n, admitted pairs PP

Output: The root of the span tree

A two-sided token both opens and closes pairs of PP and occurs in a nonsymmetric pair.

1: M←∅M \leftarrow\varnothing, and r←r \leftarrow empty list ▹\triangleright matched pairs, unmatched delimiters

2: for each position ii whose token is a delimiter of PP, in order do

3: &nbsp;&nbsp;&nbsp;&nbsp;Append ii to rr

4: &nbsp;&nbsp;&nbsp;&nbsp;if rr ends in j,ij,i with (tj,ti)∈P(t_j,t_i) \in P, and neither tjt_j nor tit_i is two-sided, then add (j,i)(j,i) to MM, and remove jj and ii from rr

5: Complete MM on rr using (B.1) and its traceback

6: Start a stack with a delimiterless root

7: for each token position ii, in order do

8: &nbsp;&nbsp;&nbsp;&nbsp;if ii opens a pair of MM then create and push a child of the top node

9: &nbsp;&nbsp;&nbsp;&nbsp;else if ii closes a pair of MM then close and pop the top node

10: &nbsp;&nbsp;&nbsp;&nbsp;else append ii to the top node’s items

11: return the root

Base Reducer

Algorithm B.2 gives drdd [20] with a closing-scan budget RR: laminar reduction uses R=1R = 1 per node, shrinking R=∞R = \infty.

Algorithm B.2 drdd: chunk sweeps and closing scans

Input: Accepted unit sequence UU, oracle Ψ\Psi, closing-scan budget RR

Output: An accepted subsequence, 1-minimal over units if R=∞R = \infty

1: s←⌊∣U∣/2⌋s \leftarrow\lfloor|U|/2 \rfloor

2: while s>1s > 1 do

3: &nbsp;&nbsp;&nbsp;&nbsp;Sweep(ss), and s←⌊s/2⌋s \leftarrow\lfloor s/2 \rfloor

4: repeat

5: &nbsp;&nbsp;&nbsp;&nbsp;Sweep(1)

6: until the sweep deletes nothing, or RR sweeps of size 1 have run

7: return UU

8: procedure Sweep(ss)

9: &nbsp;&nbsp;&nbsp;&nbsp;Partition UU into chunks c1,…,ckc_1, \ldots, c_k of ss units, the last possibly shorter

10: &nbsp;&nbsp;&nbsp;&nbsp;for i←1i \leftarrow1 to kk do

11: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if Ψ(U∖ci)=✓\Psi(U \setminus c_i) = \checkmark then U←U∖ciU \leftarrow U \setminus c_i

Laminar Reduction

Promoted spans join the current level in Algorithm B.3 and are processed in their new positions.

Fixpoint. Each accepted edit removes a nonempty token, so at most nn traversals change an input of nn tokens. An unchanged traversal rejects every single-item deletion, permitted hoist, and unwrapping against the final input, proving local minimality despite R=1R = 1. An early stop combines the unchanged prefix through stop with the suffix checked after the preceding traversal’s last change. Neither oracle monotonicity nor correct inferred structure is needed.

Query cost. With R=1R = 1, drdd costs O(k)O(k) queries for kk items. A traversal processes each node once, including promoted nodes; their item lists total O(n)O(n) entries. Charge each hoist query to its offered descendant: only its nearest remaining ancestor of the same pair can offer it, and ancestors are processed first. Each descendant is thus offered at most once per traversal; each span also costs at most one unwrapping query. Each traversal costs O(n)O(n), and at most nn changing traversals plus a final check cost O(n2)⊆O(N2)O(n^2) \subseteq O(N^2).

Shrinking

Algorithm B.4 Shrinking: shorten each distinct token at all occurrences

Input: Tokens t1⋯tnt_1 \cdots t_n left by laminar reduction, oracle Ψ\Psi

Output: The shrunk tokens

  1. for each distinct token uu with ∣u∣>1|u| > 1, in order of first occurrence do

  2. O←{i:ti=u}O \leftarrow\{i : t_i = u\} &nbsp;&nbsp; fixed while reducing uu

  3. Reduce uu’s atoms by drdd with R=∞R = \infty, testing each u′u' at all positions OO in the current input and keeping accepted edits

  4. return t1⋯tnt_1 \cdots t_n without empty tokens

For initial distinct-token lengths ℓ1,…,ℓd\ell_1, \ldots, \ell_d, shrinking costs O(∑iℓi2)⊆O(N2)O(\sum_i \ell_i^2) \subseteq O(N^2), since ∑iℓi≤N\sum_i \ell_i \le N. Later token edits may invalidate an earlier token’s local fixpoint.

Inference Procedures

These subroutines complete Algorithms 1 to 3. Discovery’s budget counts executions, so cached verdicts cost no calls.

Neutral-Word Discovery

Candidate enumeration. CANDIDATES enumerates maximal repeats as internal intervals of a suffix array’s longest-common-prefix tree whose occurrences have at least two distinct preceding atoms. Children give distinct following atoms; input ends count as distinct markers. Prefix doubling takes O(Nlog⁡2N)O(N \log^2 N) comparisons, Kasai’s longest-common-prefix construction O(N)O(N) time, and merging preceding-atom sets smaller into larger O(Nlog⁡N)O(N \log N) insertions, without queries.

Runs and classes. Maximal consecutive copies of ρ(u)\rho(u) on either side of an offset form a run; its two adjacent atoms, or end markers, are its surroundings. Inserting uu at any copy boundary within a run gives the same input. A word’s class is ⌊log⁡2∣ρ(u)∣⌋\lfloor\log_2 |\rho(u)| \rfloor.

Schedule. SCHEDULE visits distinct offsets in this order:

  1. the starts of the leading candidate’s first and last occurrences;

  2. both ends of the runs around each source word’s first and last occurrences, grouped by class, each class shuffled with seed 0, taking one offset per class in turn;

  3. remaining internal offsets, shuffled, in class 0.

Observation. Rows accepting κ\kappa earn zero credit but enter the class mean; incomplete rows are discarded (Algorithm C.1).

Algorithm C.1 OBSERVE: collect controlled evidence

Input: SS, oracle Ψ\Psi, candidate words WW, control κ\kappa, scheduled offsets, call limit lim\mathit{lim}

Output: Complete observation rows DD

Before a query would exceed lim\mathit{lim} calls, return DD.

1: D←D \leftarrow empty list 2: for each scheduled pair (b,g)(b,g) of class and offset do 3: Cg←∅\quad C_g \leftarrow\varnothing 4: \quadif Ψ(S⊕gκ)=X\Psi(S \oplus_g \kappa) = \mathrm{X} then 5: \qquadQuery Ψ(S⊕gu)\Psi(S \oplus_g u) for each u∈Wu \in W in order; U←U \leftarrow the accepted words 6: v1←X\qquad v_1 \leftarrow\mathrm{X} 7: \qquadfor each distinct length ℓ>1\ell> 1 in UU do 8: vℓ←Ψ(S⊕gκℓ)\qquad\quad v_\ell\leftarrow\Psi(S \oplus_g \kappa^\ell) 9: Cg←{u∈U:v∣u∣=X}\qquad C_g \leftarrow\{u \in U : v_{|u|} = \mathrm{X}\} 10: \quadAppend (b,g,Cg)(b,g,C_g) to DD 11: return DD

Scoring. Let W=(u0,u1,…)W = (u_0, u_1, \ldots) be the candidate order, rr its number of families, and kg=∣{ρ(u):u∈Cg}∣k_g = |\{\rho(u) : u \in C_g\}|. For nonempty DD, let DbD_b be the rows of class bb, B\mathcal{B} the observed classes, and λi=log⁡((i+1)(i+2))\lambda_i = \log((i+1)(i+2)). Define

wi(g)={log⁡r+1kg,ui∈Cg,0,otherwise,w_i(g) = \begin{cases} \log\dfrac{r+1}{k_g}, & u_i \in C_g,\\ 0, & \text{otherwise,} \end{cases}
si=mean⁡b∈B mean⁡g∈Db wi(g),s_i = \underset{b \in\mathcal{B}}{\operatorname{mean}}\ \underset{g \in D_b}{\operatorname{mean}}\ w_i(g),
ei=∣D∣si−1[∣D∣<N−1]λi.(6)e_i = |D|s_i - \mathbf{1}[|D| < N-1]\lambda_i. \tag*{(6)}

The +1+1 keeps credit positive even when every family earns it; the rank penalty vanishes after all internal offsets have complete rows. For r=3r = 3, crediting u0u_0 alone at one of two class-0 rows gives weights (log⁡4,0)(\log4, 0); crediting it alongside one other family at the sole class-1 row gives log⁡2\log2. Then

s0=12(12log⁡4+log⁡2)=log⁡2:s_0 = \frac{1}{2}\left(\frac{1}{2}\log4 + \log2\right) = \log2:

classes weigh equally despite unequal samples. If offsets remain unobserved, e0=3log⁡2−log⁡2=log⁡4e_0 = 3\log2 - \log2 = \log4; later candidates pay a larger penalty.

Confirmation. SITES scans crediting rows in input order, retaining one offset per run and up to four distinct surroundings. With fewer than two surroundings, it adds further runs to reach two sites where possible. With two or three sites, REFINESITES probes at most two occurrences with new surroundings, in input order, appending accepted sites up to four, without controls. REUSETESTS takes the first five of these insertions at the sites of TT, in order:

  • one site: 2, 4, 8, 16, and 32 copies there;

  • two sites: two copies at both together, then two at each alone, then four at each alone;

  • three or four sites: one copy at each site of every triple, in lexicographic order of indices in TT, then two copies at each site alone, then four at each alone.

Two words need at most 2(2+5)=142(2+5)=14 confirmation calls, within the 16-call reserve; unspent observation calls are also available.

Tokenization

Contexts. At offset gg, let ℓk,rk\ell_k,r_k be its kk atoms to the left and right, v±=V[g±1]v^{\pm}=V[g\pm1], and ρs\rho_s the share of classified offsets within ss atoms, excluding gg, that are boundaries. Bucket ρs\rho_s as none, at most a third, at most two thirds, fewer than all, and all. Estimate uses these 14 contexts, read down each column:

  1. (v−,v+)(v^-,v^+)  6. (ℓ2,r1)(\ell_2,r_1)  11. (ℓ3,r3)(\ell_3,r_3)

  2. ℓ1\ell_1    7. (ℓ1,r1,ρ32)(\ell_1,r_1,\rho_{32})  12. (ℓ1,r1,ρ16)(\ell_1,r_1,\rho_{16})

  3. r1r_1     8. (ℓ1,r2)(\ell_1,r_2)  13. (ℓ1,r1,ρ8)(\ell_1,r_1,\rho_8)

  4. (ℓ1,r1)(\ell_1,r_1) 9. (ℓ2,r2)(\ell_2,r_2)  14. (ℓ1,r1,v−,v+)(\ell_1,r_1,v^-,v^+)

  5. ℓ3\ell_3    10. r2r_2

Out-of-range atoms, unknown verdicts, and empty density neighborhoods use markers. VV includes predictions and tentative pooled boundaries as well as settled verdicts.

Estimate. M[j,h]=(t,b)M[j,h]=(t,b) records tt settled offsets whose jjth context had key hh at settlement, bb of them boundaries. For the keys hjh_j at gg, write (tj,bj)=M[j,hj](t_j,b_j)=M[j,h_j] and compute

p0=12,pj=bj+2pj−1tj+2,p^=σ(∑j=114αjlogit⁡pj).(7)p_0=\frac{1}{2},\qquad p_j=\frac{b_j+2p_{j-1}}{t_j+2},\qquad\hat{p}=\sigma\left(\sum_{j=1}^{14}\alpha_j\operatorname{logit}p_j\right). \tag*{(7)}

Each rate is smoothed toward its predecessor with weight two; an unseen context leaves it unchanged. Initialize α=(0,…,0,1)\boldsymbol{\alpha}=(0,\ldots,0,1), giving p^=p14\hat{p}=p_{14}. On settling verdict v∈{0,1}v\in\{0,1\}, first update VV and recompute the context keys and estimates from the current VV, MM, and weights. Take the log-loss gradient step αj←αj+0.01(v−p^)logit⁡pj\alpha_j\leftarrow\alpha_j+0.01(v-\hat{p})\operatorname{logit}p_j, then update (t,b)←(t+1,b+v)(t,b)\leftarrow(t+1,b+v) in each of the 14 entries. Clip probabilities to [10−6,1−10−6][10^{-6},1-10^{-6}] before log-odds, and log-odds to [−30,30][-30,30] before σ\sigma.

Information. Write H(q)=−qlog⁡2q−(1−q)log⁡2(1−q)H(q)=-q\log_2q-(1-q)\log_2(1-q). Under the estimates, predicting at p^≥0.98\hat{p}\ge0.98 or p^≤0.02\hat{p}\le0.02 skips queries worth at most H(0.02)≈0.14H(0.02)\approx0.14 bits. A pool triggered by ∏p^≤1/2\prod\hat{p}\le1/2 has estimated acceptance probability in [1/4,1/2][1/4,1/2], since the preceding product exceeds 1/21/2 and each pooled estimate is at least 1/21/2. Its estimated yield is therefore at least H(1/4)≈0.81H(1/4)\approx0.81 bits.

Pooling. Under factorization (§ 4.3), a rejected pool contains a non-boundary. TestPool maintains such a set TT, splitting by doubt, −∑log⁡p^h-\sum\log\hat{p}_h. It queries the shortest proper prefix holding at least half the doubt, or all but the last offset if no proper prefix does. After an accepted prefix, the suffix still contains a non-boundary.

For estimates (0.9,0.8,0.8,0.8)(0.9,0.8,0.8,0.8), the fourth offset triggers a query (product 0.46080.4608). The shortest prefix holding half the doubt comprises the first three offsets. Rejecting the pool and accepting that prefix classifies three boundaries and one non-boundary in two queries.

Query bound. Since each pooled estimate is below 0.980.98 and 0.9835<1/20.98^{35}<1/2, pools hold at most 35 offsets. Each outer iteration settles at least one offset using one pool test and at most 34 split queries. Individual probes also settle an offset, giving at most 35(N−1)=O(N)35(N-1)=O(N) queries for N≥1N\ge1.

Algorithm C.2 TestPool: test the pool

Input: Pool RR with estimates p^h\hat{p}_h, verdict map VV

  1. while RR is nonempty do

  2. T←RT \gets R, and R←R \gets empty

  3. if Ψ\Psi accepts SS with ww inserted at every offset of TT then

  4. V[h]←✓V[h] \gets\checkmark for each h∈Th \in T

  5. else

  6. while ∣T∣>1\lvert T\rvert> 1 do

  7. Split T=T1T2T = T_1T_2 by half the doubt, as above

  8. if Ψ\Psi accepts SS with ww at every offset of T1T_1 then

  9. V[h]←✓V[h] \gets\checkmark for each h∈T1h \in T_1, and T←T2T \gets T_2

  10. else

  11. Prepend T2T_2 to RR, and T←T1T \gets T_1

  12. V[h]←XV[h] \gets\mathsf{X} for the offset hh left in TT

Pair Learning

Hypotheses. Enumerate single pairs by occurrence-count classes x≤yx \le y. For families, split each non-blank token at every inner position and group prefixes, or suffixes, sharing at least two nonempty names.

Candidate intervals. Assign each position to its innermost strictly enclosing admitted interval, or to the outside region; an interval’s own delimiters belong to its surrounding region. Symmetric pairing also starts at the second occurrence when a region has an odd count, allowing a stray occurrence, and drops intervals strictly nested in one with an earlier start.

Balance prior. For uu openings, vv closings, and dd unmatched closings, a uniform shuffle leaves more than dd closings unmatched exactly when its walk (+1+1 per opening, −1-1 per closing) reaches −(d+1)-(d+1). Reflecting up to the first visit there gives a bijection to shuffles with u+d+1u+d+1 openings and v−d−1v-d-1 closings, of which there are (u+vv−d−1)\binom{u+v}{v-d-1}. Hence

Balance⁡(u,v,d)=−log⁡(1−(u+vv−d−1)(u+vv)).(8)\operatorname{Balance}(u,v,d)=-\log\left(1-\frac{\binom{u+v}{v-d-1}}{\binom{u+v}{v}}\right). \tag*{(8)}

with out-of-range binomial coefficients zero. Families sum Balance⁡\operatorname{Balance} over names, using their counts and unmatched closings on the shared stack. This sum is heuristic: one name’s stray delimiters can block another’s matches.

Parity prior. For a symmetric hypothesis occurring in rr regions, kk of them odd, independent region parities with probability 1/21/2 give

Parity⁡(r,k)=−log⁡(2−r∑i=0k(ri)).(9)\operatorname{Parity}(r,k)=-\log\left(2^{-r}\sum_{i=0}^{k}\binom{r}{i}\right). \tag*{(9)}

The cap log⁡(1+∣U∣)\log(1+\lvert U\rvert) of § 4.4 equals Balance⁡(∣U∣,∣U∣,0)\operatorname{Balance}(\lvert U\rvert,\lvert U\rvert,0).

Ranking bounds. Scoring scans occurrences, so Hypotheses⁡\operatorname{Hypotheses} visits count-class pairs and families by decreasing upper bounds on their priors:

log⁡y+1y−x+1andlog⁡(1+∑(◃,▹)∈Hmin⁡(∣S∣◃,∣S∣▹)).(10)\log\frac{y+1}{y-x+1} \qquad\text{and}\qquad \log\left(1+\sum_{(\triangleleft,\triangleright)\in H}\min(\lvert S\rvert_{\triangleleft},\lvert S\rvert_{\triangleright})\right). \tag*{(10)}

For counts x≤yx \le y, the smallest feasible dd is y−xy-x with xx openings, or 00 with yy openings; either gives −log⁡(1−x/(y+1))-\log(1-x/(y+1)). Since Balance⁡\operatorname{Balance} decreases with dd, this bounds both orientations. The family bound follows from the cap and ∣U∣≤∑min⁡(∣S∣◃,∣S∣▹)\lvert U\rvert\le\sum\min(\lvert S\rvert_{\triangleleft},\lvert S\rvert_{\triangleright}). A min-heap retains the KK best hypotheses, replacing only on strict improvement; stop when the next bound falls below its minimum. Final ties follow discovery order. Symmetric hypotheses are all scored.

Sensitivity. Sensitive duplicates each distinct delimiter of one representative pair at its occurrence nearest a multi-atom token, measuring distance in token positions. Ties, or absence of multi-atom tokens, select the earliest occurrence. Multi-atom tokens mark restrictive surroundings. Tests are individual and may use unrelated occurrences.

Confirmation. Coupled queries controls only after a paired edit is accepted, the second only if the first is rejected. In the empty-or-delete row, deletion is tried only if emptying is rejected. This costs at most three queries per row, four for empty-or-delete, and ten per interval. Test’s context is an interval’s tokens plus one on either side. Spread samples fractions 0, 1/2, 1/4, 3/4, . . . of the list length, the van der Corput binary-digit-reversal sequence, rounding down and stepping cyclically past used indices.

Algorithm C.3 Test: seek two coupling witnesses

Input: Compatible candidate intervals AA, patience π\pi

Output: true after two coupling witnesses, false otherwise

  1. L←AL \leftarrow A sorted by (length, position), retaining the first interval per context

  2. Reorder LL with Spread(∣L∣|L|), and hits←0hits \leftarrow0

  3. for j=1,…,min⁡(∣L∣,2π)j = 1, \ldots, \min(|L|, 2\pi) do

  4. if Coupled(LjL_j) then hits←hits+1hits \leftarrow hits + 1

  5. if hits=2hits = 2 then return true

  6. if j=πj = \pi and hits=0hits = 0 then return false

  7. return false

Query bound. Each of at most 2K2K hypotheses uses at most two sensitivity queries and 2π⋅102\pi\cdot10 coupling queries. The cap gives π≤2+ln⁡(1+N)\pi\le2 + \ln(1 + N), hence at most 2K(2+20(2+ln⁡(1+N)))=O(Klog⁡N)2K(2 + 20(2 + \ln(1 + N))) = O(K \log N) queries.

Supplementary Evaluation

Table Table D.1 decomposes the costs in Table 2; Tables D.2 and D.3 detail the budget sweep and exceptional admissions.

CaseInputDiscovery CallsDiscovery TimeTokenization CallsTokenization TimePair learning CallsPair learning TimeLaminar reduction OutputLaminar reduction CallsLaminar reduction TimeShrinking OutputShrinking CallsShrinking Time
asn1
asn1-aah055-nested58028717 s1258.4 s10.1 s116261.6 s1121846.3 s
c
023,62328837 s60681 s17131 s5701,7014 m45726628 s
103,07129033 s51466 s19432 s36990290 s28122625 s
tree-ssa-structalias_c_4773_96K97,65828922 s73375 s10111 s2131,77140 s1511291.5 s
tree-vect-transform_c_6496_55K55,92328812 s1,07256 s1176.2 s1604,0903 m114911.7 s
fold-const_c_8943_23K23,17128912 s49426 s1195.3 s1841,42830 s1011171.2 s
recog_c_1990_63K63,50928913 s51835 s825.9 s2141,50445 s1381401.5 s
simplify-rtx_c_4922_43K43,7202898.2 s45319 s1134.6 s2142,03458 s1351401.6 s
gimple_c_2343_122K124,59328824 s9882 m839.2 s2088,79511 m1421484.7 s
emit-rtl_c_1950_75K76,26328916 s71672 s939.9 s2351,45066 s1551422.0 s
ira-emit_c_371_17K16,4242898.4 s45517 s1184.4 s3502,09745 s1991512.5 s
crashjs
71,01228968 s33261 s16328 s2308302 m15916828 s
1083028963 s31459 s14426 s1625542 m11314025 s
commander-477828945 s37162 s7812 s24452481 s16617226 s
commander-311,05528946 s47379 s11117 s22633850 s15616025 s
javascript-algorithms-574528959 s34261 s8414 s32755292 s22026845 s
javascript-algorithms-1481428958 s24741 s7112 s29437964 s25224791 s
moment-18002892 m3252 m10529 s1876534 m18114938 s
moment-171,3402892 m4572 m13646 s2216524 m18823462 s
express-164428964 s34167 s6914 s10234662 s9813724 s
express-4890328960 s42579 s14932 s12734467 s11712923 s
graphviz
issue-1436165,58328998 s11,2972.1 h15880 s2,47345,26362 m2,27093335 s
issue-27232,14128916 s1206.5 s1195.9 s9046819 s90150.3 s
lua
luajit-9131,24828915 s44419 s1514.3 s13038012 s72611.7 s
luajit-111688928813 s964.1 s980.9 s3911,84139 s377621.1 s
pdf
pdf-fuzzer-aah05215,42128932 s22624 s19530 s11867931 s118301.0 s
pdf-fuzzer-jch20715,50528911 s121.4 s25513 s71163.6 s700.0 s
pdfimages-jch207-kw64,5432915.8 s48010 s2305.8 s31062.0 s300.0 s
pdftoppm-aah05215,49529115 s34425 s19222 s14367923 s139701.7 s
pdftoppm-jch20715,53228911 s31314 s2269.8 s80681619 s7943,08990 s
python
ackermann48328830 s17424 s353.3 s15149842 s1231188.7 s
alloc1,12528823 s35032 s14411 s4001,26897 s30432323 s
dict26528821 s12911 s896.5 s13661044 s1351168.0 s
rmroref38328824 s19417 s433.4 s20535426 s17017312 s
recursion21228823 s1099.4 s635.2 s6229022 s59654.7 s
smt
btor2-bug-16966-26302,4352891.0 s1610.8 s330.2 s1,0967,88241 s8622671.0 s
btor2-bug-21435-4013,5462891.1 s1901.2 s400.3 s3148,68847 s1,0583571.4 s
btor2-bug-16965-1039,7732891.2 s2201.9 s160.2 s1,85330,3173 m1,4954652.0 s
btor2-bug-19025-69863,7952894.1 s2659.6 s155.9 s3,689183,76655 m2,7729876.2 s
btor4-bug-29933-667495,3372893.3 s4459.5 s14228 s1,60829,2117 m1,3644381.7 s
btor4-bug-1428-13899162,9282895.8 s27013 s1164 s844143,76666 m7122591.0 s
btor4-bug-29800-10218224,1512898.0 s45421 s1183 m89496,39839 m7083241.2 s
smtlib384a04c0043,69628915 s65778 s517.7 s3389955 s1721046.0 s
smtlib46f14a43,32328914 s65978 s7812 s33899654 s1721046.0 s
smtlib957ea43,93728914 s67980 s7812 s28870140 s151945.3 s
sql
postgresql-183982772897.2 s982.9 s481.7 s1922516.4 s1261113.2 s
mysql-11246053828821 s15515 s10114 s25774539 s20819718 s
sqlite-b794e45955032884.0 s1502.1 s851.2 s2471,62523 s2331512.1 s
sqlflex-sqlite-791282893.8 s741.0 s250.4 s711181.6 s64731.0 s
sqlflex-sqlite-1651632883.8 s741.0 s200.3 s39811.1 s38400.6 s

Table D.1. Per-input stage costs on the 75 returned-word inputs. Sizes are in bytes; outputs exclude whitespace. Calls and times are per stage; Table 2 sums all five.

CaseInputDiscovery CallsDiscovery TimeTokenization CallsTokenization TimePair learning CallsPair learning TimePair learning OutputLaminar reduction CallsLaminar reduction TimeLaminar reduction OutputShrinking CallsShrinking Time
sqlflex-sqlite-2561042893.9 s590.8 s200.3 s691131.6 s69731.1 s
sqlflex-sqlite-622532893.8 s350.5 s110.2 s37620.9 s36350.5 s
sqlflex-sqlite-6861792893.8 s951.3 s140.2 s581792.4 s58630.9 s
sqlflex-sqlite-808512893.8 s390.6 s90.2 s37580.8 s36350.5 s
sqlflex-sqlite-9091442893.9 s831.2 s240.4 s842213.0 s83741.0 s
1.23,97428922 s50530 s7711 s6637119 s66804.1 s
3.23,83528923 s50535 s6411 s15754532 s1491775.9 s
4.13,93328923 s53333 s6411 s1501,29258 s1401305.9 s
5.24,05228920 s50130 s8212 s13154027 s1301596.9 s
071d221-1101,75928942 s3,4526 m2916 s1510614 s15114.1 s
2d4ec80-1108,56028919 s3,19899 s3210 s6366339 s63393.6 s
327c8af-1103,52728927 s3,2823 m4015 s6051336 s60444.4 s
4c99b96-1104,93028984 s3,35211 m3523 s6625233 s62654.1 s
8ede045-1106,39828824 s3,0952 m3713 s7060237 s60435.5 s
f053486-1109,61428974 s4,72712 m2415 s3315718 s33334.3 s
9J7A16850.2 s130.0 s20.0 s11300.1 s1180.0 s
9FMG362880.5 s170.0 s100.0 s15690.1 s15120.0 s
G4RS1772900.6 s600.1 s90.0 s153350.1 s1532880.6 s
FBC91482880.5 s820.2 s90.0 s130650.1 s1302580.5 s
6JQW442880.5 s370.1 s00.0 s21240.0 s21350.1 s
96L6632890.5 s320.1 s00.0 s4660.0 s46880.2 s
3GZX1082890.5 s500.1 s270.1 s94390.1 s941300.3 s
ZH7C16980.2 s110.0 s00.0 s10210.0 s1060.0 s
6FWR201510.3 s170.0 s00.0 s1090.0 s9250.1 s
NAT4862880.5 s230.1 s610.1 s351930.4 s35170.0 s

Table D.1 (PDF p. 31). Per-input stage costs on the 75 returned-word inputs (continued). Sizes are in bytes; outputs exclude whitespace. Calls and times are per stage.

Discovery budget. Each family contributes its smallest and largest inputs and any with a minority found/abstained outcome in the main run: 37 inputs, 20 text and 17 binary. Only the budget varies; seed 0 and the 16-call confirmation reserve are fixed. Table D.2 gives the tested grid behind the thresholds in § 7.3. At 50 and 100 calls, C’s 10 and PDF’s pdftoppm-jch207 abstain. At 600, only asn1-aah055-nested differs from the main run, returning four zero bytes instead of its 10-byte word: more budget need not preserve the choice.

BudgetTextBinarySame
5018/200/1734/37
10018/200/1734/37
20020/200/1736/37
30020/201/1737/37
40020/201/1737/37
60020/201/1736/37

Table D.2. Discovery budget sweep. Text and Binary count inputs returning a word. Same counts identical words or abstentions to the main run.

FamilyInputOpenClose
crecog_c_1990_63K**
csimplify-rtx_c_4922_43K==
pythonackermann−ans
pythonmroref:'
smtbtor2-bug-21435-401ite#b1
sqlsqlflex-sqlite-909rt0
yamlNAT4\n\n

Table D.3. Admitted pairs other than format delimiters and conditional operators. Token spellings are literal; \n denotes a newline.

Output size against input size. Figures D.1 and D.2 plot output size against input size, for drdd and AutoDiDact and for AutoDiDact and the format-aware tools. drdd’s outputs grow almost in step with the input, to a median of 18,345 bytes on the 26 inputs of at least 10 KiB. On the same inputs, AutoDiDact’s outputs have a median of 141 bytes, close to C-Reduce’s 157. HDD’s median is 149 bytes on the 18 of these inputs it covers.

Oracle calls against input size. Figures D.3 and D.4 plot oracle calls against input size for the same reducers. drdd’s calls grow with the input, to a median of about 108,000 on the 26 inputs of at least 10 KiB. On the same inputs, AutoDiDact’s calls, inference included, have a median of about 3,900, below C-Reduce’s 8,750. HDD’s median is 945 on the 18 of these inputs it covers.

Output size against input size for drdd and AutoDiDact

Figure D.1. Output size against input size for drdd and AutoDiDact on the 75 returned-word inputs, in non-whitespace kB. drdd’s outputs grow with the input, and AutoDiDact’s stay flat. Marks distinguish families, and the dashed diagonal marks no reduction.

Output size against input size for AutoDiDact, HDD, and C-Reduce

Figure D.2. Output size against input size for AutoDiDact, HDD, and C-Reduce, on the axes of Figure D.1. All three stay flat, except C-Reduce on XML.

Oracle calls against input size for drdd and AutoDiDact

Figure D.3. Oracle calls against input size for drdd and AutoDiDact on the 75 returned-word inputs. AutoDiDact’s calls include its inference. drdd’s calls grow with the input, and AutoDiDact’s stay low except on five SMT inputs and one Graphviz input.

Oracle calls against input size for AutoDiDact, HDD, and C-Reduce

Figure D.4. Oracle calls against input size for AutoDiDact, HDD, and C-Reduce, on the axes of Figure D.3. HDD makes fewer calls than AutoDiDact on 44 of its 50 inputs, and AutoDiDact fewer than C-Reduce on 59 of 75.

References

  1. [1]Alfred V. Aho and Thomas G. Peterson. 1972. A Minimum Distance Error-Correcting Parser for Context-Free Languages. SIAM J. Comput. 1, 4 (1972), 305–312. doi:10.1137/0201022DOI
  2. [2]Junwen An, Kabilan Mahathevan, and Manuel Rigger. 2026. Artifact for Paper “Dialect-Agnostic SQL Parsing via LLM-Based Segmentation”. Zenodo. doi:10.5281/zenodo.18975512DOI
  3. [3]ANTLR grammars-v4 contributors. 2025. grammars-v4: Grammars Written for ANTLR 4. https://github.com/antlr/grammars-v4/tree/82740f3f1031d56a1141ff4a8ac098aff6644181 Pinned revision used by the HDD baseline.
  4. [4]Mohammad Rifaat Arefin, Suraj Shetiya, Zili Wang, and Christoph Csallner. 2024. Fast Deterministic Black-box Context-free Grammar Inference. In Proc. Int. Conf. Softw. Eng. (ICSE). ACM. doi:10.1145/3597503.3639214
  5. [5]Arturs Backurs and Krzysztof Onak. 2016. Fast Algorithms for Parsing Sequences of Parentheses with Few Errors. In Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems (PODS). 477–488. doi:10.1145/2902251.2902304DOI
  6. [6]Osbert Bastani, Rahul Sharma, Alex Aiken, and Percy Liang. 2017. Synthesizing Program Input Grammars. In Proc. ACM SIGPLAN Conf. Program. Lang. Design Implement. (PLDI). ACM, 95–110. doi:10.1145/3062341.3062349DOI
  7. [7]Rudi Cilibrasi and Paul M. B. Vitányi. 2005. Clustering by Compression. IEEE Transactions on Information Theory 51, 4 (2005), 1523–1545. doi:10.1109/TIT.2005.844059DOI
  8. [8]Robert Dorfman. 1943. The Detection of Defective Members of Large Populations. The Annals of Mathematical Statistics 14, 4 (1943), 436–440. doi:10.1214/aoms/1177731363DOI
  9. [9]Andrea Fioraldi, Dominik Maier, Heiko Eißfeldt, and Marc Heuse. 2020. AFL++: Combining Incremental Steps of Fuzzing Research. In 14th USENIX Workshop on Offensive Technologies (WOOT 20). USENIX Association.
  10. [10]Rahul Gopinath, Björn Mathis, and Andreas Zeller. 2020. Mining Input Grammars from Dynamic Control Flow. In Proceedings of the ACM Joint European Software Engineering Conference and Symposium on the Foundations of Software Engineering (ESEC/FSE). https://publications.cispa.saarland/3101/DOI
  11. [11]Ahmad Hazimeh, Adrian Herrera, and Mathias Payer. 2020. Magma: A Ground-Truth Fuzzing Benchmark. Proc. ACM Meas. Anal. Comput. Syst. 4, 3 (2020), 49:1–49:29. doi:10.1145/3428334DOI
  12. [12]Satia Herfert, Jibesh Patra, and Michael Pradel. 2017. Automatically Reducing Tree-Structured Test Inputs. In Proc. IEEE/ACM Int. Conf. Automated Softw. Eng. (ASE). IEEE. doi:10.1109/ASE.2017.8115697DOI
  13. [13]Renáta Hodován and Ákos Kiss. [n. d.]. Picireny: Hierarchical Delta Debugging Framework. https://github.com/renatahodovan/picireny
  14. [14]Renáta Hodován and Ákos Kiss. 2016. Modernizing Hierarchical Delta Debugging. In Proc. Int. Workshop Automating Test Case Design, Selection, and Evaluation (A-TEST). ACM, 31–37. doi:10.1145/2994291.2994296DOI
  15. [15]Xiaodong Jia and Gang Tan. 2024. V-Star: Learning Visibly Pushdown Grammars from Program Inputs. Proc. ACM Program. Lang. 8, PLDI (2024).DOI
  16. [16]Bernhard Korte and Jens Vygen. 2018. Combinatorial Optimization: Theory and Algorithms (6 ed.). Algorithms and Combinatorics, Vol. 21. Springer. doi:10.1007/978-3-662-56039-6DOI
  17. [17]Gereon Kremer, Aina Niemetz, and Mathias Preiner. 2021. ddSMT 2.0: Better Delta Debugging for the SMT-LIB v2 Language and Friends. Zenodo. doi:10.5281/zenodo.4721925 Artifact, version 1.DOI
  18. [18]P. Kreutzer, T. Kunze, and M. Philippsen. 2021. Test Case Reduction: A Framework, Benchmark, and Comparative Study. In Proc. IEEE Int. Conf. Softw. Maintenance Evol. (ICSME). IEEE, 58–69. doi:10.1109/ICSME52107.2021.00012DOI
  19. [19]Neil Kulkarni, Caroline Lemieux, and Koushik Sen. 2021. Learning Highly Recursive Input Grammars. In Proc. IEEE/ACM Int. Conf. Automated Softw. Eng. (ASE). IEEE. https://www.carolinemieux.com/arvada_ase21.pdfarxiv.org/abs/2108.13340
  20. [20]Aarush Khumbhkar, Feiyang Chen, Danushka Liyanage, Xi Wu, Mohammad Amin Alipour, and Rahul Gopinath. 2026. Dr. DD: 1-Minimal Isolation of Failure Causes via Deferred Restarts. In 2026 IEEE International Symposium on Software Reliability Engineering (ISSRE). IEEE.
  21. [21]Feifei Li, Xiao Chen, Xiaoyou Sun, Xi Xiao, Shaohua Wang, Yong Ding, Sheng Wen, and Qing Li. 2026. Context-Free Grammar Inference for Complex Programming Languages in Black Box Settings. In Proc. Int. Conf. Softw. Eng. (ICSE). ACM. doi:10.1145/3744916.3773147DOI
  22. [22]Feifei Li, Xiao Chen, Xi Xiao, Xiaoyou Sun, Chuan Chen, Shaohua Wang, and Jitao Han. 2024. Incremental Context-free Grammar Inference in Black Box Settings. In Proc. IEEE/ACM Int. Conf. Automated Softw. Eng. (ASE). ACM, 1171–1182. doi:10.1145/3691620.3695494DOI
  23. [23]LLVM Project. [n. d.]. libFuzzer: A Library for Coverage-Guided Fuzz Testing. https://llvm.org/docs/LibFuzzer.html
  24. [24]David R. MacIver. [n. d.]. Shrink Ray: A Modern Multiformat Test-Case Reducer. https://github.com/DRMacIver/shrinkray
  25. [25]Jonathan Metzman, László Szekeres, Laurent Simon, Read Sprabery, and Abhishek Arya. 2021. FuzzBench: An Open Fuzzer Benchmarking Platform and Service. In Proc. ACM Joint Eur. Softw. Eng. Conf. Symp. Found. Softw. Eng. (ESEC/FSE). ACM, 1393–1403. doi:10.1145/3468264.3473932DOI
  26. [26]Ghassan Misherghi and Zhendong Su. 2006. HDD: Hierarchical Delta Debugging. In Proc. Int. Conf. Softw. Eng. (ICSE). ACM, 142–151. doi:10.1145/1134285.1134307DOI
  27. [27]Falcon Monot, Sergey Bratus, Sven M. Hallberg, and Meredith L. Patterson. 2016. The Seven Turrets of Babel: A Taxonomy of LangSec Errors and How to Expunge Them. In IEEE Cybersecurity Development (SecDev). 45–52. doi:10.1109/SecDev.2016.019
  28. [28]Philip Oliver, Jens Dietrich, Craig Anslow, and Michael Homer. 2024. Dataset for CrashJS: A NodeJS Benchmark for Automated Crash Reproduction. Zenodo. doi:10.5281/zenodo.10530515arxiv.org/abs/2405.05541
  29. [29]Jihyeok Park, Seungmin An, Dongyun Gou, Gyeongwon Kim, and Sukyoung Ryu. 2021. JEST: N+1-Version Differential Testing of Both JavaScript Engines and Specification. In Proceedings of the 43rd International Conference on Software Engineering (ICSE). 13–24. doi:10.1109/ICSE43902.2021.00015DOI
  30. [30]Perl 5 Porters. 2025. perlfaq7: Perl Language Issues. https://perldoc.perl.org/perlfaq7#Can-I-get-a-BNF/yacc/RE-for-the-Perl-language? Perl 5.20250619; “Can I get a BNF/yacc/RE for the Perl language?”.
  31. [31]John Regehr, Yang Chen, Pascal Cuoq, Eric Eide, Chucky Ellison, and Xuejun Yang. 2012. Test-Case Reduction for C Compiler Bugs. In Proc. ACM SIGPLAN Conf. Program. Lang. Des. Implement. (PLDI). ACM, 335–346. doi:10.1145/2254064.2254104DOI
  32. [32]Kostya Serebryany. 2017. OSS-Fuzz: Google’s Continuous Fuzzing Service for Open Source Software. Invited talk, 26th USENIX Security Symposium.
  33. [33]Chengnian Sun, Yuanbo Li, Qirun Zhang, Tianxiao Gu, and Zhendong Su. 2018. Perses: Syntax-Guided Program Reduction. In Proc. Int. Conf. Softw. Eng. (ICSE). ACM, 361–371. doi:10.1145/3180155.3180236DOI
  34. [34]Dániel Vince, Renáta Hodován, Daniella Bársony, and Ákos Kiss. 2021. Extending Hierarchical Delta Debugging with Hoisting. In Proc. IEEE/ACM Int. Conf. Automation of Software Test (AST). IEEE.
  35. [35]Guancheng Wang, Ruobing Shen, Junjie Chen, Yingfei Xiong, and Lu Zhang. 2021. Probabilistic Delta Debugging. In Proc. ACM Joint Eur. Softw. Eng. Conf. Symp. Found. Softw. Eng. (ESEC/FSE). ACM, 881–892. doi:10.1145/3468264.3468625DOI
  36. [36]Zhenyang Xu, Yongqiang Tian, Mengxiao Zhang, Jiarui Zhang, Puzhuo Liu, Yu Jiang, and Chengnian Sun. 2025. T-Rec: Fine-Grained Language-Agnostic Program Reduction Guided by Lexical Syntax. ACM Trans. Softw. Eng. Methodol. 34, 2 (2025), 1–31. doi:10.1145/3690631DOI
  37. [37]YAML Test Suite contributors. 2022. YAML Test Suite. https://github.com/yaml/yaml-test-suite/tree/data-2022-01-17 Release data-2022-01-17.
  38. [38]Boyang Yang, Luyao Ren, Xin Yin, Jiadong Ren, Haoye Tian, and Shunfu Jin. 2025. Input Reduction Enhanced LLM-based Program Repair. arXiv:2507.15251. doi:10.48550/arXiv.2507.15251arxiv.org/abs/2507.15251
  39. [39]Xuejun Yang, Yang Chen, Eric Eide, and John Regehr. 2011. Finding and Understanding Bugs in C Compilers. In Proc. ACM SIGPLAN Conf. Program. Lang. Design Implement. (PLDI). ACM, 283–294. doi:10.1145/1993498.1993532DOI
  40. [40]Michal Zalewski. 2014. American Fuzzy Lop. https://lcamtuf.coredump.cx/afl/
  41. [41]Andreas Zeller and Ralf Hildebrandt. 2002. Simplifying and Isolating Failure-Inducing Input. IEEE Trans. Softw. Eng. 28, 2 (2002), 183–200. doi:10.1109/32.988498DOI
  42. [42]Mengxiao Zhang, Yongqiang Tian, Zhenyang Xu, Yiwen Dong, Shin Hwei Tan, and Chengnian Sun. 2024. LPR: Large Language Models-Aided Program Reduction. In Proceedings of the 33rd ACM SIGSOFT International Symposium on Software Testing and Analysis (ISSTA 2024). doi:10.1145/3650212.3652126DOI
  43. [43]Mengxiao Zhang, Zhenyang Xu, Yongqiang Tian, Xinru Cheng, and Chengnian Sun. 2025. Artifact for “Toward a Better Understanding of Probabilistic Delta Debugging”. Zenodo. doi:10.5281/zenodo.14854239 Version 3.arxiv.org/abs/2408.04735

Paper details

vlnc:W_ej2tckyy
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Codex, Claude Code

View statement
Looking for related papers…
Contents