More Web Proxy on the site http://driver.im/

research-article

Do I use the wrong definition?: DeFuse: definition-use invariants for detecting concurrency and sequential bugs

Authors:

Weimin ZhengAuthors Info & Claims

OOPSLA '10: Proceedings of the ACM international conference on Object oriented programming systems languages and applications

Pages 160 - 174

https://doi.org/10.1145/1869459.1869474

Published: 17 October 2010 Publication History

Abstract

Software bugs, such as concurrency, memory and semantic bugs, can significantly affect system reliability. Although much effort has been made to address this problem, there are still many bugs that cannot be detected, especially concurrency bugs due to the complexity of concurrent programs. Effective approaches for detecting these common bugs are therefore highly desired.

This paper presents an invariant-based bug detection tool, DefUse, which can detect not only concurrency bugs (including the previously under-studied order violation bugs), but also memory and semantic bugs. Based on the observation that many bugs appear as violations to programmers' data flow intentions, we introduce three different types of definition-use invariants that commonly exist in both sequential and concurrent programs. We also design an algorithm to automatically extract such invariants from programs, which are then used to detect bugs. Moreover, DefUse uses various techniques to prune false positives and rank error reports.

We evaluated DefUse using sixteen real-world applications with twenty real-world concurrency and sequential bugs. Our results show that DefUse can effectively detect 19 of these bugs, including 2 new bugs that were never reported before, with only a few false positives. Our training sensitivity results show that, with the benefit of the pruning and ranking algorithms, DefUse is accurate even with insufficient training.

References

[1]

}}A. V. Aho, R. Sethi, and J. D. Ullman. Compilers: Principles,Techniques, and Tools. Addison Wesley, 1986.

Digital Library

[2]

}}P. Barford and M. Crovella. Generating representative web workloads for network and server performance evaluation. In ACM SIGMETRICS, June 1998.

Digital Library

[3]

}}M. Burrows and K. R. M. Leino. Finding stale-value errors in concurrent programs. Concurrency and Computation: Practice & Experience, 16(12):1161--1172, 2004.

Digital Library

[4]

}}M. Castro, M. Costa, and T. Harris. Securing software by enforcing data-flow integrity. In OSDI, 2006.

Digital Library

[5]

}}S. Cherem, L. Princehouse, and R. Rugina. Practical memory leak detection using guarded value-flow analysis. In PLDI, 2007.

Digital Library

[6]

}}T. Chilimbi and V. Ganapathy. HeapMD: Identifying heapbased bugs using anomaly detection. In ASPLOS, 2006.

Digital Library

[7]

}}J.-D. Choi, K. Lee, A. Loginov, R. O'Callahan, V. Sarkar, and M. Sridharan. Efficient and precise datarace detection for multithreaded object-oriented programs. In PLDI, 2002.

Digital Library

[8]

}}M. D. Ernst, J. H. Perkins, P. J. Guo, S. McCamant, C. Pacheco, M. S. Tschantz, and C. Xiao. The Daikon system for dynamic detection of likely invariants. Science of Computer Programming, 69(1-3):35--45, Dec. 2007.

Digital Library

[9]

}}C. Flanagan and S. N. Freund. Atomizer: a dynamic atomicity checker for multithreaded programs. In POPL, 2004.

Digital Library

[10]

}}C. Flanagan and S. N. Freund. FastTrack: efficient and precise dynamic race detection. In PLDI, 2009.

Digital Library

[11]

}}C. Flanagan and S. Qadeer. A type and effect system for atomicity. In PLDI, pages 338--349, 2003.

Digital Library

[12]

}}H. S. Gunawi, C. Rubio-Gonzaiz, A. C. Arpaci-Dusseau, R. H. Arpaci-Dusseau, and B. Liblit. EIO: Error handling is occasionally correct. In FAST, 2008.

Digital Library

[13]

}}S. Hangal and M. S. Lam. Tracking down software bugs using automatic anomaly detection. In ICSE, 2002.

Digital Library

[14]

}}M. J. Harrold and B. A. Malloy. Data flow testing of parallelized code. In ICSM, 1992.

[15]

}}R. Hastings and B. Joyce. Purify: Fast detection of memory leaks and access errors. In Usenix Winter Technical Conference, 1992.

[16]

}}S. Lu,W. Jiang, and Y. Zhou. A study of interleaving coverage criteria. In FSE, 2007.

Digital Library

[17]

}}S. Lu, S. Park, C. Hu, X. Ma, W. Jiang, Z. Li, R. A. Popa, and Y. Zhou. MUVI: Automatically inferring multi-variable access correlations and detecting related semantic and concurrency bugs. In SOSP, 2007.

Digital Library

[18]

}}S. Lu, S. Park, E. Seo, and Y. Zhou. Learning from mistakes - a comprehensive study of real world concurrency bug characteristics. In ASPLOS, 2008.

Digital Library

[19]

}}S. Lu, J. Tucek, F. Qin, and Y. Zhou. AVIO: Detecting atomicity violations via access interleaving invariants. In ASPLOS, 2006.

Digital Library

[20]

}}B. Lucia and L. Ceze. Finding concurrency bugs with contextaware communication graphs. In MICRO, 2009.

Digital Library

[21]

}}C.-K. Luk, R. Cohn, R. Muth, H. Patil, A. Klauser, G. Lowney, S. Wallace, V. J. Reddi, and K. Hazelwood. Pin: building customized program analysis tools with dynamic instrumentation. In PLDI, 2005.

Digital Library

[22]

}}E. Marcus and H. Stern. Blueprints for high availability (2nd edition). John Wiley and Sons, 2003.

[23]

}}D. Marino, M. Musuvathi, and S. Narayanasamy. LiteRace: effective sampling for lightweight data-race detection. In PLDI, 2009.

Digital Library

[24]

}}D. Mosberger and T. Jin. httperf - a tool for measuring web server performance. Performance Evaluation Review, 26(3):31--37, 1998.

Digital Library

[25]

}}M. Musuvathi and S. Qadeer. Iterative context bounding for systematic testing of multithreaded programs. In PLDI, 2007.

Digital Library

[26]

}}M. Musuvathi, S. Qadeer, T. Ball, and G. Basler. Finding and reproducing heisenbugs in concurrent programs. In OSDI, 2008.

Digital Library

[27]

}}S. Narayanasamy, C. Pereira, and B. Calder. Recording shared memory dependencies using strata. In ASPLOS, 2006.

Digital Library

[28]

}}N. Nethercote and J. Seward. Valgrind: A framework for heavyweight dynamic binary instrumentation. In PLDI, 2007.

Digital Library

[29]

}}R. O'Callahan and J.-D. Choi. Hybrid dynamic data race detection. In PPoPP, 2003.

Digital Library

[30]

}}S. Park, S. Lu, and Y. Zhou. CTrigger: Exposing atomicity violation bugs from their hiding places. In ASPLOS, 2009.

Digital Library

[31]

}}D. Perkovic and P. J. Keleher. Online data-race detection via coherency guarantees. In OSDI, 1996.

Digital Library

[32]

}}E. Pozniansky and A. Schuster. Efficient on-the-fly data race detection in multithreaded C++ programs. In PPoPP, 2003.

Digital Library

[33]

}}A. Sasturkar, R. Agarwal, L. Wang, and S. D. Stoller. Automated type-based analysis of data races and atomicity. In PPoPP, pages 83--94, 2005.

Digital Library

[34]

}}S. Savage, M. Burrows, G. Nelson, P. Sobalvarro, and T. Anderson. Eraser: A dynamic data race detector for multithreaded programs. ACM TOCS, 1997.

Digital Library

[35]

}}SecurityFocus. Software bug contributed to blackout. http://www.securityfocus.com/news/8016.

[36]

}}K. Sen. Race directed random testing of concurrent programs. In PLDI, 2008.

Digital Library

[37]

}}A. Shankar and R. Bodik. DITTO: Automatic incrementalization of data structure invariant checks (in Java). In PLDI, 2007.

Digital Library

[38]

}}C. von Praun and T. R. Gross. Object race detection. In OOPSLA, 2001.

Digital Library

[39]

}}C. von Praun and T. R. Gross. Static conflict analysis for multi-threaded object oriented programs. In PLDI, 2003.

Digital Library

[40]

}}M. Xu, R. Bodik, and M. Hill. A regulated transitive reduction for longer memory race recording. In ASPLOS, 2006.

Digital Library

[41]

}}M. Xu, R. Bodik, and M. D. Hill. A "flight data recorder" for enabling full-system multiprocessor deterministic replay. In ISCA, 2003.

Digital Library

[42]

}}M. Xu, R. Bodik, and M. D. Hill. A serializability violation detector for shared-memory server programs. In PLDI, pages 1--14, 2005.

Digital Library

[43]

}}C.-S. D. Yang, A. L. Souter, and L. L. Pollock. All-du-path coverage for parallel programs. In ISSTA, 1998.

Digital Library

[44]

}}J. Yu and S. Narayanasamy. A case for an interleaving constrained shared-memory multi-processor. In ISCA, 2009.

Digital Library

[45]

}}P. Zhou, W. Liu, F. Long, S. Lu, F. Qin, Y. Zhou, S. Midkiff, and J. Torrellas. AccMon: Automatically Detecting Memory-Related Bugs via Program Counter-based Invariants. In MICRO, 2004.

Digital Library

Cited By

Stoica BLu SMusuvathi MNath SFedorova ANarayanan DDi Luna GQuerzoni L(2023)WAFFLE: Exposing Memory Ordering Bugs Efficiently with Active Delay InjectionProceedings of the Eighteenth European Conference on Computer Systems10.1145/3552326.3567507(111-126)Online publication date: 8-May-2023
https://dl.acm.org/doi/10.1145/3552326.3567507
Chi JQu YLiu TZheng QYin H(2023)SeqTrans: Automatic Vulnerability Fix Via Sequence to Sequence LearningIEEE Transactions on Software Engineering10.1109/TSE.2022.315663749:2(564-585)Online publication date: 1-Feb-2023
https://doi.org/10.1109/TSE.2022.3156637
Chen ZHua YZhang YDing LFalsafi BFerdman MLu SWenisch T(2022)Efficiently detecting concurrency bugs in persistent memory programsProceedings of the 27th ACM International Conference on Architectural Support for Programming Languages and Operating Systems10.1145/3503222.3507755(873-887)Online publication date: 28-Feb-2022
https://dl.acm.org/doi/10.1145/3503222.3507755
Show More Cited By

Index Terms

Do I use the wrong definition?: DeFuse: definition-use invariants for detecting concurrency and sequential bugs
1. General and reference
  1. Cross-computing tools and techniques
    1. Reliability
2. Software and its engineering
  1. Software creation and management
    1. Software verification and validation
  2. Software organization and properties
    1. Extra-functional properties
      1. Software reliability

Recommendations

Do I use the wrong definition?: DeFuse: definition-use invariants for detecting concurrency and sequential bugs
OOPSLA '10

Software bugs, such as concurrency, memory and semantic bugs, can significantly affect system reliability. Although much effort has been made to address this problem, there are still many bugs that cannot be detected, especially concurrency bugs due to ...
Applying transactional memory to concurrency bugs
ASPLOS XVII: Proceedings of the seventeenth international conference on Architectural Support for Programming Languages and Operating Systems

Multithreaded programs often suffer from synchronization bugs such as atomicity violations and deadlocks. These bugs arise from complicated locking strategies and ad hoc synchronization methods to avoid the use of locks. A survey of the bug databases of ...
Applying transactional memory to concurrency bugs
ASPLOS '12

Multithreaded programs often suffer from synchronization bugs such as atomicity violations and deadlocks. These bugs arise from complicated locking strategies and ad hoc synchronization methods to avoid the use of locks. A survey of the bug databases of ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

OOPSLA '10: Proceedings of the ACM international conference on Object oriented programming systems languages and applications

October 2010

984 pages

ISBN:9781450302036

DOI:10.1145/1869459

General Chairs:
William R. Cook
University of Texas at Austin
,
Siobhán Clarke
Trinity College Dublin
,
Program Chairs:
Martin Rinard
MIT
,
Kevin J. Sullivan
University of Virginia
,
Daniel H. Steinberg
Dim Sum Thinking Inc.

ACM SIGPLAN Notices Volume 45, Issue 10
OOPSLA '10
October 2010
957 pages
ISSN:0362-1340
EISSN:1558-1160
DOI:10.1145/1932682
Issue’s Table of Contents

Copyright © 2010 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

SIGPLAN: ACM Special Interest Group on Programming Languages

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 17 October 2010

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

SPLASH '10

Sponsor:

SIGPLAN

SPLASH '10: Systems Programming Languages and Applications: Software for Humanity

October 17 - 21, 2010

Nevada, Reno/Tahoe, USA

Acceptance Rates

Overall Acceptance Rate 268 of 1,244 submissions, 22%

Upcoming Conference

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

97
Total Citations
View Citations
713
Total Downloads

Downloads (Last 12 months)20
Downloads (Last 6 weeks)1

Reflects downloads up to 11 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Stoica BLu SMusuvathi MNath SFedorova ANarayanan DDi Luna GQuerzoni L(2023)WAFFLE: Exposing Memory Ordering Bugs Efficiently with Active Delay InjectionProceedings of the Eighteenth European Conference on Computer Systems10.1145/3552326.3567507(111-126)Online publication date: 8-May-2023
https://dl.acm.org/doi/10.1145/3552326.3567507
Chi JQu YLiu TZheng QYin H(2023)SeqTrans: Automatic Vulnerability Fix Via Sequence to Sequence LearningIEEE Transactions on Software Engineering10.1109/TSE.2022.315663749:2(564-585)Online publication date: 1-Feb-2023
https://doi.org/10.1109/TSE.2022.3156637
Chen ZHua YZhang YDing LFalsafi BFerdman MLu SWenisch T(2022)Efficiently detecting concurrency bugs in persistent memory programsProceedings of the 27th ACM International Conference on Architectural Support for Programming Languages and Operating Systems10.1145/3503222.3507755(873-887)Online publication date: 28-Feb-2022
https://dl.acm.org/doi/10.1145/3503222.3507755
Mathur UPavlogiannis ATunç HViswanathan MFalsafi BFerdman MLu SWenisch T(2022)A tree clock data structure for causal orderings in concurrent executionsProceedings of the 27th ACM International Conference on Architectural Support for Programming Languages and Operating Systems10.1145/3503222.3507734(710-725)Online publication date: 28-Feb-2022
https://dl.acm.org/doi/10.1145/3503222.3507734
Gong SAltinbüken DFonseca PManiatis P(2021)SnowboardProceedings of the ACM SIGOPS 28th Symposium on Operating Systems Principles10.1145/3477132.3483549(66-83)Online publication date: 26-Oct-2021
https://dl.acm.org/doi/10.1145/3477132.3483549
Cai YYao PZhang CFreund SYahav E(2021)Canary: practical static detection of inter-thread value-flow bugsProceedings of the 42nd ACM SIGPLAN International Conference on Programming Language Design and Implementation10.1145/3453483.3454099(1126-1140)Online publication date: 19-Jun-2021
https://dl.acm.org/doi/10.1145/3453483.3454099
Mu YWang ZLiu SSun JChen JChen X(2021)HARS: Heuristic-Enhanced Adaptive Randomized Scheduling for Concurrency Testing2021 IEEE 21st International Conference on Software Quality, Reliability and Security (QRS)10.1109/QRS54544.2021.00033(219-230)Online publication date: Dec-2021
https://doi.org/10.1109/QRS54544.2021.00033
Sui YCheng XZhang GWang H(2020)Flow2Vec: value-flow-based precise code embeddingProceedings of the ACM on Programming Languages10.1145/34283014:OOPSLA(1-27)Online publication date: 13-Nov-2020
https://dl.acm.org/doi/10.1145/3428301
Pavlogiannis A(2019)Fast, sound, and effectively complete dynamic race predictionProceedings of the ACM on Programming Languages10.1145/33710854:POPL(1-29)Online publication date: 20-Dec-2019
https://dl.acm.org/doi/10.1145/3371085
Surbatovich MJia LLucia B(2019)I/O dependent idempotence bugs in intermittent systemsProceedings of the ACM on Programming Languages10.1145/33606093:OOPSLA(1-31)Online publication date: 10-Oct-2019
https://dl.acm.org/doi/10.1145/3360609
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.

Media

Figures

Other

Tables

View Table of Contents