Graduation Semester and Year
Summer 2026
Language
English
Document Type
Dissertation
Degree Name
Doctor of Philosophy in Computer Science
Department
Computer Science and Engineering
First Advisor
Christoph Csallner
Abstract
Context-free grammars are essential for a number of software engineering tasks like program understanding, debugging, and grammar-based testing. However, formal language descriptions (i.e. grammars) are often unavailable, outdated, or inaccessible because parsers are closed-source or cannot be instrumented. Black-box grammar inference addresses this gap using only valid sample programs and parser acceptance decisions. The problem is challenging because finite samples rarely exercise all language features or their combinations, while the inference process cannot inspect the parser’s internal representation of syntax. This dissertation develops deterministic techniques for black-box context-free grammar inference. The first tool, TreeVada introduces the structural assumption that balanced brackets often indicate nested language concepts. It uses this structure to initialize parse trees, recursively applies learned rules, and replaces nondeterministic exploration with deterministic steps. XVada extends this approach to improve scalability to larger languages. It accelerates inference through batch processing of candidate generalizations, introduces a mechanism for learning non-recursive rules, and applies Hierarchical Delta Debugging to decompose complex parse trees and expose simpler rule alternatives. In an empirical evaluation, TreeVada improved the average F1 score by 19.5\% over Arvada while providing a 2.4× speedup. Across seventeen languages grouped by grammar size and complexity, XVada maintained comparable accuracy on smaller languages while reducing average inference time by 57\% relative to TreeVada. On larger languages, XVada increased the average F1 score from 12\% to 47\%, a gain of 35 percentage points, and reduced average grammar size by 20\%. XVada demonstrated the practical utility of the inferred grammar, as it revealed one CVE, and a fuzzing campaign found 5 more bugs in Python Liquid engine, which the developer fixed upon our bug report. Overall, TreeVada and XVada provide a progressive foundation for practical black-box context-free grammar inference, improving both scalability and grammar quality.
Keywords
Grammar inference, Reverse engineering, Context-free grammars, Grammar-guided fuzzing, Security vulnerabilities, Hierarchical delta-debugging, Brackets, Nesting concepts, Parse tree, Deterministic inference
Disciplines
Computational Engineering
License
This work is licensed under a Creative Commons Attribution 4.0 International License.
Recommended Citation
Arefin, Mohammad Rifat, "Deterministic Black-Box Context-Free Grammar Inference: Scaling from Small to Big Languages" (2026). Computer Science and Engineering Dissertations. 16.
https://mavmatrix.uta.edu/cse_dissertations2/16