skip to main content
10.1145/1065010.1065014acmconferencesArticle/Chapter ViewAbstractPublication PagespldiConference Proceedingsconference-collections
Article

Scalable statistical bug isolation

Published: 12 June 2005 Publication History

Abstract

We present a statistical debugging algorithm that isolates bugs in programs containing multiple undiagnosed bugs. Earlier statistical algorithms that focus solely on identifying predictors that correlate with program failure perform poorly when there are multiple bugs. Our new technique separates the effects of different bugs and identifies predictors that are associated with individual bugs. These predictors reveal both the circumstances under which bugs occur as well as the frequencies of failure modes, making it easier to prioritize debugging efforts. Our algorithm is validated using several case studies, including examples in which the algorithm identified previously unknown, significant crashing bugs in widely used systems.

References

[1]
J. Bowring, A. Orso, and M. J. Harrold. Monitoring deployed software using software tomography. In M. B. Dwyer, editor, Proceedings of the 2002 ACM SIGPLAN-SIGSOFT workshop on Program analysis for software tools and engineering (PASTE-02), volume 28, 1 of SOFTWARE ENGINEERING NOTES, pages 2--9. ACM Press, 2002.
[2]
L. Burnell and E. Horvitz. Structure and chance: melding logic and probability for software debugging. Communications of the ACM, 38(3):31--41, 57, Mar. 1995.
[3]
T. Chilimbi and M. Hauswirth. Low-overhead memory leak detection using adaptive statistical profiling. In ASPLOS: Eleventh International Conference on Architectural Support for Programming Languages and Operating Systems, Boston, MA, Oct. 2004.
[4]
S. Elbaum and M. Hardojo. Deploying instrumented software to assist the testing activity. In RAMSS 2003 RAMSS:2003, pages 31--33.
[5]
M. D. Ernst, J. Cockrell, W. G. Griswold, and D. Notkin. Dynamically discovering likely program invariants to support program evolution. IEEE Transactions on Software Engineering, 27(2):1--25, Feb. 2001.
[6]
K. C. Gross, S. McMaster, A. Porter, A. Urmanov, and L. G. Votta. Proactive system maintenance using software telemetry. In RAMSS 2003 RAMSS:2003, pages 24--26.
[7]
S. Hangal and M. S. Lam. Tracking down software bugs using automatic anomaly detection. In Proceedings of the 24th International Conference on Software Engineering (ICSE-02), pages 291--301. ACM Press, 2002.
[8]
E. Lehmann. Testing Statistical Hypotheses. John Wiley & Sons, 2nd edition, 1986.
[9]
E. Lehmann and G. Casella. Theory of Point Estimation. Springer, 2nd edition, 2003.
[10]
B. Liblit, A. Aiken, A. X. Zheng, and M. I. Jordan. Bug isolation via remote program sampling. In J. James B. Fenwick and C. Norris, editors, Proceedings of the ACM SIGPLAN 2003 Conference on Programming Language Design and Implementation (PLDI-03), volume 38, 5 of ACM SIGPLAN Notices, pages 141--154. ACM Press, 2003.
[11]
B. Liblit, M. Naik, A. X. Zheng, A. Aiken, and M. I. Jordan. Public deployment of cooperative bug isolation. In Proceedings of the Second International Workshop on Remote Analysis and Measurement of Software Systems (RAMSS '04), pages 57--62, Edinburgh, Scotland, May 24 2004.
[12]
A. Orso, T. Apiwattanapong, and M. J. Harrold. Leveraging field data for impact analysis and regression testing. In Proceedings of the 9th European software engineering conference held jointly with 11th ACM SIGSOFT international symposium on Foundations of software engineering, pages 128--137. ACM Press, 2003.
[13]
A. Podgurski, D. Leon, P. Francis, W. Masri, M. Minch, J. Sun, and B. Wang. Automated support for classifying software failure reports. In Proceedings of the 25th International Conference on Software Engineering (ICSE-03), pages 465--477. IEEE Computer Society, 2003.
[14]
RAMSS '03: The 1st International Workshop on Remote Analysis and Measurement of Software Systems, May 2003.
[15]
S. Schleimer, D. S. Wilkerson, and A. Aiken. Winnowing: local algorithms for document fingerprinting. In ACM, editor, Proceedings of the 2003 ACM SIGMOD International Conference on Management of Data 2003, San Diego, California, June 09--12, 2003, pages 76--85, New York, NY 10036, USA, 2003. ACM Press.
[16]
A. X. Zheng, M. I. Jordan, B. Liblit, and A. Aiken. Statistical debugging of sampled programs. In S. Thrun, L. Saul, and B. Schölkopf, editors, Advances in Neural Information Processing Systems 16. MIT Press, Cambridge, MA, 2004.

Cited By

View all
  • (2023)Variable-based Fault Localization via Enhanced Decision TreeACM Transactions on Software Engineering and Methodology10.1145/362474133:2(1-32)Online publication date: 18-Sep-2023
  • (2023)Semantic DebuggingProceedings of the 31st ACM Joint European Software Engineering Conference and Symposium on the Foundations of Software Engineering10.1145/3611643.3616296(438-449)Online publication date: 30-Nov-2023
  • (2023)Blindspots in Python and Java APIs Result in Vulnerable CodeACM Transactions on Software Engineering and Methodology10.1145/357185032:3(1-31)Online publication date: 26-Apr-2023
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
PLDI '05: Proceedings of the 2005 ACM SIGPLAN conference on Programming language design and implementation
June 2005
338 pages
ISBN:1595930566
DOI:10.1145/1065010
  • cover image ACM SIGPLAN Notices
    ACM SIGPLAN Notices  Volume 40, Issue 6
    Proceedings of the 2005 ACM SIGPLAN conference on Programming language design and implementation
    June 2005
    325 pages
    ISSN:0362-1340
    EISSN:1558-1160
    DOI:10.1145/1064978
    Issue’s Table of Contents
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 ACM 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: 12 June 2005

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. bug isolation
  2. feature selection
  3. invariants
  4. random sampling
  5. statistical debugging

Qualifiers

  • Article

Conference

PLDI05
Sponsor:

Acceptance Rates

Overall Acceptance Rate 406 of 2,067 submissions, 20%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)46
  • Downloads (Last 6 weeks)10
Reflects downloads up to 20 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2023)Variable-based Fault Localization via Enhanced Decision TreeACM Transactions on Software Engineering and Methodology10.1145/362474133:2(1-32)Online publication date: 18-Sep-2023
  • (2023)Semantic DebuggingProceedings of the 31st ACM Joint European Software Engineering Conference and Symposium on the Foundations of Software Engineering10.1145/3611643.3616296(438-449)Online publication date: 30-Nov-2023
  • (2023)Blindspots in Python and Java APIs Result in Vulnerable CodeACM Transactions on Software Engineering and Methodology10.1145/357185032:3(1-31)Online publication date: 26-Apr-2023
  • (2023)Diagnosing Kernel Concurrency Failures with AITIAProceedings of the Eighteenth European Conference on Computer Systems10.1145/3552326.3567486(94-110)Online publication date: 8-May-2023
  • (2023)Toward More Efficient Statistical Debugging with Abstraction RefinementACM Transactions on Software Engineering and Methodology10.1145/354479032:2(1-38)Online publication date: 30-Mar-2023
  • (2023)iBiR: Bug-report-driven Fault InjectionACM Transactions on Software Engineering and Methodology10.1145/354294632:2(1-31)Online publication date: 30-Mar-2023
  • (2023)PASD: A Performance Analysis Approach Through the Statistical Debugging of Kernel Events2023 IEEE 23rd International Working Conference on Source Code Analysis and Manipulation (SCAM)10.1109/SCAM59687.2023.00025(151-161)Online publication date: 2-Oct-2023
  • (2023)Locating Framework-Specific Crashing Faults with Compact and Explainable Candidate SetProceedings of the 45th International Conference on Software Engineering10.1109/ICSE48619.2023.00026(172-183)Online publication date: 14-May-2023
  • (2023)Evaluating the Impact of Experimental Assumptions in Automated Fault LocalizationProceedings of the 45th International Conference on Software Engineering10.1109/ICSE48619.2023.00025(159-171)Online publication date: 14-May-2023
  • (2023)From Input to Failure: Explaining Program Behavior via Cause-Effect ChainsProceedings of the 45th International Conference on Software Engineering: Companion Proceedings10.1109/ICSE-Companion58688.2023.00081(302-304)Online publication date: 14-May-2023
  • Show More Cited By

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media