Synsema: Syntax-Guided Learning of Semantically Valid Programs

Generating inputs for systems that process highly structured data, such as compilers, is difficult due to the dual of syntactic and semantic constraints. Traditional approaches rely on manually crafted rules that require deep domain expertise and are difficult to maintain, while modern machine learning methods have to learn syntax and semantics simultaneously which is challenging. We present Synsema, a novel approach that combines insights from both worlds by reformulating the generation of semantically valid programs as a syntax-guided reinforcement learning task. By guaranteeing syntactic validity through the grammar, the agent needs to only learn the language's semantic rules, sampling from a drastically reduced space. We implement our approach in the context of Java and Rust which both exhibit strict semantic requirements, and train an agent to generate interesting and well-formed programs using fine-grained semantic feedback. Applied to compiler testing, we systematically compare different syntax-guided generation procedures with an unconstrained baseline and show that by restricting the sampling space, Synsema learns semantic rules efficiently. While an average of only 0.03% of programs generated by the baseline are semantically valid, Synsema produces a diverse set of programs with a 7.29% success rate that trigger 2.6x more compiler behaviors. In addition, Synsema discovered 5 previously unknown bugs in production compilers, validating the practical impact of our approach.