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

research-article

Public Access

AsyncClock: Scalable Inference of Asynchronous Event Causality

Authors:

Chun-Hung Hsiao,

Satish Narayanasamy,

Essam Muhammad Idris Khan,

Cristiano L. Pereira,

Gilles A. PokamAuthors Info & Claims

ACM SIGPLAN Notices, Volume 52, Issue 4

Pages 193 - 205

https://doi.org/10.1145/3093336.3037712

Published: 04 April 2017 Publication History

Abstract

Asynchronous programming model is commonly used in mobile systems and Web 2.0 environments. Asynchronous race detectors use algorithms that are an order of magnitude performance and space inefficient compared to conventional data race detectors. We solve this problem by identifying and addressing two important problems in reasoning about causality between asynchronous events.

Unlike conventional signal-wait operations, establishing causal order between two asynchronous events is fundamentally more challenging as there is no common handle they operate on. We propose a new primitive named AsyncClock that addresses this problem by explicitly tracking causally preceding events, and show that AsyncClock can handle a wide variety of asynchronous causality models. We also address the important scalability problem of efficiently identifying heirless events whose metadata can be reclaimed.

We built the first single-pass, non-graph-based Android race detector using our algorithm and applied it to find errors in 20 popular applications. Our tool incurs about 6x performance overhead, which is several times more efficient than the state-of-the-art solution. It also scales well with the execution length. We used our tool to find 147 previously unknown harmful races.

References

[1]

Message | android developers. https://developer.android.com/reference/android/os/Message.html#setAsynchronous(boolean). [Online; accessed 2016-08-15].

[2]

tool:androidmonkeyUi/application exerciser monkey | android studio. https://developer.android.com/studio/test/monkey.html,natexlaba. [Online; accessed 2016-08--15].

[3]

tool:droidracerdroidracer - software engineering and analysis lab (seal), iisc bangalore. http://www.iisc-seal.net/droidracer,natexlabb. [Online; accessed 2016-08-15].

[4]

tool:eventracerandroid Event racer for android. http://eventracer.org/android/,natexlabc. [Online; accessed 2016-08--15].

[5]

S. V. Adve, M. D. Hill, B. P. Miller, and R. H. B. Netzer. Detecting data races on weak memory systems. SIGARCH Comput. Archit. News, 19 (3): 234--243, Apr. 1991. ISSN 0163--5964. 10.1145/115953.115976. URL http://doi.acm.org/10.1145/115953.115976.

Digital Library

[6]

P. Bielik, V. Raychev, and M. Vechev. Scalable race detection for android applications. In Proceedings of the 2015 ACM SIGPLAN International Conference on Object-Oriented Programming, Systems, Languages, and Applications, OOPSLA 2015, pages 332--348, New York, NY, USA, 2015. ACM. ISBN 978-1-4503-3689-5. 10.1145/2814270.2814303. URL http://doi.acm.org/10.1145/2814270.2814303.

Digital Library

[7]

M. Christiaens and K. Bosschere. Euro-Par 2001 Parallel Processing: 7th International Euro-Par Conference Manchester, UK, August 28--31, 2001 Proceedings, chapter Accordion Clocks: Logical Clocks for Data Race Detection, pages 494--503. Springer Berlin Heidelberg, Berlin, Heidelberg, 2001. ISBN 978-3-540-44681-1. 10.1007/3-540-44681-8_73. URL http://dx.doi.org/10.1007/3-540-44681-8_73.

[8]

D. Dimitrov, V. Raychev, M. Vechev, and E. Koskinen. Commutativity race detection. In Proceedings of the 35th ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI '14, pages 305--315, New York, NY, USA, 2014. ACM. ISBN 978-1-4503-2784-8. 10.1145/2594291.2594322. URL http://doi.acm.org/10.1145/2594291.2594322.

Digital Library

[9]

D. R. Engler and K. Ashcraft. RacerX: Effective, Static Detection of Race Conditions and Deadlocks. In SOSP, pages 237--252, 2003.

Digital Library

[10]

C. Flanagan and S. N. Freund. FastTrack: Efficient and Precise Dynamic Race Detection. In PLDI, pages 121--133, 2009.

Digital Library

[11]

C.-H. Hsiao, J. Yu, S. Narayanasamy, Z. Kong, C. L. Pereira, G. A. Pokam, P. M. Chen, and J. Flinn. Race detection for event-driven mobile applications. In Proceedings of the 35th ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI '14, pages 326--336, New York, NY, USA, 2014. ACM. ISBN 978-1-4503-2784-8. 10.1145/2594291.2594330. URL http://doi.acm.org/10.1145/2594291.2594330.

Digital Library

[12]

H. V. Jagadish. A compression technique to materialize transitive closure. ACM Trans. Database Syst., 15 (4): 558--598, Dec. 1990. ISSN 0362-5915. 10.1145/99935.99944. URL http://doi.acm.org/10.1145/99935.99944.

Digital Library

[13]

P. Maiya, A. Kanade, and R. Majumdar. Race detection for android applications. In Proceedings of the 35th ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI '14, pages 316--325, New York, NY, USA, 2014. ACM. ISBN 978-1-4503-2784-8. 10.1145/2594291.2594311. URL http://doi.acm.org/10.1145/2594291.2594311.

Digital Library

[14]

F. Mattern. Virtual time and global states of distributed systems. In Parallel and Distributed Algorithms, pages 215--226. North-Holland, 1989.

[15]

R. H. B. Netzer. Optimal Tracing and Replay for Debugging Shared-Memory Parallel Programs. In Workshop on Parallel and Distributed Debugging, pages 1--11, 1993.

Digital Library

[16]

B. Petrov, M. T. Vechev, M. Sridharan, and J. Dolby. Race detection for web applications. In PLDI, pages 251--262, 2012.

Digital Library

[17]

V. Raychev, M. T. Vechev, and M. Sridharan. Effective race detection for event-driven programs. In OOPSLA, pages 151--166, 2013.

Digital Library

[18]

J. W. Voung, R. Jhala, and S. Lerner. RELAY: Static Race Detection on Millions of Lines of Code. In ESEC/SIGSOFT FSE, pages 205--214, 2007.

Digital Library

Cited By

Ma PJi ZYao PWang SRen KRoychoudhury APaiva AAbreu RStorey M(2024)Enabling Runtime Verification of Causal Discovery Algorithms with Automated Conditional Independence ReasoningProceedings of the IEEE/ACM 46th International Conference on Software Engineering10.1145/3597503.3623348(1-13)Online publication date: 20-May-2024
https://dl.acm.org/doi/10.1145/3597503.3623348
Ji ZMa PWang SBissyandé TKlein JBird CSarro F(2023)PerfCE: Performance Debugging on Databases with Chaos Engineering-Enhanced Causality AnalysisProceedings of the 38th IEEE/ACM International Conference on Automated Software Engineering10.1109/ASE56229.2023.00106(1454-1466)Online publication date: 11-Nov-2023
https://dl.acm.org/doi/10.1109/ASE56229.2023.00106
Salehnamadi NAlshayban AAhmed IMalek SGrundy JLe Goues CLo D(2020)ER catcherProceedings of the 35th IEEE/ACM International Conference on Automated Software Engineering10.1145/3324884.3416639(324-335)Online publication date: 21-Dec-2020
https://dl.acm.org/doi/10.1145/3324884.3416639
Show More Cited By

Index Terms

AsyncClock: Scalable Inference of Asynchronous Event Causality
1. Software and its engineering
  1. Software creation and management
    1. Software verification and validation
      1. Software defect analysis
        Software testing and debugging
2. Theory of computation
  1. Semantics and reasoning
    1. Program reasoning
      1. Program analysis

Recommendations

Race detection for event-driven mobile applications
PLDI '14

Mobile systems commonly support an event-based model of concurrent programming. This model, used in popular platforms such as Android, naturally supports mobile devices that have a rich array of sensors and user input modalities. Unfortunately, most ...
AsyncClock: Scalable Inference of Asynchronous Event Causality
ASPLOS '17: Proceedings of the Twenty-Second International Conference on Architectural Support for Programming Languages and Operating Systems

Asynchronous programming model is commonly used in mobile systems and Web 2.0 environments. Asynchronous race detectors use algorithms that are an order of magnitude performance and space inefficient compared to conventional data race detectors. We ...
AsyncClock: Scalable Inference of Asynchronous Event Causality
Asplos'17

Asynchronous programming model is commonly used in mobile systems and Web 2.0 environments. Asynchronous race detectors use algorithms that are an order of magnitude performance and space inefficient compared to conventional data race detectors. We ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM SIGPLAN Notices

ACM SIGPLAN Notices Volume 52, Issue 4

ASPLOS '17

April 2017

811 pages

ISSN:0362-1340

EISSN:1558-1160

DOI:10.1145/3093336

Editor:
Matthew Fluet

Issue’s Table of Contents

ASPLOS '17: Proceedings of the Twenty-Second International Conference on Architectural Support for Programming Languages and Operating Systems
April 2017
856 pages
ISBN:9781450344654
DOI:10.1145/3037697
General Chairs:
Yunji Chen
Institute of Computing Technology, CAS, China
,
Olivier Temam
Google, USA
,
Program Chair:
John Carter
IBM, USA

Copyright © 2017 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 the author(s) 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].

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 04 April 2017

Published in SIGPLAN Volume 52, Issue 4

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

MARCO/DARPA
NSF
Intel

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

9
Total Citations
View Citations
740
Total Downloads

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

Reflects downloads up to 01 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Ma PJi ZYao PWang SRen KRoychoudhury APaiva AAbreu RStorey M(2024)Enabling Runtime Verification of Causal Discovery Algorithms with Automated Conditional Independence ReasoningProceedings of the IEEE/ACM 46th International Conference on Software Engineering10.1145/3597503.3623348(1-13)Online publication date: 20-May-2024
https://dl.acm.org/doi/10.1145/3597503.3623348
Ji ZMa PWang SBissyandé TKlein JBird CSarro F(2023)PerfCE: Performance Debugging on Databases with Chaos Engineering-Enhanced Causality AnalysisProceedings of the 38th IEEE/ACM International Conference on Automated Software Engineering10.1109/ASE56229.2023.00106(1454-1466)Online publication date: 11-Nov-2023
https://dl.acm.org/doi/10.1109/ASE56229.2023.00106
Salehnamadi NAlshayban AAhmed IMalek SGrundy JLe Goues CLo D(2020)ER catcherProceedings of the 35th IEEE/ACM International Conference on Automated Software Engineering10.1145/3324884.3416639(324-335)Online publication date: 21-Dec-2020
https://dl.acm.org/doi/10.1145/3324884.3416639
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
Xu YSinger KLee IGupta RShen X(2020)Parallel determinacy race detection for futuresProceedings of the 25th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming10.1145/3332466.3374536(217-231)Online publication date: 19-Feb-2020
https://dl.acm.org/doi/10.1145/3332466.3374536
Li GLu SMusuvathi MNath SPadhye RBrecht TWilliamson C(2019)Efficient scalable thread-safety-violation detectionProceedings of the 27th ACM Symposium on Operating Systems Principles10.1145/3341301.3359638(162-180)Online publication date: 27-Oct-2019
https://dl.acm.org/doi/10.1145/3341301.3359638
Wu DLiu JSui YChen SXue J(2019)Precise Static Happens-Before Analysis for Detecting UAF Order Violations in Android2019 12th IEEE Conference on Software Testing, Validation and Verification (ICST)10.1109/ICST.2019.00035(276-287)Online publication date: Apr-2019
https://doi.org/10.1109/ICST.2019.00035
Maiya PKanade ABultan TSen K(2017)Efficient computation of happens-before relation for event-driven programsProceedings of the 26th ACM SIGSOFT International Symposium on Software Testing and Analysis10.1145/3092703.3092733(102-112)Online publication date: 10-Jul-2017
https://dl.acm.org/doi/10.1145/3092703.3092733

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

Figures

Tables

Media

View Issue’s Table of Contents