Shan Lu
Soyeon Park
Yuanyuan Zhou
Abstract
The reality of multi-core hardware has made concurrent programs pervasive. Unfortunately, writing correct concurrent programs is difficult. Addressing this challenge requires advances in multiple directions, including concurrency bug detection, concurrent program testing, concurrent programming model design, etc. Designing effective techniques in all these directions will significantly benefit from a deep understanding of real world concurrency bug characteristics.
This paper provides the first (to the best of our knowledge) comprehensive real world concurrency bug characteristic study. Specifically, we have carefully examined concurrency bug patterns, manifestation, and fix strategies of 105 randomly selected real world concurrency bugs from 4 representative server and client open-source applications (MySQL, Apache, Mozilla and OpenOffice). Our study reveals several interesting findings and provides useful guidance for concurrency bug detection, testing, and concurrent programming language design.
Some of our findings are as follows: (1) Around one third of the examined non-deadlock concurrency bugs are caused by violation to programmers' order intentions, which may not be easily expressed via synchronization primitives like locks and transactional memories; (2) Around 34% of the examined non-deadlock concurrency bugs involve multiple variables, which are not well addressed by existing bug detection tools; (3) About 92% of the examined concurrency bugs canbe reliably triggered by enforcing certain orders among no more than 4 memory accesses. This indicates that testing concurrent programs can target at exploring possible orders among every small groups of memory accesses, instead of among all memory accesses; (4) About 73% of the examinednon-deadlock concurrency bugs were not fixed by simply adding or changing locks, and many of the fixes were not correct at the first try, indicating the difficulty of reasoning concurrent execution by programmers.
Supplemental Material
Available for Download
Slides from the presentation
Supplemental material for Learning from mistakes: a comprehensive study on real world concurrency bug characteristics
- A.-R. Adl-Tabatabai, C. Kozyrakis, and B. Saha. Transactional programming in a multi-core environment. In PPOPP, 2007. Google Scholar
Digital Library
- C. S. Ananian, K. Asanovic, B. C. Kuszmaul, C. E. Leiserson, and S. Lie. Unbounded transactional memory. In HPCA, 2005. Google ScholarDigital Library
- C. Boyapati, R. Lee, and M. Rinard. Ownership types for safe programming: Preventing data races and deadlocks. In OOPSLA, 2002. Google ScholarDigital Library
- A. Bron, E. Farchi, Y. Magid, Y. Nir, and S. Ur. Applications of synchronization coverage. In PPoPP, 2005. Google ScholarDigital Library
- B. D. Carlstrom, A. McDonald, H. Chafi, J. Chung, C. C. Minh, C. Kozyrakis, and K. Olukotun. The atomos transactional programming language. In PLDI '06, 2006. Google ScholarDigital Library
- S. Chandra and P. M. Chen. Whither generic recovery from application faults? a fault study using open-source software. In DSN, 2000. Google ScholarDigital Library
- J.-D. Choi et al. Efficient and precise datarace detection for multithreaded object-oriented programs. In PLDI, 2002. Google ScholarDigital Library
- A. Chou, J. Yang, B. Chelf, S. Hallem, and D. R. Engler. An empirical study of operating system errors. In SOSP, 2001. Google ScholarDigital Library
- O. Edelstein, E. Farchi, Y. Nir, G. Ratsaby, and S. Ur. Multi-threaded java program test generation. IBM Systems Journal, 2002. Google ScholarDigital Library
- D. Engler and K. Ashcraft. RacerX: Effective, static detection of race conditions and deadlocks. In SOSP, 2003. Google ScholarDigital Library
- E. Farchi, Y. Nir, and S. Ur. Concurrent bug patterns and how to test them. In IPDPS, 2003. Google ScholarDigital Library
- C. Flanagan and S. N. Freund. Atomizer: a dynamic atomicity checker for multithreaded programs. In POPL, 2004. Google ScholarDigital Library
- P. Godefroid. Model checking for programming languages using verisoft. In POPL, 1997. Google ScholarDigital Library
- W. Gu, Z. Kalbarczyk, R. K. Iyer, and Z. Yang. Characterization of linux kernel behavior under errors. In DSN, 2003.Google Scholar
- L. Hammond, V. Wong, M. Chen, B. D. Carlstrom, J. D. Davis, B. Hertzberg, M. K. Prabhu, H. Wijaya, C. Kozyrakis, and K. Olukotun. Transactional memory coherence and consistency. In ISCA, 2004. Google ScholarDigital Library
- T. Harris and K. Fraser. Language support for lightweight transactions. In OOPSLA, 2003. Google ScholarDigital Library
- T. Harris, S. Marlow, S. Peyton-Jones, and M. Herlihy. Composable memory transactions. In PPoPP '05, 2005. Google ScholarDigital Library
- R. Hastings and B. Joyce. Purify: Fast detection of memory leaks and access errors. In Usenix, 1992.Google Scholar
- Z. Li, S. Lu, S. Myagmar, and Y. Zhou. CP-Miner: A tool for finding copy-paste and related bugs in o perating system code. In OSDI, 2004. Google ScholarDigital Library
- Z. Li, L. Tan, X. Wang, S. Lu, Y. Zhou, and C. Zhai. Have things changed now?: an empirical study of bug characteristics in modern open source software. In Proceedings of the 1st workshop on Architectural and system support for improving software dependability (ASID'06), 2006. Google ScholarDigital Library
- S. Lu, W. Jiang, and Y. Zhou. A study of interleaving coverage criteria. In FSE, 2007. Google ScholarDigital Library
- S. Lu, S. Park, C. Hu, X. Ma, W. Jiang, Z. Li, R. A. Popa, and Y. Zhou. Muvi: Automatically inferring multi-variable access correlations and detecting related semantic and concurrency bugs. In SOSP07, 2007. Google ScholarDigital Library
- S. Lu, J. Tucek, F. Qin, and Y. Zhou. Avio: Detecting atomicity violations via access interleaving invariants. In ASPLOS, 2006. Google ScholarDigital Library
- B. McCloskey, F. Zhou, D. Gay, and E. Brewer. Autolocker: synchronization inference for atomic sections. In POPL, 2006. Google ScholarDigital Library
- M. Moir. Transparent support for wait-free transactions. In 11th International Workshop on Distributed Algorithms, 1997. Google ScholarDigital Library
- K. E. Moore, J. Bobba, M. J. Moravan, M. D. Hill, and D. A. Wood. Logtm: Log-based transactional memory. In HPCA, 2006.Google ScholarCross Ref
- J. E. B. Moss and A. L. Hosking. Nested transactional memory: model and architecture sketches. Sci. Comput. Program., 2006. Google ScholarDigital Library
- M. Musuvathi and S. Qadeer. Iterative context bounding for systematic testing of multithreaded programs. In PLDI, 2007. Google ScholarDigital Library
- G. C. Necula, S. McPeak, and W. Weimer. CCured: Type-safe retrofitting of legacy code. In POPL, 2002. Google ScholarDigital Library
- N. Nethercote and J. Seward. Valgrind: A program supervision framework. ENTCS, 2003.Google Scholar
- R. H. B. Netzer and B. P. Miller. Improving the accuracy of data race detection. In PPoPP, 1991. Google ScholarDigital Library
- T. Ostrand, E. Weyuker, and R. Bell. Predicting the location and number of faults in large software systems. TSE, 2005. Google ScholarDigital Library
- M. Prvulovic and J. Torrellas. ReEnact: Using thread-level speculation mechanisms to debug data races in multithreaded codes. In ISCA, 2003. Google ScholarDigital Library
- S. Qadeer and D. Wu. Kiss: keep it simple and sequential. In PLDI, 2004. Google ScholarDigital Library
- F. Qin, J. Tucek, J. Sundaresan, and Y. Zhou. Rx: Treating bugs as allergies c a safe method to survive software failures. In SOSP, 2005. Google ScholarDigital Library
- H. E. Ramadan, C. J. Rossbach, D. E. Porter, O. S. Hofmann, A. Bhandari, and E. Witchel. Metatm/txlinux: transactional memory for an operating system. In ISCA, 2007. Google ScholarDigital Library
- S. Savage, M. Burrows, G. Nelson, P. Sobalvarro, and T. Anderson. Eraser: A dynamic data race detector for multithreaded programs. ACM TOCS, 1997. Google ScholarDigital Library
- M. Sullivan and R. Chillarege. A comparison of software defects in database management systems and operating systems. In FTCS, 1992.Google ScholarCross Ref
- R. N. Taylor, D. L. Levine, and C. D. Kelly. Structural testing of concurrent programs. IEEE Trans. Softw. Eng., 1992. Google ScholarDigital Library
- M. Vaziri, F. Tip, and J. Dolby. Associating synchronization constraints with data in an object-oriented language. In POPL, 2006. Google ScholarDigital Library
- M. Xu, R. Bodík, and M. D. Hill. A serializability violation detector for shared-memory server programs. In PLDI, 2005. Google ScholarDigital Library
- Y. Yu, T. Rodeheffer, and W. Chen. Racetrack: Efficient detection of data race conditions via adaptive tracking. In SOSP, 2005. Google ScholarDigital Library
- Z. Li et. al. Have things changed now? - an empirical study of bug characteristics in modern open source software. In ASID workshop in ASPLOS, 2006. Google ScholarDigital Library
Index Terms
- Learning from mistakes: a comprehensive study on real world concurrency bug characteristics
Recommendations
Learning from mistakes: a comprehensive study on real world concurrency bug characteristics
ASPLOS XIII: Proceedings of the 13th international conference on Architectural support for programming languages and operating systemsThe reality of multi-core hardware has made concurrent programs pervasive. Unfortunately, writing correct concurrent programs is difficult. Addressing this challenge requires advances in multiple directions, including concurrency bug detection, ...
AVIO: detecting atomicity violations via access interleaving invariants
Proceedings of the 2006 ASPLOS ConferenceConcurrency bugs are among the most difficult to test and diagnose of all software bugs. The multicore technology trend worsens this problem. Most previous concurrency bug detection work focuses on one bug subclass, data races, and neglects many other ...
Learning from mistakes: a comprehensive study on real world concurrency bug characteristics
ASPLOS '08The reality of multi-core hardware has made concurrent programs pervasive. Unfortunately, writing correct concurrent programs is difficult. Addressing this challenge requires advances in multiple directions, including concurrency bug detection, ...
Comments