This research was conducted by Akash Lal, Junghee Lim, Marina Polishchuk, and Ben Liblit.

We present and solve a path optimization problem on
programs. Given a set of program nodes, called critical nodes, we
find a shortest path through the program’s control flow graph that
touches the maximum number of these nodes. Control flow graphs
over-approximate real program behavior; by adding dataflow
analysis to the control flow graph, we narrow down on the
program’s actual behavior and discard paths deemed infeasible by
the dataflow analysis. We derive an efficient algorithm for path
optimization based on weighted pushdown systems. We present an
application for path optimization by integrating it with the Cooperative Bug Isolation
Project (*CBI*), a dynamic debugging system. CBI mines
instrumentation feedback data to find suspect program behaviors,
called bug predictors, that are strongly associated with program
failure. Instantiating critical nodes as the nodes containing bug
predictors, we solve for a shortest program path that touches
these predictors. This path can be used by a programmer to debug
his software. We present some early experience on using this
hybrid static/dynamic system for debugging.

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