并发程序变异测试研究综述

doi:10.3969/j.issn.0372-2112.2020.11.025

摘要/Abstract

摘要： 变异测试是一种面向缺陷的软件测试方法，利用人为注入的缺陷引导测试数据生成，评价测试数据的有效性，在软件工程领域得到了广泛关注.依托多核架构，开发可靠的并发程序越来越迫切.近年来，很多学者尝试将变异测试技术应用于并发程序，以提高并发程序测试的效率和可靠性.首先，介绍了本文工作与已有综述的不同；然后，阐述了与并发程序和变异测试技术相关的知识；接着，从变异实施、变异测试准则、测试数据生成等3方面，综述并发程序变异测试的研究进展，包括：变异算子设计、选择变异、高阶变异、弱变异、测试数据生成方法、变异测试工具等；最后，讨论需要进一步研究的问题.

关键词: 并发程序, 变异测试, 变异算子, 优化, 测试数据生成

Abstract: Mutation testing is a fault-oriented software testing method,which adopts manually injected defects for guiding the generation of test data and evaluating their adequacy.Researchers in the community of software engineering have paid much attention to mutation testing.The prevalence of multi-core architecture makes an ever increasing need for developing reliable concurrent programs.Many scholars have attempted to employ mutation testing to concurrent programs,with the purpose of improving the reliability and efficiency of testing these programs in recent years.Firstly,the difference between this study and previous reviews is displayed.Then,following the background related to concurrent programs and mutation testing,this study surveys the progress on mutation testing of concurrent programs from the following three aspects,mutation implementation,mutation testing adequacy criteria,and test data generation.Specifically,it surveys techniques related to optimizing mutation testing from such aspects as designing mutation operators,selective mutation,high-order mutation,weak mutation,methods of test data generation,and prototype tools.Finally,this study discusses some topics to be further researched.

Key words: concurrent program, mutation testing, mutation operator, optimization, test data generation

中图分类号:

TP311

田甜, 巩敦卫. 并发程序变异测试研究综述[J]. 电子学报, 2020, 48(11): 2267-2277.

TIAN Tian, GONG Dun-wei. Survey on Mutation Testing of Concurrent Programs[J]. Acta Electronica Sinica, 2020, 48(11): 2267-2277.

参考文献

[1] Parihar M,Bharti A.Role of software testing life cycle(STLC)in software development life cycle(SDLC)[J].International Journal of Research,2019,6(8):649-661.
[2] 苏小红,禹振,王甜甜,马培军.并发缺陷暴露、检测与规避研究综述[J].计算机学报,2015(11):2215-2233. Su X,Yu Z,Wang T,Ma P.A survey on exposing,detecting and voiding concurrency bugs[J].Chinese Journal of Computers,2015,38(11):2215-2233.(in Chinese)
[3] Bianchi F A,Margara A,Pezzè M.A survey of recent trends in testing concurrent software systems[J].IEEE Transactions on Software Engineering,2018,44(8):747-783.
[4] Christakis M,Sagonas K.Detection of asynchronous message passing errors using static analysis,practical aspects of declarative languages[A].Proceedings of the International Symposium on Practical Aspects of Declarative Languages[C].Austin:Springer,2011.5-18.
[5] Koushik S.Effective random testing of concurrent programs[A].Proceedings of the 22nd International Conference on Automated Software Engineering[C]. Atlanta:ACM,2007.323-333.
[6] Godefroid P.Model checking for programming languages using verisoft[A].Proceedings of the 24th Symposium on Principles of Programming Languages[C]. Paris:ACM,1997.174-186.
[7] Chen J.Guided Testing of Concurrent Programs Using Value Schedules[D].Waterloo:University of Waterloo,2009.
[8] Lipton R.Fault Diagnosis of Computer Programs[R]. Pittsburgh:Carnegie Mellon University,1971.
[9] DeMillo R A,Lipton R J,Sayward F G.Hints on test data selection:Help for the practicing programmer[J].Computer,1978,11(4):34-41.
[10] Offutt J.A mutation carol:Past,present and future[J].Information and Software Technology,2011,53(10):1098-1107.
[11] Arora V,Bhatia R,Singh M.A systematic review of approaches for testing concurrent programs[J].Concurrency and Computation:Practice and Experience,2016,28(5):1572-1611.
[12] Ma L,Zhang F,Sun J,et al.Deepmutation:mutation testing of deep learning systems[A].Proceedings of the 2018 IEEE 29th International Symposium on Software Reliability Engineering(ISSRE)[C].Memphis:IEEE,2018.100-111.
[13] Habibi E,Mirian-Hosseinabadi S H.Event-driven web application testing based on model-based mutation testing[J].Information and Software Technology,2015,67:159-179.
[14] Kim Y,Hong S.DEMINER:Test generation for high test coverage through mutant exploration[EB/OL].https://doi.org/10.1002/stvr.1715.2019.10.28.
[15] Carver R,Lei Y.Stateless techniques for generating global and local test oracles for message-passing concurrent programs[J].Journal of Systems and Software,2018,136:237-265.
[16] Yu T,Wen W,Han X,Hayes J.ConPredictor:Concurrency defect prediction in real-world applications[J].IEEE Transactions on Software Engineering,2019,45(5):558-575.
[17] Jia Y,Harman M.An analysis and survey of the development of mutation testing[J].IEEE Transactions on Software Engineering,2011,37(5):649-678.
[18] 陈翔,顾庆.变异测试:原理,优化和应用[J].计算机科学与探索,2012,6(12):1057-1075. Chen X,Gu Q.Mutation testing:Principal,optimization and application[J].Journal of Frontiers of Computer Science and Technology,2012,6(12):1057-1075.(in Chinese)
[19] Madeyski L,Orzeszyna W,Torkar R,Józala M.Overcoming the equivalent mutant problem:A systematic literature review and a comparative experiment of second order mutation[J].IEEE Transactions on Software Engineering,2013,40(1):23-42.
[20] Souza F C M,Papadakis M,Durelli V H S,Delamaro M E.Test data generation techniques for mutation testing:A systematic mapping[A].Proceedings of the XVII Ibero-American Conference on Software Engineering(CIBSE2014)[C].Pucón:University of La Frontera,2014.419-432.
[21] Silva R A,Souza S R S,Souza P S L.A systematic review on search based mutation testing[J].Information and Software Technology,2017,81:19-35.
[22] Belli F,Budnik C J,Hollmann A,Tuglular T,Wong W.Model-based mutation testing-approach and case studies[J].Science of Computer Programming,2016,12:25-48.
[23] Nguyen Q V,Madeyski L.Problems of mutation testing and higher order mutation testing[A].Proceedings of the 2nd International Conference on Computer Science,Applied Mathematics and Application[C].Budapest:Springer,2014.157-172.
[24] Melo S M,Carver J C,Souza P S L,Souza S R S.Empirical research on concurrent software testing:A systematic mapping study[J].Information and Software Technology,2019,105:226-251.
[25] Pizzoleto A V,Ferrari F C,Offutt J,Fernandes L,Ribeiro M.A systematic literature review of techniques and metrics to reduce the cost of mutation testing[J].Journal of Systems and Software,2019,157:110388.
[26] Kintis M,Papadakis M,Papadopoulos A,et al.How effective are mutation testing tools? An empirical analysis of Java mutation testing tools with manual analysis and real faults[J].Empirical Software Engineering,2018,23(4):2426-2463.
[27] Carver R.Mutation-based testing of concurrent programs[A].Proceedings of the IEEE International Test Conference[C].Baltimore:IEEE,1993.845-853.
[28] Jia Y,Harman M.Higher order mutation testing[J].Information and Software Technology,2009,51(10):1379-1393.
[29] King K N,Offutt A J.A fortran language system for mutation based software testing[J].Software:Practice and Experience,1991,21(7):685-718.
[30] 吴迪,徐宝文.Ada语言的发展[J].计算机科学,2014,41(1):1-15. Wu D,Xu B.Evolution of Ada programming language[J].Computer Science,2014,41(1):1-15.(in Chinese)
[31] Offutt A J,Voas J,Payne J.Mutation Operators for Ada[R].Virginia:George Mason University,1996.
[32] Ghosh S.Towards measurement of testability of concurrent object-oriented programs using fault insertion:a preliminary investigation[A].Proceedings of the 2nd IEEE International Workshop on Source Code Analysis and Manipulation[C].Montreal:IEEE,2002.17-25.
[33] Delamaro M,Pezzè M,Vincenzi A M R,Maldonado J C.Mutant operators for testing concurrent Java programs[A].Proceedings of the Brazilian Symposium on Software Engineering[C].Rio de Janeiro:Brazilian Computer Society,2001.272-285.
[34] Bradbury J S,Cordy J R,Dingel J.Mutation operators for concurrent Java(J2SE 5.0)[A].Proceedings of the 2nd Workshop on Mutation Analysis[C].Raleigh:IEEE,2006.83-92.
[35] Wu X,Zheng W,Shi Z,Wang Z,Cao L,Mu D.Concurrency bug-oriented mutation operators design for Java[A].Proceedings of the 2018 IEEE International Conference on Progress in Informatics and Computing(PIC)[C].Suzhou:IEEE,2018.364-369.
[36] Benini L,Bertozzi D,Bogliolo A,Menichelli F,Olivieri M.Mparm:Exploring the multi-processor soc design space with systemc[J].Journal of VLSI Signal Processing Systems for Signal,Image and Video Technology,2005,41(2):169-182.
[37] Sen A.Mutation operators for concurrent SystemC designs[A].Proceedings of 200910th International IEEE Workshop on Microprocessor Test and Verification[C].Austin:IEEE,2009.27-31.
[38] Nilsson R,Offutt J,Andler S F.Mutation-based testing criteria for timeliness[A].Proceedings of the 28th Annual International Computer Software and Applications Conference[C].Hong Kong:IEEE,2004.306-311
[39] Agha G,Houck C,Panwar R.Distributed execution of actor programs[A].Proceedings of the International Workshop on Languages and Compilers for Parallel Computing[C].Santa Clara:Springer,1991.1-17.
[40] Jagannath V,Gligoric M,Lauterburg S,Marinov D,Agha G.Mutation operators for actor systems[A].Proceedings of the 20103rd International Conference on Software Testing,Verification,and Validation Workshops[C].Paris:IEEE,2010.157-162
[41] Snir M,Otto S,Steven H,Walker D,Dongarra J.MPI-the Complete Reference:The MPI Core[M].USA:MIT Press,1998.
[42] Silva R A,Souza S R S,Souza P S L.Mutation operators for concurrent programs in MPI[A].Proceedings of the 201213th Latin American Test Workshop(LATW)[C].Quito:IEEE,2012.1-6.
[43] Cañizares P C,Núñez A,Lara J.OUTRIDER:Optimizing the mutation testing process in distributed Environments[J].Procedia Computer Science,2017,108:505-514.
[44] Estero-Botaro A,Palomo-Lozano F,Medina-Bulo I.Mutation operators for WS-BPEL 2.0[A].Proceedings of the 21th International Conference on Software & Systems Engineering and their Applications[C].Paris:Genie Logiciel,2008.1-7.
[45] Clark J A,Dan H,Hierons R M.Semantic mutation testing[J].Science of Computer Programming,2013,78(4):345-363.
[46] Cao L,Zheng W,Hu D,Bai H.Concurrent program semantic mutation testing based on abstract memory model[A].Proceedings of the 2015 IEEE International Conference on Information and Automation[C].Lijiang:IEEE,2015.1200-1205.
[47] 钱茛南,王雅文,宫云战,等.一种变异测试中冗余变异体的寻找方法[J].电子学报,2017,45(8):1970-1975. Qian Gen-nan,Wang Ya-wen,Gong Yun-zhan.A method four finding redundant mutants in mutation testing[J].Acta Electronica Sinic,2017,45(8):1970-1975.(in Chinese)
[48] Papadakis M,Kintis M,Zhang J,Jia Y,LeTraon Y,Harman M.Mutation testing advances:An analysis and survey[J].Advances in Computers.Netherlands:Elsevier,2019,112:275-378.
[49] Gopinath R,Alipour A,Ahmed I,Jensen C,Groce A.How hard does mutation analysis have to be,anyway?[A].Proceedings of the 26th IEEE International Symposium on Software Reliability Engineering(ISSRE)[C].Gaithersbury:IEEE,2015.216-227.
[50] Namin A S,Andrews J H,Murdoch D J.Sufficient mutation operators for measuring test effectiveness[A].Proceedings of the 30th International Conference on Software engineering[C].Leipzig:IEEE,2008.351-360.
[51] Gligoric M,Zhang L,Pereira C,Pokam G.Selective mutation testing for concurrent code[A].Proceedings of the 2013 International Symposium on Software Testing and Analysis[C].Lugano:ACM,2013.224-234.
[52] Wu L,Kaiser G.Constructing subtle concurrency bugs using synchronization-centric second-order mutation operators[R].New York:Columbia University Computer Science Technical Reports,2011.
[53] Kusano M,Wang C.CCmutator:A mutation generator for concurrency constructs in multithreaded C/C++ applications[A].Proceedings of the 28th IEEE/ACM International Conference on Automated Software Engineering[C].Palo Alto:IEEE,2013.722-725.
[54] Madiraju P,Namin A S.Paraμ-A partial and higher-order mutation tool with concurrency operators[A].Proceedings of the 2011 IEEE Fourth International Conference on Software Testing,Verification and Validation Workshops[C].Berlin:IEEE,2011.351-356.
[55] 孙昌爱,王真,潘琳.面向WS-BPEL程序的变异测试优化技术[J].计算机研究与发展,2019,56(4):895-905. Sun Changai,Wang Zhen,Pan Lin.Optimized mutation testing techniques for WS-BPEL programs[J].Journal of Computer Reasearch and Developlent,2019,56(4):895-905.(in Chinese)
[56] DeMilli R A,Offutt A J.Constraint-based automatic test data generation[J].IEEE Transactions on Software Engineering,1991,17(9):900-910.
[57] Howden W E.Weak mutation testing and completeness of test sets[J].IEEE Transactions on Software Engineering,1982,8(4):371-379.
[58] Marick B.The weak mutation hypothesis[A].Proceedings of the Symposium on Testing,Analysis,and Verification[C].Victoria:ACM,1991.190-199.
[59] Offutt A J,Lee S D.An empirical evaluation of weak mutation[J].IEEE Transactions on Software Engineering,1994,20(5):337-344.
[60] Papadakis M,Malevris N.Automatically performing weak mutation with the aid of symbolic execution,concolic testing and search-based testing[J].Software Quality Journal,2011,19(4):691-723.
[61] 巩敦卫,陈永伟,田甜.消息传递并发程序的弱变异测试及其转化[J].软件学报,2016,27(8):2008-2024. Gong D,Chen Y,Tian T.Weak mutation testing and its transformation for message passing parallel programs[J].Journal of Software,2016,27(8):2008-2024.(in Chinese)
[62] Singh M,Srivastava V M.Extended firm mutation testing:A cost reduction technique for mutation testing[A].Proceedings of the 2017 Fourth International Conference on Image Information Processing(ICIIP)[C]. Waknaghat:IEEE,2017.1-6.
[63] Woodward M R,Halewood K.From weak to strong,dead or alive[A].Proceedings of the Second Workshop on Software Testing,Verification and Analysis[C].Banff:IEEE,1988.152-158.
[64] Palomo-Lozano F,Estero-Botaro A,Medina-Bulo I,Núñez M.Test suite minimization for mutation testing of WS-BPEL compositions[A].Proceedings of the Genetic and Evolutionary Computation Conference[C].Kyoto:ACM,2018.1427-1434.
[65] Estero-Botaro A,Palomo-Lozano F,Medina-Bulo I,Domínguez-Jiménez J J,García-Domínguez A.Quality metrics for mutation testing with applications to WS-BPEL compositions[J].Software Testing,Verification and Reliability,2015,25(5-7):536-571.
[66] Gligoric M,Jagannath V,Marinov D.MuTMuT:Efficient exploration for mutation testing of multithreaded code[A].Proceedings of the 2010 Third International Conference on Software Testing,Verification and Validation[C].Paris:IEEE,2010.55-64.
[67] Sen A,Abadir M S.Coverage metrics for verification of concurrent SystemC designs using mutation testing[A].Proceedings of the 2010 IEEE International High Level Design Validation and Test Workshop(HLDVT)[C].Anaheim:IEEE,2010.75-81.
[68] Harman M,Jones B F.Search-based software engineering[J].Information and software Technology,2001,43(14):833-839.
[69] Ozkaya I.The golden age of software engineering[J].IEEE Software,2019(1):4-10.
[70] Khari M,Kumar P.An extensive evaluation of search-based software testing:a review[J].Soft Computing,2019,23(6):1933-1946.
[71] Rodrigues D S,Delamaro M E,Corrěa C G,Nunes F L S.Using genetic algorithms in test data generation:A critical systematic mapping[J].ACM Computing Surveys(CSUR),2018,51(2):41:1-41:23.
[72] Silva R A.Search Based Software Testing for the Generation of Synchronization Sequences for Mutation Testing of Concurrent Programs[D].São Paulo:Universidade de São Paulo,2018.
[73] Nilsson R,Offutt J,Mellin J.Test case generation for mutation-based testing of timeliness[J].Electronic Notes in Theoretical Computer Science,2006,164(4):97-114.
[74] Ghiduk A S,El-Zoghdy S F.CHOMK:concurrent higher-order mutants killing using genetic algorithm[J].Arabian Journal for Science and Engineering,2018,43(12):7907-7922.
[75] Takagi T,Arao T.Overview of a place/transition net-based mutation testing framework to obtain test cases effective for concurrent software[A].Proceedings of the 2015 IEEE/ACIS 16th International Conference on Software Engineering,Artificial Intelligence,Networking and Parallel/Distributed Computing(SNPD)[C].Takamatsu:IEEE,2015.1-3.
[76] Delgado-Pérez P,Segura S,Medina-Bulo I.Assessment of C++ object-oriented mutation operators:A selective mutation approach[EB/OL].https://doi.org/10.1002/stvr.1630.2017.03.20.
[77] Kurtz B,Ammann P,Offutt J,Delamaro M E,Kurtz M,GökCçe N.Analyzing the validity of selective mutation with dominator mutants[A].Proceedings of the 201624th ACM SIGSOFT International Symposium on Foundations of Software Engineering[C].Seattle:ACM,2016.571-582.
[78] Zhang J.Scalability studies on selective mutation testing[A].Proceedings of the 2015 IEEE/ACM 37th IEEE International Conference on Software Engineering[C].Florence:IEEE,2015.851-854.
[79] Gong D,Yao X,Xia M.Automatic determination of branch correlations in software testing[A].Proceedings of the 2009 WRI World Congress on Software Engineering[C].Xiamen:IEEE,2009.211-215.
[80] Tian T,Gong D,Kuo F C,Liu H.Genetic algorithm based test data generation for MPI parallel programs with blocking communication[J].Journal of Systems and Software,2019,155:130-144.
[81] Zhang J,Zhang L,Harman M,Hao D,Jia Y,Zhang L.Predictive mutation testing[J].IEEE Transactions on Software Engineering,2019,45(9):898-918.
[82] Madeyski L,Orzeszyna W,Torkar R,Jozala M.Overcoming the equivalent mutant problem:A systematic literature review and a comparative experiment of second order mutation[J].IEEE Transactions on Software Engineering,2013,40(1):23-42.
[83] Kintis M,Malevris N.Using data flow patterns for equivalent mutant detection[A].Proceedings of the 2014 IEEE Seventh International Conference on Software Testing,Verification and Validation Workshops[C].Cleveland:IEEE,2014.196-205.
[84] Kintis M.Effective Methods to Tackle the Equivalent Mutant Problem When Testing Software with Mutation[D].Athens:Athens University of Economics and Business,2016.
[85] Holling D,Banescu S,Probst M,Petrovska A,Pretschner A.Nequivack:Assessing mutation score confidence[A].Proceedings of the 2016 IEEE Ninth International Conference on Software Testing,Verification and Validation Workshops(ICSTW)[C].Chicago:IEEE,2016.152-161.
[86] Papadakis M,Malevris N.Mutation based test case generation via a path selection strategy[J].Information and Software Technology,2012,54(9):915-932.
[87] Sun C,Jia J,Liu H,Zhang X.A lightweight program dependence based approach to concurrent mutation analysis[A].Proceedings of the 2018 IEEE 42nd Annual Computer Software and Applications Conference(COMPSAC)[C].Tokyo:IEEE,2018.116-125.