June 12-15, 2005, Chicago, Illinois, USA | Ben Liblit, Mayur Naik, Alice X. Zheng, Alex Aiken, Michael I. Jordan
This paper presents a statistical debugging algorithm designed to isolate bugs in programs with multiple undiagnosed bugs. Unlike previous statistical algorithms that struggle with multiple bugs, the new technique separates the effects of different bugs and identifies predictors associated with individual bugs. These predictors reveal both the circumstances under which bugs occur and the frequencies of failure modes, making it easier to prioritize debugging efforts. The algorithm is validated through several case studies, including examples where it identified previously unknown, significant crashing bugs in widely used systems.
The paper discusses the challenges of applying statistical debugging to large programs, such as the redundancy of predicates and the prevalence of predicates predicting multiple bugs. It introduces a new algorithm that addresses these issues by ranking predictors based on their importance and accuracy. The algorithm is validated through experiments, showing improved results over previous methods. The paper also demonstrates that relatively few runs are sufficient to isolate all bugs, making the approach feasible for both in-house automatic testing and deployment to end users.
The background section explains the instrumentation techniques used to monitor program behavior, including random sampling and client-side data summarization. The cause isolation algorithm is detailed, explaining how it simulates the iterative process of identifying and fixing bugs. The paper discusses the statistical interpretation of the algorithm and the balancing of specificity and sensitivity in ranking predictors.
Experiments with five case studies, including MOSS, CCRYPT, BC, EXIF, and RHYTHMBOX, demonstrate the effectiveness of the algorithm. The results show that the algorithm can isolate previously unknown bugs and provide valuable insights into their causes. The paper concludes by estimating the number of runs needed to identify all bug predictors, suggesting that the approach is efficient and practical for real-world applications.This paper presents a statistical debugging algorithm designed to isolate bugs in programs with multiple undiagnosed bugs. Unlike previous statistical algorithms that struggle with multiple bugs, the new technique separates the effects of different bugs and identifies predictors associated with individual bugs. These predictors reveal both the circumstances under which bugs occur and the frequencies of failure modes, making it easier to prioritize debugging efforts. The algorithm is validated through several case studies, including examples where it identified previously unknown, significant crashing bugs in widely used systems.
The paper discusses the challenges of applying statistical debugging to large programs, such as the redundancy of predicates and the prevalence of predicates predicting multiple bugs. It introduces a new algorithm that addresses these issues by ranking predictors based on their importance and accuracy. The algorithm is validated through experiments, showing improved results over previous methods. The paper also demonstrates that relatively few runs are sufficient to isolate all bugs, making the approach feasible for both in-house automatic testing and deployment to end users.
The background section explains the instrumentation techniques used to monitor program behavior, including random sampling and client-side data summarization. The cause isolation algorithm is detailed, explaining how it simulates the iterative process of identifying and fixing bugs. The paper discusses the statistical interpretation of the algorithm and the balancing of specificity and sensitivity in ranking predictors.
Experiments with five case studies, including MOSS, CCRYPT, BC, EXIF, and RHYTHMBOX, demonstrate the effectiveness of the algorithm. The results show that the algorithm can isolate previously unknown bugs and provide valuable insights into their causes. The paper concludes by estimating the number of runs needed to identify all bug predictors, suggesting that the approach is efficient and practical for real-world applications.