Memory Indexing: Canonicalizing Addresses Across Executions

Memory Indexing: Canonicalizing Addresses Across Executions
FSE 2010, 20%=34/169

Fine-grained program execution comparison examines different executions generated by different program versions, different inputs, or by perturbations. It has a wide range of applications in debugging, regression testing, program comprehension, and security. Meaningful comparison demands that executions are aligned before they are compared, otherwise the resulting differences do not reflect semantic differences. Prior work has focused on aligning executions along the control flow dimension. In this paper, we observe that the memory dimension is also critical and propose a novel solution to align memory locations across different executions. We introduce a canonical representation for memory locations and pointer values called memory indexing. Aligned memory locations across runs share the same index. We formally define the semantics of memory indexing and present a cost-effective design. We also show that memory indexing overcomes an important challenge in automated debugging by enabling robust state replacement across runs.

[doi] [pdf]
 author    = {William N. Sumner and
              Xiangyu Zhang},
 title     = {Memory indexing: canonicalizing addresses across executions},
 booktitle = {SIGSOFT FSE},
 year      = {2010},
 pages     = {217-226},
 ee        = {},
 crossref  = {DBLP:conf/sigsoft/2010},
 bibsource = {DBLP,}