Computer technology is rapidly permeating all spheres of society.  A computer system that affects the lives of thousands or millions of people creates a massive community of users who have an interest in the correct behavior of that system.  Widespread network connectivity means that we now have the ability to tap this potential. The work supported by this grant explored how to harness the power of large user communities to diagnose a particularly pernicious class of computer defects: software concurrency bugs. These elusive bugs that arise when a computer system is performing multiple tasks simultaneously, and some of those tasks interfere with each other in destructive, unpredictable ways.

To address these problems, we developed Cooperative Crug Isolation (CCI), a low-overhead instrumentation framework to diagnose production-run failures caused by concurrency bugs (crugs). CCI tracks specific thread interleavings at run-time, and uses statistical models to identify strong failure predictors among these. We offer a varied suite of predicates that represent different trade-offs between complexity and fault isolation capability. We also developed variant random sampling strategies that suit different types of predicates and help keep the run-time overhead low. Experiments show that these schemes span a wide spectrum of performance and diagnosis capabilities, each suitable for different usage scenarios.

However, recognizing that a bug exists is only half of the battle. Someone still needs to fix the problem’s root cause. This debugging task is difficult in general; it is especially slow and error-prone for concurrency bugs. With NSF’s generous support, we created CFix, a system that automates the repair of concurrency bugs. CFix works with a wide variety of concurrency-bug detectors, including (but definitely not limited to) our own CCI system. For each failure-inducing interleaving reported by a bug detector, CFix first determines a combination of mutual-exclusion and order relationships that, once enforced, can prevent the buggy interleaving. CFix then uses static analysis and testing to determine where to insert what synchronization operations to force the desired mutual-exclusion and order relationships, with a best effort to avoid deadlocks and excessive performance losses. CFix also simplifies its own patches by merging fixes for related bugs. Evaluation using four different types of bug detectors and thirteen real-world concurrency-bug cases shows that CFix can successfully patch these cases without causing deadlocks or excessive performance degradation. Patches automatically generated by CFix are of similar quality to those manually written by developers. An award nomination for part of this work cited it as “one of the first papers to attack the problem of automated bug fixing” of any kind. Thus, this represents a major step forward not only for concurrent software but also for reliable computing in general.

Concurrency is the future: of this there is no doubt. Our ability to maintain software quality in that concurrent future is, however, very much in doubt. The work sponsored by this research grant represents several major steps forward toward safeguarding that future.

Last Modified: 05/26/2016
Modified by: Benjamin R Liblit