基于SOM神经网络的二阶变异体约简方法
|
摘要
二阶变异测试通过向源程序中人工注入两个缺陷来模拟程序实际的复杂缺陷,在软件测试中具有重要意义.但由一阶变异体组合形成二阶变异体后数量会急剧增长,极大地增加了程序的执行开销.为了减少二阶变异体数量,降低程序的执行开销,提出一种基于SOM神经网络的二阶变异体约简方法.该方法首先采用较为全面的二阶变异体错误组合策略,对一阶变异体组合形成二阶变异体;然后,根据二阶变异体执行过程中的中间值相似性,进行基于SOM神经网络的变异体聚类.使用经典的基准程序和开源程序进行了方法的验证,实验结果表明,一方面,使用错误覆盖更为全面的组合策略能够充分模拟程序的复杂缺陷,聚类约简后,二阶变异体的个数在极大减少的同时,二阶变异充分度和一阶变异充分度更加接近,但是因为执行的二阶变异体数目明显降低,从而使得运行聚类后的二阶变异体时间开销明显比执行全部二阶变异体降低;另一方面,实验过程发现了有利于增加测试组件的隐藏二阶变异体.
Second-order mutation testing simulates the actual complex defects in the original program by manually injecting two defects into the original program, which is of great significance in the mutation testing. However, the number of second-order mutants formed by the combination of first-order mutants will greatly increase, which will bring large execution costs. In order to reduce the number of second-order mutants and reduce the time consumption in the running procedure, this study proposes a method of second-order mutant reduction based on SOM neural network. The proposed method firstly utilizes a morecomprehensive combination strategy to generate feasible second order mutants based on traditional first-order mutant generation, and then construct accurate SOM neural network according to the similarity of intermediate values in the execution of second-order mutants, and at last mutants are clustered based on such model to achieve second-order mutant reduction and subtle mutant detection. This study uses the benchmark and open source projects to verify the method. Experimental results show that on the one hand, although the number of mutants is very large, it has decreased significantly through the SOM neural network, while the second-order mutation score level is the same as the pre-unclustered mutation score. However, because the number of second-order mutants performed is significantly reduced, the time cost of mutation testing was greatly lower than the execution of all mutants. On the other hand, subtle second-order mutants that facilitate the addition of test components are found.
Second-order mutation testing simulates the actual complex defects in the original program by manually injecting two defects into the original program, which is of great significance in the mutation testing. However, the number of second-order mutants formed by the combination of first-order mutants will greatly increase, which will bring large execution costs. In order to reduce the number of second-order mutants and reduce the time consumption in the running procedure, this study proposes a method of second-order mutant reduction based on SOM neural network. The proposed method firstly utilizes a morecomprehensive combination strategy to generate feasible second order mutants based on traditional first-order mutant generation, and then construct accurate SOM neural network according to the similarity of intermediate values in the execution of second-order mutants, and at last mutants are clustered based on such model to achieve second-order mutant reduction and subtle mutant detection. This study uses the benchmark and open source projects to verify the method. Experimental results show that on the one hand, although the number of mutants is very large, it has decreased significantly through the SOM neural network, while the second-order mutation score level is the same as the pre-unclustered mutation score. However, because the number of second-order mutants performed is significantly reduced, the time cost of mutation testing was greatly lower than the execution of all mutants. On the other hand, subtle second-order mutants that facilitate the addition of test components are found.
引文
[1]DeMillo RA,Lipton RJ,Sayward FG.Hints on test data selection:Help for the practicing programmer.Computer,1978,11(4):34-41.[doi:10.1109/C-M.1978.218136]
[2]Shan JH,Gao YF,Liu MH,Liu JH,Zhang L,Sun JS.A new approach to automated test data generation in mutation testing.Chinese Journal of Computers,2008,31(6):1025-1034(in Chinese with English abstract).[2]单锦辉,高友峰,刘明浩,刘江红,张路,孙家骕.一种新的变异测试数据自动生成方法.计算机学报,2008,31(6):1025-1034.
[3]Purushothaman R,Perry DE.Toward understanding the rhetoric of small source code changes.IEEE Trans.on Software Engineering,2005,31(6):511-526.[doi:10.1109/TSE.2005.74]
[4]Jia Y,Harman M.Higher order mutation testing.Information and Software Technology,2009,51(10):1379-1393.[doi:10.1016/j.infsof.2009.04.016]
[5]Langdon WB,Harman M,Jia Y.Efficient multi-objective higher order mutation testing with genetic programming.Journal of Systems and Software,2010,83(12):2416-2430.[doi:10.1016/j.jss.2010.07.027]
[6]Jia Y,Harman M.Constructing subtle faults using higher order mutation testing.In:Proc.of the 8th IEEE Int’l Working Conf.on Source Code Analysis and Manipulation.2008.249-258.[doi:10.1109/SCAM.2008.36]
[7]Omar E,Ghosh S,Whitley D.Subtle higher order mutants.Information and Software Technology,2017,81:3-18.[doi:10.1016/j.infsof.2016.01.016]
[8]Ghiduk AS,Girgis MR,Shehata MH.Higher order mutation testing:A systematic literature review.Computer Science Review,2017,25(6):29-48.[doi:10.1016/j.cosrev.2017.06.001]
[9]Polo M,Piattini M,GarcaRodrguez I.Decreasing the cost of mutation testing with second order mutants.Software Testing,Verication and Reliability,2008,19(2):111-131.[doi:10.1002/stvr.392]
[10]Mateo PR,Usaola MP,Alemn JLF.Validating second-order mutation at system level.IEEE Trans.on Software Engineering,2013,39(4):570-587.[doi:10.1109/TSE.2012.39]
[11]Ghiduk AS.Reducing the number of higher-order mutants with the aid of data flow.E-Informatica Software Engineering Journal,2016,10(1):31-49.[doi:10.5277/e-Inf160102]
[12]Nguyen QV,Madeyski L.Problems of mutation testing and higher order mutation testing.In:Proc.of the Advanced Computational Methods for Knowledge Engineering.2014.157-172.[doi:10.1007/978-3-319-06569-4_12]
[13]Nguyen QV,Madeyski L.Empirical evaluation of multiobjective optimization algorithms searching for higher order mutants.Cybernetics and Systems,2016,47(1-2):48-68.[doi:10.1080/01969722.2016.1128763]
[14]Ma YS,Kim SW.Mutation testing cost reduction by clustering overlapped mutants.Journal of Systems and Software,2016,115:18-30.[doi:10.1016/j.jss.2016.01.007]
[15]Hussain S.Mutation clustering[MS.Thesis].Kings College London,2008.
[16]Kohonen T.The self-organizing map.In:Proc.of the IEEE’90.1990.1464-1480.[doi:10.1016/S0925-2312(98)00030-7]
[17]Delgado S,Higuera C,Calle-Espinosa J,Morn F,Montero F.A som prototype-based cluster analysis methodology.Expert Systems with Applications,2017,88:14-28.[doi:10.1016/j.eswa.2017.06.022]
[18]Nguyen QV,Madeyski L.Addressing mutation testing problems by applying multi-objective optimization algorithms and higher order mutation.Journal of Intelligent&Fuzzy Systems,2017,32(2):1173-1182.[doi:10.3233/JIFS-169117]
[19]Kurtz B,Ammann P,Delamaro ME,Offutt J,Deng L.Mutant subsumption graphs.In:Proc.of the 2014 IEEE 7th Int’l Conf.on Software Testing,Verication and Validation Workshops.Piscataway:IEEE,2014.176-185.[doi:10.1109/ICSTW.2014.20]
[20]Yao X,Harman M,Jia Y.A study of equivalent and stubborn mutation operators using human analysis of equivalence.In:Proc.of the 36th Int’l Conf.on Software Engineering(ICSE 2014).New York:ACM Press,2014.919-930.[doi:10.1145/2568225.2568265]
[21]Shin D,Bae DH.A theoretical framework for understanding mutation-based testing methods.In:Proc.of the 2016 IEEE Int’l Conf.on Software Testing,Verification and Validation(ICST).Piscataway:IEEE,2016.299-308.[doi:10.1109/ICST.2016.22]
[2]Shan JH,Gao YF,Liu MH,Liu JH,Zhang L,Sun JS.A new approach to automated test data generation in mutation testing.Chinese Journal of Computers,2008,31(6):1025-1034(in Chinese with English abstract).[2]单锦辉,高友峰,刘明浩,刘江红,张路,孙家骕.一种新的变异测试数据自动生成方法.计算机学报,2008,31(6):1025-1034.
[3]Purushothaman R,Perry DE.Toward understanding the rhetoric of small source code changes.IEEE Trans.on Software Engineering,2005,31(6):511-526.[doi:10.1109/TSE.2005.74]
[4]Jia Y,Harman M.Higher order mutation testing.Information and Software Technology,2009,51(10):1379-1393.[doi:10.1016/j.infsof.2009.04.016]
[5]Langdon WB,Harman M,Jia Y.Efficient multi-objective higher order mutation testing with genetic programming.Journal of Systems and Software,2010,83(12):2416-2430.[doi:10.1016/j.jss.2010.07.027]
[6]Jia Y,Harman M.Constructing subtle faults using higher order mutation testing.In:Proc.of the 8th IEEE Int’l Working Conf.on Source Code Analysis and Manipulation.2008.249-258.[doi:10.1109/SCAM.2008.36]
[7]Omar E,Ghosh S,Whitley D.Subtle higher order mutants.Information and Software Technology,2017,81:3-18.[doi:10.1016/j.infsof.2016.01.016]
[8]Ghiduk AS,Girgis MR,Shehata MH.Higher order mutation testing:A systematic literature review.Computer Science Review,2017,25(6):29-48.[doi:10.1016/j.cosrev.2017.06.001]
[9]Polo M,Piattini M,GarcaRodrguez I.Decreasing the cost of mutation testing with second order mutants.Software Testing,Verication and Reliability,2008,19(2):111-131.[doi:10.1002/stvr.392]
[10]Mateo PR,Usaola MP,Alemn JLF.Validating second-order mutation at system level.IEEE Trans.on Software Engineering,2013,39(4):570-587.[doi:10.1109/TSE.2012.39]
[11]Ghiduk AS.Reducing the number of higher-order mutants with the aid of data flow.E-Informatica Software Engineering Journal,2016,10(1):31-49.[doi:10.5277/e-Inf160102]
[12]Nguyen QV,Madeyski L.Problems of mutation testing and higher order mutation testing.In:Proc.of the Advanced Computational Methods for Knowledge Engineering.2014.157-172.[doi:10.1007/978-3-319-06569-4_12]
[13]Nguyen QV,Madeyski L.Empirical evaluation of multiobjective optimization algorithms searching for higher order mutants.Cybernetics and Systems,2016,47(1-2):48-68.[doi:10.1080/01969722.2016.1128763]
[14]Ma YS,Kim SW.Mutation testing cost reduction by clustering overlapped mutants.Journal of Systems and Software,2016,115:18-30.[doi:10.1016/j.jss.2016.01.007]
[15]Hussain S.Mutation clustering[MS.Thesis].Kings College London,2008.
[16]Kohonen T.The self-organizing map.In:Proc.of the IEEE’90.1990.1464-1480.[doi:10.1016/S0925-2312(98)00030-7]
[17]Delgado S,Higuera C,Calle-Espinosa J,Morn F,Montero F.A som prototype-based cluster analysis methodology.Expert Systems with Applications,2017,88:14-28.[doi:10.1016/j.eswa.2017.06.022]
[18]Nguyen QV,Madeyski L.Addressing mutation testing problems by applying multi-objective optimization algorithms and higher order mutation.Journal of Intelligent&Fuzzy Systems,2017,32(2):1173-1182.[doi:10.3233/JIFS-169117]
[19]Kurtz B,Ammann P,Delamaro ME,Offutt J,Deng L.Mutant subsumption graphs.In:Proc.of the 2014 IEEE 7th Int’l Conf.on Software Testing,Verication and Validation Workshops.Piscataway:IEEE,2014.176-185.[doi:10.1109/ICSTW.2014.20]
[20]Yao X,Harman M,Jia Y.A study of equivalent and stubborn mutation operators using human analysis of equivalence.In:Proc.of the 36th Int’l Conf.on Software Engineering(ICSE 2014).New York:ACM Press,2014.919-930.[doi:10.1145/2568225.2568265]
[21]Shin D,Bae DH.A theoretical framework for understanding mutation-based testing methods.In:Proc.of the 2016 IEEE Int’l Conf.on Software Testing,Verification and Validation(ICST).Piscataway:IEEE,2016.299-308.[doi:10.1109/ICST.2016.22]