An End-to-end Theory for Compositional Symbolic Execution: From Expressive Specifications to SMT
Compositional symbolic execution (CSE) is a powerful technique for program verification and bug-finding, yet existing formal theories of CSE do not sufficiently bridge the gap between idealised models and real-world tools. We present mechanised progress towards a foundational, realistic, and end-to-end theory of CSE in the Rocq proof assistant. Our theory advances realism at both ends of the CSE pipeline: it supports an expressive frontend with algebraic data types, logical functions, and lemmas; it also provides a verified connection to SMT-LIB compliant SMT solvers. Our contributions include: (1) a CSE theory that captures practical verification patterns; (2) a standalone, reusable Rocq mechanisation of the SMT-LIB standard; (3) a proven-correct encoding from CSE backend queries to SMT-LIB queries that accounts for semantic discrepancies and optimises using type information; and (4) empirical evidence for the backend by extracting our verified SMT encoding and routing a sizeable fragment of solver queries from the CSE tool Gillian through it.