research-article

Effective race detection for event-driven programs

Authors:

Veselin Raychev,

Manu SridharanAuthors Info & Claims

OOPSLA '13: Proceedings of the 2013 ACM SIGPLAN international conference on Object oriented programming systems languages & applications

Pages 151 - 166

https://doi.org/10.1145/2509136.2509538

Published: 29 October 2013 Publication History

Abstract

Like shared-memory multi-threaded programs, event-driven programs such as client-side web applications are susceptible to data races that are hard to reproduce and debug. Race detection for such programs is hampered by their pervasive use of ad hoc synchronization, which can lead to a prohibitive number of false positives. Race detection also faces a scalability challenge, as a large number of short-running event handlers can quickly overwhelm standard vector-clock-based techniques.

This paper presents several novel contributions that address both of these challenges. First, we introduce race coverage, a systematic method for exposing ad hoc synchronization and other (potentially harmful) races to the user, significantly reducing false positives. Second, we present an efficient connectivity algorithm for computing race coverage. The algorithm is based on chain decomposition and leverages the structure of event-driven programs to dramatically decrease the overhead of vector clocks.

We implemented our techniques in a tool called EventRacer and evaluated it on a number of public web sites. The results indicate substantial performance and precision improvements of our approach over the state-of-the-art. Using EventRacer, we found many harmful races, most of which are beyond the reach of current techniques.

References

[1]

AGARWAL, A., AND GARG, V. K. Efficient dependency tracking for relevant events in shared-memory systems. In PODC (2005).

Digital Library

[2]

ARTZI, S., DOLBY, J., JENSEN, S. H., MØLLER, A., AND TIP, F. A Framework for Automated Testing of JavaScript Web Applications. In ICSE (May 2011).

Digital Library

[3]

CHRISTIAENS, M., AND BOSSCHERE, K. D. Accordion clocks: Logical clocks for data race detection. In Euro-Par (2001).

Digital Library

[4]

FLANAGAN, C., AND FREUND, S. N. FastTrack: efficient and precise dynamic race detection. In PLDI (2009).

Digital Library

[5]

HTML5 specification. http://www.w3.org/TR/html5/.

[6]

IDE, J., BODIK, R., AND KIMELMAN, D. Concurrency concerns in rich Internet applications. In EC2 (2009).

[7]

JAGADISH, H. V. A compression technique to materialize transitive closure. ACM Trans. Database Syst. 15, 4 (Dec. 1990), 558--598.

Digital Library

[8]

KASIKCI, B., ZAMFIR, C., AND CANDEA, G. Data races vs. data race bugs: telling the difference with Portend. In ASPLOS (2012).

Digital Library

[9]

LAMPORT, L. Time, clocks, and the ordering of events in a distributed system. In ACM Operating Systems (1978).

Digital Library

[10]

MATTERN, F. Virtual time and global states of distributed systems. In Proc. Workshop on Parallel and Distributed Algorithms (1989), C. M. et al., Ed.

[11]

Bug 538892 - Replying to or forwarding emails on Hotmail no longer works properly: message content is often lost. https://bugzilla.mozilla.org/show_bug.cgi?id=538892.

[12]

NARAYANASAMY, S., WANG, Z., TIGANI, J., EDWARDS, A., AND CALDER, B. Automatically classifying benign and harmful data races using replay analysis. In PLDI (2007).

Digital Library

[13]

NETZER, R. H. B., AND MILLER, B. P. Improving the accuracy of data race detection. In PPOPP (1991).

Digital Library

[14]

NETZER, R. N., AND MILLER, B. P. Detecting data races in parallel program executions. In LCPC (1989).

[15]

PETROV, B., VECHEV, M., SRIDHARAN, M., AND DOLBY, J. Race detection for web applications. In PLDI (2012).

Digital Library

[16]

POZNIANSKY, E., AND SCHUSTER, A. Efficient on-the-fly data race detection in multithreaded c++ programs. In PPoPP (2003).

Digital Library

[17]

RICHARDS, G., LEBRESNE, S., BURG, B., AND VITEK, J. An analysis of the dynamic behavior of JavaScript programs. In PLDI (2010).

Digital Library

[18]

SEN, K. Race directed random testing of concurrent programs. In PLDI (2008), pp. 11--21.

Digital Library

[19]

SHI, Y., PARK, S., YIN, Z., LU, S., ZHOU, Y., CHEN, W., AND ZHENG, W. Do i use the wrong definition?: Defuse: definition-use invariants for detecting concurrency and sequential bugs. In OOPSLA (2010).

Digital Library

[20]

WebKit. http://www.webkit.org/.

[21]

ZHENG, Y., BAO, T., AND ZHANG, X. Statically locating web application bugs caused by asynchronous calls. In WWW'2011 (2011).

Digital Library

Cited By

Munsters AScull Pupo AGonzalez Boix E(2024)BoaSpect: An Expressive Instrumentation Platform for JavaScriptCompanion Proceedings of the 8th International Conference on the Art, Science, and Engineering of Programming10.1145/3660829.3660839(47-51)Online publication date: 11-Mar-2024
https://dl.acm.org/doi/10.1145/3660829.3660839
Guo XQi XLi YWu C(2024)PredRacer: Predictively Detecting Data Races in Android Applications2024 IEEE International Conference on Software Analysis, Evolution and Reengineering (SANER)10.1109/SANER60148.2024.00031(239-249)Online publication date: 12-Mar-2024
https://doi.org/10.1109/SANER60148.2024.00031
Ganji MAlimadadi STip FChandra SBlincoe KTonella P(2023)Code Coverage Criteria for Asynchronous ProgramsProceedings of the 31st ACM Joint European Software Engineering Conference and Symposium on the Foundations of Software Engineering10.1145/3611643.3616292(1307-1319)Online publication date: 30-Nov-2023
https://dl.acm.org/doi/10.1145/3611643.3616292
Show More Cited By

Index Terms

Effective race detection for event-driven programs

Recommendations

Race detection for web applications
PLDI '12

Modern web pages are becoming increasingly full-featured, and this additional functionality often requires greater use of asynchrony. Unfortunately, this asynchrony can trigger unexpected concurrency errors, even though web page scripts are executed ...
Effective race detection for event-driven programs
OOPSLA '13

Like shared-memory multi-threaded programs, event-driven programs such as client-side web applications are susceptible to data races that are hard to reproduce and debug. Race detection for such programs is hampered by their pervasive use of ad hoc ...
Race directed random testing of concurrent programs
PLDI '08

Bugs in multi-threaded programs often arise due to data races. Numerous static and dynamic program analysis techniques have been proposed to detect data races. We propose a novel randomized dynamic analysis technique that utilizes potential data race ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

OOPSLA '13: Proceedings of the 2013 ACM SIGPLAN international conference on Object oriented programming systems languages & applications

October 2013

904 pages

ISBN:9781450323741

DOI:10.1145/2509136

Co-chair:
Antony Hosking
Purdue University, USA
,
General Chair:
Patrick Eugster
Purdue University, USA
,
Program Chair:
Cristina V. Lopes
University of California, Irvine, USA

ACM SIGPLAN Notices Volume 48, Issue 10
OOPSLA '13
October 2013
867 pages
ISSN:0362-1340
EISSN:1558-1160
DOI:10.1145/2544173
Editor:
Mark W. Bailey
Hamilton College, Clinton, NY
Issue’s Table of Contents

Copyright © 2013 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: 29 October 2013

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

SPLASH '13

Sponsor:

SIGPLAN

SPLASH '13: Conference on Systems, Programming, and Applications: Software for Humanity

October 29 - 31, 2013

Indiana, Indianapolis, USA

Acceptance Rates

OOPSLA '13 Paper Acceptance Rate 50 of 189 submissions, 26%;

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

Upcoming Conference

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

119
Total Citations
View Citations
766
Total Downloads

Downloads (Last 12 months)60
Downloads (Last 6 weeks)11

Reflects downloads up to 24 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Munsters AScull Pupo AGonzalez Boix E(2024)BoaSpect: An Expressive Instrumentation Platform for JavaScriptCompanion Proceedings of the 8th International Conference on the Art, Science, and Engineering of Programming10.1145/3660829.3660839(47-51)Online publication date: 11-Mar-2024
https://dl.acm.org/doi/10.1145/3660829.3660839
Guo XQi XLi YWu C(2024)PredRacer: Predictively Detecting Data Races in Android Applications2024 IEEE International Conference on Software Analysis, Evolution and Reengineering (SANER)10.1109/SANER60148.2024.00031(239-249)Online publication date: 12-Mar-2024
https://doi.org/10.1109/SANER60148.2024.00031
Ganji MAlimadadi STip FChandra SBlincoe KTonella P(2023)Code Coverage Criteria for Asynchronous ProgramsProceedings of the 31st ACM Joint European Software Engineering Conference and Symposium on the Foundations of Software Engineering10.1145/3611643.3616292(1307-1319)Online publication date: 30-Nov-2023
https://dl.acm.org/doi/10.1145/3611643.3616292
Cui SGao YUnterguggenberger RPichler WLivingstone SHuang J(2023)SmallRace: Static Race Detection for Dynamic Languages - A Case on Smalltalk2023 IEEE/ACM 45th International Conference on Software Engineering (ICSE)10.1109/ICSE48619.2023.00102(1136-1147)Online publication date: May-2023
https://doi.org/10.1109/ICSE48619.2023.00102
Abdulla PAtig MBønneland FDas SJonsson BLång MSagonas K(2023)Tailoring Stateless Model Checking for Event-Driven Multi-threaded ProgramsAutomated Technology for Verification and Analysis10.1007/978-3-031-45332-8_9(176-198)Online publication date: 19-Oct-2023
https://doi.org/10.1007/978-3-031-45332-8_9
Qiu ZShao SZhao QKhan HHui XJin GLo DMcIntosh SNovielli N(2022)A deep study of the effects and fixes of server-side request races in web applicationsProceedings of the 19th International Conference on Mining Software Repositories10.1145/3524842.3528463(744-756)Online publication date: 23-May-2022
https://dl.acm.org/doi/10.1145/3524842.3528463
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
Qiu ZShao SZhao QJin GSpinellis DGousios GChechik MDi Penta M(2021)Understanding and detecting server-side request races in web applicationsProceedings of the 29th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering10.1145/3468264.3468594(842-854)Online publication date: 20-Aug-2021
https://dl.acm.org/doi/10.1145/3468264.3468594
Liu BLiu PLi YTsai CDa Silva DHuang JFreund SYahav E(2021)When threads meet events: efficient and precise static race detection with originsProceedings of the 42nd ACM SIGPLAN International Conference on Programming Language Design and Implementation10.1145/3453483.3454073(725-739)Online publication date: 19-Jun-2021
https://dl.acm.org/doi/10.1145/3453483.3454073
Chang XDou WWei JHuang TXie JDeng YYang JYang JGrundy J(2021)Race detection for event-driven Node.js applicationsProceedings of the 36th IEEE/ACM International Conference on Automated Software Engineering10.1109/ASE51524.2021.9678814(480-491)Online publication date: 15-Nov-2021
https://dl.acm.org/doi/10.1109/ASE51524.2021.9678814
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