Execution Indexing and Its Application in Debugging

Execution indexing (EI) [PLDI'08] is a dynamic analysis primitive that facilitates comparison across executions. These executions could be those induced by different inputs on the same program, those with the same inputs but different schedules, or even those induced by the same input on different program versions, depending on the scenarios. It canonicalizes the control flow of the executions and allows them to be properly aligned before comparison, to the precision level of individual executed instructions. This is particularly necessary in the presence of loops, recursions and control flow divergence. Note that the nth instance of an instruction in one run unlikely corresponds to that in the other run.

Aligning along the control flow dimension is not sufficient in many applications, we developed memory indexing (MI) [FSE'10] to align along the memory dimension. In particular, given a memory location in one run, it identifies the semantically corresponding memory location in the other run. Note that due to execution differences, different amounts of memory may be allocated, and the same object may be allocated in different locations in the two runs. MI tolerates such differences by canonicalizing memory addresses.

The two primitives give rise to new opportunities for many applications. In particular, it allows advance in automated debugging. In scenarios when both the failing execution and a reference execution (e.g. a passing run with a slightly different input) are available, effective automated debugging can be achieved by comparing the two runs to identify the failure causal path ([FSE'10] and [FASE'09]), which is the path leading from the root cause to the failure with each step causally connected. It is key to understanding and fixing the fault. EI and MI are leveraged to compare program states at aligned execution points. We reason about if a subset of state differences is critical to the failure by copying such differences from the failing run to the passing run and observing if such state mutation can induce the failure in the passing run. Robust state replacement can not be achieved without indexing. For instance, copying the absoluate value of a pointer variable from one run to the run is problematic.

Funding

	Automated Software Failure Causal Path Computation NSF-CCF-0917007, 2009-2012.
	NSF Career: Scalable Dynamic Program Reasoning NSF-CCF-0845870, 2008-2013.

A demo for the debugging technique

Students

• William N. Sumner
  
• Dasarath Weeratunge
• Yunhui Zheng
  
• Dohyeong Kim
  

Publications

Fundamentals

Applications