Dataflow testing, a form of white-box (clear-box) testing based on dataflow analysis, has been shown in several empirical studies to be more effective at revealing error than other, structure-based testing criteria [2,8]. Several forms of dataflow testing exist, among them the all-uses criterion. All-uses dataflow analysis for testing purposes is based on the computation of def-use pairs:

The key to all-uses dataflow testing is the accurate computation of def-use pairs. Intraprocedural dataflow analysis is relatively easily performed; but in order to obtain an accurate set of def-use pairs, interprocedural interactions and aliasing effects must also be taken into account. [6,7]

Barriers exist to the acceptance of dataflow testing in commercial settings. Foremost is that dataflow testing generates larger test sets than most other criteria. This is especially true when one takes into consideration the effect of aliases. An alias exists in a program any time two (or more) variables reference the same memory location [1]. In the presence of pointers, alias analysis has been shown to be an NP-complete problem [10,11]. Hence any algorithm to accurately compute def-use pairs must be an estimation algorithm. Given that the estimation is to be as accurate as possible, underestimation of def-use pairs is unacceptable. Thus alias analysis algorithms must be "safe" in the sense that they capture all existing aliases, and possibly overestimate the number of aliases actually present in a program.

So, in order for more rigorous testing methods to gain acceptance, ways must be found to decrease test suite size while not reducing the ability of a test suite to reveal error [4]. Several groups of researchers have studied the test suite minimization problem [5,12,14-17]. However, the results of these studies have been somewhat contradictory [14-17], have focussed on other testing criteria [12] or on regression testing [5]. Currently, researchers in the NUCAR lab are studying ways of pruning test sets in more effectively so that minimization can occur without any correspondent decrease in error detection effectiveness.

Test set pruning can occur in several ways. One method is to decrease the number of def-use pairs that exist in a program, thereby (presumably) decreasing the number of test cases needed to obtain full coverage. A second technique is to eliminate redundant test cases (i.e. test cases that exercise the same def-use pairs). However, in cases of hard-to-detect errors, eliminating a test case that is redundant on the basis of coverage may cause the result in removing the one case capable of revealing that hard-to-detect error. [14,15] Therefore, more sophisticated pruning algorithms are called for.

[1] Aho, Alfred, Sethi, Ravi and Ullman, Jeffrey. Compilers, Principles, Techniques, and Tools. Addison-Wesley, 1986.

[2] Frankl, Phyllis and Weiss, Stuart."An Experimental Comparison of the Effectiveness of Branch Testing and Data Flow Testing" in IEEE Transactions on Software Engineering, 19(8), August, 1993

[3] Gabbay, Freddy and Mendelson, Avi. "Using Value Prediction to Increase the Power of Speculative Execution" in ACM Transactions on Computer Systems, 16(3), March, 1998.

[4] Harrold, Mary Jean. "Testing - A Roadmap" in Future of Software Engineering: 22nd International Conference on Software Engineering, June 2000.

[5] Harrold, Mary Jean, Gupta, Rajiv, and Soffa, Mary Lou. "A Methodology for Controlling the Size of a Test Suite" in ACM Transactions on Software Engineering, 2(3), March, 1993

[6] Harrold, Mary Jean and Soffa, Mary Lou. "Computation of Interprocedural Definition and Use Dependencies" in Proceedings of the IEEE Computer Society 1990 International Conference on Computer Languages, Mary, 1990.

[7] Harrold, Mary Jean and Soffa, Mary Lou. "Efficient Computation of Interprocedural Definition-Use Chains" in ACM Transactions on Programming Languages and Systems, 16(2). March, 1994.

[8] Hutchins, Monica, Foster, Herb, Goradia, Tarak, and Ostrand, Thomas. "Experiments on the Effectiveness of Dataflow- and Controlflow-Based Test Adequacy Criteria" in Proceedings of the 16th International Conference on Software Testing, May, 1994

[9] Lipasti, Mikko, Wilkerson, Christopher and Shen, John P. "Value Locality and Load Value Prediction" in Proceedings of the 7th International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS), October 1996.

[10] Pande, Hemant, Landi, William, and Ryder, Barbara. "Interprocedural Reaching Definitions in the Presence of Pointers". Rutgers University Laboratory of Computer Science Research Technical Report LCSR-TR-193, October, 1992

[11] Pande, Hemant, Landi, William, and Ryder, Barbara. "Interprocedural Def-Use Associations for C Systems with Single-Level Pointers" in IEEE Transactions on Software Engineering, 20(5), May, 1994.

[12] Offutt, A. Jefferson, et. al, 1995

[13] Rapps, Sandra and Weyuker, Elaine. "Selecting Software Test Data using Data Flow Information" in IEEE Transactions on Software Engineering, 11(4), April, 1985.

[14] Rothermel, Gregg, Harrold, Mary Jean, Ostrin, Jeffrey, and Hong, Christie. "An Empirical Study of the Effects of Minimization on the Fault Detection Capabilities of Test Suites" in Proceedings of the International Conference on Software Maintenance (ICSM), November, 1998.

[15] Rothermel, Gregg, Harrold, Mary Jean, von Ronne, Jeffrey, Hong, Christie, and Ostrin, Jeffrey. "Experiments to Assess the Cost-Benefits of Test-Suite Reduction", Georgia Institute of Technology College of Computing Technical Report TR-GIT-99-29, December, 1999.

[16] Wong, W. Eric, Horgan, Joseph, London,Saul and Mathur, Aditya. "Effect of Test Set Minimization on Fault Detection Effectiveness" in Software - Practice and Experience, 28(4), April, 1998.

[17] Wong, W. Eric, Horgan, Joseph, Mathur, Aditya, and Pasquini, Alberto. "Test Set Size Minimization and Fault Detection Effectiveness: A Case Study in a Space Application" in Journal of Software and Systems, 48(1999) October, 1999.