Weak Mutation Testing and Its Transformation for Message Passing Parallel Programs
Author:
Affiliation:

Fund Project:

National Natural Science Foundation of China (61375067); National Program on Key Basic Research Project of China (973) (2014CB046306-2); Natural Science Foundation of Jiangsu Province of China (BK2012566)

  • Article
  • | |
  • Metrics
  • |
  • Reference [48]
  • |
  • Related
  • |
  • Cited by
  • | |
  • Comments
    Abstract:

    A parallel program can yield nondeterministic execution, which increases the complexity and the difficulty in program testing. The mutation testing of a message passing parallel program is investigated, and an approach to transforming the weak mutation testing for the program is presented in this study with the purpose of improving the efficiency of the mutation testing. First, the mutation condition statements are built based on the type of statements and the changes resulted from mutating these statements. Then, a new program is formed by inserting all these mutation condition statements into the original program. As a result, the problem of the weak mutation testing of the original program can be transformed into that of covering the branches of the new program, therefore providing advantages of solving the problem of mutation testing by using previous methods of branch coverage. The proposed approach is applied to test eight benchmark message passing parallel programs, and the empirical results demonstrate that this new approach is not only feasible but also necessary.

    Reference
    [1] Hamlet D. Software quality, software process, and software testing. Advances in Computers, 1995,41(8):191-229. [doi: 10.1016/ S0065-2458(08)60234-X]
    [2] Jia Y, Harman M. An analysis and survey of the development of mutation testing. IEEE Trans. on Software Engineering, 2011, 37(5):649-678. [doi: 10.1109/TSE.2010.62]
    [3] Madeyski L, Orzeszyna W, Torkar R, Jozala M. Overcoming the equivalent mutant problem: A systematic literature review and a comparative experiment of 2nd order mutation. IEEE Trans. on Software Engineering, 2014,40(1):23-42. [doi: 10.1109/TSE. 2013.44]
    [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] 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]
    [6] Offutt AJ, Lee SD. How strong is weak mutation? In: Howden W, ed. Proc. of the Symp. on Testing, Analysis, and Verification. New York: ACM Press, 1991. 200-213. [doi: 10.1145/120807.120826]
    [7] Marick B. The weak mutation hypothesis. In: Howden W, ed. Proc. of the Symp. on Testing, Analysis, and Verification. New York: ACM Press, 1991. 190-199. [doi: 10.1145/120807.120825]
    [8] Souza SRS, Brito MAS, Silva RA, Souza RSL, Zaluska E. Research in concurrent software testing: A systematic review. In: Lourenço J, Farchi E, eds. Proc. of the Workshop on Parallel and Distributed Systems: Testing, Analysis, and Debugging. New York: ACM Press, 2011. 1-5. [doi: 10.1145/2002962.2002964]
    [9] Souza PSL, Souza SRS, Zaluska E. Structural testing for message-passing concurrent programs: An extended test model. Concurrency and Computation: Practice and Experience, 2014,26(1):21-50. [doi: 10.1002/cpe.2937]
    [10] DeMilli RA, Offutt AJ. Constraint-Based automatic test data generation. IEEE Trans. on Software Engineering, 1991,17(9): 900-910. [doi: 10.1109/32.92910]
    [11] Howden WE. Weak mutation testing and completeness of test sets. IEEE Trans. on Software Engineering, 1982,8(4):371-379. [doi: 10.1109/TSE.1982.235571]
    [12] Girgis MR, Woodward MR. An integrated system for program testing using weak mutation and data flow analysis. In: Lehman MM, Hünke H, Boehm B, eds. Proc. of the 8th Int'l Conf. on Software Engineering. Los Alamitos: IEEE Computer Society Press, 1985. 313-319.
    [13] Horgan JR, Mathur AP. Weak mutation is probably strong mutation. Technical Report, SERC-TR-83-P, West Lafayette: Purdue University, 1990.
    [14] Offutt AJ, Lee SD. An empirical evaluation of weak mutation. IEEE Trans. on Software Engineering, 1994,20(5):337-344. [doi: 10.1109/32.286422]
    [15] Xu SY. A method of simplifying complexity of mutation testing. Journal of Shanghai University (Natural Science Edition), 2007, 13(5):524-531 (in Chinese with English abstract). [doi: 10.3969/j.issn.1007-2861.2007.05.007]
    [16] 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). [doi: 10.3321/j.issn:0254-4164.2008.06. 015]
    [17] Li JJ, Weiss D, Yee H. Code-Coverage guided prioritized test generation. Information and Software Technology, 2006,48(12): 1187-1198. [doi: 10.1016/j.infsof.2006.06.007]
    [18] Madeyski L. The impact of test-first programming on branch coverage and mutation score indicator of unit tests: An experiment. Information and Software Technology, 2010,52(2):169-184. [doi: 10.1016/j.infsof.2009.08.007]
    [19] Murrill BW. An empirical, path-oriented approach to software analysis and testing. Journal of Systems and Software, 2008,81(2): 249-261. [doi: 10.1016/j.jss.2007.05.008]
    [20] Lin JC, Yeh PL. Automatic test data generation for path testing using GAs. Information Sciences, 2001,131(1-4):47-64. [doi: 10.1016/S0020-0255(00)00093-1]
    [21] Ahmed MA, Hermadi I. GA-Based multiple paths test data generator. Computers & Operations Research, 2008,35(10):3107-3124. [doi: 10.1016/j.cor.2007.01.012]
    [22] Watkins A, Hufnagel EM. Evolutionary test data generation: A comparison of fitness functions. Software: Practice and Experience, 2006,36(1):95-116. [doi: 10.1002/spe.684]
    [23] Pargas RP, Harrold MJ, Peck RR. Test-Data generation using genetic algorithms. Software Testing Verification and Reliability, 1999,9(4):263-282. [doi: 10.1002/(SICI)1099-1689(199912)9:4<263::AID-STVR190>3.0.CO;2-Y]
    [24] Wegener J, Buhr K, Pohlheim H. Automatic test data generation for structural testing of embedded software systems by evolutionary testing. In: Langdon WB, Cantú-Paz E, Mathias KE, Roy R, Davis D, Poli R, Balakrishnan K, Honavar VG, Rudolph G, Wegener J, Bull L, Potter MA, Schultz AC, Miller JF, Burke E, Jonoska N, eds. Proc. of the Genetic and Evolutionary Computation Conf. San Francisco: Morgan Kaufmann Publishers, 2002. 1233-1240.
    [25] Gong DW, Zhang Y. Novel evolutionary generation approach to test data for multiple paths coverage. Acta Electronica Sinica, 2010,38(6):1299-1304 (in Chinese with English abstract).
    [26] Gong DW, Zhang WQ, Yao XJ. Evolutionary generation of test data for many paths coverage based on grouping. Journal of Systems and Software, 2011,84(12):2222-2233. [doi: 10.1016/j.jss.2011.06.028]
    [27] Papadakis M, Malevris N. Automatically performing weak mutation with the aid of symbolic execution, concolic testing and search-based testing. Software Quality Journal, 2011,19(4):691-723. [doi: 10.1007/s11219-011-9142-y]
    [28] Papadakis M, Malevris N. Mutation based test case generation via a path selection strategy. Information and Software Technology, 2012,54(9):915-932. [doi: 10.1016/j.infsof.2012.02.004]
    [29] Carver RH, Lei Y. Distributed reachability testing of concurrent programs. Concurrency and Computation: Practice and Experience, 2010,22(18):2445-2466. [doi: 10.1002/cpe.1573]
    [30] Hilbrich T, de Supinski BR, Nagel WE, Protze J, Bsier C, Müller MS. Distributed wait state tracking for runtime MPI deadlock detection. In: Gropp W, Matsuoka S, eds. Proc. of the Int'l Conf. for High Performance Computing, Networking, Storage and Analysis. New York: ACM Press, 2013. 1-12.[doi: 10.1145/2503210.2503237]
    [31] Takahashi J, Kojima H, Furukawa Z. Coverage based testing for concurrent software. In: Croll PR, ed. Proc. of the 28th Int'l Conf. on Distributed Computing Systems Workshops. Washington: IEEE Computer Society, 2008. 533-538. [doi: 10.1109/ICDCS. Workshops.2008.76]
    [32] Tian T, Gong DW. Model of test data generation for path coverage of message-passing parallel programs and its evolution-based solution. Chinese Journal of Computers, 2013,36(11):2212-2223 (in Chinese with English abstract). [doi: 10.3724/SP.J.1016.2013. 02212]
    [33] Carver R. Mutation-Based testing of concurrent programs. In: Proc. of the IEEE Int'l Test Conf. on Designing, Testing, and Diagnostics. Washington: IEEE Computer Society, 1993. 845-853. [doi: 10.1109/TEST.1993.470617]
    [34] Bradbury JS, Cordy JR, Dingel J. Mutation operators for concurrent Java (J2SE 5.0). In: Proc. of the 2nd Workshop on Mutation Analysis. Washington: IEEE Computer Society, 2006. 83-92. [doi: 10.1109/MUTATION.2006.10]
    [35] Sen A, Abadir MS. Coverage metrics for verification of concurrent SystemC designs using mutation testing. In: Mishra P, Zilic Z, eds. Proc. of the IEEE Int'l High Level Design Validation and Test Workshop. IEEE, 2010. 75-81. [doi: 10.1109/HLDVT.2010. 5496659]
    [36] Gligoric M, Jagannath V, Marinov D. MuTMuT: Efficient exploration for mutation testing of multithreaded code. In: Gaudel MC, Cavalli AR, Ghosh S, eds. Proc. of the 3rd Int'l Conf. on Software Testing, Verification and Validation. Washington: IEEE Computer Society, 2010. 55-64. [doi: 10.1109/ICST.2010.33]
    [37] Gligoric M, Zhang LM, Pereira C, Pokam G. Selective mutation testing for concurrent code. In: Pezzè M, Harman M, eds. Proc. of the 2013 Int'l Symp. on Software Testing and Analysis. New York: ACM Press, 2013. 224-234. [doi: 10.1145/2483760. 2483773]
    [38] Silva RA, de Souza SRS, de Souza PSL. Mutation operators for concurrent programs in MPI. In: Champac V, Zorian Y, eds. Proc. of the 13th Latin American Test Workshop. Washington: IEEE Computer Society, 2012: 1-6. [doi: 10.1109/LATW.2012.6261240]
    [39] Chen GL, An H, Chen L, Zheng QL, Shan JL. Parallel Algorithm Practice. Beijing: Higher Education Press, 2004 (in Chinese).
    [40] Ma YS, Offutt J, Kwon YR. MuJava: A mutation system for Java. In: Osterweil LJ, Rombach D, Soffa ML, eds. Proc. of the 28th Int'l Conf. on Software Engineering. New York: ACM Press, 2006. 827-830. [doi: 10.1145/1134285.1134425]
    [41] Yao XJ. Theory of evolutionary generation of test data for complex software and applications [Ph.D. Thesis]. Xuzhou: China University of Mining and Technology, 2011 (in Chinese with English abstract).
    附中文参考文献:
    [15] 徐拾义.降低软件变异测试复杂性的新方法.上海大学学报(自然科学版),2007,13(5):524-531. [doi: 10.3969/j.issn.1007-2861. 2007.05.007]
    [16] 单锦辉,高友峰,刘明浩,刘江红,张路,孙家骕.一种新的变异测试数据自动生成方法.计算机学报,2008,31(6):1025-1034. [doi: 10.3321/j.issn:0254-4164.2008.06.015]
    [25] 巩敦卫,张岩.一种新的多路径覆盖测试数据进化生成方法.电子学报,2010,38(6):1299-1304.
    [32] 田甜,巩敦卫.消息传递并行程序路径覆盖测试数据生成问题的模型及其进化求解方法.计算机学报,2013,36(11):2212-2223. [doi: 10.3724/SP.J.1016.2013.02212]
    [39] 陈国良,安虹,陈崚,郑启龙,单久龙.并行算法实践.北京:高等教育出版社,2004.
    [41] 姚香娟.复杂软件测试数据进化生成理论及应用[博士学位论文].徐州:中国矿业大学,2011.
    Related
    Cited by
    Comments
    Comments
    分享到微博
    Submit
Get Citation

巩敦卫,陈永伟,田甜.消息传递并行程序的弱变异测试及其转化.软件学报,2016,27(8):2008-2024

Copy
Share
Article Metrics
  • Abstract:
  • PDF:
  • HTML:
  • Cited by:
History
  • Received:December 26,2014
  • Revised:April 09,2015
  • Online: August 08,2016
You are the first2038044Visitors
Copyright: Institute of Software, Chinese Academy of Sciences Beijing ICP No. 05046678-4
Address:4# South Fourth Street, Zhong Guan Cun, Beijing 100190,Postal Code:100190
Phone:010-62562563 Fax:010-62562533 Email:jos@iscas.ac.cn
Technical Support:Beijing Qinyun Technology Development Co., Ltd.

Beijing Public Network Security No. 11040202500063