Delta4Ms: Improving mutation-based fault localization by eliminating mutant bias
Hengyuan Liu
College of Information Science and Technology, Beijing University of Chemical Technology, Beijing, China
Search for more papers by this authorZheng Li
College of Information Science and Technology, Beijing University of Chemical Technology, Beijing, China
Search for more papers by this authorBaolong Han
College of Information Science and Technology, Beijing University of Chemical Technology, Beijing, China
Search for more papers by this authorYangtao Liu
College of Information Science and Technology, Beijing University of Chemical Technology, Beijing, China
Search for more papers by this authorXiang Chen
School of Information Science and Technology, Nantong University, Jiangsu, China
Search for more papers by this authorCorresponding Author
Yong Liu
College of Information Science and Technology, Beijing University of Chemical Technology, Beijing, China
Correspondence
Yong Liu, College of Information Science and Technology, Beijing University of Chemical Technology, North Third Ring Road 15, Chaoyang District, Beijing 100029, China.
Email: [email protected]
Search for more papers by this authorHengyuan Liu
College of Information Science and Technology, Beijing University of Chemical Technology, Beijing, China
Search for more papers by this authorZheng Li
College of Information Science and Technology, Beijing University of Chemical Technology, Beijing, China
Search for more papers by this authorBaolong Han
College of Information Science and Technology, Beijing University of Chemical Technology, Beijing, China
Search for more papers by this authorYangtao Liu
College of Information Science and Technology, Beijing University of Chemical Technology, Beijing, China
Search for more papers by this authorXiang Chen
School of Information Science and Technology, Nantong University, Jiangsu, China
Search for more papers by this authorCorresponding Author
Yong Liu
College of Information Science and Technology, Beijing University of Chemical Technology, Beijing, China
Correspondence
Yong Liu, College of Information Science and Technology, Beijing University of Chemical Technology, North Third Ring Road 15, Chaoyang District, Beijing 100029, China.
Email: [email protected]
Search for more papers by this authorAbstract
Fault localization is a complex, costly and time-consuming task in software debugging. Numerous automated techniques have been developed to expedite this process. Mutation-based fault localization (MBFL) is one of the most widely studied techniques which uses mutation analysis to generate mutants for revealing potential faults in the program. However, our theoretical analysis exposes an inherent conflict between the fundamental assumption and the essential meaning of existing MBFL suspiciousness. This conflict is caused by mutant bias. Intuitively, the suspiciousness can be corrected by eliminating the mutant bias for more accurately measuring the faulty probability of the corresponding mutant statement. In this paper, we introduce Delta4Ms, a fault localization approach designed to eliminate mutant bias. Delta4Ms integrates the principles of signal theory, modelling the actual suspiciousness and mutant bias as the desired and false signal components, respectively. Based on theoretical derivation, the average suspiciousness of mutants serves as an estimate of mutant bias. Delta4Ms effectively mitigates mutant bias, extracting the desired signal and yielding corrected suspiciousness for fault localization. To precisely estimate mutant bias, higher order mutants (HOMs) are incorporated. We conduct an extensive experimental evaluation of Delta4Ms on 320 real-fault programs from Codeflaws. The results indicate that our model significantly outperforms existing SBFL and MBFL techniques, showing a considerable improvement in fault localization effectiveness. We further assessed the robustness of Delta4Ms by examining different HOM ratios and HOM generation strategies. Moreover, Delta4Ms achieves a substantial reduction in mutation execution cost and minimal accuracy loss through the implementation of test case reduction. Finally, we perform preliminary experiments on 15 real-fault programs from the Defects4J benchmark to assess the generalization of the model's fault localization effectiveness.
Open Research
DATA AVAILABILITY STATEMENT
The data that support the findings of this study are openly available in DNMBFL at https://github.com/759031482/DNMBFL.
REFERENCES
- 1Shin D, Bae D-H. A theoretical framework for understanding mutation-based testing methods. In 2016 IEEE International Conference on Software Testing, Verification and Validation (ICST). IEEE: Chicago, IL, 2016; 299–308.
- 2Wong WE, Gao R, Li Y, Abreu R, Wotawa F. A survey on software fault localization. IEEE Trans Softw Eng. 2016; 42(8): 707–740.
- 3Keller F, Grunske L, Heiden S, Filieri A, van Hoorn A, Lo D. A critical evaluation of spectrum-based fault localization techniques on a large-scale software system. In 2017 IEEE International Conference on Software Quality, Reliability and Security (QRS). IEEE: Prague, Czech Republic, 2017; 114–125.
- 4Arrieta A, Segura S, Markiegi U, Sagardui G, Etxeberria L. Spectrum-based fault localization in software product lines. Inform Softw Technol. 2018; 100: 18–31.
- 5Lukins SK, Kraft NA, Etzkorn LH. Bug localization using latent Dirichlet allocation. Inform Softw Technol. 2010; 52(9): 972–990.
- 6Rao S, Kak A. Retrieval from software libraries for bug localization: a comparative study of generic and composite text models—a retrospective. In ACM SIGSOFT Software Engineering Notes. ACM: New York, NY, 2021; 33–36.
- 7Saha RK, Lease M, Khurshid S, Perry DE. Improving bug localization using structured information retrieval. In 2013 28th IEEE/ACM International Conference on Automated Software Engineering (ASE). IEEE: Silicon Valley, CA, 2013; 345–355.
- 8Wong WE, Debroy V, Golden R, Xu X, Thuraisingham B. Effective software fault localization using an RBF neural network. IEEE Trans Reliab. 2011; 61(1): 149–169.
- 9Gao R, Wong WE, Chen Z, Wang Y. Effective software fault localization using predicted execution results. Softw Qual J. 2017; 25(1): 131–169.
- 10Zhang Z, Lei Y, Mao X, Li P. CNN-FL: an effective approach for localizing faults using convolutional neural networks. In 2019 IEEE 26th International Conference on Software Analysis, Evolution and Reengineering (SANER). IEEE: Hangzhou, China, 2019; 445–455.
- 11Moon S, Kim Y, Kim M, Yoo S. Ask the mutants: mutating faulty programs for fault localization. In Proceedings of the 2014 IEEE Seventh International Conference on Software Testing, Verification and Validation. IEEE: Cleveland, OH, 2014; 153–162.
- 12Papadakis M, Le Traon Y. Using mutants to locate “unknown” faults. In 2012 IEEE Fifth International Conference on Software Testing, Verification and Validation. IEEE: Montreal, QC, 2012; 691–700.
- 13Papadakis M, Le Traon Y. Metallaxis-FL: mutation-based fault localization. Softw Test Verif Reliab. 2015; 25(5–7): 605–628.
- 14Li Z, Wang H, Liu Y. HMER: a hybrid mutation execution reduction approach for mutation-based fault localization. J Syst Softw. 2020; 2020:110661.
10.1016/j.jss.2020.110661 Google Scholar
- 15Wang H, Du B, He J, Liu Y, Chen X. IETCR: an information entropy based test case reduction strategy for mutation-based fault localization. IEEE Access. 2020; 8: 124297–124310.
- 16Zhang L, Li Z, Feng Y, Zhang Z, Chan WK, Zhang J, Zhou Y. Improving fault-localization accuracy by referencing debugging history to alleviate structure bias in code suspiciousness. IEEE Trans Reliab. 2020; 69(3): 1021–1049.
- 17Reps T, Ball T, Das M, Larus J. 1997. The use of program profiling for software maintenance with applications to the year 2000 problem. In Software Engineering—ESEC/FSE'97 Springer Berlin Heidelberg: Berlin, Heidelberg; 432–449.
10.1007/3-540-63531-9_29 Google Scholar
- 18Kooli M, Kaddachi F, Di Natale G, Bosio A, Benoit P, Torres L. Computing reliability: on the differences between software testing and software fault injection techniques. Microprocess Microsyst. 2017; 50: 102–112.
- 19DeMillo RA, Lipton RJ, Sayward FG. Hints on test data selection: Help for the practicing programmer. Computer. 1978; 11(4): 34–41.
- 20Pearson S, Campos J, Just R, Fraser G, Abreu R, Ernst MD, et al. Evaluating and improving fault localization. In Proceedings of the 39th International Conference on Software Engineering. IEEE: Buenos Aires, Argentina, 2017; 609–620.
- 21Lou Y, Ghanbari A, Li X, Zhang L, Zhang H, Hao D, Zhang L. Can automated program repair refine fault localization? A unified debugging approach. In Proceedings of the 29th ACM SIGSOFT International Symposium on Software Testing and Analysis. ISSTA 2020. ACM: New York, NY, 2020; 75–87.
- 22Benton S, Li X, Lou Y, Zhang L. On the effectiveness of unified debugging: an extensive study on 16 program repair systems. In Proceedings of the 35th IEEE/ACM International Conference on Automated Software Engineering. ASE '20. ACM: New York, NY, 2021; 907–918.
- 23Benton S, Li X, Lou Y, Zhang L. Evaluating and improving unified debugging. IEEE Trans Softw Eng. 2022; 48(11): 4692–4716.
- 24Yoo S. Evolving human competitive spectra-based fault localisation techniques. In Search Based Software Engineering: 4th International Symposium. Springer: Berlin, Heidelberg, 2012; 244–258.
- 25Abreu R, Zoeteweij P, Van Gemund AJC. An evaluation of similarity coefficients for software fault localization. In 2006 12th Pacific Rim International Symposium on Dependable Computing (PRDC'06). IEEE: Riverside, CA, 2006; 39–46.
- 26Naish L, Lee HJ, Ramamohanarao K. A model for spectra-based software diagnosis. ACM Trans Softw Eng Methodol (TOSEM). 2011; 20(3): 1–32.
- 27Jones JA, Harrold MJ, Stasko J. Visualization of test information to assist fault localization. In Proceedings of the 24th International Conference on Software Engineering. ICSE 2002. IEEE: Orlando, FL, 2002; 467–477.
- 28Du B, Cai Y, Wang H, Liu Y, Chen X. Improving the performance of mutation-based fault localization via mutant bias practical experience report. In 2022 IEEE 33rd International Symposium on Software Reliability Engineering (ISSRE). IEEE: Charlotte, NC, 2022; 309–320.
- 29Jimenez M, Checkam TT, Cordy M, Papadakis M, Kintis M, Traon YL, Harman M. Are mutants really natural? A study on how “naturalness” helps mutant selection. In Proceedings of the 12th ACM/IEEE International Symposium on Empirical Software Engineering and Measurement. ACM: New York, NY, 2018; 1–10.
- 30Papadakis M, Kintis M, Zhang J, Jia Y, Le Traon Y, Harman M. 2019. Mutation testing advances: an analysis and survey. In Advances in computers, vol. 112 Elsevier: Amsterdam, Netherlands; 275–378.
- 31Papadakis M, Le Traon Y. Effective fault localization via mutation analysis: a selective mutation approach. In Proceedings of the 29th Annual ACM Symposium on Applied Computing. ACM: New York, NY, 2014; 1293–1300.
- 32Jia Y, Harman M. Higher order mutation testing. Inform Softw Technol. 2009; 51(10): 1379–1393.
- 33Offutt AJ. Investigations of the software testing coupling effect. ACM Trans Softw Eng Methodol (TOSEM). 1992; 1(1): 5–20.
10.1145/125489.125473 Google Scholar
- 34Kintis M, Papadakis M, Malevris N. Evaluating mutation testing alternatives: a collateral experiment. In 2010 Asia Pacific Software Engineering Conference. IEEE: Sydney, NSW, 2010; 300–309.
- 35Lima JAP, Guizzo G, Vergilio SR, Silva APC, Filho HLJ, Ehrenfried HV. Evaluating different strategies for reduction of mutation testing costs. In Proceedings of the 1st Brazilian Symposium on Systematic and Automated Software Testing. ACM: New York, NY, 2016; 1–10.
- 36Nguyen QV, Madeyski L. Addressing mutation testing problems by applying multi-objective optimization algorithms and higher order mutation. J Intell Fuzzy Syst. 2017; 32(2): 1173–1182.
- 37Jang J-I, Ryu D, Baik J. HOTFUZ: cost-effective higher-order mutation-based fault localization. Softw Testing, Verif Reliab. 2022; 32(8): e1802.
- 38Nguyen QV, Madeyski L. Higher order mutation testing to drive development of new test cases: an empirical comparison of three strategies. In Asian Conference on Intelligent Information and Database Systems. Springer: Berlin, Heidelberg, 2016; 235–244.
- 39Harman M, Jia Y, Langdon WB. Strong higher order mutation-based test data generation. In Proceedings of the 19th ACM SIGSOFT Symposium and the 13th European Conference on Foundations of Software Engineering. ACM: New York, NY, 2011; 212–222.
- 40Gopinath R, Jensen C, Groce A. The theory of composite faults. In 2017 IEEE International Conference on Software Testing, Verification and Validation (ICST). IEEE: Tokyo, Japan, 2017; 47–57.
- 41Wang H, Li Z, Liu Y, Chen X, Paul D, Cai Y, Fan L. Can higher-order mutants improve the performance of mutation-based fault localization? IEEE Trans Reliab. 2022; 71(2): 1157–1173.
- 42Li Z, Shi B, Wang H, Liu Y, Chen X. HMBFL: higher-order mutation-based fault localization. In 2021 8th International Conference on Dependable Systems and Their Applications (DSA). IEEE: Yinchuan, China, 2021; 66–77.
- 43Tan SH, Yi J, Mechtaev S, Roychoudhury A, et al. Codeflaws: a programming competition benchmark for evaluating automated program repair tools. In 2017 IEEE/ACM 39th International Conference on Software Engineering Companion (ICSE-C). IEEE: Buenos Aires, Argentina, 2017; 180–182.
- 44Voas JM. PIE: a dynamic failure-based technique. IEEE Trans Softw Eng. 1992; 8: 717–727.
- 45Devore JL. Probability and statistics for engineering and the sciences. Cengage Learning: Boston, USA, 2015.
- 46Yoo S, Xie X, Kuo F-C, Chen TY, Harman M. Human competitiveness of genetic programming in spectrum-based fault localisation: theoretical and empirical analysis. ACM Trans Softw Eng Methodol (TOSEM). 2017; 26(1): 1–30.
- 47Perez A, Riboira A, Abreu R. A topology-based model for estimating the diagnostic efficiency of statistics-based approaches. In 2012 IEEE 23rd International Symposium on Software Reliability Engineering Workshops. IEEE: Dallas, TX, 2012; 171–176.
- 48Papadakis M, Chekam TT, Le Traon Y. Mutant quality indicators. In 2018 IEEE International Conference on Software Testing, Verification and Validation Workshops (ICSTW). IEEE: Västerås, Sweden, 2018; 32–39.
- 49Chekam TT, Papadakis M, Bissyandé TF, Le Traon Y, Sen K. Selecting fault revealing mutants. Empir Softw Eng. 2020; 25(1): 434–487.
- 50Yang Q, Li JJ, Weiss DM. A survey of coverage-based testing tools. Comput J. 2009; 52(5): 589–597.
- 51Agrawal H, DeMillo R, Hathaway R, Hsu W, Hsu W, Krauser EW, et al. Design of mutant operators for the C programming language, Indiana, USA, 1989.
- 52Nguyen Q-V, Pham DTH. Is higher order mutant harder to kill than first order mutant? An experimental study. In Asian Conference on Intelligent Information and Database Systems. Springer, 2018; 664–673.
- 53Wong WE, Mathur AP. Reducing the cost of mutation testing: an empirical study. J Syst Softw. 1995; 31(3): 185–196.
- 54Frankl PG, Weiss SN, Hu C. All-uses vs mutation testing: an experimental comparison of effectiveness. J Syst Softw. 1997; 38(3): 235–253.
- 55Papadakis M, Malevris N. An empirical evaluation of the first and second order mutation testing strategies. In 2010 Third International Conference on Software Testing, Verification, and Validation Workshops. IEEE: Paris, France, 2010; 90–99.
- 56Rao S, Kak A. Retrieval from software libraries for bug localization: a comparative study of generic and composite text models—a retrospective. SIGSOFT Softw Eng Notes. 2021; 46(3): 33–36. https://doi.org/10.1145/3468744.3468755
10.1145/3468744.3468755 Google Scholar
- 57Liu Y, Li M, Wu Y, Li Z. A weighted fuzzy classification approach to identify and manipulate coincidental correct test cases for fault localization. J Syst Softw. 2019; 151: 20–37.
- 58Le BT-D, Lo D, Le Goues C, Grunske L. A learning-to-rank based fault localization approach using likely invariants. In Proceedings of the 25th International Symposium on Software Testing and Analysis. ISSTA 2016. ACM: New York, NY, 2016; 177–188. https://doi.org/10.1145/2931037.2931049
10.1145/2931037.2931049 Google Scholar
- 59Kochhar PS, Xia X, Lo D, Li S. Practitioners' expectations on automated fault localization. In Proceedings of the 25th International Symposium on Software Testing and Analysis. ACM: New York, NY, 2016; 165–176. https://doi.org/10.1145/2931037.2931051
10.1145/2931037.2931051 Google Scholar
- 60Sohn J, Yoo S. FLUCCS: using code and change metrics to improve fault localization. In Proceedings of the 26th ACM SIGSOFT International Symposium on Software Testing and Analysis. ACM: New York, NY, 2017; 273–283. https://doi.org/10.1145/3092703.3092717
10.1145/3092703.3092717 Google Scholar
- 61Li X, Li W, Zhang Y, Zhang L. DeepFL: integrating multiple fault diagnosis dimensions for deep fault localization. In Proceedings of the 28th ACM SIGSOFT International Symposium on Software Testing and Analysis. ACM: New York, NY, 2019; 169–180. https://doi.org/10.1145/3293882.3330574
10.1145/3293882.3330574 Google Scholar
- 62Moffat A, Zobel J. Rank-biased precision for measurement of retrieval effectiveness. ACM Trans Inform Syst (TOIS). 2008; 27(1): 2.
- 63Zhang L, Marinov D, Khurshid S. Faster mutation testing inspired by test prioritization and reduction. In Proceedings of the 2013 International Symposium on Software Testing and Analysis. ACM: New York, NY, 2013; 235–245. https://doi.org/10.1145/2483760.2483782
10.1145/2483760.2483782 Google Scholar
- 64Just R, Ernst MD, Fraser G. Efficient mutation analysis by propagating and partitioning infected execution states. In Proceedings of the 2014 International Symposium on Software Testing and Analysis. ACM: New York, NY, USA, 2014; 315–326. https://doi.org/10.1145/2610384.2610388
10.1145/2610384.2610388 Google Scholar
- 65Liu Y, Li Z, Wang L, Hu Z, Zhao R. Statement-oriented mutant reduction strategy for mutation based fault localization. In 2017 IEEE International Conference on Software Quality, Reliability and Security (QRS). IEEE: Prague, Czech Republic, 2017; 126–137.
- 66Wilcoxon F. Individual comparisons by ranking methods. Biometr Bull. 1945; 1945: 80–83.
10.2307/3001968 Google Scholar
- 67Cohen J. Statistical power analysis for the behavioral sciences. Academic Press: New York, USA, 2013.
10.4324/9780203771587 Google Scholar
- 68Just R, Jalali D, Ernst MD. Defects4J: a database of existing faults to enable controlled testing studies for Java programs. In Proceedings of the 2014 International Symposium on Software Testing and Analysis. ACM: New York, NY, 2014; 437–440.
- 69Lindström B, Márki A. On strong mutation and the theory of subsuming logic-based mutants. Softw Test Verif Reliab. 2019; 29(1–2): e1667. https://doi.org/10.1002/stvr.1667
- 70Do Prado Lima JA, Vergilio SR. A systematic mapping study on higher order mutation testing. J Syst Softw. 2019; 154: 92–109.
- 71Lou Y, Zhu Q, Dong J, Li X, Sun Z, Hao D, et al. Boosting coverage-based fault localization via graph-based representation learning. In Proceedings of the 29th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering. ACM: New York, NY, 2021; 664–676. https://doi.org/10.1145/3468264.3468580
10.1145/3468264.3468580 Google Scholar
- 72Hu J, Xie H, Lei Y, Yu K. A light-weight data augmentation method for fault localization. Inform Softw Technol. 2023; 2023:107148.
10.1016/j.infsof.2023.107148 Google Scholar