Complexity Theory of Randomised Testing

Unknown

Conceptio › Archive › arXiv CS

arXiv CSopen access

Complexity Theory of Randomised Testing

Unknown · 2026 · arxiv_cs

arXiv CS · Papers · License: Open Access · 2026

Open Source ↗Direct PDF ↓

softwarearchitecture softwareengineering testing

software engineering, software architecture, testing

Complexity Theory of Randomised Testing

arXiv:2607.11811v1 [cs.PL] 13 Jul 2026

PINGSHI YU, Imperial College London, United Kingdom CHENGSONG TAN, Kaihong, China NICOLAS WU, Imperial College London, United Kingdom ALASTAIR DONALDSON, Imperial College London, United Kingdom Randomised testing is a widely-used approach to software validation, yet despite years of practical development its theoretical foundations remain thin. In particular, the fundamental question of what it means for a set of inputs to be generable has gone unanswered in both the literature and folklore. We present, for the first time, complexity-theoretic foundations for random generators in software testing. We model generators as Turing machine transducers that consume random bits and produce string-encoded outputs, and show that the theoretically generable languages coincide exactly with the recursively enumerable languages. This has direct implications for testing at the boundaries of decidability, such as in the field of compiler testing. Turning to efficient generation, we show that the polynomial-time generable languages lie within NP, that certain important NP-complete languages admit efficient generators, and that—under standard cryptographic assumptions—there are languages in P for which no efficient generator exists: the complexity of efficienct generation and of efficient decision are not the same. We then show that space-bounded complexity is the natural framework for generators producing correlated samples, capturing methodologies such as coverageguided fuzzing and symbolic execution. Beyond classification, we characterise efficient generability: a language has a polynomial-time generator iff it admits a certificate scheme over a verifier—so witness planting, the folklore technique behind generators to test SAT solvers, is in a sense the only route to efficient generation. Our theory also yields design principles for property-based testing libraries: we prove no library can compositionally derive efficient generators from logical predicates involving conjunction or negation, under standard assumptions. However, restricted classes like NL (equivalently, linear Datalog predicates) would admit such a compilation.

Introduction

At first sight, software testing, concerned with the observed behaviour of particular programs on particular inputs, is far removed from complexity theory, which distinguishes what can be computed in principle from what can be computed by an efficient algorithm. Yet, in property-based testing (PBT) [10, 33], where a system under test (SUT) is executed on many automatically generated inputs, a critical component to the success of a testing campaign is the generator, a randomised algorithm. Due to the intricacies of realistic generators, much work has gone into their implementation [31, 50], library tooling [10, 20, 33, 52], and on automatic derivation of generators from predicates [16, 17, 28]. But despite their importance, little is known about the theoretical limits of generator expressivity: what can be generated at all, and what can be generated efficiently? We give the first complexity-theoretic formalisation of generators in randomised testing, establishing a number of results about what can and cannot be generated, and why. Our formulation is applicable to the majority of generators found in testing practice: generators are modelled as Turing machine transducers that consume bitstrings and must eventually produce string-encoded outputs. Once generators are cast within this framework, each generator associates with a formal language—the set of outputs it can produce. This allows rigorous investigation of the limits of generation in general, as well as under a variety of time and space constraints. In establishing our novel framework, we build upon previous theoretical work on language generation that predates PBT (and which in our view deserves more attention) [44, 45]. Authors’ Contact Information: Pingshi Yu, [email protected], Imperial College London, London, United Kingdom; Chengsong Tan, [email protected], Kaihong, Shenzhen, China; Nicolas Wu, [email protected], Imperial College London, London, United Kingdom; Alastair Donaldson, [email protected], Imperial College London, London, United Kingdom.

0:2

Pingshi Yu, Chengsong Tan, Nicolas Wu, and Alastair Donaldson

// [a=19, b=4] void foo(int a, int b) { unsigned i = 0; while(i != a) { i += b; } }

(a) Nonterminating C program.

(declare-const p Bool) (declare-const r Bool) (declare-const q Bool) ; from unsat generator (assert (=> (and q r) (and (not q) r))) ; from sat generator ; by e.g. [p=F, q=T, r=F] (assert (=> (and p q) r))

// [a=21219] // halts in 100 steps void bar(int a) { int i; for (i = 0; i < 100; i++) { if (i == a) break; } }

(b) (Un)satisfiable formulas.

Fig. 1. Possible test cases produced by example generators.

To illustrate the kinds of questions our theoretical framework allows us to ask and answer, we give three examples in the context of programming languages research. Example: testing a termination checker. Suppose we are presented with a termination checking tool for C-programs, which is claimed to be conservative: the tool should emit a “may not terminate” diagnostic for at least those (program, input) pairs where the program does not terminate on the input. To apply PBT to this tool we thus need a generator of elements from the set NonTerm = {(𝑝, 𝑖) : 𝑝 a C program, 𝑖 an input, 𝑝 does not terminate on 𝑖}. If testing finds a (𝑝, 𝑖) pair for which the checker does not emit a diagnostic, it has found a bug in the checker. Figure 1a illustrates one such pair that should be producible by the generator. While of course we can create a generator that produces many such pairs of examples (possibly including Figure 1a), our theory tells us that it is impossible to create such a generator without sacrificing some part of the NonTerm space: we show that the recursively enumerable (RE) languages are precisely the generable ones, and since NonTerm is not in RE (assuming an unbounded memory semantics for C), it cannot be generable. Example: testing a SAT solver. To apply PBT to a SAT solver we would like two generators, generating satisfiable (unsatisfiable) formulas: if the solver claims that any are unsatisfiable (satisfiable) this is a bug. Figure 1b uses SMT-LIB syntax to sketch simple formulas that such generators might be expected to produce. Our theory confirms that generators covering the full space of satisfiable or unsatisfiable problems can exist, and that a generator of satisfiable problems that runs in polynomial time can be constructed (even though deciding satisfiability is NP-complete). However, we show that (unless P = NP) a fully general polynomial-time generator of unsatisfiable problems cannot exist. Furthermore, if we move from SAT to QBF instances by allowing quantifiers, a fully general polynomial-time generator cannot exist even for the satisfiable case. Example: time-bounded differential compiler testing. As a final motivating example, a campaign for randomised differential compiler testing typically requires (program, input) pairs where the program does terminate on the input. To make such a campaign efficient we might further want the generator to provide a time bound for each generated program, avoiding the need for arbitrarily-selected timeout values. We would thus like to generate (𝑝, 𝑖, 𝑘) triples comprising a program 𝑝 that is guaranteed to terminate on input 𝑖 within 𝑘 time steps1 (see Figure 1c). Although this input space is generable, we show that unless standard complexity-theoretic assumptions turn out to be false, a time-efficient generator cannot cover the set of all such programs: no generator of independent samples exist that uses 𝑞(𝑛) time to generate programs of size 𝑛, for some polynomial 𝑞. Not only that, polynomial generation remains out of reach even if the generator had access to an efficient SAT solver. The results established in Section 6 show that polynomial space 𝑞(𝑛) would 1 Assuming that each basic operation of the program takes one time step.

Complexity Theory of Randomised Testing

EPG

generator classes

0:3

classical classes

classical and generator classes coincide

PSPACEG = PSPACE

GEN = RE

P ⊈ PG, EPG (*)

Fig. 2. Complexity relationships between the new generators classes and known classes. Purple dotted boundaries denote generator classes that do not coincide with classical ones; purple solid boundaries denote generator classes that do coincide with classical ones; black dashed boundaries denote classical complexity classes that do not coincide with generator classes. The generator classes are LG: logspace generable, PG: polynomial-time generable, EPG: expected polynomial-time generable, PSPACEG: polynomial-space generable, and GEN: all generable languages. P contains NL, intersects PG and EPG, and is contained in NP. (*) Noncontainment of P is contingent on standard cryptographic assumptions.

also not be sufficient to produce all such programs of size 𝑛—limiting the use of feedback-driven generation techniques such as concolic execution [7, 8] and coverage-guided fuzzing [5] for this particular set. A practical solution would have to make some engineering trade-offs. Beyond classification, our framework yields a characterisation of efficient generability: we show that a language has a polynomial-time generator if and only if it has a verifier admitting a certificate scheme—a way to sample certificates and reconstruct random instances around them. This shows that some form of witness planting (including one based on a trivial verifier)—the folklore technique behind generators for SAT and graph reachability—is used by all time-efficient generators. Separately, a long-standing goal in the PBT literature is to automatically derive efficient generators from predicates [9, 16, 28]. We prove a negative result in this context: under standard assumptions, no library can compositionally map predicates from a logic containing conjunction or negation to polynomial-time generators—any homomorphic translation must give up either expressivity or efficiency. On the other hand, we show that restricted classes like NL (equivalently, predicates in linear Datalog) can in principle be compiled compositionally to polynomial-time generators. By studying the power of generators under various resource constraints, we establish a wide range of results about testing that fall out naturally. Some confirm intuitions from testing folklore; others are novel insights that were previously inaccessible without such a formal model. Contributions. In summary, our main contributions are: • We provide the first complexity-theoretic foundations of generators for randomised testing (Section 2), and derive expressivity bounds applicable to all generators (Section 3). • We propose a notion of time/space constraints for generators, and derive theoretical limits of efficient generation (Section 4, Section 5, Section 6). • We establish general principles for constructing time-efficient generators, and limitations on the design of composable testing libraries (Section 7). Throughout the paper, we introduce several generator-specific complexity classes: LG (log-space generable), PG (polynomial-time generable), EPG (expected polynomial-time generable), PSPACEG (polynomial-space generable) and GEN (everything that can be generated). Figure 2 serves as a roadmap to the complexity landscape established in our work.

0:4

Pingshi Yu, Chengsong Tan, Nicolas Wu, and Alastair Donaldson

Modelling Generators

A generator in randomised testing produces structured inputs for an SUT [35], e.g. inputs that the SUT is supposed to accept, or deliberately malformed inputs designed to stress the SUT. These structured inputs can be viewed as strings in a language. For generality, and to allow the application of complexity theory, we formulate generators as Turing machines, and their outputs as string encodings of data. We model randomness as an explicit input bitstring supplied to a deterministic Turing machine, where random selections are made during computation by reading from this bitstring. This is in line with how randomness is implemented in common randomised testing libraries such as Hypothesis [33].2 In practice, generation is driven by a pseudorandom number generator (PRNG), which we idealise as an inexhaustible supply of independent, unbiased random bits: a generator consumes some finite prefix of an infinite stream and produces an output. There are two caveats with the informal description, which we make formal below. First, we permit a generator that produces nothing for every stream, characterising generators of the empty set, and is useful for our theoretical model. Second, a generator being productive “given an infinite stream” is too strong if interpreted as “given every infinite stream”. We show in Section 2.3 that reasonable generators can still fail to produce a value in extreme, albeit probability 0 events—so we require producivity only almost surely. Although it is natural to define generators to take infinite streams as input, infinite streams are not a natural input space for Turing machines. To reconcile this, we proceed in three steps: (1) We define bitstring transducers, which operate on finite bitstrings, together with a halting condition. A halting transducer either accepts, producing an output, or rejects, where a rejection only occurs when the transducer runs out of its finite input (Section 2.1). (2) We lift a halting transducer to infinite streams. Because rejection only occurs after input exhaustion, acceptance is monotone under extension of the input, thus every accepting run belongs to an equivalence class represented by a unique minimal accepting prefix. This lets us define what a transducer does on an infinite stream, and lets us measure the set of accepted bitstreams (Section 2.2). (3) We define the notion of eventual productivity as almost-sure acceptance of infinite streams under the measure of infinite sequences of fair coin-flips, and obtain the definition of a generator (Section 2.3).3 Preliminaries. Unless stated otherwise, all tapes of a Turing machine (TM) are assumed to be infinite (to the right), initially empty, with the head pointed at some fixed, designated initial cell. The alphabet on all tapes of Turing machines is finite, and includes the “ ” symbol to represent blank spaces. The blank symbol will never be written. When we make the statement “tape with alphabet Γ”, we implicitly mean it has alphabet Γ ⊎ { }, and all empty cells on the tape are populated by symbols. We say a tape is read-once-only if the head never moves left and the machine never writes to the tape. Similarly, a tape is write-once-only if the head never moves left, and after any write operation the tape head is immediately moved to the right. For a Turing machine 𝑀 with a single input tape, we say “𝑀 ran on 𝑥”, or “𝑀 ran with input 𝑥”, or “𝑀 (𝑥)”, to mean the computation performed by 𝑀 in the initial state, with the input tape populated using 𝑥 starting from the initial cell. This also extends to machines with multiple input tapes. For example, 2 It is also possible to model randomness using nondeterministic Turing machines, which would result in an equivalent model. We choose deterministic Turing machines with an explicit random input to stay in line with practical implementations, and because it makes later definitions more convenient. The results for the deterministic case translate directly to the nondeterministic case. 3 In Appendix A.1 we discuss an alternative natural notion of eventual productivity based only on Turing machines.

Complexity Theory of Randomised Testing

0:5

on a machine 𝑀 with two input tapes, 𝑀 (𝑥, 𝑦) means the computation performed by 𝑀 in the initial state, with the first input tape populated using 𝑥 and the second using 𝑦. 2.1

Transducers on finite bitstrings

Definition 2.1 (Bitstring Transducer). A bitstring transducer 𝑇 is a Turing machine with three tapes: a read-once-only input tape with alphabet {0, 1}, a working tape with alphabet Σ, and a write-once-only output tape with alphabet Γ. For a bitstring 𝑏 ∈ {0, 1}∗ , if 𝑇 (𝑏) accepts, the contents of the output tape (disregarding empty cells) 𝑥 ∈ Γ ∗ are said to be produced by 𝑇 , denoted 𝑇 (𝑏) = 𝑥. If there is no ambiguity, we may say transducer for short. Definition 2.2 (Random Selection). During an execution, we say that the transducer 𝑇 makes a random selection whenever a transition moves the input tape head right—that is, it reads a bit from the input bitstring. Multiple random bits can be combined together in a procedure to make more refined random selections (e.g. conditional dependence, or selections among more than two possibilities). Procedures are computations (potentially with side effects) that consume randomness in the sense of Definition 2.2, and generators are special cases of procedures that write values to the output tape. Procedures are used to modularise algorithmic descriptions and help with clarity of exposition. Example 2.1. A transducer 𝑁 can select any 𝑛 ∈ N at random via the following iterative procedure. 𝑁 reads the input in pairs of bits. In each round it reads a continuation bit; if it is 1, 𝑁 reads a further data bit, appends it to a buffer on the working tape, and begins a new round; if it is 0, 𝑁 halts and outputs the buffer, interpreted as a binary numeral. Writing the input stream as 𝑏 0𝑏 1𝑏 2 . . ., the Í −1 transducer computes 𝑘𝑖=0 𝑏 2𝑖+1 2𝑖 where 𝑘 = min{𝑖 : 𝑏 2𝑖 = 0}, whenever this 𝑘 exists. Note that the only way 𝑁 rejects is when it runs out of input bits, e.g. on 1 or 101 (the continuation bit promises another bit that is not supplied), or on 10 (no continuation bit is supplied). The accepting runs of Example 2.1 consume 2𝑘 + 1 bits for some 𝑘 ≥ 0, and rejections occur due to the stream ending prematurely. This is the behaviour we now generalise to our halting condition. Definition 2.3 (Halting Transducer). A bitstring transducer 𝑇 is halting if (1) for every input 𝑏 ∈ {0, 1}∗ , 𝑇 (𝑏) halts; and (2) 𝑇 rejects iff the input head attempts to read a blank cell (a cell containing ). The second clause prevents premature rejections and is a necessary precursor for the formal definition of “eventual productivity” below. From Definition 2.3, we can immediately observe the following, useful for the upcoming generalisation to infinite streams. Observation 2.1 (Monotonicity). Let 𝑇 be halting and suppose 𝑇 (𝑏) accepts. Then the run 𝑇 (𝑏) reads no cell beyond the |𝑏 |-th, since by Definition 2.3 reading a blank would force rejection. Hence for every 𝑏 ′ having 𝑏 as a prefix, the run of 𝑇 on 𝑏 ′ is identical, so 𝑇 (𝑏 ′ ) accepts and 𝑇 (𝑏 ′ ) = 𝑇 (𝑏). 2.2

From finite bitstrings to infinite streams

By Observation 2.1, the accepting behaviour of a halting transducer 𝑇 is completely determined by the shortest bitstrings on which it accepts. Definition 2.4. For a halting transducer 𝑇 , the minimal accepted bitstrings 𝐴𝑇 are 𝐴𝑇 = { 𝑏 ∈ {0, 1}∗ : 𝑇 (𝑏) accepts ∧ ∀𝑏 ′ . 𝑏 ′ a strict prefix of 𝑏 =⇒ 𝑇 (𝑏 ′ ) rejects }. Again by Observation 2.1, no element of 𝐴𝑇 is a prefix of another, i.e. 𝐴𝑇 is prefix-free, and 𝑇 accepts a finite bitstring 𝑏 exactly when some element of 𝐴𝑇 is a prefix of 𝑏. Note that 𝐴𝑇 is defined for conceptual convenience, and is not intended to be computed directly.

0:6

Pingshi Yu, Chengsong Tan, Nicolas Wu, and Alastair Donaldson

We can now assign a natural semantics of 𝑇 on an infinite bitstream bs ∈ {0, 1}𝜔 : its behaviour is identical to 𝑇 (𝑏), where 𝑏 ∈ 𝐴𝑇 is a prefix of 𝑏𝑠, if 𝑏 exists. Definition 2.5. For a halting transducer 𝑇 and an infinite bitstream bs, define 𝑇 (bs) as: (1) 𝑇 (𝑏), if 𝑏 ∈ 𝐴𝑇 and 𝑏 is a prefix of bs; (2) divergent, if no 𝑏 ∈ 𝐴𝑇 is a prefix of bs. This is well-defined: as 𝐴𝑇 is prefix-free, at most one 𝑏 ∈ 𝐴𝑇 is a prefix of bs. To speak of the probability that 𝑇 produces an output, we use the standard measure of infinite sequences of fair coin-flips, which models the PRNG that drives generators in practice. Definition 2.6 (Distribution of Random Bitstreams). Let I denote the distribution of bitstreams {0, 1}𝜔 , where for a random variable 𝑋 distributed according to I (written 𝑋 ∼ I), all bits of 𝑋 are independently and identically distributed (i.i.d.) following a fair Bernoulli distribution Ber(0.5). For a set of bitstreams 𝐵 ⊆ {0, 1}𝜔 , denote the probability of 𝐵 under I by 𝜇 (𝐵). Definition 2.7. For a bitstring 𝑏 ∈ {0, 1}∗ , define the cylinder 𝑆𝑏 as: 𝑆𝑏 = {𝑏 ++ bs : bs ∈ {0, 1}𝜔 }. Definition 2.8. The accepted infinite bitstreams of a halting transducer 𝑇 are Ø 𝐴𝑇𝜔 = 𝑆𝑏 . 𝑏 ∈𝐴𝑇

Since 𝐴𝑇 is prefix-free, the cylinders 𝑆𝑏 for 𝑏 ∈ 𝐴𝑇 are pairwise disjoint. 𝐴𝑇 is also countable, thus 𝐴𝑇𝜔 is a countable disjoint union of cylinders, and is measurable with ∑︁ 𝜇 (𝐴𝑇𝜔 ) = 2− |𝑏 | . 𝑏 ∈𝐴𝑇

This quantity is the probability that 𝑇 , when driven by an idealised PRNG, produces an output. 2.3

Eventual productivity

We are now ready to formalise the “eventual productivity” requirement of a generator. The strongest interpretation of eventual productivity is that 𝑇 (bs) is defined for every bs ∈ {0, 1}𝜔 , equivalently 𝐴𝑇𝜔 = {0, 1}𝜔 . However, this is too strong in practice. Consider the natural number transducer 𝑁 of Example 2.1. It diverges on exactly the streams in: 𝑋 = {𝑏 0𝑏 1 . . . : ∀𝑖 ∈ N. 𝑖 even ⇒ 𝑏𝑖 = 1}, that is, streams in which every continuation bit is 1, so that 𝑁 never stops asking for another data bit. Ruling out transducers like 𝑁 would make it impossible to sample from an infinite set—any transducer with infinitely many possible outputs must have infinitely many accepting prefixes, and so there must exist streams on which the transducer is never productive. This would severely limit the applicability of our model. Observe however, that the set 𝑋 has trivial measure, as 𝜇 (𝑋 ) = lim𝑖→∞ 2−𝑖 = 0. We therefore formalise eventual productivity as almost-sure acceptance. 𝜔 ) = 1 or 𝜇 (𝐴𝜔 ) = 0. Definition 2.9 (Generators). A halting transducer 𝐺 is a generator if 𝜇 (𝐴𝐺 𝐺 𝜔 ) = 0 iff 𝐴 = ∅ iff 𝐺 rejects every finite bitstring. Observation 2.2. 𝜇 (𝐴𝐺 𝐺 𝜔) = Í − |𝑏 | = 0 iff 𝐴 is empty. By Proof. Each 𝑆𝑏 has 𝜇 (𝑆𝑏 ) = 2− |𝑏 | > 0, so 𝜇 (𝐴𝐺 𝐺 𝑏 ∈𝐴𝐺 2 Observation 2.1, 𝐴𝐺 = ∅ iff 𝐺 accepts no finite bitstring. □

Complexity Theory of Randomised Testing

0:7

𝜔 ) = 1 or 0) are for the two behaviours permitted of generators: the first The two cases (𝜇 (𝐴𝐺 characterises almost-sure productivity; the second describes the case where all inputs are rejected (corresponding to a generator for the empty set). It is undecidable to check whether a given transducer is a generator, but this is not an issue since we show generator conditions on a caseby-case basis throughout this work.4 For added intuition, it may help to consider the transducers that are not generators. These are the transducers that fail to halt on some finite bitstring, or that diverge on a non-negligible — but not co-negligible — set of streams. To illustrate the definition, we verify that it matches our intuitions on Example 2.1, and that rejection sampling yields true generators.

Proposition 2.1. The transducer 𝑁 of natural numbers described in Example 2.1 is a generator. Proof. 𝑁 is clearly halting: on any finite bitstring it either meets a 0 continuation bit and accepts, or exhausts its input and rejects. The set of bitstreams not accepted by 𝑁 is 𝑋 as above, so 𝐴𝜔𝑁 = {0, 1}𝜔 \ 𝑋 and 𝜇 (𝐴𝜔𝑁 ) = 1 − 𝜇 (𝑋 ). Since 𝜇 (𝑋 ) = 0, 𝜇 (𝐴𝜔𝑁 ) = 1 and 𝑁 is a generator. □ Definition 2.10 (Generator by Rejection Sampling). Let 𝑓 be a total computable predicate on {0, 1}∗ . The generator 𝐺 𝑓 based on rejection sampling on 𝑓 is defined as follows. (1) Sample an 𝑛 (e.g. using Example 2.1), then sample a string 𝑤 of length 𝑛. (2) Compute 𝑓 (𝑤). If 𝑓 (𝑤) returns true, output 𝑤. Otherwise restart from step 1. Proposition 2.2. If 𝑓 is a computable predicate on {0, 1}∗ such that 𝑓 holds for at least one 𝑤 ∈ {0, 1}∗ , then 𝐺 𝑓 is a generator. Proof. See Appendix A.2. 3

□

A Framework for Generability

In testing, randomness is an essential tool to enable systematic exploration of the input space. The goal of randomised testing can be viewed as the validation of a certain property that must hold on the program when executed on the random inputs. The commonly practised paradigm of property-based testing (PBT) validates properties of the form ∀𝑥 .Pre(𝑥) =⇒ Post (𝑥), which suits the vast majority of use cases. For instance, fuzzing can be seen as validating the property: “for all inputs 𝑥, the program should not crash”. Differential testing can be seen as validating: “for all valid inputs 𝑥, the two implementations 𝑇 ,𝑇 ′ must have 𝑇 (𝑥) = 𝑇 ′ (𝑥)”. The key to the successful application of randomised testing is an effective generator, whose job is to generate inputs that satisfy the preconditions of the property, which then enables the property to be checked on the program. We now show a few example scenarios below of programs and their properties that may be tested, and will be referring back to them throughout this section. Example 3.1 (Binary Search Trees). Program 𝑃 takes as input a binary search tree 𝑇 and an index 𝑖, and outputs the 𝑖th smallest element within the tree. 𝑃 should satisfy the following property, where bst (𝑇 ) is a predicate checking that 𝑇 is a binary search tree, and 𝑖, 𝑗 are integers: ∀𝑇 , 𝑖, 𝑗 .bst (𝑇 ) ∧ 0 ≤ 𝑖 ≤ 𝑗 < |𝑇 | =⇒ 𝑃 (𝑇 , 𝑖) ≤ 𝑃 (𝑇 , 𝑗) Example 3.2 (Counting SAT Assignments). Program 𝑃 takes as input a CNF boolean formula 𝜓 and outputs the number of satisfying assignments of 𝜓 . 𝑃 should satisfy the following property, where sat is the predicate for the satisfiability of the formula, and 𝜓 [𝑥/𝐴] is the substitution of 𝐴 for 𝑥 in 𝜓 : ∀𝜓 .sat (𝜓 ) =⇒ 𝑃 (𝜓 ) > 0 ∧ 𝑃 (𝜓 ) = 𝑃 (𝜓 [𝑥 0 /𝑇 ]) + 𝑃 (𝜓 [𝑥 0 /𝐹 ]) 4 In a similar vein, the undecidability of the Halting problem does not prevent people from developing useful algorithms.

0:8

Pingshi Yu, Chengsong Tan, Nicolas Wu, and Alastair Donaldson

Example 3.3 (Tensor Decomposition). Program 𝑃 takes a tensor 𝑇 over field 𝐹 , and outputs a decomposition of 𝑇 as a product of rank-1 tensors. 𝑃 should satisfy the following: Ì ∀𝑇 , 𝑟 . rank(𝑇 ) = 𝑟 =⇒ length(𝑃 (𝑇 )) = 𝑟 ∧ (∀𝑖 < 𝑟 . rank(𝑃 (𝑇 )𝑖 ) = 1) ∧ 𝑃 (𝑇 )𝑖 = 𝑇 . 𝑖<𝑟

Example 3.4 (C Compiler). Program 𝑃 is a compiler for the C language, taking an optimisation flag (0 or 1) as the first argument and a C program as the second argument. 𝑃 should satisfy the following property, where wd (𝑐) is a predicate checking 𝑐 is a C program with well-defined semantics (assume it doesn’t take inputs), and 𝑃 (𝑜, 𝑐) () denotes executing the executable produced by compiling 𝑐 using 𝑃 on optimisation 𝑜: ∀𝑐.wd (𝑐) =⇒ 𝑃 (0, 𝑐) () = 𝑃 (1, 𝑐) () In each case, for a property Prop = ∀𝑥 .Pre(𝑥) =⇒ Post (𝑥), the ideal generator should implement a distribution on the elements of the set Precond = {𝑥 : Pre(𝑥)}. 3.1

The Design Space of Generability

We first address some nuances in the design space of the formal language associated with a generator. This is an important step, since languages are the central object of study in any complexity theory. Allow generators to sample only a subset of Precond? Sampling from a strict subset of Precond would mean there exist elements 𝑥 ∈ Precond that can never be generated. Such a generator can still find bugs, but never ones triggered only by inputs outside its range. Thus the generator of a subset of Precond would not be appropriate to fully test Prop. As a pragmatic choice, it is common in practice to create generators that sample from only a subset of inputs that satisfies a property’s precondition. For instance, when the precondition is seemingly too complex5 to write a generator for, such as the property described in Example 3.4, generators typically focus on specific subsets of the input space heuristically understood to contain potential bug triggers [12, 31]. Although existing literature refers to these as “generators” of Cprograms for validating compilers, the property they are testing for is more accurately understood as a different from the one in Example 3.4, with a more restrictive precondition: ∀𝑐.producible(𝑐) =⇒ 𝑃 (0, 𝑐) () = 𝑃 (1, 𝑐) () where producible is to denote the predicate corresponding to the targeted subset of inputs the generator produces. For example, restricted C-programs amenable to implemented analyses [50], or C-programs containing constrained forms of loops [32]. Allow generators to sample a superset of Precond? Generators sampling from a superset of Precond would be able to trigger all possible property violations, but risk false positives from inputs outside of Precond. Rejection sampling is required to filter the inputs, selecting only ones that satisfy the precondition. Depending on requirements, this filter can be applied either as a final step of generation, or after a bug-triggering input has been found to check for false-positivity. While filtering works well when deciding the precondition is easy (Example 3.1), the precondition itself can be hard to decide, and is not in general related to the complexity of the algorithm under test. For example, checking the precondition is NP-hard in Example 3.2 and Example 3.3, and undecidable in Example 3.4 (deciding if a C program is well-defined is undecidable [11]). Example 3.3 is worth highlighting here: computing the rank of 𝑇 is NP-hard, but if rank(𝑇 ) is known, the decomposition is computable in time polynomial in the size of the tensor. The runtime of the test campaign can 5 Note this is only an empirical understanding, which is thus far not formalised. When is a set really too complex to generate?

We will look to give theoretical answers to this question in the coming sections.

Complexity Theory of Randomised Testing

0:9

thus be dominated by the filtering stage. These filters also need to be provided separately, and when the filter is complex, it can be an additional source of complexity and bugs in the testing system. Moreover, test case throughput is an important factor for the effectiveness of a testing campaign [4, 34]. Spending significant time deciding the validity of inputs can often mean fewer or missed bugs. If a precondition-satisfying input is produced rarely by a generator, for instance, using a generator of random ASTs (or even random strings) for Example 3.4, then it can be the case that no tests are ever run, due to the low probability of finding a satisfying input! Indeed, if the generator produces precondition-satisfying inputs with probability 𝑝, then one expects 1/𝑝 attempts to find a usable input—and 1/𝑝 can easily scale exponentially with the size of the generated test case. In the Example 3.4 case, a random AST would have vanishingly low probability of satisfying the language specification [23], and a random string even more so. What distributions should generators implement? A generator implements a particular distribution over the set of inputs, and in practice impacts the effectiveness of a testing campaign. Randomised testing employs a wide range of distributions, which can also be adjusted as testing progresses [18, 36]. However, there is no canonical distribution around which to build a complexity theory. The uniform distribution (on elements of a given size) is commonly studied theoretically, but fail to capture the diversity of distributions used in practice. Indeed, in the design of generators, the distribution implemented is often an orthogonal concern to samplability itself. Therefore, as a first step towards a complexity-theoretic model of generators, we remain agnostic to distributions, and aim to gain fundamental understanding of which sets can be generated at all. This serves as a prerequisite to the harder question of generability under prescribed distributions, and also ensures generality of our results. The “no-go” results we derive, a type of result common in complexity theory, apply to generators implementing any computable distribution, rather than being contingent on distributional assumptions. The only requirement we impose is distributional support [37]: the support of the implemented distribution must equal the whole set. One natural concern is that the weak assumption of only distributional support may be overly permissive, since it allows distributions that assign negligible weight to parts of the set. However, distributional support is a stronger guarantee than it may first appear—once an input is producible, however improbably, practical techniques can often amplify the probability of producing desirable outcomes. For example, the bitstring input to a generator can be viewed as an optimisation parameter, and this insight was used in previous works [17, 33, 36] to tune generators, producing outputs that would have otherwise been infeasible due to their low probability weights. 3.2

Unconstrained Generability

In light of the insights from the above discussion, we give the following definition for the language associated with a generator. Definition 3.1 (Generated Language). For a generator 𝐺, the language generated by 𝐺 is: L (𝐺) = {𝑥 | ∃ 𝑏 ∈ {0, 1}+ . 𝐺 (𝑏) = 𝑥 } The following is the most general class of languages that is generable. The only requirement is that there exists an algorithm (generator) to generate the elements. Definition 3.2 (Generable Languages). For an alphabet Σ, we define the set of generable languages, GEN, as follows: GEN = {L (𝐺) : 𝐺 is a generator} A language 𝐿 is generable if 𝐿 ∈ GEN.

0:10

Pingshi Yu, Chengsong Tan, Nicolas Wu, and Alastair Donaldson

For a language 𝐿, we have defined our generators to associate with 𝐿 a surjective computable function {0, 1}∗ → 𝐿 that constructs instances of 𝐿 from randomness. On the other hand, one of the most commonly studied objects in complexity theory is Turing recognisers, which implement a (potentially partial) predicate for some language 𝐿. Turing recognisers associate a language 𝐿 with a function of type Σ∗ → B, which accepts 𝑥 ∈ Σ∗ iff 𝑥 ∈ 𝐿. The standard class of RE, or recursively enumerable languages, is the set of all languages whose elements can be recognised by a Turing machine (predicate). Definition 3.3 (Recursively Enumerable Languages). For a given alphabet Σ, the recursively enumerable languages are: RE = {𝐿 ⊆ Σ∗ : ∃ a Turing machine 𝑀. ∀𝑥 ∈ Σ∗,

𝑥 ∈ 𝐿 ⇔ 𝑀 halts and accepts 𝑥 }

In Definition 3.3, 𝑀 refers to a standard Turing machine that accepts/rejects an input, rather than the transducer style within Definition 2.1. 𝑀 can be seen as a membership predicate for some set 𝑆, where 𝑀 (𝑥) accepts if and only if 𝑥 ∈ 𝑆 (but importantly may loop instead of rejecting if 𝑥 ∉ 𝑆). The RE sets/languages with a membership predicate algorithm that always halts are called decidable, and the complement of the decidable languages in P (Σ∗ ) is called undecidable. The well-definedness of a C-program (wd in Example 3.4) is an undecidable problem, making it a “hard” member of RE. As noted earlier, the natural approach of rejection sampling cannot be used within any generator of well-defined C-programs (programs 𝑥 satisfying wd (𝑥)), since generators must terminate on any finite input, and the test for a string 𝑥 satisfying wd (𝑥) may never terminate. The inability to use rejection sampling of course extends to all RE languages. This raises the natural question: is it actually possible to write a generator for well-defined C-programs, or indeed any undecidable set? The question is not limited to a single generation algorithm that one may write: any conceivable procedure, or combinations of procedures whose set of outputs equals the set of well-defined C-programs would be a generator. We now show that in the resource unconstrained case, the generable languages are precisely the recursive enumerable languages. This is consistent with the known fact that standard transducers have images equalling the RE languages—the additional constraints of a generator do not sacrifice any expressive power. However, for testing this already leads to interesting conclusions, which we discuss in more detail later in the section: programs such as compilers often do deal with undecideability, and this places fundamental constraints on the types of properties that can be fully tested on such programs. Later in Section 5 and Section 6, we will see that additional resource (time or space) constraints lead to situations where the generator and their corresponding decision complexity classes do not coincide. Theorem 3.1 (Generability is Recursive Enumerability). RE = GEN. Proof. We defer the full proof to Appendix A.4. Intuitively, GEN ⊆ RE is due to the RE machine being able to enumerate through all finite bitstrings (as random seeds 𝑏) to check if the generator can produce some 𝑥. RE ⊆ GEN is due to the generator being able to perform dovetailing to find a single accepted string by the recogniser, which can then be used as fallback for a nondeterministic guess of the membership certificate for some randomly chosen 𝑥. □ Consequences for PBT: When testing a property for which the set of acceptable inputs is recursively enumerable, Theorem 3.1 implies that a generator for the complete input format exists—i.e., ambition in generator-writing is at least theoretically justified. However, properties whose preconditions are not recursively enumerable cannot be fully tested by any generator, no matter how it is engineered.

Complexity Theory of Randomised Testing

0:11

For instance, it is possible to write a generator that will output, with non-zero probability, all instances of seemingly very hard problems, such as: Definition 3.4. The language of halting computations on Turing machines: HALT = {⟨𝑀, 𝑤⟩ : Turing machine 𝑀 halts on input 𝑤 } The equality also yields a class of non-generable languages—ones that lie outside of RE. Corollary 3.1. All languages outside of RE are not generable. Non-RE languages are a large set, and one way to obtain languages in it is via complementing languages known to be in RE. A language 𝐿 is undecidable if there is no Turing machine that halts on all inputs and accepts exactly the strings in 𝐿. Rice’s theorem [39] is a well-known result that states all (non-trivial) semantic properties on Turing machines are undecidable. Hence, at least one of the language itself, or its complement, is non-RE. The result also extends from Turing machines to Turing-complete programming languages, and we will quote this version. For a Turing-complete programming language 𝐾, let 𝑃𝐾 be the set of encodings of well-defined programs written in 𝐾, and for 𝑀 ∈ 𝑃𝐾 let L (𝑀) be the set of strings 𝑤 such that 𝑀 (𝑤) executes without rejection (crashes or errors). A semantic property is a set 𝑆 ⊆ 𝑃𝐾 that depends only on program semantics: if L (𝑀) = L (𝑁 ) then 𝑀 ∈ 𝑆 ⇐⇒ 𝑁 ∈ 𝑆. It is non-trivial if 𝑆 ≠ ∅ and 𝑆 ≠ 𝑃𝐾 , and its complement is 𝑆 𝑐 = 𝑃𝐾 \ 𝑆. Rice’s theorem [39] implies every non-trivial semantic property is undecidable, yielding the following: Corollary 3.2. Let 𝑆 ⊆ 𝑃𝐾 be a non-trivial semantic property over programs written in a Turing complete language 𝐾. Then at least one of 𝑆 or 𝑆 𝑐 is not in GEN. Proof. Suppose for a contradiction both 𝑆 and 𝑆 𝑐 are generable, then both are also recursively enumerable by Theorem 3.1, thus 𝑆 is actually decidable. This contradicts Rice’s Theorem. □ These results are particularly applicable to software that can come face-to-face with non-RE languages, such as compilers. In this context, it means that there are properties of the compiler implementation that can never be completely tested, due to the lack of a generator for the property. This includes the use of rejection sampling. For example, in C++, termination is a property relevant for the well-definedness of programs, defined by the language specification. One might be interested in building a generator to test the compiler (its inputs being programs) for the following: programs that do not terminate should nonetheless not crash the compiler. However, although the terminating programs are generable, there are no generators of all non-terminating programs: Corollary 3.3. For a Turing-complete language 𝐾, the set of non-Halting programs, LOOP, is not generable, where LOOP = {𝑀 ∈ 𝑃𝐾 : 𝑀 takes no inputs and does not terminate} Consequences for PBT: You cannot fully test compiler properties with non-RE preconditions, e.g., the behaviour on non-terminating programs (Corollary 3.3). Any generator of a producible subset is testing a different, weaker property—a trade-off that should be made explicitly, not discovered accidentally. Of course, the existence of generators is only one of the concerns of PBT practitioners. We now turn to another important consideration: their efficiency.

0:12

Pingshi Yu, Chengsong Tan, Nicolas Wu, and Alastair Donaldson

Generator Families

We cannot wait all day for a generator to produce an output for an SUT: an effective generator needs to rapidly produce a large corpus of inputs for the SUT. Thus, as with algorithms, it is helpful to associate resource constraints with generators. But, unlike algorithms, generators do not have a natural input parameter on which the input size can be defined, and hence there also lacks a definition of resource constraint, which are based on the input size. In practice, PBT libraries like QuickCheck indeed include an optional size parameter, which a generator implementation can use to control the sizes of the generated objects. We introduce a similar parameter in our model, which allows a priori specification of the output size—from which we can then define the notion of resource usage for generators. Adding these constraints would allow our model to be applicable to generators that use the size parameter. The following aims to capture the notion of parameterised generators, namely a family of generators that each generates a portion of the intended language (instances of a particular size), and where the union of their generated languages is the whole language. Definition 4.1 (Implementation of a Family of TMs). Let (𝑀𝑖 )𝑖 ∈𝐶 be a family of TMs indexed by strings 𝐶 ⊆ {0, 1}∗ . We say that 𝑀 implements (𝑀𝑖 )𝑖 ∈𝐶 , written 𝑀 = (𝑀𝑖 )𝑖 ∈𝐶 , if (𝑀𝑖 )𝑖 ∈𝐶 is a uniform family as follows: • 𝑀 has an extra read-only input tape compared to each 𝑀𝑖 . • For all 𝑖 ∈ 𝐶, 𝑀 (𝑖) = 𝑀𝑖 . That is, with 𝑖 on the input tape of 𝑀, 𝑀 behaves exactly as 𝑀𝑖 . Definition 4.2 (Family of Generators). Let 𝐿 be a language, and (𝐿𝑖 )𝑖 ∈𝐶 a partition of 𝐿 indexed by the set 𝐶 ⊆ {0, 1}∗ . 𝐺 = (𝐺𝑖 )𝑖 ∈𝐶 is a generator for 𝐿 if for each Ð 𝑖 ∈ 𝐶, L (𝐺𝑖 ) = 𝐿𝑖 . The language generated by 𝐺, L (𝐺) is defined as L (𝐺) = 𝑖 ∈N L (𝐺𝑖 ). For the special case where 𝐶 = {1𝑖 : 𝑖 ∈ N} is used to partition a set 𝐿 into 𝐿𝑖 = {𝑤 ∈ 𝐿 : |𝑤 | = 𝑖}, we will also denote 𝐶 as N, and 𝐿1𝑛 as 𝐿𝑛 , for brevity. This will be used when we consider lengthbased partitions of a language 𝐿 in the following sections. Using this, we can define the generable languages under space and time constraints. Definition 4.3. For a time constructible function 𝑡 : N → N, the generator family 𝐺 = (𝐺𝑖 )𝑖 ∈N is time bounded by 𝑡 if for all 𝑖 ∈ N, 𝐺𝑖 terminates within time 𝑡 (𝑖). Define the class of languages GTIME(𝑡 (𝑛)) generable by some 𝑡-time bounded generators as: GTIME(𝑡 (𝑛)) = {L (𝐺) : ∀𝑖.𝐺𝑖 is time bounded by 𝑡 (𝑖)} Definition 4.4. For a space constructible function 𝑠 : N → N, the generator family 𝐺 = (𝐺𝑖 )𝑖 ∈N is space bounded by 𝑠 if for all 𝑖 ∈ N, 𝐺𝑖 uses no more than 𝑠 (𝑖) cells on its work tape. Define the class of languages GSPACE(𝑠 (𝑛)) generable by some 𝑠-space bounded generators as: GSPACE(𝑠 (𝑛)) = {L (𝐺) : ∀𝑖.𝐺𝑖 is space bounded by 𝑠 (𝑖)} The following is immediate for both time and space bounded generators: Proposition 4.1. Suppose 𝑠 : N → N is space-constructible with 𝑠 (𝑖) > log(𝑖), and 𝑡 : N → N is time-constructible with 𝑡 (𝑖) > 𝑖, then: GSPACE(𝑠 (𝑛)) ⊆ NSPACE(𝑠 (𝑛))

GTIME(𝑡 (𝑛)) ⊆ NTIME(𝑡 (𝑛))

Proof. By simulation. For a full proof, see Appendix A.5. 4.1

□

Alternative Notions of Size

In our formalisation, a generator 𝐺 for a language 𝐿 will produce, on input 𝑛, a random element 𝑥 ∈ 𝐿 of length exactly 𝑛. We discuss here some alternative possible formalisations of instance size, inspired by testing practice.

Complexity Theory of Randomised Testing

0:13

4.1.1 On generating elements of size |𝑥 | ≤ 𝑛. Some generators in practice produce, given an 𝑛 ∈ N, elements of size |𝑥 | ≤ 𝑛 rather than |𝑥 | = 𝑛. These generators can fit within our framework by observing that such generator 𝐺 of the language 𝐿 can be mapped to an equivalent generator of the following language: 𝐿pad = {𝑥#0𝑖 : 𝑥 ∈ 𝐿 ∧ 𝑖 ∈ N} where 0𝑖 denotes 𝑖 repetitions of the reserved element 0, and # is a dedicated separator element. If 𝐿pad is generable by the |𝑥 | = 𝑛 scheme (for a given 𝑛, produce elements of length exactly 𝑛), then 𝐿 is generable by the |𝑥 | ≤ 𝑛 scheme (for a given 𝑛, produce elements of length at most 𝑛). Moreover, observe that the decision complexity of 𝐿𝑝𝑎𝑑 is the same as 𝐿, hence the later no-go results from connections to decision complexity classes also applies for |𝑥 | ≤ 𝑛 generation schemes. 4.1.2 Other parameterisations of size. Apart from string length, there can also be other concievable notions of size for a language 𝐿, in forms of some computable function 𝑠𝑧 : 𝐿 → N. For instance, for CNF formulas, the number of clauses or variables can both be useful notions of size. However, it is difficult to define notions of complexity on metrics like the clauses or variables count. This is because formulas with a fixed number of clauses or variables can, in general, describe formulas of arbitrary size in terms of their string representations. Grouping these together in a complexity-theoretic formalisation would mean assigning the same measure of complexity to all such elements—yet the arbitrary lengths of their string representations would genuinely take vastly different (particularly time) resources to produce. For 𝑠𝑧 based on the number of clauses or variables, the string representations of 𝑥 with 𝑠𝑧 (𝑥) = 𝑚 has unbounded ratios: ∀𝑛 ∈ N.∃𝑚 ∈ N.∃𝑥 ∈ 𝐿𝑚 . |𝑥𝑚| > 𝑛, where 𝐿𝑚 = {𝑥 ∈ Σ∗ : 𝑠𝑧 (𝑥) = 𝑚}. Alternatively, consider another 𝑠𝑧 where 𝑠𝑧 (𝑥) is within some range of |𝑥 |, e.g. (1 − 𝛿)|𝑥 | ≤ 𝑠𝑧 (𝑥) ≤ (1 + 𝛿)|𝑥 | In these cases, we can recover the fixed-length paradigm by padding all elements with 𝑠𝑧 (𝑥) = 𝑚 to a string of length exactly (1 + 𝛿)𝑚: the 𝑠𝑧-𝑚 elements are generable in the 𝑠𝑧-based paradigm if and only if length (1 + 𝛿)𝑚 elements are generable in the fixed-length paradigm. 5

Polynomial-Time Generators

In this section, we discuss generators that run in polynomial time, which corresponds to the class of realistically implementable generators. We note that prior work [44, 45] also considered polynomial-time generators, and actually predates PBT [10] itself. In the course of establishing a number of new results, we will also walk through some previously known results (Corollary 5.1, Proposition 5.1, Proposition 5.3) within our framework to highlight the links between modern-day PBT and complexity theory. An equivalent version of the following definition was first introduced in Definition 3.1 of [44]. Definition 5.1 (Polynomial-Time Generators). The generator family 𝐺 = (𝐺𝑖 )𝑖 ∈N runs in polynomial time if there exists a polynomial 𝑝 such that for all 𝑖 ∈ N, 𝐺𝑖 terminates in time 𝑝 (𝑖). Remark 1. We do not need the empty set clause of Definition 3.1 in [44], because we define the generator of an empty set as one that rejects all inputs, and we can use its rejection within 𝑝 (𝑖) steps (on a length 𝑝 (𝑖) input bitstring) to determine the emptiness of L (𝐺𝑖 ). On the other hand, if L (𝐺𝑖 ) ≠ ∅, then it can never reject when provided with a length 𝑝 (𝑖) input bitstring. Definition 5.2. The class of languages generable by some polynomial-time generator is: Ø PG = GTIME(𝑛𝑖 ) 𝑖 ∈N

0:14

Pingshi Yu, Chengsong Tan, Nicolas Wu, and Alastair Donaldson

Generators in randomised testing often use rejection sampling to produce generators for properties that are difficult to write explicit generators for. However, this approach trades ease in development for runtime during generation. If a property 𝑡 is satisfied by the generator with probability 𝑝, then the expected samples (time) to find such an instance is 1/𝑝—and this can easily be exponential if 𝑡 occurs rarely enough. The polynomial time constraint implies that for realistic generators, the use of such rejection sampling is only possible in controlled cases where 1/𝑝 is at most a polynomial. We will first see that the polynomial time generable languages are wholly contained within NP. Corollary 5.1. PG ⊆ NP. Proof. Consequence of Proposition 4.1.

□

Consequences for PBT: Corollary 5.1 shows that NP membership of the precondition is a necessary condition for efficient generation: if a precondition is PSPACE-hard or coNP-hard (e.g. quantified formulas, unsatisfiable formulas), there is no hope in seeking a fast, fully general generator—one must resort to rejection sampling or restrictions. Example 5.1. If NP ≠ PSPACE, then the following PSPACE-complete language is not generable in polynomial time: QBF = {𝜙 : 𝜙 is a satisfiable quantified boolean formula} where a quantified boolean formula is a propositional boolean formula with quantifiers. Example 5.2. If NP ≠ coNP, then the following coNP-complete language is not generable in polynomial time: TAUT = {𝜙 : 𝜙 is true for all assignments} The natural follow up question is whether the containment PG ⊆ NP is strict. We see that PG does contain some of the hardest problems in NP, namely CNF-SAT. Proposition 5.1. CNF-SAT ∈ PG. Proof. We give a sketch of the key ideas, and defer full detail to Appendix A.6. Consider a generator that first samples a random assignment x, then generates the formula 𝜙 based on x clause-by-clause. For each clause, we pick a random literal to evaluate to True, referring to the earlier chosen assignment x. The other literals in the clause are chosen at random. By construction, as 𝜙 is in CNF, each clause of 𝜙 is satisfied by x, and thus 𝜙 [x] also evaluates to True. Any satisfiable CNF-SAT formula 𝜓 has a chance of being sampled this way: if 𝜓 is satisfied by y, then the above procedure has a chance of choosing y and then constructing 𝜓 around y. □ Consequences for PBT: A precondition that is hard to decide can still be easy to generate: you can fully test properties on a #SAT solver (Example 3.2) without ever solving SAT, for example by using the generator in Proposition 5.1. Thus, testing difficulty cannot be inferred from decision difficulty. However, having an efficient generator for an NP-hard language does not directly yield a way to sample from easier languages, due to the lack of natural reductions for generators (as far as we know). The reduction used in NP-hardness embeds the easier language into the harder language. For generators, we would like the opposite: to surjectively map from instances of the hard language to the easier one, which is what is needed to implement a generator for the easier language. In fact, despite having a generator for an NP-complete problem, we will show below an example of a language in NP (in fact, 𝑃) that is unlikely to have a polynomial-time generator.

Complexity Theory of Randomised Testing

5.1

0:15

PG vs. NP

We now introduce a concrete problem in NP that is likely not in PG, as its membership in PG would contradict cryptographic assumptions that have withstood decades of scrutiny. Following [43], we will base our construction on so-called collision-resistant hash functions. Definition 5.3 (Hash Functions [43]). A hash function ℎ is a collection of functions (ℎ𝑛 )𝑛∈N , ℎ𝑛 : {0, 1}𝑛+1 → {0, 1}𝑛 , such that there exists a computable function ℎ : N × {0, 1}+ → {0, 1}+ with ℎ(𝑛, 𝑥) = ℎ𝑛 (𝑥) for all 𝑛 ∈ N, and ℎ runs in time polynomial in 𝑛. Definition 5.4 (Collision-Resistant Hash Functions). Hash function ℎ is considered collisionresistant if there exists no polynomial-time bounded randomised algorithm 𝐴 : N → {0, 1}∗ × {0, 1}∗ and polynomial 𝑞 such that for infinitely many 𝑛 ∈ N: P(𝐴(𝑛) = (𝑥, 𝑦) ∧ 𝑥 ≠ 𝑦 ∧ ℎ𝑛 (𝑥) = ℎ𝑛 (𝑦)) >

1 𝑞(𝑛)

If a randomised collision-finding algorithm of Definition 5.4 exists for the polynomial 𝑝-bounded hash function ℎ, then one can find size-𝑛 hash collisions of ℎ in expected polynomial time. Remark 2 (Unkeyed hashes and uniform attacks). In cryptographic literature [27], keyed hash families (ℎ𝑘 )𝑘 ∈𝐾 are more commonly used, with security against non-uniform attacks. We instead use unkeyed hash functions (Definition 5.3) with security against uniform attacks (Definition 5.4). Unkeyed hashes capture practical algorithms like SHA-256, but cannot resist non-uniform attacks: a hash collision is guaranteed to exist for each 𝑛 by the pigeonhole principle, and it is possible to hard-wire them into non-uniform circuits. Uniform attacks [40] are a formalisation of the security guarantees in practice: collisions exist, but there exist no efficient algorithms to find them. As we shall see later, the uniformity of generators and the resistance of unkeyed hashes against uniform attacks are precisely what give us the non-generability result of Proposition 5.2. Define the following language for a hash function ℎ: Definition 5.5. For hash function ℎ: COLLISIONℎ = {(𝑥, 𝑦) ∈ {0, 1}+ × {0, 1}+ : 𝑥 ≠ 𝑦 ∧ |𝑥 | = |𝑦| ∧ ℎ |𝑥 | (𝑥) = ℎ |𝑥 | (𝑦)} Clearly, for any hash function ℎ (collision-resistant or not), given (𝑥, 𝑦), a Turing machine 𝑀 can execute ℎ(𝑥) and ℎ(𝑦), and accept if they compute the same hash. Since ℎ executes in time polynomial in its input size, 𝑀 will terminate in polynomial time. Lemma 5.1. For all hash functions ℎ, COLLISIONℎ ∈ 𝑃. Proposition 5.2. If for all hash functions ℎ, COLLISIONℎ ∈ PG, then collision resistant hash functions do not exist. Proof. Suppose COLLISIONℎ ∈ PG, then there exists a polynomial-time generator 𝐺 = (𝐺𝑖 )𝑖 ∈N with L (𝐺) = COLLISIONℎ . For a given 𝑛 ∈ N, we can find a collision of ℎ𝑛 by running 𝐺 2𝑛+1 (assuming 1 character is used as a separator) to obtain a pair (𝑥, 𝑦) ∈ COLLISIONℎ of size 2𝑛 + 1. Note this is possible due to the uniformity of (𝐺𝑖 )𝑖 ∈N . Since |𝑥 | = |𝑦| we know that |𝑥 | = |𝑦| = 𝑛, and hence the pair found is a collision of ℎ𝑛 : ℎ𝑛 (𝑥) = ℎ𝑛 (𝑦). As 𝐺𝑖 runs in polynomial time, we have therefore a randomised algorithm that finds hash collisions in polynomial time, for infinitely many 𝑛, and with success probability 1. □ Theorem 5.1 (Cryptographic Separation). If collision-resistant hash functions exist, then PG ⊊ NP. In fact, P ⊈ PG.

0:16

Pingshi Yu, Chengsong Tan, Nicolas Wu, and Alastair Donaldson

Consequences for PBT: Simple software may be infeasible to test efficiently, in full generality. Easyto-decide preconditions (here, checking a hash collision in Theorem 5.1) can still be difficult to generate satisfying inputs for. Easy decision complexity is neither necessary nor sufficient for generability. (For a classification of what is efficiently generable, see our certificate scheme of Theorem 7.1.) So, the power of efficient generators has an interesting relationship with the classical decision classes: PG contains some of the hardest problems in NP, yet it also does not contain some problems in P. We thus see that the complexity of the language for generation is a related but different concept from the complexity of the language for decision algorithms. Some generators in testing literature also make use of SAT solvers [6, 32, 46, 48], to increase expressivity. Here we quote a result first shown in [44]: with a SAT oracle, one can generate all NP problems in a polynomial number of steps. Let Σ𝑖𝑃 denote the 𝑖th level of the polynomial hierarchy with an NP base machine. For a generator class 𝑋 with constraints 𝑌 and language 𝐿, define 𝑋 𝐿 as the class of languages generable by generators with constraints 𝑌 and oracle access to a decider for 𝐿. For a generator complexity class Ð 𝑋 and a decision complexity class 𝐶, define 𝑋 𝐶 = 𝐿∈𝐶 𝑋 𝐿 . Proposition 5.3. ΣP1 = NP ⊆ PGNP ⊆ NPNP = ΣP2 Proof. A case from a more general result in [45]. See Appendix A.8 for a proof of this case.

□

Consequences for PBT: Although using a SAT/SMT solver during generation allows NP preconditions to be satisfied, Proposition 5.3 shows it is not a panacea: for example, PSPACE-hard or EXPTIME-hard preconditions remain out of reach even with a perfect SAT or SMT solver, respectively. 5.2

Expected Polynomial-Time Generators

Since sampling is inherently a random process, another feasible resource constraint on generators is via the expected time to produce a sample, rather than a deterministic time bound. The following defines expected polynomial time generators: Definition 5.6. The generator family 𝐺 = (𝐺𝑖 )𝑖 ∈N runs in expected polynomial time if there exists a polynomial 𝑝 such that for all 𝑖 ∈ N, 𝐺𝑖 terminates in expected time 𝑝 (𝑖). Moreover, for all 𝑤 ∈ L (𝐺𝑖 ), there exists at least one bitstream where 𝑤 is produced before time 𝑝 (𝑖). The condition that there exists at least one path of polynomial length for any 𝑤 ensures that there are no fundamentally difficult instances in the language.6 Our definition does not collapse to PG, since execution paths longer than polynomial are still permitted. Intuitively, expected polynomial time describes repeated retries of a polynomial process with bounded chance of failure: a generator version of BPP. On lucky runs, the process takes polynomial time, which corresponds to the existence of a polynomial-length path. Definition 5.7. The class of languages generable by some expected polynomial-time generator is: EPG = {L (𝐺) : 𝐺 is an expected polynomial-time generator} Proposition 5.4. PG ⊆ EPG ⊆ NP. Proof. A generator that terminates in deterministic time 𝑝 (𝑖) will also terminate in expected time at most 𝑝 (𝑖), thus PG ⊆ EPG. EPG ⊆ NP follows by simulation—for a full proof, see Appendix A.7. □ 6 Such an issue of hard instances hiding in long runs was also noted in [25], where interestingly, the modelling choice made

by Jerrum et al. [25] was to ignore the expected-time case and only focus on deterministic time bounds.

Complexity Theory of Randomised Testing

0:17

Consider the language PRIMES, defined as follows: Definition 5.8. Assume 𝑥 is interpreted in its binary representation, define: PRIMES = {𝑥 ∈ {0, 1}∗ : 𝑥 > 1 ∧ ∀𝑦.1 < 𝑦 < 𝑥 =⇒ 𝑔𝑐𝑑 (𝑥, 𝑦) = 1} We show that PRIMES ∈ EPG: an interesting case as it is an open problem in mathematics to determine whether there exists a PG algorithm for PRIMES [49]. That is, an algorithm which always produces a prime number of a certain size within polynomial time. However, it does have a natural algorithm running in expected polynomial time, and also does not follow the structure established for PG in Theorem 7.1. It would thus be tempting to conjecture that PG ⊊ EPG. Proposition 5.5. PRIMES ∈ EPG. Proof. This is a straightforward application of the fact that PRIMES ∈ 𝑃 [1], and the Prime Number Theorem on the density of primes. Together, these allow us to use rejection sampling for primes between 2𝑛 and 2𝑛+1 . See Appendix A.9 for a full proof. □ Consequences for PBT: Giving up worst-case polynomial time guarantees can at times result in simpler generator designs, and potentially allow more sets to be sampled (but is an open problem whether this is the case [49]). However, care must be taken to ensure the runtime is truly polynomial in expectation (as in Proposition 5.5), and that no element is intrinsically hard to sample: otherwise the efficiency and soundness (distributional support) guarantees no longer hold. Akin to boosting the probability of deciding a language in probabilistic complexity classes, we can make a similar statement on boosting the probability of generating an instance for EPG. Proposition 5.6. For 𝐿 ∈ EPG, and any 𝜖 > 0, there exists an algorithm 𝐴 that produces a sample 𝑥 ∈ 𝐿 of length 𝑛 with probability > 1 − 𝜖, in polynomial time of 𝑛 and log(1/𝜖). Proof. By considering long runs and using Markov’s inequality to bound the non-generation probability. See Appendix A.10 for a full proof. □ This boosting result means that for EPG languages, we can obtain samples with arbitrarily high probability in polynomial time. Thus, this would also rule out the membership of COLLISIONℎ in EPG, unless collision-resistant hash functions do not exist. Proposition 5.7. If collision-resistant hash functions exist, then EPG ⊊ NP. Moreover, 𝑃 ⊈ EPG. Proof. Suppose for a contradiction that for all hash functions ℎ, COLLISIONℎ ∈ EPG, then there exists an expected polynomial time generator that generates COLLISIONℎ . By Proposition 5.6, for any 𝑘 ∈ N, we can obtain a generator that produces a length-𝑛 sample of COLLISIONℎ with probability at least 1/𝑘, within polynomial time in 𝑛 (with 𝜖 fixed to 1/𝑘, the log(1/𝜖) term becomes a constant factor in the polynomial). Since this is a procedure that violates the collision resistance property (Definition 5.4) of ℎ, no hash functions are collision resistant, which is a contradiction. □ 6

Space Bounded Generators

Space-bounded generators have a limited amount of space to work with, but can exhibit arbitrary running time. Whilst this seems like a rather loose restriction on generators, we note that these constraints actually correspond to a large class of generators implemented in practice. Space-bounded generation can model test-case generation algorithms that produce not only independent outputs in a single run (like in the case of PG or EPG), but also past-dependent outputs in an iterative fashion. That is, algorithms where previous outputs can influence future produced