Efficient Program Execution Indexing

Efficient Program Execution Indexing
PLDI 2008, 18%=34/184

Update: If you have used execution indexing in the past, you will likely wish to look at the PEPID paper that resolves some of the efficiency and accuracy issues present in this original work.

Execution indexing uniquely identifies a point in an execution. Desirable execution indices reveal correlations between points in an execution and establish correspondence between points across multiple executions. Therefore, execution indexing is essential for a wide variety of dynamic program analyses, for example, it can be used to organize program profiles; it can precisely identify the point in a re-execution that corresponds to a given point in an original execution and thus facilitate debugging or dynamic instrumentation. In this paper, we formally define the concept of execution index and propose an indexing scheme based on execution structure and program state. We present a highly optimized online implementation of the technique. We also perform a client study, which targets producing a failure inducing schedule for a data race by verifying the two alternative happens-before orderings of a racing pair. Indexing is used to precisely locate corresponding points across multiple executions in the presence of non-determinism so that no heavyweight tracing/replay system is needed.

[doi] [pdf]
 author    = {Bin Xin and
              William N. Sumner and
              Xiangyu Zhang},
 title     = {Efficient program execution indexing},
 booktitle = {PLDI},
 year      = {2008},
 pages     = {238-248},
 ee        = {http://doi.acm.org/10.1145/1375581.1375611},
 crossref  = {DBLP:conf/pldi/2008},
 bibsource = {DBLP, http://dblp.uni-trier.de}