International Journal of Intelligent Systems and Applications (IJISA)
IJISA Vol. 10, No. 1, 8 Jan. 2018
Cover page and Table of Contents: PDF (size: 720KB)
An Approach for the Generation of Higher Order Mutants Using Genetic Algorithms
Full Text (PDF, 720KB), PP.34-45
Views: 0 Downloads: 0
Author(s)
Anas Abuljadayel
1,*
Fadi Wedyan
1
Index Terms
Higher order mutant, mutation testing, genetic algorithm, software testing, equivalent mutants, evolutionary approach
Abstract
Mutation testing is a structural testing technique in which the effectiveness of a test suite is measured by the suite ability to detect seeded faults. One fault is seeded into a copy of the program, called mutant, leading to a large number of mutants with a high cost of compiling and running the test suite against the mutants. Moreover, many of the mutants produce the same output as the original program (called equivalent mutants), such mutants need to be minimized to produce accurate results. Higher order mutation testing aims at solving these problems by allowing more than one fault to be seeded in the mutant. Recent work in higher order mutation show promising result in reducing the cost of mutation testing and increasing the approach effectiveness. In this paper, we present an approach for generating higher order mutants using a genetic algorithm. The aim of the proposed approach is to produce subtle and harder to kill mutants, and reduce the percentage of produced equivalent mutants. A Java tool has been developed, called HOMJava (Higher Order Mutation for Java), which implements the proposed approach. An experimental study was performed to evaluate the effectiveness of the proposed approach. The results show that the approach was able to produce subtle higher order mutants, the fitness of mutants improved by almost 99% compared with the first order mutants used in the experiment. The percentage of produced equivalent mutants was about 4%.
Cite This Paper
Anas Abuljadayel, Fadi Wedyan, "An Approach for the Generation of Higher Order Mutants Using Genetic Algorithms", International Journal of Intelligent Systems and Applications(IJISA), Vol.10, No.1, pp.34-45, 2018. DOI:10.5815/ijisa.2018.01.05
Reference
[1]R. DeMillo, R. Lipton, and F. Sayward, “Hints on test data selection: Help for the practicing programmer,” Computer, vol. 11(4), pp. 34-41, 1978.
[2]R. Hamlet, “Testing programs with the aid of a compiler,” IEEE Transactions on Software Engineering, vol. 3(4), pp. 279-290, 1977.
[3]P. G. Frankl, S. N. Weiss, and C. Hu, “All-Uses vs Mutation Testing: An Experimental Comparison of Effectiveness,” Journal of Systems and Software, vol. 38(3), pp. 235-253, 1997.
[4]J. Offutt, J. Pan, K. Tewary, and T. Zhang, “An Experimental Evaluation of Data Flow and Mutation Testing,” Software Practice and Experience, vol. 26(2), pp. 165-176, 1996.
[5]T. A. Budd, R. DeMillo, R. Lipton, and F. Sayward, “The design of a prototype mutation system for program testing,” in: AFIPS National Computer Conference, Anaheim, New Jersey, USA, 1978, pp. 623-627.
[6]H. Zhu, P. A. V. Hall, J. H. R. May, “Software unit test coverage and adequacy,” ACM Computing Surveys, vol. 29, pp. 366-427, 1997.
[7]J. Offutt and R. Untch, “Mutation 2000: Uniting the orthogonal,” Mutation testing for the new century, 2001, 34-44.
[8]J. Offutt and J. Pan, “Automatically detecting equivalent mutants and infeasible paths,” Software Testing, Verification and Reliability, vol. 7, pp. 165-192, 1997.
[9]T. A. Budd and D. Angluin, “Two notions of correctness and their relation to testing,” Acta Informatica, vol. 18, pp. 31-45, 1982.
[10]R. DeMillo, R. Lipton, and F. Sayward, “Hints on test data selection: help for the practical programmer,” IEEE Computer, vol. 11(4), pp. 31-41, 1978.
[11]P. Frankl P and O. Iakounenko, “Further empirical studies of test effectiveness,” in: Proceedings of the 6th ACM SIGSOFT International Symposium on Foundations of Software Engineering, Orlando, USA, 1998, pp. 153-162.
[12]D. Baldwin and F. Sayward, “Heuristics for determining equivalence of program mutations,” DTIC Document, Tech. Rep., 1979.
[13]J. Offutt and W. Craft, “Using compiler optimization techniques to detect equivalent mutants,” Software Testing, Verification and Reliability, vol. 4(3), pp. 131-154, 1994.
[14]J. Offutt and J. Pan, “Detecting equivalent mutants and the feasible path problem,” in: Proceedings of the Eleventh Annual Conference on Computer Assurance, 1996, pp. 224-236.
[15]J. Offutt and J. Pan, “Automatically detecting equivalent mutants and infeasible paths,” Software testing, verification and reliability, vol. 7(3), pp. 165-192, 1997.
[16]R. Hierons, M. Harman, and S. Danicic, “Using program slicing to assist in the detection of equivalent mutants,” Software Testing, Verification and Reliability, vol. 9(4), pp. 233-262, 1999.
[17]E. Mresa and L. Bottaci, “Efficiency of mutation operators and selective mutation strategies: An empirical study,” Software Testing Verification and Reliability, vol. 9(4), pp. 205-232, 1999.
[18]B. Grun, D. Schuler, and A. Zeller, “The impact of equivalent mutants,” in: Software Testing, Verification and Validation Workshops, Denver, Colorado, USA, 2009, pp. 192-199.
[19]D. Schuler, A. Zeller, “Covering and uncovering equivalent mutants,” Software Testing, Verification and Reliability, vol. 23(5), pp. 353-374, 2013.
[20]K. Adamopoulos, M. Harman, and R. Hierons, “How to overcome the equivalent mutant problem and achieve tailored selective mutation using co-evolution,” in: Genetic and Evolutionary Computation–GECCO, Heidelberg, 2004, pp. 1338-1349.
[21]J. Offutt and S. Lee, “An empirical evaluation of weak mutation,” IEEE Transactions on Software Engineering, vol. 20(5), pp. 337-344, 1994.
[22]A. Acree, “On Mutation,” Ph.D. Dissertation, Atlanta, GA, USA, Georgia Institute of Technology, 1980.
[23]T. Budd, “Mutation analysis of program test data,” Ph.D. Dissertation, New Haven, CT, USA, Yale University, 1980.
[24]S. Hussain, “Mutation clustering,” Master Thesis, Strand, London, Kings College London, 2008.
[25]W. Howden, “Weak mutation testing and completeness of test sets,” IEEE Transactions on Software Engineering, vol. 4, pp. 371-379, 1982.
[26]M. Polo and M. Piattini, “Decreasing the cost of mutation
testing with second-order mutants,” Software Testing, Verification and Reliability, vol. 19(2), pp. 111–131, 2009.
[27]Y. Jia and M. Harman, “Higher order mutation testing,” Information and Software Technology, vol. 51(10), pp. 1379–1393, 2009.
[28]W. Langdon, M. Harman, and Y. Jia, “Efficient multi-objective higher order mutation testing with genetic programming,” Journal of systems and Software, vol. 83(12), pp. 2416–2430, 2010.
[29]E. Omar and S. Ghosh, “An exploratory study of higher order mutation testing in aspect-oriented programming,” in: IEEE 23rd International Symposium on Software Reliability Engineering (ISSRE), Dallas, TX, USA, 2012, pp. 1–10.
[30]P. Reales Mateo, M. Polo, M. Usaola, and J. Fernandez Aleman, “Validating second-order mutation at system level,” IEEE Transactions on Software Engineering, vol. 39(4), pp. 570–587, 2013.
[31]E. Omar, S. Ghosh, and D. Whitley, “Constructing subtle higher order mutants for Java and AspectJ programs,” in: IEEE 24th International Symposium on Software Reliability Engineering (ISSRE), Pasadena, CA, USA, 2013, pp. 340–349.
[32]E. Omar, S. Ghosh, D. Whitley, “Comparing search techniques for finding subtle higher order mutants,” in: Proceedings of the 2014 conference on Genetic and evolutionary computation, ACM, Vancouver, BC, Canada, 2014, pp. 1271–1278.
[33]F. Wedyan and S. Ghosh, “On generating mutants for aspect programs,” Information and Software Technology, vol .54(8), pp. 900–914, 2012.
[34]L. Madeysk, W. Orzeszyna, R. Torkar, and M. Jozala, “Overcoming the equivalent mutant problem: A systematic literature review and a comparative experiment of second order mutation,” IEEE Transactions on Software Engineering, vol. 40(1), pp. 23-42, 2014.
[35]J. Holland,”Genetic Algorithms and the Optimal Allocation of Trial,” SIAM Journal on Computing, vol. 2(2), pp. 88-105, 1973.
[36]Y. Ma, J. Offutt, and Y. Kwon, “MuJava: an automated class mutation system,” Software Testing, Verification and Reliability, vol. 15(2), pp. 97-133, 2005.
[37]R. Untch, J. Offutt, and M. Harrold, “Mutation analysis using program schemata,” in: Proceedings of the 1993 International Symposium on Software Testing, and Analysis (ISSTA), ACM Press, Cambridge, MA, 1993, pp. 139–148.
[38]C. Fonseca and P. Fleming, “Genetic algorithms for multiobjective optimization: formulation, discussion and generalization,” in: Proceedings of the 5th International Conference on Genetic Algorithms, ICGA-93, 1993, pp. 416–423.
[39]J. S. Baekken and R. T. Alexander, “A candidate fault model for AspectJ pointcuts,” in: International Symposium on Software Reliability Engineering, Raleigh, North Carolina, USA, 2006, pp. 169–178.
[40]F. Ferrari, J. Maldonado, and A. Rashid, “Mutation Testing for Aspect-Oriented Programs,” in: International Conference on Software Testing, Verification, and Validation, Lillehammer, Norway, 2008, pp. 52-61.
[41]E. Omar, S. Ghosh, and D. Whitley, “HOMAJ: A tool for higher order mutation testing in AspectJ and Java,” in: IEEE Seventh International Conference on Software Testing, Verification and Validation Workshops (ICSTW), Cleveland, Ohio, USA, 2014, pp. 165–170.
[42]A. Derezinska and K. Halas, “Experimental evaluation of mutation testing approaches to python programs,” in: IEEE 7th International Conference on Software Testing, Verification and Validation Workshops (ICSTW), Cleveland, Ohio, USA, 2014, pp. 156–164.
[43]M. Kintis, M. Papadakis, and N. Malevris, “Employing second order mutation for isolating first-order equivalent mutants,” Software Testing, Verification and Reliability, vol. 25(5-7), pp. 508-535, 2014.
[44]Q. V. Nguyen and L. Madeyski, “Searching for Strongly Subsuming Higher Order Mutants by Applying Multi-objective Optimization Algorithm,” in: Advanced Computational Methods for Knowledge Engineering, 2015, pp. 391-402.
[45]S. Mouchawrab, L. Briand, M. Penta, “Assessing, comparing, and combining state machine-based testing and structural testing: a series of experiments,” IEEE Transactions on Software Engineering, vol. 37(2), pp. 161-187, 2011.
[46]H. Do, S. Elbaum, and G. Rothermel, “Supporting controlled experimentation with testing techniques: an infrastructure and its potential impact,” Empirical Software Engineering, vol. 10(4), pp. 405-435, 2005.
[47]C. Pacheco, S. Lahiri, M. Ernst, and T. Ball, “Feedback-directed random test generation,” in: Proceedings of the 29th international conference on Software Engineering, Minneapolis, MN, USA, 2007, pp. 75–84.
[48]S. Tokumoto, H. Yoshida, K. Sakamoto, and S. Honiden, "MuVM: Higher Order Mutation Analysis Virtual Machine for C," in: IEEE International Conference on Software Testing, Verification and Validation (ICST), Chicago, IL, USA, 2016, pp. 320-329.
[49]Q.V. Nguyen and L. Madeyski, "Addressing mutation testing problems by applying multi-objective optimization algorithms and higher order mutation," Journal of Intelligent & Fuzzy Systems, vol. 32(2), pp. 1173-1182, 2017.
[50]Q.V. Nguyen and L. Madeyski, "Empirical evaluation of multiobjective optimization algorithms searching for higher order mutants," Cybernetics and Systems, vol. 47(1-2), pp. 48–68, 2016.
[51]Q.V. Nguyen and L. Madeyski, "Higher order mutation testing to drive development of new test cases: An empirical comparison of three strategies," in: Intelligent Information and Database Systems: 8th Asian Conference, ACIIDS, Da Nang, Vietnam, 2016, pp. 235–244. Springer, Berlin Heidelberg, 2016.
[52]Q.V. Nguyen and L. Madeyski, "On the relationship between the order of mutation testing and the properties of generated higher order mutants," in: Intelligent Information and Database Systems: 8th Asian Conference, ACIIDS, Da Nang, Vietnam, 2016, pp. 245–254. Springer, Berlin Heidelberg, 2016.
[53]E. Omar, S. Ghosh, and D. Whitley, “Subtle higher order mutants,” Journal Information and Software Technology, vol. 81(C), pp. 3-18, 2017.
[54]F. Wedyan, S. Ghosh, and L. Vijayasarathy, “An Approach and Tool for Measurement of State Variable Based Data-Flow Test Coverage for Aspect-Oriented Programs”, Information and Software Technology, vol. 59, no. 3, pp. 233-254, March 2015.