Residual Coverage Monitoring for Java Programs


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.

Contact: Michal Young