A prototype residual testing tool has been constructed at Purdue by Christina
Pavlopoulou. This tool selectively monitors Java programs for statements
and blocks. Initially, all blocks are monitored, but subsequent to a few
test runs the program can be instrumented again, removing monitoring of
blocks that have already been covered and leaving only the probes needed
to recognize execution of the "residue" of unexecuted code. Since
the high-frequency program paths tend to be executed on almost every program
run, the cost of selective reinstrumentation quickly falls nearly to zero.
The prototype tool instruments Java .class files. In principle this means
that it should work for other programming languages that use Java bytecodes
as an executable or intermediate form, such as the Intermetrics implementation
of Ada 95. Experiments to date have been based on Java code.
The current prototype tool monitors execution of basic blocks, which is equivalent to monitoring statement coverage. Like any test coverage tool, it maintains a cumulative coverage table on disk. The table which is maintained at run-time can be much smaller because it has entries only for the "residue," that is, blocks that have not yet been executed in any test run. The diagram below summarizes the relations among the key data structures. Much more detail is available in the Purdue M.S. thesis of Christina Pavlopoulou, who implemented the tool [PDF][PostScript].
In addition to serving as a "proof of concept"
for residual testing, experiments with the prototype will help shape the
design of more sophisticated monitoring aids that monitor path-oriented
test coverage criteria, such as data flow coverage testing [see also the
ProTaos project at U.C. Irvine]. Low-cost monitoring of path-oriented criteria
poses some additional challenges, since it is entirely possible that a very
low-frequency sub-path is made up entirely of high-frequency blocks. Approaches
under consideration include techniques borrowed from compiler technology,
including transformations used in VLIW compilers and path-profiling techniques
developed by Ball and Larus.