Software QA FYI - SQAFYI

Heuristic Test Oracles

By: Douglas Hoffman

Capture and comparison of results is one key to successful software testing. For manual tests this often consists of viewing results to determine if they are anything like what we might expect. It is more complicated with automated tests, as each automated test case provides a set of inputs to the software under test (SUT) and compares the returned results against what is expected. Expected results are generated using a mechanism called a test oracle.

The term oracle may be used to mean several things in testing—the process of generating expected results, the expected results themselves, or the answer to whether or not the actual results are what we expected. In this article, the word oracle is used to mean an alternate program or mechanism used for generating expected results.

It is often impractical to exactly reproduce or compare accurate results, but it isn’t necessary for an oracle to be perfect to be useful. Several categories of oracles are described in Table 1. In this article, I’ll describe some ideas associated with what I call heuristic oracles.

A heuristic oracle provides exact results for a few inputs and uses simpler consistency checks (heuristics) for the rest. Regardless of the complexity of the SUT, known or easily-computed result values can be chosen for the exact comparisons. The heuristic oracle can usually be built into the test case or verifier to simplify testing. This approach can have substantial advantages. Furthermore, the same heuristic oracle or simple variations are often reusable across broad classes of software.

As a simple example of the idea, consider the sine function (see Figure 1). An implementation of sine could be tested against a separately implemented routine that uses a different computational algorithm. That separate routine is a True Oracle. Such an oracle is very flexible—it can be used with as many test inputs as you have time to generate, it can accept any inputs the SUT can, and it has a high likelihood of identifying errors.

Note that it won’t necessarily find all errors because it might share some with the SUT. For example, the same hardware or operating system fault might affect both (such as the “Pentium bug”), or both might use the wrong units. In such cases, both the SUT and the oracle could produce the same wrong answer. Unfortunately, this independent oracle is expensive both to create and use, often costing as much or more than the SUT to develop and using equal or greater machine resources. It also has a high likelihood of having its own errors because its complexity often rivals the SUT.

The other extreme is to have no oracle at all. I’ve reviewed automated tests that were proudly created and run, sending thousands or millions of test values to the SUT—and confirming nothing more than that the test does not crash the system or provide some other spectacular notice to the tester.

That’s not expensive, but it’s also rarely useful and certainly tells us nothing about whether the answers from the SUT are correct.

A heuristic oracle provides a reasonable alternative between slow, expensive, and voluminous results generation on the one hand, and unverified SUT results on the other. The approach can be used when the SUT can be characterized as having a nice, predictable relationship between the inputs and results—one that can be exploited in testing. (See the sidebar for a further discussion of the relationships where heuristic oracles can most easily be used.) For the sine function, the predictable relationship used for the heuristic is that the function increases between 0 and 90 degrees, decreases from 90 to 270 degrees, and increases again to 360 degrees. The exact value of sine at 34 degrees is hard to predict, but you can easily check that it’s larger than the value at 33 degrees and smaller than the value at 35 degrees. For the values of sine that are easy to predict [sin(0) is 0, sin(90 degrees) is 1, sin(180 degrees) is 0, and sin(270 degrees) is –1], exact results can be checked. Between the four values the heuristic applies.

Full article...

Other Resource

... to read more articles, visit

Heuristic Test Oracles