Semantic Reification: A New Paradigm for Random Program Generation

Researchers at ETH Zurich introduced semantic reification, a new paradigm for random program generation that constructs programs based on their control flow and execution paths rather than syntax, ensuring generated programs are semantically correct and terminating even with arbitrary control flow like unbounded loops. Their implementation for C compilers, Reify, uncovered 59 bugs in GCC and LLVM over five months, including 36 wrong-code bugs and 24 long-latent issues, many of which were high-priority and involved semantic characteristics missed by existing tools. The work, presented at PLDI 2026, opens new directions for validating compilers, debuggers, analyzers, and verifiers.

PLDI 2026 https://pldi26.sigplan.org series https://pldi26.sigplan.org/series/pldi / PLDI Research Papers https://pldi26.sigplan.org/track/pldi-2026-papers / Semantic Reification: A New Paradigm for Random Program Generation This program is tentative and subject to change. Thu 18 Jun 2026 14:40 - 15:00 at - Flatirons 2 https://pldi26.sigplan.org/room/pldi-2026-venue-flatirons-2 Generative Testing and Program Synthesis https://pldi26.sigplan.org/track/pldi-2026-papers program We introduce semantic reification, a novel paradigm for random program generation that centers on program semantics rather than syntax. Our key insight is to reformulate random program generation to capture two types of program semantics: 1 compile-time semantics what a program can do , represented by the control flow graph CFG , and 2 runtime semantics what a program actually does , represented by execution paths within the CFG. For any CFG and any execution path on it, semantic reification constructs a program guaranteed to be well-behaved with respect to a specific input and output. This means that when executed with this input, the program deterministically follows the designated execution path to produce the expected output. This paradigm differs from existing work by supporting arbitrary control flow such as unbounded loops and irreducible regions, while still ensuring that the generated programs are semantically correct and terminating. We develop a practical realization of this paradigm. First, we introduce symbolic function reification that integrates a lightweight form of symbolic execution into the generation process to generate an individual, leaf function i.e., a function that is free of function calls . Each leaf function satisfies the constraints of a given CFG and a selected execution path. Second, we compose multiple leaf functions into a larger, more complex program via semantics-preserving peephole rewriting, guided by an arbitrary call graph. Over five months, our implementation for C compilers, Reify, has uncovered 59 bugs in GCC and LLVM 57 confirmed, 27 fixed , 24 of which are long-latent. Among them, 36 are wrong-code bugs, many are high-priority issues, and most of them involve semantic characteristics overlooked by existing tools. We believe semantic reification opens new directions for research beyond compilers, such as validating debuggers, analyzers, and verifiers. This program is tentative and subject to change. Thu 18 JunDisplayed time zone: Mountain Time US & Canada change userProgramSettings Mountain Time US & Canada change userProgramSettings 14:00 - 15:20 | ||| 14:00 20mTalk | PLDI Research Papers | 20m Trace-Guided Synthesis of Effectful Test Generators Zhe Zhou https://pldi26.sigplan.org/profile/zhezhou Purdue University, Ankush Desai https://pldi26.sigplan.org/profile/ankushdesai1 Snowflake, Benjamin Delaware https://pldi26.sigplan.org/profile/benjamindelaware Purdue University, Suresh Jagannathan https://pldi26.sigplan.org/profile/sureshjagannathan Purdue University DOI https://doi.org/10.1145/3808264 20m Semantic Reification: A New Paradigm for Random Program Generation Kavya Chopra https://pldi26.sigplan.org/profile/kavyachopra ETH Zurich, Cong Li https://pldi26.sigplan.org/profile/congli ETH Zurich, Thodoris Sotiropoulos https://pldi26.sigplan.org/profile/thodorissotiropoulos ETH Zurich, Zhendong Su https://pldi26.sigplan.org/profile/zhendongsu ETH Zurich DOI https://doi.org/10.1145/3808268 Pre-print https://connglli.github.io/pdfs/reify pldi26.pdf 20m The Search for Constrained Random Generators Harrison Goldstein https://pldi26.sigplan.org/profile/harrisonjgoldstein SUNY Buffalo, Hila Peleg https://pldi26.sigplan.org/profile/hilapeleg Technion, Cassia Torczon https://pldi26.sigplan.org/profile/cassiatorczon University of Pennsylvania, Daniel Sainati https://pldi26.sigplan.org/profile/danielsainati University of Pennsylvania, Leonidas Lampropoulos https://pldi26.sigplan.org/profile/leonidaslampropoulos University of Maryland at College Park, Benjamin C. Pierce https://pldi26.sigplan.org/profile/benjamincpierce University of Pennsylvania