  In this paper, we propose a novel approach that aims to offer an alternative
to the prevalent paradigm to dynamic slicing construction. Dynamic slicing
requires dynamic data and control dependencies that arise in an execution.
During a single execution, memory reference information is recorded and then
traversed to extract dependencies. Execute-once approaches and tools are
challenged even by executions of moderate size of simple and short programs. We
propose to shift practical time complexity from execution size to slice size.
In particular, our approach executes the program multiple times while tracking
targeted information at each execution. We present a concrete algorithm that
follows an on-demand re-execution paradigm that uses a novel concept of
frontier dependency to incrementally build a dynamic slice. To focus dependency
tracking, the algorithm relies on static analysis. We show results of an
evaluation on the SV-COMP benchmark and Antrl4 unit tests that provide evidence
that on-demand re-execution can provide performance gains particularly when
slice size is small and execution size is large.
