|  | |||||||||
Using Data Flow Analysis for Testing
Mary Jean Harrold
Department of Computer Science
Clemson University
Clemson, SC 29634-1906
Abstract
Data flow analysis that computes the relationships among the data objects in a program has many applications in program testing. In this paper, we overview static data flow testing, dynamic data flow testing and program slicing, all of which require some type of data flow analysis. For each type of testing, we give background and definitions, present examples, discuss applications of that type of testing and examine some existing tools.
1 Introduction
Data flow analysis that computes the relationships among the data objects in a program is useful in program testing. Fosdick and Osterweil[7] used data flow information to identify data flow anomalies, such as uses of a variable before any value is assigned to the variable. Their techniques require no program execution to detect these anomalies and thus, are referred to as static data flow testing. Other researchers[11, 20, 24, 25, 29] used data flow information to guide the selection of test cases for program execution. This method of testing is referred to as dynamic data flow testing since the program is executed with the test cases. Data flow information is also used to compute a program slice, which is a set of statements in a program that may affect a particular statement. Weiser[31] first defined a backward static slice that could be used for debugging. However, slicing techniques, such as forward slicing and dynamic slicing, have subsequently been used for testing.
In this paper, we overview static data flow testing, dynamic data flow testing and program slicing. We present an example that is used throughout the paper to illustrate each of these concepts. We omit many of the details and much of the formality but refer the reader to the literature for further study.
In the next section, we present general definitions that provide background for the rest of the paper and we introduce our example. Section 3 briefly discusses static data flow testing. In Section 4, we present dynamic data flow testing by concentrating on the Rapps and Weyuker[29] family of data flow testing criteria. Several types of slicing are presented in Section 5. In each of Sections 3, 4 and 5 we present an overview of the concepts and then discuss extensions. We overview some existing tools in Section 6 and give our conclusions in Section 7.
2 Background
This section presents basic definitions concerning data flow analysis, control flow graphs and program dependence graphs that are used for testing and are referenced throughout the rest of the paper. For a formal treatment of these concepts, see Aho, Sethi and Ullman[2], Rapps and Weyuker[29], Ferrante, Ottenstein and Warren[6], and Beizer[3]. For our discussion, we use program to refer to the software under test, which may be a monolithic program or a single procedure.
Control Flow Graph
To perform data flow analysis, a program is decomposed into basic blocks. Each basic block is a sequence of consecutive statments in which flow of control enters at the beginning and leaves at the end without halt or possibility of branching except at the end[2]. When data flow analysis is performed on a