Mutants as Patches: Towards a formal approach to Mutation Testing

• Autorzy: Lewowski Tomasz , Madeyski Lech

Identyfikatory

DOI

10.2478/fcds-2019-0019

• Języki publikacji: EN

Abstrakty

EN

Background: Mutation testing is a widely explored technique used to evaluate the quality of software tests, but little attention has been given to its mathematical foundations. Aim: We provide a formal description of the core concepts in mutation testing, relations between them and conclusions that can be drawn from the presented model. Method: We introduce concepts of mutant space and patch space, and refer to patch merging procedure from the patch theory. We explicitly present constraints, such as location-dependence, that affect mutation operators. We also present a way to use introduced formalism with traditional operators proposed in other papers. Results: The proposed formalism allows to describe interactions between separate mutations using well-known abstract algebra notation. Conclusion: The presented formalism may substantially decrease the number of tested weak mutants and increase the number of valuable ones, while giving tools to partially address the problem of equivalent mutants, particularly for higher-order mutation testing. However, additional empirical evaluation is still needed.

Słowa kluczowe

EN

mutation testing; fault-based testing; patches; equivalent mutants

• Wydawca: Wydawnictwo Politechniki Poznańskiej
• Czasopismo: Foundations of Computing and Decision Sciences
• Rocznik: 2019
• Tom: Vol. 44, No. 4
• Strony: 379--405
• Opis fizyczny: Bibliogr. 53 poz.

Twórcy

autor

Lewowski Tomasz

• Faculty of Computer Science and Management, Wroclaw University of Science and Technology, Wybrzeze Wyspianskiego 27, 50370 Wroclaw

autor

Madeyski Lech

• Faculty of Computer Science and Management, Wroclaw University of Science and Technology, Wybrzeze Wyspianskiego 27, 50370 Wroclaw

Bibliografia

• [1] Unified Diff Format. https://www.gnu.org/software/diffutils/manual/ html_node/Unified-Format.html. Accessed: 2019-06-21.
• [2] Angiuli C., Morehouse E., Licata D.R., and Harper R. Homotopical patch theory. SIGPLAN Not., 49(9):243-256, Aug. 2014.
• [3] Arkhangel’skii A. and Pontryagin L., editors. General topology I: basic concepts and constructions dimension theory. Springer, 1990.
• [4] Baker R.J. and Habli I. An empirical evaluation of mutation testing for improving the test quality of safety-critical software. IEEE Transactions on Software Engineering, 39(6):787-805, 2013.
• [5] Belli F. and Beyazit M. A formal framework for mutation testing. In Proceedings of the 4th International Conference on Secure Software Integration and Reliability Improvement (SSIRI’2010), pages 121-130, Singapore, Singapore, June 2010.
• [6] Bishop D.M. Group theory and chemistry. Courier Corporation, 1993.
• [7] Calcagno C., Distefano D., Dubreil J., Gabi D., Hooimeijer P., Luca M., O’Hearn P., Papakonstantinou I., Purbrick J., and Rodriguez D. Moving fast with software verification. In Havelund K., Holzmann G., and Joshi R., editors, NASA Formal Methods, pages 3-11, Cham, 2015. Springer International Publishing.
• [8] de Oliveira A.A.L., Camilo-Junior C.G., and Vincenzi A.M.R. A coevolutionary algorithm to automatic test case selection and mutant in mutation testing. In 2013 IEEE Congress on Evolutionary Computation, pages 829-836, Cancun, Mexico, June 2013.
• [9] Delamaro M.E., Offutt J., and Ammann P. Designing deletion mutation operators. In 2014 IEEE Seventh International Conference on Software Testing, Verification and Validation, pages 11-20, Cleveland, OH, USA, March 2014.
• [10] Delgado-Pérez P., Medina-Bulo I., Dominguez-Jimenez J.J., García-Domínguez A., and Palomo-Lozano F. Class mutation operators for c++ object- oriented systems. annals of telecommunications - annales des telecommunications, 70(3):137-148, Apr 2015.
• [11] DeMillo R., Lipton R.J., and Sayward F. Program mutation: A new approach to program testing. Infotech State of the Art Report, Software Testing, 2:107-126, 1979.
• [12] DeMillo R.A., Lipton R.J., and Sayward F.G. Hints on Test Data Selection: Help for the Practicing Programmer. IEEE Computer, 11(4):34-41, 1978.
• [13] Deng L., Offutt J., and Li N. Empirical evaluation of the statement deletion mutation operator. In 2013 IEEE Sixth International Conference on Software Testing, Verification and Validation, pages 84-93, Luxembourg, Luxembourg, March 2013.
• [14] Estero-Botaro A., Palomo-Lozano F., and Medina-Bulo I. Mutation operators for WS-BPEL 2.0. In 21th International Conference on Software & Systems Engineering and their Applications, 2008.
• [15] Findler R.B. and Felleisen M. Contracts for Higher-order Functions. SIGPLAN Not., 37(9):48-59, Sept. 2002.
• [16] Gligoric M., Jagannath V., and Marinov D. MuTMuT: Efficient exploration for mutation testing of multithreaded code. In 2010 Third International Conference on Software Testing, Verification and Validation (ICST), pages 55-64. IEEE, 2010.
• [17] Hamlet R.G. Testing Programs with the Aid of a Compiler. IEEE Transactions on Software Engineering, 3(4):279-290, 1977.
• [18] Harman M., Jia Y., and Langdon W.B. A Manifesto for Higher Order Mutation Testing. In Proceedings of the 2010 Third International Conference on Software Testing, Verification, and Validation Workshops, ICSTW ’10, pages 80-89, Paris, France, 2010. IEEE Computer Society.
• [19] Hu J., Li N., and Offutt J. An analysis of oo mutation operators. In 2011 IEEE Fourth International Conference on Software Testing, Verification and Validation Workshops, pages 334-341, March 2011.
• [20] Jacobson J. A formalization of Darcs patch theory using inverse semigroups. ftp://ftp.math.ucla.edu/pub/camreport/cam09-83.pdf, 2009. Accessed: 2018-06-20.
• [21] Jia Y. and Harman M. Higher Order Mutation Testing. Information and Software Technology, 51(10):1379 - 1393, 2009. Source Code Analysis and Manipulation, SCAM 2008.
• [22] Johann P. and Ghani N. Foundations for Structured Programming with GADTs. SIGPLAN Not., 43(1):297-308, Jan. 2008.
• [23] Johnson S.C. Lint, a C program checker. Technical report, Bell Laboratories, 1978.
• [24] Just R., Ernst M.D., and Fraser G. Using State Infection Conditions to Detect Equivalent Mutants and Speed up Mutation Analysis. CoRR, abs/1303.2784, 2013.
• [25] Kim S., Clark J., and McDermid J. The rigorous generation of Java mutation operators using HAZOP. In Proceedings of the 12th International Conference on Software & Systems Engineering and their Applications (ICSSEA’99), 1999.
• [26] Kintis M. and Malevris N. Identifying more equivalent mutants via code similarity. In Proceedings of the 20th Asia-Pacific Software Engineering Conference (APSEC’2013), volume 1, pages 180-188. IEEE, 2013.
• [27] Kostrikin A. Introduction into Algebra. Nauka, Moscow, 1977.
• [28] Larus J.R. Whole program paths. SIGPLAN Not., 34(5):259-269, May 1999.
• [29] Lidl R. and Pilz G. Applied abstract algebra. Springer Science & Business Media, 2012.
• [30] Lyubarskii G.Y. The application of group theory in physics. Elsevier, 2013.
• [31] Ma Y.-S., Kwon Y.-R., and Offutt J. Inter-class mutation operators for java. In Proceedings of the 13th International Symposium on Software Reliability Engineering, (ISSRE’2002), pages 352-363, Annapolis, MD, USA, USA, 2002. IEEE.
• [32] Madeyski L. Impact of pair programming on thoroughness and fault detection effectiveness of unit test suites. Software Process: Improvement and Practice, 13(3):281-295, 2008.
• [33] Madeyski L., Orzeszyna W., Torkar R., and Józala M. Overcoming the Equivalent Mutant Problem: A Systematic Literature Review and a Comparative Experiment of Second Order Mutation. IEEE Transactions on Software Engineering, 40(1):23-42, 1 2014.
• [34] Madeyski L. and Radyk N. Judy-a mutation testing tool for Java. IET Software, 4(1):32-42, 2010.
• [35] Meyers S. and Lejter M. Automatic detection of c++programming errors: Initial thoughts on a lint++. Technical report, Brown University, Providence, RI, USA, 1991.
• [36] Mimram S. and Giusto C.D. A categorical theory of patches. CoRR, abs/1311.3903, 2013.
• [37] Morell L. A theory of fault-based testing. IEEE Transactions on Software Engineering, 16(8):844-857, Aug 1990.
• [38] Morell L.J. A Theory of Error-based Testing. PhD thesis, University of Maryland at College Park, College Park, MD, USA, 1984.
• [39] Navarro G. A guided tour to approximate string matching. ACM computing surveys (CSUR), 33(1):31-88, 2001.
• [40] Nguyen Q.V. and Madeyski L. Problems of mutation testing and higher order mutation testing. In van Do T., Thi H.A.L., and Nguyen N.T., editors, Advanced Computational Methods for Knowledge Engineering, pages 157-172. Springer International Publishing, 2014.
• [41] Nguyen Q.V. and Madeyski L. Searching for Strongly Subsuming Higher Order Mutants by Applying Multiobjective Optimization Algorithm. In Le Thi H.A., Nguyen N.T., and Do T.V., editors, Advanced Computational Methods for Knowledge Engineering, volume 358 of Advances in Intelligent Systems and Computing, pages 391-402. Springer International Publishing, 2015.
• [42] Offutt A.J., Lee A., Rothermel G., Untch R.H., and Zapf C. An experimental determination of sufficient mutant operators. ACM Transactions on Software Engineering and Methodology (TOSEM), 5(2):99-118, 1996.
• [43] Offutt A.J. and Pan J. Automatically detecting equivalent mutants and infeasible paths. Software Testing, Verification and Reliability, 7(3):165-192, 1997.
• [44] Praphamontripong U. and Offutt J. Applying mutation testing to web applications. In Proceedings of the 3rd International Conference on Software Testing, Verification, and Validation Workshops (ICSTW’2010), pages 132-141, Paris, France, 2010. IEEE.
• [45] Runeson P. A survey of unit testing practices. IEEE Software, 23(4):22-29, July 2006.
• [46] Schuler D. and Zeller A. Javalanche: efficient mutation testing for java. In Proceedings of the the 7th joint meeting of the European software engineering conference and the ACM SIGSOFT symposium on the foundations of software engineering, pages 297-298, Amsterdam, The Netherlands, 2009. ACM.
• [47] Shin D. and Bae D.H. A theoretical framework for understanding mutationbased testing methods. In Proceedings of the IEEE International Conference on Software Testing, Verification and Validation (ICST’2016), pages 299-308, Chicago, IL, USA, April 2016.
• [48] Siami Namin A., Andrews J.H., and Murdoch D.J. Sufficient mutation operators for measuring test effectiveness. In Proceedings of the 30th International Conference on Software Engineering (ICSE’2018), pages 351-360, Leipzig, Germany, 2008. ACM.
• [49] Smith B.H. and Williams L. An Empirical Evaluation of the MuJava Mutation Operators. In Proceedings of the Testing: Academic and Industrial Conference Practice and Research Techniques (TAICPART-MUTATION’2007), pages 193-202, Washington, DC, USA, 2007. IEEE Computer Society.
• [50] Smith J.M. Elemental Design Patterns. Addison-Wesley, 2012.
• [51] Sun Y., Wang Q., and Yang Y. FRLink: Improving the recovery of missing issuecommit links by revisiting file relevance. Information and Software Technology, 84:33-47, 2017.
• [52] Tillmann N. and Schulte W. Parameterized unit tests. In Proceedings of the 10th European Software Engineering Conference Held Jointly with 13th ACM SIGSOFT International Symposium on Foundations of Software Engineering, ESEC/FSE-13, pages 253-262, Lisbon, Portugal, 2005. ACM.
• [53] Usaola M.P. and Mateo P.R. Mutation testing cost reduction techniques: A survey. IEEE Software, 27(3):80-86, May 2010.

Uwagi

Opracowanie rekordu w ramach umowy 509/P-DUN/2018 ze środków MNiSW przeznaczonych na działalność upowszechniającą naukę (2019).