Tests should accept any correct program ↑ Writing ↑ cceckman.com

Let’s talk about software tests.

A test is a program that takes in some other program, and returns an accept/reject response: my_test(program) -> boolean.¹

A test is supposed to check some (not all) correctness properties of the program. But it’s easy to write a test that checks the wrong thing, and rejects programs that are correct.

This leads to a comment I often make during code review:

A test should accept on any correct program.

The spectrum of software correctness

Writing good tests requires careful thought, and not a little effort.

At the one end of the spectrum are tests that apply over all inputs. You might write and check a proof, or use a model checker. These require careful formalizations – even restructuring of the software – to make sure the property you’re trying to test is actually decidaable.

Alternatively, you can test empirically, and run the program on a subset of possible inputs. Property testing and fuzz testing can explore the input space to find interesting inputs. Most commonly (in my experience), you write directed tests, where the particular input is embedded in the test.²

Don’t look under the hood

The easiest test to write requires very little thought: a change-detector test, which precisely mirrors the code under test.³ More broadly, it’s easy to write tests that depend on details of the code under test that are not relevant for correctness.

Consider this (Pythonic) pseudocode example:

def add_from_fetched_arguments(fetch_a: Callable[[], int], fetch_b: Callable[[], int]) -> int:
    a = fetch_a()
    b = fetch_b()
    return a + b

The program name gives its expectation: it adds whatever it fetched from the arguments.

You might be tempted to write a test that:

1. Asserts that A is called (and provides value 3)
2. Asserts that B is called (and provides value 4)
3. Asserts that the result is 7

But which of these properties is relevant for correctness? If fetch_a and fetch_b have no side effects or ordering constraints, then only property (3) actually matters!

You might say: “If you test on just inputs 3 and 4, then return 7 passes the tests, but is not correct!” That’s true – and if that’s a problem, then you should consider writing multiple test cases so the trivial result doesn’t hold, or upgrading to a property-based test.⁴

Asymmetry in testing

Directed tests, property-based tests, and fuzzers are all forms of testing, not proof. As Dijkstra said,

Testing shows the presence, not the absence of bugs.

More generally, a test can prove incorrectness, but not correctness.

If we know a test won’t prove correctness, we should be broad in what we consider correct; tend towards false positives (accepting some incorrect programs), not false negatives (rejecting correct programs). A test will only ever validate a narrow set of properties – keep those properties to the bare minimum.

Practical advice

Use test-driven development: write the tests, then write the implementation. Write the test based on what must happen for success, not what could happen.

Use fakes instead of mocks. Test outcomes / state, not interactions.

Try out property-based testing. Carry proofs in your types.

Finally, use good judgement. There are cases where checking the an exact output can be valuable,⁵ and times when specific examples are more useful than general properties.⁶ It’s not always practical to build a test that is completely isolated from implementation details; just be careful which details you embed in the test, and try to keep the set minimal.

Let me know if you have thoughts on this!