Better predicate testing

ABSTRACT

Mutation testing is widely recognized as being extremely powerful, but is considered difficult to automate enough for practical use. This paper theoretically addresses two possible reasons for this: the generation of redundant mutants and the lack of integration of mutation analysis with other test criteria. By addressing these two issues, this paper brings an important mutation operator, relational-operator-replacement (ROR), closer to practical use. First, we develop fault hierarchies for the six relational operators, each of which generates seven mutants per clause. These hierarchies show that, for any given clause, only three mutants are necessary. This theoretical result can be integrated easily into mutation analysis tools, thereby eliminating generation of 57% of the ROR mutants. Second, we show how to bring the power of the ROR operator to the widely used Multiple Condition-Decision Coverage (MCDC) test criterion. This theoretical result includes an algorithm to transform any MCDC-adequate test set into a test set that also satisfies RORG, a new version of ROR appropriate for the MCDC context. The transformation does not use traditional mutation analysis, so can easily be integrated into existing MCDC tools and processes.

References

1. P. Ammann and J. Offutt. Introduction to Software Testing. Cambridge University Press, Cambridge, UK, 2008. ISBN 0-52188-038-1.
2. P. Ammann, J. Offutt, and H. Huang. Coverage criteria for logical expressions. In Proceedings of the 14th International Symposium on Software Reliability Engineering, pages 99--107, Denver, CO, November 2003. IEEE Computer Society Press.
3. T. Y. Chen, M. F. Lau, and Y. T. Yu. MUMCUT: A fault-based strategy for testing boolean specifications. In APSEC '99: Proceedings of the Sixth Asia Pacific Software Engineering Conference, pages 606--613, Takamatsu, Japan, 1999. IEEE Computer Society Press.
4. J. Chilenski and L. A. Richey. Definition for a masking form of modified condition decision coverage (MCDC). Technical report, Boeing, Seattle, WA, 1997. http://www.boeing.com/nosearch/mcdc/.
5. J. J. Chilenski and S. P. Miller. Applicability of modified condition/decision coverage to software testing. Software Engineering Journal, 9(5):193--200, September 1994.
6. M. E. Delamaro and J. C. Maldonado. Proteum-A tool for the assessment of test adequacy for C programs. In Proceedings of the Conference on Performability in Computing Systems (PCS 96), pages 79--95, New Brunswick, NJ, July 1996.
7. R. A. DeMillo, R. J. Lipton, and F. G. Sayward. Hints on test data selection: Help for the practicing programmer. IEEE Computer, 11(4):34--41, April 1978.
8. R. A. DeMillo and J. Offutt. Constraint-based automatic test data generation. IEEE Transactions on Software Engineering, 17(9):900--910, September 1991.
9. A. Gargantini and G. Fraser. Generating minimal fault detecting test suites for boolean expressions. In AMOST 2010 - 6th Workshop on Advances in Model Based Testing, pages 37--45, Paris, France, April 2010.
10. J. M. Hanks. Testing COBOL programs by mutation: Volume I-introduction to the CMS.1 system, volume II - CMS.1 system documentation. Technical report GIT-ICS-80/04, Georgia Institute of Technology, February 1980.
11. Y. Jia and M. Harman. Constructing subtle faults using higher order mutation testing. In 2008 Eighth IEEE International Working Conference on Source Code Analysis and Manipulation, pages 249--258, Beijing, September 2008.
12. Y. Jia and M. Harman. An analysis and survey of the development of mutation testing. IEEE Transactions of Software Engineering, To appear, 2010. DOI: http://doi.ieeecomputersociety.org/10.1109/TSE.2010.62.
13. G. Kaminski and P. Ammann. Using a fault hierarchy to improve the efficiency of DNF logic mutation testing. In 2nd IEEE International Conference on Software Testing, Verification and Validation (ICST 2009), pages 386--395, Denver, CO, April 2009.
14. G. Kaminski and P. Ammann. Using logic criterion feasibility to reduce test set size while guaranteeing fault detection. In 2nd IEEE International Conference on Software Testing, Verification and Validation (ICST 2009), pages 356--365, Denver, CO, April 2009.
15. G. Kaminski and P. Ammann. Applications of optimization to logic testing. In CSTVA 2010 - 2nd Workshop on Constraints in Software Testing, Verification and Analysis, pages 331--336, Paris, France, April 2010.
16. G. Kaminski and P. Ammann. Reducing logic test set size while preserving fault detection. Journal of Software Testing, Verification and Reliability, Wiley, to appear. Special issue from the 2009 International Conference on Software Testing, Verification and Validation.
17. G. Kaminski, G. Williams, and P. Ammann. Reconciling perspectives of logic testing for software. Journal of Software Testing, Verification and Reliability, Wiley, 18(3):149--188, September 2008.
18. S. Kim, J. A. Clark, and J. A. McDermid. Investigating the effectiveness of object-oriented strategies with the mutation method. In Proceedings of Mutation 2000: Mutation Testing in the Twentieth and the Twenty First Centuries, pages 4--100, San Jose, CA, October 2000. Wiley's Software Testing, Verification, and Reliability, December 2001.
19. K. N. King and J. Offutt. A Fortran language system for mutation-based software testing. Software-Practice and Experience, 21(7):685--718, July 1991.
20. M. F. Lau and Y. T. Yu. An extended fault class hierarchy for specification-based testing. ACM Transactions on Software Engineering Methodology, 14(3):247--276, July 2005.
21. N. Li, U. Praphamontripong, and J. Offutt. An experimental comparison of four unit test criteria: Mutation, edge-pair, all-uses and prime path coverage. In Fifth Workshop on Mutation Analysis (Mutation 2009), Denver CO, April 2009.
22. Y.-S. Ma, J. Offutt, and Y.-R. Kwon. MuJava : An automated class mutation system. Software Testing, Verification, and Reliability, Wiley, 15(2):97--133, June 2005.
23. J. Offutt, A. Lee, G. Rothermel, R. Untch, and C. Zapf. An experimental determination of sufficient mutation operators. ACM Transactions on Software Engineering Methodology, 5(2):99--118, April 1996.
24. J. Offutt and S. D. Lee. An empirical evaluation of weak mutation. IEEE Transactions on Software Engineering, 20(5):337--344, May 1994.
25. J. Offutt, J. Payne, and J. M. Voas. Mutation operators for Ada. Technical report ISSE-TR-96-09, Department of Information and Software Engineering, George Mason University, Fairfax VA, March 1996. http://www.cs.gmu.edu/tr~admin/.
26. RTCA-DO-178B. Software considerations in airborne systems and equipment certification, December 1992.
27. C. Sun, Y. Dong, R. Lai, K. Y. Sim, and T. Y. Chen. Analyzing and extending MUMCUT for fault-based testing of general boolean expressions. In The Sixth IEEE International Conference on Computer and Information Technology, pages 184--189, Seoul, Korea, September 2006.

Index Terms

• Software and its engineering

  • Software creation and management

    • Software verification and validation

      • Software defect analysis

        • Software testing and debugging