The Test Oracle Problem

In software testing, we focus on generating test inputs. But a test input is only half of a test case. The other half is knowing what the correct output should be.

This is the Test Oracle Problem.

A test oracle is a procedure to determine if a test passed or failed. The problem is that distinguishing between correct and incorrect behavior is often difficult. For complex systems, creating an oracle can be as difficult as writing the program itself. This is a bottleneck for test automation.

Consider a function that calculates the average of an array:

public static float calculateAverage(int[] values) {
    if (values == null || values.length == 0) {
        return 0;
    }
    long total = 0;
    for (int i = 0; i < values.length; i++) {
        total += values[i];
    }
    return (float) total / values.length;
}

We can manually determine that calculateAverage([1, 2, 3]) should be 2.0. But what is the correct output for calculateAverage([Integer.MAX_VALUE, 1])? An automated test needs a way to compute this expected value without re-implementing the function.

If we cannot automatically and reliably determine the expected behavior, we cannot fully automate our testing.

Sources of Oracle Information

To build an oracle, we extract the expected behavior from a source. This can be manual or automated. Common sources include:

• Documentation: User manuals, software requirements, and design documents.
• Reference Implementations: Another program (or an older version of the same program) can serve as an oracle. The test fails if the new implementation's output differs from the reference implementation's output for the same input.
• Algebraic Properties: Test properties that must be true, even without knowing the exact result. For a Stack data structure, assert that pop(push(s,v)) equals s.
• Formal Specifications: Languages like the Java Modeling Language (JML) specify behavior using pre-conditions (requires) and post-conditions (ensures) in code annotations. These can be checked at runtime.

Automating Oracles with In-Code Checks

The most common way to automate oracles is to embed them in test code.

1. Assertions

Test frameworks like JUnit provide assertion methods. An assertion is an automated oracle for a test. The example assertEquals(0, calculateAverage(emptyArray)) checks if the calculateAverage function produces the expected value 0 when given an empty array.

2. Representation Invariants

A representation invariant is a property that any instance of a class must fulfill at all times (or at the end of every public method).

This is implemented as a method, repOk() or isValid(), that returns true if the object's internal state is valid.

For example, a Submission class may have requirements that the title is at most 80 characters and the body is at most 250 words. An oracle can be written to check this:

// A method inside the Submission class
public boolean isValid() {
    // Check title constraints
    if (this.title != null && this.title.length() > 80) {
        return false;
    }
    
    // Check body constraints
    if (this.body != null) {
        int wordCount = this.body.strip().split("(\\s+)").length;
        if (wordCount >= 250) {
            return false;
        }
    }
    
    // All checks passed
    return true;
}