Logo PTI
Polish Information Processing Society
Logo FedCSIS

Annals of Computer Science and Information Systems, Volume 11

Proceedings of the 2017 Federated Conference on Computer Science and Information Systems

Using Classification for Cost Reduction of Applying Mutation Testing


DOI: http://dx.doi.org/10.15439/2017F215

Citation: Proceedings of the 2017 Federated Conference on Computer Science and Information Systems, M. Ganzha, L. Maciaszek, M. Paprzycki (eds). ACSIS, Vol. 11, pages 99108 ()

Full text

Abstract. The paper uses machine learning methods to deal with the problem of reducing the cost of applying mutation testing. A method of classifying mutants of a program using structural similarity is proposed. To calculate such a similarity each mutant is firstly converted into a hierarchical graph, which represents the mutant's control flow, variables and conditions. Then using such a graph form graph kernels are introduced to calculate similarity among mutants.The classification algorithm is then applied for prediction. This approach helps to lower the number of mutants which have to be executed. An experimental validation of this approach is also presented.


  1. W. Afzal, R. Torkar, and R. Feldt, “A systematic review of search-based testing for non-functional system properties,” Information and Software Technology, vol. 51, no. 6, 2009, pp. 957-976.
  2. S. Ali, L. C. Briand, H. Hemmati, and R. K. Panesar-Walawege, “A systematic review of the application and empirical investigation of search-based test-case generation,” IEEE Transactions on Software Engineering, 2010, pp. 742-762
  3. V. U. B. Challagulla, F. B. Bastani, I.-L. Yen, and R. A. Paul, “Empirical assessment of machine learning based software defect prediction techniques,” International Journal on Artificial Intelligence Tools, vol. 17, no. 2,2008, pp. 389-400.
  4. J. Strug, B. Strug, “Machine learning approach in mutation testing,” LNCS, vol. 764, 2012, pp. 200-214, http://dx.doi.org/10.1007/978-3-642-34691-0_15
  5. J. Strug, B. Strug, “Classifying Mutants with Decomposition Kernel,” LNCS, vol. 9692,Springer, 2016, pp.644-654, http://dx.doi.org/10.1007/978-3-319-39378-0_55
  6. R. A. DeMillo, R. J. Lipton, F. G. Sayward, “Hints on test data selection: help for the practicing programmer,” Computer, vol. 11, no. 4, 1978, pp. 34-41, http://dx.doi.org/ 10.1109/C-M.1978.218136
  7. J. H. Andrews, L. C. Briand, Y. Labiche, “Is mutation an appropriate tool for testing experiments?,” in Proc. ICSE’05, 2005, pp. 402-411, http://dx.doi.org/10.1145/1062455.1062530
  8. M. Harman, Y. Jia, “An analysis and survey of the development of mutation testing,” IEEE Transactions Software Engineering, vol. 37, no. 5, 2011, pp. 649-678, http://dx.doi.org/10.1109/TSE.2010.62
  9. H. Agrawal, R. DeMillo, R. Hathaway, W. Hsu, W. Hsu, E. Krauser, R. J. Martin, A. Mathur, E.Spafford, “Design of mutant operators for the C programming language,” Department of Computer Science, Purdue University, Lafayette, Indiana, Technical Report SERC-TR-41-P, April, 2006.
  10. B. Aichernig, J. Auer, E. Jobstl, R. Korosec, W. Krenn, R. Schlick, B. V. Schmidt, “Model-based mutation testing of an industrial measurement device,” LNCS, vol. 8570, 2014, pp. 1-19, http://dx.doi.org /10.1007/978-3-319-09099-3_1
  11. A. Derezinska, “Object-oriented mutation to asses the quality of tests,” in Proc. of the 29th Euromicro Conference, Belek-Antalya, Turkey, 2003, pp. 417-420.
  12. R. Just, “The major mutation framework: Efficient and scalable mutation analysis for Java,” in Proc of ISSTA’14, San Jose, Bay Area, CA, 2014, pp. 433-436, http://dx.doi.org/10.1145/2610384.2628053
  13. G. Kaminski, P. Ammann, J. Offutt, “Improving logic-based testing,” Journal of Systems and Software, vol. 86, no. 8, 2013, pp. 2002-2012, http://dx.doi.org/10.1016/j.jss.2012.08.024
  14. S. Kim, J. A. Clark, J. A. McDermid, “Class mutation: mutation testing for object-oriented programs,” in Proc. Net.ObjectDays Conference on Object-Oriented Software Systems Conference’00, Erfurt, Germany, 2000, pp. 9-12.
  15. J. Strug, “Applying Mutation Testing for Assessing Test Suites Quality at Model Level,” in Proc. of FedCSIS’16, ACSIS, vol. 8, 2016, pp. 1593- 1596, http://dx.doi.org/10.15439/2016F82
  16. J. Strug, “Mutation Testing Approach to Negative Testing,” Journal of Engineering, vol. 2016, 13 pages, http://dx.doi.org/10.1155/2016/6589140
  17. A. P. Mathur, “Performance, effectiveness, and reliability issues in software testing,” in Proc. COMPSAC’91, Tokyo, Japan, 1991, pp. 604-605, http://dx.doi.org/10.1109/CMPSAC.1991.170248
  18. A. P. Mathur, E. W. Krauser, “Mutant Unification for Improved Vectorization,” Purdue University, West Lafayette, IN, Technique Repoer SERC-TR-14-P, 1988.
  19. S. Hussain, “Mutation clustering,” Master’s thesis, King’s College London, Strand, London, 2008.
  20. C. Ji, Z. Chen, B. Xu, Z. Zhao, “A novel method of mutation clustering based on domain analysis,” in Proc. of SEKE Conference’09, Boston, Massachusetts, 2009, pp. 422-425.
  21. A.T. Acree, “On mutation,” Master’s thesis, Georgia Institute of Technology, Atlanta, Georgia, 1980.
  22. T. A. Budd, “Mutation analysis of program test data,” Master’s thesis, Yale University, New Haven, Connecticut, 1980.
  23. A. P. Mathur, W. E. Wong, “An empirical comparison of mutation and data flow based test adequacy criteria,” Software Testing, Verification and Reliability, vol. 4, no. 1, 1994, pp. 9-31, http://dx.doi.org/10.1002/stvr.4370040104
  24. W. E. Wong, “On mutation and data flow,” Master’s thesis, Purdue University, West Lafayette, Indiana, 1993.
  25. R. Agrawal, T. Imielinski, A. Swami, “Mining association rules between sets of items in large databases,” in Proc. of ACM-SIGMOD’93, Washinghton, D.C, 1993, pp. 207-216, http://dx.doi.org/10.1145/170035.170072
  26. J. Han, J. Pei, Y. Yin, R. Mao, “Mining frequent patterns without candidate generation: a frequent-pattern tree approach,” Data Mining and Knowledge Discovery, vol 8, no. 1, 2004, pp. 53-87, http://dx.doi.org/10.1023/B:DAMI.0000005258.31418.83
  27. A. Inokuchi, T. Washio, H. A. Motoda, “An apriori-based algorithm for mining frequent substructures from graph data,” in Proc. of PKDD’00, Lyon, France, 2000, pp. 87-92.
  28. B. Strug, “Using co-occurring graph patterns in computer aided design evaluation,” LNCS, vol. 9120, 2015, pp. 768-777 , http://dx.doi.org/10.1007/ 978-3-319-19369-4_68
  29. H. Bunke, K. Riesen, “Recent advances in graph-based pattern recognition with applications in document analysis,” Pattern Recognition, vol. 44, no. 5, 2011, pp. 1057-1067, http://dx.doi.org/10.1016/j.patcog.2010.11.015
  30. K. Riesen, H. Bunke, “Reducing the dimensionality of dissimilarity space embedding graph kernels,” Engineering Applications of Artificial Intelligence, vol. 22, no. 1, 2009, pp. 48-56, http://dx.doi.org/10.1016/j.engappai.2008.04.006
  31. B. Scholkopf, A. J. Smola, Learning with kernels, Cambridge, MT, MIT Press, 2002.
  32. T. Gartner, Kernels for structured data, (Series in Machine Perception and Artificial Intelligence), World Scientific, 2009.
  33. H. Kashima, K. Tsuda, A. Inokuchi, “Marginalized kernels between labeled graphs,” in Proc. of ICML’03, Washington, DC, 2003, pp. 321-328.
  34. K. M. Borgwardt, H. P. Kriegel, “Shortest-path kernels on graphs,” in Proc. of ICDM’05, Houston, Texas, 2005, pp. 74-81, http://dx.doi.org/10.1109/ICDM.2005.132
  35. B. Strug, “Automatic design quality evaluation using graph similarity measures,” Automation in Construction, vol. 32, 2013, pp. 187-195, http://dx.doi.org/10.1016/j.autcon.2012.12.015
  36. M. Collins, N. Duffy, “New ranking algorithms for parsing and tagging kernels over discrete structures, and the voted perceptron,” in Proc. of ACL’02, Philadephia, Pennsylvania, July, 2002, pp. 263-270, http://dx.doi.org/10.3115/1073083.1073128
  37. D. Haussler, “Convolutional kernels on discrete structures,” Computer Science Department, UC Santa Cruz, Technical Report UCSC-CRL, 1999.
  38. K. Shin, T. Kuboyama, “A generalization of Haussler’s convolution kernel - mapping kernel and its application to tree kernels,” J. Comput. Sci. Technol, vol. 25, no. 5, 2010, pp. 1040-1054, http://dx.doi.org/10.1007/s11390-010-1082-7
  39. Y. Ma, J. Offutt, Y. R. Kwon, “Mujava: a mutation system for Java,” in Proc. ICSE’06, Shanghai, China, 2006, pp. 827-830, http://dx.doi.org/10.1145/1134285.1134425
  40. M. Chein, M.-L. Mugnier, G. Simonet, “Nested graphs: a graph-based knowledge representation model with FOL semantics,” in Proc. of KR’98, Trento, Italy, 1998, pp. 524-535.
  41. J. Strug, B. Strug, “Using structural similarity to classify tests in mutation testing,” Applied Mechanics and Materials, vol. 378, 2013, pp. 546-551, http://dx.doi.org/10.4028/www.scientific.net/AMM.378.546
  42. P. G. Frankl, S. N. Weiss, C. Hu, “All-uses vs mutation testing: an experimental comparison of effectiveness,” Journal of Systems and Software, vol. 38, no. 3, 1997, pp. 235-253, http://dx.doi.org/10.1016/S0164-1212(96)00154-9
  43. A. J. Offutt, J. Pan, K. Tewary, T. Zhang, “An experimental evaluation of data flow and mutation testing,” Software, Practice and Experience, vol. 26, no. 2, 1996, pp. 165-176, http://dx.doi.org/10.1002/(SICI)1097-024X(199602)26:2<165::AID-SPE5>3.0.CO;2-K
  44. Y.-S. Ma, Y.-R. Kwon, A. J. Offutt, “Inter-class mutation operators for Java,” in Proc. ISSRE’02, Annapolis, MD, 2002, pp. 352-366.
  45. H. Wang, I.Düntsch, G. Gediga, and G. Guo, “Nearest Neighbours without k”, In: Barbara Dunin-Keplicz, Andrzej Jankowski, Andrzej Skowron, and Marcin Szczuka, editors, Monitoring, Security, and Rescue Techniques in Multiagent Systems, Advances in Soft Computing, vol. 28, 2005, pp 179-189, http://dx.doi.org/10.1007/3-540-32370-8_12.