Among all types of software bugs, concurrency bugs in multi-threaded parallel programs are especially troublesome. They widely exist and are becoming increasingly severe due to the pervasiveness of multi-core machines. Existing approaches to detecting concurrency bugs mostly struggle at the complicated cause of concurrency bugs --- non-deterministic interaction among multiple threads in concurrent programs.
This project aims to address the concurrency bug problem through an effect-oriented approach. Specifically, it will provide (1) a characteristic study and a deep understanding of the error propagation process of real-world concurrency bugs; (2) an effect-oriented bug detection and testing framework that can identify potential failures in a program and search for concurrency bugs leading to these failures through backward analysis; (3) a bug-fixing tool that leverages the error propagation information identified above and suggests patches to software developers; (4) a general effect-oriented philosophy that can guide other tools related to multi-threaded parallel programs. This research will improve our understanding of the dependability problem of concurrent software, provide substantial tool support to help lower software development and maintenance costs, and improve software users' everyday experience through faster and more reliable software on a wide spectrum of platforms.
With the pervasive use of multi-threaded software in the multi-core era, concurrency bugs (i.e., synchronization problems among multiple threads) are a huge threat to the availability and reliability of software systems everywhere. Unfortunately, due to the complicated root causes of concurrency bugs, previous techniques suffer from low accuracy in bug detection, high overhead in failure diagnosis and recovery, and provide no support for automated bug fixing. This project tackles the concurrency bug problem from a novel perspective --- the effect/error-propagation patterns of common real-world concurrency bugs. By understanding and leveraging the effect patterns, this project has made significant contributions to the state of the art in concurrency-bug detection, failure diagnosis, failure recovery, and fixing: - It designs effect-oriented detection tools that can automatically identify concurrency bugs with much higher accuracy than traditional tools and have found previously unknown concurrency bugs from real-world open-source software; - It provides low-overhead failure diagnosis tools that leverages hardware performance monitoring unit and cooperative failure diagnosis philosophy to help figure out the root causes of production-run failures with low run-time overhead; - It provides a featherweight effect-oriented failure recovery system that can automatically and transparently recover production-run software from concurrency-bug failures with non-perceivable run-time overhead on commodity systems; - It also pioneers automated bug fixing for one common type of concurrency bugs --- atomicity violations. The above techniques can help significantly improve the availability and reliability of multi-threaded software, and hence improve the daily experience of software users ---- with better bug detection tools, fewer bugs will escape to the field; with effective failure recovery, end users will rarely be bothered by the manifestation of concurrency bugs; with efficient failure diagnosis and automated bug fixing, the system down-town will be significantly reduced. The research results of this project have been disseminated through top-tier conference proceedings, research talks, benchmark dissemination, and others. Work from this project won ACM-SIGPLAN CACM Research Highlight Nomination. Tech-transfer for some of the techniques are under way. Two Ph.D. students, three master students, and three undergraduate students have gone through thorough training in this project and have graduated, becoming faculty member in academia, researcher in research lab, graduate students in top graduate programs, and software developer in software industry. Out-reach activities and teaching improvement based on this project are also conducted by the PI.
