Summary Data flow testing creates test requirements as definition‐use (DU) associations, where adefinitionis a program location that assigns a value to a variable and auseis a location where that value is accessed. Data flow testing is expensive, largely because of the number of test requirements. Luckily, many DU‐associations are redundant in the sense that if one test requirement (e.g. node, edge and DU‐association) is covered, other DU‐associations are guaranteed to also be covered. This relationship is calledsubsumption. Thus, testers can save resources by only covering DU‐associations that are not subsumed by other testing requirements. Although this has the potential to significantly decrease the cost of data flow testing, there are roadblocks to its application. Finding data flow subsumptions correctly and efficiently has been an elusive goal; the savings provided by data flow subsumptions and the cost to find them need to be assessed; and the fault detection ability of a reduced set of DU‐associations and the advantages of data flow testing over node and edge coverage need to be verified. This paper presents novel solutions to these problems. We present algorithms that correctly find data flow subsumptions and are asymptotically less costly than previous algorithms. We present empirical data that show that data flow subsumption is effective at reducing the number of DU‐associations to be tested and can be found at scale. Furthermore, we found that using reduced DU‐associations decreased the fault detection ability by less than 2%, and data flow testing adds testing value beyond node and edge coverage.

Data flow testing helps testers design effective tests by requiring the tests to execute sequences of statements from definitions of variables to one or more subsequent uses. These def-use associations are derived from graphs that model software behavior. A "flow graph" that only includes paths that cover defuse associations, and not other control flows, has been defined elsewhere. Although these flow graphs have several advantages over previous graphs, as computed, they omit some valid paths, which are needed to use the graphs to discover subsumption relationships and generate test data. These omissions lead to errors in the results. This paper extends previous solutions by presenting a graph that represents all paths that cover def-use associations. The paper presents empirical data showing that this graph can be generated at reasonable cost and efficiently applied for data flow subsumption discovery.

Data flow testing creates test requirements as definition-use (DU) associations, where a definition is a program location that assigns a value to a variable and a use is a location where that value is accessed. Data flow testing is expensive, largely because of the number of test requirements. Luckily, many DU-associations are redundant in the sense that if one test requirement (e.g., node, edge, DU-association) is covered, other DU-associations are guaranteed to also be covered. This relationship is called subsumption. Thus, testers can save resources by only covering DU-associations that are not subsumed by other testing requirements. Although this has the potential to significantly decrease the cost of data flow testing, finding subsumption among DU-associations is quite difficult. Previous solutions are costly and contain subtle flaws that sometimes lead to incorrect results. We model the data flow testing subsumption as a data flow analysis framework, allowing us to use efficient algorithms that quickly discover data flow subsumption relationships. Experimental data suggest that the framework and algorithm can reduce the cost of data flow testing and will work at scale.