research-article

Race detection for Android applications

Authors:

Rupak MajumdarAuthors Info & Claims

ACM SIGPLAN Notices, Volume 49, Issue 6

Pages 316 - 325

https://doi.org/10.1145/2666356.2594311

Published: 09 June 2014 Publication History

Abstract

Programming environments for smartphones expose a concurrency model that combines multi-threading and asynchronous event-based dispatch. While this enables the development of efficient and feature-rich applications, unforeseen thread interleavings coupled with non-deterministic reorderings of asynchronous tasks can lead to subtle concurrency errors in the applications.

In this paper, we formalize the concurrency semantics of the Android programming model. We further define the happens-before relation for Android applications, and develop a dynamic race detection technique based on this relation. Our relation generalizes the so far independently studied happens-before relations for multi-threaded programs and single-threaded event-driven programs. Additionally, our race detection technique uses a model of the Android runtime environment to reduce false positives.

We have implemented a tool called DroidRacer. It generates execution traces by systematically testing Android applications and detects data races by computing the happens-before relation on the traces. We analyzed 15 Android applications including popular applications such as Facebook, Twitter and K-9 Mail. Our results indicate that data races are prevalent in Android applications, and that DroidRacer is an effective tool to identify data races.

References

[1]

J. Alves-Foss, editor. Formal Syntax and Semantics of Java, volume 1523 of LNCS, 1999.

Digital Library

[2]

D. Amalfitano, A. R. Fasolino, P. Tramontana, S. D. Carmine, and A. M. Memon. Using GUI ripping for automated testing of Android applications. In ASE, pages 258--261, 2012.

Digital Library

[3]

A. Desai, V. Gupta, E. Jackson, S. Qadeer, S. Rajamani, and D. Zufferey. P: safe asynchronous event-driven programming. In PLDI, pages 321--332. ACM, 2013.

Digital Library

[4]

A. Dunkels, B. Gronvall, and T. Voigt. Contiki - A lightweight and flexible operating system for tiny networked sensors. In LCN, pages 455--462, 2004.

Digital Library

[5]

D. Engler and K. Ashcraft. RacerX: Effective, static detection of race conditions and deadlocks. In SOSP, pages 237--252, 2003.

Digital Library

[6]

C. Flanagan and S. N. Freund. Type-based race detection for Java. In PLDI, pages 219--232, 2000.

Digital Library

[7]

C. Flanagan and S. N. Freund. FastTrack: Efficient and precise dynamic race detection. In PLDI, pages 121--133, 2009.

Digital Library

[8]

P. Ganty and R. Majumdar. Algorithmic verification of asynchronous programs. TOPLAS, 34(1):6:1--6:48, 2012.

Digital Library

[9]

J. Ide, R. Bodik, and D. Kimelman. Concurrency concerns in rich internet applications. In EC(2), CAV Workshop, 2009.

[10]

A. Igarashi, B. C. Pierce, and P. Wadler. Featherweight Java: A minimal core calculus for Java and GJ. TOPLAS, pages 396--450, 2001.

Digital Library

[11]

A. Itzkovitz, A. Schuster, and O. Zeev-Ben-Mordehai. Toward integration of data race detection in DSM systems. J. Parallel Distrib. Comput., pages 180--203, 1999.

Digital Library

[12]

H. Jula, T. Rensch, and G. Candea. Platform-wide deadlock immunity for mobile phones. In DSN-W, pages 205--210, 2011.

Digital Library

[13]

V. Kahlon, N. Sinha, E. Kruus, and Y. Zhang. Static data race detection for concurrent programs with asynchronous calls. In ESEC/FSE, pages 13--22, 2009.

Digital Library

[14]

K. Klues, C. M. Liang, J. Paek, R. Musaloiu-Elefteri, P. Levis, A. Terzis, and R. Govindan. TOSThreads: Thread-safe and non-invasive preemption in TinyOS. In SenSys, pages 127--140, 2009.

Digital Library

[15]

L. Lamport. Time, clocks, and the ordering of events in a distributed system. Commun. ACM, pages 558--565, 1978.

Digital Library

[16]

A. Machiry, R. Tahiliani, and M. Naik. Dynodroid: an input generation system for Android apps. In FSE, pages 224--234, 2013.

Digital Library

[17]

M. Naik, A. Aiken, and J. Whaley. Effective static race detection for Java. In PLDI, pages 308--319, 2006.

Digital Library

[18]

R. O'Callahan and J. Choi. Hybrid dynamic data race detection. In PPOPP, pages 167--178, 2003.

Digital Library

[19]

V. S. Pai, P. Druschel, and W. Zwaenepoel. Flash: An efficient and portable web server. In USENIX, pages 199--212, 1999.

Digital Library

[20]

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

Digital Library

[21]

E. Pozniansky and A. Schuster. Efficient on-the-fly data race detection in multithreaded C++ programs. In PPOPP, pages 179--190, 2003.

Digital Library

[22]

E. Pozniansky and A. Schuster. MultiRace: Efficient on-the-fly data race detection in multithreaded C++ programs. Concurr. Comput.: Pract. Exper., pages 327--340, 2007.

Digital Library

[23]

P. Pratikakis, J. S. Foster, and M. Hicks. LOCKSMITH: Practical static race detection for C. TOPLAS, 33(1):3:1--3:55, 2011.

Digital Library

[24]

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

Digital Library

[25]

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

Digital Library

[26]

K. Veeraraghavan, P. M. Chen, J. Flinn, and S. Narayanasamy. Detecting and surviving data races using complementary schedules. In SOSP, pages 369--384, 2011.

Digital Library

[27]

J. W. Voung, R. Jhala, and S. Lerner. RELAY: Static race detection on millions of lines of code. In FSE, pages 205--214, 2007.

Digital Library

[28]

Y. Yu, T. Rodeheffer, and W. Chen. Racetrack: Efficient detection of data race conditions via adaptive tracking. In SOSP, pages 221--234, 2005.

Digital Library

[29]

S. Zhang, H. Lü, and M. D. Ernst. Finding errors in multithreaded GUI applications. In ISSTA, pages 243--253, 2012.

Digital Library

[30]

Y. Zheng, T. Bao, and X. Zhang. Statically locating web application bugs caused by asynchronous calls. In WWW, pages 805--814, 2011.

Digital Library

Cited By

Qiu JZhou ZLi YLi ZQian FLin HGao DSu HMiao XLiu YXu TWitchel EArpaci-Dusseau ARossbach CKeeton K(2024)vSoC: Efficient Virtual System-on-Chip on Heterogeneous HardwareProceedings of the ACM SIGOPS 30th Symposium on Operating Systems Principles10.1145/3694715.3695946(558-573)Online publication date: 4-Nov-2024
https://dl.acm.org/doi/10.1145/3694715.3695946
Alecci MSamhi JLi LBissyandé TKlein J(2024)Improving Logic Bomb Identification in Android Apps via Context-Aware Anomaly DetectionIEEE Transactions on Dependable and Secure Computing10.1109/TDSC.2024.335897921:5(4735-4753)Online publication date: 1-Sep-2024
https://dl.acm.org/doi/10.1109/TDSC.2024.3358979
Zhou JXu LLu GZhang WZhang XJust RFraser G(2023)NodeRT: Detecting Races in Node.js Applications PracticallyProceedings of the 32nd ACM SIGSOFT International Symposium on Software Testing and Analysis10.1145/3597926.3598139(1332-1344)Online publication date: 12-Jul-2023
https://dl.acm.org/doi/10.1145/3597926.3598139
Show More Cited By

Index Terms

Race detection for Android applications

Recommendations

Scalable race detection for Android applications
OOPSLA '15

We present a complete end-to-end dynamic analysis system for finding data races in mobile Android applications. The capabilities of our system significantly exceed the state of the art: our system can analyze real-world application interactions in ...
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 ...
Race detection for Android applications
PLDI '14: Proceedings of the 35th ACM SIGPLAN Conference on Programming Language Design and Implementation

Programming environments for smartphones expose a concurrency model that combines multi-threading and asynchronous event-based dispatch. While this enables the development of efficient and feature-rich applications, unforeseen thread interleavings ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM SIGPLAN Notices

ACM SIGPLAN Notices Volume 49, Issue 6

PLDI '14

June 2014

598 pages

ISSN:0362-1340

EISSN:1558-1160

DOI:10.1145/2666356

Editor:
Andy Gill
University of Kansas, Lawrence, KS

Issue’s Table of Contents

PLDI '14: Proceedings of the 35th ACM SIGPLAN Conference on Programming Language Design and Implementation
June 2014
619 pages
ISBN:9781450327848
DOI:10.1145/2594291
General Chair:
Michael O'Boyle
University of Edinburgh
,
Program Chair:
Keshav Pingali
University of Texas, Austin

Copyright © 2014 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]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 09 June 2014

Published in SIGPLAN Volume 49, Issue 6

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Bundesministerium für Bildung und Forschung
Department of Science and Technology, Ministry of Science and Technology
Government of India
Government of Germany
Max-Planck-Gesellschaft

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

126
Total Citations
View Citations
1,047
Total Downloads

Downloads (Last 12 months)29
Downloads (Last 6 weeks)9

Reflects downloads up to 12 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Qiu JZhou ZLi YLi ZQian FLin HGao DSu HMiao XLiu YXu TWitchel EArpaci-Dusseau ARossbach CKeeton K(2024)vSoC: Efficient Virtual System-on-Chip on Heterogeneous HardwareProceedings of the ACM SIGOPS 30th Symposium on Operating Systems Principles10.1145/3694715.3695946(558-573)Online publication date: 4-Nov-2024
https://dl.acm.org/doi/10.1145/3694715.3695946
Alecci MSamhi JLi LBissyandé TKlein J(2024)Improving Logic Bomb Identification in Android Apps via Context-Aware Anomaly DetectionIEEE Transactions on Dependable and Secure Computing10.1109/TDSC.2024.335897921:5(4735-4753)Online publication date: 1-Sep-2024
https://dl.acm.org/doi/10.1109/TDSC.2024.3358979
Zhou JXu LLu GZhang WZhang XJust RFraser G(2023)NodeRT: Detecting Races in Node.js Applications PracticallyProceedings of the 32nd ACM SIGSOFT International Symposium on Software Testing and Analysis10.1145/3597926.3598139(1332-1344)Online publication date: 12-Jul-2023
https://dl.acm.org/doi/10.1145/3597926.3598139
Eke NSalihu IUsman A(2023)Comparative Analysis of Fully Automated Testing Techniques for Android Applications2023 2nd International Conference on Multidisciplinary Engineering and Applied Science (ICMEAS)10.1109/ICMEAS58693.2023.10429901(1-6)Online publication date: 1-Nov-2023
https://doi.org/10.1109/ICMEAS58693.2023.10429901
Cui BWang MZhang CYan JYan JZhang JBissyandé TKlein JBird CSarro F(2023)Detection of Java Basic Thread Misuses Based on Static Event AnalysisProceedings of the 38th IEEE/ACM International Conference on Automated Software Engineering10.1109/ASE56229.2023.00145(1049-1060)Online publication date: 11-Nov-2023
https://dl.acm.org/doi/10.1109/ASE56229.2023.00145
Li CChen RWang BYu TGao DYang MRyu SSmaragdakis Y(2022)Precise and efficient atomicity violation detection for interrupt-driven programs via staged path pruningProceedings of the 31st ACM SIGSOFT International Symposium on Software Testing and Analysis10.1145/3533767.3534412(506-518)Online publication date: 18-Jul-2022
https://dl.acm.org/doi/10.1145/3533767.3534412
Samhi JGao JDaoudi NGraux PHoyez HSun XAllix KBissyandé TKlein JDwyer MDamian DZeller A(2022)JuCifyProceedings of the 44th International Conference on Software Engineering10.1145/3510003.3512766(1232-1244)Online publication date: 21-May-2022
https://dl.acm.org/doi/10.1145/3510003.3512766
Samhi JLi LBissyandé TKlein JDwyer MDamian DZeller A(2022)DifuzerProceedings of the 44th International Conference on Software Engineering10.1145/3510003.3510135(723-735)Online publication date: 21-May-2022
https://dl.acm.org/doi/10.1145/3510003.3510135
Wang YGao FWang LYu TZhao JLi X(2022)Automatic Detection, Validation, and Repair of Race Conditions in Interrupt-Driven Embedded SoftwareIEEE Transactions on Software Engineering10.1109/TSE.2020.298917148:1(346-363)Online publication date: 1-Jan-2022
https://doi.org/10.1109/TSE.2020.2989171
Dentamaro VImpedovo DPirlo GAbbattista GGattulli VBuscicchio CFiore C(2021)Non-Invasive Personalized In-Store Location-Based MarketingHandbook of Research on Applied AI for International Business and Marketing Applications10.4018/978-1-7998-5077-9.ch018(365-390)Online publication date: 2021
https://doi.org/10.4018/978-1-7998-5077-9.ch018
Show More Cited By

View Options

Get Access

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 Issue’s Table of Contents