论文标题
按需重新执行的动态切片
Dynamic Slicing by On-demand Re-execution
论文作者
论文摘要
在本文中，我们提出了一种新颖的方法，旨在为动态切片结构提供替代风格的范式。动态切片需要在执行中出现的动态数据和控制依赖性。在单个执行过程中，记录内存参考信息，然后遍历以提取依赖项。即使执行中等规模的简单和简短程序的执行方式，执行的方法和工具也受到挑战。我们建议将实际时间复杂性从执行尺寸转移到切片大小。特别是，我们的方法在每个执行下跟踪目标信息时多次执行程序。我们提出了一种混凝土算法，该算法遵循按需重新执行范式，该范式使用Frontier依赖性的新颖概念来逐步构建动态切片。为了集中依赖性跟踪，该算法依赖于静态分析。我们展示了对SV-Comp基准和ANTRL4单元测试的评估结果，该测试提供了证据表明按需重新执行可以提供性能提高，尤其是当切片尺寸较小并且执行尺寸较大时。
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.
