Recovering Execution Data from Incomplete Observations

This research was conducted by Peter Ohmann, David Bingham Brown, Ben Liblit, and Thomas Reps. The paper appeared in the Thirteenth International Workshop on Dynamic Analysis (WODA 2015).


Due to resource constraints, tracing production applications often results in incomplete data. Nevertheless, developers ideally want answers to queries about the program's execution beyond data explicitly gathered. For example, a developer may ask whether a particular program statement executed during the run corresponding to a given failure report.

In this work, we investigate the problem of determining whether each statement in a program executed, did not execute, or may have executed, given a set of (possibly-incomplete) observations. Using two distinct formalisms, we propose two solutions to this problem. The first formulation represents observations as regular languages, and computes intersections over these languages using finite-state acceptors. The second formulation encodes the problem as a set of Boolean constraints, and uses answer set programming to solve the constraints.

Full Paper

The full paper is available as a single PDF document. A suggested BibTeX citation record is also available.