Skip to content
Software Testing · First Principles

The Infinite Input Space — Why You Can't Prove It Works

The overview made one uncomfortable claim and asked you to take it on faith: you cannot prove non-trivial software works by testing it. This page pays that debt. We are going to make the claim precise — precise enough that you could not un-believe it if you tried — by doing nothing more sophisticated than counting.

The argument is arithmetic, not philosophy. Once you have counted the inputs to the simplest function you can imagine, the conclusion is forced: testing is not proof, and it never could be. What testing is — sampling, betting, buying confidence — falls out the other side, and the rest of the book is about doing that well.

Count the inputs to the simplest possible function

Section titled “Count the inputs to the simplest possible function”

Take a function so trivial it feels insulting to test: add two integers.

    fn add(a: i64, b: i64) -> i64

No state, no I/O, no clock, no network. Two arguments in, one number out. How many distinct inputs does it have?

An i64 is a 64-bit integer, so it has 2⁶⁴ possible values. The input is a pair of them, so the number of distinct (a, b) pairs is:

    2^64  ×  2^64  =  2^128


    2^128  ≈  3.4 × 10^38


    = 340,282,366,920,938,463,463,374,607,431,768,211,456
      distinct inputs — for a two-line function.

Now suppose you had an absurdly fast test rig that could run and check one billion (10⁹) inputs every second. How long to try them all?

That is add. It is the friendliest function in existence. It is pure, deterministic, and takes only two arguments. And exhaustive testing is already physically impossible — not hard, not expensive, impossible in this universe.

Real programs are unimaginably worse

Section titled “Real programs are unimaginably worse”

Every ingredient a real program adds multiplies the space, and the multiplications compound:

  • More arguments. A function of n arguments multiplies the counts. Three i64s is 2¹⁹² inputs. Four is 2²⁵⁶ — already more than the estimated number of atoms in the observable universe.
  • Wider types. A single String argument has no fixed size at all: the set of possible strings is countably infinite. One string parameter already makes the input space unbounded.
  • State. A method on an object behaves differently depending on the object’s current fields. The real input is (arguments × every reachable internal state), and state accumulates across calls.
  • Time. Behavior can depend on the clock: leap seconds, month boundaries, the year 2038, daylight-saving transitions. The current time is effectively another input, and it is never the same twice.
  • Concurrency. With two threads touching shared data, the input includes the interleaving — the order in which their steps happen to land. There are exponentially many interleavings, and the scheduler picks a different one each run. (This is exactly what rust/kvlite/tests/concurrency.rs probes for the key-value store.)
  • The outside world. Disk-full, a truncated network packet, a slow DNS reply, a corrupt file. Each is another dimension of input you did not choose and cannot enumerate.
    add(i64, i64)         2^128 inputs            (already impossible)
        + more args       × 2^64 each
        + a String arg    × infinity
        + object state    × every reachable state
        + the clock       × every distinct instant
        + threads         × every interleaving
        + the environment × every failure mode
        ───────────────────────────────────────────
        a real program:   effectively infinite

You are not choosing between “test everything” and “test most of it.” You are choosing which vanishingly thin slice of an infinite space to sample. That reframing is the whole point of this page.

Under the hood — counting inputs in bits

Section titled “Under the hood — counting inputs in bits”

The reason these numbers explode so fast is that input spaces grow exponentially in the number of bits, and it is worth being able to do the estimate on a napkin. The trick: an input made of b bits has 2ᵇ possible values, and combining inputs adds their bit-widths (because you multiply their counts, and multiplying powers of two adds exponents).

    Input                         bits (b)   distinct values (2^b)
    ─────────────────────────────────────────────────────────────
    one bool                        1        2
    one byte  (u8)                  8        256
    one i32                        32        ~4.3 × 10^9
    one i64                        64        ~1.8 × 10^19
    two i64s  (add's arguments)   128        ~3.4 × 10^38
    a 20-char ASCII string        140        ~1.4 × 10^42

A handy rule of thumb: every 10 bits is roughly ×1000 (2¹⁰ = 1024 ≈ 10³). So 128 bits is about 10^(128 × 0.301) ≈ 10³⁸, which is where the 3.4 × 10³⁸ came from without a calculator. The practical upshot: whenever you see a function’s arguments, mentally add up their bit-widths. Past about 40 bits (a trillion inputs) exhaustive testing is already off the table, and most single arguments blow past that alone. This is why you sample: the arithmetic leaves no other option.

Testing is sampling, not proof

Section titled “Testing is sampling, not proof”

Here is the consequence, stated as sharply as it can be. When you run a test, one of exactly two things happens:

  1. The test fails. This is conclusive: you have found an input for which the program is wrong. A single failing test proves the program incorrect for that input. This is real, hard knowledge.
  2. The test passes. This tells you only that the program was correct for the specific inputs you tried. It says nothing about the astronomically larger set of inputs you did not try.

This asymmetry is the heart of the matter, and it is Dijkstra’s famous formulation:

“Testing shows the presence of bugs, not their absence.” — Edsger W. Dijkstra, 1969

A failing test is a proof of presence. A passing test is not a proof of absence — it is the absence of a proof of presence, which is a very different and much weaker thing. Think of testing as fishing an infinite lake: catching a fish proves there are fish; catching nothing all afternoon does not prove the lake is empty. It proves your hooks did not land where the fish were.

    INFINITE INPUT SPACE  (every possible input to the program)
    ┌─────────────────────────────────────────────────────────┐
    │                                                          │
    │     • • •         the inputs your tests actually try     │
    │   •   ×   •        (a finite handful; × marks a bug)     │
    │     • • •                                                │
    │                                                          │
    │   everything else — untested, unknown, unproven          │
    │                                                          │
    └─────────────────────────────────────────────────────────┘
      Green suite = "no bug found in the dots we sampled."
      It says nothing about the vast blank space around them.

Green means “no bug found in the cases we tried”

Section titled “Green means “no bug found in the cases we tried””

Internalize the precise meaning of a green test suite, because most of the industry quietly mistranslates it:

  • What people hear: “The software is correct.”
  • What green actually means: “For the finite set of inputs these tests exercised, the program produced the expected outputs — this time.”

That is a real, useful signal. It is evidence. It is just not proof, and the gap between the two is where production incidents live. A passing suite is a receipt showing what you checked; it is never a certificate of correctness for what you didn’t.

This is not pedantry — it changes how you act. If green meant “correct,” a passing suite would be a stopping point: you’d be done. Because green really means “no bug found in the cases we tried,” a passing suite is instead an invitation: the honest next question is always which cases did we not try, and which of those are risky? The tester who reads green as “done” ships bugs; the tester who reads it as “which slice didn’t I sample?” finds them first. Every technique in the later Parts of this book — coverage, property-based testing, fuzzing, mutation testing — is a different, systematic answer to that same question: how do I make my sample land where the bugs actually are?

Every test case is a bet

Section titled “Every test case is a bet”

If you can only sample a thin slice, then choosing the slice is the entire craft. And here is the idea that turns “testing is sampling” into a usable skill: every test case you write is an implicit bet.

When you test add(2, 3) and get 5, you are almost never actually interested in the pair (2, 3). You are betting that (2, 3) stands in for a huge class of “two small positive integers that don’t overflow” — that if the function is right for (2, 3), it is right for (2, 4), (10, 7), and a billion other pairs you will never run. You are wagering that the whole class behaves the same way, and that one representative speaks for all of it.

That wager is usually reasonable, and it is the only thing that makes testing tractable. But notice what it means: your test suite is a portfolio of bets about which inputs are equivalent. The bug lives wherever your bet is wrong — wherever an input you assumed behaved like your representative actually behaves differently.

    You wrote one test:      add(2, 3) == 5


    The bet you actually made:
      "small positives behave alike" — one representative covers the class.


    Where the bet quietly fails:
      add(i64::MAX, 1)   → overflow: a DIFFERENT class you never bet on
      add(i64::MIN, -1)  → another boundary the representative hid


    A good tester bets on the RISKY classes, not the comfortable ones.

This is the seed of equivalence partitioning and boundary-value analysis, techniques we develop fully later in the book. For now, keep the intuition: you are not trying to cover the input space (you can’t); you are trying to identify the classes where behavior changes — around zero, at the maximum, on the empty input, at the type boundary, at the leap second — and place one bet on each. Good test design is finding the boundaries between equivalence classes and betting there, where the bets are most likely to be wrong.

Notice the shift in mindset this forces. A beginner writes tests by asking “what inputs are easy to type?” and ends up with a dozen bets on the same comfortable class — add(2, 3), add(4, 5), add(10, 20) — which together cover exactly as much of the space as one of them, while the overflow boundary, the sign boundary, and zero all go untested. An experienced tester writes one test per class and spends the saved effort discovering classes the beginner never noticed. The number of tests is not the point; the number of distinct bets on distinct classes is. A real example lives in rust/kvlite/tests/server.rs: the round-trip test SET name ada lovelace → GET name → VALUE ada lovelace is a deliberate bet on the risky class “values containing spaces survive the wire protocol” — a class the naive single-word test SET k v would never have covered.

But doesn’t proof exist? Yes — rarely, and at a price

Section titled “But doesn’t proof exist? Yes — rarely, and at a price”

An honest objection: mathematicians do prove programs correct, and some inputs can be exhausted. Both are true, and both are exceptions that prove the rule.

  • Exhaustive testing is possible when the input space is genuinely small. A function taking a single u8 (one byte) has only 256 inputs — you can, and should, try all of them. The technique is real; it just evaporates the instant the space grows, which it almost always does.
  • Formal verification proves a program meets a specification for all inputs using mathematical logic, not sampling. It is real and powerful — it is used for CPU designs, aircraft control code, cryptographic protocols, and the seL4 microkernel. But it is expensive: it demands a formal specification (itself a huge effort), specialist skills, and often more work than writing the code. It is reserved for software where a bug is catastrophic and the budget is enormous.

For the overwhelming majority of software — web apps, services, libraries, the code you will actually ship — neither exhaustive testing nor formal proof is affordable. Sampling well is the only option you can pay for. That is not a defeat. It is the constraint that makes testing a discipline worth mastering: given that you can only sample, sample where it matters most.

    Strength of guarantee                 Affordability / when to use
    ─────────────────────────────────────────────────────────────────
    Formal verification   proof, all inputs   rare · catastrophic-risk,
                                              huge budget (avionics, kernels)
    Exhaustive testing    proof, tiny space   only when inputs are small
                                              (e.g. a single u8: 256 cases)
    Sampling (testing)    evidence, not proof the default for ~all software
                                              — cheap, and the only affordable
                                                option once the space is big

The order of that table is also an order of cost: the stronger the guarantee, the more you pay and the narrower the situations where you can justify it. Real engineering lives in the bottom row almost all the time, which is why this book spends its pages there.

Where this leaves us

Section titled “Where this leaves us”

So testing can never prove correctness. If you stop reading here, that sounds like bad news — the goal is unreachable. But it is not the goal. The goal was never proof; it was justified confidence, and confidence is exactly the kind of thing you can buy with a good sample. A test suite that bets on the risky classes and comes back green has genuinely earned you something: not certainty, but a defensible, evidence-backed belief that the risky paths work.

That is the subject of the next page: if a passing suite is not proof, then what is it worth, and how do you make it worth more? We have established the constraint. Now we turn it into a strategy.

The architect’s lens

Section titled “The architect’s lens”
  • Why does it exist? The idea “testing is sampling from an infinite space” exists because the alternative — proof by exhaustion — is physically impossible for all but the tiniest functions, as the 2¹²⁸ count for a two-integer add makes undeniable.
  • What problem does it solve? It replaces an impossible goal (“prove it correct”) with an achievable one (“gather enough evidence, on the right inputs, to justify confidence”), which is the only goal you can actually fund.
  • What are the trade-offs? Sampling can never give certainty — a passing suite is evidence, not proof — so you trade the impossible dream of guaranteed correctness for the affordable reality of managed risk. The skill is spending a finite testing budget where a wrong bet hurts most.
  • When should I avoid it? When the input space is genuinely tiny (test it exhaustively instead) or when a defect is catastrophic and the budget is huge (reach for formal verification). Sampling is the default precisely because those conditions are rare.
  • What breaks if I remove it? If you forget testing is sampling, you read a green suite as “proven correct,” stop hunting for the classes you never sampled, and ship the Ariane 5 / Pentium-shaped bug that was hiding on the slice your bets never covered.

Check your understanding

Section titled “Check your understanding”
  1. A colleague says, “Our whole test suite is green, so the feature is correct.” Using the infinite input space, explain precisely what is wrong with that inference — and what green does legitimately mean.
  2. Count the input space of fn add(a: i64, b: i64) -> i64 and explain, in one or two sentences, why exhaustive testing of it is impossible even with a billion-checks-per-second machine.
  3. Restate Dijkstra’s line — “testing shows the presence of bugs, not their absence” — in terms of the two possible outcomes of running a single test, and why they are asymmetric.
  4. You write one test: add(2, 3) == 5. What bet are you actually making, and name two inputs where that bet could quietly be wrong.
  5. Formal verification and exhaustive testing both give stronger guarantees than sampling. Why isn’t the answer “just always use them,” and what makes sampling the default for most software?
Show answers
  1. The suite only exercised a finite handful of inputs out of an effectively infinite space, so a pass tells you nothing about the untested rest — it cannot prove the absence of bugs. Green legitimately means only “no bug was found in the specific cases we tried, this time”: it is evidence, not proof.
  2. It has 2⁶⁴ × 2⁶⁴ = 2¹²⁸ ≈ 3.4 × 10³⁸ distinct inputs. At 10⁹ checks/second that is ~3.4 × 10²⁹ seconds ≈ 1.1 × 10²² years — roughly 800 billion times the age of the universe — so you can never run them all; the barrier is counting, not engineering.
  3. A test can only fail (conclusive: the program is wrong for that input — a proof of presence) or pass (inconclusive: correct only for the inputs tried — no proof of absence). The outcomes are asymmetric because one failing case proves incorrectness outright, while any number of passing cases still leaves the infinite unsampled remainder unproven.
  4. You are betting that (2, 3) represents the whole class of “small positive integers that don’t overflow,” so one representative speaks for all of them. It could be wrong at inputs in other classes you never bet on — e.g. add(i64::MAX, 1) (positive overflow) or add(i64::MIN, -1) (the negative boundary).
  5. Because both are prohibitively expensive: exhaustive testing only works when the input space is tiny (it evaporates as the space grows), and formal verification demands a formal spec, specialist skills, and often more effort than the code itself. For ordinary software neither is affordable, so sampling well — betting on the riskiest classes — is the only option you can actually pay for.