page 1  (16 pages)
2to next section

Implementing an Interprocedural Dataflow Tester

using Abstract Execution?

John Lloyd and Mary Jean Harrold
Department of Computer Science, Clemson University, Clemson, SC 29634-1906, U.S.A.

July 30, 1995

FATE is a system that accepts a C program P , and builds an interprocedural dataflow tester that assists the user in measuring dataflow coverage for a test set T . FATE identifies both intraprocedural and interprocedural definition-use pairs that are satisfied by a test, and accounts for aliasing due to reference parameters and single-level pointers. FATE consists of two major components. The first component of FATE is an abstract execution tool that produces an instrumented version of P , and a dataflow tester for P . When the instrumented version of P is executed, it produces a small trace of the significant events that occurred during P 's execution with some test t in T . The dataflow tester reads the significant events file and determines the definition-use pairs satisfied by t. The second component of FATE is a user interface that controls the environment for the dataflow testing. The user interface allows the user to run the abstract execution tool, execute the instrumented version of P and the dataflow tester for P for each test in T , and view the satisfied and unsatisfied definitions-use pairs. The user interface communicates with the instrumented version and the dataflow tester using either Parallel Virtual Machine (PVM) or sockets. Users can provide additional tests to FATE until the desired coverage is achieved. The main benefits of FATE over existing systems are that FATE works on more than one procedure at a time and FATE produces small trace files.
KEY WORDS: Interprocedural dataflow testing Abstract execution Aliasing Dataflow analysis


Testing is used during software development to reveal errors in the software and increase confidence in the correctness of the software. Due to the cost of software maintenance and the possible catastrophic results of software failure, developing an effective test suite is a critical task in software development. There are two major categories of techniques for developing test suites [1]: black box techniques, which select a test suite without using a program's code, and white box techniques, which use a program's code to develop tests. One white box approach is dataflow testing, which is a family of coverage criteria that require test suites that force values of assignments (definitions) to be used (uses) during a program's execution [2, 3, 4]. Dataflow analysis techniques[5] compute these definition-use pairs in the program, and the definition-use pairs are used to guide the selection of a test suite. Although dataflow testing was originally developed for unit testing of single procedures, it has been extended for use in interprocedural testing [6]. Experiments performed to compare the effectiveness of dataflow testing to other white box approaches suggest that dataflow testing is superior to techniques based only on the control flow in the program [7].

Several dataflow testing systems have been developed and used for experimentation. ASSET [8] is a dataflow tester for single Pascal procedures. Combat [9] and ATAC [10] are dataflow testing systems that handle single C procedures. However, none of these dataflow testers performs interprocedural dataflow ?This work was partially supported by grants from icrosoft, Inc. and Data General orp. and by S under Grants -9109531 and -9357811 to lemson niversity.