The chaining approach for software test data generation

ABSTRACT

Software testing is very labor intensive and expensive and accounts for a significant portion of software system development cost. If the testing process could be automated, the cost of developing software could be significantly reduced. Test data generation in program testing is the process of identifying a set of test data that satisfies a selected testing criterion, such as statement coverage and branch coverage. In this article we present a chaining approach for automated software test data generation which builds on the current theory of execution-oriented test data generation. In the chaining approach, test data are derived based on the actual execution of the program under test. For many programs, the execution of the selected statement may require prior execution of some other statements. The existing methods of test data generation may not efficiently generate test data for these types of programs because they only use control flow information of a program during the search process. The chaining approach uses data dependence analysis to guide the search process, i.e., data dependence analysis automatically identifies statements that affect the execution of the selected statement. The chaining approach uses these statements to form a sequence of statements that is to be executed prior to the execution of the selected statement. The experiments have shown that the chaining approach may significantly improve the chances of finding test data as compared to the existing methods of automated test data generation.

REFERENCES

• 1: ~ALBEI~TS, D. 1976. The economics of software quality assurance. In AFIPS Conference ~Proceedings: 1976 National Computer Conference. Vol. 45. AFIPS Press, 433-442.
• 2: David L Bird , Carlos Urias Munoz, Automatic generation of random self-checking test cases, IBM Systems Journal, v.22 n.3, p.229-245, 1983
• 3: Robert S. Boyer , Bernard Elspas , Karl N. Levitt, SELECT—a formal system for testing and debugging programs by symbolic execution, ACM SIGPLAN Notices, v.10 n.6, p.234-245, June 1975
• 4: ~CLANKS:. L 1976. A system to generate test data and symbolically execute programs. IEEE ~Trans. Softw. Eng. 2. 3, 215-222.
• 5: ~CLARKE, L. 1979. Automatic test data selection techniques. Infotech State of the Art Report ~on Software Testing, Infotech International. Sept.
• 6: Richard A. DeMillo , A. Jefferson Offutt, Constraint-Based Automatic Test Data Generation, IEEE Transactions on Software Engineering, v.17 n.9, p.900-910, September 1991 [doi>10.1109/32.92910]
• 7: Richard A. DeMillo , A. Jefferson Offutt, Experimental results from an automatic test case generator, ACM Transactions on Software Engineering and Methodology (TOSEM), v.2 n.2, p.109-127, April 1993 [doi>10.1145/151257.151258]
• 8: Richard A. DeMillo , W. Michael McCracken , R. J. Martin , John F. Passafiume, Software testing and evaluation, Benjamin-Cummings Publishing Co., Inc., Redwood City, CA, 1987
• 9: Jeanne Ferrante , Karl J. Ottenstein , Joe D. Warren, The program dependence graph and its use in optimization, ACM Transactions on Programming Languages and Systems (TOPLAS), v.9 n.3, p.319-349, July 1987 [doi>10.1145/24039.24041]
• 10: ~GILL,, P. :\xl) MURRAY, W.. Eds. 1974. Numerical Methods /br Constrained Optimization. ~Academic, New York.
• 11: H. Glass , L. Cooper, Sequential Search: A Method for Solving Constrained Optimization Problems, Journal of the ACM (JACM), v.12 n.1, p.71-82, Jan. 1965 [doi>10.1145/321250.321256]
• 12: ~HOWDEN. W, E. 1977. Symbolic testing and the DISSECT symbolic evaluation system. IEEE ~Trans. Noftw. Eng. 4, 4. 266-278.
• 13: ~INCE, D 1987. The automatic generation of test data. Comput. J. 30, 1, 63-69.
• 14: W. H. Jessop , J. R. Kane , S. Roy , J. M. Scanlon, ATLAS-An Automated Software Testing System, Proceedings of the 2nd international conference on Software engineering, p.629-635, October 13-15, 1976, San Francisco, California, United States
• 15: ~KOREL, B. 1989. TESTGEN A structural test data generation system. In the 6th Interna- ~tional ('onj{'rence on Softwore Testing IWashington, D.C.i. USPDI, Washington, D.C,
• 16: B. Korel, Automated Software Test Data Generation, IEEE Transactions on Software Engineering, v.16 n.8, p.870-879, August 1990 [doi>10.1109/32.57624]
• 17: ~KoREI,, B. 1990b. A dynamic approach of automated test data generation. In the Confer- ~enee oil Software Maintenance (San Diego, Cali~). 311-317.
• 18: ~KOREI,, B 1992. Dynamic method for software test data generation. ,}, So/?w. Testing Veri~ ~Rcliab. 2. 4, 203-213.
• 19: ~KOREL, B. 1995. TESTGEN--An execution-oriented test data generation system. Tech. Rep. ~TR-SE-95-01, Dept. of Computer Science, Illinois Inst. of Technology, Chicago.
• 20: B. Korel , J. Laski, Dynamic program slicing, Information Processing Letters, v.29 n.3, p.155-163, October 26, 1988 [doi>10.1016/0020-0190(88)90054-3]
• 21: KOREL, B. AND FERGUSON, R. 1995. Chaining approach of test data generation--Experimen- ~tal results. Tech. Rep. TR-SE-95-02, Dept. of Computer Science, Illinois Inst. of Technology, ~Chicago.
• 22: ~LASgI, J. AND KOREL, B. 1983. Data flow oriented program testing strategy. IEEE Trans. ~Softw. Eng. 9, 3, 347-354.
• 23: Glenford J. Myers, Art of Software Testing, John Wiley & Sons, Inc., New York, NY, 1979
• 24: ~RAMAMOORTHY, C., HO, S., AND CHEN, W. 1976. On the automated generation of program ~test data. IEEE Trans. Softw. Eng. 2, 4, 293-300.
• 25: Sandra Rapps , Elaine J. Weyuker, Selecting software test data using data flow information, IEEE Transactions on Software Engineering, v.11 n.4, p.367-375, April 1985 [doi>10.1109/TSE.1985.232226]
• 26: ~WEISER, M. 1982. Program slicing. IEEE Trans. Softw. Eng. SE-IO, 4, 352-357.

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.5 Testing and Debugging
          Subjects: Testing tools (e.g., data generators, coverage testing)

General Terms:
Experimentation, Measurement, Performance

Keywords:
data dependency, dynamic analysis, heuristics, program execution