DARWIN: An Approach for Debugging Evolving Programs

Dawei Qi, Abhik Roychoudhury, Zhengkai Liang, and Kapil Vaswani

Abstract

Bugs in programs are often introduced when programs evolve from a stable version to a new version. In this paper, we propose an new approach called Darwin for automatically finding potential root causes of such bugs. Given two programs, a reference program and a modified program, and an input that fails on the modifed program, our approach uses symbolic execution to automatically synthesize a new input that (a) is very similar to the failing input, and (b) does not fail. We find the potential cause(s) of failure by comparing control flow behavior of the passing and failing inputs and identifying code fragments where the control flow diverge.

A notable feature of our approach is that it handles hard-to-explain bugs like code missing errors by pointing to code in the reference program. We have implemented this approach and conducted experiments using several real world applications such as the Apache web server, libPNG (a library for manipulating PNG images), and TCP flow (a program for displaying data sent through TCP connections). In each of these applications, Darwin was able to localize bugs with high accuracy. Even these applications contain several thousands lines of code, Darwin could usually narrow down the potential root causes to less than 10 lines. In addition, we find that the inputs synthesized by Darwin provide additional value by revealing other undiscovered errors or suggesting fixes to buggy inputs.

Details

Publication typeInproceedings
Published inACM Transactions on Software Engineering and Methodology (TOSEM)
PublisherACM

Previous versions

Kapil Vaswani and Abhik Rouchoudhury. Darwin - An Approach for Debugging Evolving Programs, Microsoft, 25 December 2008.

Dawei Qu, Abhik Roychoudhury, Zengkai Lang, and Kapil Vaswani. Darwin: An Approach for Debugging Evolving Programs, Association for Computing Machinery, Inc., September 2009.

> Publications > DARWIN: An Approach for Debugging Evolving Programs