Tools & Automation

Heuristic
QUICK LOOK
■ When and why to use
heuristic oracles
■ Choosing your heuristic

Test Oracles The balance between exhaustive comparison

■ When heuristics won’t work

and no comparison at all by Douglas Hoffman

C
apture 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 any-
thing 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 com-
pares 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 generat-
ing 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 alter-
nate program or mechanism used for generating expected results.

Table 1: Five Approaches to Oracles

he heuristic approach is only one implement in a tool chest for SQA—the decision about which approach is best for you
T depends on your test situation. The table below gives descriptions of five approaches to oracles that have been successfully
employed across the software industry to verify automated software tests.

TRUE ORACLE HEURISTIC ORACLE SAMPLING ORACLE CONSISTENT ORACLE NO ORACLE

Definition ■ Independent ■ Verifies some values, ■ Selects a specific ■ Verifies current run ■ Doesn’t check
generation of all as well as consistency collection of inputs results with a previous correctness of results
expected results of remaining values or results run (Regression Test) (only that some results
were produced)
Advantages ■ No encountered ■ Faster and easier ■ Can select easily ■ Fastest method ■ Can run any amount
errors go than True Oracle computed or using an oracle of data (limited only by
undetected ■ Much less expensive recognized results ■ Verification is the time the SUT takes)
to create and use ■ Can manually verify straightforward
with only simple ■ Can generate and

oracle verify large amounts

of data
Disadvantages ■ Expensive ■ Can miss systematic ■ May miss systematic ■ Original run may ■ Only spectacular
to implement errors (as in and specific errors include undetected failures are noticed
■ Complex and often following sine ■ Often “trains the errors
time-consuming wave example) software to pass
when run the test”

29
March/April 1999 Software Testing & Quality Engineering [Link]
 FIGURE 1 A sine wave FIGURE 2 A sine wave with errors FIGURE 3 Another incorrect sine
that could be detected by a heuristic oracle wave

It is often impractical to exactly reproduce or compare nothing more than that the test does not crash the system
accurate results, but it isn’t necessary for an oracle to be or provide some other spectacular notice to the tester.
perfect to be useful. Several categories of oracles are That’s not expensive, but it’s also rarely useful and certain-
described in Table 1. In this article, I’ll describe some ideas ly tells us nothing about whether the answers from the SUT
associated with what I call heuristic oracles. are correct.
A heuristic oracle provides exact results for a few A heuristic oracle provides a reasonable alternative
inputs and uses simpler consistency checks (heuristics) for between slow, expensive, and voluminous results genera-
the rest. Regardless of the complexity of the SUT, known or tion on the one hand, and unverified SUT results on the oth-
easily-computed result values can be chosen for the exact er. The approach can be used when the SUT can be charac-
comparisons. The heuristic oracle can usually be built into terized as having a nice, predictable relationship between
the test case or verifier to simplify testing. This approach the inputs and results—one that can be exploited in testing.
can have substantial advantages. Furthermore, the same (See the sidebar for a further discussion of the relation-
heuristic oracle or simple variations are often reusable ships where heuristic oracles can most easily be used.) For
across broad classes of software. the sine function, the predictable relationship used for the
As a simple example of the idea, consider the sine heuristic is that the function increases between 0 and 90
function (see Figure 1). An implementation of sine could degrees, decreases from 90 to 270 degrees, and increases
be tested against a separately imple-
mented routine that uses a different
computational algorithm. That separate
routine is a True Oracle. Such an oracle What are nice,
is very flexible—it can be used with as predictable relationships?
many test inputs as you have time to
generate, it can accept any inputs the lgorithms and results come in many forms. Often there are so many variables
SUT can, and it has a high likelihood of
identifying errors.
A involved that we despair at the prospect of entering arbitrary data in a test,
and we fall back on sets of input and result values we already know. Heuristic ora-
Note that it won’t necessarily find
all errors because it might share some cles depend upon our seeing some relationship between the inputs and results in
with the SUT. For example, the same the SUT and exploiting that relationship through an underlying simpler one.
hardware or operating system fault So, one question is what types of relationships should we look for? I define
might affect both (such as the “Pen- “nice relationships” as ones that work for ranges of inputs and/or outputs. The
tium bug”), or both might use the
heuristic must hold for all values in the definable range(s) of inputs or results—
wrong units. In such cases, both the
SUT and the oracle could produce the without gaps. When there are exceptions in the range, the function (or compari-
same wrong answer. Unfortunately, son) gets extremely complicated, usually negating the value of using the heuristic
this independent oracle is expensive oracle. It gets really difficult to sort through input values to decide if the relation-
both to create and use, often costing ship applies. If the sine relationship (sequential results getting larger or smaller)
as much or more than the SUT to
only worked for integer degree values, the heuristic wouldn’t be very useful. In
develop and using equal or greater
machine resources. It also has a high order to be “nice” the relationship needs to be continuous. It may only apply for
likelihood of having its own errors one range of values, as is the case in the sine example, but a few simple checks on
because its complexity often rivals the the input values easily put the results into one of the two heuristics.
SUT. “Predictable relationships” are fairly easy to identify—and the nature of the
The other extreme is to have no predictability is what we use to come up with the heuristic. In the sine example,
oracle at all. I’ve reviewed automated
the results predictably increase or decrease between the minima and maxima, and
tests that were proudly created and
run, sending thousands or millions of this is the basis of discovering the simple heuristic.
test values to the SUT—and confirming
30
[Link] Software Testing & Quality Engineering March/April 1999
 Data Source 3 3 Remote Device
• Binary values (Vn)
• Save first value (V1)
• Randomly chosen start (V1)
• Check for same interval
• Randomly chosen interval (I) between sequential values (I)
• Random number of values (m) • Count number of values (n)
• Each sequential value interval • Return V1, Vn, I, n to confirm
more than previous (Vn+1=Vn+I)

FIGURE 4 An invalid sine wave FIGURE 5 A heuristic for data communications verification
with inverted values

again to 360 degrees. The exact value of sine at 34 degrees being modified daily, making it impossible to know in
is hard to predict, but you can easily check that it’s larger advance how many responses there would be to any reason-
than the value at 33 degrees and smaller than the value at able query. However, we knew that old records weren’t sup-
35 degrees. For the values of sine that are easy to predict posed to be dropped from the database, and we knew when
[sin(0) is 0, sin(90 degrees) is 1, sin(180 degrees) is 0, and each test was written. So we divided the results of a search
sin(270 degrees) is –1], exact results can be checked. into two sets: those records that predated the test (and
Between the four values the heuristic applies. were known), and those that came after (and the test could-
This heuristic oracle is very easy to implement com- n’t predict). We checked that the first set was the right size
pared to an alternate version of sine and runs much faster. (that no records had been incorrectly dropped), and that
The number of inputs to try can be chosen based on the specific values appeared in each record. (Since we knew
time allocated to run the test. It will find errors such as about these records, we selected information that was
those shown in Figures 2 and 3. In Figure 2, the predictable unique to the record and not likely to appear in new ones.)
descent from crest to trough is violated. In Figure 3, the This meant the records contained specific expected values.
curve is too large in the vertical direction. Heuristic oracles For the second set, we could only apply weaker
are also good at finding errors such as the discontinuous heuristics to test that the search criteria had been met. In
(incorrect) sine wave in Figure 4. This heuristic approach both cases, we could only check that the returned records
also finds most problems at internal boundary conditions matched (in some way) the search criteria. We couldn’t
and special value cases. check that all matching records had been returned. Even
at the point the test was written, it would have been
impractical to independently check every record in the
Larger Examples databases.
Math functions are not the only place that heuristic ora- Another example of heuristic oracle application
cles are useful. I recall two database applications where occurred where the data integrity over a data communica-
we overcame practical limitations of automated testing tions link was tested with huge amounts of auto-generated,
using heuristic oracles. The first case was with a software pseudo-random, binary data using simple algorithms for
company that produced commercial relational database generation and checking (see Figure 5). We needed to gen-
systems. Large databases were needed, with a staggering erate a vast amount of random traffic and confirm that no
number of transactions. Verification of results from the data had been lost or corrupted. The sending test driver
automated tests meant sifting through huge binary files generated sequences of ascending or descending values
containing complex interconnections, and verifying the with random start values, random lengths, and constant
correctness of all the data values and interconnections. sequential differences chosen at random. The receiving test
That was not going to happen in our lifetimes. driver only needed to compute differences between sequen-
But by applying heuristics to the relationships we were tial values, verify that the differences remained constant,
able to write oracles and automate verification for most of and then send back the start value, end value, increment,
the database results. For example, auto-generated fields and number of values to confirm any transmission.
like Invoice Number correspond with Date/Time of cre-
ation, so when the results of searches are sorted by
Date/Time they should have ascending (or descending)
Choosing
Invoice Numbers. Your Heuristic
At another company the biggest challenge in testing The big trick with this approach is to come up with the
the database was the vast size and dynamic updating of the heuristic to apply in the oracle. Most complex algorithms
data sets. Testing had to be done on the live data because it contain simpler patterns. If you step back and look at the
wasn’t practical to duplicate a reasonable test set from the relationships between the inputs and the results, you
two hundred on-line data bases of 5 to 30GB each. The data often can come up with really simple approximations or
within each record varied from a few thousand characters observations that give you the heuristic. Pictures of the
to several megabytes, making complete record comparison functions, the data, and the SUT may help you visualize
impractical. The data content in the live databases was also the patterns. Patterns may be based on only some of the
31
March/April 1999 Software Testing & Quality Engineering [Link]
 FIGURE 6 A sawtooth graph the FIGURE 7 Graphs (due to rounding
oracle accepts errors) the oracle accepts

input variables or results. There may be more than one Keep in mind that the very nature of a heuristic means
pattern; so look for more than one, and then pick the sim- that it is not exact. The general rules can miss detecting
plest one that will do the job. The simpler the algorithm actual problems. For instance, the heuristic oracle for the
the faster, cheaper, and more reliable the heuristic oracle. sine example would erroneously pass the sawtooth func-
If you can’t see the simple approximation or rule-of- tion in Figure 6. The four exact points are correct, and that
thumb, then you can’t create a heuristic oracle for the function smoothly increases or decreases in the appropri-
function. ate regions—but if verifying the accuracy is critical for all
Some tricks may help. Break the SUT up into pieces. the values, then the heuristic oracle won’t do the job.
Each piece may be based on a range of inputs (or results). However, it’s not likely that a sine function would be
In the sine example, I broke the function into two ranges incorrectly implemented as a sawtooth function. That’s an
for the heuristics: rising results and falling results. The important point. Heuristic oracles work when the failures
mega-databases were verified by splitting the results into they detect are failures that real programmers are likely to
two categories: those known at the time of writing the tests, make. Heuristic oracles don’t work if plausible mistakes
and new results. Then two different heuristic approaches would produce results that still satisfy the predictable rela-
were applied to verify them. tionship behind the oracle. For example, in the case of the
Another trick is to look for other simple relationships sine function, rounding errors might lead to the kind of
between the input variables and results related to those you incorrect graphs shown in Figure 7, but these variances
are testing. For example, the date/time of creation for a would still pass the heuristic oracle’s test.
record may correlate with the record number, and therefore When planning to use a heuristic oracle, try to predict
all records created on a specific date should form a block. what failures it should catch and which it might miss, and
(If there is a gap in the record numbers, the missing record ask if you’re willing to accept that risk. In the sine example
must be absent from the database. It cannot have been cre- in Figure 7, other tests would be required to check for the
ated on any other day.) rounding errors.
You can often divide test results into two groups: what Care must be taken to choose the best method of
we know to expect, and what we can’t predict. In the sine results comparison when you are creating a test environ-
example, there were four values that could be predicted ment architecture and planning automated tests. Oracles
exactly. The rest were verified using a heuristic oracle. are required for verification, but the nature of an oracle
When looking for patterns, consider reordering the depends on several factors—most of which are under the
data. For example, two equivalent sets of elements can be control of the automation architect and test designer. In the
sorted and compared to show they do (or do not) contain range of oracles you have to choose from, heuristic oracles
the same items. provide alternatives to more expensive or impractical True
Blocks of information can often be represented by the Oracles, while providing useful data about characteristics
starting value and count of elements. Variations are possi- of expected results. When you find yourself in situations
ble by using fixed increments between values or using sim- where complete information is unavailable or impractical to
ple patterns for changing increments. acquire, a heuristic oracle can offer you an important
potential method of verification. STQE
When Heuristic Douglas Hoffman has been in the software engineering
Oracles Don’t Work and quality assurance fields for over 25 years and is
If you don’t have a simple pattern to work from, you don’t currently an independent consultant with Software
have the necessary heuristic. GUI contents and navigations Quality Methods, LLC. He is very active professionally,
usually don’t have simple patterns, and heuristic oracles is a member of several professional societies, and has
won’t apply. If your pattern is too complex, then you add been a participant at dozens of software quality and
the risk that the heuristic oracle will introduce errors (and metrics conferences. He has earned a Certificate in Soft-
therefore produce false reports of errors in the SUT). Over- ware Quality Engineering from ASQ and has degrees in
ly complex patterns lead to expensive heuristic oracles that CS, EE, and an MBA. His email address is [Link]-
don’t verify the accuracy of the SUT’s results. If you’re man@[Link].
going to all that expense it might be better to use a True
Oracle.
32
[Link] Software Testing & Quality Engineering March/April 1999