Hybridizing genetic algorithm and harmony search for higher-order mutation testing
Pages 4429 - 4452
Abstract
Mutation testing can evaluate the quality of the test inputs, generate test data, and simulate any test coverage criterion. Genetic algorithms and harmony search have been applied to reduce the cost of generating test inputs. Although hybridizing search algorithms enhances the efficiency of searching the solution domain, there is a shortage of applying the hybrid search techniques in mutation testing. This paper merges the genetic and harmony search algorithms to effectively generate test data to kill higher-order mutants. In addition, the performance of the proposed technique will be evaluated and compared with a stand-alone genetic algorithm and a stand-alone harmony search algorithm through an empirical study using a set of benchmark programs. The experimental study shows that the proposed technique outperformed the compared algorithms, reaching a higher killing ratio, where the proposed approach kills 92.8% of higher-order mutants for all tested programs. In comparison, GA kills 88.7%, and HA kills 86.6%. Besides, the proposed algorithm overcame the compared algorithm in reaching a targeted killing ratio faster than the compared algorithms. HGA reduced the execution time for each program with a reduction ratio ranging from 58.9% to 89.8%.
References
[1]
Pacheco C., Lahiri S.K., Ernst M.D., Ball T. Feedbackdirected random test generation, in Proceedings of the 29th International Conference on Software Engineering, ICSE’07, 2007, pp. 75–84.
[2]
Liu M., Gao Y., Shan J., Liu J., Zhang L., Sun J. An approach to test data generation for killing multiple mutants, in Proceedings of the 22nd IEEE International Conference on Software Maintenance, ICSM’06, 2006, pp. 113–122.
[3]
Harman M., Jia Y., Langdon B. Strong higher order mutation-based test data generation, in Proceedings of the 8th European Software Engineering Conference and the ACM SIGSOFT Symposium on the Foundations of Software Engineering (ESEC/FSE ’11), 2011, pp. 212–222.
[4]
Papadakis M., Malevris N., Kallia M. Towards automating the generation of mutation tests, in Proceedings of the 5th Workshop on Automation of Software Test, AST ’10, 2010, pp. 111–118.
[5]
Ghiduk A.S., Girgis M.R. and Shehata M.H., Higher-order mutation testing: a systematic literature review, Computer Science Review Journal 25 (2017), 29–48.
[6]
Jia Y. and Harman M., Higher order mutation testing, Information and Software Technology 51(10) (2009), 1379–1393.
[7]
Serdyukov K.E., Avdeenko T.V. Using genetic algorithm for generating optimal data sets to automatic testing the program code, in Proceedings of International Conference on Information Technology and Nanotechnology (ITNT-2019), 2019, pp. 174–182.
[8]
Dang X., Gong D., Yao X., Tian T., Liu H. Enhancement of Mutation Testing via Fuzzy Clustering and Multi-population Genetic Algorithm, in IEEE Transactions on Software Engineering, pp. 1–1, 2021.
[9]
Mao C., Harmony search-based test data generation for branch coverage in software structural testing, Neural Computing and Applications 25 (2015), 199–216.
[10]
Sahoo R.K., Ojha D., Mohapatra D.P., Patra M.R. Automatic generation and optimization of test data using harmony search algorithm, in Proceedings 6th International Conference on Advances in Computing and Information Technology, 2016, pp. 23–32.
[11]
Sabbagh Jafari S.M., Ziaaddini F. Optimization of software cost estimation using harmony search algorithm, 2016 1st Conference on Swarm Intelligence and Evolutionary Computation (CSIEC), pp. 131–135, 2016.
[12]
Amarjeet and Chhabra J.K., Harmony search based remodularization forobject-oriented software systems, Computer Languages, Systems & Structures 47(part 2) (2017), 153–169.
[13]
Kang J., Kwon S., Ryu D. and Baik J., HASPO: Harmony Search-Based Parameter Optimization for Just-in-Time Software Defect Prediction in Maritime Software, Applied Sciences 11(5) (2021), 2002.
[14]
Geem Prajapati Z.W., Harmony Search-Based Approach for Multi-Objective Software Architecture Reconstruction, Mathematics 8 (2020), 1906.
[15]
Mala D.J., Ruby E. and Mohan V., A hybrid test optimization framework coupling genetic algorithm with local search technique, Computing and Informatics 29 (2010), 133–164.
[16]
Singh A., Garg N. and Saini T., A hybrid approach of genetic algorithm and particle swarm technique to software test case generation, International Journal of Innovations in Engineering and Technology (IJIET) 3(4) (2014), 208–214.
[17]
Wang G. and Guo L., A novel hybrid bat algorithm with harmony search for global numerical optimization, Journal of Applied Mathematics 2013 (2013), 1–21, Article ID 696491.
[18]
Kaveh A. and Talatahari S., Particle swarm optimizer, ant colony strategy and harmony search scheme hybridized for optimization of truss structures, Computers & Structures 87(5-6) (2009), 267–283.
[19]
Yildiz A., Ozturk F. Hybrid taguchi-harmony search approach for shape optimization, In Geem Z (ed) Recent advances in Harmony search algorithm. Springer, Berlin, 2010, pp. 89–98.
[20]
Hasani K., Kravchenko S.A. and Werner F., A hybridization of harmony search and simulated annealing to minimize mean flow time for the two-machine scheduling problem with a single server, International Journal of Operation Research (IJORN) 3(1) (2014), 9–26.
[21]
Souza F., Papadakis M., Durelli V.H., Delamaro M.E. Test data generation techniques for mutation testing: A systematic mapping, in Proceedings of the 11th Workshop on Experimental Software Engineering (ESELAW ’14), 2014, pp. 1–14.
[22]
Baudry B., Flrurey F., Jean-Marc J. and Le Traon Y., From genetic to bacteriological algorithms for mutation-based testing, Software Testing Verification Reliability 15 (2005), 73–96.
[23]
Papadakis M. and Malevris N., Searching and generating test inputs for mutation testing, Journal Springer Plus 2 (2013), 1–12.
[24]
Louzada J., Camilo-Junior C.G., Vincenzi A., Rodrigues C. An elitist evolutionary algorithm for automatically generating test data, in Proceedings ofWorld Congress on Computational Intelligence (WCCI’12), 2012, pp. 1–8.
[25]
Haga H., Suehiro A. Automatic test case generation based on genetic algorithm and mutation analysis, in International Conference on Control System, Computing and Engineering (ICCSCE’12), 2012, pp. 119–123.
[26]
Rad M., Akbari F., Bakht A. Implementation ofcommon genetic and bacteriological algorithms in optimizing testing data in mutation testing, in Proceedings of 2010 International Conference Computational Intelligence and Software Engineering (CiSE’10), 2010, pp. 1–6.
[27]
Fraser G., Zeller A. Mutation-driven generation of unit tests and oracles, in Proceedings of International Symposium on Software Testing and Analysis (ISSTA’10), 2010, pp. 147–157.
[28]
Mishra K.K., Tiwari S., Kumar A., Misra A. An approach for mutation testing using elitist genetic algorithm, in Proceedings of International Conference on Computer Science and Information Technology, 2010, pp. 426–429.
[29]
Ayari K., Bouktif S., Antoniol G. Automatic mutation test input data generation via ant colony, in Proceedings of the Conference of Genetic and Evolutionary Computation, 2007, pp. 1074–1081.
[30]
Alzubaidy L.M. and Allhafid B.S., Proposed software testing using intelligent water drop (IWD) & ant colony optimization (ACO), International Journal of Computer Science Issues 10(5) (2013), 91–97.
[31]
Srivastava P.R., Baby K. Automated software testing using metaheuristics techniques based on ant colony optimization, in Proceedings of 2010 International Symposium on Electronic System Design, Bhubaneswar, 2010, pp. 235–240.
[32]
Espinoza F.B., Minsker B., Goldberg D. Aself-adaptive hybrid genetic algorithm, in Proceedings of the 3rd Annual Conference on Genetic and Evolutionary Computation, (GECCO’01), 2001, pp. 759–759.
[33]
Andrews J., Briand L., Labiche Y. Is mutation an appropriate tool for testing experiments? in Proceedings of the 27th International Conference on Software Engineering, ICSE ’05, 2005, pp. 402–411.
[34]
Do H. and Rothermel G., On the use of mutation faults in empirical assessments of test case prioritization techniques, IEEE Transactions on Software Engineering 32(9) (2006), 733–752.
[35]
Zhu H., Hall P.A.V. and May J.H.R., Software unit test coverage and adequacy, ACM Computing Surveys 29(4) (1997), 366–427.
[36]
DeMillo R.A., Lipton R.J. and Sayward F.G., Hints on test data selection: Help for the practicing programmer, Computer 11(4) (1978), 34–41.
[37]
Hamlet R.G., Testing programs with the aid of a compiler, IEEE Transactions on Software Engineering 3(4) (1977), 279–290.
[38]
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) (2014), 23–44.
[39]
Jia Y., Harman M. Constructing Subtle Faults Using Higher Order Mutation Testing, in Proceedings of the 8th InternationalWorking Conference on Source Code Analysis and Manipulation (SCAM’08), 2008, pp. 249–258.
[40]
Michalewicz Z. Genetic algorithms+Data Structures Evolution Programs, 3rd. Springer. 1998.
[41]
Geem Z.W., Kim J.H. and Loganathan G.V., A new heuristic optimization algorithm Harmony search, Simulation 76(2) (2001), 60–68.
[42]
Askarzadeh A., Rashedi E. Harmony Search Algorithm: Basic Concepts and Engineering Applications, Chapter 1 of Recent Developments in Intelligent Nature-Inspired Computing, IGI-Global, 2017, pp. 1–36.
[43]
Mahdavi M., Fesanghary M. and Damangir E., An improved harmony search algorithm for solving optimization problems, Applied Mathematics and Computation 188(2) (2007), 1567–1579.
[44]
Goldberg D.E. Genetic Algorithms in Search, Optimization and Machine Learning, 1st ed. Addison-Wesley Longman Publishing Co., Inc., Boston, MA, USA, 1989.
[45]
“MuClipse”, http://muclipse.sourceforge.net,2008
[46]
Ghiduk A.S., Girgis M.R. and Shehata M.H., Reducing the cost of higher-order mutation testing, Arabian Journal for Science and Engineering 43(12) (2018), 7473–7486.
[47]
Smits J.P.G. Callisto –selecting effective mutation operators for mutation testing, Master Essay, EEMCS: Electrical Engineering, Mathematics and Computer Science, University of Twente, Enschede, Netherlands, 2022. http://purl.utwente.nl/essays/89294 last visited May, 7, 2022.
[48]
Humbatova N., Jahangirova G., Tonella P. DeepCrime: mutation testing of deep learning systems based on real faults, In Proceedings of the 30th ACM SIGSOFT International Symposium on Software Testing and Analysis (ISSTA 2021). Association for Computing Machinery, New York, NY, USA, pp. 67–78, 2021.
[49]
Lee D. and Seo Y., Identification of propagated defects to reduce software testing cost via mutation testing[J], Mathematical Biosciences and Engineering 19(6) (2022), 6124–6140.
[50]
Wong C., Meinicke J., Chen L., Diniz J.P., Kästner C., Figueiredo E. Efficiently finding higher-order mutants, In Proceedings of the 28th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering. Association for Computing Machinery, New York, NY, USA, pp. 1165–1177, 2020.
[51]
Wang H., Li Z., Liu Y., Chen X., Paul D., Cai Y., Fan L. Can higher-order mutants improve the performance of mutation-based fault localization? IEEE Transactions on Reliability, (2022), 1–17.
[52]
Beller M. et al. What it would take to use mutation testing in industry—a study at Facebook, 2021 IEEE/ACM 43rd International Conference on Software Engineering: Software Engineering in Practice (ICSE-SEIP), pp. 268–277, 2021.
[53]
Rodríguez-Trujillo I.C. Mutation testing techniques for mobile applications, PhD. Thesis, Universidad De Concepcion, Facultad de Ingeniería, Departamento en Ciencias de la Computación, Id: 21160055, 2021.
[54]
Godboley S., Mohapatra D.P. Towards agile mutation testing using branch coverage based prioritization technique, In: Przybyl-ek, A., Jarzebowicz, A., Luković, I., Ng, Y.Y. (eds) Lean and Agile Software Development. LASD 2022. Lecture Notes in Business Information Processing, vol 438. Springer, Cham, 2022.
Recommendations
The mechanical arm control based on harmony search genetic algorithm
Considering the low efficiency and instability of traditional genetic algorithm optimized PID controller, an improved algorithm named harmony search genetic algorithm to optimize PID controller's parameters of mechanical arm is proposed in this paper. ...
Application of genetic algorithm and tabu search in software testing
COMPUTE '11: Proceedings of the Fourth Annual ACM Bangalore ConferenceThis paper presents a technique for automatic test-data generation in software testing. The proposed approach is based on genetic and tabu search algorithms. It combines the strength of two metaheuristic techniques and produces efficient results. The ...
Mutation-based genetic algorithm for efficiency optimisation of unit testing
Fault in a software program can be detected by mutation testing. However, mutation testing is an expensive process in a software testing domain. In this paper, we have introduced a method based on genetic algorithm and mutation analysis for unit testing ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
© 2024 – IOS Press. All rights reserved.
Publisher
IOS Press
Netherlands
Publication History
Published: 14 February 2024
Author Tags
Qualifiers
- Research-article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 13 Dec 2024