Semi-automated debugging via binary search through a process lifetime
Kapil Arya, Tyler Denniston, Ana-Maria Visan, Gene D. Cooperman · 2013
A common programmer experience is to execute a long-running computation only to see a bug crash the program after hours or days. While it is often easy to capture a "buggy" expression value at the point of the crash, it is less easy to discover the point in the program where the expression became buggy. For such "difficult" bugs, this work presents an automated tool based on binary search through a process lifetime. The tool operates both in single-threaded and multi-threaded program. The underlying algorithm depends on on checkpoints, deterministic replay, and decomposition of debugging histories. The tool is scalable in the sense that the running time is a small constant factor beyond the standalone running time. Further, it requires only a logarithmic number of probes of the expression value --- an advantage when the time to execute the expression is large. The algorithm is demonstrated for such real-world programs as MySQL.