Race detection for event-driven mobile applications

Abstract

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 existing tools for detecting concurrency errors of parallel programs focus on a thread-based model of concurrency. If one applies such tools directly to an event-based program, they work poorly because they infer false dependencies between unrelated events handled sequentially by the same thread.

In this paper we present a race detection tool named CAFA for event-driven mobile systems. CAFA uses the causality model that we have developed for the Android event-driven system. A novel contribution of our model is that it accounts for the causal order due to the event queues, which are not accounted for in past data race detectors. Detecting races based on low-level races between memory accesses leads to a large number of false positives. CAFA overcomes this problem by checking for races between high-level operations. We discuss our experience in using CAFA for finding and understanding a number of known and unknown harmful races in open-source Android applications.

References

1. Android Open Source Project. http://source.android.com/.
2. Dalvik Technical Information. http://source.android.com/devices/tech/dalvik/index.html.
3. List of free and open-source Android apllications. http://en.wikipedia.org/wiki/List_of_free_and_open-source_Android_applications.
4. F-Droid. https://f-droid.org.
5. Twitter Finagle. https://github.com/twitter/finagle.
6. Libprocess. http://www.eecs.berkeley.edu/~benh/libprocess/.
7. S. V. Adve and M. D. Hill. Weak ordering---a new definition. In Proceedings of the 17th Annual International Symposium on Computer Architecture, ISCA '90, pages 2--14, New York, NY, USA, 1990. ACM. ISBN 0-89791-366-3.. URL http://doi.acm.org/10.1145/325164.325100.
8. J. Armstrong, R. Virding, and M. Williams. Concurrent programming in ERLANG. Prentice Hall, 1993. ISBN 978-0-13-285792-5.
9. A. Desai, V. Gupta, E. K. Jackson, S. Qadeer, S. K. Rajamani, and D. Zufferey. P: safe asynchronous event-driven programming. In PLDI, pages 321--332, 2013.
10. D. R. Engler and K. Ashcraft. RacerX: Effective, Static Detection of Race Conditions and Deadlocks. In SOSP, pages 237--252, 2003.
11. C. Flanagan and S. N. Freund. FastTrack: Efficient and Precise Dynamic Race Detection. In PLDI, pages 121--133, 2009.
12. R. C. Huang, E. Halberg, and G. E. Suh. Non-race concurrency bug detection through order-sensitive critical sections. In ISCA, pages 655--666, 2013.
13. V. Kahlon and C. Wang. Universal Causality Graphs: A Precise Happens-Before Model for Detecting Bugs in Concurrent Programs. In CAV, pages 434--449, 2010.
14. L. Lamport. How to make a multiprocessor computer that correctly executes multiprocess programs. Computers, IEEE Transactions on, C-28(9):690--691, Sept 1979. ISSN 0018--9340..
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.
16. A. Pathak, Y. C. Hu, and M. Zhang. Bootstrapping energy debugging on smartphones: a first look at energy bugs in mobile devices. In HotNets, page 5, 2011.
17. A. Pathak, A. Jindal, Y. C. Hu, and S. P. Midkiff. What is keeping my phone awake?: characterizing and detecting no-sleep energy bugs in smartphone apps. In MobiSys, pages 267--280, 2012.
18. B. Petrov, M. T. Vechev, M. Sridharan, and J. Dolby. Race detection for web applications. In PLDI, pages 251--262, 2012.
19. L. Ravindranath, J. Padhye, S. Agarwal, R. Mahajan, I. Obermiller, and S. Shayandeh. Appinsight: mobile app performance monitoring in the wild. In OSDI, pages 107--120, 2012.
20. V. Raychev, M. T. Vechev, and M. Sridharan. Effective race detection for event-driven programs. In OOPSLA, pages 151--166, 2013.
21. Y. Smaragdakis, J. Evans, C. Sadowski, J. Yi, and C. Flanagan. Sound predictive race detection in polynomial time. In POPL, pages 387--400, 2012.
22. 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.
23. L. Zhang, D. R. Bild, R. P. Dick, Z. M. Mao, and P. A. Dinda. Panappticon: Event-based tracing to measure mobile application and platform performance. In CODES+ISSS, pages 1--10, 2013.
24. W. Zhang, J. Lim, R. Olichandran, J. Scherpelz, G. Jin, S. Lu, and T. W. Reps. ConSeq: Detecting Concurrency Bugs through Sequential Errors. In ASPLOS, pages 251--264, 2011.
25. W. Zhang, C. Sun, J. Lim, S. Lu, and T. W. Reps. Conmem: Detecting crash-triggering concurrency bugs through an effect-oriented approach. ACM Trans. Softw. Eng. Methodol., 22(2):10, 2013.

Index Terms

• General and reference

  • Cross-computing tools and techniques

    • Reliability

• Information systems

  • Data management systems

    • Middleware for databases

      • Distributed transaction monitors

• Software and its engineering

  • Software creation and management

    • Software verification and validation

      • Software defect analysis

        • Software testing and debugging

  • Software organization and properties

    • Contextual software domains

      • Operating systems

        • Process management

          • Monitors

    • Extra-functional properties

      • Software reliability

• Theory of computation

  • Logic

  • Semantics and reasoning

    • Program reasoning