Underpinning Property-Based Testing
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.
| Definitions | Gen. | Enum. | Check. |
|---|---|---|---|
| Expressions | 24,425 | 25,352 | 1,060 |
| Policies | 1,736 | 0 | 58 |
| Schemas | 1,886 | 0 | 0 |
| Total | 28,047 | 25,352 | 1,118 |
