Reducing the Number of Higher-order Mutants with the Aid of Data Flow

• Autorzy: Ghiduk A. S.

Identyfikatory

DOI

10.5277/e-Inf160102

• Języki publikacji: EN

Abstrakty

EN

Higher-order mutants are created by injecting two or more mutations into the original program, while first-order mutants are generated by seeding single faults in the original program. Mutant generation is a key stage of mutation testing which is computationally very expensive, especially in the case of higher-order mutants. Although many mutation testing techniques have been developed to construct the first-order mutants, a very small number of techniques have been presented to generate the higher-order mutants because of the exponential growth of the number of higher-order mutants, and the coupling effect between higher-order and first-order mutants. To overcome the exponential explosion in the number of higher-order mutants considered, this paper introduces a new technique for generating a reduced set of higher-order mutants. The proposed technique utilizes a data-flow analysis to decrease the number of mutation points through the program under test and consequently reduce the number of higher-order mutants. In this technique only positions of defs and uses are considered as locations to seed the mutation. The generated set of higher-order mutants consists of a reduced number of mutants, which reduces the costs of higher-order mutation testing. In addition, the proposed technique can generate the higher-order mutants directly without generating the first-order mutants or by combining two or more first-order mutants. A set of experiments are conducted to evaluate the effectiveness of the proposed technique. The results of the conducted experiments are presented and compared with the results of the related work. These results showed that the proposed technique is more effective than the earlier techniques in generating higher-order mutants without affecting the efficiency of mutation testing.

Słowa kluczowe

EN

mutation testing; first-order mutants; higher-order mutants; data-flow analysis

• Wydawca: Oficyna Wydawnicza Politechniki Wrocławskiej
• Czasopismo: e-Informatica Software Engineering Journal
• Rocznik: 2016
• Tom: Vol. 10, nr 1
• Strony: 31--49
• Opis fizyczny: Bibliogr. 67 poz., tab., rys.

Twórcy

autor

Ghiduk A. S.

• Dept. of IT, Col lege of Computers and Information Technology, Taif University, Saudi Arabia, Department of Mathematics and Computer Science, Faculty of Science, Beni-Suef University, Egypt

Bibliografia

• [1] Y. Jia and M. Harman, “Higher order mutation testing,” Inf. Softw. Technol., Vol. 51, No. 10, Oct. 2009, pp. 1379–1393. [Online]. http://dx.doi.org/10.1016/j.infsof.2009.04.016
• [2] W.B. Langdon, M. Harman, and Y. Jia, “Efficient multi-objective higher order mutation testing with genetic programming,” J. Syst. Softw., Vol. 83, No. 12, Dec. 2010, pp. 2416–2430. [Online]. http://dx.doi.org/10.1016/j.jss.2010.07.027
• [3] R.A. DeMillo, R.J. Lipton, and F.G. Say- ward, “Hints on test data selection: Help for the practicing programmer,” Computer, Vol. 11, No. 4, Apr. 1978, pp. 34–41. [Online]. http://dx.doi.org/10.1109/C-M.1978.218136
• [4] R.G. Hamlet, “Testing programs with the aid of a compiler,” IEEE Transactions on Software Engineering, Vol. SE-3, No. 4, July 1977, pp. 279–290.
• [5] K. Ayari, S. Bouktif, and G. Antoniol, “Automatic mutation test input data generation via ant colony,” in Proceedings of the 9th Annual Conference on Genetic and Evolutionary Computation, ser. GECCO ’07. New York, NY, USA: ACM, 2007, pp. 1074–1081. [Online]. http://doi.acm.org/10.1145/1276958.1277172
• [6] W.E. Howden, “Weak mutation testing and com- pleteness of test sets,” IEEE Transactions on Software Engineering, Vol. SE-8, No. 4, July
• 1982, pp. 371–379.
• [7] Q.V. Nguyen and L. Madeyski, Advanced Computational Methods for Knowledge Engineering: Proceedings of the 2nd International Conference on Computer Science, Applied Mathematics and Applications (ICCSAMA 2014). Cham: Springer International Publishing, 2014, ch. Problems of Mutation Testing and Higher Order Mutation Testing, pp. 157–172. [Online]. http://dx.doi.org/10.1007/978-3-319-06569-4_12
• [8] M. Kintis, M. Papadakis, and N. Malevris, “Isolating first order equivalent mutants via second order mutation,” in IEEE Fifth International Conference on Software Testing, Verification and Validation (ICST), April 2012, pp. 701–710.
• [9] L. Madeyski, W. Orzeszyna, R. Torkar, and M. Józala, “Overcoming the equivalent mutant problem: A systematic literature review and a comparative experiment of second order mutation,” IEEE Transactions on Software Engineering, Vol. 40, No. 1, Jan 2014, pp. 23–42.
• [10] A.T. Acree, “On mutation,” Ph.D. dissertation, Georgia Inst of Tech Atlanta School of Information and Computer Science, Aug 1980.
• [11] T.A. Budd, “Mutation analysis of program test data,” Ph.D. dissertation, Yale Univ, 1980.
• [12] I. Bluemke and K. Kulesza, New Results in Dependability and Computer Systems: Proceedings of the 8th International Conference on Dependability and Complex Systems DepCoS-RELCOMEX, September 9-13, 2013, Brunów, Poland. Heidelberg: Springer International Publishing, 2013, ch. Reduction of Computational Cost in Mutation Testing by Sampling Mutants, pp. 41–51. [Online]. http://dx.doi.org/10.1007/978-3-319-00945-2_4
• [13] H. Agrawal, R.A. DeMillo, R. Hathaway, W.M. Hsu, W. Hsu, E. Krauser, R.J. Martin, A.P. Mathur, and E. Spafford, “Design of mutant operators for the C programming language,” Software Eng. Research Center, Computer Science Dept., Purdue Univ., Technical Report SERC-TR-41-P, 1989.
• [14] A.P. Mathur, “Performance, effectiveness, and reliability issues in software testing,” in Computer Software and Applications Conference, 1991. COMPSAC ’91., Proceedings of the Fifteenth Annual International, Sep 1991, pp. 604 – 605.
• [15] K.N. King and A.J. Offutt, “A fortran language system for mutation-based software testing,” Softw. Pract. Exper., Vol. 21, No. 7, Jun. 1991, pp. 685–718. [Online]. http://dx.doi.org/10.1002/spe.4380210704
• [16] A.J. Offutt, G. Rothermel, and C. Zapf, “An experimental evaluation of selective mutation,” in Software Engineering, 1993. Proceedings., 15th International Conference on, May 1993, pp. 100–107.
• [17] S. Hussain, “Mutation clustering,” Master’s thesis, King’s College London, 2008.
• [18] A.J. Offutt, “Investigations of the software testing coupling effect,” ACM Trans. Softw. Eng. Methodol., Vol. 1, No. 1, Jan. 1992, pp. 5–20. [Online]. http: //doi.acm.org/10.1145/125489.125473
• [19] M. Kintis, M. Papadakis, and N. Malevris, “Eval- uating mutation testing alternatives: A collateral experiment,” in Software Engineering Con- ference (APSEC), 2010 17th Asia Pacific, Nov 2010, pp. 300–309.
• [20] M. Polo, M. Piattini, and I. García-Rodríguez, “Decreasing the cost of mutation testing with second-order mutants,” Softw. Test. Verif. Reliab., Vol. 19, 2009, pp. 111–131.
• [21] M. Harman, Y. Jia, and W.B. Langdon, “A manifesto for higher order mutation testing,” in Software Testing, Verification, and Validation Workshops (ICSTW), 2010 Third International Conference on, April 2010, pp. 80–89.
• [22] Y. Jia and M. Harman, “Constructing subtle faults using higher order mutation testing,” in Eighth IEEE International Working Conference onSource Code Analysis and Manipulation, Sept 2008, pp. 249–258.
• [23] P.M. Herman, “A data flow analysis approach to program testing,” Australian Computer Journal, Vol. 8, No. 3, 1976, pp. 92–96.
• [24] S. Rapps and E.J. Weyuker, “Selecting soft- ware test data using data flow information,” IEEE Transactions on Software Engineering, Vol. SE-11, No. 4, April 1985, pp. 367–375.
• [25] P.G. Frankl and E.J. Weyuker, “An applicable family of data flow testing criteria,” IEEE Trans- actions on Software Engineering, Vol. 14, No. 10, Oct 1988, pp. 1483–1498.
• [26] A.S. Ghiduk, M.J. Harrold, and M.R. Girgis, “Using genetic algorithms to aid test-data generation for data-flow coverage,” in Software Engineering Conference, 2007. APSEC 2007. 14th Asia-Pacific, Dec 2007, pp. 41–48.
• [27] I. Burnstein, Practical Software Testing, 1st ed. Springer Science+Business Media New York: Springer Professional Computing, 2003, ch. A Process-Oriented Approach.
• [28] M. Papadakis and N. Malevris, “Automatically performing weak mutation with the aid of symbolic execution, concolic testing and search-based testing,” Software Quality Journal, Vol. 19, No. 4, Dec. 2011, pp. 691–723. [Online]. http://dx.doi.org/10.1007/s11219-011-9142-y
• [29] M.S. Hecht, Flow Analysis of Computer Pro- grams. New York, NY, USA: Elsevier Science Inc., 1977.
• [30] S. Rapps and E.J. Weyuker, “Data flow analysis techniques for test data selection,” in Proceedings of the 6th International Conference on Software Engineering, ser. ICSE ’82. Los Alamitos, CA, USA: IEEE Computer Society Press, 1982, pp. 272–278. [Online]. http://dl.acm.org/citation.cfm?id=800254.807769
• [31] F.E. Allen and J. Cocke, “A program data flow analysis procedure,” Commun. ACM, Vol. 19, No. 3, Mar. 1976, p. 137. [Online]. http://doi.acm.org/10.1145/360018.360025
• [32] B.H. Smith and L. Williams, “On guiding the augmentation of an automated test suite via mutation analysis,” Empirical Softw. Engg., Vol. 14, No. 3, Jun. 2009, pp. 341–369. [Online]. http://dx.doi.org/10.1007/s10664-008-9083-7
• [33] B.H. Smith and L. Williams, “An empirical evaluation of the muJava mutation operators,” in Testing: Academic and Industrial Conference Practice and Research Techniques - MUTATION, 2007. TAICPART-MUTATION 2007, Sept 2007, pp. 193–202.
• [34] Y.S. Ma and J. Offutt, “Description of method-level mutation operators for Java,” 2005. [Online]. https://cs.gmu.edu/~offutt/mujava/ mutopsMethod.pdf
• [35] P. May, J. Timmis, and K. Mander, Artificial Immune Systems: 6th International Conference, ICARIS 2007, Santos, Brazil, August 26-29, 2007. Proceedings. Berlin, Heidelberg: Springer Berlin Heidelberg, 2007, ch. Immune and Evolutionary Approaches to Software Mutation Testing, pp. 336–347. [Online]. http://dx.doi.org/10.1007/978-3-540-73922-7_29
• [36] C.C. Michael, G. McGraw, and M.A. Schatz, “Generating software test data by evolution,” IEEE Transactions on Software Engineering, Vol. 27, No. 12, Dec. 2001, pp. 1085–1110. [Online]. http://dx.doi.org/10.1109/32.988709
• [37] R.P. Pargas, M.J. Harrold, and R. Peck, “Test-data generation using genetic algorithms,” Softw. Test., Verif. Reliab., Vol. 9, No. 4, 1999, pp. 263–282. [Online]. http://dx.doi.org/10.1002/(SICI)1099-1689(199912)9:4<263::AID- STVR190>3.0.CO;2-Y
• [38] Y. Jia and M. Harman, “An analysis and survey of the development of mutation testing,” IEEE Transactions on Software Engineering, Vol. 37, No. 5, Sept 2011, pp. 649–678.
• [39] T.A. Budd, R.J. Lipton, R. DeMillo, and F. Say- ward, “The design of a prototype mutation system for program testing,” in Proceedings NCC, AFIPS Conference Records, 1978, pp. 623–627.
• [40] T.A. Budd, R.A. DeMillo, R.J. Lipton, and F.G. Sayward, “Theoretical and empirical studies on using program mutation to test the functional correctness of programs,” in Proceedings of the 7th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, ser. POPL ’80. New York, NY, USA: ACM, 1980, pp. 220–233. [Online]. http://doi.acm.org/10.1145/567446.567468
• [41] A. J.Offutt and K.N. King, “A FORTRAN 77 in- terpreter for mutation analysis,” SIGPLAN Not., Vol. 22, No. 7, Jul. 1987, pp. 177–188. [Online]. http://doi.acm.org/10.1145/960114.29669
• [42] J. Bowser, “Reference manual for Ada mutant operators,” Georgia Inst. of Technology, Technical Report GIT-SERC-88/02, 1988.
• [43] A.J. Offutta, J. Voas, and J. Payn, “Mutation operators for Ada,” George Mason Univ., Technical Report ISSE-TR-96-09, 1996.
• [44] S. Kim, J.A. Clark, and J.A. McDermid, “The rigorous generation of Java mutation operators using HAZOP,” in 12th International Conf. Software and Systems Eng. and Their Applications, 1999.
• [45] Y.S. Ma, Y.R. Kwon, and J. Offutt, “Inter-class mutation operators for Java,” in Software Reliability Engineering, 2002. ISSRE 2003. Proceedings. 13th International Symposium on, 2002, pp.352–363.
• [46] R.T. Alexander, J.M. Bieman, S. Ghosh, and B. Ji, “Mutation of Java objects,” in Proceedings of the 13th International Symposium on Software Reliability Engineering, 2002, pp. 341–351.
• [47] J.S. Bradbury, J.R. Cordy, and J. Dingel, “Mu- tation operators for concurrent Java (J2SE 5.0),” in Mutation Analysis, 2006. Second Workshop on, Nov 2006, p. 11.
• [48] A. Derezińska, Software Engineering Techniques: Design for Quality. Boston, MA: Springer US, 2007, ch. Advanced mutation operators applicable in C# programs, pp. 283–288. [Online]. http://dx.doi.org/10.1007/978-0-387-39388-9_27
• [49] A. Derezinska, “Quality assessment of mutation operators dedicated for C# programs,” in Qual- ity Software, 2006. QSIC 2006. Sixth International Conference on, Oct 2006, pp. 227–234.
• [50] F.C. Ferrari, J.C. Maldonado, and A. Rashid, “Mutation testing for aspect-oriented programs,” in Software Testing, Verification, and Validation, 2008 1st International Conference on, April 2008, pp. 52–61.
• [51] P. Anbalagan and T. Xie, “Efficient mutant generation for mutation testing of pointcuts in aspect-oriented programs,” in Proceedings of the Second Workshop on Mutation Analysis, ser. MUTATION ’06. Washington, DC, USA: IEEE Computer Society, 2006, p. 3. [Online]. http://dx.doi.org/10.1109/MUTATION.2006.3
• [52] P. Anbalagan and T. Xie, “Automated genera- tion of pointcut mutants for testing pointcuts in AspectJ programs,” in 19th International Sympo- sium on Software Reliability Engineering, 2008. ISSRE 2008., Nov 2008, pp. 239–248.
• [53] A.J. Offutt and R.H. Untch, “Mutation testing for the new century,” W.E. Wong, Ed. Norwell, MA, USA: Kluwer Academic Publishers, 2001, ch. Mutation 2000: Uniting the Orthogonal, pp. 34–44. [Online]. http://dl.acm.org/citation.cfm?id=571305.571314 [54] A.P. Mathur and W.E. Wong, “An empirical comparison of data flow and mutation-based test adequacy criteria,” Soft- ware Testing, Verification and Reliability, Vol. 4, No. 1, 1994, pp. 9–31. [Online]. http://dx.doi.org/10.1002/stvr.4370040104
• [55] C. Ji, Z. Chen, B. Xu, and Z. Zhao, “A novel method of mutation clustering based on domain analysis,” in Proceedings of the 21st International Conference on Software Engineering & Knowledge Engineering (SEKE’2009), Boston, Massachusetts, USA, July 1-3, 2009, 2009, pp.422–425.
• [56] A.S. Namin and J.H. Andrews, “Finding sufficient mutation operators via variable reduction,” in Proceedings of the Second Workshop on Mutation Analysis, ser. MUTA- TION ’06. Washington, DC, USA: IEEE Computer Society, 2006, p. 5. [Online]. http://dx.doi.org/10.1109/MUTATION.2006.7
• [57] A.S. Namin and J.H. Andrews, “On sufficiency of mutants,” in Companion to the Proceedings of the 29th International Conference on Software Engineering, ser. ICSE COMPANION ’07. Washington, DC, USA: IEEE Computer Society, 2007, pp. 73–74. [Online]. http://dx.doi.org/10.1109/ICSECOMPANION.2007.56
• [58] W.E. Wong, “On mutation and data flow,” Ph.D. dissertation, West Lafayette, IN, USA, 1993, uMI Order No. GAX94-20921.
• [59] W.E. Wong and A.P. Mathur, “Reducing the cost of mutation testing: An empirical study,” J. Syst. Softw., Vol. 31, No. 3, Dec. 1995, pp. 185–196. [Online]. http://dx.doi.org/10.1016/0164-1212(94)00098-0
• [60] A.J. Offutt, A. Lee, G. Rothermel, R.H. Untch, and C. Zapf, “An experimental de- termination of sufficient mutant operators,” ACM Trans. Softw. Eng. Methodol., Vol. 5, No. 2, Apr. 1996, pp. 99–118. [Online]. http://doi.acm.org/10.1145/227607.227610
• [61] E.S. Mresa and L. Bottaci, “Efficiency of mutation operators and selective mutation strategies: an empirical study,” Software Testing, Verification and Reliability, Vol. 9, No. 4, 1999, pp. 205–232. [Online]. http://dx.doi.org/10.1002/(SICI)1099-1689(199912)9:4<205::AID- STVR186>3.0.CO;2-X
• [62] W.B. Langdon, M. Harman, and Y. Jia, “Multi objective higher order mutation testing with genetic programming,” in Testing: Academic and Industrial Conference - Practice and Research Techniques, 2009. TAIC PART ’09, Sept 2009, pp. 21–29.
• [63] M.R. Girgis and M.R. Woodward, “An integrated system for program testing using weak mutation and data flow analysis,” in Proceedings of the 8th International Conference on Software Engineering, ser. ICSE ’85. Los Alamitos, CA, USA: IEEE Computer Society Press, 1985, pp. 313–319. [Online]. http://dl.acm.org/citation.cfm?id=319568.319662
• [64] A.C. Marshall, D. Hedley, I.J. Riddell, and M.A.Hennell, “Static dataflow-aided weak mutation analysis (sdawm),” Inf. Softw. Technol., Vol. 32, No. 1, Jan. 1990, pp. 99–104. [Online]. http://dx.doi.org/10.1016/0950-5849(90)90053-T
• [65] A.J. Offutt and K. Tewary, “Empirical compar- isons of data flow and mutation testing,” 1992.
• [66] W.E. Wong and A.P. Mathur, “Fault detection effectiveness of mutation and data flow testing,” Software Quality Journal, Vol. 4, No. 1, pp. 69–83. [Online]. http://dx.doi.org/10.1007/BF00404650
• [67] S. Kakarla, S. Momotaz, and A.S. Namin, “An evaluation of mutation and data-flow testing: A meta-analysis,” in IEEE Fourth International Conference on Software Testing, Verification and Validation Workshops (ICSTW), March 2011, pp.366–375. e-Informatica Software Engineering Journal, Volume 10, Issue 1, 2016, pages: 69–87,