Systematic Literature Review on Search Based Mutation Testing

Authors

Jatana Nishtha, Suri Bharti, Rani Shweta

Abstract

Search based techniques have been widely applied in the domain of software testing. This Systematic Literature Review aims to present the research carried out in the field of search based approaches applied particularly to mutation testing. During the course of literature review, renowned databases were searched for the relevant publications in the field to include relevant studies up to the year 2014. Few studies for the year 2015-16, gathered by performing snowball search, have also been included. For reviewing the literature in the field, 43 studies were evaluated, out of which 18 studies were thoroughly studied and analysed. The result of this SLR shows that search based techniques were applied to mutation testing primarily for two purposes, either for mutant optimisation or for test case optimisation. The future directions of this SLR suggests the application of search based techniques for other issues related to mutation testing, like, solution to equivalents mutants, generation of non-trivial mutants, multi-objective test data generation and non-functional testing.

Keywords

software testing, analysis and verification, systematic reviews and mapping studies

References

1. G.J. Myers, C. Sandler, and T. Badgett, The artof software testing. John Wiley & Sons, 2011.
2. J. Edvardsson, “A survey on automatic testdata generation,” in Proceedings of the 2nd Conferenceon Computer Science and Engineering,1999, pp. 21–28.
3. M. Prasanna, S. Sivanandam, R. Venkatesan,and R. Sundarrajan, “A survey on automatictest case generation,” Academic Open InternetJournal, Vol. 15, No. part 6, 2005.
4. H. Tahbildar and B. Kalita, “Automated softwaretest data generation: Direction of research,”International Journal of Computer Science andEngineering Survey, Vol. 2, No. 1, 2011, pp.99–120.
5. S. Anand, E.K. Burke, T.Y. Chen, J. Clark,M.B. Cohen, W. Grieskamp, M. Harman, M.J.Harrold, P. McMinn et al., “An orchestratedsurvey of methodologies for automated softwaretest case generation,” Journal of Systems andSoftware, Vol. 86, No. 8, 2013, pp. 1978–2001.
6. C.A.C. Coello, “A comprehensive survey ofevolutionary-based multiobjective optimizationtechniques,” Knowledge and Information systems,Vol. 1, No. 3, 1999, pp. 269–308.
7. P. McMinn, “Search-based software test datageneration: A survey,” Software Testing Verificationand Reliability, Vol. 14, No. 2, 2004, pp.105–156.
8. P. McMinn, “Search-based software testing: Past,present and future,” in IEEE Fourth InternationalConference on Software Testing, Verificationand Validation Workshops (ICSTW). IEEE,2011, pp. 153–163.
9. L. Bottaci, “A genetic algorithm fitness functionfor mutation testing,” in Proceedings of theSEMINALL-workshop at the 23rd InternationalConference on Software Engineering, Toronto,Canada, 2001.
10. M. Papadakis and N. Malevris, “Searching andgenerating test inputs for mutation testing,”SpringerPlus, Vol. 2, No. 1, 2013, p. 1.
11. F. Souza, M. Papadakis, V.H. Durelli, and M.E.Delamaro, “Test data generation techniques formutation testing: A systematic mapping,” Proceedingsof the 11th ESELAW, 2014, pp. 1–14.
12. Y. Jia and M. Harman, “An analysis and surveyof the development of mutation testing,” IEEETransactions on Software Engineering, Vol. 37,No. 5, 2011, pp. 649–678.
13. N. Jatana, S. Rani, and B. Suri, “State of art inthe field of search-based mutation testing,” in4th International Conference on Reliability, InfocomTechnologies and Optimization (ICRITO)(Trends and Future Directions). IEEE, 2015, pp.1–6.
14. R.A. Silva, S. do Rocio Senger de Souza, andP.S.L. de Souza, “A systematic review on searchbased mutation testing,” Information and SoftwareTechnology, 2016.
15. C. Wohlin, “Guidelines for snowballing in systematicliterature studies and a replication insoftware engineering,” in Proceedings of the 18thInternational Conference on Evaluation and Assessmentin Software Engineering. ACM, 2014,p. 38.
16. P. Cronin, F. Ryan, and M. Coughlan, “Undertakinga literature review: A step-by-stepapproach,” British Journal of Nursing, Vol. 17,No. 1, 2008, p. 38.
17. K. Petersen, R. Feldt, S. Mujtaba, and M. Mattsson,“Systematic mapping studies in softwareengineering,” in 12th International Conferenceon Evaluation and Assessment in Software Engineering,Vol. 17, No. 1. sn, 2008.
18. B. Kitchenham, “Procedures for performingsystematic reviews,” Keele University, KeeleUniversity, Keele, Staffs, UK, Joint TechnicalReport TR/SE-0401, 2004. [Online]. http://csnotes.upm.edu.my/kelasmaya/pgkm20910.nsf/0/715071a8011d4c2f482577a700386d3a/$FILE/10.1.1.122.3308.pdf
19. M.J. Grant and A. Booth, “A typology of reviews:An analysis of 14 review types and associatedmethodologies,” Health Information and LibrariesJournal, Vol. 26, No. 2, 2009, pp. 91–108.
20. B. Kitchenham and S. Charters, “Guidelines forperforming systematic literature reviews in softwareengineering,” Keele University & Universityof Durham, EBSE Technical Report EBSE2007-01, 2007.
21. W. Orzeszyna, L. Madeyski, andR. Torkar, Protocol for a systematicliterature review of methods dealingwith equivalent mutant problem. [Online].http://madeyski.e-informatyka.pl/download/slr/EquivalentMutantsSLRProtocol.pdf
22. L. Madeyski, W. Orzeszyna, R. Torkar, andM. Jozala, “Overcoming the equivalent mutantproblem: A systematic literature review and acomparative experiment of second order mutation,”IEEE Transactions on Software Engineering,Vol. 40, No. 1, 2014, pp. 23–42.
23. B. Baudry, V. Le Hanh, J.M. Jézéquel, andY. Le Traon, “Trustable components: Yet anothermutation-based approach,” in Mutationtesting for the new century. Springer, 2001, pp.47–54.
24. B. Baudry, F. Fleurey, J.M. Jézéquel, andY. Le Traon, “Genes and bacteria for automatictest cases optimization in the .NET environment,”in 13th International Symposium on SoftwareReliability Engineering. IEEE, 2002, pp.195–206.
25. P. May, K. Mander, and J. Timmis, “Softwarevaccination: An artificial immune systemapproach to mutation testing,” in InternationalConference on Artificial Immune Systems.Springer, 2003, pp. 81–92.
26. M.C.F. Emer and S.R. Vergilio, “Selection andevaluation of test data based on genetic programming,”Software Quality Journal, Vol. 11, No. 2,2003, pp. 167–186.
27. K. Adamopoulos, M. Harman, and R.M. Hierons,“How to overcome the equivalent mutantproblem and achieve tailored selective mutationusing co-evolution,” in Genetic and evolutionarycomputation conference. Springer, 2004, pp.1338–1349.
28. M. Masud, A. Nayak, M. Zaman, and N. Bansal,“Strategy for mutation testing using genetic algorithms,”in Canadian Conference on Electricaland Computer Engineering. IEEE, 2005, pp.1049–1052.
29. K. Ayari, S. Bouktif, and G. Antoniol, “Automaticmutation test input data generation viaant colony,” in Proceedings of the 9th annualconference on Genetic and evolutionary computation.ACM, 2007, pp. 1074–1081.
30. Y. Jia and M. Harman, “Constructing subtlefaults using higher order mutation testing,”in Eighth IEEE International Working Conferenceon Source Code Analysis and Manipulation.IEEE, 2008, pp. 249–258.
31. K. Mishra, S. Tiwari, A. Kumar, and A. Misra,“An approach for mutation testing using elitistgenetic algorithm,” in 3rd IEEE InternationalConference on Computer Science and InformationTechnology (ICCSIT), Vol. 5. IEEE, 2010,pp. 426–429.
32. B. Schwarz, D. Schuler, and A. Zeller, “Breedinghigh-impact mutations,” in IEEE FourthInternational Conference on Software Testing,Verification and Validation Workshops (ICSTW).IEEE, 2011, pp. 382–387.
33. M. Harman, Y. Jia, and W.B. Langdon, “Stronghigher order mutation-based test data generation,”in Proceedings of the 19th ACM SIGSOFTSymposium and the 13th European Conferenceon Foundations of Software Engineering. ACM,2011, pp. 212–222.
34. J.J. Domínguez-Jiménez, A. Estero-Botaro,A. García-Domínguez, and I. Medina-Bulo, “Evolutionarymutation testing,” Information andSoftware Technology, Vol. 53, No. 10, 2011, pp.1108–1123.
35. G. Fraser and A. Zeller, “Mutation-driven generationof unit tests and oracles,” IEEE Transactionson Software Engineering, Vol. 38, No. 2,2012, pp. 278–292.
36. A.A.L. de Oliveira, C.G. Camilo-Junior, andA.M. Vincenzi, “A coevolutionary algorithm toautomatic test case selection and mutant in mutationtesting,” in IEEE Congress on EvolutionaryComputation. IEEE, 2013, pp. 829–836.
37. M.B. Bashir and A. Nadeem, “A fitnessfunction for evolutionary mutation testing ofobject-oriented programs,” in 9th InternationalConference on Emerging Technologies (ICET).IEEE, 2013, pp. 1–6.
38. P.S. Yiasemis and A.S. Andreou, “Locating andcorrecting software faults in executable codeslices via evolutionary mutation testing,” in InternationalConference on Enterprise InformationSystems. Springer, 2012, pp. 207–227.
39. E. Omar, S. Ghosh, and D. Whitley, “Comparingsearch techniques for finding subtle higher ordermutants,” in Proceedings of the Annual Conferenceon Genetic and Evolutionary Computation.ACM, 2014, pp. 1271–1278.
40. E. Omar, S. Ghosh, and D. Whitley, “Constructingsubtle higher order mutants for Java andAspectJ programs,” in IEEE 24th InternationalSymposium on Software Reliability Engineering(ISSRE). IEEE, 2013, pp. 340–349.
41. Y.M.B. Ali and F. Benmaiza, “Generating testcase for object-oriented software using geneticalgorithm and mutation testing method,” InternationalJournal of Applied Metaheuristic Computing(IJAMC), Vol. 3, No. 1, 2012, pp. 15–23.
42. A.S. Banzi, T. Nobre, G.B. Pinheiro, J.C.G.Árias, A. Pozo, and S.R. Vergilio, “Selecting mutationoperators with a multiobjective approach,”Expert Systems with Applications, Vol. 39, No. 15,2012, pp. 12 131–12 142.
43. B. Baudry, V. Le Hanh, J.M. Jézéquel, andY. Le Traon, “Building trust into oo componentsusing a genetic analogy,” in 11th InternationalSymposium on Software Reliability Engineering.IEEE, 2000, pp. 4–14.
44. S. Subramanian and R. Natarajan, “A tool forgeneration and minimization of test suite bymutant gene algorithm,” Journal of ComputerSciences, Vol. 7, No. 10, 2011, pp. 1581–1589.
45. K.T. Le Thi My Hanh and N.T.B. Tung,“Mutation-based test data generation forsimulink models using genetic algorithm andsimulated annealing,” International Journal ofComputer and Information Technology, Vol. 3,No. 04, 2014, pp. 763–771.
46. N.T. Binh, K.T. Tung et al., “A novel testdata generation approach based upon mutationtesting by using artificial immune system forSimulink models,” in Knowledge and SystemsEngineering. Springer, 2015, pp. 169–181.
47. L.T.M. Hanh, N.T. Binh, and K.T. Tung,“Applying the meta-heuristic algorithms formutation-based test data generation for Simulinkmodels,” in Proceedings of the Fifth Symposiumon Information and Communication Technology.ACM, 2014, pp. 102–109.
48. B.N. Thanh and T.K. Thanh, “Survey onmutation-based test data generation,” InternationalJournal of Electrical and Computer Engineering,Vol. 5, No. 5, 2015.
49. M. Patrick, “Metaheuristic optimisation andmutation-driven test data generation,” in ComputationalIntelligence and Quantitative SoftwareEngineering. Springer, 2016, pp. 89–115.
50. F. Popentiu-Vladicescu and G. Albeanu,“Nature-inspired approaches in software faultsidentification and debugging,” Procedia ComputerScience, Vol. 92, 2016, pp. 6–12.
51. M. Dave and R. Agrawal, “Search based techniquesand mutation analysis in automatic testcase generation: A survey,” in IEEE InternationalAdvance Computing Conference (IACC).IEEE, 2015, pp. 795–799.
52. Y. Jia, F. Wu, M. Harman, and J. Krinke, “Geneticimprovement using higher order mutation,”in Proceedings of the Companion Publication ofthe Annual Conference on Genetic and EvolutionaryComputation. ACM, 2015, pp. 803–804.
53. Q.V. Nguyen and L. Madeyski, “Searching forstrongly subsuming higher order mutants by applyingmulti-objective optimization algorithm,”in Advanced Computational Methods for KnowledgeEngineering. Springer, 2015, pp. 391–402.
54. Q.V. Nguyen and L. Madeyski, “Higher ordermutation testing to drive development of newtest cases: An empirical comparison of threestrategies,” in Asian Conference on IntelligentInformation and Database Systems. Springer,2016, pp. 235–244.
55. Q.V. Nguyen and L. Madeyski, “Empirical evaluationof multiobjective optimization algorithmssearching for higher order mutants,” Cyberneticsand Systems, 2016.
56. F. Wu, M. Harman, Y. Jia, and J. Krinke,“HOMI: Searching higher order mutants for softwareimprovement,” in International Symposiumon Search Based Software Engineering. Springer,2016, pp. 18–33.
57. A. Estero-Botaro, A. García-Domínguez, J.J.Domínguez-Jiménez, F. Palomo-Lozano, andI. Medina-Bulo, “A framework for genetictest-case generation for ws-bpel compositions,”in IFIP International Conference on TestingSoftware and Systems. Springer, 2014, pp. 1–16.
58. C.P. Rao and P. Govindarajulu, “Genetic algorithmfor automatic generation of representativetest suite for mutation testing,” InternationalJournal of Computer Science and Network Security(IJCSNS), Vol. 15, No. 2, 2015, p. 11.
59. S. Rani and B. Suri, “An approach for test datageneration based on genetic algorithm and deletemutation operators,” in Second InternationalConference on Advances in Computing and CommunicationEngineering (ICACCE). IEEE, 2015,pp. 714–718.
60. F.C.M. Souza, M. Papadakis, Y. Le Traon, andM.E. Delamaro, “Strong mutation-based testdata generation using hill climbing,” in Proceedingsof the 9th International Workshop onSearch-Based Software Testing. ACM, 2016, pp.45–54.
61. N. Jatana, B. Suri, S. Misra, P. Kumar, and A.R.Choudhury, “Particle swarm based evolution andgeneration of test data using mutation testing,”in International Conference on ComputationalScience and its Applications. Springer, 2016, pp.585–594.
62. N.T. Binh, K.T. Tung et al., “A novel fitnessfunction of metaheuristic algorithms for test datageneration for Simulink models based on mutationanalysis,” Journal of Systems and Software,Vol. 120, 2016, pp. 17–30.
63. N. Jatana, B. Suri, P. Kumar, and B. Wadhwa,“Test suite reduction by mutation testing mappedto set cover problem,” in Proceedings of the SecondInternational Conference on Informationand Communication Technology for CompetitiveStrategies. ACM, 2016, p. 36.
64. P. McMinn, M. Harman, K. Lakhotia, Y. Hassoun,and J. Wegener, “Input domain reductionthrough irrelevant variable removal and its effecton local, global, and hybrid search-based structuraltest data generation,” IEEE Transactionson Software Engineering, Vol. 38, No. 2, 2012,pp. 453–477.
65. M. Dorigo and G.D. Caro, New ideas in optimization.McGraw-Hill Ltd., 1999, ch. The antcolony optimization meta-heuristic, pp. 11–32.
66. M. Dorigo, G. Di Caro, and L.M. Gambardella,“Ant algorithms for discrete optimization,” Artificiallife, Vol. 5, No. 2, 1999, pp. 137–172.
67. M. Dorigo, “Optimization, learning and naturalalgorithms,” Ph. D. Thesis, Politecnico diMilano, Italy, 1992.
68. T. Stützle, M. López-Ibáñez, and M. Dorigo, “Aconcise overview of applications of ant colonyoptimization,” Wiley Encyclopedia of OperationsResearch and Management Science, 2011.
69. B. Suri and S. Singhal, “Literature survey ofant colony optimization in software testing,” inCSI Sixth International Conference on SoftwareEngineering (CONSEG). IEEE, 2012, pp. 1–7.
70. A.S. Fraser, “Simulation of genetic systems byautomatic digital computers VI. Epistasis,” AustralianJournal of Biological Sciences, Vol. 13,No. 2, 1960, pp. 150–162.
71. H.J. Bremermann, The evolution of intelligence:The nervous system as a model of its environment.University of Washington, Department ofMathematics, 1958.
72. J.H. Holland, Adaptation in natural and artificialsystems: an introductory analysis with applicationsto biology, control, and artificial intelligence.U Michigan Press, 1975.
73. C. Sharma, S. Sabharwal, and R. Sibal, “Asurvey on software testing techniques usinggenetic algorithm,” CoRR, 2014. [Online].https://arxiv.org/abs/1411.1154
74. E. Omar and S. Ghosh, “An exploratory study ofhigher order mutation testing in aspect-orientedprogramming,” in IEEE 23rd InternationalSymposium on Software Reliability Engineering.IEEE, 2012, pp. 1–10.
75. B. Baudry, F. Fleurey, J.M. Jézéquel, andY. Le Traon, “Automatic test case optimizationusing a bacteriological adaptation model: Applicationto .NET components,” in 17th IEEEInternational Conference on Automated SoftwareEngineering. IEEE, 2002, pp. 253–256.
76. B. Baudry, F. Fleurey, J.M. Jézéquel, andY. Le Traon, “From genetic to bacteriologicalalgorithms for mutation-based testing,” SoftwareTesting, Verification and Reliability, Vol. 15,No. 2, 2005, pp. 73–96.
77. P. May, J. Timmis, and K. Mander, “Immuneand evolutionary approaches to software mutationtesting,” in Artificial Immune Systems.Springer, 2007, pp. 336–347.
78. P. May, K. Mander, and J. Timmis, “Mutationtesting: An artificial immune system approach,”in UK-Softest. UK Software Testing Workshop.Citeseer, 2003.
79. M. Papadakis and N. Malevris, “Automaticallyperforming weak mutation with the aidof symbolic execution, concolic testing andsearch-based testing,” Software Quality Journal,Vol. 19, No. 4, 2011, pp. 691–723.
80. Y. Jia and M. Harman, “Higher order mutationtesting,” Information and Software Technology,Vol. 51, No. 10, 2009, pp. 1379–1393.
81. Y. Jia, “Higher order mutation testing,” Ph.D.dissertation, University College London, 2013.[Online]. http://discovery.ucl.ac.uk/1401264/1/YuePhDFinal2013.pdf
82. Q.V. Nguyen and L. Madeyski, “Problems of mutationtesting and higher order mutation testing,”in Advanced computational methods for knowledgeengineering. Springer, 2014, pp. 157–172.
83. M. Harman, Y. Jia, and Y. Zhang, “Achievements,open problems and challenges for searchbased software testing,” in IEEE 8th InternationalConference on Software Testing, Verificationand Validation (ICST). IEEE, 2015, pp.1–12.