Today, we'll continue our conversation from last time about testing and how to make it better.

Sorting records, continued

Recall that we considered generating random tests and validating properties of the output for the sort_records function.

We can make a distinction relevant to these two answers: soundness vs. completeness.

This distinction comes from proof theory: a proof system is sound if everything that is provable is in fact true, and complete if if everything that is true has a proof (Source: Cornell soundness and completeness lecture notes).

Other examples

Consider another example function: integer prime factorization.

The task of this function: given an integer, express that integer as the product of primes.

For example:

4 -> 2*2
1 -> 1
12 -> 2*2 * 3

We'll again break down the task of property-based testing to two concerns: (1) generating inputs, and (2) checking the validity of the output the function calculates for that input.

One problem we encounter with this example is that one of these properties is more difficult to check! Knowing if a number is prime can be computationally difficult as numbers get larger.

We might test just a subset of properties. For example, that the product is correct and that no prime factor is even.

Assorted testing topics

Next, we'll go through an assortment of topics related to testing, with an eye toward some industry terminology.

"Test-driven development"

The approximate formula:

1. Take your specification from the client.
2. Define the data types your program needs, with as little detail as possible to write tests.
3. Convert the specifications into tests. Run the tests, any new ones should fail (because you haven't actually implemented them).
4. Implement the simplest code that passes the new tests. Check that they pass.
5. Improve/optimize the code while maintaining that the tests pass.

Anecdote: a class I had as an undergraduate actually required us to turn in our test suite far before the assignment was due, and we were graded on how many bad implementations our test suite could uncover!

Distinction: unit vs. integration testing

"Unit" testing tends to mean checking a single, specific function in your codebase.

Large scale software projects also aim to have "integration" tests that intend to check functionality across numerous functions, typically with the goal of modeling a production flow of data. For example, an integration test for a web-based application may test that a piece of data coming in from the network is correctly parsed, analyzed, then written to the database.

A challenge with integration tests is that some inputs and outputs of our computer system may be difficult to simulate in a testing environment. For example, we wouldn't want our tests to write fake data to a real production database.

Mocking objects/designing for testing

To test code written for production without actually impacting production, integration tests often need to "mock" some components of the data.

An analogy from Wikipedia: you can think of mock objects as being similar to crash dummies for testings cars, except for software!

System designers could choose to mock objects for the following reasons: because the real code would modify a production resource (which could also have privacy implications), because the test is trying to simulate something that happens intermittently (like network traffic or a timer going off), or because it would be impractical for an automated test to wait for certain inputs (user interaction, sensor or Bluetooth data).

Mock objects share the same interface as the "real" data (for example, they might be a subclass in an object-oriented language like Java) but have a minimal implementation.

Often, the production implementation code itself might need "hooks" to allow engineers to swap in a testing configuration.

Metric: Test coverage

One way to measure the "success" of a test suite is to look at its *coverage: the number of lines of code executed by a run of the test suite (or sometimes, the number of blocks in the control flow graph executed).

Different languages have different tools and libraries for automatically calculated test coverage. Some teams require new code to strictly improve the total test coverage metric for a project.

Google Code Coverage Best Practices: "Although there is no “ideal code coverage number,” at Google we offer the general guidelines of 60% as “acceptable”, 75% as “commendable” and 90% as “exemplary.”"

Coverage-guided fuzzing

Note, fuzzing is widely used! See the Oss-Fuzz (Open-Source Software program).

One distinction between fuzzing and PBT is that fuzzing systems tend to have less programmer specification on how to generate inputs (though the terminology is quite fuzzy here in practical use).

One way that fuzzing systems get better without having programs specify exact input generation strategies is by automatically searching for inputs that achieve higher test coverage percentages.

For example, if we were fuzzing a Linux command-line utility, much of the initial code where purely random inputs would fail would be in parsing the input strings. This makes inputs fail before they get to the interesting "business logic" of the program. Fuzzing systems attempt to build on inputs that achieve progressively higher coverage, which indicates that the inputs have gotten "deeper" into the code.

Test-case reduction

Note that whether you manually run into an issue, or find it via an automated technique like fuzzing or PBT, bugs are more useful when they are concise, replicable, and actionable.

For a fun video example of manual test case reduction, see this blog post and video by my PhD advisor, Adrian Sampson.

Differential testing

Sometimes, it's hard to describe the output with properties for every generated program.

For an example close to my heart, consider compilers that must generate assembly code (e.g., x86-64). There are many different valid sequences of x86 instructions to implement a specific high-level piece of code.

Differential testings is the idea that while the exact outputs of multiple distinct systems need not be the same, some behavior of those outputs should be.

In the case of compilers, differential testing involves compiling the same input program with multiple distinct compilers (e.g., GCC, LLVM, Intel's ICC) and checking that when executed, the programs produce the same output.