research-article

Public Access

ECHO: instantaneous in situ race detection in the IDE

Authors:

Jeff HuangAuthors Info & Claims

FSE 2016: Proceedings of the 2016 24th ACM SIGSOFT International Symposium on Foundations of Software Engineering

Pages 775 - 786

https://doi.org/10.1145/2950290.2950332

Published: 01 November 2016 Publication History

Abstract

We present ECHO, a new technique that detects data races instantaneously in the IDE while developers code. ECHO is the first technique of its kind for incremental race detection supporting both code addition and deletion in the IDE. Unlike conventional static race detectors, ECHO warns developers of potential data races immediately as they are introduced into the program. The core underpinning ECHO is a set of new change-aware static analyses based on a novel static happens-before graph that, given a program change, efficiently compute the change-relevant information without re-analyzing the whole program. Our evaluation within a Java environment on both popular benchmarks and real- world applications shows promising results: for each code addition, or deletion, ECHO can instantly pinpoint all the races in a few milliseconds on average, three to four orders of magnitude faster than a conventional whole-program race detector with the same precision.

References

[1]

Mayur Naik, Alex Aiken, and John Whaley. Effective static race detection for Java. In ACM SIGPLAN Conference on Programming Language Design and Implementation, pages 308–319, 2006.

Digital Library

[2]

Jan Wen Voung, Ranjit Jhala, and Sorin Lerner. Relay: static race detection on millions of lines of code. ESEC-Joint European Software Engineering Conference and ACM SIGSOFT Symposium on Foundations of Software Engineering, 2007.

Digital Library

[3]

Cormac Flanagan and Stephen N. Freund. FastTrack: efficient and precise dynamic race detection. In ACM SIGPLAN Conference on Programming Language Design and Implementation, pages 121–133, 2009.

Digital Library

[4]

Jeff Huang, Patrick O’Neil Meredith, and Grigore Rosu. Maximal sound predictive race detection with control flow abstraction. In ACM SIGPLAN Conference on Programming Language Design and Implementation, pages 337–348, 2014.

Digital Library

[5]

Swarnendu Biswas, Minjia Zhang, Michael D. Bond, and Brandon Lucia. Valor: Efficient, software-only region conflict exceptions. In ACM SIGPLAN Conference on Object Oriented Programming, Systems, Languages, and Applications, 2015.

Digital Library

[6]

Veselin Raychev, Martin Vechev, and Manu Sridharan. Effective race detection for event-driven programs. In ACM SIGPLAN International Conference on Object Oriented Programming Systems Languages and Applications, pages 151–166, 2013.

Digital Library

[7]

ThreadSanitizer Documentation. http://clang.llvm.org/docs/ThreadSanitizer.html.

[8]

Intel inspector. https://software.intel.com/en-us/intel-inspector-xe/.

[9]

Go data race detector. https://golang.org/doc/articles/race\ detector.html.

[10]

The True Cost of a Software Bug. http: //blog.celerity.com/the-true-cost-of-a-software-bug/.

[11]

The Eclipse IDE. https://eclipse.org/downloads/.

[12]

Dawson Engler and Ken Ashcraft. Racerx: effective, static detection of race conditions and deadlocks. In ACM Symposium on Operating Systems Principles, 2003.

Digital Library

[13]

The ECHO webpage. http://parasol.tamu.edu/˜jeff/echo/.

[14]

Yannis Smaragdakis and George Balatsouras. Pointer analysis. Found. Trends Program. Lang., 2(1):1–69, 2015.

Digital Library

[15]

William Landi and Barbara G. Ryder. Pointer-induced aliasing: A problem classification. In Proceedings of the 18th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, pages 93–103, 1991.

Digital Library

[16]

John Whaley and Monica S. Lam. Cloning-based context-sensitive pointer alias analysis using binary decision diagrams. In Proceedings of the ACM SIGPLAN 2004 Conference on Programming Language Design and Implementation, pages 131–144, 2004.

Digital Library

[17]

Yi Lu, Lei Shang, Xinwei Xie, and Jingling Xue. An incremental points-to analysis with cfl-reachability. In Compiler Construction, pages 61–81, 2013.

Digital Library

[18]

Jyh-shiarn Yur, Barbara G Ryder, and William A Landi. An incremental flow-and context-sensitive pointer aliasing analysis. In Proceedings of the 21st international conference on Software engineering, pages 442–451, 1999.

Digital Library

[19]

Robert O’Callahan and Jong-Deok Choi. Hybrid dynamic data race detection. In ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, 2003.

Digital Library

[20]

WALA pointer analysis. http://wala.sourceforge.net/ wiki/\\index.php/UserGuide:PointerAnalysis.

[21]

Ben Hardekopf and Calvin Lin. The ant and the grasshopper: Fast and accurate pointer analysis for millions of lines of code. In Proceedings of the 28th ACM SIGPLAN Conference on Programming Language Design and Implementation, pages 290–299, 2007.

Digital Library

[22]

Cormac Flanagan and Shaz Qadeer. A type and effect system for atomicity. In ACM SIGPLAN Conference on Programming Language Design and Implementation, 2003.

Digital Library

[23]

T. J. Watson Libraries for Analysis (WALA). http://wala.sourceforge.net/.

[24]

Jeff Huang. Stateless model checking concurrent programs with maximal causality reduction. In ACM SIGPLAN Conference on Programming Language Design and Implementation, pages 165–174, 2015.

Digital Library

[25]

H2 Database Engine. http://www.h2database.com.

[26]

WebLech

[27]

ECHO technical report. http://parasol.tamu.edu/˜jeff/academic/echo-tr.pdf.

[28]

George Kastrinis and Yannis Smaragdakis. Hybrid context-sensitivity for points-to analysis. In Proceedings of the 34th ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI ’13, pages 423–434, 2013.

Digital Library

[29]

Manu Sridharan and Rastislav Bod´ık. Refinement-based context-sensitive points-to analysis for java. In Proceedings of the 27th ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI ’06, pages 387–400, 2006.

Digital Library

[30]

Patrick Cousot, Radhia Cousot, and Francesco Logozzo. A parametric segmentation functor for fully automatic and scalable array content analysis. In ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, 2011.

Digital Library

[31]

Denis Gopan, Thomas Reps, and Mooly Sagiv. A framework for numeric analysis of array operations. In ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, 2005.

Digital Library

[32]

Nicolas Halbwachs and Mathias Péron. Discovering properties about arrays in simple programs. In ACM SIGPLAN Conference on Programming Language Design and Implementation, 2008.

Digital Library

[33]

Weiwei Xiong, Soyeon Park, Jiaqi Zhang, Yuanyuan Zhou, and Zhiqiang Ma. Ad hoc synchronization considered harmful. In USENIX Symposium on Operating Systems Design and Implementation, 2010.

Digital Library

[34]

Jeff Huang and Lawrence Rauchwerger. Finding schedule-sensitive branches. In Joint European Conference and ACM SIGSOFT Symposium on Foundations of Software Engineering, 2015.

Digital Library

[35]

Le Yin. Effectively recognize ad hoc synchronizations with static analysis. In LCPC, 2013.

[36]

Chandrasekhar Boyapati, Robert Lee, and Martin Rinard. Ownership types for safe programming: preventing data races and deadlocks. In ACM SIGPLAN Conference on Object Oriented Programming, Systems, Languages, and Applications, 2002.

Digital Library

[37]

Nicholas D. Matsakis and Thomas R. Gross. A time-aware type system for data-race protection and guaranteed initialization. In ACM SIGPLAN Conference on Object Oriented Programming, Systems, Languages, and Applications, 2010.

Digital Library

[38]

Chandrasekhar Boyapati and Martin Rinard. A parameterized type system for race-free Java programs. In ACM SIGPLAN Conference on Object Oriented Programming, Systems, Languages, and Applications, 2001.

Digital Library

[39]

Cormac Flanagan and Stephen N. Freund. Type-based race detection for Java. In ACM SIGPLAN Conference on Programming Language Design and Implementation, 2000.

Digital Library

[40]

Martin Abadi, Cormac Flanagan, and Stephen N. Freund. Types for safe locking: Static race detection for Java. ACM Trans. Program. Lang. Syst., 28(2):207–255, 2006.

Digital Library

[41]

Bart Jacobs, Frank Piessens, Jan Smans, K. Rustan M. Leino, and Wolfram Schulte. A programming model for concurrent object-oriented programs. ACM Trans. Program. Lang. Syst., 31(1):1:1–1:48, 2008.

Digital Library

[42]

Cormac Flanagan, K. Rustan M. Leino, Mark Lillibridge, Greg Nelson, James B. Saxe, and Raymie Stata. Extended static checking for Java. In ACM SIGPLAN Conference on Programming Language Design and Implementation, 2002.

Digital Library

[43]

Mayur Naik and Alex Aiken. Conditional must not aliasing for static race detection. In ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, 2007.

Digital Library

[44]

Polyvios Pratikakis, Jeffrey S. Foster, and Michael Hicks. Locksmith: context-sensitive correlation analysis for race detection. In ACM SIGPLAN Conference on Programming Language Design and Implementation, 2006.

Digital Library

[45]

Thomas A. Henzinger, Ranjit Jhala, and Rupak Majumdar. Race checking by context inference. In ACM SIGPLAN Conference on Programming Language Design and Implementation, 2004.

Digital Library

[46]

Vineet Kahlon, Yu Yang, Sriram Sankaranarayanan, and Aarti Gupta. Fast and accurate static data-race detection for concurrent programs. In International Conference on Computer Aided Verification, 2007.

Digital Library

[47]

Cosmin Radoi and Danny Dig. Practical static race detection for Java parallel loops. In Proceedings of the 2013 International Symposium on Software Testing and Analysis, pages 178–190, 2013.

Digital Library

[48]

Vineet Kahlon, Nishant Sinha, Erik Kruus, and Yun Zhang. Static data race detection for concurrent programs with asynchronous calls. In Joint European Software Engineering Conference and ACM SIGSOFT Symposium on Foundations of Software Engineering, 2009.

Digital Library

[49]

Christoph von Praun and Thomas R. Gross. Static conflict analysis for multi-threaded object-oriented programs. In ACM SIGPLAN Conference on Programming Language Design and Implementation, 2003.

Digital Library

[50]

Manu Sridharan, Denis Gopan, Lexin Shan, and Rastislav Bod´ık. Demand-driven points-to analysis for java. In Proceedings of the 20th Annual ACM SIGPLAN Conference on Object-oriented Programming, Systems, Languages, and Applications, pages 59–76, 2005.

Digital Library

[51]

Diptikalyan Saha and C. R. Ramakrishnan. Incremental and demand-driven points-to analysis using logic programming. In Proceedings of the 7th ACM SIGPLAN International Conference on Principles and Practice of Declarative Programming, pages 117–128, 2005.

Digital Library

[52]

Steven Arzt and Eric Bodden. Reviser: Efficiently updating ide-/ifds-based data-flow analyses in response to incremental program changes. In Proceedings of the 36th International Conference on Software Engineering, pages 288–298, 2014.

Digital Library

Cited By

Shi ZMathur UPavlogiannis ARoychoudhury APaiva AAbreu RStorey M(2024)Optimistic Prediction of Synchronization-Reversal Data RacesProceedings of the IEEE/ACM 46th International Conference on Software Engineering10.1145/3597503.3639099(1-13)Online publication date: 20-May-2024
https://dl.acm.org/doi/10.1145/3597503.3639099
Cai YYao PYe CZhang CCalandrino JTroncoso C(2023)Place your locks wellProceedings of the 32nd USENIX Conference on Security Symposium10.5555/3620237.3620446(3727-3744)Online publication date: 9-Aug-2023
https://dl.acm.org/doi/10.5555/3620237.3620446
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
Show More Cited By

Index Terms

ECHO: instantaneous in situ race detection in the IDE
1. Software and its engineering
  1. Software notations and tools
    1. Software maintenance tools

Recommendations

What are race conditions?: Some issues and formalizations

In shared-memory parallel programs that use explicit synchronization, race conditions result when accesses to shared memory are not properly synchronized. Race conditions are often considered to be manifestations of bugs, since their presence can cause ...
Lightweight data race detection for production runs
CC 2017: Proceedings of the 26th International Conference on Compiler Construction

To detect data races that harm production systems, program analysis must target production runs. However, sound and precise data race detection adds too much run-time overhead for use in production systems. Even existing approaches that provide ...
Dynamic race detection for C++11
POPL '17: Proceedings of the 44th ACM SIGPLAN Symposium on Principles of Programming Languages

The intricate rules for memory ordering and synchronisation associated with the C/C++11 memory model mean that data races can be difficult to eliminate from concurrent programs. Dynamic data race analysis can pinpoint races in large and complex ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

FSE 2016: Proceedings of the 2016 24th ACM SIGSOFT International Symposium on Foundations of Software Engineering

November 2016

1156 pages

ISBN:9781450342186

DOI:10.1145/2950290

General Chair:
Thomas Zimmermann
Microsoft Research, USA
,
Program Chairs:
Jane Cleland-Huang
University of Notre Dame, USA
,
Zhendong Su
University of California at Davis, USA

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

SIGSOFT: ACM Special Interest Group on Software Engineering

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 November 2016

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

National Science Foundation
Google Research

Conference

FSE'16

Sponsor:

SIGSOFT

FSE'16: 24nd ACM SIGSOFT International Symposium on the Foundations of Software Engineering

November 13 - 18, 2016

WA, Seattle, USA

Acceptance Rates

Overall Acceptance Rate 17 of 128 submissions, 13%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

29
Total Citations
View Citations
519
Total Downloads

Downloads (Last 12 months)107
Downloads (Last 6 weeks)10

Reflects downloads up to 24 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Shi ZMathur UPavlogiannis ARoychoudhury APaiva AAbreu RStorey M(2024)Optimistic Prediction of Synchronization-Reversal Data RacesProceedings of the IEEE/ACM 46th International Conference on Software Engineering10.1145/3597503.3639099(1-13)Online publication date: 20-May-2024
https://dl.acm.org/doi/10.1145/3597503.3639099
Cai YYao PYe CZhang CCalandrino JTroncoso C(2023)Place your locks wellProceedings of the 32nd USENIX Conference on Security Symposium10.5555/3620237.3620446(3727-3744)Online publication date: 9-Aug-2023
https://dl.acm.org/doi/10.5555/3620237.3620446
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
Wauters CPlas JStiévenart QRoover C(2023)Change Pattern Detection for Optimising Incremental Static Analysis2023 IEEE 23rd International Working Conference on Source Code Analysis and Manipulation (SCAM)10.1109/SCAM59687.2023.00016(49-60)Online publication date: 2-Oct-2023
https://doi.org/10.1109/SCAM59687.2023.00016
Zhu SGuo YZhang LCai YGrundy JPollock LPenta M(2023)Tolerate Control-Flow Changes for Sound Data Race PredictionProceedings of the 45th International Conference on Software Engineering10.1109/ICSE48619.2023.00118(1342-1354)Online publication date: 14-May-2023
https://dl.acm.org/doi/10.1109/ICSE48619.2023.00118
Guo YLiang ZZhu SWang JYang ZShen WZhang JCai Y(2023)Sound Predictive Fuzzing for Multi-threaded Programs2023 IEEE 47th Annual Computers, Software, and Applications Conference (COMPSAC)10.1109/COMPSAC57700.2023.00110(810-819)Online publication date: Jun-2023
https://doi.org/10.1109/COMPSAC57700.2023.00110
Van der Plas JStiévenart QDe Roover C(2023)Result Invalidation for Incremental Modular AnalysesVerification, Model Checking, and Abstract Interpretation10.1007/978-3-031-24950-1_14(296-319)Online publication date: 16-Jan-2023
https://dl.acm.org/doi/10.1007/978-3-031-24950-1_14
Liu BHuang J(2022)SHARP: fast incremental context-sensitive pointer analysis for JavaProceedings of the ACM on Programming Languages10.1145/35273326:OOPSLA1(1-28)Online publication date: 29-Apr-2022
https://dl.acm.org/doi/10.1145/3527332
Jana AChimdyalwar BKumar SVenkatesh R(2022)Fast Analysis of Evolving Software Systems2022 IEEE International Symposium on Software Reliability Engineering Workshops (ISSREW)10.1109/ISSREW55968.2022.00038(49-54)Online publication date: Oct-2022
https://doi.org/10.1109/ISSREW55968.2022.00038
Cai YYun HWang JQiao LPalsberg JSpinellis DGousios GChechik MDi Penta M(2021)Sound and efficient concurrency bug predictionProceedings of the 29th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering10.1145/3468264.3468549(255-267)Online publication date: 20-Aug-2021
https://dl.acm.org/doi/10.1145/3468264.3468549
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

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

Media

Figures

Other

Tables

View Table of Contents