Guoliang Jin
Linhai Song
Shan Lu
Ben Liblit
Abstract
Fixing software bugs has always been an important and time-consuming process in software development. Fixing concurrency bugs has become especially critical in the multicore era. However, fixing concurrency bugs is challenging, in part due to non-deterministic failures and tricky parallel reasoning. Beyond correctly fixing the original problem in the software, a good patch should also avoid introducing new bugs, degrading performance unnecessarily, or damaging software readability. Existing tools cannot automate the whole fixing process and provide good-quality patches.
We present AFix, a tool that automates the whole process of fixing one common type of concurrency bug: single-variable atomicity violations. AFix starts from the bug reports of existing bug-detection tools. It augments these with static analysis to construct a suitable patch for each bug report. It further tries to combine the patches of multiple bugs for better performance and code readability. Finally, AFix's run-time component provides testing customized for each patch. Our evaluation shows that patches automatically generated by AFix correctly eliminate six out of eight real-world bugs and significantly decrease the failure probability in the other two cases. AFix patches never introduce new bugs and usually have similar performance to manually-designed patches.
- A. Aviram, S.-C. Weng, S. Hu, and B. Ford. Efficient system-enforced deterministic parallelism. In OSDI, 2010. Google Scholar
Digital Library
- T. Bergan, N. Hunt, L. Ceze, and S. D. Gribble. Deterministic process groups in dOS. In OSDI, 2010. Google ScholarDigital Library
- E. D. Berger, T. Yang, T. Liu, and G. Novark. Grace: safe multithreaded programming for C/C. In OOPSLA, 2009. Google ScholarDigital Library
- M. D. Bond, K. E. Coons, and K. S. McKinley. Pacer: Proportional detection of data races. In PLDI, 2010. Google ScholarDigital Library
- L. Chew and D. Lie. Kivati: fast detection and prevention of atomicity violations. In EuroSys, 2010. Google ScholarDigital Library
- J.-D. Choi, K. Lee, A. Loginov, R. O'Callahan, V. Sarkar, and M. Sridharan. Efficient and precise datarace detection for multithreaded object-oriented programs. In PLDI, 2002. Google ScholarDigital Library
- C. Cowan, H. Hinton, C. Pu, and J. Walpole. The cracker patch choice: An analysis of post hoc security techniques. In In Proceedings of the National Information Systems Security Conference (NISSC), 2000.Google Scholar
- J. Deshmukh, G. Ramalingam, V. P. Ranganath, and K. Vaswani. Logical concurrency control from sequential proofs. In European Symposium on Programming, 2010. Google ScholarDigital Library
- C. Flanagan and S. N. Freund. Atomizer: a dynamic atomicity checker for multithreaded programs. In POPL, 2004. Google ScholarDigital Library
- C. Flanagan and S. N. Freund. FastTrack: efficient and precise dynamic race detection. In PLDI, 2009. Google ScholarDigital Library
- M. Harman. Automated patching techniques: the fix is in: technical perspective. Commun. ACM, 53 (5): 108--108, 2010. ISSN 0001-0782. http://doi.acm.org/10.1145/1735223.1735248. Google ScholarDigital Library
- G. Jin, A. Thakur, B. Liblit, and S. Lu. Instrumentation and sampling strategies for Cooperative Concurrency Bug Isolation. In OOPSLA, 2010. Google ScholarDigital Library
- H. Jula, D. Tralamazza, C. Zamfir, and G. Candea. Deadlock immunity: Enabling systems to defend against deadlocks. In OSDI, 2008. Google ScholarDigital Library
- E. Kandrot and B. Eich. Our JavaScript is 3x slower than IE's, Sept. 2000. URL https://bugzilla.mozilla.org/show_bug.cgi?id=54743.Google Scholar
- B. Krebs. A time to patch II: Mozilla. The Washington Post Security Fix blog, http://voices.washingtonpost.com/securityfix/2006/02/a_time_to_patch_ii_mozilla.html.Google Scholar
- B. Krena, Z. Letko, R. Tzoref, S. Ur, and T. Vojnar. Healing data races on-the-fly. In PADTAD, 2007. Google ScholarDigital Library
- C. Lattner and V. Adve. LLVM: A compilation framework for lifelong program analysis & transformation. In CGO, 2004. Google ScholarDigital Library
- Z. Letko, T. Vojnar, and B. Křena. AtomRace: data race and atomicity violation detector and healer. In PADTAD, 2008. 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
- S. Lu, S. Park, E. Seo, and Y. Zhou. Learning from mistakes -- a comprehensive study of real world concurrency bug characteristics. In ASPLOS, Mar. 2008. Google ScholarDigital Library
- B. Lucia, J. Devietti, L. Ceze, and K. Strauss. Atom-Aid: Detecting and surviving atomicity violations. IEEE Micro, 29 (1), 2009. Google ScholarDigital Library
- C.-K. Luk, R. Cohn, R. Muth, H. Patil, A. Klauser, G. Lowney, S. Wallace, V. J. Reddi, and K. Hazelwood. Pin: building customized program analysis tools with dynamic instrumentation. In PLDI, 2005. Google ScholarDigital Library
- B. McCloskey, F. Zhou, D. Gay, and E. Brewer. Autolocker: synchronization inference for atomic sections. In POPL, 2006. Google ScholarDigital Library
- Microsoft. Revamping the microsoft security bulletin release process, Feb. 2005. URL http://www.microsoft.com/technet/security/bulletin/revsbwp.mspx.Google Scholar
- S. Park, S. Lu, and Y. Zhou. CTrigger: exposing atomicity violation bugs from their hiding places. In ASPLOS, 2009. Google ScholarDigital Library
- S. Park, R. W. Vuduc, and M. J. Harrold. Falcon: fault localization in concurrent programs. In ICSE, 2010. Google ScholarDigital Library
- R. Pegoraro. Apple updates Leopard--again. Washington Post, Feb. 2008.Google Scholar
- J. H. Perkins, S. Kim, S. Larsen, S. P. Amarasinghe, J. Bachrach, M. Carbin, C. Pacheco, F. Sherwood, S. Sidiroglou, G. Sullivan, W.-F. Wong, Y. Zibin, M. D. Ernst, and M. C. Rinard. Automatically patching errors in deployed software. In SOSP, 2009. Google ScholarDigital Library
- K. Poulsen. Software bug contributed to blackout. SecurityFocus, Feb. 2004. URL http://www.securityfocus.com/news/8016.Google Scholar
- P. Ratanaworabhan, M. Burtscher, D. Kirovski, B. Zorn, R. Nagpal, and K. Pattabiraman. Detecting and tolerating asymmetric races. In PPoPP, 2009. Google ScholarDigital Library
- E. Rescorla. Security holes ... who cares? In USENIX Security Conference, 2003. Google ScholarDigital Library
- S. Savage, M. Burrows, G. Nelson, P. Sobalvarro, and T. Anderson. Eraser: A dynamic data race detector for multithreaded programs. ACM Transactions on Computer Systems, 15, 1997. Google ScholarDigital Library
- S. Sidiroglou, S. Ioannidis, and A. D. Keromytis. Band-aid patching. In HotDep, 2007. Google ScholarDigital Library
- A. Solar-Lezama, C. G. Jones, and R. Bodik. Sketching concurrent data structures. In PLDI, 2008. Google ScholarDigital Library
- C. Tian, V. Nagarajan, R. Gupta, and S. Tallam. Dynamic recognition of synchronization operations for improved data race detection. In ISSTA, 2008. Google ScholarDigital Library
- G. Upadhyaya, S. P. Midkiff, and V. S. Pai. Automatic atomic region identification in shared memory spmd programs. In OOPSLA, 2010. 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. T. Vechev, E. Yahav, and G. Yorsh. Abstraction-guided synthesis of synchronization. In POPL, 2010. Google ScholarDigital Library
- D. Weeratunge, X. Zhang, and S. Jagannathan. Analyzing multicore dumps to facilitate concurrency bug reproduction. In ASPLOS, 2010. Google ScholarDigital Library
- J. Wu, H. Cui, and J. Yang. Bypassing races in live applications with execution filters. In OSDI, 2010. Google ScholarDigital Library
- W. Xiong, S. Park, J. Zhang, Y. Zhou, and Z. Ma. Ad hoc synchronization considered harmful. In OSDI, 2010. Google ScholarDigital Library
- C. Zamfir and G. Candea. Execution synthesis: A technique for automated software debugging. In EuroSys, 2010. Google ScholarDigital Library
Index Terms
- Automated atomicity-violation fixing
Recommendations
Automated atomicity-violation fixing
PLDI '11: Proceedings of the 32nd ACM SIGPLAN Conference on Programming Language Design and ImplementationFixing software bugs has always been an important and time-consuming process in software development. Fixing concurrency bugs has become especially critical in the multicore era. However, fixing concurrency bugs is challenging, in part due to non-...
Finding Atomicity-Violation Bugs through Unserializable Interleaving Testing
Multicore hardware is making concurrent programs pervasive. Unfortunately, concurrent programs are prone to bugs. Among different types of concurrency bugs, atomicity violations are common and important. How to test the interleaving space and expose ...
Adaptively generating high quality fixes for atomicity violations
ESEC/FSE 2017: Proceedings of the 2017 11th Joint Meeting on Foundations of Software EngineeringIt is difficult to fix atomicity violations correctly. Existing gate lock algorithm (GLA) simply inserts gate locks to serialize exe-cutions, which may introduce performance bugs and deadlocks. Synthesized context-aware gate locks (by Grail) require ...
Comments