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

research-article

Public Access

nAdroid: statically detecting ordering violations in Android applications

Authors:

Changhee JungAuthors Info & Claims

CGO '18: Proceedings of the 2018 International Symposium on Code Generation and Optimization

Pages 62 - 74

https://doi.org/10.1145/3168829

Published: 24 February 2018 Publication History

Abstract

Modern mobile applications use a hybrid concurrency model. In this model, events are handled sequentially by event loop(s), and long-running tasks are offloaded to other threads. Concurrency errors in this hybrid concurrency model can take multiple forms: traditional atomicity and ordering violations between threads, as well as ordering violations between event callbacks on a single event loop.

This paper presents nAdroid, a static ordering violation detector for Android applications. Using our threadification technique, nAdroid statically models event callbacks as threads. Threadification converts ordering violations between event callbacks into ordering violations between threads, after which state-of-the-art thread-based race detection tools can be applied. nAdroid then applies a combination of sound and unsound filters, based on the Android concurrency model and its happens-before relation, to prune out false and benign warnings.

We evaluated nAdroid with 27 open source Android applications. Experimental results show that nAdroid detects 88 (at least 58 new) harmful ordering violations, and outperforms the state-of-the-art static technique with fewer false negatives and false positives.

References

[1]

Steven Arzt, Siegfried Rasthofer, Christian Fritz, Eric Bodden, Alexandre Bartel, Jacques Klein, Yves Le Traon, Damien Octeau, and Patrick McDaniel. 2014. FlowDroid: Precise Context, Flow, Field, Object-sensitive and Lifecycle-aware Taint Analysis for Android Apps. In Proceedings of the 35th ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI '14). 259-269.

Digital Library

[2]

Abhijeet Banerjee, Lee Kee Chong, Sudipta Chattopadhyay, and Abhik Roychoudhury. 2014. Detecting Energy Bugs and Hotspots in Mobile Apps. In Proceedings of the 22Nd ACM SIGSOFT International Symposium on Foundations of Software Engineering (FSE 2014). 588-598.

Digital Library

[3]

Pavol Bielik, Veselin Raychev, and Martin Vechev. 2015. 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). 332-348.

Digital Library

[4]

Sam Blackshear, Alexandra Gendreau, and Bor-Yuh Evan Chang. 2015. Droidel: A General Approach to Android Framework Modeling. In Proceedings of the 4th ACM SIGPLAN International Workshop on State Of the Art in Program Analysis (SOAP 2015). 19-25.

Digital Library

[5]

Chandrasekhar Boyapati, Robert Lee, and Martin Rinard. 2002. Ownership Types for Safe Programming: Preventing Data Races and Deadlocks. In Proceedings of the 17th ACM SIGPLAN Conference on Object-oriented Programming, Systems, Languages, and Applications (OOPSLA '02). 211-230.

Digital Library

[6]

CVE-2008-0034. 2008. http://www.cvedetails.com/cve/CVE-2008-0034.

[7]

CVE-2010-0923. 2010. http://www.cvedetails.com/cve/CVE-2010-0923.

[8]

CVE-2010-1754. 2010. http://www.cvedetails.com/cve/CVE-2010-1754.

[9]

James Davis, Arun Thekumparampil, and Dongyoon Lee. 2017. Node. fz: Fuzzing the Server-Side Event-Driven Architecture. In Proceedings of the Twelfth European Conference on Computer Systems. ACM, 145-160.

Digital Library

[10]

James Davis, Arun Thekumparampil, and Dongyoon Lee. 2017. Node.Fz: Fuzzing the Server-Side Event-Driven Architecture. In Proceedings of the Twelfth European Conference on Computer Systems (EuroSys'17). 145-160.

Digital Library

[11]

Evelyn Duesterwald and Mary Lou Soffa. 1991. Concurrency analysis in the presence of procedures using a data-flow framework. In Proceedings of the symposium on Testing, analysis, and verification. ACM, 36-48.

Digital Library

[12]

Dawson Engler and Ken Ashcraft. 2003. RacerX: Effective, Static Detection of Race Conditions and Deadlocks. In Proceedings of the Nineteenth ACM Symposium on Operating Systems Principles (SOSP '03). 237-252.

Digital Library

[13]

F-Droid. 2017. https://f-droid.org/.

[14]

Cormac Flanagan and Stephen N. Freund. 2000. Type-based Race Detection for Java. In Proceedings of the ACM SIGPLAN 2000 Conference on Programming Language Design and Implementation (PLDI '00). 219-232.

Digital Library

[15]

Cormac Flanagan and Stephen N Freund. 2009. FastTrack: efficient and precise dynamic race detection. In ACM Sigplan Notices, Vol. 44. ACM, 121-133.

Digital Library

[16]

Patrice Godefroid. 1997. Model checking for programming languages using VeriSoft. In Proceedings of the 24th ACM SIGPLAN-SIGACT symposium on Principles of programming languages. ACM, 174-186.

Digital Library

[17]

Chun-Hung Hsiao, Jie Yu, Satish Narayanasamy, Ziyun Kong, Cristiano L. Pereira, Gilles A. Pokam, Peter M. Chen, and Jason Flinn. 2014. Race Detection for Event-driven Mobile Applications. In Proceedings of the 35th ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI '14). 326-336.

Digital Library

[18]

Jeff Huang. 2015. Stateless model checking concurrent programs with maximal causality reduction. In ACM SIGPLAN Notices, Vol. 50. ACM, 165-174.

Digital Library

[19]

Jeff Huang and Arun K Rajagopalan. 2016. Precise and maximal race detection from incomplete traces. In Proceedings of the 2016 ACM SIGPLAN International Conference on Object-Oriented Programming, Systems, Languages, and Applications. ACM, 462-476.

Digital Library

[20]

Baris Kasikci, Cristian Zamfir, and George Candea. 2012. Data Races vs. Data Race Bugs: Telling the Difference with Portend. In Proceedings of the Seventeenth International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS XVII). 185-198.

Digital Library

[21]

Patrick Lam, Eric Bodden, Ondrej Lhotak, and Laurie Hendren. 2011. The Soot framework for Java program analysis: a retrospective. In Cetus Users and Compiler Infastructure Workshop (CETUS 2011), Vol. 15. 35.

[22]

Leslie Lamport. 1978. Time, Clocks, and the Ordering of Events in a Distributed System. Commun. ACM 21, 7 (July 1978), 558-565.

Digital Library

[23]

Lin Li and Clark Verbrugge. 2005. A Practical MHP Information Analysis for Concurrent Java Programs. In Proceedings of the 17th International Conference on Languages and Compilers for High Performance Computing (LCPC'04). 194-208.

Digital Library

[24]

Yu Lin, Cosmin Radoi, and Danny Dig. 2014. Retrofitting Concurrency for Android Applications Through Refactoring. In Proceedings of the 22Nd ACM SIGSOFT International Symposium on Foundations of Software Engineering (FSE 2014). 341-352.

Digital Library

[25]

Brandon Lucia and Luis Ceze. 2013. Cooperative empirical failure avoidance for multithreaded programs. In ACM SIGPLAN Notices, Vol. 48. ACM, 39-50.

Digital Library

[26]

Pallavi Maiya, Aditya Kanade, and Rupak Majumdar. 2014. Race Detection for Android Applications. In Proceedings of the 35th ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI '14). 316-325.

Digital Library

[27]

Ana Milanova, Atanas Rountev, and Barbara G. Ryder. 2002. Parameterized Object Sensitivity for Points-to and Side-effect Analyses for Java. In Proceedings of the 2002 ACM SIGSOFT International Symposium on Software Testing and Analysis (ISSTA '02). 1-11.

Digital Library

[28]

Ana Milanova, Atanas Rountev, and Barbara G. Ryder. 2005. Parameterized Object Sensitivity for Points-to Analysis for Java. ACM Trans. Softw. Eng. Methodol. 14, 1 (Jan. 2005), 1-41.

Digital Library

[29]

Mayur Naik, Alex Aiken, and John Whaley. 2006. Effective Static Race Detection for Java. In Proceedings of the 2006 ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI '06). 308-319.

Digital Library

[30]

Satish Narayanasamy, Zhenghao Wang, Jordan Tigani, Andrew Edwards, and Brad Calder. 2007. Automatically Classifying Benign and Harmful Data Races Using Replay Analysis. In Proceedings of the 28th ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI '07). 22-31.

Digital Library

[31]

Gleb Naumovich, George S. Avrunin, and Lori A. Clarke. 1999. An Efficient Algorithm for Computing MHP Information for Concurrent Java Programs. In Proceedings of the 7th European Software Engineering Conference Held Jointly with the 7th ACM SIGSOFT International Symposium on Foundations of Software Engineering (ESEC/FSE-7). 338-354.

Digital Library

[32]

Best new octa-core Android smartphones (2015 edition). 2015. http://www.phonearena.com/news/Best-new-octa-core-Android-smartphones-2015-edition_id65222.

[33]

Abhinav Pathak, Abhilash Jindal, Y. Charlie Hu, and Samuel P. Midkiff. 2012. What is Keeping My Phone Awake?: Characterizing and Detecting No-sleep Energy Bugs in Smartphone Apps. In Proceedings of the 10th International Conference on Mobile Systems, Applications, and Services (MobiSys '12). 267-280.

Digital Library

[34]

Boris Petrov, Martin Vechev, Manu Sridharan, and Julian Dolby. 2012. Race Detection for Web Applications. In Proceedings of the 33rd ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI '12). 251-262.

Digital Library

[35]

Polyvios Pratikakis, Jeffrey S. Foster, and Michael Hicks. 2006. LOCKSMITH: Context-sensitive Correlation Analysis for Race Detection. In Proceedings of the 27th ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI '06). 320-331.

Digital Library

[36]

Polyvios Pratikakis, Jeffrey S. Foster, and Michael Hicks. 2011. LOCKSMITH: Practical Static Race Detection for C. ACM Trans. Program. Lang. Syst. 33, 1, Article 3 (Jan. 2011), 3:1-3:55 pages.

Digital Library

[37]

Shaz Qadeer and Dinghao Wu. 2004. KISS: Keep It Simple and Sequential. In Proceedings of the ACM SIGPLAN 2004 Conference on Programming Language Design and Implementation (PLDI '04). 14-24.

Digital Library

[38]

Veselin Raychev, Martin Vechev, and Manu Sridharan. 2013. Effective Race Detection for Event-driven Programs. In Proceedings of the 2013 ACM SIGPLAN International Conference on Object Oriented Programming Systems Languages & Applications (OOPSLA '13). 151-166.

Digital Library

[39]

Gholamreza Safi, Arman Shahbazian, William G. J. Halfond, and Nenad Medvidovic. 2015. Detecting Event Anomalies in Event-based Systems. In Proceedings of the 2015 10th Joint Meeting on Foundations of Software Engineering (ESEC/FSE 2015). 25-37.

Digital Library

[40]

Stefan Savage, Michael Burrows, Greg Nelson, Patrick Sobalvarro, and Thomas Anderson. 1997. Eraser: A dynamic data race detector for multithreaded programs. ACM Transactions on Computer Systems (TOCS) 15, 4 (1997), 391-411.

Digital Library

[41]

Tianwei Sheng, Neil Vachharajani, Stephane Eranian, Robert Hundt, Wenguang Chen, and Weimin Zheng. 2011. RACEZ: a lightweight and non-invasive race detection tool for production applications. In Software Engineering (ICSE), 2011 33rd International Conference on. IEEE, 401-410.

Digital Library

[42]

Kaushik Veeraraghavan, Peter M Chen, Jason Flinn, and Satish Narayanasamy. 2011. Detecting and surviving data races using complementary schedules. In Proceedings of the twenty-third ACM symposium on operating systems principles. ACM, 369-384.

Digital Library

[43]

Jan Wen Voung, Ranjit Jhala, and Sorin Lerner. 2007. RELAY: Static Race Detection on Millions of Lines of Code. In Proceedings of the the 6th Joint Meeting of the European Software Engineering Conference and the ACM SIGSOFT Symposium on The Foundations of Software Engineering (ESEC-FSE '07). 205-214.

Digital Library

[44]

TJ Wala. 2014. Watson libraries for analysis. http://wala.sourceforge.net/wiki/index.php/Main_Page.

[45]

Wenwen Wang, Zhenjiang Wang, Chenggang Wu, Pen-Chung Yew, Xipeng Shen, Xiang Yuan, Jianjun Li, Xiaobing Feng, and Yong Guan. 2014. Localization of concurrency bugs using shared memory access pairs. In Proceedings of the 29th ACM/IEEE international conference on Automated software engineering. ACM, 611-622.

Digital Library

[46]

John Whaley. 2007. Context-sensitive Pointer Analysis Using Binary Decision Diagrams. Ph.D. Dissertation. Stanford, CA, USA. Advisor(s) Lam, Monica. AAI3253554.

Digital Library

[47]

Jingyue Wu, Heming Cui, and Junfeng Yang. 2010. Bypassing Races in Live Applications with Execution Filters. In OSDI, Vol. 10. 1-13.

Digital Library

[48]

Yuan Yu, Tom Rodeheffer, and Wei Chen. 2005. Racetrack: efficient detection of data race conditions via adaptive tracking. In ACM SIGOPS Operating Systems Review, Vol. 39. ACM, 221-234.

Digital Library

[49]

Tong Zhang, Changhee Jung, and Dongyoon Lee. 2017. ProRace: Practical Data Race Detection for Production Use. In Proceedings of the Twenty-Second International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS '17). 149-162.

Digital Library

[50]

Tong Zhang, Dongyoon Lee, and Changhee Jung. 2016. TxRace: Efficient Data Race Detection Using Commodity Hardware Transactional Memory. In Proceedings of the Twenty-First International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS '16). 159-173.

Digital Library

Cited By

Coppola RFulcini TArdito LTorchiano M(2025)Kotlin assimilating the Android ecosystem: An appraisal of diffusion and impact on maintainabilityJournal of Systems and Software10.1016/j.jss.2025.112346222(112346)Online publication date: Apr-2025
https://doi.org/10.1016/j.jss.2025.112346
Samhi JJust RBissyandé TErnst MKlein JChristakis MPradel M(2024)Call Graph Soundness in Android Static AnalysisProceedings of the 33rd ACM SIGSOFT International Symposium on Software Testing and Analysis10.1145/3650212.3680333(945-957)Online publication date: 11-Sep-2024
https://dl.acm.org/doi/10.1145/3650212.3680333
Bozkurt E(2022)The usage of cybernetic in complex software systems and its application to the deterministic multithreadingConcurrency and Computation: Practice and Experience10.1002/cpe.737534:28Online publication date: 31-Oct-2022
https://doi.org/10.1002/cpe.7375
Show More Cited By

Index Terms

nAdroid: statically detecting ordering violations in Android applications
1. Software and its engineering
  1. Software creation and management
    1. Software verification and validation
      1. Software defect analysis
        Software testing and debugging

Recommendations

Generating test cases to expose concurrency bugs in Android applications
ASE '16: Proceedings of the 31st IEEE/ACM International Conference on Automated Software Engineering

Mobile systems usually support an event-based model of concurrent programming. This model, although advantageous to maintain responsive user interfaces, may lead to subtle concurrency errors due to unforeseen threads interleaving coupled with non-...
Automatically Detecting Exception Handling Defects in Android Applications
Internetware '20: Proceedings of the 12th Asia-Pacific Symposium on Internetware

Developers often neglect to handle exceptions, which leads to exception handling defects that affect the robustness of applications or even cause crashes. To improve the robustness of android applications while reducing the development burden of ...
HybriDroid: static analysis framework for Android hybrid applications
ASE '16: Proceedings of the 31st IEEE/ACM International Conference on Automated Software Engineering

Mobile applications (apps) have long invaded the realm of desktop apps, and hybrid apps become a promising solution for supporting multiple mobile platforms. Providing both platform-specific functionalities via native code like native apps and user ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

CGO '18: Proceedings of the 2018 International Symposium on Code Generation and Optimization

February 2018

377 pages

ISBN:9781450356176

DOI:10.1145/3179541

General Chairs:
Jens Knoop
Vienna University of Technology, Austria
,
Markus Schordan
Lawrence Livermore National Laboratory, USA
,
Program Chairs:
Teresa Johnson
Google, USA
,
Michael O'Boyle
University of Edinburgh, UK

Copyright © 2018 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
SIGMICRO: ACM Special Interest Group on Microarchitectural Research and Processing
IEEE-CS: Computer Society

Publisher

Association for Computing Machinery

New York, NY, United States

Publication Notes

Badge change: Article originally badged under Version 1.0 guidelines https://www.acm.org/publications/policies/artifact-review-badging

Publication History

Published: 24 February 2018

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Badges

Author Tags

Qualifiers

Research-article

Funding Sources

Google Faculty Research Awards
National Science Foundation

Conference

CGO '18

Sponsor:

CGO '18: 16th Annual IEEE/ACM International Symposium on Code Generation and Optimization

February 24 - 28, 2018

Vienna, Austria

Acceptance Rates

Overall Acceptance Rate 312 of 1,061 submissions, 29%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

9
Total Citations
View Citations
532
Total Downloads

Downloads (Last 12 months)94
Downloads (Last 6 weeks)21

Reflects downloads up to 20 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Coppola RFulcini TArdito LTorchiano M(2025)Kotlin assimilating the Android ecosystem: An appraisal of diffusion and impact on maintainabilityJournal of Systems and Software10.1016/j.jss.2025.112346222(112346)Online publication date: Apr-2025
https://doi.org/10.1016/j.jss.2025.112346
Samhi JJust RBissyandé TErnst MKlein JChristakis MPradel M(2024)Call Graph Soundness in Android Static AnalysisProceedings of the 33rd ACM SIGSOFT International Symposium on Software Testing and Analysis10.1145/3650212.3680333(945-957)Online publication date: 11-Sep-2024
https://dl.acm.org/doi/10.1145/3650212.3680333
Bozkurt E(2022)The usage of cybernetic in complex software systems and its application to the deterministic multithreadingConcurrency and Computation: Practice and Experience10.1002/cpe.737534:28Online publication date: 31-Oct-2022
https://doi.org/10.1002/cpe.7375
Dong ZTiwari AYu XRoychoudhury ASpinellis DGousios GChechik MDi Penta M(2021)Flaky test detection in Android via event order explorationProceedings of the 29th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering10.1145/3468264.3468584(367-378)Online publication date: 20-Aug-2021
https://dl.acm.org/doi/10.1145/3468264.3468584
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
Salehnamadi NAlshayban AAhmed IMalek Sde Lara EMohomed INieh JBelding E(2020)A benchmark for event-race analysis in android appsProceedings of the 18th International Conference on Mobile Systems, Applications, and Services10.1145/3386901.3396602(466-467)Online publication date: 15-Jun-2020
https://dl.acm.org/doi/10.1145/3386901.3396602
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
Wu DHe DChen SXue J(2020)Exposing Android Event-Based Races by Selective Branch Instrumentation2020 IEEE 31st International Symposium on Software Reliability Engineering (ISSRE)10.1109/ISSRE5003.2020.00033(265-276)Online publication date: Oct-2020
https://doi.org/10.1109/ISSRE5003.2020.00033
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

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