电子学报 ›› 2020, Vol. 48 ›› Issue (11): 2267-2277.DOI: 10.3969/j.issn.0372-2112.2020.11.025
田甜1, 巩敦卫2
收稿日期:
2019-10-29
修回日期:
2020-01-27
出版日期:
2020-11-25
发布日期:
2020-11-25
通讯作者:
巩敦卫
作者简介:
田甜 女,1987年1月出生于山东德州,山东建筑大学副教授,主要研究方向为程序分析与测试.E-mail:tian_tiantian@126.com
基金资助:
TIAN Tian1, GONG Dun-wei2
Received:
2019-10-29
Revised:
2020-01-27
Online:
2020-11-25
Published:
2020-11-25
摘要: 变异测试是一种面向缺陷的软件测试方法,利用人为注入的缺陷引导测试数据生成,评价测试数据的有效性,在软件工程领域得到了广泛关注.依托多核架构,开发可靠的并发程序越来越迫切.近年来,很多学者尝试将变异测试技术应用于并发程序,以提高并发程序测试的效率和可靠性.首先,介绍了本文工作与已有综述的不同;然后,阐述了与并发程序和变异测试技术相关的知识;接着,从变异实施、变异测试准则、测试数据生成等3方面,综述并发程序变异测试的研究进展,包括:变异算子设计、选择变异、高阶变异、弱变异、测试数据生成方法、变异测试工具等;最后,讨论需要进一步研究的问题.
中图分类号:
田甜, 巩敦卫. 并发程序变异测试研究综述[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. |
[1] | 王鼎, 尹洁昕, 郑娜娥, 聂福全. 信号传播速度未知下基于运动单站到达频率的定位新方法[J]. 电子学报, 2022, 50(5): 1181-1191. |
[2] | 窦子铮, 姚铮, 陆明泉. 无线电区域定位系统的分布式空间基准自主建立技术[J]. 电子学报, 2022, 50(4): 841-848. |
[3] | 蒋林, 方东君, 周和文, 黄惠保. 基于射线模型的改进全局路径规划算法[J]. 电子学报, 2022, 50(3): 548-556. |
[4] | 余若峰, 杨威, 付耀文, 张文鹏. 面向不同雷达任务的认知波形优化综述[J]. 电子学报, 2022, 50(3): 726-752. |
[5] | 汪禹宏, 张屹. 基于适应度指导交配限制策略的重组算子与多目标优化研究[J]. 电子学报, 2022, 50(3): 710-717. |
[6] | 史宏强, 李岳衡, 黄平, 谭跃跃, 刘陕陕, 居美艳. 基于APD与PIN接收机的UWOC系统误码率性能优化研究[J]. 电子学报, 2022, 50(2): 446-454. |
[7] | 蒋华伟, 郭陶, 杨震. 车辆路径问题研究进展[J]. 电子学报, 2022, 50(2): 480-492. |
[8] | 董明, 李敬, 索永录, 唐恩贤, 马宏伟, 陈渊, 张广明, 万翔. 基于改进果蝇优化算法正交匹配追踪的超声信号降噪方法[J]. 电子学报, 2022, 50(2): 493-501. |
[9] | 何雪, 胡志忠. 分数阶低通滤波器的优化设计研究[J]. 电子学报, 2022, 50(1): 185-194. |
[10] | 张屹, 陆逸舟, 王帅, 陆曈曈. 基于多源交配选择策略的重组算子与多目标优化研究[J]. 电子学报, 2021, 49(9): 1754-1760. |
[11] | 李彦苍, 巩翔宇. 基于信息熵的改进狮群算法及其在组合优化中的应用[J]. 电子学报, 2021, 49(8): 1577-1585. |
[12] | 柴蓉, 谢德胜, 陈前斌. 基于成本及功耗联合优化的SDN虚拟网络映射算法[J]. 电子学报, 2021, 49(8): 1615-1624. |
[13] | 王蔚龙, 李勇军, 赵尚弘, 辛宁, 赵海燕, 张泰江. 基于两阶段帕累托优化的卫星下行链路功率分配方法[J]. 电子学报, 2021, 49(6): 1101-1107. |
[14] | 刘景森, 马义想, 李煜. 改进蝴蝶算法求解多维复杂函数优化问题[J]. 电子学报, 2021, 49(6): 1068-1076. |
[15] | 廖彬, 黄静莱, 王鑫, 孙瑞娜, 葛晓燕, 国冰磊. SCEA:一种适应高维海量数据的并行聚类集成算法[J]. 电子学报, 2021, 49(6): 1077-1087. |
阅读次数 | ||||||
全文 |
|
|||||
摘要 |
|
|||||