Constraint-based test data generation in the presence of stack-directed pointers

ABSTRACT

Constraint-Based Test data generation (CBT) exploits constraint satisfaction techniques to generate test data able to kill a given mutant or to reach a selected branch in a program. When pointer variables are present in the program, aliasing problems may arise and may lead to the failure of current CBT approaches. In our work, we propose an overall CBT method that exploits the results of an intraprocedural points-to analysis and provides two specific constraint combinators for automatically generating test data able to reach a selected branch. Our approach correctly handles multi-levels stack-directed pointers that are mainly used in real-time control systems. The method has been fully implemented in the test data generation tool INKA and first experiences in applying it to a variety of existing programs tend to show the interest of the approach.

REFERENCES

• 1: 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 ]
• 2: A. Jefferson Offutt , Zhenyi Jin , Jie Pan, The dynamic domain reduction procedure for test data generation, Software—Practice & Experience, v.29 n.2, p.167-193, Feb. 1999 [doi>10.1002/(SICI)1097-024X(199902)29:2<167::AID-SPE225>3.3.CO;2-M ]
• 3: Arnaud Gotlieb , Bernard Botella , Michel Rueher, Automatic test data generation using constraint solving techniques, Proceedings of the 1998 ACM SIGSOFT international symposium on Software testing and analysis, p.53-62, March 02-04, 1998, Clearwater Beach, Florida, United States
• 4: Arnaud Gotlieb , Bernard Botella , Michel Rueher, A CLP Framework for Computing Structural Test Data, Proceedings of the First International Conference on Computational Logic, p.399-413, July 01, 2000
• 5: Meudec, C., "ATGen: automatic test data generation using constraint logic programming and symbolic execution", Software Testing, Verification and Reliability, vol. 11, no. 2, pp. 81--96, June 2001.
• 6: Kim Marriott , Peter J. Stuckey, Introduction to Constraint Logic Programming, MIT Press, Cambridge, MA, 1998
• 7: Axlog Ingenierie and Thales Airborne Systems, INKA--V1 User's Manual, december 2002.
• 8: Christopher Lapkowski , Laurie J. Hendren, Extended SSA Numbering: Introducing SSA Properties to Language with Multi-level Pointers, Proceedings of the 7th International Conference on Compiler Construction, p.128-143, March 28-April 04, 1998
• 9: Thomas J. Ostrand , Elaine J. Weyuker, Data flow-based test adequacy analysis for languages with pointers, Proceedings of the symposium on Testing, analysis, and verification, p.74-86, October 08-10, 1991, Victoria, British Columbia, Canada [doi>10.1145/120807.120814]
• 10: V. Benjamin Livshits , Monica S. Lam, Tracking pointers with path and context sensitivity for bug detection in C programs, Proceedings of the 9th European software engineering conference held jointly with 11th ACM SIGSOFT international symposium on Foundations of software engineering, September 01-05, 2003, Helsinki, Finland
• 11: David W. Binkley , James R. Lyle, Application of the pointer state subgraph to static program slicing, Journal of Systems and Software, v.40 n.1, p.17-27, Jan. 1998 [doi>10.1016/S0164-1212(97)00016-2 ]

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:
Reliability

Keywords:
constraint satisfaction, constraint-based test data generation, stack-directed pointers