Scalable Statistical Bug Isolation

Scalable Statistical Bug Isolation

June 12-15, 2005 | Ben Liblit, Mayur Naik, Alice X. Zheng, Alex Aiken, Michael I. Jordan
This paper presents a statistical debugging algorithm that isolates bugs in programs with multiple undiagnosed bugs. Previous statistical debugging methods focused on identifying predictors correlated with program failure but struggled with multiple bugs. The new technique separates the effects of different bugs and identifies predictors associated with individual bugs, revealing failure conditions and failure mode frequencies. The algorithm is validated through case studies, including identifying previously unknown, significant crashing bugs in widely used systems. The algorithm uses feedback reports from program runs, where each report includes a bit indicating success or failure and a bit vector for each predicate. A predicate is a bug predictor if it statistically likely indicates a failure. The algorithm selects a subset of predicates that predict all bugs and ranks them by importance. It addresses scalability issues in regularized logistic regression, such as predicate redundancy, multiple bug predictors, and varying bug occurrence rates. The algorithm identifies bug predictors by calculating the probability that a predicate being true implies failure. It also considers the context of a predicate being observed, distinguishing between deterministic and non-deterministic bugs. The algorithm ranks predicates based on their increase in failure probability when observed, and uses statistical significance to filter out irrelevant predictors. The algorithm is validated through experiments showing improved results over previous methods. It successfully isolates bugs in complex applications and identifies previously unknown serious crashing bugs in open source applications. The algorithm is effective for both in-house testing and deployment to end users. It can help isolate any type of failure, not just program crashes, by labeling runs as successful or unsuccessful. The algorithm uses sparse random sampling and client-side data summarization to reduce performance overhead. It tracks various program behaviors, such as branch conditions, return values, and scalar relationships. The algorithm isolates bugs by iteratively identifying and removing the most important predictors, reducing the number of predicates to examine. The algorithm is effective in reducing the number of predicates to examine, with significant reductions in large applications. It handles redundancy by eliminating predictors that do not contribute to bug isolation. The algorithm is validated through experiments with various applications, including MOSS, CCRYPT, BC, EXIF, and RHYTHMBOX. It successfully isolates bugs in these applications, demonstrating its effectiveness in identifying and fixing bugs. The algorithm provides a complementary approach to static analysis, identifying bugs beyond the reach of current static analysis techniques.This paper presents a statistical debugging algorithm that isolates bugs in programs with multiple undiagnosed bugs. Previous statistical debugging methods focused on identifying predictors correlated with program failure but struggled with multiple bugs. The new technique separates the effects of different bugs and identifies predictors associated with individual bugs, revealing failure conditions and failure mode frequencies. The algorithm is validated through case studies, including identifying previously unknown, significant crashing bugs in widely used systems. The algorithm uses feedback reports from program runs, where each report includes a bit indicating success or failure and a bit vector for each predicate. A predicate is a bug predictor if it statistically likely indicates a failure. The algorithm selects a subset of predicates that predict all bugs and ranks them by importance. It addresses scalability issues in regularized logistic regression, such as predicate redundancy, multiple bug predictors, and varying bug occurrence rates. The algorithm identifies bug predictors by calculating the probability that a predicate being true implies failure. It also considers the context of a predicate being observed, distinguishing between deterministic and non-deterministic bugs. The algorithm ranks predicates based on their increase in failure probability when observed, and uses statistical significance to filter out irrelevant predictors. The algorithm is validated through experiments showing improved results over previous methods. It successfully isolates bugs in complex applications and identifies previously unknown serious crashing bugs in open source applications. The algorithm is effective for both in-house testing and deployment to end users. It can help isolate any type of failure, not just program crashes, by labeling runs as successful or unsuccessful. The algorithm uses sparse random sampling and client-side data summarization to reduce performance overhead. It tracks various program behaviors, such as branch conditions, return values, and scalar relationships. The algorithm isolates bugs by iteratively identifying and removing the most important predictors, reducing the number of predicates to examine. The algorithm is effective in reducing the number of predicates to examine, with significant reductions in large applications. It handles redundancy by eliminating predictors that do not contribute to bug isolation. The algorithm is validated through experiments with various applications, including MOSS, CCRYPT, BC, EXIF, and RHYTHMBOX. It successfully isolates bugs in these applications, demonstrating its effectiveness in identifying and fixing bugs. The algorithm provides a complementary approach to static analysis, identifying bugs beyond the reach of current static analysis techniques.
Reach us at info@study.space