Automated test data generation for programs with procedures

ABSTRACT

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 or branch coverage. The existing methods of test data generation are limited to unit testing and may not efficiently generate test data for programs with procedures. In this paper we present an approach for automated test data generation for programs with procedures. This approach builds on the current theory of execution-oriented test data generation. In this 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 that may be part of some procedures. The existing methods use only control flow information of a program during the search process and may not efficiently generate test data for these types of programs because they are not able to identify statements that affect execution of the selected statement. Our approach uses data dependence analysis to guide the process of test data generation. Data dependence analysis automatically identifies statements (or procedures) that affect the execution of the selected statement and this information is used to guide the search process. The initial experiments have shown that this approach may improve the chances of finding test data.

REFERENCES

• Bir82: 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
• Boy75: 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
• Cla76: L. Clarke, "A system to generate test data and symbolically execute programs," IEEE Transactions on Software Engineering, vol. 2, No. 3, 1976, pp. 215-222.
• DeM87: 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
• DeM91: 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]
• Gil74: P. Gill, W. Murray, Ed., Numerical Methods for Constrained Optimization, New York: Academic, 1974.
• Har89: M. Harrold , M. Soffa, Interprocedual data flow testing, Proceedings of the ACM SIGSOFT '89 third symposium on Software testing, analysis, and verification, p.158-167, December 13-15, 1989, Key West, Florida, United States
• Fer94: R. Ferguson, B. Korel, "The chaining approach for software test data generation," Technical Report, Computer Science Department, Wayne State University, CSC-94-003, 1994.
• How77: W. E. Howden, "Symbolic testing and the DISSECT symbolic evaluation system," IEEE Transactions on Software Engineering, vol. 4, No. 4, 1977, pp. 266-278.
• Kor89: B. Korel, "TESTGEN- A strucUwal test data generation system," 6-th International Conference on Software Testing, Washington, D.C., 1989.
• Kor90a: 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]
• Kor90b: B. Korel, "A dynamic approach of automated test data generation," Conference on Software Maintenance, San Diego, CA, 1990, pp. 311- 317.
• Kor92: B. Korel, "Dynamic method for software test data generation," Journal of Software Testing, Verification, and Reliability, vol. 2, 1992, pp. 203-213.
• Kor95: B. Korel, "TESTGEN - An execution-oriented test data generation system," Technical Report TR-SE-95-01, Department of Computer Science, Illinois Institute of Technology, 1995.
• Las83: J. Laski, B. Korel, "Data flow oriented program testing strategy," iEEE Transactions on Software Engineering, vol. 9, No. 3, 1983, pp. 347-354.
• Muc81: Steven S. Muchnick , Neil D. Jones, Program Flow Analysis: Theory and Application, Prentice Hall Professional Technical Reference, 1981
• Ram76: C. Ramamoorthy, S. Ho, W. Chert, "On the automated generation of program test data," IEEE Transactions on Software Engineering, vol. 2, No. 4, 1976, pp. 293-300.
• Rap85: 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]

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)

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features
          Subjects: Procedures, functions, and subroutines

General Terms:
Design, Experimentation, Theory