1 Introduction↩︎

Black-box inference of context-free grammars from sample programs faces two key challenges. First, existing approaches do not scale to larger languages, at best producing grammars of low accuracy. Second, inferred grammars are excessively large and cryptic, making inferred grammars difficult for humans to interpret and use.

These two challenges are important as, first, many languages of practical use are large and complex [1]. Second, besides fuzzing [2], [3] and security analysis [4], other key use-cases of grammar inference include reverse engineering [5], documentation, and human understanding of rare and under-documented commercial languages [6], so readability is also very important. At a high level, these challenges are important as context-free grammars are widely used in programming language design, documentation, and as an input for fuzzing systems that search for parser bugs [7]–[9].

Black-box grammar inference is a fundamentally hard problem [10], as we only have access to a black-box parser of an unknown language \(\mathcal{L}\) and a few sample \(\mathcal{L}\) programs. The sample programs may not cover all \(\mathcal{L}\) language features and will almost certainly not cover all possible combinations of these language features.

Recent advances in black-box context-free grammar inference include Arvada [11], TreeVada [12], Kedavra [13], and Crucio [14]. The pioneering Arvada infers grammars directly from complete input strings while exploring multiple generalization paths. Arvada suffers from low accuracy, inefficient processing, and poor grammar readability. The more recent TreeVada, Kedavra, and Crucio succeed at improving upon Arvada. However, these improvement still do not scale to large and complex languages though. They also only partially address Arvada’s grammar readability issues. Specifically, even if the inferred grammar only partially covers the target “golden” grammar, the inferred grammar has many more rules and relies on a cryptic naming scheme.

XVada is a deterministic automated TreeVada-style black-box grammar inference technique. XVada contains several new techniques for iterative parse-tree construction, including treating each bracketed token sequence as a candidate grammar rule alternative, adding indirection to enable learning of non-recursive rules, and batch grammar generalization processing. The latter translates a successful grammar generalization into an update of the current ranked list of remaining candidate grammar generalization steps, to avoid the expensive re-ranking of all parse trees after each generalization step. XVada further decomposes complex inferred parse trees via Hierarchical Delta Debugging (HDD) [15] to learn grammar rule alternatives and infers descriptive non-terminal names via LLM queries.

In an empirical comparison that addresses several experimental design issues in recent related studies (e.g., Glade-II [16] and Crucio), TreeVada and XVada were the only approaches that could successfully process all 17 languages of various sizes. On smaller languages XVada yielded grammars of similar accuracy, while achieving much higher average accuracy on larger languages. At the same time, XVada-inferred grammars were on average more compact. While running on Python Liquid, XVada found a denial-of-service CVE. Using the XVada-inferred grammar, an off-the-shelf fuzzer then found five bugs the Python Liquid developers fixed based on our bug reports. To summarize, the paper makes the following major contributions.

• XVada is the first black-box approach for inferring context-free grammars that scales to larger languages and produces grammars that are compact with high accuracy.

• The paper identifies pitfalls in recent work that can inflate F1 scores, including incompatible precision/recall grammar interpretations and duplicate-heavy test suites.

• In an empirical comparison on larger languages, XVada improves on the highest-scoring competitor (TreeVada) both in grammar accuracy and grammar compactness.

• XVada also found a CVE in the widely used Python Liquid engine. Fuzzing based on the XVada-inferred grammar found five more since-fixed Python Liquid bugs.

• The XVada implementation, scripts, and data (including for replicating the experiments) are freely available online: https://github.com/rifatarefin/xvada

2 Background↩︎

Almost all programming languages employ context-free grammars in their design [7]. Similarly, many popular languages are at least partially documented via a context-free grammar. Context-free grammars are also a popular input format for fuzzers. Following is relevant context of the Arvada and TreeVada approaches XVada builds on, as well as issues we identified in the experimental design of Crucio we aim to improve upon in our evaluation.

2.1 Grammar Inference via Parse Tree Generalization↩︎

Arvada introduced parse tree generalization via bubble-and-merge for learning context-free grammars [11]. Arvada starts from initial flat trees, e.g., the two Figure 1a example trees. Figure 1b bubbles up the sibling node sequence a==b under the new non-terminal node \(t_{new}\). Arvada then checks if it can replace \(t_{new}\) with any existing non-terminal node and vice-versa.

As replacing (the implicit parent of) true with \(t_{new}\) and vice versa here yields syntactically correct programs, Arvada treats a==b and true as alternatives of the same grammar rule. We thus merge \(t_{new}\) and (the parent of) true and relabel them as \(t_1\) in Figure 1c. The tree-induced grammar thus now includes the new rule \(t_1 \to \textcolor{teal}{\texttt{a==b}}\; | \;\textcolor{teal}{\texttt{true}}\).

Instead of flat trees, Arvada’s successor TreeVada [12] first pre-structures trees, based on the common structural assumption [17] that brackets indicate concept nesting [18].

Before accepting a candidate bubble into the parse trees, Arvada/TreeVada heuristically validate it via CheckBubble. CheckBubble samples (at most 50) candidate strings from the parse trees, by instantiating the candidate alternatives throughout the parse trees. If the black-box parser accepts all thereby generated programs, CheckBubble returns true and the new generalization is accepted. The limited sampling (up to 50) may miss invalid program instantiations and may thus merge invalid generalizations into the trees.

2.2 Reassessing Crucio’s Evaluation↩︎

The recent Crucio black-box grammar inference work reported high F1 scores for complex programming languages [14]. Upon close examination, we find two major issues with that study’s evaluation design that make it hard to generalize these early findings.

Different Grammars for Precision and Recall Metrics: A key limitation of Crucio’s evaluation methodology is that precision and recall are computed using different interpretations of the inferred grammar. Specifically, precision is measured using a grammar that instantiates each lexical class only with the concrete character sequences observed during training, whereas recall is measured using a different grammar that maps the same lexical class to a deterministic finite automaton (DFA), potentially accepting a much larger set of character sequences. As a result, the reported F1 score combines precision and recall computed on different grammars, making it difficult to interpret and compare fairly with approaches that evaluate both metrics using the same inferred grammar.

More formally, let \(\tau\) denote an inferred lexical class, \(S_\tau\) denote the set of tokens of type \(\tau\) observed in the seed programs, and \(D_\tau\) denote the language accepted by the DFA inferred for \(\tau\), where typically \(S_\tau \neq D_\tau\). During precision evaluation, Crucio generates programs by instantiating \(\tau\) exclusively with tokens from \(S_\tau\). During recall evaluation, however, an unseen token \(x \notin S_\tau\) is considered an instance of \(\tau\) whenever \(x \in D_\tau\). Precision thus evaluates a grammar whose lexical productions are restricted to \(S_\tau\), yet recall evaluates a more permissive grammar whose lexical productions are defined by \(D_\tau\). For example, if the seed inputs contain only the identifier FooBar, precision is computed using a grammar that generates only FooBar for that identifier class, while recall is computed using a grammar whose inferred DFA may accept a much broader set of identifiers.

Precision Metric Does Not Sample Complete Programs: All recent grammar inference approaches evaluate precision by sampling programs from the inferred grammar. Earlier studies, including Arvada [11], TreeVada [12], Kedavra [13] recursively generate an entire program by expanding grammar rules from the start symbol to the lexical terminals. We refer to this conventional strategy as full-program sampling (\(P_{sample}\)). In contrast, Crucio introduces a mutation-based precision metric, denoted as \(P_{swap}\). Rather than generating a complete program from scratch, \(P_{swap}\) begins with an existing valid program accepted by the inferred grammar and randomly selects a non-terminal subtree to regenerate while keeping the remainder of the program unchanged.

Figure 2 illustrates this process. \(P_{swap}\) randomly selects non-terminal exp, freezes its left and right context, and only expands exp to generate a concrete string fragment (y*2), which it then plugs back into the original program.

Evaluating a grammar’s generative capacity recursively from the top down (as in \(P_{sample}\)) exposes over-generalization. Lacking context-sensitivity, a flawed (context-free) grammar may incorrectly allow constructs such as a \(while\) loop inside a variable assignment. \(P_{swap}\) conceals such structural flaws. By freezing the mutation’s context in the original valid program, \(P_{swap}\) ensures that the program remains correct outside the (local) mutation, which artificially constrains the search space for generating invalid programs.

Based on the Crucio artifact logs, Table 1 shows the impact of using \(P_{swap}\) or \(P_{sample}\) in Crucio for five languages used in previous studies. \(P_{swap}\) is often an order of magnitude higher, also increasing the F1 score.

\(P_{swap}\) also diverges from inferred grammars’ practical utility. The primary downstream consumers of these tools, such as syntax-directed fuzzing engines [3], [19] typically operate by expanding a grammar continuously from the start rule to generate novel inputs. A precision metric based on \(P_{swap}\) effectively evaluates the stability of the grammar under single-point mutation rather than its standalone generative robustness. While mutation-based generation is a valid testing strategy, using it to define the precision of the grammar itself misrepresents the artifact’s reliability when deployed in standard, end-to-end generative tasks.

3 XVada↩︎

We present XVada, a deterministic black-box CFG inference tool that iteratively builds parse trees by merging tree non-terminals. This section describes XVada’s building blocks in pipeline order. After inference, XVada optionally queries an LLM to label each non-terminal with a summary of the strings it derives. For readability, we use these LLM-generated non-terminal names also in the intermediate XVada example trees throughout this section.

3.1 Initial Parse-trees↩︎

3.1.1 Tokenization↩︎

Before constructing parse trees, XVada tokenizes the input programs. Each whitespace, special, or non-ASCII character XVada treats as an individual token. Each contiguous letter sequence and each contiguous digit sequence XVada groups into a token labeled by the grouped sequence. For example, XVada maps $$FooBar123 to four tokens: $, $, FooBar, and 123.

3.1.2 Minimizing whitespace↩︎

To reduce the size of an input program’s token sequence and the subsequent search space, we iteratively trim whitespace. This process ensures that the input program remains valid, i.e., it retains required whitespace. XVada scans the token sequence left to right. Whenever we encounter a whitespace, we temporarily remove it and query the oracle on the resulting character sequence. If the oracle accepts the input, we omit the whitespace; otherwise, we restore it. For example, with a C-language compiler XVada trims inta=1; to inta=1;.

3.1.3 String-literal guardrail↩︎

Prior approaches (including TreeVada, Kedavra, and Crucio) commonly treat a sequence wrapped by single or double quotes such as ’a’ or "big dog" as a single string literal token. This heuristic works well for many languages, but it may be unsound when quotation marks serve other purposes.

To avoid incorrectly mapping such sequences to a single token, we introduce an oracle-guided string-identification guardrail. When XVada encounters a sequence enclosed by matching quotes or backticks (’, ", or ‘), we replace the enclosed contents with arbitrary characters and query the oracle. If the oracle accepts the modified program, XVada treats this as evidence that the quoted contents are unconstrained string data and collapses the quote-enclosed sequence to a single token, so "big dog" would yield the three tokens ", big dog, and ". Otherwise, we keep the sequence’s default tokenization.

3.1.4 Bracket-based parse-tree initialization↩︎

After tokenization, XVada constructs for each seed program an initial flat parse tree. Following TreeVada, XVada is built on the “soft” assumption that many languages use [](){} brackets as (recursive) nesting constructs. We thus use a bracket-based heuristic that moves each bracketed token sequence under a newly created child node, thereby introducing an initial syntactic hierarchy. Once this pre-structuring step is complete, we invoke MergeAllValid, which systematically merges any pair of non-terminal nodes it can interchange while preserving oracle-validity of the generated strings.

3.2 Bracket-guided Bubble Selection↩︎

While TreeVada pre-structures its parse trees along [](){} brackets as (recursive) nesting constructs, TreeVada does not exploit the bracketed sequence itself. As such a bracketed sequence can be a syntactic unit, XVada treats each bracketed sequence as a candidate bubble, e.g., the 1+1 sequence in ()-brackets the Figure 3 Lua program. As with any candidate bubble b, XVada tries to merge all occurrences of b in the seed programs in the same step, and succeeds here with merging both 1+1 instances with 1 into exp.

While earlier approaches such as Arvada and TreeVada may eventually also propose the same 1+1 bubble, these earlier approaches would do so as a result of their regular (expensive) bubble ranking process. Besides extra runtime, earlier tools may also first get confused by one of their heuristics, get stuck in their exploration, and thus never apply such a within-brackets bubble candidate. We thus prioritize bracket-derived bubble candidates over regular ones, and rank the resulting in-bracket bubble list using TreeVada’s depth and length-aware heuristic.

3.3 Indirection-based Merge to Learn Non-recursive Rules↩︎

Arvada’s bidirectional replacement check prevents both Arvada and TreeVada from learning certain non-recursive rules. Specifically, requiring bidirectional interchangeability of a candidate bubble with its direct or transitive child creates recursive grammar rules. Besides such recursive rules, XVada also supports learning non-recursive rules via its indirection-based merge technique. The technique applies when unidirectional replacement succeeds, but the merge target non-terminal also occurs inside the candidate bubble.

Such an in-bubble occurrence creates a recursive rule and thus a recursive replacement check, causing an otherwise valid merge to be rejected. To resolve this, we add a level of indirection to the target node. If the bidirectional check succeeds with this indirection we merge the bubbled-up node with the added node. If the merge-attempt fails we discard the changes. The tiny language’s expression rules are an example. Specifically, tiny permits at most one negation per int:

\[\begin{array}{l} \textit{expr} \to \textit{expr op elem} \mid \textit{elem}\\ \textit{op} \to \textcolor{teal}{\texttt{+}}\mid\textcolor{teal}{\texttt{-}}\\ \textit{elem} \to \textit{ident} \mid \textit{int}\\ \textit{int} \to \textit{num} \mid \textcolor{teal}{\texttt{-}}~\textit{num} \\ \textit{num} \to (\textcolor{teal}{\texttt{0}} \mid \cdots \mid \textcolor{teal}{\texttt{9}})+ \end{array}\]

Figure 4 (left) illustrates this limitation for the subtree rooted at expr in a seed program that contains the fragment -9 + 5. At this point (potentially among others) we consider 9 and 5 as equivalent at num, e.g., after generating programs with fragments -9 + 9 and -5 + 5 the oracle accepted as valid, implying the rule \(\textit{num} \to \textcolor{teal}{\texttt{5}} \mid \textcolor{teal}{\texttt{9}}\).

Arvada/TreeVada next consider candidate bubble \([\)-, num\(]\) under a fresh non-terminal node \(t\). Specifically, CheckBubble tests if \([\)-, num\(]\) at \(t\) is equivalent with the already established alternative expansions of an existing non-terminal in the tree such as num. If successful, this would merge \([\)-, num\(]\) at \(t\) with 5 and 9 at \(num\), yielding the rule \(\textit{num} \to \textcolor{teal}{\texttt{-}}~\textit{num} \mid \textcolor{teal}{\texttt{5}} \mid \textcolor{teal}{\texttt{9}}\).

In the equivalence test (via mutual replacement), num replacing \(t\) yields valid tiny programs with expr such as 5 + 5. But the reverse (\(t\) replacing num) produces invalid tiny programs, e.g., containing a expr of --9 + -9. This triggers Arvada and TreeVada to discard the \([\)-, num\(]\) candidate bubble, which (for a seed program as in Figure 4) makes them miss tiny’s non-recursive integer negation rule. Instead they are left with the overly specific rule \(\textit{expr} \to \textcolor{teal}{\texttt{-}}~\textit{num}~\textcolor{teal}{\texttt{+}}~\textit{num}\).

The key observation is that we can still generalize such an overly specific grammar rule, even in a non-recursive case as tiny’s int negation. At the core, we want to test the equivalence of \([\)-, num\(]\) with the existing derivations (5 and 9) of num. Instead of merging t with num directly, we thus add a level of indirection, i.e., a new intermediate node between num and its parent everywhere in our parse trees other than our candidate bubble t. This yields the same equivalence test, but breaks recursion, is accepted by the oracle parser, and infers tiny’s non-recursive int negation rule \(\textit{int} \to \textcolor{teal}{\texttt{-}}~\textit{num}\mid\textit{num}\).

3.4 Batch Bubble Processing↩︎

Each successful bubble merge in Arvada or TreeVada has a high overhead, as Arvada/TreeVada update their parse trees, which invalidates indices and the context of the remaining bubble candidates. The approaches thus discard their entire bubble ranking, re-identify all possible bubbles, and re-rank them from scratch. In the Figure 5 example Arvada/TreeVada would discard their ranked candidate bubble list after merging 1+1 with 1 into exp.

We observe that a bubble merge may leave some tree regions unaffected. Instead of discarding the remaining bubble candidates, XVada’s dynamic batch processing keeps attempting to merge the list’s bubbles (in rank-order), by evaluating each candidate against the current tree state as follows.

3.4.0.1 Unaffected (Keep)

The candidate bubble targets a sequence of nodes that is spatially disjoint from the regions modified by previous merges in the current batch, such as a==b in Figure 5. We retain such a candidate as is and attempt to merge it, as it remains strictly valid.

3.4.0.2 Relabeled (Update)

A prior merge in this batch has renamed a node in this candidate bubble. In the Figure 5 example, the a==b candidate bubble’s new parent bool merged with the (implicit) parent of true, which affects the next candidate bubble x=true. XVada propagates the new label to such a candidate bubble, updating the bubble’s elements to match the current tree state while preserving the intended structural grouping. In Figure 5 we relabel x=true to x=bool.

3.4.0.3 Broken (Discard)

A prior merge has consumed, split, or structurally reconfigured the nodes targeted by this candidate bubble. Due to this structural overlap or conflict, we deem this candidate “broken” and discard it. In Figure 5 two merges overlap with the b then x candidate bubble, which breaks the bubble, as the bubble’s nodes are no longer tree siblings.

3.5 Hierarchical Delta Debugging (HDD) to Decompose Trees↩︎

Arvada/TreeVada generalize one parse tree per seed program, which can be remarkably effective for small diverse seed programs. But with increasing program size each seed program tends to become a larger monolith with redundancies within and across programs, where each program uses a similar complex structure and no seed program demonstrates simple grammar rule alternatives. This becomes a problem for Arvada/TreeVada if such rules are non-recursive. For example, if each Java seed program declares its superclass then Arvada/TreeVada do not learn the base case of no declared superclass.

In the Figure 6 example, HDD prunes the else branch from the if-then-else construct. After decomposition, the pruned tree induces an additional grammar rule that admits if-then constructs without an else branch, thus exposing a smaller reusable construct that was not present in the seed programs.

Following the idea of hierarchical delta-debugging (HDD) [15], [20], after bubble exploration we traverse each parse tree top-down from the root. At each visited node \(n\), we perform delta-debugging (ddmin [20]) on \(n\)’s child nodes and partition them into \(g\) contiguous chunks (starting with \(g\) = 2). For each chunk, we construct two candidate trees. One deletes the chunk (and all transitive children). The other deletes \(n\)’s other (non-chunk) children (and their transitive children). If no candidate tree passes the below oracle check at the current granularity, we increase \(g\) (up to the number of \(n\)’s child nodes) and repeat.

Similar to a bubble merge, we add a candidate tree to our trees \(\mathcal{T}\), if our black-box parser accepts 50 sampled programs as valid. We first select the up to 20 trees \(\mathcal{T}_t \subseteq \mathcal{T}\) that share the most non-terminals with candidate tree \(t\), i.e., we count the elements in the intersection \(|\mathit{NT}(t) \cap \mathit{NT}(u)|\) of \(t\)’s non-terminals \(\mathit{NT}(t)\) with another tree \(u \in \mathcal{T}\). We sample 50 programs from \(\{t\}\cup\mathcal{T}_t\) (up to a rule-expansion depth 2).

3.6 Descriptive Label for Each Non-terminal via LLM↩︎

Once no further generalization is possible, XVada’s iterative bubble-and-merge process terminates. We then allow XVada to optionally relabel the tree non-terminals so that the tree-induced grammar becomes human comprehensible and thus easier to inspect. For each non-terminal we query a lightweight LLM (GPT 4o-mini) to summarize up to two strings derivable from that non-terminal, as shown in Figure [fig:prompt95label].

None

3.7 Generalizing Terminals from Seed Observations↩︎

While HDD decomposition yields the final parse trees, the trees’ leaf nodes still only reflect the terminal samples we observed in the seed programs (e.g., 5 and 9 for num in Figure 4). To approximate the language’s likely greater terminal variety, XVada generalizes terminals beyond the observed samples. We thus incrementally assign each terminal (such as num) a larger character class, sample 10 programs using the new class, and accept the generalization if the black-box parser accepts all sampled programs.

For alphabetic and numeric tokens XVada follows the Arvada/TreeVada character-class hierarchy. Both upper-case and lower-case sequences generalize to a mixed-case sequence, which generalizes to an alphanumeric (lower/upper case and positive int) sequence. Similarly, digit \(\to\) positive int \(\to\) alphanumeric. While Arvada/TreeVada stop there, we then iteratively try to add special characters !"#$%&’()*+,-./:;<=>?@[\]^\(\wedge\)_‘{|}~ (one at a time) to the inferred class. Per character, we sample 10 programs and again use the black-box parser as the oracle.

To a quote-bracketed string we apply the same special character generalization, followed by a similar approach to adding whitespace \t\r\n (one at a time), which we again validate with 10 sampled programs each.

Since XVada infers trees from whitespace-minimized token sequences, the final grammar includes the minimum number of whitespace required for syntactic validity. To support both whitespace-sensitive and -insensitive languages the evaluation parser compiled from the inferred grammar ignores additional whitespace. Note that we do not post process the inferred grammar to remove ambiguities (i.e. fix left recursions). We therefore, use Earley parsing for compiling the evaluation parser, as it can handle any context-free grammar. XVada also allows users to export grammars to the more performant ANTLR4 format, which requires an additional normalization phase to remove indirect left recursions.

4 Evaluation Setup↩︎

We address the following research questions:

• RQ1: How accurate are the grammars inferred by XVada compared with those inferred by state-of-the-art approaches, when evaluated against the golden grammar of languages with varying sizes and complexities?

• RQ2: How compact are XVada-inferred grammars compared with similarly accurate grammars produced by state-of-the-art approaches?

• RQ3: How does HDD affect the accuracy of grammars inferred by XVada?

• RQ4: How effective are XVada-inferred grammars for practical fuzzing tasks?

4.1 Languages, Grammars, Parsers, Seed & Test Programs↩︎

For each language in our study, we obtain its “golden” grammar (where available), valid seed programs (Table 2), an existing “golden” black-box parser and “golden” valid test programs from the following grammar-mining artifacts and grammar repositories. We use turtle, while, lisp, xml, json, tinyc, c-500, and curl from TreeVada [21]. (TreeVada subjects use R1 seed variants, c-500 is tinyc with the larger R5 seeds.) We add minic from Kedavra¹ and tiny, lua, c, and mysql from Glade-II [22]. We further add liquid, using Python Liquid² as the black-box parser and collecting its seed programs and 1k held-out test programs from Shopify’s liquid-spec suite³. Finally, we add java, cpp, and rust grammars from the ANTLR4 grammar repository⁴ and generate their seed/test programs the same way as for the Glade-II subjects below.

Excessive duplicates in Glade-II: The Glade-II replication study by Bendrissou et al., published at PLDI 2022 [16], made several contributions, including re-implementing the Glade tool and releasing new evaluation subjects [22]. Each Glade-II subject comes with 1k test programs. But of its 18 ANTLR4 subjects, only pascal has no duplicate test program. Most affected is ints, which has 139 unique test programs but (among others) 515 test programs that only contain the single character 0. As a consequence, even a trivial grammar that only recognizes 0 would score 51.5% recall on ints. Similarly, lua has 462 unique test programs (but 322 programs that only contain a single whitespace character) and in mysql 305 are unique (while 287 are empty).

Such artifacts are not representative of the corresponding golden grammar and thus yield misleading recall and F1 scores. To avoid this issue, we use we use the golden grammars for tiny, lua, c, and mysql from Glade-II and generate new seed and test sets without duplicates using the off-the-shelf grammar fuzzer Grammarinator [3]. To avoid excessive program growth, we set the fuzzer’s max-depth parameter to the minimum depth required to reach every non-terminal from the start rule (Table 2, column D).

4.2 Golden Grammar and Language Complexity: Lo vs. Hi↩︎

Table 2 orders our golden grammars by non-terminals (NT), which correlates with several other Table 2 size and complexity metrics⁵. At a high level, higher metric values imply larger grammar size and complexity. We create two groups: small/toy (top) and larger / more complex (bottom).

Basic metrics are number of terminals (T) and non-terminals (NT). The average right-hand side length (RHS) divides total terminal and non-terminal occurrences on all rules’ right-hand sides by the number of non-terminals (NT). The average McCabe cyclomatic complexity (MCC) divides the total number of “branch” operators (alternative rule |, optional term ?, and closures * and +) of all rules by the number of non-terminals (NT). Depth (D) is the largest minimum distance of a non-terminal from the grammar’s start non-terminal.

Two metrics generate from the grammar a LR parser [8] and count its properties, e.g., the LR automaton’s states (LRS). The basic lookahead metric (LAT) adds for each terminal the number of LR automaton states that do not lead to an error when that terminal is in the lookahead, divided by the number of terminals (T). The final metric captures a language property directly from the grammar rules. The maximum number of different terminal pairs starting with a given terminal (LTPSM) iteratively expands all grammar rules to compute all possible terminal pairs.

By comparing 16 languages (including DSLs and several Java versions) on 21 metrics, gMetrics proposes four grammar categories [1]: tiny, small (mainly DSLs), intermediate (3rd-generation general-purpose), and big. The cut-offs are LRS (100, 1k, 3k), LAT (20, 200, 500), and LTPSM (6, 50, 70). The cut-offs align with our two groups of low (tiny and small) and high (intermediate and big) complexity grammars for our Table 2 subjects. There are three exceptions. (1) First, with no golden grammar available, we categorize curl as Lo as it is a regular language. (2) Second, also with no golden grammar available, we categorize liquid as Hi because its collected programs contain context-free structure, e.g., nested brackets, and the inferred grammar statistics align more closely with the Hi group. (3) Third, with only partial gMetrics results, we categorize mysql as Hi as it scores highest on the available metrics, i.e., terminals, non-terminals, and depth.

4.3 Metrics: Runtime, Inferred Grammars’ Size & Accuracy↩︎

The Crucio artifact⁶ does not generate any grammar file output. To compare with Crucio, we convert its program generation model \(P_{\text{sample}}\) into an equivalent set of production rules and export the resulting grammar. To evaluate how accurately an inferred grammar \(\mathcal{G}\) captures the target language, we then use the three Arvada/TreeVada study metrics:

Precision: We sample 1k programs from \(\mathcal{G}\) and count how many are accepted by the existing (“golden”) black-box parser.

Recall: We use the existing held-out (“golden”) test set of valid programs (e.g., generated from the golden grammar) and count how many are accepted by a Python Earley parser generated from \(\mathcal{G}\).

F1 Score: As usual, F1 is the harmonic mean of precision \(p\) and recall \(r\): \(2*p*r/(p+r)\), which is widely considered a useful overall metric for the inferred grammar’s accuracy.

For precision Arvada and TreeVada used a fixed grammar expansion depth of 5 (which does not reach deeper nested non-terminals), while Kedavra limits each production rule to at most 10 uses (which may also prevent deeply nested rules from being used). To ensure that our sampling can exercise all reachable non-terminals, our evaluation just sets each grammar’s maximum rule expansion depth to the minimum depth required to reach any non-terminal from the start rule (i.e., the grammar’s Table 4 D value).

Grammar Size: Given two equally accurate grammars, a human consumer may prefer the more compact one. We thus count across all rule alternatives \(A\) all terminal and non-terminal occurrences: \(S=A*l(A)\), which for the Table 2 golden grammars is NT\(*\)RHS.

Runtime: For Table 3 we ran each experiment with a 48h time-out on a 2.1GHz Intel Xeon Platinum 8160 machine with 192 GB RAM running Rocky Linux 9.7. To approximate a user’s experience with the non-deterministic subjects, for Kedavra and Crucio we ran each experiment five times and report the average. Reported runtimes do not include converting Crucio’s internal representation to a grammar output file or measuring precision or recall.

5 Results↩︎

Table 3 shows grammar accuracy and inference time. Each parse attempt yielded a valid vs. invalid result before our 5 minute time-out. Table 4 characterizes the resulting grammar sizes. We discuss the Lo and Hi language groups separately because the tools exhibit substantially different behavior across these groups.

5.1 RQ1: Effectiveness↩︎

Kedavra on Lo languages: Kedavra was highly effective on the seven Lo subjects whose golden grammars have fewer than ten non-terminals (Table 2): it obtains an F1 score of 1.00 on six subjects and 0.98 on json. It is also the fastest tool on four of these subjects (while, lisp, tinyc, and c-500). Its performance is weaker on the remaining Lo subjects with larger golden grammars: F1 falls to 0.67 on tiny (13 non-terminals) and 0.65 on minic (14 non-terminals), and to 0.25 on curl. Overall, Kedavra attains an average Lo-group F1 of 0.85 in 198 seconds, compared with XVada’s 0.88 in 485 seconds and TreeVada’s 0.87 in 1,134 seconds. However, this pattern does not extend to the Hi group: Kedavra terminates with an unhandled exception during inference for liquid, c and rust, and does not infer a grammar for lua, java, cpp, or mysql within the 48-hour limit.

Crucio under a fair evaluation protocol: Crucio completes all Lo subjects and four Hi subjects (liquid, lua, c, and java). However, when its exported grammar is evaluated using the same full-program sampling and parsing protocol as the other tools (Section 4), its F1 scores are extremely low: its best result is 0.47 on while, while all other completed subjects score at most 0.09. The while golden grammar uses only the fixed terminals L and n at expression positions rather than a general identifier rule. This result is consistent with the evaluation asymmetry discussed in Section 3.

XVada across both groups: XVada achieves the highest average F1 score in the Lo group (88%), narrowly exceeding TreeVada (87%) and Kedavra (85%). While these accuracy scores are comparable, XVada reduces the average grammar-construction time by 57% relative to TreeVada (485 versus 1,134 seconds); Kedavra is faster still where it completes (198 seconds). In the Hi group, TreeVada infers a grammar for all seven languages but obtains F1 scores between 4 and 26%. XVada improves the F1 score on every Hi subject, with its strongest result of 99% on liquid, and raises the group average from 12 to 47%. XVada thus provides the strongest accuracy among the tools that complete the Hi-group experiments, although its average runtime is 9% higher than TreeVada’s (51k vs. 47k seconds).

5.2 RQ2: Grammar Size (Compactness)↩︎

EBNF grammar representation is typically more compact than BNF. As Kedavra counts EBNF elements (as opposed to unfolding ?*+ closure operators), the Kedavra count is lower than what we would report for an equivalent BNF-based TreeVada/XVada grammar. Without converting between EBNF and BNF, we can thus not directly compare Kedavra grammar sizes with TreeVada/XVada (which makes the findings presented in the Kedavra study hard to interpret).

Table 4 column S shows that XVada generally infers more compact grammars than TreeVada. On the Lo subjects, XVada reduces average \(S\) from rrmk-Avg_lo_treevada_S to rrmk-Avg_lo_xvada_S and is smaller than TreeVada on 8 of 10 languages. The reduction is especially visible for turtle, json, and minic. On the Hi subjects, the difference is larger: average \(S\) decreases from rrmk-Avg_hi_treevada_S to rrmk-Avg_hi_xvada_S, and XVada is smaller on 5 of 7 languages, especially for c, java, cpp, and rust.

5.3 RQ3: HDD’s Contribution to Accuracy↩︎

Table 5 isolates HDD’s contribution by comparing XVada with and without HDD. To expose HDD’s impact, we want large seed programs to be less likely to exhibit simple grammar-rule alternatives. We thus use a random seed subset (5 of the Table 2 seed programs for Lo, 10 for Hi).

The main effect of HDD is improved recall (on average from 49 to 52% on Lo, raising average F1 from 55 to 58%, with average precision unchanged at 85%). On Hi the effect is larger (except rust): average recall increases from 25 to 29%, average precision from 55 to 60%, and average F1 from 26 to 32%. The largest gains occur when the reduced seed sets are mostly compositions of smaller complete program fragments. For example, liquid improves from 42 to 68% F1, c from 29 to 43%, and lua from 2 to 9%. In contrast, subjects whose reduced seed set already exhibits the relevant alternatives show little or no F1 change. Only in rust, F1 drops indicating HDD added incorrect decomposed alternatives. For both language groups the average HDD runtime overhead is below 1%, i.e., 1.4 of 206 seconds (Lo) and 20 of 7,912 seconds (Hi).

5.4 RQ4: Fuzzing the Python Liquid Parser: 5 Bugs & a CVE↩︎

XVada learns from a black-box parser and encodes the parser’s accept/reject behavior in the inferred grammar. This allows a grammar-based fuzzer to mutate parser-specific derivation trees, helping it reach deeply nested parser states.

Liquid is Shopify’s template language, first implemented in Ruby and since adopted widely (with implementations in python, js, c#, etc.). For RQ4 we pass the XVada-inferred Liquid grammar to the coverage-driven & grammar-aware Nautilus fuzzer [2] to find bugs in the python Liquid engine, which (according to PyPIStats) gets over 1M monthly downloads⁷. (XVada’s grammar inference is blackbox and does not use coverage data; only the fuzzer is greybox.) As the public Nautilus artifact is no longer maintained, we use LibAFL [25]. The fuzzer requires grammars to include whitespace explicitly, which XVada supports. We thus provide the inferred production rules directly to the fuzzer in json format.

Findings: The highest-impact finding was the denial-of-service (DoS) vulnerability CVE-2026-55865 XVada found during black-box grammar inference (without fuzzing). A malformed case tag with no terminating endcase yielded an infinite loop in Python Liquid. An attacker who can submit templates could thus prevent parsing from terminating and consume service resources.

Fuzzing then found five additional bugs (all since fixed by Python Liquid developers). These bugs involve improperly handling malformed or missing tag arguments, nested bracket unfolding, and nested markup blocks, leading to resource-exhaustion failures or uncaught runtime exceptions such as RecursionError and MemoryError.

6 Threats to Validity↩︎

Having a representative sample [26] (a finite set of positive examples where all grammar rules are exercised) is crucial for inferred grammar’s coverage. To best approximate this condition, we sample from golden grammar (where possible) using a standalone fuzzer instead of using real programs as seed/test sets. Real programs tend to be biased toward commonly used parts of a language [2], and therefore may leave many grammar rules unexercised. While this choice improves language coverage, but may make our seed/test sets differ from naturally occurring programs.

7 Related Work↩︎

Large language models (LLMs) have made significant advancements and show remarkable ability in many software engineering tasks. These models demonstrate robust performance in code understanding, enabling effective code summarization, refactoring, verification, and auto-completion. However, theoretical [27] and empirical studies [28]–[31] suggest that LLMs have limited ability to learn formal grammars (such as context-free grammars) from sample programs.

Grammar inference is a long-studied problem. Angluin’s seminal active learning work shows how to learn regular languages from queries and counterexamples [32], and also discusses context-free learning under stronger assumptions [33]. For program inputs, however, these assumptions rarely hold: a parser typically provides only membership queries, and query complexity grows quickly beyond regular languages [34]. Glade showed that this black-box setting can still be effective by learning seed-specific structure and using oracle feedback to generalize input grammars [35].

A second line of work connects grammar inference with compression. Sequitur replaces repeated adjacent sequences with hierarchical rules [36]. The already discussed Arvada, TreeVada, Kedavra, and Crucio adapt this intuition to black-box context-free inference.

Besides oracle answers, white-box approaches also leverage parser internals. Autogram mines grammars from dynamic taints [37], while Mimid maps dynamic control-flow contexts to grammar structure [38]. These techniques can produce well-labeled grammars, but require access to parser internals. More recent static approaches reduce the dependence on seed inputs: Panini infers regular grammars for short ad hoc parsers using summaries of string operations [39], and Stalagmite uses symbolic parsing to infer context-free grammars from recursive-descent parser code [40]. These approaches are complementary to black-box grammar inference: they exploit source code when available, whereas our setting assumes only sample programs and a black-box parser oracle.

8 Conclusions↩︎

XVada introduced several new techniques for deterministic inference of context-free grammars. In an empirical comparison that avoids several pitfalls of recent studies, XVada improved on the highest-scoring competitor (TreeVada) both in grammar accuracy and grammar compactness. XVada also found a CVE in the widely used Python Liquid engine. Fuzzing based on the XVada-inferred grammar found five more bugs, which the Python Liquid developers fixed based on our bug reports. XVada and all experimental data and scripts are publicly available.

References↩︎

---

1. Accessed June 2026: https://github.com/Sinpersrect/kedavra↩︎

2. Accessed June 2026: https://github.com/jg-rp/liquid/tree/v2.2.1↩︎

3. Accessed June 2026: https://github.com/Shopify/liquid-spec↩︎

4. Accessed June 2026: https://github.com/antlr/grammars-v4↩︎

5. Metrics computed via gMetrics [1] (which extends SynC [23], [24]). gMetrics uses ANTLR v3, so we slightly modified v4 grammars to v3 syntax.↩︎

6. Accessed June 2026: https://github.com/Sinpersrect/crucio↩︎

7. Accessed June 2026: https://pypistats.org/packages/python-liquid↩︎