WorksComputer Science
Underpinning Property-Based Testing
Abstract
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.
Introduction
underpin trans. To support or strengthen. . . especially by laying a solid foundation. . . or by substituting stronger or more solid for weaker or softer materials.
Oxford English Dictionary
Property-based testing (PBT) combines software testing, which is critical for ensuring that software systems behave as expected, with formal methods, which give a robust language for formally stating those expectations. Rather than checking a function’s output on one particular input, like standard unit testing, PBT checks that a property holds over a whole class of inputs. When testing compilers, module APIs, and databases, for example, that class might be well-typed programs, well-formed method-call sequences, or valid SQL queries. Valid inputs like these are often extremely rare in the space of all inputs, so testing such properties requires constrained random generation: efficiently sampling from the inputs in that class.
To address the challenge of constrained random generation, the PBT literature uses generators: programs specifically designed to efficiently sample from an appropriate distribution of test data. Well-designed generators have been used to uncover interesting bugs in complex targets like compilers [28, 63], stateful services [44], and high-assurance automotive software [1], and can outperform weaker generators enhanced with feedback-guided fuzzing [50, 54, 78].
Needing to hand-write good generators is a usability barrier for PBT [38], so recent work has begun to automate the generator creation process: systems like Cобb [48], Palamedes [39], and QuickCheck [32, 64] automate the production of generators for a wide range of use cases. AI programming tools can extend that range further [78]. Unfortunately, existing approaches for generator synthesis offer, at best, partial guarantees that the generators they produce are high quality. Existing tools can show that a generator is sound and complete: it is able to generate all
Authors’ Contact Information: Ernest Ng, Amazon Web Services, Boston, MA, USA and Cornell University, Ithaca, NY, USA, [email protected]; Segev Elazar Mittelman, University of Maryland, College Park, MD, USA and Amazon Web Services, Arlington, VA, USA, [email protected]; Joshua M. Cohen, Amazon Web Services, Boston, MA, USA, [email protected]; Katherine Hough, Amazon Web Services, Arlington, VA, USA, [email protected]; Michael Hicks, Amazon Web Services, Arlington, VA, USA and University of Pennsylvania, Philadelphia, PA, USA, [email protected]; Harrison Goldstein, University at Buffalo, SUNY, Buffalo, NY, USA, [email protected]. and only the values that satisfy the chosen set of constraints. More than that, though, a generator’s distribution must be useful for finding bugs. For example, if a generator could theoretically produce every natural number, but in practice it produces 0 half of the time and has a vanishingly small chance of producing values greater than 30, then it will miss bugs that manifest only with larger numbers. Modern frameworks for synthesizing generators and proving their correctness say nothing about distributions; indeed, Palamedes will produce a skewed Nat generator like the one just described. It is possible to address distributional problems through experimentation and tuning, e.g., using a tool like Tyche [41], but not always — if a user wants to rule out some very rare bad behavior, for example, they may need to test their generator for as long as or longer than the system under test. Ultimately, since developers use tests to detect defects in their code, poorly distributed generators constitute a real risk to software correctness.
In this paper, we address these challenges with a new library called Basalt, written in Lean [25], that can express distributional correctness properties to ensure that both hand-written and synthesized PBT generators are high-quality. Basalt provides a foundational semantics, just like the original foundation for PBT, QuickChick [65], but uses a richer probabilistic semantics, rather than QuickChick’s possibilistic one. This means that clients can prove distributional properties about their generators, e.g., that a generator produces the uniform distribution, that the expected size of a generated value is less than a certain bound, or that the probability of a certain feature exceeds a minimum threshold. Basalt generators are also more expressive than prior encodings: they can express potentially non-terminating generators, which arise naturally (even a simple generator for arbitrary natural numbers is not structurally terminating), and users can prove almost-sure termination as needed.
Basalt is not just a formal framework; it is a fully featured library designed for practical use. Thanks to a tagless-final embedding [8], the same code that is used for proofs is directly executable. Leveraging recent work on boosting PBT generator speed [68], these generators run at least as fast as flagship PBT frameworks like Haskell’s QuickCheck and OCaml’s Base_quickcheck (§ 5.1).1 We show that automatic generator synthesis tools, specifically Palamedes and Specimen [70] (a port of QuickChick to Lean), can be re-tooled to construct Basalt generators, and we use this new underpinning to automatically derive correctness proofs for Specimen generators. Finally, we implement generators for two real-world systems in Basalt. We use Specimen to derive Basalt generators for the Cedar policy language [24], proving distributional properties desired by the Cedar development team, and we use LLMs to implement generators for the Strata intermediate verification language [73], proving correctness and distributional properties about them, thereby demonstrating that our proof infrastructure is legible to AI-based proof tools. Ultimately, we position Basalt as a new underpinning for PBT, with the theoretical strength and practical engineering necessary to build trustworthy test infrastructure.
In the rest of this paper, we present the following contributions:
The design and implementation of Basalt, a generator library with a probabilistic semantics which supports efficient and potentially non-terminating generators (§ 2 and § 3).
Proof infrastructure for reasoning about the support, distributions, termination, and cost of generators (§ 4).
An evaluation (§ 5) that benchmarks Basalt’s performance, shows that Basalt can underpin synthesis tools Palamedes and Specimen, and applies Basalt to two real-world systems, Cedar and Strata.
We conclude with related (§ 6) and future (§ 7) work.
Basalt Basics
In this section, we describe the core of Basalt, which allows users to write generators that support both execution and distributional proofs.
Basalt by Example
Let us look at two Basalt generators to get a sense of the pieces that they are built from. The simplest possible generator looks like this:
def genFiveToTen [Generator G] : G Nat := choose 5 10
This generator uniformly samples a natural number between 5 and 10 (inclusive). As with QuickCheck [22], Basalt generators can be combined using monadic do-notation:
def genPairFiveToTen [Generator G] : G (Nat × Nat) := do
let x ← genFiveToTen
let y ← genFiveToTen
return (x, y)
The back-arrow notation can be read as “sample from the generator on the right and bind it to the variable on the left.”
The Generator Type Class
The example generator definitions may look a bit mysterious; genFiveToTen produces a value of type G Nat, but G itself is not defined. Indeed, the definitions are polymorphic over the choice of G — Basalt generators use a typed tagless-final [8] embedding, where generators are defined only by the operations that they support.
Concretely, a generator is any type constructor that can implement the following simplified type class (see § 3 for the full version):
class Generator (g : Type → Type) extends
Monad g,
RandomChoice g,
A generator must be a Monad, which enables the QuickCheck-style do-notation. A generator also needs a way to make random choices: the RandomChoice class provides it as a single operation, choose, which makes an inclusive choice over a nonempty range of natural numbers.
class RandomChoice (m : Type u → Type v) where
choose : (lo hi : Nat) → (h : lo ≤ hi) → m Nat
Every other way of making random choices is built on top of choose.
The benefit of a tagless-final embedding is that the same program can be interpreted in multiple ways. This allows us to write one generator and use it twice: once for testing and once for proofs of correctness. It works because the explicit type of a generator like genPairFiveToTen is:
genPairFiveToTen : ∀ {G : Type → Type} [Generator G], G (Nat × Nat)
We can read this as saying “if you give me a type constructor G and show that G has all of the operations of a Generator, then I can give you a generator of type G (Nat × Nat). In the next two subsections, we present Generator instances for testing and proof, respectively.”
Generator Instance: IO
To run a generator during testing, we use the IO instance of Generator, which does what you might expect: the monad instance sequences effectful computations, and the RandomChoice instance samples a PRNG. We can use Lean’s #eval command to sample from the generators in § 2.1 by instantiating G with IO:
#eval (genFiveToTen : IO Nat) #eval (genPairFiveToTen : IO (Nat × Nat))
-- 7 -- (10, 6)
Generator Instance: SPMF
To prove properties about a generator, including ones about its distribution, we use the SPMF instance of Generator. This instance interprets generators as sub-probability mass functions (SPMFs), implemented in Lean as follows:2
def SPMF (α : Type) : Type := {μ : α → ℝ≥0∞ // (∑' a, μ a) ≤ 1}
The mass function assigns a mass (essentially a probability) to every value in the domain .3 And we require that the sum of the mass over all s be at most 1.
To build the interpretation, we can start with RandomChoice. We express a random choice as a uniform distribution over a range:4
instance : RandomChoice SPMF where
choose lo hi h :=
let k := hi - lo + 1
⟨fun n => if (lo ≤ n ∧ n ≤ hi) then (1 / k) else 0, ...⟩
The angle-bracket notation pairs a value, in this case our mass function, with a proof, in this case the proof that the total mass is bounded above by 1. We omit the proof for brevity. We discuss our reasoning for this particular randomness primitive in Appendix § 9.
Then we can define the monad operations as the standard discrete probability monad [33, 67]:
instance : Monad SPMF where
pure a := ⟨fun a' => if a' = a then 1 else 0, ...⟩
bind x f := ⟨fun b => ∑' a, x a * f a b, ...⟩
The pure operation produces a point-mass distribution, and bind sequences two distributions, averaging the continuation over outcomes of , weighted by their probabilities.
In this paper we visualize SPMFs as jars of colored sand, where each color corresponds to a different outcome. Since the total mass of all outcomes is at most one, the jar cannot be filled past the top. To sample a value, imagine picking a random spot in the jar and taking the outcome whose color is at that spot. Figure 1 visualizes genFiveToTen.
Figure 1. genFiveToTen, drawn as a jar of sand.
Faithfulness
A key benefit of Basalt is that both the IO and SPMF interpretations run the same code, but that does not necessarily mean that they must perfectly agree. One might hope we can make this argument by parametricity, but in Lean it is technically possible for a generator to inspect types. To get around this, we prove faithfulness — agreement between the code that runs and the code for proofs — on a per-generator basis. We describe this proof process at a high level in Appendix § 10, and the full machinery appears in the artifact.
Recursive Generators in Basalt
In this section, we complete the Generator type class, and discuss how Basalt represents recursive, potentially non-terminating generators.
More Examples
Figure 2 shows two recursive generators. The first, genNat, produces an arbitrary natural number. At each step, the generator chooses from two options with equal probability (the oneOf combinator uses choose to choose uniformly between branches). It may return 0, or else it may generate a natural number by calling genNat recursively and then add 1 to it.

Figure 2. Recursive generators: genNat produces arbitrary natural numbers; genHeap produces valid min-heaps.
The second, genHeap, produces valid min-heaps (trees whose values never decrease along any root-to-leaf path) [23]. Again, the generator chooses from two options with equal probability. It may return a leaf, ending generation. Or it may compute a new value , by adding a random delta to lo (the minimum allowable value in the sub-heap), and recursively generate two sub-heaps whose new minimum value is . The result is a generator that produces all possible valid heaps, and only valid heaps.
Relaxing Structural Termination
Neither genNat nor genHeap terminates structurally, i.e., by recursing on strictly smaller inputs. Instead, these generators terminate almost surely (i.e., with probability 1): genNat stops at each step with probability , and for every pair of children that genHeap creates, one of them will end up a leaf in expectation. This feature of Basalt makes it possible to avoid programming around and reasoning about fuel. In QuickChick, genHeap would instead need to take a fuel argument and return an Option (see Appendix § 13). The fuel argument ensures that the generator always has some decreasing argument for its recursive calls. This fuel management causes a number of paper cuts: the user needs to read and write code that is unrelated to the generator’s actual operation; the result is wrapped in an Option, so downstream users need to handle out-of-fuel failures; end-users need to decide on an amount of fuel to pass (which could potentially be insufficient); and proofs need to reason about termination and correctness all at once.
Most importantly, indexing generators with fuel makes distributional arguments much more complicated. For example, consider a generator that does rejection sampling to filter genPairFiveToTen down to a uniform distribution over those pairs that are in sorted order:
def genPairFiveToTenSorted [Generator G] : G (Nat × Nat) := do
let (x, y) ← genPairFiveToTen
if x ≤ y then return (x, y) else genPairFiveToTenSorted
partial_fixpoint
This generator is clearly not structurally terminating, but it does terminate “almost surely,” since each attempt succeeds with a fixed, positive probability. The generator also obviously gives the distribution we want, with an equal chance of producing any sorted pair. If we added fuel, the distribution would no longer be strictly uniform; it would only be uniform when conditioned on returning some.
The Full Generator Type Class
To support generators that do not terminate structurally, the Generator class needs a few more pieces:
class Generator (g : Type → Type) extends
Monad g,
RandomChoice g,
(∀ α, Inhabited (g α)),
(∀ α, CCPO (g α)),
MonoBind g
Lean requires Inhabited, CCPO, and MonoBind in order to use its partial_fixpoint feature.5 Lean’s standard library defines a CCPO as follows:
def chain (c : α → Prop) : Prop := ∀ x y, c x → c y → x ⊑ y ∨ y ⊑ x
class CCPO (α : Sort u) extends PartialOrder α where
has_csup {c : α → Prop} (hc : chain c) : ∃ s, ∀ x, s ⊑ x ↔ (∀ y, c y → y ⊑ x)
Given a partial order (), a chain is a totally ordered subset of values under that partial order. If all chains in the partial order have least upper bounds, then we say that partial order is “chain-complete” — i.e., it is a CCPO.
To understand this paper’s contributions, we can focus on a relatively narrow application of this idea: CCPOs give a way to build fixpoints of functions. Every CCPO has a least element , the upper bound of the empty chain. If a function is monotone (i.e., ), then has a least fixed point. To see why, imagine applying to over and over; since and is monotone, this gives a chain:
Each element of the chain approximates the fixed point more closely, and in many cases the least upper bound of the chain (which is guaranteed to exist) is the fixed point itself. The partial_fixpoint annotation (which appears in genNat and genHeap) uses Lean.Order.fix to represent non-terminating recursion; we show what these fixed points look like for SPMFs below.
The Inhabited constraint is required by partial_fixpoint, and the MonoBind constraint asserts that the Monad’s bind operation is monotone with respect to the partial order.
Revisiting IO
The IO instances for CCPO, Inhabited, and MonoBind are all provided by Lean in the standard library. Lean compiles partial_fixpoint definitions to ordinary partial functions that do not interact with Lean’s kernel. We can sample these generators just like their non-recursive counterparts:
#eval (genNat : IO Nat)
-- 4
#eval (genHeap 0 : IO (Tree Nat))
-- node (node leaf 4 leaf) 2 (node leaf 3 leaf)
Revisiting SPMFs
The CCPO instance for SPMFs is much more interesting. Recall that the total mass of an SPMF is allowed to be less than one. If the probabilities of all terminating outcomes sum to less than one, then we can interpret the remaining mass as the probability of no terminating outcome – in other words, divergence.
We can construct a CCPO instance that builds on this intuition. First, we need a partial order that orders distributions by how well defined they are. Concretely:
instance : Lean.Order.PartialOrder (SPMF α) where
rel p q := ∀ a, p a ≤ q a
In other words, is less than when assigns at least as much mass to every as does; the probability of an event can only go up along a chain.
To build some intuition, recall the jars of sand from Figure 1. So far, every jar has been full, but now we consider what happens when there is some empty space at the top; an unfilled jar represents an SPMF whose total mass is less than one. If we pick a spot in the empty space, we get no value at all; in other words, the generator diverges. If jars p and q are ordered by the relation above, then we can get from p to q by only adding sand, never removing any. A chain is then a sequence of jars, each with at least as much sand of each color as the one before it. If we want to know what the least upper bound of the chain looks like, we fill a jar with the maximum of each color of sand that appears in any jar in the chain.
Figure 3. Two jars with p ⊑ q.
Put back into Lean, the CCPO instance for SPMF looks like:
instance : CCPO (SPMF α) where
has_csSup := fun c => ⟨⟨fun a => ⟨⋃ μ ∈ c, μ a, ...⟩, ...⟩
In other words, the least upper bound of a chain is the SPMF where the mass of each outcome is the supremum of its masses along the chain.
Let us revisit genNat, now written out explicitly with Lean.Order.fix:
def genNatExplicit [Generator G] : G Nat :=
let f := fun g => oneOf [
fun () => return 0,
fun () => do let n ← g; return (n + 1)
]
Lean.Order.fix f
This generator either stops with probability and produces 0 or else recursively generates a number and returns . Interpreted at SPMF, the iteration chain of starts from the empty jar , as shown in Figure 4: each application of adds sand for one more outcome, never removing any. The least upper bound of this chain assigns probability to each , and it is a fixed point of : it is exactly genNat’s distribution. Practically, this means that we can work with this definition in Lean safely, even though it does not terminate structurally.
Figure 4. The chain of more-defined distributions formed by iterating f from the definition of genNat.
Size and Backtracking
Basalt also supports two common patterns from real PBT generators: automatic handling of sizes and infrastructure for backtracking. Rather than support these in Generator, we layer them on top and give each its own proof infrastructure: Basalt provides sizes through an auxiliary Sized type class and backtracking via the OptionT monad transformer. See Appendix § 11 and Appendix § 12 for more detail.
Proving Properties of Generators
So far we have seen the underlying representation of Basalt generators, along with a few ways to interpret them. Now, we lean more heavily on the SPMF interpretation specifically to enable distribution-aware proofs about generators. We discuss a variety of properties that developers can prove (§ 4.1 and § 4.2), and our approach to proof automation (§ 4.3). Finally, we discuss the trade-offs between proofs and sampling for generator validation (§ 4.4).
Proofs about Support
The first two properties that we care about proving for a generator are well known in the literature: soundness and completeness [30, 31, 65, 77]. To define these properties, we first need to define support in the context of SPMFs; the support of a generator is the set of values with nonzero mass:
def support (p : SPMF α) : Set α := {x | p x ≠ 0}
Then a generator is sound if every a in the support of g satisfies some predicate P.
def IsSound (g : SPMF α) (P : α → Prop) : Prop :=
∀ a, a ∈ SPMF.support g → P a
If we think of as the precondition of a property under test, then soundness says that will not violate the property’s precondition and cause false positives. And a generator is complete if every that satisfies is in the support of .
def IsComplete (g : SPMF α) (P : α → Prop) : Prop :=
∀ a, P a → a ∈ SPMF.support g
If cannot produce some values that satisfy , then no matter how many tests we run we may fail to exercise some aspects of the target system. We often combine these properties into one, IsSoundAndComplete. We can prove that genHeap is sound and complete with respect to isHeap, a definition of the min-heap invariant.
theorem genHeap.sound_complete :
IsSoundAndComplete (genHeap lo) (isHeap lo)
For this and all other theorems in this section, we give the full proof scripts in Appendix § 14; most of these proofs are quite short, thanks to automation that we discuss in § 4.3.
Proofs about Distributions
Soundness and completeness are expressible in other PBT frameworks; the properties in this section require a semantic domain like SPMFs to express and prove.
Probabilities. The quintessential property that becomes provable with our SPMF semantics is the probability of a particular outcome.
def ProbabilityOf (g : SPMF α) (a : α) : ℝ≥0∞ := g a
This allows us to characterize parts of the distribution, potentially highlighting issues that could impact testing. We can prove that genHeap puts half of its mass on the empty heap:
theorem genHeap.prob_empty : ProbabilityOf (genHeap lo) leaf = 1 / 2
This is quite bad! The empty heap is not useful for testing, and thus in practice we might want to tune genHeap to ensure that it produces a more interesting distribution.
Expected Values. We can also talk about expected values over the distribution of a generator. Concretely, if we are given a function over the values that generates, we can compute an expected value as follows:
def ExpectedValue (g : SPMF α) (f : α → ℝ≥0∞) : ℝ≥0∞ := ∑' a, g a * f a
Choosing lets us measure various aspects of the distribution, for example, the average size of a generated value or the average number of times a certain constructor appears. We can prove that the expected value of genNat is at most 1:
theorem genNat.expect_le : ExpectedValue genNat (fun n => n) ≤ 1
This tells us that genNat mostly produces small numbers; in fact, it is exactly the skewed generator described in § 1. Like genHeap, it might need some tuning to be actually usable for testing.
Almost-Sure Termination. Since we allow generators that do not terminate structurally, we might also want to prove almost-sure termination. We define mass as the sum of the masses of the values can generate, and then we say a generator almost surely (AS) terminates if that mass is 1:
def mass (p : SPMF α) : ℝ≥0∞ := ∑' a, p a
def IsAlmostSurelyTerminating (g : SPMF α) : Prop := SPMF.mass g = 1
AS termination might seem net-neutral, since it fixes a problem that we created for Basalt. But remember that allowing generators that do not terminate structurally brings them more in line with the way QuickCheck generators are naturally written, enables more flexible distributional control, and avoids the overhead of fuel in termination-insensitive proofs.
Cost. Another correctness criterion that Basalt unlocks is efficiency. Two generators that have the same support can achieve that support in very different ways. For example, genHeap produces valid heaps directly, “by construction,” but one could also generate heaps by generating arbitrary trees until a heap happens to show up. We provide the following predicate for expressing efficiency in terms of the relationship between generated values and the number of choices the generator makes to produce them:
def IsCostBounded (g : SPMF.Cost α) (c : α → Nat) : Prop :=
∀ (a, n) ∈ SPMF.support g, n ≤ c a
This requires a new interpretation of generators, SPMF.Cost, where SPMF.Cost is equivalent to SPMF (). The definition is the same as SPMF, but every choose adds 1 to the running total (the Nat), and bind adds up the totals of the computations it sequences. We can show that our genHeap makes choices, where is the size of the tree and is the sum of the values in the tree:
theorem genHeap.cost_bounded :
IsCostBounded (genHeap lo) (fun t => 3 * t.size + t.sum + 1)
The cost model keeps us honest: looking only at the structure of genHeap, we might conclude that it makes a number of choices linear in the size of the tree, but each call to genNat also makes a number of choices linear in the value it produces, so we have to account for those costs as well.
Positive AS Termination. We can combine many of the above properties — AS termination, expectation, and cost — to prove a stronger property about generator efficiency. AS termination says that a generator eventually terminates, but this does not guarantee that it does so in a reasonable amount of time. We can also prove positive AS termination, which additionally requires the expected running time to be finite. A generator is positively AS terminating if it is AS terminating and its expected cost is bounded by some finite B:
def IsExpectedCostBounded (g : SPMF.Cost α) (B : ℝ≥0∞) : Prop :=
ExpectedValue g (fun (_, n) => n) ≤ B
Producing n with genNat takes choices, and we just saw that the expected value of genNat is at most 1. So we expect genNat to make at most 2 choices on average, and indeed we can prove it:
theorem genNat.expected_cost_bounded :
IsExpectedCostBounded genNat 2
Together with genNat.terminates (Appendix § 14), this shows that genNat is positively AS terminating. Not every AS terminating generator is positively AS terminating. At each step, genHeap either stops with probability or recurses twice. On average, each call to genHeap makes exactly one more recursive call. We can prove that no finite bound holds:
theorem genHeap.not_expected_cost_bounded {B : ℝ≥0∞} (hB : B ≠ ⊤) (lo : Nat) :
¬ IsExpectedCostBounded (genHeap lo) B
Combined with genHeap.prob_empty, this paints a particularly poor picture of genHeap: half of its heaps are empty, and yet generating a heap takes unboundedly many choices on average. In the language of branching processes [42], genHeap is critical: it terminates with probability 1, but its expected cost is infinite.
Compositional Proofs via Program Logics
The previous subsections outline what users might prove with Basalt, but not how they prove those things. Some of the proofs are straightforward and can be done easily with Lean’s built-in proof automation, but others are tedious without extra help.
We define a tactic called walk (which appears in many of the proofs in Appendix § 14) that implements verification condition generation based on weakest preconditions [27] for a wide range of theorems about generators. For each shape of theorem, we implement a lightweight program logic: soundness uses a demonic nondeterminism semantics [59, 82]; completeness uses an angelic semantics that follows a style similar to incorrectness logic [60] and coverage types [80]; termination uses an expectation logic that is real-valued rather than truth-valued [46, 57]; and cost bounding works like soundness at a different interpretation. We give an example of this tactic in action in Appendix § 15.
We chose to build our own machinery here, rather than rely on Lean’s built-in verification condition generation tactic [74] or one of the emerging Lean program verifiers like Loom [35] and VCVio [76], to give ourselves maximal control. Lean’s built-in machinery only works over Prop-valued assertions, and all of the existing machinery handles termination differently from how we do. As these systems mature, we will revisit our approach to automation.
We also understand that many users will prefer to write correctness proofs like the ones in this section with the help of AI. In § 5, we describe some real-world workflows that use both our walk tactic and AI assistance to build generator correctness proofs; we see no need for users to have to choose one or the other.
Proofs and Testing: Better Together
If a developer is not ready to prove properties of their generator yet, they can also test their generators to get a sense of how they perform. Existing work has explored this approach in detail, and Basalt provides commands for getting statistical feedback from generators that is similar to what libraries like QuickCheck and Hypothesis [56] provide. A user could also pipe their generator statistics into a tool like Tyche [41] to make the statistical feedback visual.
Users of Basalt may develop hypotheses about distributional properties using testing and then choose to prove those properties to get stronger guarantees. Basalt can also prove properties outside the reach of testing, answering questions such as:
Can this generator, in principle, generate every value I care about? Issues of completeness cannot be validated by sampling, by definition. This kind of issue appears in the literature: Lampropoulos Lampropoulos [49] discusses how when testing information-flow control designs, a generator for indistinguishable machine states missed a large part of the state space.
Are there rare cases where this generator produces a bad (invalid, extremely large, etc.) value? If an event is rare, the user may need to test their generator for longer than their system under test to be confident that bad events will not come up in practice.
Does a generator with parameters behave a certain way for all possible parameters? If a generator is parameterized (e.g., by a size bound, by data, or even by another generator),
it is impossible to sample it without first picking values for its parameters; this means it is difficult to establish certain properties in a vacuum. Pałka et al. [63]’s generator for well-typed lambda terms, for example, is parameterized by a generator for types. Sampling can only validate properties about the two generators together, while proofs can decouple those properties.
Is the distribution of this generator equal to one I care about? For applications where specific distributions are critical (e.g., when a precise distribution of values is needed to evaluate performance), sampling cannot give a firm guarantee of distributional equivalence. Some tools in the literature target uniform distributions [7, 21], while others attempt to match arbitrary user-defined distributions [75, 81]; none of these tools provide proofs.
Does the generator terminate and is the expected size of generated values bounded? Sampling a generator that fails to terminate, or that produces arbitrarily large values, can slow down development and lead to frustrating feedback loops. As discussed above, generators like genHeap have infinite expected cost and may rarely produce extremely large values; this shows up in the literature as well [7, 58].
We recommend a balanced approach, combining testing for quick feedback with proofs for generators as they evolve over time.
Scaling up Basalt
So far, we have seen that Basalt enables new kinds of validation for PBT generators; in this section, we show how it can scale to real-world workflows. First, we argue that Basalt is a competitive choice based on performance: we show that Basalt generators run at least as fast as generators in established PBT frameworks (§ 5.1). Second, we show that Basalt can serve as a foundational substrate for generator automation by retargeting two existing generator-synthesis libraries, Palamedes [39] and Specimen [70] (a Lean port, and expansion, of QuickChick [51]), to use Basalt (§ 5.2). This closes the loop discussed in § 1: users can synthesize a generator, tune it, and guarantee that it is high-quality. Finally, we present two industrial case studies of Basalt. We used it to develop generators for well-typed programs in Cedar, an open-source authorization language used widely in industry (§5.3.1). We also used Basalt to develop generators for well-typed programs in Strata, an intermediate verification language that is under active development at a major technology company (§ 5.4). Development of the proofs and generators in these case studies was greatly accelerated by AI-assisted programming tools, demonstrating a compelling vision for how Basalt can scale in practice.
Run-Time Performance
Basalt is designed not just to prove properties about generators, but also to execute them on real systems. For generator execution to be practical, it must be fast. (Indeed, a recent PBT user study reveals that industry PBT practitioners run tests frequently with a limited time budget [38].) Inspired by recent work on improving PBT generator performance [68], we implemented two optimizations that ensure Basalt generators run efficiently. First, rather than use Lean’s standard IO.rand, which we found introduced several unnecessary allocations for every random draw, we implemented the SplitMix64 PRNG [71] in C and linked it into a standalone Lean library that Basalt calls.6 Second, we implemented common generator combinators like oneOf and frequency as macros that expand to if-chains; this avoids allocating lists of generators in a tight loop.
Figure 5 shows the results of a lightweight experiment that demonstrates Basalt’s performance. It is faster than Haskell’s QuickCheck, OCaml’s Base_quickcheck, and Lean’s Plausible. The experiment measures four simple workloads: valid binary search trees (BSTs), valid heaps, sorted lists, and unconstrained natural numbers. We implemented each workload as idiomatically as possible while ensuring that each generator produces the same distribution of data. Appendix § 18 gives the generators for every implementation. The figure shows generator throughput. We chose the number of values to generate to ensure that start-up time does not dominate the measurement; a faster generator (e.g., for natural numbers) generates more samples (70M) than a slower generator (e.g., for BSTs, 280K). The chart reports the geometric mean of the throughput over 20 trials. We find that Basalt is faster than the comparisons, and much faster than Basalt without the aforementioned enhancements.
Figure 5. Generation throughput of Basalt vs. Haskell’s QuickCheck vs. OCaml’s Base_quickcheck vs. Lean’s Plausible. We compared each implementation with Basalt on each benchmark using Welch’s t-test on log throughput. We corrected the p-values for multiple comparisons with Holm’s method. Every difference is significant: all p-values are well below 0.001. Experiments were completed on an M5 Max MacBook Pro.
Basalt as a Foundation for Automatic Generator Synthesis
We designed Basalt’s generator API to match abstractions provided by popular PBT libraries, like QuickCheck. Nevertheless, the need to hand-write generators is a known challenge to PBT adoption [38], so we also designed Basalt as a potential backend for existing frameworks for automatic generator synthesis. As a backend, Basalt gives these frameworks’ users the ability to write distributional proofs about their synthesized generators, and also allows the frameworks’ developers to synthesize proofs about their synthesized generators. To demonstrate this potential, we retrofitted two Lean generator synthesis tools – Palamades [39] and Specimen [70] (based on automation in QuickCheck [51, 64]) – to target Basalt.
Palamedes. Palamedes [39] is a recently published library that uses deductive program synthesis to automatically produce PBT generators. Basalt and Palamedes use different generator abstractions (Palamedes uses a free generator [37] as its core data structure), so the main task was swapping one for the other. First, this means that some of the optimizations that Palamedes performs in the object language (by pattern-matching on the structure of a generator) need to be done in the meta-language (by pattern-matching on the syntax of the generator) when using Basalt. Second, the free generator structure approach means that Palamedes handles recursion implicitly, through the following constructor:
indexed : (Nat → Gen (Option α)) → Gen α
The support of .indexed f is defined as the union of the supports of all f n, under the assumption that f is continuous.
The first of these issues turned out to be less of an issue than we thought, since Palamedes already needed to do some meta-programming to manage optimization under binders. We converted a few object-language analyses and moved the rest to the meta-programming that Palamedes was already doing. The bigger change was non-termination; rather than try to model .indexed directly, we opted to convert the recursion combinators (the unfold operations) to partial_fixpoints and change the proof infrastructure to use our reasoning principles.
At the time of writing, Palamedes still only automates proofs for soundness and completeness (as it did in the original paper), but we think automating termination and cost proofs for a subset of generators should also be possible. In the meantime, users can use AI-based programming tools to fill in the missing proofs.
Specimen. Specimen [70] is a Lean port of Rocq’s QuickChick PBT library, which automatically derives generators for data that must satisfy predicates expressed as inductive relations [32]. To derive such generators, Specimen attempts to find the best sub-generators for a relation’s constructors. Specimen finds these sub-generators by searching over candidate generators that instantiate a constructor’s universally quantified variables and satisfy its hypotheses, all while maximizing a modular heuristic that approximates generator efficacy. Specimen derives these hypothesis-satisfying generators with a recursive call to the same search. For example, one might wish to derive a good generator for well-formed heaps satisfying this inductive relation:
inductive IsHeap : Nat → Tree Nat → Prop where
| leaf : IsHeap l₀ leaf
| node : l₀ ≤ x → IsHeap x l → IsHeap x r → IsHeap l₀ (node l x r)
Running the command derive_mutual_generator (fun l₀ => ∃ t, IsHeap l₀ t) derives a recursive generator of the same shape as genHeap, which relies on a derived generator for Nats x that satisfy l₀ ≤ x for some lower bound l₀.
Modifying Specimen to emit Basalt generators was straightforward because schedules, Specimen’s intermediate representation for the generators it derives, are already generic over the particular monad and combinators used for each type of derivation. Specimen’s search results in a large dependency graph of these schedules, with some of those schedules possibly being defined mutually recursively; when producing generators, Specimen traverses this dependency graph and builds concrete programs. Previously, Specimen’s compiler expressed generators using the monad and combinators from the Lean PBT library, Plausible [52]; switching to Basalt only required swapping Plausible’s monad and generator combinators with Basalt’s combinators defined over an arbitrary Generator instance. These derived programs make use of sizes and backtracking, features Basalt supports natively.
Once Specimen was underpinned with Basalt, we were able to improve the library. Specimen is based on a new algorithm for generator synthesis, presented by Elazar Mittelman et al. [32], and it does not support automatically derived proofs due to difficulties around mutually recursive derivations [70]. Basalt helps address these issues, and our version of Specimen now supports proof automation. By leveraging Basalt’s walk tactic and soundness and completeness infrastructure, alongside the proof strategy from QuickChick’s derived correctness proofs for non-mutually recursive generators [51, 64, 66], Specimen is able to derive correctness proofs automatically for a wide range of generators. Soundness proofs use the same concise Basalt proof script (Appendix § 16) for each mutually recursive group of generators. Completeness, which says that every term satisfying a relation has to be generable at a large enough size, is proven by applying walk to each of the generator’s branches corresponding to the constructors of the relation, examining whether the term could be generated by that constructor and which choices could arrive at it.
Our experience re-engineering Palamedes and Specimen to emit Basalt generators indicates that Basalt’s generator abstractions are sufficiently expressive to describe generators synthesized from existing tools, and that Basalt’s proof automation infrastructure can be effectively leveraged by existing synthesis tools.
Case Studies
Generators for binary search trees, min-heaps, and other data structures commonly presented in the PBT literature are small and well understood. To show that Basalt scales to realistic use-cases, which involve many non-trivial, interrelated data structures and validity predicates, we present two real-world case studies: Cedar, a domain-specific language used for writing authorization policies, and Strata, an intermediate verification language used for proofs about programs at a large technology company. We find that in both cases, Basalt was able to meet these projects’ needs, and is now (or soon will be) in production use.
5.3.1 Cedar Case Study. Cedar is an open-source authorization policy language used by cloud services such as Amazon Verified Permissions. The production implementation of Cedar is written in Rust, but, following an approach it calls Verification-Guided Development [28], the Cedar team maintains formally verified models of key Cedar components in Lean [13]. To provide assurance that the production implementation of Cedar behaves as expected, the two implementations of Cedar are differentially tested. Performing this differential testing requires a good generator for Cedar policies. The Cedar team handwrote a generator in Rust for Cedar policies. Writing this generator was expensive: according to the Cedar team, it took about six months to get a working draft of the generator at about 5,400 lines of code [32]. The generator has required nonstop maintenance since then to track changes to Cedar, with 152 commits in 39 of the 41 months [13] since its initial release. To see if this generator maintenance was avoidable, we attempted to derive a generator for valid Cedar policies automatically using Specimen, and prove it correct using its new Basalt backing.
Cedar’s validator, which, given a Cedar schema and policy, decides whether the pair is valid, was initially written as an executable function, so to use Specimen on it we first had to translate it to an equivalent inductive relational specification. Specimen’s derivation creates a generator that inverts the relation to produce well-formed schemas and valid policies by construction. To perform this translation, we used Claude Opus 5.0, iteratively refining the resulting relations with Specimen by deriving a generator and testing its output for divergence with the functional specification, before using the LLM to prove each relation’s correspondence with its function. The final specification describes Cedar’s validation with 159 inductive relations. Specimen uses these to derive generators for valid Cedar expressions, policies, and schemas. The dependency graph of generators required to define the top-level generators amounts to 291 definitions, about 54,500 lines of code (LoC), with 20 mutually recursive groups (Table 1).
| Definitions | Lines of derived code | Mutually recursive groups | ||||||||
| Gen. | Enum. | Check. | Gen. | Enum. | Check. | Groups | Largest | Mean | Mean (>1) | |
| Expressions | 95 | 138 | 11 | 24,425 | 25,352 | 1,060 | 181 | 21 | 1.35 | 4.32 |
| Policies | 21 | 0 | 2 | 1,736 | 0 | 58 | 23 | 1 | 1.00 | — |
| Schemas | 24 | 0 | 0 | 1,886 | 0 | 0 | 23 | 2 | 1.04 | 2.00 |
| Total | 140 | 138 | 13 | 28,047 | 25,352 | 1,118 | 227 | 21 | 1.28 | 4.20 |
Table 1. Overview of the Cedar generators derived using Specimen’s Basalt backend: no. of definitions, LoC, no. of mutually recursive groups in the dependency graph, and these groups’ sizes. These figures are broken down across generators (Gen.), enumerators (Enum.), and checkers (Check.). Enumerators and checkers support the generators derived by Specimen: enumerators are used to exhaustively search for values, e.g., when trying to validate an existential statement, and checkers help to filter invalid values from generators that are too permissive.
Re-engineering Specimen to emit Basalt generators only results in slightly higher overhead when deriving generators (57 seconds vs. 49 seconds). When the derived Basalt generators are executed using the SplitMix PRNG (§ 5.1), the generators run only 2% to 3% slower than when compiled directly to Plausible. Specimen is unable to take advantage of the speed provided by Basalt’s macros as of yet. There is ample room for optimization. This experience demonstrates that Basalt remains competitive with existing generator libraries and can be feasibly used as the foundational generator framework underpinning industrial PBT deployments.
Proofs about the generated inputs. Moving beyond the soundness and completeness proofs that Specimen now automates, we can explore interesting distributional properties. Cedar’s developers have repeatedly tuned their hand-written generators to control the size of generated inputs [13]. We identified three recurring patterns in these tuning changes, and for each one we prove a corresponding bound on our derived generators (Appendix I states these bounds precisely). Unlike soundness and completeness, which Specimen proves automatically, these bounds were proven using an LLM.
The first pattern concerns the number of request environments in a generated policy [9, 10, 18]. Cedar policies are validated against a schema, which defines which principal and resource types each action applies to. Each valid combination of principal type, action, and resource type is called a request environment, and validation checks a policy once per request environment. We prove that our derived schema generator respects a configurable cap on request environments and produces schemas with more than one request environment with at least 27% probability (provided that such schemas are reachable based on the generator’s arguments).
The second pattern involves entity hierarchies [16, 17, 19, 20]. Cedar policies refer to entities: an application’s principals, actions, and resources. Entities can be grouped into hierarchies; for example, a photo may belong to several albums, and an album may itself belong to another album [14]. Our derived schema generator supports a sparse mode. We prove that every hierarchy produced in this mode is a forest, and the expected number of ancestors of an entity type grows at most logarithmically in a configurable size parameter.
Finally, the Cedar team has repeatedly adjusted the depth of generated expressions [11, 12, 15]. A policy’s conditions are Boolean expressions that can be nested arbitrarily deeply. The depth of an expression cannot be bounded independently of its context: in a well-typed policy, an access `.x.y.z to an optional attribute must appear under a check has , so an expression that uses the check must copy . We prove that the depth of every generated expression is bounded linearly in the product of the generator’s two size parameters plus the maximum depth of any checked attribute access it could contain (detailed in Appendix I).
Strata Case Study
We also used Basalt to develop generators for Strata [73], an intermediate verification language implemented in Lean. Strata is under active use at a major technology company as part of a pipeline for proving properties of programs in a variety of source languages, including Python. Strata consists of a series of dialects that represent programs at different levels of abstraction, along with transformations between these dialects. We used PBT to gain confidence in the correctness of those parts of Strata’s implementation whose proofs are still in development (e.g., semantics-preservation properties of certain transformations), and of parts for which proofs are infeasible (e.g., round-trip properties of Strata’s IO-using pretty printer and parser). To do this, we developed bespoke generators of well-typed programs in Strata’s Core dialect using Basalt. In particular, we used Claude Opus 5.0 to automatically synthesize generators of different Strata Core components and to prove properties of these generators.7 We proved using Basalt that the generators are sound and complete (up to some side conditions), and that they satisfy specific distributional properties. The remainder of this subsection describes Strata in more detail, the generators and their properties, and the dozens of bugs we found using PBT.
Overview. Strata’s central dialect is dubbed Strata Core and takes inspiration from prior intermediate verification languages such as Why3 [4] and Boogie [3]. Strata Core is stratified into several layers: the expression language is a -calculus with Hindley–Milner-style prenex polymorphism, uninterpreted calls to ambient functions (built-in functions for arithmetic, string manipulation, etc.), and existential and universal quantification. The imperative fragment includes mutable variables (including non-deterministic assignment) and structured control flow (including loop invariants). Top-level declarations include abstract types, pure functions, stateful procedures with Dafny-style pre- and postconditions [53], user-defined algebraic data types, and type aliases. Our generators support generating programs in a large subset of Strata Core (features not supported include recursive functions, and generating pre- and postconditions with a known verification outcome).
Since Strata Core consists of multiple language layers, our LLM-synthesized Basalt generators likewise have a layered structure. Both the generators and their correctness proofs compose to produce results for full Strata Core programs. For the expression layer, we generate well-typed terms in a type-directed manner, with the generator closely following the structure of typing rules, as pioneered by Paka et al. [63]. For the imperative fragment of Strata Core, we generate commands and statements sequentially, extending the typing context when new definitions are introduced, so that later-generated portions can refer to earlier definitions. Soundness and completeness proofs are performed by induction on the generator’s size parameter and case analysis on the type of the generated term, following prior work [51, 64].
An initial version of these LLM-synthesized proofs was done prior to the development of Basalt’s proof automation tactics (§ 4.3). These proofs were later refactored to use Basalt’s walk tactic and auxiliary macros, allowing for a cumulative reduction of over 4,000 lines of code across all generator proofs. For example, in the soundness proof for the expression generator, these proof automation tactics were able to reduce the proof size by approximately 90%. In the original proofs, for each possible combination of size and base type, the generator needs to choose among a list of sub-generators according to some weights, requiring a proof that each choice of sub-generator produces a well-typed term. The original proof had to perform case analysis for each choice of sub-generator, then reason about the chosen sub-generator’s support. This line of repetitive reasoning is automated by the walk tactic, demonstrating how Basalt’s proof automation facilities effectively help LLMs synthesize more succinct proofs about generators. Table 2a displays the size of the typing specification, generators and associated correctness proofs for different fragments of Strata Core.
| Fragment | No. of constructors in Strata AST | No. of typing rules | No. of generator definitions | No. of generator theorems & lemmas |
| Primitives | – | – | 7 | 11 |
| Types & exprs. | 21 | 10 | 30 | 363 |
| Commands | 12 | 7 | 11 | 51 |
| Statements | 6 | 11 | 14 | 244 |
| Procedures | 12 | 3 | 3 | 66 |
| Functions | 1 | 1 | 21 | 79 |
| Data types | 2 | 21 | 15 | 137 |
| Declarations | 15 | 12 | 19 | 189 |
| General purpose | – | – | 3 | 45 |
| Total | 69 | 65 | 123 | 1,185 |
| Category | Properties | Bugs found |
| Parser | 1 | 2 |
| Pretty-printer | 6 | 10 |
| Type checking & inference | 17 | 3 |
| Transformations | 97 | 6 |
| Symbolic execution | 6 | 1 |
| SMT encoding | 8 | 4 |
| Derived functions | 3 | 2 |
| Specifications | – | 9 |
| PBT infrastructure | 19 | – |
| Total | 157 | 37 |
Table 2. Scale of the Basalt generators for Strata Core and their proofs (left), along with the properties tested and bugs found (right). (a) Size of each Strata Core fragment’s AST and its typing specification, and of our Basalt generators and their proofs. (Constructor counts are summed across all AST data types.) (b) Properties tested and bugs found in Strata via PBT (by category) using Basalt generators. (Some spec bugs were found via testing, while others were found when proving generators correct.)
Controlling size of generated programs. Beyond soundness and completeness, some properties we wanted to prove about our generators are lower bounds on the probability of generating nested statements (e.g., loops and conditionals), and upper bounds on the expected frequency of such statements (the exact bounds may change based on generator tuning).8 Proving these properties required changing our generators’ design. Our initial generators used the same size parameter to control the recursion depth and the maximum length of nested statement bodies. However, we realized that using this design, the best upper bound we could prove on the expected number of loops in generated programs grew factorially. We instead decided to decouple these parameters and limit the lengths of nested statements’ bodies. This change enabled us to prove bounds on the probability and expected frequency of AST nodes that are independent of size. In practice, we choose generated instances to have a small size to avoid potential blowups in generated programs. However, reasoning about the parameterized distribution with Basalt requires us to handle these cases, making the generators more robust.
Bugs found. With our generators, we regularly test over 150 properties, of which over 130 span the Strata codebase (the remaining properties are tests of the generators themselves and associated PBT infrastructure, e.g. QuickCheck-style shrinkers [22]). For example, we test that the parser and pretty-printer round-trip (parse(print(p)) = p for all randomly generated programs p), and that common sub-expression elimination does not result in unbound variables. Table 2b summarizes the Strata PBT effort, conveying the number of properties tested and bugs found. We now briefly discuss some notable bugs. When testing the round-trip property for the parser and pretty-printer, we found that the polymorphic function foo<s>(x: s) { . . . } (where s is a type variable) failed to parse, as <s was also Strata’s concrete syntax for the signed less-than operator over bit-vectors. This syntactic ambiguity meant that users were unable to define polymorphic functions with type variables beginning with s. Another bug we found involves Strata’s symbolic execution engine, which collects proof obligations expressed in the form of assertions in the source program. We found that in programs containing two consecutive non-deterministic branches, proof obligations in one of the conditionals would be silently dropped. This bug has since been fixed. Bugs like these show how Basalt generators helped uncover difficult-to-find bugs, thereby improving the reliability of Strata’s codebase.
Related Work
Representing Generators for PBT. The original QuickCheck paper [22] defines a PBT generator as a function from random seeds to values. Paraskevopoulou et al. [65] formalized the QuickCheck representation in Rocq, allowing users to prove correctness properties for generators. They defined the support of a generator — the set of values that it can potentially generate — as follows:
def QC.support (g : QC.Gen α) : Set α := {x | ∃ s, g s = x}
In other words, a generator’s support is the set of all values for which there exists a seed that produces the value. The QuickChick representation is useful for many things, but it cannot capture proofs about distributions. Our representation addresses this limitation, creating a stronger foundation for proofs about PBT moving forward.
Goldstein and Pierce [40] introduced free generators, in which generators are represented as a data structure that can be interpreted differently in various contexts. Using this mechanism, free generators can be interpreted as parsers for random sequences of choices. Our representation is inspired by free generators, but we make generators interpretable both as executable functions and as proof objects, allowing users to directly prove properties about their generators’ distributions.
Yu et al. [79] develop complexity-theoretic foundations for PBT generators, modeling generators as Turing machine transducers from random bits to outputs. They show that for certain classes of preconditions, efficient (polynomial time) constrained generators are impossible to achieve under standard complexity-theoretic assumptions, in which case one must settle for rejection sampling or restrict the generator’s sample space. Basalt allows users to implement both constrained and rejection-sampling-based generators and prove distributional properties about them. Crucially, users are not limited to either generator design: they can switch between the two, based on what is theoretically possible and what meets their practical needs.
Dynamic Alternatives for Constrained Generation. Research across both the programming languages and fuzzing communities sometimes eschews static generators for dynamic approaches that constrain the generation space based on feedback gathered during testing. These approaches often seem compelling, since writing generators like the ones we work with in Basalt can be time-consuming. But these dynamic approaches to generation have substantial downsides. First, there is mounting evidence that stronger static generators are better at finding bugs than weaker generators enhanced by dynamic feedback. Vikram and Padhye [78] compared constrained generators that produce well-formed inputs by construction against generators that employ coverage-guided fuzzing and found that coverage guidance only contributes marginally to the branch coverage of generated inputs. These results are corroborated by Lampropoulos et al. [50]: they developed FuzzChick, a variant of Rocq’s QuickChick framework which combines coverage guidance with automatically derived mutation functions for algebraic data types, interleaving coverage-guided mutation with random generation. When evaluating FuzzChick against QuickChick, they found that bespoke generators that produce well-formed inputs by construction (e.g., QuickChick generators synthesized directly from an inductive relation [51, 64]) remain more performant overall. Second, many dynamic approaches to generation do not guarantee distributional properties like the ones Basalt can prove. Coverage-guided fuzzing [36], including parametric generator-based fuzzing [29, 61, 62], makes no claims to approximate any particular distribution. Indeed, existing work has shown that some parametric fuzzing schemes are subject to the havoc paradox [54], in which changing the randomness for a generator has unpredictable impacts on the distribution of the generated values. Solver-based approaches [26, 69, 72] are similarly limited.
Nevertheless, it would be interesting to see how Basalt might interact with some limited kinds of dynamic feedback. In Basalt, since generators are implemented as type classes that can be interpreted differently for various use-cases, one could envisage developing a “coverage-guided fuzzing” instance of the Generator type class, which allows users to still prove correctness and distributional properties of their generators, but also reap the benefits of coverage guidance. Our hope is that one could prove some properties about the implementation once-and-for-all, e.g., that a particular fuzzing scheme avoids the havoc paradox.
SPMFs as a Semantic Domain. Basalt follows a long tradition in the probabilistic programming languages literature. Many languages over the years have used SPMFs or a similar structure to represent potentially diverging distributions, including seminal work by Kozen [47] and Jones and Plotkin [45] and recent work by Zilberstein et al. [82] and Hetzenberger et al. [43]. While Basalt is the first application of SPMFs to PBT that we know of, we are certainly not the first to apply them to distributional semantics. Our SPMF monad is also based on the Giry monad [34] for discrete distributions, which has been replicated before in various forms.
SPMFs also arise in other libraries for theorem proving. For example, CryptHOL [55] uses a shallowly embedded SPMF monad to capture and prove properties of cryptographic systems in Isabelle/HOL, and ALEA [2] has a similar scheme for proving properties of randomized algorithms in Rocq. In Lean, VCView [76] provides an SPMF-based semantics as a basis for a program logic. Basalt’s contribution is to apply these ideas to PBT.
Future Work and Conclusion
We have presented Basalt, a foundational library for PBT generators with a probabilistic semantics. In Basalt, the generator code that runs for testing (at least as fast as generators in established PBT frameworks) is the same code that supports proofs about soundness, completeness, distributions, termination, and cost. Because Basalt represents structurally non-terminating generators without fuel, natural generators like rejection samplers keep the distributions their authors intended. This foundation is strong enough to support automation: Palamedes and Specimen now produce Basalt generators, and Specimen derives correctness proofs for the generators it builds. In industrial case studies, Basalt generators for Cedar were proved sound, complete, and within the size limits its developers asked for, and Basalt generators helped find bugs in Strata. Looking ahead, we see two directions for building on this foundation.
Using Proofs as Tuning Feedback. Basalt lets programmers prove that a generator’s distribution falls short of a specification, but it does not help fix the generator. Existing work [75, 81] has begun to explore automated strategies for tuning PBT generators, and Basalt could complement those tools well. In particular, we think that counterexamples from failing proof automation could be useful feedback for automated tuning systems. We hope these approaches can close the loop on high-quality generator automation: a developer will be able to write down a generator in Basalt (or get one from Palamedes or Specimen), express some distributional goal, and automatically obtain a generator that provably meets that goal.
Building a Library of High-Quality Generators. Basalt also gives the PBT community a common language for sharing generators. We envision a library that supplies generators from a wide range of domains, alongside proofs that guarantee the quality of those generators. If a programmer needs a generator for SQL queries, PNG files, or simple Python programs, they may be able to take one off the shelf, read through its theorems, and run it against their codebase. For more bespoke tasks, programmers can use existing library generators as a starting point and build their own (which, hopefully, they will contribute back to the library when they are done).
AI Use
AI was used as a programming tool in this work; it was used while designing Basalt itself, while building our case study implementations (especially where mentioned above), and while setting up our experiments. All AI-generated code was extensively reviewed by humans. AI was also used in small ways for editing tasks in the paper itself (e.g., moving a section to the appendix or checking for typos and inconsistencies), but no text in the paper was written by AI.
References
Primitives for Randomness
The choose operator was not our only available option for a primitive randomness operator, but it has a number of qualities that make it work well for our use-cases. First, it is relatively efficient; primitives like flip and coin, which produce only one bit of randomness at a time, are theoretically nice but impractical to implement. Second, it is first-order. Some formalisms make combinators primitive, like oneOf, which makes a uniform random choice between a list of generators, or frequency, which makes a weighted choice between sub-generators, but both of these are higher-order and can be theoretically challenging as a built-in combinator.
Our choose also has some disadvantages. Using ranges (as opposed to UInt64) makes proofs much easier, but it means that implementations either need to sample integers of arbitrary size or else diverge slightly from the true semantics. We have never seen this cause real issues, but it is a small bit of friction between theory and practice. Also, any single choice of randomness primitive locks the implementation into that granularity of randomness. If another option becomes available, it is difficult to adapt the existing formalism to that approach. This cost is unavoidable when building a static formalism.
Proving Faithfulness
Connecting the IO interpretation to the SPMF interpretation requires a series of steps, each of which we validate in different ways.
The IO interpretation agrees with an “IOModel” interpretation that abstracts the C code in Lean.
Challenge: The IO interpretation calls C code on a global PRNG state, whereas the model is a pure Lean interpretation of SplitMix.
Validation: We run both implementations of SplitMix on 1,000 random seeds, and ensure that each produces exactly the same stream of 100 values. We also require that generators be run in a single-threaded environment.
The “IOModel” interpretation agrees with an “IdealizedModel” interpretation that is assumed to be a perfect PRNG.
Challenge: The idealized model assumes that draws from the PRNG are independent and uniformly random.
Validation: While this is strictly speaking false of any PRNG, SplitMix is known to be a good approximation of a real RNG. (Note: QuickChick also makes this assumption.)
The “IdealizedModel” interpretation agrees with the SPMF interpretation.
Challenge: This fact is easy to prove of each Generator operation, but the end-to-end argument requires parametricity.
Validation: We prove this fact on a per-generator basis, using a logical relation that connects the two interpretations. The walk tactic allows us to fully automate these proofs for users.
In the end, this chain of reasoning shows that the IO interpretation samples from a reasonable approximation of the SPMF distribution.
Size
Basalt’s Generator class and its standard interpretations do not include a size as a primitive, but they support running and reasoning about generators that rely on a size parameter. Basalt manages size with an additional type class that carries the standard QuickCheck size operations:
class Sized (g : Type → Type) where
sized : (Nat → g α) → g α
resize : Nat → g α → g α
And we can add sizes to any generator by just adding a Nat argument:
def WithSize (G : Type → Type v) (α : Type) : Type := Nat → G α
instance [Generator G] : Generator (WithSize G) where ...
instance [Monad G] : Sized (WithSize G) where ...
If a user wants to use size combinators in their generator, they can simply add a Sized constraint alongside the Generator constraint. For example, this is how Haskell’s QuickCheck defines the listOf combinator:
def listOf [Generator G] [Sized G] (gen : G α) : G (List α) :=
sized fun n => do
let k ← chooseNat 0 n
vectorOf k gen
When the user finally interprets a generator like this, the size falls out naturally as an argument. For proofs, the user can interpret this generator at type Nat → SPMF (List α) (instantiating G as WithSize SPMF), at which point they can decide whether to supply a concrete size or quantify over sizes. For execution, the user can interpret at Nat → IO (List α) (instantiating G as WithSize IO) and sample at whatever size they feel is appropriate.
Failure and Backtracking
Much like with Sized, we can also layer failure and backtracking into generators via auxiliary monads. If a generator should be allowed to fail, we can give it type [Generator G], OptionT G ; for example:
def tryGenFive [Generator G] (tries : Nat) : OptionT G Nat := do
match tries with
| 0 => failure
| tries' + 1 =>
let x ← genNat
if x == 5 then return x else tryGenFive tries'
This works out because OptionT G can be made an instance of Generator for any G that is itself a Generator. We build some lightweight proof infrastructure to help users deal with generators like this, but most of the standard Basalt infrastructure continues to work with partial generators.
A Fuel-Based Heap Generator
In QuickChick, the genHeap generator from Figure 2 would need to look something like the following. The code that manages fuel is highlighted in yellow.
def genHeapStruct [Generator G] (fuel : Nat) (lo : Nat) : OptionT G (Tree Nat) :=
match fuel with
| 0 => failure
| fuel' + 1 =>
oneOf [
fun () => return leaf,
fun () => do
let delta ← genNat
let x := lo + delta
let l ← genHeapStruct fuel' x
let r ← genHeapStruct fuel' x
return (node l x r)
]
Proofs of Generator Properties
This appendix gives the full proofs of the theorems stated in § 4. Many of them use walk, the custom Basalt tactic described in § 4.3.
Soundness and completeness of genHeap
theorem genHeap.sound_complete :
IsSoundAndComplete (genHeap lo) (isHeap lo) := by
refine .intro ?sound ?complete
case sound =>
rw [IsSoundFor.iff_obs]
walk fixpoint [genNat.sound_complete.sound.obs]
all_goals simp_all [isHeap]
case complete =>
refine IsCompleteFor.of_measure
(gen := fun lo => (genHeap lo : SPMF (Tree Nat)))
(fun _ t => t.size) (fun n ih lo t hn h => ?_) lo
rw [genHeap, SPMF.mem_support_iff_may]
walk [genNat.sound_complete.complete.obs, SPMF.le_may_of_measure ih]
cases t with
| leaf => simp
| node l x r =>
obtain ⟨d, rfl⟩ := Nat.exists_eq_add_of_le h.1
grind [= size, = isHeap]
Probability that genHeap returns the empty heap
theorem genHeap.prob_empty : ProbabilityOf (genHeap lo) leaf = 1 / 2 := by
rw [genHeap]
simp [SPMF.prob, SPMF.expect_oneOf, SPMF.expect_bind, SPMF.expect_map,
SPMF.expect_const, Function.comp_def]
Expected value of genNat
theorem genNat.expect_le : ExpectedValue genNat (fun n => n) ≤ 1 := by
rw [SPMF.expect_eq_obs]
walk fixpoint
norm_num
Almost-sure termination of genNat
theorem genNat.terminates : IsAlmostSurelyTerminating genNat := by
mass_fixpoint using SPMF.LfpIsOne.affine (m := 1 / 2) (by norm_num)
simp [ENNReal.div_eq_inv_mul, mul_add]
Cost bound for genHeap
theorem genHeap.cost_bounded :
IsCostBounded (genHeap lo) (fun t => 3 * t.size + t.sum + 1) := by
rw [IsCostBounded.iff_obs]
walk fixpoint [genNat.cost_bounded.obs]
all_goals simp only [Tree.size, Tree.sum]; omega
Expected cost bound for genNat
theorem genNat.expected_cost_bounded :
IsExpectedCostBounded genNat 2 := by
rw [IsExpectedCostBounded.iff_obs]
walk fixpoint
exact ENNReal.div_le_of_le_mul (by norm_num)
No expected cost bound for genHeap
theorem genHeap.not_expected_cost_bounded {B : ℝ≥0∞} (hB : B ≠ ⊤) (lo : Nat) :
¬ IsExpectedCostBounded (genHeap lo : SPMF.Cost (Tree Nat)) B := by
refine IsExpectedCostBounded.not_of_step_iInf
(g := fun lo => genHeap lo) one_ne_zero hB (fun lo => ?_) lo
have hm := fun lo' =>
(genHeap.cost_faithful (lo := lo')).one_le_mass genHeap.terminates
have hnat := genNat.cost_faithful.one_le_mass genNat.terminates
conv_rhs => rw [genHeap]
walk [fun lo' => SPMF.Cost.le_expect_add (hm lo')
(iInf_le (fun j => SPMF.Cost.expectObs.spec (genHeap j : SPMF.Cost (Tree Nat))
(fun _ n => (n : ℝ≥0∞))) lo'),
SPMF.Cost.le_expect_add (x := genNat) (h := fun _ n => (n : ℝ≥0∞))
hnat zero_le]
generalize ⨅ j, SPMF.Cost.expectObs.spec (genHeap j : SPMF.Cost (Tree Nat))
(fun _ n => (n : ℝ≥0∞)) = m
norm_num
rw [ENNReal.le_div_iff_mul_le (by norm_num) (by norm_num)]
exact le_of_eq (by ring)
An Example of the walk Tactic
Consider proving the following theorem:
theorem genPairFiveToTen.sound :
IsSound genPairFiveToTen (fun (x, y) => x ≤ 20 ∧ y ≤ 20)
After applying the walk tactic, we are left with two goals:
(x : ℕ), (hx : 5 ≤ x ∧ x ≤ 10) ⊢ x ≤ 20
(y : ℕ), (hy : 5 ≤ y ∧ y ≤ 10) ⊢ y ≤ 20
Each of which can be easily discharged by grind or similar.
Specimen’s Soundness Proofs
Soundness for a Specimen generator states that for each relation and input arguments ins a successful generation of output arguments outs from its derived generator genR must satisfy ins outs.
theorem genR.sound : ∀ fuel initSize size ins,
succObs.spec (genR fuel initSize size ins) (fun outs => R ins outs) :=
by intro fuel
induction fuel with
| zero => intros; rw [genR.eq_def]; walk
| succ f ih =>
intros; rw [genR.eq_def]
unfold_gen_instances [ih, facts]
walk [ih, facts]
all_goals ((try check_hyps [facts]); ctor_leaf)
Though not required by Basalt generators, Specimen generators rely on structural termination through a fuel argument, which the proof inducts on. At fuel zero, the generator fails, which is irrelevant to the specification succObs, which only focuses on values that the generator produces successfully. For non-zero fuel, the inductive hypothesis gives access to soundness proofs for successful recursive calls. Specimen generators construct data that satisfies their relations by mirroring each rule of R with a branch of the generator satisfying it, so that a successful generation of a branch amounts to an implicit proof that R holds. By way of Basalt’s walk tactic and check_hyps (a Specimen tactic), the proof script uses the inductive hypothesis, ih, to convert the recursive generator calls to proofs of inductive uses of R in the constructor, and facts, the soundness proofs about generator dependencies, to convert non-recursive calls into proofs of the other relations that constructor relies on. For mutually recursive groups, the ih is the conjunction of the soundness statements for all the group members. Finally, ctor_leaf (a Specimen tactic) applies R’s constructor to the proofs of the inductive relations required to satisfy it reflected from the generator calls.
I Theorems for the Cedar Generators
This section states the size and generator properties summarized in §5.3.1. Specimen generators are parameterized by at least two sizes: indicates the maximum recursion depth of the generator and indicates the maximum size of any data generated as an arbitrary member of a type (like a random string or integer). These properties are defined with respect to these two sizes, and for the schema generator, a budget intended to cap the number of request environments its schemas have.
(1) Support. Regardless of whether a schema is generated with a sparse, flat, or dense hierarchy graph, the number of request environments the generated schema has is capped by the configurable budget .
theorem schema_combinations (b n l : Nat) (m : HierMode) (Γ : TypeEnv)
(h : (m, Γ) ∈ supp (schemaGen b n l)) :
Γ.schema.environments.length ≤ b
(2) Distribution. With a budget of at least one, the schema generator always succeeds at generating a schema.
theorem schema_never_fails (b n l : Nat) (hb : 1 ≤ b) :
Pr[schemaGen b n l succeeds] = 1
(3) Distribution. With a budget of at least 2 and , the probability of a schema with at least 2 entity types having at least 2 request environments is at least .
theorem schema_varied (b n l : Nat) (hb : 2 ≤ b) (hl : 1 ≤ l) :
Pr[(_, Γ) ← schemaGen b n l : 2 ≤ Γ.schema.environments.length
| 2 ≤ Γ.ets.toList.length]
≥ 5 / 18
(4) Support. The schema generator can choose to generate entity hierarchies of different densities. When it chooses to generate in the sparse mode, it generates a forest.
theorem sparse_hierarchy_forest (b n l : Nat) (Γ : TypeEnv)
(h : (.sparse, Γ) ∈ supp (schemaGen b n l)) :
∀ t ∈ hierarchy Γ, t.2 = [] ∨ ∃ p ps, t.2 = p :: ps ∧ (p, ps) ∈
hierarchy Γ
(5) Distribution. When the schema generator succeeds in the sparse mode and the schema contains at least one standard entity type (hierarchy Γ ≠ []), the average number of ancestors of entity types in the hierarchy has expectation upper bounded by ln(ℓ + 1).
theorem sparse_mean_ancestors (b n l : Nat) :
E[(m, Γ) ← schemaGen b n l : .ofReal (meanAncestors Γ)
| m = .sparse ∧ hierarchy Γ ≠ []]
≤ .ofReal (Real.log (l + 1))
(6) Support. For any set of capabilities, c, which encode the enclosing checks whose expressions may be copied into a generated expression and whose depth is not limited by or , any type environment Γ, type τ, the well-typed expression generator at those capabilities, environment, and desired type only produces expressions e whose depth is bounded by the sum of the depth of the enclosing checks and a term linear in the product of and .
theorem expr_depth (decl syn : Bool) (c : Capabilities) (Γ : TypeEnv)
(τ : CedarType) (n l : Nat) (e : Expr) (c' : Capabilities)
(h : (e, c') ∈ supp (exprGen decl syn c Γ τ n l)) :
exprDepth e ≤ n * (l + 2) + capsDepth c
Micro-Benchmark Generators
The following generators are used for the micro-benchmarks in § 5.1. There are four workloads:
nat generates an unconstrained natural number. It is genNat from Figure 2.
bst generates a valid binary search tree with keys from 0 to 999.
heap generates a valid min-heap. It is genHeap from Figure 2, with weights 5:4 instead of 1:1.
sorted generates a sorted list of natural numbers, with weights 1:9.
We changed the weights for heap and sorted to make the distributions more interesting. The expected sizes are 1 for nat, about 137.3 nodes for bst, 4 nodes for heap, and 9 elements for sorted. Every implementation generates the same four distributions.
Basalt
The two tree types are ordinary inductive types:
inductive BST.Tree (α : Type) where
| leaf : BST.Tree α
| node : BST.Tree α → α → BST.Tree α → BST.Tree α
inductive Heap.Tree where
| leaf : Heap.Tree
| node : Heap.Tree → Nat → Heap.Tree → Heap.Tree
The generators use the oneOf! and frequency! macros, which expand to a chain of ifs on literal running totals.
def genNat [Generator G] : G Nat := do
oneOf! [
fun _ => pure 0,
fun _ => do
let n ← genNat
pure (n + 1)
]
partial_fixpoint
def genWeightedBST [Generator G] (lo hi : Int) : G (BST.Tree Int) := do
if h : lo > hi then
return .leaf
else
frequency! [
(1, fun _ => pure .leaf),
(5, fun _ => do
let x ← chooseInt lo hi (by omega)
let l ← genWeightedBST lo (x - 1)
let r ← genWeightedBST (x + 1) hi
return .node l x r)
] (by simp)
partial_fixpoint
def genHeap [Generator G] (lo : Nat) : G Heap.Tree :=
frequency! [
(5, fun _ => pure .leaf),
(4, fun _ => do
let delta ← genNat
let x := lo + delta
let l ← genHeap x
let r ← genHeap x
return .node l x r)
] (by simp)
partial_fixpoint
def genSortedGt [Generator G] (m : Nat) : G (List Nat) := do
frequency! [
(1, fun _ => pure []),
(9, fun _ => do
let delta ← genNat
let x := m + delta
let xs ← genSortedGt x
return x :: xs)
] (by simp)
partial_fixpoint
The “no macro” implementation uses the same code with oneOf! and frequency! replaced by the functions oneOf and frequency. The “IO.rand” implementation uses the standard IO PRNG instead of SplitMix. The “no opt.” implementation does both.
Plausible
These generators are written the way a Plausible user would write them: as partial defs at Plausible’s Gen monad, using Plausible’s Gen.oneOf and Gen.frequency. They reuse the tree types from §J.1.
partial def genNat : Gen Nat :=
Gen.oneOf #[
pure 0,
do
let n ← genNat
pure (n + 1)
] (by simp)
partial def genWeightedBST (lo hi : Int) : Gen (BST.Tree Int) :=
if h : lo > hi then
pure .leaf
else
Gen.frequency (pure .leaf) [
(1, pure .leaf),
(5, do
let ⟨x, _⟩ ← Gen.choose Int lo hi (by omega)
let l ← genWeightedBST lo (x - 1)
let r ← genWeightedBST (x + 1) hi
return .node l x r)
]
partial def genHeap (lo : Nat) : Gen Heap.Tree :=
Gen.frequency (pure .leaf) [
(5, pure .leaf),
(4, do
let delta ← genNat
let x := lo + delta
let l ← genHeap x
let r ← genHeap x
return .node l x r)
]
partial def genSortedGt (m : Nat) : Gen (List Nat) :=
Gen.frequency (pure []) [
(1, pure []),
(9, do
let delta ← genNat
let x := m + delta
let xs ← genSortedGt x
return x :: xs)
]
QuickCheck
We use QuickCheck 2.19, compiled with GHC 9.10.3 and -O2. The tree and list types have strict fields, so every value is fully built when it is generated.
data Tree = Leaf | Node !Tree !Int !Tree
data SList = Nil | Cons !Int !SList
genNat :: Gen Int
genNat = oneof [pure 0, do n <- genNat; pure $! n + 1]
genBST :: Int -> Int -> Gen Tree
genBST lo hi
| lo > hi = pure Leaf
| otherwise =
frequency
[ (1, pure Leaf)
, (5, do
x <- chooseInt (lo, hi)
l <- genBST lo (x - 1)
r <- genBST (x + 1) hi
pure (Node l x r))
]
genHeap :: Int -> Gen Tree
genHeap lo =
frequency
[ (5, pure Leaf)
, (4, do
delta <- genNat
let !x = lo + delta
l <- genHeap x
r <- genHeap x
pure (Node l x r))
]
genSorted :: Int -> Gen SList
genSorted m =
frequency
[ (1, pure Nil)
, (9, do
delta <- genNat
let !x = m + delta
xs <- genSorted x
pure (Cons x xs))
]
Base_quickcheck
We use Base_quickcheck v0.17.1, compiled with OCaml 5.4.1, flambda, and -O3. Base_quickcheck’s own weighted_union draws a float, so we wrote frequency by hand on int_uniform_inclusive.
let frequency (gs : (int * 'a Generator.t) list) : 'a Generator.t =
let total = List.fold_left (fun acc (w, _) -> acc + w) 0 gs in
let rec pick n = function
| [] -> assert false
| (k, g) :: gs -> if n < k then g else pick (n - k) gs
in
let%bind n = Generator.int_uniform_inclusive 0 (total - 1) in
pick n gs
type bst = Leaf | Node of bst * int * bst
let nat : int Generator.t =
Generator.fixed_point (fun nat ->
Generator.union
[ return 0
; (let%bind n = nat in return (n + 1)) ])
let rec gen_bst lo hi : bst Generator.t =
if lo > hi
then return Leaf
else
frequency
[ 1, return Leaf
; ( 5
, let%bind x = Generator.int_uniform_inclusive lo hi in
let%bind l = gen_bst lo (x - 1) in
let%bind r = gen_bst (x + 1) hi in
return (Node (l, x, r)) ) ]
let rec gen_heap lo : bst Generator.t =
frequency
[ 5, return Leaf
; ( 4
, let%bind delta = nat in
let x = lo + delta in
let%bind l = gen_heap x in
let%bind r = gen_heap x in
return (Node (l, x, r)) ) ]
let rec gen_sorted m : int list Generator.t =
frequency
[ 1, return []
; ( 9
, let%bind delta = nat in
let x = m + delta in
let%bind xs = gen_sorted x in
return (x :: xs) ) ]References
- [1]Thomas Arts, John Hughes, Ulf Norell, and Hans Svensson. 2015. Testing AUTOSAR software with QuickCheck. In 2015 IEEE Eighth International Conference on Software Testing, Verification and Validation Workshops (ICSTW). 1–4. doi:10.1109/ICSTW.2015.7107466DOI
- [2]Philippe Audebaud and Christine Paulin-Mohring. 2009. Proofs of Randomized Algorithms in Coq. 74, 8 (2009), 568–589. doi:10.1016/j.scico.2007.09.002DOI
- [3]Mike Barten, Bor-Yuh Evan Chang, Robert DeLine, Bart Jacobs, and K. Rustan M. Leino. 2006. Boogie: A Modular Reusable Verifier for Object-Oriented Programs. In Formal Methods for Components and Objects (FMCO). doi:10.1007/11804192_17
- [4]François Bobot, Jean-Christophe Fillâtre, Claude Marché, and Andrei Paskevich. 2011. Why?: Shepherd Your Herd of Provers. In Workshop on Intermediate Verification Languages (Boogie). https://inria.hal.science/hal-00790310
- [5]Joachim Breitner. 2025. Extrinsic Termination Proofs for Well-Founded Recursion in Lean. Blog post. https://www.joachim-breitner.de/blog/816-Extrinsic_termination_proofs_for_well-founded_recursion_in_Lean
- [6]Joachim Breitner. 2025. F91 in Lean. Blog post. https://www.joachim-breitner.de/blog/817-F91_in_Lean
- [7]Benjamin Canou and Alexis Darrasse. 2009. Fast and Sound Random Generation for Automated Testing and Benchmarking in Objective Caml. In Workshop on PML. doi:10.1145/1596627.1596637DOI
- [8]Jacques Carette, Oleg Kiselyov, and Chung-Chieh Shan. 2009. Finally Tagless, Partially Evaluated: Tagless Staged Interpreters for Simpler Typed Languages. Journal of Functional Programming 19, 5 (2009), 509–543. doi:10.1017/S0956796809007205DOI
- [9]Cedar Team. 2025. Limit number of request environments in generated schema (Issue #610). GitHub issue cedar-policy/cedar-spec#610. https://github.com/cedar-policy/cedar-spec/issues/610 Accessed November 2026.
- [10]Cedar Team. 2025. Limit the number of iterations in target sycм←x←drt (PR #719). GitHub pull request cedar-policy/cedar-spec#719. https://github.com/cedar-policy/cedar-spec/pull/719 Accessed November 2026.
- [11]Cedar Team. 2025. Cedar FuzzTargetInput struct for abac targets (PR #764). GitHub pull request cedar-policy/cedar-spec#764. https://github.com/cedar-policy/cedar-spec/pull/764 Accessed November 2026.
- [12]Cedar Team. 2026. Add Cedar type generator respecting max_width and max_depth (PR #923). GitHub pull request cedar-policy/cedar-spec#923. https://github.com/cedar-policy/cedar-spec/pull/923 Accessed November 2026.
- [13]Cedar Team. 2026. cedar-spec: Formal Specification and Verification of Cedar. https://github.com/cedar-policy/cedar-spec Accessed November 2026.
- [14]Cedar Team. 2026. Entities. Cedar Policy Language Reference Guide. https://docs.cedarpolicy.com/policies/syntax-entity.html Accessed November 2026.
- [15]Cedar Team. 2026. Fix recursion limit being hit in policy-cedar-to-json fuzzing target (Issue #942). GitHub issue cedar-policy/cedar-spec#942. https://github.com/cedar-policy/cedar-spec/issues/942 Accessed November 2026.
- [16]Cedar Team. 2026. Generate sparser entity hierarchies robust to 0x00-heavy fuzzer input (PR #1060). GitHub pull request cedar-policy/cedar-spec#1060. https://github.com/cedar-policy/cedar-spec/pull/1060 Accessed November 2026.
- [17]Cedar Team. 2026. Reduce size of generated entity type hierarchy (PR #1044). GitHub pull request cedar-policy/cedar-spec#1044. https://github.com/cedar-policy/cedar-spec/pull/1044 Accessed November 2026.
- [18]Cedar Team. 2026. Reduce the maximum request envs in term-drt and cex-drt targets (PR #853). GitHub pull request cedar-policy/cedar-spec#853. https://github.com/cedar-policy/cedar-spec/pull/853 Accessed November 2026.
- [19]Cedar Team. 2026. Tune entity/type edge budgets for hierarchy density (PR #1062). GitHub pull request cedar-policy/cedar-spec/pull/1062. https://github.com/cedar-policy/cedar-spec/pull/1062 Accessed November 2026.
- [20]Cedar Team. 2026. Tweak generators to build less dense entity hierarchies (PR #1051). GitHub pull request cedar-policy/cedar-spec#1051. https://github.com/cedar-policy/cedar-spec/pull/1051 Accessed November 2026.
- [21]Koen Claessen, Jonas Duregard, and Michal H. Palka. 2015. Generating Constrained Random Data with Uniform Distribution. Journal of Functional Programming 25 (2015), e8. doi:10.1017/S0956796815000143DOI
- [22]Koen Claessen and John Hughes. 2000. QuickCheck: A Lightweight Tool for Random Testing of Haskell Programs. In International Conference on Functional Programming (ICFP). doi:10.1145/351240.351266DOI
- [23]Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. 2022. Heapsort. In Introduction to Algorithms (4th ed.). MIT Press, Cambridge, MA, Chapter 6.
- [24]Joseph W. Cutler, Craig Diselkoen, Aaron Eline, Shaobo He, Kyle Headley, Michael Hicks, Kesha Hietala, Elheferios Ioannidis, John Kastner, Anwar Mamat, Darin McAdams, Matt McCutchen, Neha Rungta, Emina Torlak, and Andrew M. Wells. 2024. Cedar: A New Language for Expressive, Fast, Safe, and Analyzable Authorization. Proceedings of the ACM on Programming Languages 8, OOPSLA1 (2024), 670–697. doi:10.1145/3649835DOI
- [25]Leonardo de Moura and Sebastian Ullrich. 2021. The Lean 4 Theorem Prover and Programming Language. In Conference on Automated Deduction (CADE). doi:10.1007/978-3-030-79876-5_37DOI
- [26]Kyle Dewey, Lawton Nichols, and Ben Hardekopf. 2015. Automated Data Structure Generation: Refuting Common Wisdom. In International Conference on Software Engineering (ICSE). doi:10.1109/ICSE.2015.26DOI
- [27]Edsger W. Dijkstra. 1975. Guarded Commands, Nondeterminacy and Formal Derivation of Programs. Commun. ACM 18, 8 (1975), 453–457. doi:10.1145/360993.360975
- [28]Craig Diselkoen, Aaron Eline, Shaobo He, Kyle Headley, Michael Hicks, Kesha Hietala, John Kastner, Anwar Mamat, Matt McCutchen, Neha Rungta, Bhakti Shah, Emina Torlak, and Andrew Wells. 2024. How We Built Cedar: A Verification-Guided Approach. In Companion Proceedings of the Foundations of Software Engineering (FSE Companion). doi:10.1145/3663529.3663854
- [29]Stephen Dolan. 2017. Crowbar: Property fuzzing for OCaml. https://github.com/stedolan/crowbar
- [30]Peter Dybjer, Qiao Haiyan, and Makoto Takeyama. 2003. Combining Testing and Proving in Dependent Type Theory. In Theorem Proving in Higher Order Logics, David Basin and Burkhart Wolff (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg, 188–203. doi:10.1007/10930755_12
- [31]Peter Dybjer, Qiao Haiyan, and Makoto Takeyama. 2004. Random generators for dependent types. In Proceedings of the First International Conference on Theoretical Aspects of Computing (Guiyang, China) (ICTAC ’04). Springer-Verlag, Berlin, Heidelberg, 341–355. doi:10.1007/978-3-540-31862-0_25
- [32]Segev Elazar Mittelman, Harrison Goldstein, and Leonidas Lampropoulos. 2026. Testing Theorems, Fully Automatically. Proceedings of the ACM on Programming Languages 10, OOPSLA2 (2026), 177–204. doi:10.1145/3839453
- [33]Martin Erwig and Steve Kollmansberger. 2005. Functional Pearl: Probabilistic functional programming in Haskell. Journal of Functional Programming 16 (2005). Issue 1. doi:10.1017/S0956796805005721DOI
- [34]Michele Giry. 1982. A Categorical Approach to Probability Theory. In Categorical aspects of topology and analysis. Springer, 68–85. https://link.springer.com/content/pdf/10.1007/BFb0092872.pdf
- [35]Vladimir Gladshtein, George Pirlea, Qiyuan Zhao, Vitaly Kurin, and Ilya Sergey. 2026. Foundational Multi-Modal Program Verifiers. Proceedings of the ACM on Programming Languages 10, POPL (2026), 2233–2264. doi:10.1145/3776719DOI
- [36]Patrice Godefroid, Adam Kiezun, and Michael Y. Levin. 2008. Grammar-based whitebox fuzzing. In Proceedings of the 29th ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI ’08). Association for Computing Machinery, New York, NY, USA, 206–215. doi:10.1145/1375581.1375607
- [37]Harrison Goldstein. 2022. Parsing Randomness: Free Generators Development. doi:10.5281/zenodo.7086231DOI
- [38]Harrison Goldstein, Joseph W. Cutler, Daniel Dickstein, Benjamin C. Pierce, and Andrew Head. 2024. Property-Based Testing in Practice. In International Conference on Software Engineering (ICSE). doi:10.1145/3597503.3639581DOI
- [39]Harrison Goldstein, Hila Peleg, Cassia Torczon, Daniel Sajnati, Leonidas Lampropoulos, and Benjamin C. Pierce. 2026. The Search for Constrained Random Generators. Proceedings of the ACM on Programming Languages 10, PLDI (2026), 2060–2084. doi:10.1145/3808329DOI
- [40]Harrison Goldstein and Benjamin C. Pierce. 2022. Parsing Randomness. Proceedings of the ACM on Programming Languages 6, OOPSLA2 (2022), 89–113. doi:10.1145/3563291DOI
- [41]Harrison Goldstein, Jeffrey Tao, Zac Hatfield-Dodds, Benjamin C. Pierce, and Andrew Head. 2024. Tyche: Making Sense of Property-Based Testing Effectiveness. In User Interface Software and Technology (UIST). doi:10.1145/3654777.3676407
- [42]Theodore Edward Harris et al. 1963. The Theory of Branching Processes. Vol. 6. Springer, Berlin.
- [43]Matthias Hetzenberger, Georg Moser, and Florian Zuleger. 2026. A Cost-Aware Probability Monad for Liquid Haskell. In Haskell Symposium. doi:10.1145/3830439.3831276DOI
- [44]Nouraldin Jaber, Dongyun Jin, Bernhard Kragl, Enrico Magnago, Gustavo Petri, Thorsten Tarrach, and Serdar Tasiran. 2026. High Fidelity Models for Large Scale Stateful Services (Operational Systems). In Operating Systems Design and Implementation (OSDI). https://www.usenix.org/conference/osdi26/presentation/jaber
- [45]C. Jones and G.D. Plotkin. 1989. A Probabilistic Powerdomain of Evaluations. In [1989] Proceedings. Fourth Annual Symposium on Logic in Computer Science (Pacific Grove, CA, USA, 1989). IEEE Comput. Soc. Press, 186–195. doi:10.1109/LICS.1989.39173
- [46]Dexter Kozen. 1985. A Probabilistic PDL. (1985). https://www.cs.cornell.edu/~kozen/Papers/PPDL.pdf
- [47]Dexter Kozen. 1979. Semantics of Probabilistic Programs. In Foundations of Computer Science (FOCS). doi:10.1109/SFCS.1979.38DOI
- [48]Patrick LaFontaine, Zhe Zhou, Ashish Mishra, Suresh Jagannathan, and Benjamin Delaware. 2025. We’ve Got You Covered: Type-Guided Repair of Incomplete Input Generators. Proceedings of the ACM on Programming Languages 9, OOPSLA2 (2025), 3008–3036. doi:10.1145/3763158DOI
- [49]Leonidas Lampropoulos. 2018. Random Testing for Language Design. Ph.D. Dissertation. University of Pennsylvania. https://leonidas.github.io/pdf/Leo-PhD-Thesis.pdf
- [50]Leonidas Lampropoulos, Michael Hicks, and Benjamin C. Pierce. 2019. Coverage guided, property based testing. PACMPL 3, OOPSLA (2019), 181:1–181:29. doi:10.1145/3360607DOI
- [51]Leonidas Lampropoulos, Zoe Paraskevopoulou, and Benjamin C. Pierce. 2017. Generating Good Generators for Inductive Relations. Proceedings of the ACM on Programming Languages 2, POPL (2017), 1–30. doi:10.1145/3158133DOI
- [52]Lean Community. 2025. Plausible. https://github.com/leanprover-community/plausible
- [53]K. Rustan M. Leino. 2010. Dafny: An Automatic Program Verifier for Functional Correctness. In Logic for Programming, Artificial Intelligence, and Reasoning (LPAR). doi:10.1007/978-3-642-17511-4_20DOI
- [54]Ao Li, Madonna Huang, Vasudev Vikram, Caroline Lemieux, and Rohan Padhye. 2025. The havoc paradox in generator-based fuzzing. ACM Transactions on Software Engineering and Methodology 35, 1 (2025), 1–26.DOI
- [55]Andreas Lochbihler. 2016. Probabilistic Functions and Cryptographic Oracles in Higher Order Logic. In Programming Languages and Systems (Berlin, Heidelberg, 2016), Peter Thiemann (Ed.). Springer, 503–531. doi:10.1007/978-3-662-49498-1_20DOI
- [56]David R. MacIver, Zac Hatfield-Dodds, et al. 2019. Hypothesis: A New Approach to Property-Based Testing. Journal of Open Source Software 4, 43 (2019), 1891. doi:10.21105/joss.01891DOI
- [57]Annabelle McIver and Carroll Morgan. 2004. Abstraction, Refinement and Proof for Probabilistic Systems. Springer-Verlag, New York, NY. doi:10.1007/b138392
- [58]Agustín Matías Alejandro Russo, and John Hughes. 2018. Branching Processes for QuickCheck Generators. In Haskell Symposium. doi:10.1145/3242744.3242747DOI
- [59]Carroll Morgan, Annabelle McIver, and Karen Seidel. 1996. Probabilistic Predicate Transformers. ACM Transactions on Programming Languages and Systems 18, 3 (1996), 325–353. doi:10.1145/229542.229547DOI
- [60]Peter W. O’Hearn. 2019. Incorrectness Logic. Proceedings of the ACM on Programming Languages 4, POPL (2019), 1–32. doi:10.1145/3371078DOI
- [61]Rohan Padhye, Caroline Lemieux, and Koushik Sen. 2019. JQF: coverage-guided property-based testing in Java. In Proceedings of the 28th ACM SIGSOFT International Symposium on Software Testing and Analysis, ISSTA 2019, Beijing, China, July 15-19, 2019, Dongmei Zhang and Anders Møller (Eds.). ACM, 398–401. doi:10.1145/3293882.3339002DOI
- [62]Rohan Padhye, Caroline Lemieux, Koushik Sen, Mike Papadakis, and Yves Le Traon. 2019. Combining Fuzzing with zest. In Proceedings of the 28th ACM SIGSOFT International Symposium on Software Testing and Analysis (ISSTA 2019). Association for Computing Machinery, New York, NY, USA, 329–340. doi:10.1145/3293882.3330576DOI
- [63]Michał H. Palka, Koen Claessen, Alejandra Russo, and John Hughes. 2011. Testing an Optimising Compiler by Generating Random Lambda Terms. In Automation of Software Test (AST). doi:10.1145/1982595.1982615DOI
- [64]Zoe Paraskevopoulou, Aaron Eline, and Leonidas Lampropoulos. 2022. Computing Correctly with Inductive Relations. In Programming Language Design and Implementation (PLDI). doi:10.1145/3519939.3523707DOI
- [65]Zoe Paraskevopoulou, Cătălin Hrițcu, Maxime Dénès, Leonidas Lampropoulos, and Benjamin C. Pierce. 2015. Foundational Property-Based Testing. In Interactive Theorem Proving (ITP). doi:10.1007/978-3-319-221-1_22DOI
- [66]QuickChick Team. 2026. QuickCheck: Randomized Property-Based Testing Plugin for Coq. https://github.com/QuickChick/QuickChick. Accessed November 2026.
- [67]Norman Ramsey and Avi Pfeffer. 2002. Stochastic lambda calculus and monads of probability distributions. In Principles of Programming Languages (POPL). doi:10.1145/503272.503288DOI
- [68]Cynthia Richey, Joseph W. Cutler, Harrison Goldstein, and Benjamin C. Pierce. 2026. Fail Faster: Staging and Fast Randomness for High-Performance PBT. Proceedings of the ACM on Programming Languages 10, OOPSLA1 (2026), 1737–1762. doi:10.1145/3798263DOI
- [69]Eric L. Seidel, Niki Vazou, and Ranjit Jhala. 2015. Type Targeted Testing. In European Symposium on Programming (ESOP). doi:10.1007/978-3-662-46669-8_33DOI
- [70]Specimen Team. 2026. Specimen: Automatically Derived Generators, Enumerators, and Checkers for Inductive Relations in Lean. https://github.com/strata-org/specimen Accessed October 2026.
- [71]Guy L. Steele, Doug Lea, and Christine H. Flood. 2014. Fast Splittable Pseudorandom Number Generators. In Object-Oriented Programming, Systems, Languages, and Applications (OOPSLA). doi:10.1145/2660193.2660195DOI
- [72]Dominic Steinhöfel and Andreas Zeller. 2022. Input Invariants. In European Software Engineering Conference and Symposium on the Foundations of Software Engineering (ESEC/FSE). doi:10.1145/3540250.3549139
- [73]Strata Team. 2026. The Strata Core Language Syntax. https://strata-org.github.io/Strata/langdef/html-single/ Accessed October 2026.
- [74]The Lean Developers. 2026. The Lean Language Reference. https://lean-lang.org/doc/reference/4.35.0-rc2/ Version 4.35.0-rc2.
- [75]Ryan Tjoa, Poorva Garg, Harrison Goldstein, Todd Millstein, Benjamin C. Pierce, and Guy Van den Broeck. 2025. Tuning Random Generators: Property-Based Testing as Probabilistic Programming. Proceedings of the ACM on Programming Languages 9, OOPSLA2 (2025), 894–921. doi:10.1145/3763082
- [76]Devon Tuma, Quang Dao, James Waters, Alexander Hicks, and Nicholas Hopper. 2026. VCVio: Verified Cryptography in Lean via Oracle Effects and Handlers. Cryptology ePrint Archive, Paper 2026/899. https://eprint.iacr.org/2026/899
- [77]Cas van der Rest and Wouter Swierstra. 2022. A completely unique account of enumeration. Proceedings of the ACM on Programming Languages 6, ICFP (Aug. 2022), 105:411–105:437. doi:10.1145/3547636DOI
- [78]Vasudev Vikram and Rohan Padhye. 2026. Predicate-Guided Synthesis of Input Generators via Gentoo. In International Conference on Automated Software Engineering (ASE) (ASE ’26). doi:10.1145/3832783.3837441DOI
- [79]Pingshi Yu, Chengsong Tan, Nicolas Wu, and Alastair F. Donaldson. 2026. Complexity Theory of Randomised Testing. arXiv:2607.11811. doi:10.48550/arXiv.2607.11811DOI
- [80]Zhe Zhou, Ashish Mishra, Benjamin Delaware, and Suresh Jagannathan. 2023. Covering All the Bases: Type-Based Verification of Test Input Generators. Proceedings of the ACM on Programming Languages 7, PLDI (2023), 1244–1267. doi:10.1145/3591271
- [81]Francille Zhuang. 2026. Ariadne: Automatically Tuning Generator Weights Using Dynamic Sampling. Student Research Competition poster, ACM SIGPLAN Symposium on Principles of Programming Languages (POPL ’26).
- [82]Noam Zilberstein, Dexter Kozen, Alexandra Silva, and Joseph Tassartoti. 2025. A Demonic Outcome Logic for Randomized Nondeterminism. Proceedings of the ACM on Programming Languages 9, POPL (2025), 539–568. doi:10.1145/3704855DOI



