Article

Bug isolation via remote program sampling

Authors:

Alice X. Zheng,

Michael I. JordanAuthors Info & Claims

PLDI '03: Proceedings of the ACM SIGPLAN 2003 conference on Programming language design and implementation

Pages 141 - 154

https://doi.org/10.1145/781131.781148

Published: 09 May 2003 Publication History

Abstract

We propose a low-overhead sampling infrastructure for gathering information from the executions experienced by a program's user community. Several example applications illustrate ways to use sampled instrumentation to isolate bugs. Assertion-dense code can be transformed to share the cost of assertions among many users. Lacking assertions, broad guesses can be made about predicates that predict program errors and a process of elimination used to whittle these down to the true bug. Finally, even for non-deterministic bugs such as memory corruption, statistical modeling based on logistic regression allows us to identify program behaviors that are strongly correlated with failure and are therefore likely places to look for the error.

References

[1]

J. M. Anderson, L. M. Berc, J. Dean, S. Ghemawat, M. R. Henzinger, S.-T. A. Leung, R. L. Sites, M. T. Vandevoorde, C. A. Waldspurger, and W. E. Weihl. Continuous profiling: Where have all the cycles gone? ACM Transactions on Computer Systems, 15(4):357--390, Nov. 1997.

Digital Library

[2]

M. Arnold and B. Ryder. A framework for reducing the cost of instrumented code. ACM SIGPLAN Notices, 36(5):168--179, May 2001.

Digital Library

[3]

M. Arnold and P. F. Sweeney. Approximating the calling context tree via sampling. Research report RC 21789 (98099), IBM T.J. Watson Research Center, Yorktown Heights, New York, July 7 2000.

[4]

Association for Computing Machinery. Proceedings of the International Conference on Software Engineering, Buenos Aires, Argentina, May 2002.

[5]

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.

Digital Library

[6]

L. Breiman, J. H. Friedman, R. A. Olshen, and C. J. Stone. Classification and Regression Trees. Statistics/Probability Series. Wadsworth Publishing Company, Belmont, California, U.S.A., 1984.

[7]

P. Broadwell, M. Harren, and N. Sastry. Scrash: A system for generating secure crash information. In Proceedings of the 11th USENIX Security Symposium, Washington, DC, Aug. 4--8 2003. To appear.

Digital Library

[8]

M. Burrows, U. Erlingson, S.-T. Leung, M. Vandevoorde, C. Waldspurger, K. Walker, and B. Weihl. Efficient and flexible value sampling. ACM SIGPLAN Notices, 35(11):160--167, Nov. 2000.

Digital Library

[9]

J. Canny. Collaborative filtering with privacy. In Proceedings of the IEEE Symposium on Research in Security and Privacy, pages 45--57, Oakland, CA, May 2002. IEEE Computer Society, Technical Committee on Security and Privacy, IEEE Computer Society Press.

Digital Library

[10]

M. C. Carlisle. Olden: Parallelizing Programs with Dynamic Data Structures on Distributed-Memory Machines. PhD thesis, Department of Computer Science, Princeton University, June 1996.

Digital Library

[11]

C. Dellarocas. Immunizing online reputation reporting systems against unfair ratings and discriminatory behavior. In Proceedings of the 2nd ACM Conference on Electronic Commerce (EC-00), pages 150--157. ACM, 2000.

Digital Library

[12]

B. Demsky and M. C. Rinard. Role-based exploration of object-oriented programs. In Proceedings of the International Conference on Software Engineering {4}.

Digital Library

[13]

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.

Digital Library

[14]

D. Esler. Welcome to the virtual ramp. Overhaul & Maintenance, VII(2):55, Mar. 2001.

[15]

T. R. Golub, D. K. Slonim, P. Tamayo, C. Huard, M. Gaasenbeek, J. P. Mesirov, H. Coller, M. L. Loh, J. R. Downing, M. A. Caligiuri, C. D. Bloomfield, and E. S. Lander. Molecular classification of cancer: class discovery and class prediction by gene expression monitoring. Science, 286(5439):531--537, 1999.

[16]

S. Hangal and M. S. Lam. Tracking down software bugs using automatic anomaly detection. In Proceedings of the International Conference on Software Engineering {4}, pages 291--301.

Digital Library

[17]

T. Hastie, R. Tibshirani, and J. Friedman. The Elements of Statistical Learning. Stats. Springer, 2001.

[18]

M. Hirzel and T. Chilimbi. Bursty tracing: A framework for low-overhead temporal profiling. In 4th ACM Workshop on Feedback-Directed and Dynamic Optimization, Austin, Texas, Dec. 1 2001.

[19]

Microsoft Corp. Microsoft 2002 annual report and form 10-K. Available at http://www.microsoft.com/msft/ar02/, Redmond, Washington, 2002.

[20]

B. Miller, D. Koski, C. P. Lee, V. Maganty, R. Murthy, A. Natarajan, and J. Steidl. Fuzz revisited: A re-examination of the reliability of UNIX utilities and services. Technical report, Computer Science Department, University of Wisconsin, Madison, WI, 1995.

[21]

G. Necula, S. McPeak, and W. Weimer. CCured: Type-safe retrofitting of legacy code. In C. Norris and J. James B. Fenwick, editors, Proceedings of the 2002 ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL-02), volume 37, 1 of ACM SIGPLAN Notices, pages 128--139. ACM Press, 2002.

Digital Library

[22]

S. P. Reiss and M. Renieris. Encoding program executions. In Proceedings of the 23rd International Conference on Software Engeneering (ICSE-01), pages 221--232. IEEE Computer Society, 2001.

Digital Library

[23]

SPEC 95. Standard Performance Evaluation Corporation Benchmarks. http://www.spec.org/osg/cpu95/CINT95/, July 1995.

[24]

R. Tibshirani, T. Hastie, B. Narasimhan, and G. Chu. Diagnosis of multiple cancer types by shrunken centroids of gene expression. PNAS, 99(10):6567--6572, 2002.

[25]

O. Traub, S. Schechter, and M. D. Smith. Ephemeral instrumentation for lightweight program profiling. Unpublished technical report, Department of Electrical Engineering and Computer Science, Hardward University, Cambridge, Massachusetts, June 2000.

[26]

D. M. Volpano and G. Smith. A type-based approach to program security. In M. Bidoit and M. Dauchet, editors, TAPSOFT '97: Theory and Practice of Software Development, volume 1214 of Lecture Notes in Computer Science, pages 607--621. Springer-Verlag, 1997.

Digital Library

[27]

J. Whaley. A portable sampling-based profiler for Java virtual machines. In Proceedings of the ACM 2000 conference on Java Grande, pages 78--87. ACM Press, 2000.

Digital Library

[28]

S. Zdancewic, L. Zheng, N. Nystrom, and A. C. Myers. Untrusted hosts and confidentiality: Secure program partitioning. In Proceedings of the 18th ACM Symposium on Operating Systems Principles (SOSP'01), pages 1--14. Chateau Lake Louise, Banff, Alberta, Canada, Oct. 2001. Appeared as ACM Operating Systems Review 35.5.

Digital Library

Cited By

Liu RShinde STahvildari LStoodley MSundaresan VPirvu M(2024)Using Semeru Cloud Compiler to Enhance Cloud-Native Java Application Performance2024 34th International Conference on Collaborative Advances in Software and COmputiNg (CASCON)10.1109/CASCON62161.2024.10838216(1-9)Online publication date: 11-Nov-2024
https://doi.org/10.1109/CASCON62161.2024.10838216
Jiang JWang YChen JLv DLiu M(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
https://dl.acm.org/doi/10.1145/3624741
Zhang YHu YLi HShi WNing ZLuo XZhang FJust RFraser G(2023)Alligator in Vest: A Practical Failure-Diagnosis Framework via Arm Hardware FeaturesProceedings of the 32nd ACM SIGSOFT International Symposium on Software Testing and Analysis10.1145/3597926.3598106(917-928)Online publication date: 13-Jul-2023
https://doi.org/10.1145/3597926.3598106
Show More Cited By

Index Terms

Bug isolation via remote program sampling

Recommendations

Bug isolation via remote program sampling

We propose a low-overhead sampling infrastructure for gathering information from the executions experienced by a program's user community. Several example applications illustrate ways to use sampled instrumentation to isolate bugs. Assertion-dense code ...
Scalable statistical bug isolation
PLDI '05: Proceedings of the 2005 ACM SIGPLAN conference on Programming language design and implementation

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 ...
Scalable statistical bug isolation
Proceedings of the 2005 ACM SIGPLAN conference on Programming language design and implementation

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 ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

PLDI '03: Proceedings of the ACM SIGPLAN 2003 conference on Programming language design and implementation

June 2003

360 pages

ISBN:1581136625

DOI:10.1145/781131

General Chair:
Ron Cytron
Washington University, USA
,
Program Chair:
Rajiv Gupta
University of Arizona, USA

ACM SIGPLAN Notices Volume 38, Issue 5
May 2003
349 pages
ISSN:0362-1340
EISSN:1558-1160
DOI:10.1145/780822
Issue’s Table of Contents

Copyright © 2003 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 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: 09 May 2003

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

PLDI03

Sponsor:

PLDI03: ACM SIGPLAN Conference on Programming Language Design and Implementation

June 9 - 11, 2003

California, San Diego, USA

Acceptance Rates

PLDI '03 Paper Acceptance Rate 28 of 131 submissions, 21%;

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

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

346
Total Citations
View Citations
2,041
Total Downloads

Downloads (Last 12 months)46
Downloads (Last 6 weeks)4

Reflects downloads up to 02 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Liu RShinde STahvildari LStoodley MSundaresan VPirvu M(2024)Using Semeru Cloud Compiler to Enhance Cloud-Native Java Application Performance2024 34th International Conference on Collaborative Advances in Software and COmputiNg (CASCON)10.1109/CASCON62161.2024.10838216(1-9)Online publication date: 11-Nov-2024
https://doi.org/10.1109/CASCON62161.2024.10838216
Jiang JWang YChen JLv DLiu M(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
https://dl.acm.org/doi/10.1145/3624741
Zhang YHu YLi HShi WNing ZLuo XZhang FJust RFraser G(2023)Alligator in Vest: A Practical Failure-Diagnosis Framework via Arm Hardware FeaturesProceedings of the 32nd ACM SIGSOFT International Symposium on Software Testing and Analysis10.1145/3597926.3598106(917-928)Online publication date: 13-Jul-2023
https://doi.org/10.1145/3597926.3598106
Zuo ZNiu XZhang SFang LKhoo SLu SSun CXu G(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
https://dl.acm.org/doi/10.1145/3544790
Li XChen JLiu YWu KGallagher J(2023)Combatting Energy Issues for Mobile ApplicationsACM Transactions on Software Engineering and Methodology10.1145/352785132:1(1-44)Online publication date: 13-Feb-2023
https://dl.acm.org/doi/10.1145/3527851
Toslali MAtes EEllis AZhang ZHuye DLiu LPuterman SCoskun ASambasivan R(2021)Automating instrumentation choices for performance problems in distributed applications with VAIFProceedings of the ACM Symposium on Cloud Computing10.1145/3472883.3487000(61-75)Online publication date: 1-Nov-2021
https://dl.acm.org/doi/10.1145/3472883.3487000
Abou Assi RMasri WTrad C(2021)How detrimental is coincidental correctness to coverage‐based fault detection and localization? An empirical studySoftware Testing, Verification and Reliability10.1002/stvr.176231:5Online publication date: 9-Jan-2021
https://doi.org/10.1002/stvr.1762
Zhang HLatif SBassily RRountev ACapkun SRoesner F(2020)Differentially-private control-flow node coverage for software usage analysisProceedings of the 29th USENIX Conference on Security Symposium10.5555/3489212.3489270(1021-1038)Online publication date: 12-Aug-2020
https://dl.acm.org/doi/10.5555/3489212.3489270
Zhang HHao YLatif SBassily RRountev A(2020)Differentially-private software frequency profiling under linear constraintsProceedings of the ACM on Programming Languages10.1145/34282714:OOPSLA(1-24)Online publication date: 13-Nov-2020
https://dl.acm.org/doi/10.1145/3428271
Ates ESturmann LToslali MKrieger OMegginson RCoskun ASambasivan R(2019)An automated, cross-layer instrumentation framework for diagnosing performance problems in distributed applicationsProceedings of the ACM Symposium on Cloud Computing10.1145/3357223.3362704(165-170)Online publication date: 20-Nov-2019
https://dl.acm.org/doi/10.1145/3357223.3362704
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten