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.

Background: Debugging is a key task during the software development cycle. Spectrum-based Fault Localization (SFL) is a promising technique to improve and automate debugging. SFL techniques use control-flow spectra to pinpoint the most suspicious program elements. However, data-flow spectra provide more detailed information about the program execution, which may be useful for fault localization. Aims: We evaluate the effectiveness and efficiency of ten SFL ranking metrics using data-flow spectra. Method: We compare the performance of data- and control-flow spectra for SFL using 163 faults from 5 real-world open source programs, which contain from 468 to 4130 test cases. The data- and control-flow spectra types used in our evaluation are definition-use associations (DUAs) and lines, respectively. Results: Using data-flow spectra, up to 50% more faults are ranked in the top-15 positions compared to control-flow spectra. Also, most SFL ranking metrics present better effectiveness using data-flow to inspect up to the top-40 positions. The execution cost of data-flow spectra is higher than control-flow, taking from 22 seconds to less than 9 minutes. Data-flow has an average overhead of 353% for all programs, while the average overhead for control-flow is of 102%. Conclusions: The results suggest that SFL techniques can benefit from using data-flow spectra to classify faults in better positions, which may lead developers to inspect less code to find bugs. The execution cost to gather data-flow is higher compared to control-flow, but it is not prohibitive. Moreover, data-flow spectra also provide information about suspicious variables for fault localization, which may improve the developers' performance using SFL.

Data-flow (DF) testing was introduced more than thirty years ago aiming at extensively evaluating a program structure. It requires tests that traverse a path in which the definition of a variable and its subsequent use, i.e., a definition-use association (dua), is exercised. While control-flow testing tools have being able to tackle big systems-large and long running programs, DF testing tools have failed to do so. This situation is in part due to the costs associated with tracking duas at run-time. Recently, an algorithm, called Bitwise Algorithm (BA), which uses bit vectors and bitwise operations for tracking intra-procedural duas at run-time, was proposed. This paper presents the implementation of BA for programs compiled into bytecodes. Previous approaches were able to deal with small to medium size programs with high penalties in terms of execution and memory. Our experimental results show that by using BA we are able to tackle large systems with more than 200 KLOCs and 300K required duas. Furthermore, for several programs the execution penalty was comparable with that imposed by a popular control-flow testing tool.