Mutant selection by using Fourier expansion

takan, savaş; Allmer, Jens

doi:10.3906/elk-1909-90

Mutant selection by using Fourier expansion

Savas TAKAN, (Bilgisayar Mühendisliği Bölümü, Mühendislik Fakültesi, İzmir Yüksek Teknoloji Enstitüsü, İzmir, Türkiye)

Tolga AYAV (Bilgisayar Mühendisliği Bölümü, Mühendislik Fakültesi, İzmir Yüksek Teknoloji Enstitüsü, İzmir, Türkiye)

Turkish Journal of Electrical Engineering and Computer Sciences

1 0

Yıl: 2020 Cilt: 28 Sayı: 5 Sayfa Aralığı: 2750 - 2767 Metin Dili: İngilizce DOI: 10.3906/elk-1909-90 İndeks Tarihi: 04-06-2022

Mutant selection by using Fourier expansion

Öz:

Mutation analysis is a widely used technique to evaluate the effectiveness of test cases in both hardware and software testing. The original model is mutated systematically under certain fault assumptions and test cases are checked against the mutants created to see whether the test cases can detect the faults or not. Mutation analysis is usually a computationally intensive task, particularly in finite state machine (FSM) testing due to a possibly huge amount of mutants. Random selection could be a practical reduction method under the assumption that each mutant is identical in terms of the probability of occurrence of its associating fault. The present study proposes a mutant selection method based on Fourier analysis of Boolean functions. Fourier helps to identify the most effective transitions on the output so that the mutants related to those transitions can be selected. Such mutants are considered more important since they are more likely to be killed. To evaluate the method, test cases are generated by the well-known W method, which has the capability of detecting every potential fault. The original and reduced sets of mutants are compared with respect to their importance values. Evaluations show that the mutants selected by the proposed technique are more effective, which reduces the cost of mutation analysis without sacrificing the performance of the mutation analysis

Anahtar Kelime:

Belge Türü: Makale Makale Türü: Araştırma Makalesi Erişim Türü: Erişime Açık

1] Mathur AP. Foundations of Software Testing, 2/e. India: Pearson Education, 2013.
[2] Lee D, Yannakakis M. Principles and methods of testing finite state machines-a survey. Proceedings of the IEEE. 1996; 84 (8): 1090-1123.
[3] Endo AT, Simao A. Evaluating test suite characteristics, cost, and effectiveness of FSM-based testing methods. Information and Software Technology 2013; 55 (6): 1045-1062.
[4] Belli F, Beyazıt M, Endo AT, Mathur A, Simao A. Fault domain-based testing in imperfect situations: a heuristic approach and case studies. Software Quality Journal 2015; 23 (3): 423-452.
[5] Fragal VH, Simao A, Mousavi MR, Turker UC. Extending hsi test generation method for software product lines. The Computer Journal 2019; 62 (1): 109-129.
[6] Damasceno CDN, Masiero PC, Simao A. Evaluating test characteristics and effectiveness of fsm-based testing methods on rbac systems. In: Proceedings of the 30th Brazilian Symposium on Software Engineering; Rio de Janerio, Brazil; 2016. pp. 83-92.
[7] Naito S. Fault detection for sequential machines by transition tours. In: Processing of 11th IEEE International Sympiosium on Fault Tolerant Computing (FTCS-11); New York, NY, USA; 1981. pp. 238-243.
[8] Chow TS. Testing software design modeled by finite-state machines. IEEE Transactions on Software Engineering 1978; 4 (3): 178-187.
[9] Fujiwara S, Bochmann Gv, Khendek F, Amalou M, Ghedamsi A. Test selection based on finite state models. IEEE Transactions on Software Engineering 1991; 17 (6): 591-603.
[10] Sabnani K, Dahbura A. A protocol test generation procedure. Computer Networks and ISDN Systems 1988; 15 (4): 285-297.
[11] Vuong ST. The UIOv-method for protocol test sequence generation. In: Processing of 2nd IFIP International Workshop on Protocol Test Systems (IWPTS’89); Berlin, Germany; 1989. pp. 161-175.
[12] Gonenc G. A method for the design of fault detection experiments. IEEE Transactions on Computers 1970; 100 (6): 551-558.
[13] Petrenko A, Yevtushenko N. Testing from partial deterministic FSM specifications. IEEE Transactions on Comput- ers 2005; 54 (9): 1154-1165.
[14] Petrenko A. Nondeterministic state machine in protocol conformance testing. In: Processing of the 6th International Workshop on Protocol Test systems (IWPTS); Pau, France; 1993. pp. 363-378.
[15] Dorofeeva M, Koufareva I. Novel modification of the W-method. Bulletin of the Novosibirsk Computing Center Series: Computer Science 2002; 1 (18): 69-80.
[16] Papadakis M, Kintis M, Zhang J, Jia Y, Le Traon Y et al. Mutation testing advances: An analysis and survey. In: Memon AM (editor). Advances in Computers. Amsterdam, Netherlands: Elsevier Science Press, 2019, pp. 275-378.
[17] Pizzoleto AV, Ferrari FC, Offutt J, Fernandes L, Ribeiro M. A systematic literature review of techniques and metrics to reduce the cost of mutation testing. Journal of Systems and Software 2019; 157: 110388.
[18] Fabbri SCPF, Maldonado JC, Delamaro M. Proteum/FSM: A tool to support finite state machine validation based on mutation testing. In: Processing of the 19th International Conference of the Chilean Computer Science Society IEEE (SCCC’99); Talca, Chile; 1999. pp. 96-104
19] Maldonado JC, Delamaro ME, Fabbri SC, Da Silva Simao A, Sugeta T et al. Proteum: A family of tools to support specification and program testing based on mutation. In: Wong WE (editor). Mutation Testing for the New Century. Boston, MA, USA: Springer, 2001, pp. 113-116.
[20] Fabbri SPF, Delamaro ME, Maldonado JC, Masiero PC. Mutation analysis testing for finite state machines. In: Proceedings of 1994 IEEE International Symposium on Software Reliability Engineering; Monterey, CA, USA; 1994. pp. 220-229.
[21] Da Silva Simao A, Ambrosio AM, Fabbri SCPF, Do Amaral ASMS, Martins E et al. Plavis/FSM: an environment to integrate FSM-based testing tools. In: Processing of Tool Session of 19th Brazilian Symposium on Software Engineering; Uberlândia, MG, Brazil; 2005. pp. 1-6.
[22] Li Jh, Dai Gx, Li Hh. Mutation analysis for testing finite state machines. In: Proceedings of The 2nd IEEE International Symposium on Electronic Commerce and Security (ISECS); Nanchang City, China; 2009. pp. 620- 624.
[23] Petrenko A, Timo ON, Ramesh S. Multiple mutation testing from FSM. In: Proceedings of the International Conference on Formal Techniques for Distributed Objects, Components, and Systems; Heraklion, Greece; 2016. pp. 222-238.
[24] Timo ON, Petrenko A, Ramesh S. Multiple mutation testing from finite state machines with symbolic inputs. In: Proceedings of the 19th IFIP International Conference on Testing Software and Systems; St. Petersburg, Russia; 2017. pp. 108-125.
[25] Jia Y, Harman M. An analysis and survey of the development of mutation testing. IEEE Transactions on Software Engineering 2010; 37 (5): 649-678.
[26] Silva RA, De Souza SdRS, De Souza PSL. A systematic review on search based mutation testing. Information and Software Technology 2017; 81: 19-35.
[27] Ferrari FC, Pizzoleto AV, Offutt J. A systematic review of cost reduction techniques for mutation testing: Pre- liminary results. In: Proceedings of the IEEE 11th International Conference on Software Testing, Verification and Validation Workshops (ICST); Vasteras, Sweden; 2018. pp. 1-10.
[28] Petrovic G, Ivankovic M. State of mutation testing at Google. In: Proceedings of the 40th International Conference on Software Engineering: Software Engineering in Practice; Gothenburg, Sweden; 2018. pp. 163-171.
[29] Zhu Q, Panichella A, Zaidman A. An investigation of compression techniques to speed up mutation testing. In: Proceedings of the IEEE 11th International Conference on Software Testing, Verification and Validation (ICST); Vasteras, Sweden; 2018. pp. 274-284.
[30] McMinn P, Wright CJ, McCurdy CJ, Kapfhammer GM. Automatic detection and removal of ineffective mutants for the mutation analysis of relational database schemas. IEEE Transactions on Software Engineering 2017; 45 (5): 427-463.
[31] Acree Jr AT. On mutation. PhD, Georgia Institute of Technology, North Avenue, Atlanta, USA, 1980.
[32] Mathur AP, Wong WE. An empirical comparison of data ow and mutation-based test adequacy criteria. Software Testing, Verification and Reliability 1994; 4 (1): 9-31.
[33] Zhang L, Hou SS, Hu JJ, Xie T, Mei H. Is operator-based mutant selection superior to random mutant selection? In: Proceedings of the 32nd ACM/IEEE International Conference on Software Engineering; Cape Town, South Africa; 2010. pp. 435-444.
[34] Derezinska A, Rudnik M. Evaluation of mutant sampling criteria in object-oriented mutation testing. In: Proceed- ings of the 2017 Federated Conference on Computer Science and Information Systems (FedCSIS), IEEE; Prague, Czech Republic; 2017. pp. 1315-1324.
[35] Mathur AP. Performance, effectiveness, and reliability issues in software testing. In: Proceedings of the 15th Annual International Computer Software & Applications Conference, IEEE; Tokio, Japan; 1991. pp. 604-605.
36] Offutt AJ, Rothermel G, Zapf C. An experimental evaluation of selective mutation. In: Proceedings of the 15th International Conference on Software Engineering, IEEE; Baltimore, MD, USA; 1993. pp. 100-107.
[37] Wong WE, Mathur AP. Reducing the cost of mutation testing: An empirical study. Journal of Systems and Software 1995; 31 (3): 185-196.
[38] Offutt AJ, Lee A, Rothermel G, Untch RH, Zapf C. An experimental determination of sufficient mutant operators. ACM Transactions on Software Engineering and Methodology (TOSEM) 1996; 5 (2): 99-118.
[39] Namin AS, Andrews J, Murdoch D. Sufficient mutation operators for measuring test effectiveness. In: Proceedings of the ACM/IEEE 30th International Conference on Software Engineering. IEEE; Leipzig, Germany; 2008. pp. 351-360.
[40] Vincenzi AMR, Maldonado JC, Barbosa EF, Delamaro ME. Unit and integration testing strategies for C programs using mutation. Software Testing, Verification and Reliability 2001; 11 (4): 249-268.
[41] Just R, Schweiggert F. Higher accuracy and lower run time: efficient mutation analysis using non-redundant mutation operators. Software Testing, Verification and Reliability 2015; 25 (5-7): 490-507.
[42] Delamaro ME, Deng L, Durelli VHS, Li N, Offutt J. Experimental evaluation of SDL and one-op mutation for C. In: Proceedings of the 7th IEEE International Conference on Software Testing, Verification and Validation; Ohio, USA; 2014. pp. 203-212.
[43] Jia Y, Harman M. Constructing subtle faults using higher order mutation testing. In: Proceedings of the 8th IEEE International Working Conference on Source Code Analysis and Manipulation; Beijing, China; 2008. pp. 249-258.
[44] Polo M, Piattini M, Garcia-Rodriguez I. Decreasing the cost of mutation testing with second-order mutants. Software Testing, Verification and Reliability 2009; 19 (2): 111-131.
[45] Papadakis M, Malevris N. An empirical evaluation of the first and second order mutation testing strategies. In: Proceedings of the 3th IEEE International Conference on Software Testing, Verification, and Validation Workshops; Paris, France; 2010. pp. 90-99.
[46] Harman M, Jia Y, Reales Mateo P, Polo M. Angels and monsters: An empirical investigation of potential test effectiveness and efficiency improvement from strongly subsuming higher order mutation. In: Proceedings of the 29th ACM/IEEE international Conference on Automated Software Engineering; Vasteras, Sweden; 2014. pp. 397- 408.
[47] Offutt AJ. A practical system for mutation testing: Help for the common programmer. In: Proceedings of the International Test Conference, IEEE; Washington, DC, USA; 1994. pp. 824-830.
[48] Hierons R, Harman M, Danicic S. Using program slicing to assist in the detection of equivalent mutants. Software Testing, Verification and Reliability 1999; 9 (4): 233-262.
[49] Yao X, Harman M, Jia Y. A study of equivalent and stubborn mutation operators using human analysis of equivalence. In: Proceedings of the 36th International Conference on Software Engineering; Hyderabad, India; 2014. pp. 919-930.
[50] Papadakis M, Delamaro M, Le Traon Y. Mitigating the effects of equivalent mutants with mutant classification strategies. Science of Computer Programming 2014; 95: 298-319.
[51] Kintis M, Papadakis M, Malevris N. Employing second-order mutation for isolating first-order equivalent mutants. Software Testing, Verification and Reliability 2015; 25 (5-7): 508-535.
[52] Papadakis M, Jia Y, Harman M, Le Traon Y. Trivial compiler equivalence: A large scale empirical study of a simple, fast and effective equivalent mutant detection technique. In: Proceedings of the 37th IEEE International Conference on Software Engineering; Florence, Italy; 2015. pp. 936-946.
[53] Kintis M, Papadakis M, Jia Y, Malevris N, Le Traon Y et al. Detecting trivial mutant equivalences via compiler optimisations. IEEE Transactions on Software Engineering 2017; 44 (4): 308-333.
[54] König H. Protocol Engineering. Heidelberg, Germany: Springer, 2012.
55] Papadakis M, Just R. Special issue on Mutation Testing. Information and Software Technology 2017; 81:1-2.
[56] Zhang J, Zhang L, Harman M, Hao D, Jia Y et al. Predictive mutation testing. IEEE Transactions on Software Engineering 2018; 45 (9): 898-918.
[57] Aichernig BK, Tappler M. Learning from faults: Mutation testing in active automata learning. In: Proceedings of the NASA Formal Methods Symposium; Moffett Field, CA, USA; 2017. pp. 19-34.
[58] O’Donnell R. Analysis of boolean functions. Cambridge, UK: Cambridge University Press, 2014.
[59] De Wolf R. A brief introduction to Fourier analysis on the Boolean cube. Theory of Computing 2008; 1-20.

APA	takan s, Allmer J (2020). Mutant selection by using Fourier expansion. , 2750 - 2767. 10.3906/elk-1909-90
Chicago	takan savaş,Allmer Jens Mutant selection by using Fourier expansion. (2020): 2750 - 2767. 10.3906/elk-1909-90
MLA	takan savaş,Allmer Jens Mutant selection by using Fourier expansion. , 2020, ss.2750 - 2767. 10.3906/elk-1909-90
AMA	takan s,Allmer J Mutant selection by using Fourier expansion. . 2020; 2750 - 2767. 10.3906/elk-1909-90
Vancouver	takan s,Allmer J Mutant selection by using Fourier expansion. . 2020; 2750 - 2767. 10.3906/elk-1909-90
IEEE	takan s,Allmer J "Mutant selection by using Fourier expansion." , ss.2750 - 2767, 2020. 10.3906/elk-1909-90
ISNAD	takan, savaş - Allmer, Jens. "Mutant selection by using Fourier expansion". (2020), 2750-2767. https://doi.org/10.3906/elk-1909-90

APA	takan s, Allmer J (2020). Mutant selection by using Fourier expansion. Turkish Journal of Electrical Engineering and Computer Sciences, 28(5), 2750 - 2767. 10.3906/elk-1909-90
Chicago	takan savaş,Allmer Jens Mutant selection by using Fourier expansion. Turkish Journal of Electrical Engineering and Computer Sciences 28, no.5 (2020): 2750 - 2767. 10.3906/elk-1909-90
MLA	takan savaş,Allmer Jens Mutant selection by using Fourier expansion. Turkish Journal of Electrical Engineering and Computer Sciences, vol.28, no.5, 2020, ss.2750 - 2767. 10.3906/elk-1909-90
AMA	takan s,Allmer J Mutant selection by using Fourier expansion. Turkish Journal of Electrical Engineering and Computer Sciences. 2020; 28(5): 2750 - 2767. 10.3906/elk-1909-90
Vancouver	takan s,Allmer J Mutant selection by using Fourier expansion. Turkish Journal of Electrical Engineering and Computer Sciences. 2020; 28(5): 2750 - 2767. 10.3906/elk-1909-90
IEEE	takan s,Allmer J "Mutant selection by using Fourier expansion." Turkish Journal of Electrical Engineering and Computer Sciences, 28, ss.2750 - 2767, 2020. 10.3906/elk-1909-90
ISNAD	takan, savaş - Allmer, Jens. "Mutant selection by using Fourier expansion". Turkish Journal of Electrical Engineering and Computer Sciences 28/5 (2020), 2750-2767. https://doi.org/10.3906/elk-1909-90