Automatic Failure Inducing Chain Computation through Aligned Execution Comparison
William Nick Sumner, Xiangyu Zhang · Purdue e-Pubs (Purdue University System) · 2008
In this paper, we propose an automated debugging technique that explains a failure by computing its causal path leading from the root cause to the failure.Given a failing execution, the technique first searches for a dynamic patch.Fine-grained execution comparison between the failing run and the patched run is performed to isolate the causal path.We introduce a formal system, wherein the corrected version of a faulty program is assumed so that the concept of ideal failure inducing chain (FIC) can be defined by comparing the failing run and the run on the corrected program using the same input.Properties of such chains are studied.A product of the formal system is a metric that serves in the objective evaluation of the proposed technique.We identify a key enabling technique called execution indexing, whose goal is to establish a mapping between equivalent points in two different executions so that comparison can be meaningfully performed.We show that a control structure based indexing scheme, when integrated into the formal system, demonstrates very nice properties that can be exploited to develop an effective and efficient debugging algorithm.The evaluation shows that the metric lives up to its promise, computing desired FICs, and the proposed approach is able to compute high quality FICs.The results of our technique significantly supercede the state of the art.