Semantic Reification: A New Paradigm for Random Program Generation
Semantic reification is a new approach to random program generation that focuses on program semantics instead of syntax. It captures both compile-time and runtime semantics to ensure generated programs are well-behaved and produce expected outputs. The implementation, called Reify, has successfully identified numerous bugs in existing compilers, highlighting its potential for broader applications in software validation.
- ▪Semantic reification emphasizes program semantics over syntax for random program generation.
- ▪It captures compile-time and runtime semantics to ensure well-behaved program outputs.
- ▪The Reify implementation has uncovered 59 bugs in GCC and LLVM, including high-priority issues.
Opening excerpt (first ~120 words) tap to expand
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.
…
Excerpt limited to ~120 words for fair-use compliance. The full article is at Sigplan.
Discussion
0 commentsMore from Sigplan
