Mutation-based software testing using program schemata

ABSTRACT

Mutation analysis is a powerful technique for assessing the quality of test data used in unit testing software. Unfortunately, current automated mutation analysis systems suffer from severe performance problems. In this paper the principles of mutation analysis are reviewed, current automation approaches are described, and a new method of performing mutation analysis is outlined. Performance improvements of over 300% are reported and other advantages of this new method are highlighted.

REFERENCES

• 1: Barton P. Miller , Louis Fredriksen , Bryan So, An empirical study of the reliability of UNIX utilities, Communications of the ACM, v.33 n.12, p.32-44, Dec. 1990 [doi>10.1145/96267.96279]
• 2: R. A. DeMillo, R. J. Lipton, and F. G. Sayward, "Hints on Test Data Selection: Help for the Practicing Programmer," Computer, vol. 11, pp. 34-41, Apr. 1978.
• 3: T. A. Budd, "Mutation Analysis: Ideas, Exampies, Problems and Prospects," in Proceedings of the Summer School on Computer Program Testing (B. Chandrasekaran and S. Radicchi, eds.), Computer Program Testing, (SO- GESTA, Urbino, Italy), pp. 129-148, North- Holland Publishing Company, Amsterdam, Netherlands, June 29-July 3 1981.
• 4: J. E. Burns, "Stability of Test Data from Program Mutation," in Digest for the Workshop on Software Testing and Test Documentation, (Ft. Lauderdale, FL), pp. 324-332, IEEE Computer Society Press, Dec. 18-20 1978.
• 5: Allen Troy Acree, Jr., On mutation, 1980
• 6: Timothy Alan Budd, Mutation analysis of program test data, 1980
• 7: R. A. DeMillo and A. P. Mathur, "On the Use of Software Artifacts to Evaluate the Effectiveness of Mutation Analysis for Detecting Errors in Production Software," Technical Report SERC-TR-92-P, Software Engineering Research Center, Purdue University, West Lafayette, IN, Feb. 9 1991.
• 8: M. R. Girgis and M. R. Woodward, "An Experimental Comparison of the Error Exposing Ability of Program Testing Criteria," in Proceedings of the Workshop on Software Testing, (Banff, Alberta, Canada), pp. 64-73, IEEE Computer Society Press, July 1986.
• 9: L. J. Morell, A Theory of Fault-Based Testing, IEEE Transactions on Software Engineering, v.16 n.8, p.844-857, August 1990 [doi>10.1109/32.57623]
• 10: E. J. Weyuker, "On Testing Non-testable Programs," The Computer Journal, vol. 25, pp. 465-470, Nov. 1982.
• 11: W. M. Craft, "Detecting Equivalent Mutants Using Compiler Optimization Techniques," Technical Report 91-128, Computer Science Department, Clemson University, Clemson, SC, Sept. 1989. Master's Paper.
• 12: B. Choi and A. P. Mathur, "Use of Fifth Generation Computers for High Performance Reliable Software Testing (Final Report)," Technical Report SERC-TR-72-P, Software Engineering Research Center, Purdue University, West Lafayette, IN, Apr. 10 1990.
• 13: T. A. Budd, R. J. Lipton, F. G. Sayward, and R. A. DeMillo, "The Design of a Prototype Mutation System for Program Testing," in Proceedings of the National Computer Conference, (Anaheim, CA), pp. 623-627, The Association for Computing Machinery, AFIPS Press, Montvale, NJ, June 5-8 1978. Vol. 47.
• 14: K. N. King , A. Jefferson Offutt, A Fortran language system for mutation-based software testing, Software—Practice & Experience, v.21 n.7, p.685-718, July 1991 [doi>10.1002/spe.4380210704]
• 15: Edward W. Krauser , Aditya P. Mathur , Vernon J. Rego, High Performance Software Testing on SIMD Machines, IEEE Transactions on Software Engineering, v.17 n.5, p.403-423, May 1991 [doi>10.1109/32.90444]
• 16: M. Sahinoglu and E. H. Spafford, "Sequential Statistical Procedures for Approving Test Sets Using Mutation-Based Software Testing," Technical Report SERC-TR-79-P, Software Engineering Research Center, Purdue University, West Lafayette, IN, Sept. 3 1990.
• 17: W. Hsu, M. Sahinoglu, and E. H. Spafford, "An Experimental Approach to Statistical Mutation-Based Testing," Technical Report SERC-TR-63-P, Software Engineering Research Center, Purdue University, West Lafayette, IN, Apr. 10 1990.
• 18: A. P. Mathur and E. W. Krauser, "Mutant Unification for Improved Vectorization," Technical Report SERC-TR-14-P, Software Engineering Research Center, Purdue University, West Lafayette, IN, Apr. 25 1988.
• 19: B. Choi, A. P. Mathur, and B. Pattison, "Architecture of PMothra: A Tool for Mutation Baaed Testing on the Hypercube," Technical Report SERC-TR-45-P, Software Engineering Research Center, Purdue University, West Lafayette, IN, June 1 1989.
• 20: S. V. Fichter, "HyperMothra: A Parallel Interpreter for the Mothra Mutation Testing System," Technical Report 92-100, Computer Science Department, Clemson University, Clemson, SC, Dec. 1991. Master's Paper.
• 21: A. J. Offutt, VI , K. N. King, A Fortran 77 interpreter for mutation analysis, Papers of the Symposium on Interpreters and interpretive techniques, p.177-188, June 24-26, 1987, St. Paul, Minnesota, United States
• 22: R. A. DeMillo, E. W. Krauser, and A. P. Mathur, "An Approach to Compiler-Integrated Soi tware Testing," Technical Report SERC- TR-71-P, Software Engineering Research Center, Purdue University, West Lafayette, IN, Apr. 1990.
• 23: R. A. DeMillo, E. W. Krauser, and A. P. Mathur, "Compiler-Integrated Program Mutation," in Proceedings of the Fifteenth Annual International Computer Soft~nare and Applications Conference (COMPSAC), (Tokyo, Japan), pp. 351-356, IEEE Computer Society Press, Sept. 11-13 1991.
• 24: O. Baruch , S. Katz, Partially interpreted schemas for CSP programming, Science of Computer Programming, v.10 n.1, p.1-18, Feb. 1988 [doi>10.1016/0167-6423(88)90013-5]
• 25: A. J. Offutt and S. D. Lee, "IMSCU Programmer's Reference Manual," Technical Report 91- 121, Computer Science Department, Clemaon University, Clemson, SC, 1991.

INDEX TERMS

Keywords:
Fault-based testing, mutation analysis, program schemata, software testing