Synthesizing racy tests

Abstract

Subtle concurrency errors in multithreaded libraries that arise because of incorrect or inadequate synchronization are often difficult to pinpoint precisely using only static techniques. On the other hand, the effectiveness of dynamic race detectors is critically dependent on multithreaded test suites whose execution can be used to identify and trigger races. Usually, such multithreaded tests need to invoke a specific combination of methods with objects involved in the invocations being shared appropriately to expose a race. Without a priori knowledge of the race, construction of such tests can be challenging. In this paper, we present a lightweight and scalable technique for synthesizing precisely these kinds of tests. Given a multithreaded library and a sequential test suite, we describe a fully automated analysis that examines sequential execution traces, and produces as its output a concurrent client program that drives shared objects via library method calls to states conducive for triggering a race. Experimental results on a variety of well-tested Java libraries yield 101 synthesized multithreaded tests in less than four minutes. Analyzing the execution of these tests using an off-the-shelf race detector reveals 187 harmful races, including several previously unreported ones. Our implementation, named NARADA, and the results of our experiments are available at http://www.csa.iisc.ernet.in/~sss/tools/narada.

References

1. D. F. Bacon, R. E. Strom, and A. Tarafdar. Guava: A dialect of Java without data races. In Proceedings of the 15th ACM SIGPLAN Conference on Object-oriented Programming, Systems, Languages, and Applications, OOPSLA ’00, pages 382–400, 2000.
2. E. Bodden and K. Havelund. Aspect-oriented race detection in Java. IEEE Transactions on Software Engineering, 36(4):509–527, 2010.
3. S. Burckhardt, P. Kothari, M. Musuvathi, and S. Nagarakatte. A randomized scheduler with probabilistic guarantees of finding bugs. In Proceedings of the Fifteenth Edition of ASPLOS on Architectural Support for Programming Languages and Operating Systems, ASPLOS XV, pages 167–178, 2010.
4. C. Cadar, D. Dunbar, and D. Engler. Klee: Unassisted and automatic generation of high-coverage tests for complex systems programs. In Proceedings of the 8th USENIX Conference on Operating Systems Design and Implementation, OSDI’08, pages 209–224, 2008.
5. D. Engler and K. Ashcraft. RacerX: Effective, static detection of race conditions and deadlocks. In Proceedings of the ACM Symposium on Operating Systems Principles (SOSP), pages 237–252, 2003.
6. M. Eslamimehr and J. Palsberg. Race directed scheduling of concurrent programs. In Proceedings of the 19th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPoPP ’14, pages 301–314, 2014.
7. C. Flanagan and S. N. Freund. Fasttrack: Efficient and precise dynamic race detection. In Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI ’09, pages 121–133, 2009.
8. P. Godefroid, N. Klarlund, and K. Sen. Dart: Directed automated random testing. In Proceedings of the 2005 ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI ’05, pages 213–223, 2005.
9. V. Jagannath, M. Gligoric, D. Jin, Q. Luo, G. Rosu, and D. Marinov. Improved multithreaded unit testing. In Proceedings of the 19th ACM SIGSOFT Symposium and the European Conference on Foundations of Software Engineering, ESEC/FSE ’11, pages 223–233, 2011.
10. G. Jin, W. Zhang, D. Deng, B. Liblit, and S. Lu. Automated concurrency-bug fixing. In Proceedings of the 10th USENIX Conference on Operating Systems Design and Implementation, OSDI’12, pages 389–400, 2012.
11. P. Joshi, C.-S. Park, K. Sen, and M. Naik. A randomized dynamic program analysis technique for detecting real deadlocks. In Proceedings of the 2009 ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI ’09, pages 110–120, 2009.
12. S. McPeak, C.-H. Gros, and M. K. Ramanathan. Scalable and incremental software bug detection. In Proceedings of the ACM SIGSOFT Symposium on Foundations of Software Engineering, ESEC/FSE 2013, pages 554–564, 2013.
13. M. Musuvathi and S. Qadeer. Iterative context bounding for systematic testing of multithreaded programs. In Proceedings of the 2007 ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI ’07, pages 446–455, 2007.
14. S. Nagarakatte, S. Burckhardt, M. M. Martin, and M. Musuvathi. Multicore acceleration of priority-based schedulers for concurrency bug detection. In Proceedings of the 33rd ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI ’12, pages 543–554, 2012.
15. M. Naik, A. Aiken, and J. Whaley. Effective static race detection for Java. In Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI), 2006.
16. C. Pacheco, S. K. Lahiri, M. D. Ernst, and T. Ball. Feedback-directed random test generation. In Proceedings of the 29th International Conference on Software Engineering, ICSE ’07, pages 75–84, 2007.
17. D. Perelman, S. Gulwani, D. Grossman, and P. Provost. Test-driven synthesis. In Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI), 2014.
18. B. Petrov, M. Vechev, M. Sridharan, and J. Dolby. Race detection for web applications. In Proceedings of the 33rd ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI ’12, pages 251–262, 2012.
19. E. Pozniansky and A. Schuster. Efficient on-the-fly data race detection in multithreaded C++ programs. In Proceedings of the Ninth ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPoPP ’03, pages 179–190, 2003.
20. M. Pradel and T. R. Gross. Fully automatic and precise detection of thread safety violations. In Proceedings of the 33rd ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI ’12, pages 521–530, 2012.
21. P. Pratikakis, J. S. Foster, and M. Hicks. Locksmith: Context-sensitive correlation analysis for race detection. In Proceedings of the 2006 ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI ’06, pages 320–331, 2006.
22. M. Samak and M. K. Ramanathan. Multithreaded test synthesis for deadlock detection. In Proceedings of the 2014 ACM International Conference on Object Oriented Programming Systems Languages and Applications, OOPSLA ’14, pages 473–489, 2014.
23. M. Samak and M. K. Ramanathan. Trace driven dynamic deadlock detection and reproduction. In Proceedings of the 2014 ACM SIGPLAN Conference on Principles and Practices of Parallel Programming, PPoPP ’14, pages 29–42, 2014.
24. S. Savage, M. Burrows, G. Nelson, P. Sobalvarro, and T. Anderson. Eraser: a dynamic data race detector for multithreaded programs. ACM Trans. Comput. Syst., 15(4):391–411, Nov. 1997.
25. K. Sen. Race directed random testing of concurrent programs. In Proceedings of the 2008 ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI ’08, pages 11–21, 2008.
26. Y. Smaragdakis, J. Evans, C. Sadowski, J. Yi, and C. Flanagan. Sound predictive race detection in polynomial time. In Proceedings of the 39th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL ’12, pages 387–400, 2012.
27. R. Surendran, R. Raman, S. Chaudhuri, J. Mellor-Crummey, and V. Sarkar. Test-driven repair of data races in structured parallel programs. In Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI), 2014.
28. R. Vallee-Rai, E. Gagnon, L. Hendren, P. Lam, P. Pominville, and V. Sundaresan. Optimizing java bytecode using the soot framework: Is it feasible? In In International Conference on Compiler Construction, LNCS 1781, pages 18–34, 2000.
29. B. Xin, W. N. Sumner, and X. Zhang. Efficient program execution indexing. In Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI), 2008.
30. J. Yu, S. Narayanasamy, C. Pereira, and G. Pokam. Maple: A coverage-driven testing tool for multithreaded programs. In Proceedings of the ACM Conference on Object Oriented Programming Systems Languages and Applications (OOPSLA), pages 485–502, 2012.

Index Terms

• Software and its engineering

  • Software creation and management

    • Software verification and validation

      • Software defect analysis

        • Software testing and debugging

• Theory of computation

  • Semantics and reasoning

    • Program semantics