← All papers
First page of Underpinning Property-Based Testing

Underpinning Property-Based Testing

Ernest Ng, Segev Elazar Mittelman, Joshua M. Cohen, Katherine Hough, Michael Hicks, Harrison Goldstein

cs.PL Nov 16, 2026 · v1
Implements Basalt, a Lean library of property-based testing generators that run as executable samplers and also support proofs about their distributions.
As the property-based testing community strives to automate challenging parts of the process away from users — in particular, the construction of generators — it is critical that we can clearly state what it means for that automation to be correct. We present a new framework for PBT, implemented in the Lean theorem prover, that provides a more solid foundation to build on. Our generators are interpretable: interpreted one way, they can be run efficiently as programs that sample randomness; and interpreted another way, they enable a wide range of correctness proofs, including proofs about distributions that other foundational PBT models do not support. We evaluate our framework extensively, with both small and large benchmarks and case studies, arguing that the extra power brought by distributional proofs is practically important for the next generation of generator automation.

Automated synthesis of property-based testing generators lacks a clear correctness foundation. Existing foundational models can prove soundness and completeness of a generator, but they cannot prove properties about the distributions generators sample from.

Basalt is a Lean library in which generators are written against a Generator type class. Interpreted in IO, a generator runs as an efficient random sampler using a C SplitMix64 PRNG and optimized combinators. Interpreted as sub-probability mass functions, it supports proofs of soundness, completeness, distributions, termination and cost. Lean's partial_fixpoint lets generators that do not terminate structurally, such as rejection samplers, be written without fuel.

Basalt generators run at least as fast as Haskell QuickCheck and OCaml Base_quickcheck. The Palamedes and Specimen synthesis tools were retargeted to Basalt, and Specimen now derives correctness proofs for the generators it builds. In industrial case studies, Cedar generators were proved sound, complete and within requested size limits, and Strata generators helped find bugs.

DefinitionsGen.Enum.Check.
Expressions24,42525,3521,060
Policies1,736058
Schemas1,88600
Total28,04725,3521,118
Specimen-derived Basalt code for Cedar (lines of derived code)