Towards Automated Debugging

Today, debugging and repairing software failures is an expensive, tedious and human-intensive task. Our research group is exploring ways to use the abundant computing power of today’s systems to simplify this task greatly. In our results to date, we have shown that we can narrow down the possible root causes of large software failures to just a few (e.g., 2-10) program locations, even in large programs, for a wide range of bugs. The algorithm is almost fully automatic, except for an input construction step that requires a small amount of manual effort per program. The algorithm uses dynamically observed likely invariants to identify candidate locations for the root causes, and then uses novel static and dynamic analyses to filter out false positives and to extract valuable information for understanding the failure. We are also able to extract valuable additional information for diagnosing a failure, including the fault propagation chain from each candidate root cause to the failure, several “passing” inputs that are very close in behavior to the failing input, and likely program invariants that capture the differences between passing and failing runs. We are now extending the approach to automate the input construction step more fully using concolic execution; to triage and analyze in-field faiures using information from production environments; and to diagnose application failures in data-center-scale Internet services.

The results on fault localization to date are from joint work with Swarup Sahoo. The ongoing project on automating input construction also includes Sean Bartell, Blake Bassett and Professor Tao Xie (all at the University of Illinois). The project on data-center-scale services includes, in addition, Bogdan Stoica and Professor Jim Larus at EPFL. This research has been supported primarily by the US National Science Foundation (NSF).

Vikram Adve is a Professor of Computer Science at the University of Illinois at Urbana-Champaign and is currently spending a sabbatical year as a Visiting Professor at EPFL. Adve’s current research focuses on Virtual Instruction Set Computing (VISC), in which his group is exploring the benefits that accrue if all software on a system were shipped in virtual instruction set form instead of native machine code. Some examples of such benefits include automated diagnosis of software failures; improving software portability for heterogeneous parallel systems; and novel performance optimization techniques in static languages. Adve and his student, Chris Lattner, co-developed the LLVM Compiler Infrastructure, which enables novel compilation capabilities for a wide range of languages. LLVM is widely used in production systems, ranging from consumer devices (MacOS, iOS and Android) to GPU computing (most implementations of OpenCL and CUDA) to supercomputers (Cray). Adve, Lattner and Evan Cheng received the ACM Software System Award in 2012 for co-developing LLVM. One of Adve’s Ph.D. students, Robert Bocchino, was honored with the ACM SIGPLAN Distinguished Dissertation Award and another, John Criwell, won Honorable Mentions for both the ACM SIGOPS Distinguished Dissertation Award and the ACM Doctoral Dissertation Award. Adve is a Fellow of the ACM.