A Bayesian Framework for Automated Debugging
Pages 880 - 891
Abstract
Debugging takes up a significant portion of developer time. As a result, automated debugging techniques including Fault Localization (FL) and Automated Program Repair (APR) have garnered significant attention due to their potential to aid developers in debugging tasks. With the recent advance in techniques that treat the two tasks as closely coupled, such as Unified Debugging, a framework to formally express these two tasks together would heighten our understanding of automated debugging and provide a way to formally analyze techniques and approaches. To this end, we propose a Bayesian framework of understanding automated debugging. We find that the Bayesian framework, along with a concrete statement of the objective of automated debugging, can recover maximal fault localization formulae from prior work, as well as analyze existing APR techniques and their underlying assumptions. As a means of empirically demonstrating our framework, we further propose BAPP, a Bayesian Patch Prioritization technique that incorporates intermediate program values to analyze likely patch locations and repair actions, with its core equations being derived by our Bayesian framework. We find that incorporating program values allows BAPP to identify correct patches more precisely: the rankings produced by BAPP reduced the number of required patch evaluations by 68% and consequently reduced the repair time by 34 minutes on average. Further, our Bayesian framework suggests a number of changes to the way fault localization information is used in program repair, which we validate is useful for BAPP. These results highlight the potential of value-cognizant automated debugging techniques, and further verifies our theoretical framework.
References
[1]
Rawad Abou Assi, Chadi Trad, Marwan Maalouf, and Wes Masri. 2019. Coincidental correctness in the Defects4J benchmark. Software Testing, Verification and Reliability, 29 (2019), 03, https://doi.org/10.1002/stvr.1696
[2]
Rui Abreu and Arjan J. C. van Gemund. 2009. A Low-Cost Approximate Minimal Hitting Set Algorithm and its Application to Model-Based Diagnosis. In SARA.
[3]
R. Abreu, P. Zoeteweij, and A.J.C. van Gemund. 2009. Spectrum-Based Multiple Fault Localization. In Proceedings of the 24th IEEE/ACM International Conference on Automated Software Engineering (ASE 2009). 88–99. issn:1938-4300 https://doi.org/10.1109/ASE.2009.25
[4]
Gabin An, Juyeon Yoon, Jeongju Sohn, Jingun Hong, Dongwon Hwang, and Shin Yoo. 2022. Automatically Identifying Shared Root Causes of Test Breakages in SAP HANA. In Proceedings of the 44th IEEE/ACM International Conference on Software Engineering - Software Engineering In Practice Track (ICSE SEIP 2022). 65–74.
[5]
Samuel Benton, Yuntong Xie, Lan Lu, Mengshi Zhang, Xia Li, and Lingming Zhang. 2022. Towards Boosting Patch Execution On-the-Fly. In 2022 IEEE/ACM 44th International Conference on Software Engineering (ICSE). 2165–2176. https://doi.org/10.1145/3510003.3510117
[6]
Mariano Ceccato, Alessandro Marchetto, Leonardo Mariani, Cu D. Nguyen, and Paolo Tonella. 2012. An empirical study about the effectiveness of debugging when random test cases are used. In 2012 34th International Conference on Software Engineering (ICSE). 452–462. https://doi.org/10.1109/ICSE.2012.6227170
[7]
Zimin Chen, Steve Kommrusch, Michele Tufano, L. Pouchet, D. Poshyvanyk, and Monperrus Martin. 2019. SequenceR: Sequence-to-Sequence Learning for End-to-End Program Repair. ArXiv, abs/1901.01808 (2019).
[8]
Thomas Durieux and Martin Monperrus. 2016. DynaMoth: Dynamic Code Synthesis for Automatic Program Repair. In 2016 IEEE/ACM 11th International Workshop in Automation of Software Test (AST). 85–91. https://doi.org/10.1145/2896921.2896931
[9]
Shin Hong, Taehoon Kwak, Byeongcheol Lee, Yiru Jeon, Bongsuk Ko, Yunho Kim, and Moonzoo Kim. 2017. MUSEUM: Debugging Real-World Multilingual Programs Using Mutation Analysis. Information and Software Technology, 82 (2017), 80–95.
[10]
James A. Jones, Mary Jean Harrold, and John Stasko. 2002. Visualization of test information to assist fault localization. In Proceedings of the 24th International Conference on Software Engineering. ACM, New York, NY, USA. 467–477.
[11]
Dongsun Kim, Jaechang Nam, Jaewoo Song, and Sunghun Kim. 2013. Automatic Patch Generation Learned from Human-written Patches. In Proceedings of the 2013 International Conference on Software Engineering (ICSE ’13). IEEE Press, Piscataway, NJ, USA. 802–811. isbn:978-1-4673-3076-3
[12]
Serkan Kirbas, Etienne Windels, Olayori McBello, Kevin Kells, Matthew Pagano, Rafal Szalanski, Vesna Nowack, Emily Rowan Winter, Steve Counsell, David Bowes, Tracy Hall, Saemundur Haraldsson, and John Woodward. 2021. On The Introduction of Automatic Program Repair in Bloomberg. IEEE Software, 38, 4 (2021), 43–51. https://doi.org/10.1109/MS.2021.3071086
[13]
Pavneet Singh Kochhar, Xin Xia, David Lo, and Shanping Li. 2016. Practitioners’ Expectations on Automated Fault Localization. In Proceedings of the 25th International Symposium on Software Testing and Analysis (ISSTA 2016). Association for Computing Machinery, New York, NY, USA. 165–176. isbn:9781450343909
[14]
Anil Koyuncu, Kui Liu, Tegawendé F. Bissyandé, Dongsun Kim, Jacques Klein, Martin Monperrus, and Yves Le Traon. 2020. FixMiner: Mining Relevant Fix Patterns for Automated Program Repair. Empirical Softw. Engg., 25, 3 (2020), may, 1980–2024. issn:1382-3256 https://doi.org/10.1007/s10664-019-09780-z
[15]
Claire Le Goues, ThanhVu Nguyen, Stephanie Forrest, and Westley Weimer. 2012. GenProg: A Generic Method for Automatic Software Repair. IEEE Transactions on Software Engineering, 38, 1 (2012), 54–72. https://doi.org/10.1109/TSE.2011.104
[16]
Claire Le Goues, Michael Pradel, Abhik Roychoudhury, and Satish Chandra. 2021. Automatic Program Repair. IEEE Software, 38, 4 (2021), 22–27. https://doi.org/10.1109/MS.2021.3072577
[17]
Xia Li, Wei Li, Yuqun Zhang, and Lingming Zhang. 2019. DeepFL: Integrating Multiple Fault Diagnosis Dimensions for Deep Fault Localization. In Proceedings of the 28th ACM SIGSOFT International Symposium on Software Testing and Analysis (ISSTA 2019). Association for Computing Machinery, New York, NY, USA. 169–180. isbn:9781450362245 https://doi.org/10.1145/3293882.3330574
[18]
Kui Liu, Anil Koyuncu, Tegawendé F. Bissyandé, Dongsun Kim, Jacques Klein, and Yves Le Traon. 2019. You Cannot Fix What You Cannot Find! An Investigation of Fault Localization Bias in Benchmarking Automated Program Repair Systems. In 2019 12th IEEE Conference on Software Testing, Validation and Verification (ICST). 102–113. https://doi.org/10.1109/ICST.2019.00020
[19]
Kui Liu, Shangwen Wang, Anil Koyuncu, Kisub Kim, Tegawendé F. Bissyandé, Dongsun Kim, Peng Wu, Jacques Klein, Xiaoguang Mao, and Yves Le Traon. 2020. On the Efficiency of Test Suite based Program Repair A Systematic Assessment of 16 Automated Repair Systems for Java Programs. 2020 IEEE/ACM 42nd International Conference on Software Engineering (ICSE), 615–627.
[20]
Fan Long and Martin Rinard. 2016. Automatic Patch Generation by Learning Correct Code. In Proceedings of the 43rd Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL ’16). Association for Computing Machinery, New York, NY, USA. 298–312. isbn:9781450335492 https://doi.org/10.1145/2837614.2837617
[21]
Yiling Lou, Ali Ghanbari, Xia Li, Lingming Zhang, Haotian Zhang, Dan Hao, and Lu Zhang. 2020. 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). Association for Computing Machinery, New York, NY, USA. 75–87.
[22]
Yiling Lou, Ali Ghanbari, Xia Li, Lingming Zhang, Haotian Zhang, Dan Hao, and Lu Zhang. 2020. 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. ACM. https://doi.org/10.1145/3395363.3397351
[23]
Alexandru Marginean, Johannes Bader, Satish Chandra, Mark Harman, Yue Jia, Ke Mao, Alexander Mols, and Andrew Scott. 2019. SapFix: Automated End-to-End Repair at Scale. In 2019 IEEE/ACM 41st International Conference on Software Engineering: Software Engineering in Practice (ICSE-SEIP). 269–278. https://doi.org/10.1109/ICSE-SEIP.2019.00039
[24]
Sergey Mechtaev, Jooyong Yi, and Abhik Roychoudhury. 2015. Directfix: Looking for simple program repairs. In 2015 IEEE/ACM 37th IEEE International Conference on Software Engineering. 448–458.
[25]
S. Mechtaev, J. Yi, and A. Roychoudhury. 2016. Angelix: Scalable Multiline Program Patch Synthesis via Symbolic Analysis. In 2016 IEEE/ACM 38th International Conference on Software Engineering (ICSE). 691–701.
[26]
Seokhyeon Moon, Yunho Kim, Moonzoo Kim, and Shin Yoo. 2014. Ask the Mutants: Mutating Faulty Programs for Fault Localization. In 2014 IEEE Seventh International Conference on Software Testing, Verification and Validation. 153–162. https://doi.org/10.1109/ICST.2014.28
[27]
Akira Ochiai. 1957. Zoogeographic studies on the soleoid fishes found in Japan and its neighbouring regions. Bulletin of Japanese Society of Scientific Fisheries, 22 (1957), 526–530.
[28]
Kai Pan, Sunghun Kim, and E. James Whitehead. 2009. Toward an Understanding of Bug Fix Patterns. Empirical Softw. Engg., 14, 3 (2009), jun, 286–315. issn:1382-3256 https://doi.org/10.1007/s10664-008-9077-5
[29]
Chris Parnin and Alessandro Orso. 2011. Are automated debugging techniques actually helping programmers? In Proceedings of the 2011 International Symposium on Software Testing and Analysis (ISSTA 2011). ACM, New York, NY, USA. 199–209.
[30]
Ripon K. Saha, Yingjun Lyu, Hiroaki Yoshida, and Mukul R. Prasad. 2017. Elixir: Effective object-oriented program repair. In 2017 32nd IEEE/ACM International Conference on Automated Software Engineering (ASE). 648–659. https://doi.org/10.1109/ASE.2017.8115675
[31]
Jeongju Sohn and Shin Yoo. 2017. FLUCCS: Using Code and Change Metrics to Improve Fault Localization. In Proceedings of the 26th ACM SIGSOFT International Symposium on Software Testing and Analysis (ISSTA 2017). Association for Computing Machinery, New York, NY, USA. 273–283. isbn:9781450350761 https://doi.org/10.1145/3092703.3092717
[32]
Yi Song, Xiaoyuan Xie, Xihao Zhang, Quanming Liu, and Ruizhi Gao. 2023. Evolving Ranking-Based Failure Proximities for Better Clustering in Fault Isolation. In Proceedings of the 37th IEEE/ACM International Conference on Automated Software Engineering (ASE ’22). Association for Computing Machinery, New York, NY, USA. Article 41, 13 pages. isbn:9781450394758
[33]
Gregory Tassey. 2002. The Economic Impacts of Inadequate Infrastructure for Software Testing. 05.
[34]
Chris Thunes. 2022. javalang: Pure Python Java parser and tools. https://github.com/c2nes/javalang
[35]
W. Weimer, Z. P. Fry, and S. Forrest. 2013. Leveraging program equivalence for adaptive program repair: Models and first results. In 2013 28th IEEE/ACM International Conference on Automated Software Engineering (ASE). 356–366.
[36]
Ming Wen, Junjie Chen, Yongqiang Tian, Rongxin Wu, Dan Hao, Shi Han, and Shing-Chi Cheung. 2021. Historical Spectrum Based Fault Localization. IEEE Transactions on Software Engineering, 47, 11 (2021), 2348–2368. https://doi.org/10.1109/TSE.2019.2948158
[37]
W. Eric Wong, Yu Qi, Lei Zhao, and Kai-Yuan Cai. 2007. Effective Fault Localization using Code Coverage. In 31st Annual International Computer Software and Applications Conference (COMPSAC 2007). 1, 449–456. https://doi.org/10.1109/COMPSAC.2007.109
[38]
Xiaoyuan Xie, Tsong Yueh Chen, Fei-Ching Kuo, and Baowen Xu. 2013. A Theoretical Analysis of the Risk Evaluation Formulas for Spectrum-based Fault Localization. ACM Transactions on Software Engineering Methodology, 22, 4 (2013), Article 31, October, 40 pages. issn:1049-331X
[39]
Xuezheng Xu, Yulei Sui, Hua Yan, and Jingling Xue. 2019. VFix: Value-Flow-Guided Precise Program Repair for Null Pointer Dereferences. In Proceedings of the 41st International Conference on Software Engineering (ICSE ’19). IEEE Press, 512–523. https://doi.org/10.1109/ICSE.2019.00063
[40]
He Ye, Matias Martinez, Xiapu Luo, Tao Zhang, and Martin Monperrus. 2022. SelfAPR: Self-supervised Program Repair with Test Execution Diagnostics. https://doi.org/10.48550/ARXIV.2203.12755
[41]
Shin Yoo, Xiaoyuan Xie, Fei-Ching Kuo, Tsong Yueh Chen, and Mark Harman. 2014. No Pot of Gold at the End of Program Spectrum Rainbow: Greatest Risk Evaluation Formula Does Not Exist. University College London.
[42]
Shin Yoo, Xiaoyuan Xie, Fei-Ching Kuo, Tsong Yueh Chen, and Mark Harman. 2017. Human Competitiveness of Genetic Programming in SBFL: Theoretical and Empirical Analysis. ACM Transactions on Software Engineering and Methodology, 26, 1 (2017), July, 4:1–4:30.
[43]
Muhan Zeng, Yiqian Wu, Zhentao Ye, Yingfei Xiong, Xin Zhang, and Lu Zhang. 2022. Fault Localization via Efficient Probabilistic Modeling of Program Semantics. In 2022 IEEE/ACM 44th International Conference on Software Engineering (ICSE). 958–969. https://doi.org/10.1145/3510003.3510073
[44]
Qihao Zhu, Zeyu Sun, Yuan-an Xiao, Wenjie Zhang, Kang Yuan, Yingfei Xiong, and Lu Zhang. 2021. A Syntax-Guided Edit Decoder for Neural Program Repair. In Proceedings of the 29th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering (ESEC/FSE 2021). Association for Computing Machinery, New York, NY, USA. 341–353. isbn:9781450385626 https://doi.org/10.1145/3468264.3468544
Index Terms
- A Bayesian Framework for Automated Debugging
Recommendations
Using automated program repair for evaluating the effectiveness of fault localization techniques
ISSTA 2013: Proceedings of the 2013 International Symposium on Software Testing and AnalysisMany techniques on automated fault localization (AFL) have been introduced to assist developers in debugging. Prior studies evaluate the localization technique from the viewpoint of developers: measuring how many benefits that developers can obtain ...
Empirical Effectiveness Evaluation of Spectra-Based Fault Localization on Automated Program Repair
COMPSAC '13: Proceedings of the 2013 IEEE 37th Annual Computer Software and Applications ConferenceResearchers have proposed many spectra-based fault localization (SBFL) techniques in the past decades. Existing studies evaluate the effectiveness of these techniques from the viewpoint of developers, and have drawn some important conclusions through ...
Comparing developer-provided to user-provided tests for fault localization and automated program repair
ISSTA 2018: Proceedings of the 27th ACM SIGSOFT International Symposium on Software Testing and AnalysisTo realistically evaluate a software testing or debugging technique, it must be run on defects and tests that are characteristic of those a developer would encounter in practice. For example, to determine the utility of a fault localization or automated ...
Comments
Information & Contributors
Information
Published In
July 2023
1554 pages
Copyright © 2023 ACM.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].
Sponsors
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 13 July 2023
Check for updates
Author Tags
Qualifiers
- Research-article
Conference
ISSTA '23
Sponsor:
ISSTA '23: 32nd ACM SIGSOFT International Symposium on Software Testing and Analysis
July 17 - 21, 2023
WA, Seattle, USA
Acceptance Rates
Overall Acceptance Rate 58 of 213 submissions, 27%
Upcoming Conference
ISSTA '25
- Sponsor:
- sigsoft
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 196Total Downloads
- Downloads (Last 12 months)74
- Downloads (Last 6 weeks)0
Reflects downloads up to 18 Feb 2025
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in