In an empirical comparison that avoids several pitfalls of recent studies, XVada improves on the highest-scoring competitor (TreeVada) both in grammar accuracy and grammar compactness and finds a CVE in the widely used Python Liquid engine.
Abstract
Black-box context-free grammar inference is crucial for program analysis, reverse engineering, program understanding, fuzzing, and security. But existing approaches such as Arvada, TreeVada, Kedavra, and Cucio struggle with scalability, accuracy, and grammar readability, especially on larger languages. To address this challenge, we introduce XVada with several new techniques for deterministic inference of context-free grammars. In an empirical comparison that avoids several pitfalls of recent studies, 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 bugs, which the Python Liquid developers fixed based on our bug reports. XVada and all experimental data and scripts are freely available.
Large Language Models (LLMs) must strictly adhere to grammatical constraints for reliable structured generation in agentic workflows, code synthesis, and domain-specific language (DSL) generation. Grammar-Constrained Decoding (GCD) enforces this by masking out tokens incompatible with the target grammar at each decodin...
Shu-Yi Ling, Liang-Yi Kang, Jie Liu et al.· Proceedings of the 41st IEEE...· 0 citations
This work proposes a lookahead-guided decoding framework for context-free grammars based on pushdown automata based on bounded pushdown summaries with reachability labels and upper-bound distances to acceptance.
Vincenzo Collura, Karim Tit, Eleonora Giunchiglia et al.· 1 citation
Modern software systems are increasingly variant-rich, and feature models capture this variability formally. The Universal Variability Language (UVL) has emerged as a community-driven standard for expressing such models, but creating and maintaining UVL artifacts remains a manual, expert-driven task. Large Language Mod...
Johannes Stümpfle, Fethiye Tunç, N. Jazdi et al.· Proceedings of the ACM/IEEE...· 0 citations
When generating programs with language models, constrained decoding can apply program analyses to exclude tokens that violate syntax, scope, or typing rules. However, there is a duplication: standard training already teaches the model to suppress the tokens rejected by these analyses. This duplication leads to the ques...
The ANVIL compiler architecture is proposed, where ANVIL performs exceptionally well on leading benchmarks by using language models purely where they are effective, rather than as a catch-all tool.
Priyadarshan Patil, A. Basu, Vikas Reddy et al.· 0 citations
Recent advances in code intelligence are largely driven by large language models (LLMs), which represent code as token sequences and achieve strong results on many software engineering tasks. However, standard token-based approaches often struggle to capture the inherent structural regularities of programming languages...
Qing-Lin Liang, Zhao Zhang, Chen Liu et al.· Proceedings of the ACM on So...· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
