REPT: Reverse Debugging of Failures in Deployed Software

分析数据流和执行控制流
使用英特尔的硬件追踪每一条指令的数据
数据前推和后退结合，直到值收敛

摘要

调试已部署系统中的软件故障非常重要，因为它们会影响到真正的用户和客户。然而，调试这类故障在实践中是出了名的困难，因为开发人员不得不依赖内存转储等有限的信息。由于部署系统无法提供高保真的程序跟踪，因此通常无法获得执行历史记录。

在本文中，我们介绍了一个实用的系统 REPT，它能对已部署系统中的软件故障进行反向调试。REPT 通过将程序控制流的在线轻量级硬件跟踪与恢复数据流的离线二进制分析相结合，高保真地重建了执行历史。由于信息丢失和并发执行，要恢复故障前数千条指令的数据值似乎是不可能的。REPT 可根据硬件记录的时间戳构建部分执行顺序，并通过纠错迭代执行正向和反向执行，从而应对这些挑战。

我们设计并实现了 REPT，将其部署在 Microsoft Windows 上，并将其集成到 WinDbg 中。我们在 16 个实际错误上对 REPT 进行了评估，结果表明它能准确（平均 92%）、高效（20 秒内）地恢复这些错误的数据值。我们还证明它能对 14 个错误进行有效的反向调试。

引言

已部署系统中的软件故障是不可避免的，调试这类故障至关重要，因为它们会影响到真正的用户和客户。众所周知，执行日志有助于调试[28]，但没有人愿意为始终在线的日志记录/跟踪支付高昂的性能开销，因为正常运行时大多数日志或跟踪都会被丢弃。因此，只有在部署的软件出现故障时才会捕获内存转储，以便进行事后诊断。

唉，由于信息有限，开发人员调试内存转储很有难度。其结果是，有相当一部分错误没有得到修复[32,59]。在某些情况下，得到修复的错误可能需要数周时间[32]。

更糟糕的是，简化的软件流程要求较短的发布周期[53]，这限制了软件发布前的内部测试范围。频繁的发布增加了对已部署软件所报告的调试故障的依赖，因为这些故障的发生已成为检测某些错误的唯一方法。频繁的发布也增加了对快速解决错误的需求，以满足较短的发布期限。

关于调试失败的文献非常丰富，大致可分为两类：

自动根源诊断 [16, 37-41, 61] 试图自动确定导致程序失败的罪魁祸首语句。由于各种限制（例如，需要修改代码 [37、40、41]，无法有效处理复杂软件 [37、61]，或仅限于故障子集 [37、39]），这些系统都没有在实践中部署。此外，尽管根本原因诊断可以帮助开发人员确定故障背后的原因，但开发人员往往需要更深入地了解导致故障的条件和状态，才能修复错误，而这些系统却无法提供这些信息。
用于调试的故障再现试图使开发人员能够检查导致故障的程序输入和状态。符号执行[22]和模型检查[21, 58]等详尽测试技术或状态空间探索[51]可用于确定导致故障的输入和状态，以便进行调试。遗憾的是，这些技术需要重量级的运行时监控[26]。另一种重现故障的流行技术是记录/重放系统[46, 48, 50, 52, 56]，该系统记录程序执行，随后可以重放以调试故障。这也被称为反向调试 [31, 55] 或时间旅行调试 [44]。从好的方面看，反向调试允许开发人员在失败的执行过程中来回检查程序的状态（即控制流和数据流），从而真正理解错误并设计修复方案。另一方面，在多核运行的多线程程序中，记录/重放系统会产生令人望而却步的开销（最先进系统的开销高达 200%[56]），因此在部署系统中使用这些系统是不切实际的。

由于现有技术的局限性，包括苹果（Apple）[17]、谷歌（Google）[33]和微软（Microsoft）[30]在内的主要软件厂商以及 Ubuntu[54] 等开源系统都提供错误报告服务，以收集已部署软件的故障数据并进行分析。据我们所知，即使是在生产中部署的最先进的错误诊断系统，即 RETracer [27]，也只能分流由违规访问造成的故障。

为了解决调试已部署系统中软件故障的难题，我们认为需要一种实用的解决方案来反向调试此类故障。要做到切实可行，该解决方案必须：(1) 在已部署系统上运行时，运行时性能开销极低；(2) 能够准确高效地恢复执行历史；(3) 可使用未修改的源代码/二进制文件；(4) 适用于多种类型的错误（如并发错误）。

在本文中，我们将介绍 REPT1，一种用于反向调试已部署系统中软件故障的实用解决方案。REPT 背后有两个关键理念。首先，REPT 利用硬件跟踪技术，以较低的性能开销记录程序的控制流。其次，REPT 利用新颖的二进制分析技术，根据记录的控制流信息和内存转储中保存的数据值恢复数据流信息。因此，REPT 可以结合记录的控制流和恢复的数据流进行反向调试。

REPT 面临的主要挑战是如何根据记录的控制流和内存转储中保存的数据值，准确、高效地恢复数据值。要做到准确，REPT 必须能够正确恢复执行历史中的大部分数据值。为了提高效率，REPT 必须降低运行时监控开销，并在几分钟内完成分析。为解决这一难题，我们引入了一种新的二进制分析方法，该方法结合前向执行和后向执行来迭代模拟指令并恢复数据值。REPT 采用以下两种新技术进行分析：

首先，我们设计了一种纠错方案，用于检测和纠正向未知地址写入内存时产生的值冲突。在模拟内存写入指令时，如果目标地址未知，则将所有内存值标记为未知，这种做法过于保守。相反，REPT 不会触及内存，而是依靠检测目标内存中的陈旧值所导致的冲突。与以往使用昂贵的假设检验来决定内存别名的解决方案不同 [57]，纠错方案使 REPT 能够高效地运行迭代分析。

其次，我们利用现代硬件提供的定时信息来确定非确定性事件的顺序，例如跨多个线程的竞赛。长期以来，非确定性一直是阻碍现有记录/重放系统以低开销实现高准确性的难题。REPT 可以利用现代硬件提供的细粒度时间戳，在大多数情况下识别同一内存位置的访问顺序。当定时信息不足时，REPT 会限制使用无法推断顺序的内存访问。这样，它们的值就不会对其他数据的恢复产生负面影响。

我们通过两个组件实现 REPT。在线跟踪组件是一个控制 Intel Processor Trace (PT) [36] 的驱动程序，已作为 Microsoft Windows 的一部分部署在数亿台机器上。离线二进制分析组件是一个集成到 WinDbg [45] 中的可加载库。我们还增强了 Windows 错误报告 (WER) 服务 [30]，以控制已部署系统上的硬件跟踪。

为了衡量 REPT 的有效性和效率，我们对 Chrome、Apache、PHP 和 Python 等软件中的 16 个实际错误进行了评估。我们的实验表明，REPT 可以对其中 14 个错误（包括 2 个并发错误）进行有效的反向调试。我们通过将 REPT 恢复的数据值与时间旅行调试（TTD）[44] 记录的数据值进行比较，来评估 REPT 的数据恢复准确性，时间旅行调试是一种缓慢但精确的记录/重放工具。我们的实验表明，REPT 的平均准确率可达 92%，并能在 20 秒内完成对这些错误的分析。

概述

问题陈述

REPT 的总体目标是以较低的运行时开销反向调试已部署软件中的故障。REPT 分两步实现反向调试。(1) REPT 利用硬件支持记录程序执行的控制流和时序信息。当故障发生时，REPT 会保存一个丰富的内存转储，其中包括最终的程序状态以及故障发生前额外记录的控制流和时序信息。(2) REPT 使用一种新的离线二进制分析技术，根据丰富的内存转储恢复执行历史中的数据值。

REPT 需要恢复数据值，因为目前还没有有效记录程序执行过程中所有数据值的硬件支持。不过，英特尔 PT [36] 和 ARM Embedded Trace Macrocell [18] 等硬件功能可以有效记录控制流和时序信息。

设计选择

在设计 REPT 时，我们做出了三种设计选择。

仅内存转储与在线数据捕获：我们选择只依赖内存转储中的数据，而不是在执行过程中记录更多数据，以尽量减少部署系统的性能开销。此外，要进行在线数据捕获，我们需要修改操作系统或程序，因为现有硬件不支持这样做。我们选择不这样做，以尽量减少干扰。

二进制与源代码：我们选择在二进制级别而非源代码级别进行分析，原因有三。首先，通过在指令级执行分析，REPT 基本上与编程语言和编译器无关。这使得 REPT 既能支持本地语言（如 C/C++），也能支持托管语言（如 C#）。其次，当今的应用程序通常由来自不同供应商的多个模块/库组成，并非所有源代码都可用于分析[25]。第三，由于编译器的优化和临时变量的使用，源代码和二进制指令之间的映射并不直接，因此将源代码级的分析结果转换回二进制级是一个不小的挑战。

具体执行与符号执行：重建执行的一种流行方法是符号执行。在符号执行中，执行程序时输入的是不受约束的符号值（例如，布尔值最初可以取真或假中的任意值），而不是具体值。随着程序的执行，符号执行会收集符号值的约束条件。每当发生感兴趣的事件（如失败）时，符号执行就会使用约束求解器来确定会导致失败的程序输入。从概念上讲，符号执行可能有助于恢复数据值。我们可以将操作数（如每条指令引用的寄存器和内存位置）视为变量，并根据指令的语义在这些变量之间生成约束。但是，如果执行跟踪较长，收集到的变量约束可能会过于庞大（特别是当内存位置被符号化时），即使是最先进的约束求解器也无法在合理的时间内求解。因此，我们选择具体执行而不是符号执行。REPT 在指令序列的每个位置保留寄存器和内存位置的具体值，并分析每条指令以恢复其操作数的具体值。

挑战

为了实现反向调试，REPT 在恢复执行历史中的寄存器和内存值时面临三个挑战。

不可扭转的指令

REPT 面临的第一个挑战是处理不可逆指令。如果每条指令都是可逆的（即根据指令执行后的程序状态，可以完全确定指令执行前的程序状态），那么 REPT 的设计将非常简单：反转每条指令的语义，恢复指令序列中每个位置的数据值。然而，许多指令是不可逆的（如 xor rax,rax），因此会破坏信息。我们利用前向执行来恢复在后向执行中无法恢复的值，从而解决了这一难题。

缺失的内存写入

REPT 面临的第二个挑战是如何处理写入未知地址的内存。大多数内存地址无法静态确定。由于不可逆转指令的存在，分析可能无法完全恢复数据值，因此 REPT 在分析过程中可能不知道内存写入的目的地。出现这种情况时，一种选择是假设所有内存位置的值都变得未知。这种做法过于保守，因为它可能导致分析漏掉许多实际上可以恢复的数据值。如果 REPT 选择忽略内存写入，分析结果将在内存位置留下无效值，该值可能会传播到其他寄存器或内存位置。我们通过使用纠错功能来解决这一难题。

并行写内存

REPT 面临的第三个挑战是正确识别共享内存访问的顺序。在存在来自不同线程的多条指令序列的情况下，尽管硬件提供了时间戳，但可能无法推断并发内存访问的执行顺序。REPT 需要正确处理这些内存访问，否则可能会推断出这些内存位置的错误值。我们在分析中限制使用从并发内存访问中恢复的数据值，从而解决了这一难题。

设计

在本节中，我们将重点介绍 REPT 如何解决上一节讨论的三个关键技术挑战，从而描述 REPT 的设计。

为简洁起见，我们将指令序列定义为 I = {Ii|i = 1, 2, …, n}，其中 Ii 代表序列中执行的第 i 条指令。我们假设内存转储在第 n 条指令执行后可用。我们将程序的状态 S 定义为寄存器和内存位置中所有数据值的集合。我们将 Si 定义为第 i 条指令执行后的程序状态。因此，S0 代表执行第一条指令 I1 之前的程序状态，Sn 代表存储在内存转储中的程序状态。如果所有寄存器和内存的值都已知，我们就定义 Si 为完整状态。如果给定一个完整的状态 Si，我们可以完全恢复 Si-1，那么我们就将指令 Ii 定义为可逆指令；否则，我们就称该指令为不可逆转指令。REPT 的设计并不局限于特定的体系结构，不过，在本文的其余部分，我们将在示例中使用 x86-64 指令。

在本节的其余部分，我们将逐步介绍 REPT 的设计，描述它如何处理日益复杂和现实的场景。

只有可逆指令的单一指令序列（第 3.1 节）。
包含不可逆指令但不访问内存的单一指令序列（第 3.2 节）。
包含不可逆指令和内存访问的单一指令序列（第 3.3 节）。
包含不可逆指令和内存访问的多指令序列（第 3.4 节）。

逆转指令

REPT 的第一种机制假定输入是一个只有可逆指令的单一指令序列。由于每条指令都是可逆的，REPT 可以逆转每条指令的效果，从而完全恢复从指令序列结束到开始的初始程序状态。例如，如果指令序列中只有一条指令 I1 = add rax,rbx 和 S1 = {rax=3, rbx=1}，那么分析可以恢复 S0 = {rax=2, rbx=1}。

不可逆指令处理

REPT 的第二种机制假定存在一个包含不可逆指令的单一指令序列，但该序列不包括任何内存访问。实际上，大多数指令都是不可逆的。例如，xor rbx,rbx 是不可逆的，因为根据该指令的语义和指令执行后的 rbx 值，无法恢复指令执行前的 rbx 值。因此，针对可逆指令的直接逆向分析在一般情况下并不适用。

恢复被破坏值的关键思路是在前向分析中进行推断。只要被破坏的值来自其他寄存器和内存位置，并且这些寄存器和内存位置的值可用，我们就可以使用这些值来恢复被破坏的值。根据这一思路，我们的基本解决方案是反复执行后向和前向分析来恢复数据值，直到没有新值被恢复为止。

从概念上讲，给定指令序列 I 和最终状态 Sn，我们首先将 S0 至 Sn-1 程序状态中的所有寄存器值标记为未知。然后进行后向分析，恢复从 Sn-1 到 S0 的程序状态。之后，我们再进行前向分析，更新从 S0 到 Sn-1 的程序状态。我们重复这些步骤，直到达到一个固定点：即在后向或前向分析中没有任何状态被更新。在更新程序状态时，我们只将寄存器的值从未知值改为推断值。最重要的是，这种分析不会产生相互冲突的推断值，因为所有的初始值都是正确的，分析中的任何步骤都不会在正确值的基础上引入错误值。这也保证了迭代分析的收敛性。

我们在图 1 中展示了一个处理不可逆指令的示例。该指令序列有三条指令，其中两条是不可逆指令。由于在第一条指令之前没有指令，因此我们不能指望在 S0 中恢复 rbx。本例中有三点值得注意。首先，根据第二次迭代中的前向分析，我们恢复了 S1 中 rbx 的值。其次，在第二次迭代的前向分析中，我们保留了 S2 中 rax 的值 3，尽管在 S1 中 rax 的值是未知的。第三，在后向分析的最后一次迭代中，我们恢复 rax 在 S1 中的值 2。

恢复内存写

REPT 的第三种机制假定存在单一的指令序列，其中包含不可逆指令和内存访问。实际上，总有指令访问内存。与可通过指令静态识别的寄存器不同，内存访问的地址并不总是已知的。对于目标地址未知的内存写入指令，我们无法正确更新目标内存的值。缺少更新可能会引入一个过时的值，从而对后续分析产生负面影响。如果采用保守的方法，在内存写入丢失时将所有内存标记为未知，则会导致不必要的、不可接受的信息丢失。

我们解决内存写入缺失问题的关键是使用纠错技术。REPT 背后的直觉是，继续使用可能有效的内存值来推断其他值，并在以后根据冲突结果纠正无效值。在介绍 REPT 的纠错算法之前，我们先用一个例子来解释其高层次思想。

图 2 中的示例有五条指令。其中有三条关键更新指令，用粗体字标出。在逆向分析的第一次迭代中，由于我们不知道 rbx 在 S4 中的值，因此不改变地址 g 的值。原始值是 3，但新推断的值是 4（rax + [g] = 1 + 3 = 4）。我们的分析保留了原始值 3，因为它是从最终的程序状态推断出来的，我们假定最终的程序状态是正确的。在逆向分析的第三次迭代中，根据指令 I3 前后的 rax 值，我们可以恢复 [g] 的值为 2。

接下来，我们将介绍 REPT 用来恢复丢失的内存写入的算法。我们首先在第 3.3.1 节中介绍数据推理图，然后在第 3.3.2 节中解释我们如何使用该图检测和纠正内存写入丢失导致的错误。

数据推理图

在进行前后向分析时，REPT 维护一个数据推理图。数据推理图不同于传统的数据流图，因为数据推理图跟踪的是数据值是如何向前或向后推理出来的，而数据流图跟踪的只是程序的一个数据流方向。

图 3 显示了一个数据推理图示例。在这个例子中，我们使用 rcx 恢复 [rax]，然后使用后者恢复 rbx。这里我们假设 rax 的值在 I1 和 In 之间没有变化。

数据推理图中的节点代表执行指令时访问的寄存器或内存位置。如果一个节点对应的寄存器或内存位置用于读取，则称为使用节点。同样，如果一个节点用于写入，则称为 def 节点。例如，rbx@I1 是使用节点，rcx@In 是定义节点。如果在一条指令中，一个寄存器或内存位置同时被读取和写入，我们将为其创建两个节点：一个使用节点和一个定义节点。最后，REPT 将内存转储中的数据视为使用节点，因为它们的值可以像其他使用节点一样向后传播。

数据推理图中有两种方向边：值边和地址边。从节点 A 到节点 B 的值边表示 REPT 使用 A 的值来推断 B 的值。从 A 到 B 的地址边表示 A 的值用于计算 B 的地址。例如，从 rcx@In 到 [rax]@In 的边是值边，而从 rax@In 到 [rax]@In 的边是地址边。要获取或设置内存位置的值，必须知道其地址。在设置内存节点值时，除了值边外，REPT 还会添加来自寄存器节点的地址边，用于计算内存节点的地址。一个内存节点可以有多个传入地址边（例如，基寄存器和索引寄存器共同用于指定地址）。

有两种类型的值边。在第一种价值边中，连接的节点来自同一指令，我们称之为水平边。具体来说，在后向分析中，如果一个 def 节点的值是已知的，并且可以用来推断同一指令中一个使用节点的值，我们就恢复使用节点的值，并在两个节点之间添加一条水平边。同样，在前向分析中，如果已知一个使用节点的值，并可用来推断同一指令中一个定义节点的值，我们就恢复定义节点的值，并在两个节点之间添加一条水平边。值得注意的是，一个节点可能有多条水平输入值边。例如，给定 add rax,rbx，rax 的 def 节点可能有两条来自 rax 和 rbx 的使用节点的输入值边。

在第二种值边中，连接的节点来自不同的指令，但它们对应于相同的寄存器或内存位置。这种值边被称为垂直边。直观地说，通过垂直边缘连接的节点属于同一个定义-使用链（即一个定义及其所有达到的使用）。在后向分析中，我们沿 def-use 链从使用节点恢复值到前一个使用节点或 def 节点，并在两者之间添加垂直边。同样，在前向分析中，我们沿着定义-使用链从定义节点或使用节点向其后的使用节点恢复值，并添加相应的垂直边。换句话说，def 节点的值只能向前传播，而使用节点的值则可以双向传播。

对于数据推理图中的每个节点，REPT 还维护一个取消引用级别，以帮助纠错（第 3.3.2 节）。具体来说，内存转储中值的所有使用节点的取消引用级别均为 0。对于任何其他节点，REPT 分三步确定其取消引用级别：(1) 对于所有传入的值边，找出源节点的最大取消引用级别 D1；(2) 对于所有传入的地址边，找出源节点的最大取消引用级别 D2；(3) 挑选 D1 和 D2 + 1 之间较大的值作为目标节点的取消引用级别。我们可以看到，取消引用级别实际上衡量的是从内存转储中存储的值到给定节点的最大地址边的数量。节点的取消引用级别反映了其值的置信度，因为数据推断错误是由于内存写入丢失造成的。较高的取消引用级别意味着较低的置信度。

纠错

在前后迭代分析过程中，REPT 不断更新数据推理图，并检测和纠正不一致之处。不一致有两种：值冲突和边冲突。 当推断值与现有值不匹配时，就会发生值冲突。当内存位置的一个新确定的定义节点打破了通过垂直边连接的两个节点之间先前假定的定义-使用关系时，就会发生边冲突。请看图 3 中的示例。如果 REPT 检测到对 I1 和 In 之间由 rax 指定的同一内存位置的另一次写入，则这次内存写入将导致 [rax]@In 和 [rax]@I1 之间的垂直边发生冲突。

REPT 检测到冲突时，会停止对当前指令的分析，找出无效节点，然后运行无效化过程。对于这两种类型的冲突，无效化过程都从初始节点开始。在边冲突的情况下，初始节点是断开的垂直边的目标节点，因为它不再属于同一 def-use 链。在值冲突的情况下，REPT 会检查新推断值的节点的取消引用级别是否小于或等于现有值的节点的取消引用级别（这意味着新值的置信度较高或相等）。如果是这样，REPT 会选择现有值的节点作为初始节点进行无效化。否则，REPT 会丢弃新推断的值，并继续执行下一条指令。

如果 REPT 识别出一个初始节点需要作废，它会首先处理其每一条出站值边和地址边。对于值边，目标节点被标记为未知。对于地址边，目标节点将从数据推理图中删除，因为其地址变得未知，因此该内存位置上的这种定义或使用可能不再存在。然后，REPT 对这些目标节点递归应用失效过程。值得注意的是，数据推理图保证不会出现循环，因为 REPT 只有在首次推理出节点的值时，才会将节点和边添加到图中。

为确保分析的收敛性，REPT 为每个节点维护一个无效值黑名单。每次节点失效，其值就会被添加到黑名单中。一旦某个值进入节点的黑名单，该节点就不能再接受该值。这确保了迭代分析过程不会再次进入冲突状态，从而保证算法最终收敛。但是，如果一个正确的值的置信度低于另一个不正确的值，那么该值就会被错误地列入节点的黑名单。这就导致了一个问题，即一个值是可以恢复的，但由于使用了黑名单而无法恢复。我们选择保留黑名单，是为了优先考虑分析的收敛性，而不是数据恢复能力的提高。

处理并行

当我们面对在多个内核上同时执行的多条指令序列时，这个问题看似难以解决，因为如果没有完美的执行指令顺序，就可能有大量的指令排序方式。我们对解决这一难题有两个见解。首先，我们利用硬件跟踪记录的定时信息来构建不同线程中执行指令的部分顺序。其次，我们认识到内存写入是唯一可能影响数据恢复顺序的操作。

在指令序列中插入时间戳后，我们将两个时间戳之间的指令称为指令子序列。我们将两个时间戳称为子序列的开始和结束时间。给定来自两个不同指令序列的两个指令子序列，我们根据它们的开始和结束时间推断它们的相对执行顺序。如果一个子序列的结束时间早于另一个子序列的开始时间，我们就认为第一个子序列的执行时间早于另一个子序列。否则，我们就说它们的顺序无法推断，两个子序列是并发的。请注意，同一指令序列中两个子序列的顺序总是可以根据它们在指令序列中的位置来确定。如果两条指令所属的指令子序列是并发的，我们就说这两条指令是并发的。如果相应的内存访问指令是并发的，我们就说两条内存访问是并发的。

给定在多个内核上同时执行的多个指令序列，REPT 首先将它们划分为子序列，然后根据推断出的顺序将它们合并为一个单一的概念指令序列。对于无法推断出顺序的两个子序列，REPT 会在新构建的序列中任意插入一个，然后再插入另一个。一个自然的问题是，任意选择两个并发子序列的顺序是否会影响数据恢复。显然，如果我们改变两个并发访问同一位置内存的子序列的顺序，并且其中一个是写入，那么我们可能会得到不同的内存位置值。另一方面，如果并发子序列没有任何并发内存写入到同一位置，那么 REPT 将它们放入合并指令序列的顺序并不重要。

由于我们无法判断并发指令子序列的顺序，因此我们的目标是消除它们的模糊顺序对数据恢复的影响。具体来说，在迭代分析过程中，对于每次内存访问（无论读取还是写入），REPT 都会检测是否有并发内存写入到相同位置。如果有，REPT 会采取以下步骤来限制数据推理图中内存访问的使用。首先，REPT 删除代表内存访问的节点的所有垂直边，并使传出垂直边的目标节点无效。然后，REPT 给内存访问节点贴上标签，使其不会在垂直边中使用。这是因为 REPT 不知道内存访问是发生在并发内存写入同一位置之前还是之后。但是，REPT 仍然允许水平值边推断该节点的值。

剩下的一个问题是，为并发指令子序列选择任意顺序是否会影响对同一位置的并发内存写入的检测。我们的观察结果是，只要不存在两个独立的并发写入，即一个写入会影响另一个写入目的地的推断，REPT 的分析就能正常工作。我们承认这种可能性是存在的，但这取决于时间信息的粒度。考虑到现代硬件支持的时间戳粒度，我们认为这种情况在实践中很少发生 [39]。

实现

在本节中，我们首先介绍 REPT 的在线硬件跟踪和离线二进制分析的实现细节。然后介绍其部署情况。

在线硬件追踪

REPT 利用英特尔处理器跟踪（PT）记录程序执行的控制流和时序信息。英特尔 PT 在 2014 年发布 Broadwell 架构时可用。英特尔 PT 支持各种程序跟踪模式，REPT 目前使用每线程循环缓冲区模式来跟踪进程内所有线程的用户空间执行情况。REPT 支持配置循环缓冲区大小和时间戳粒度。我们没有将英特尔 PT 配置为对整个执行过程进行跟踪，因为这将带来频繁中断（当跟踪缓冲区满时）和 I/O 工作量（当缓冲区被写入某个持久性存储时）所造成的性能开销。当跟踪的进程失败时，其最终状态和记录的英特尔 PT 跟踪会保存在一个内存转储中。

离线二进制分析

REPT 将带有英特尔 PT 跟踪的内存转储作为输入，并输出每个线程的恢复执行历史。首先，REPT 对跟踪进行解析，以重建控制流。解析英特尔 PT 跟踪要求转储中的二进制代码与收集跟踪时执行的代码相同。因此，只要代码在循环跟踪缓冲区中记录其执行过程后未被修改，REPT 就支持已合并代码。接下来，REPT 将本地指令转换为指定操作码和操作数的中间表示 (IR)，并进行正向和反向分析，直至收敛。

除了最终的程序状态和常量，REPT 还可以利用控制依赖关系来恢复数据。例如，如果只有当寄存器的值为 0 时才执行条件分支，那么 REPT 就可以在观察到分支被执行后推断出寄存器的值。

程序调用系统调用来请求操作系统服务，而操作系统可能会修改进程中的某些寄存器和内存值作为回应。在系统调用时，REPT 会根据调用约定将所有易失性寄存器标记为未知。REPT 目前不处理内核的内存写入，而是将其与丢失的内存写入同样处理，并依靠纠错机制来检测和解决冲突。我们承认，语义感知的系统调用处理可以通过更多的工程努力来完成，以帮助改善数据恢复，但我们将其留待未来的工作来完成。

部署

我们在两个组件中实现了 REPT，并将其部署到 Microsoft Windows 的生态系统中，用于程序跟踪、故障报告和调试。

首先，我们将在线硬件跟踪组件作为一个 8.5K 行 C 代码的驱动程序来实现。它负责控制目标进程的跟踪，并在被监控进程失败时在内存转储中捕获跟踪结果。我们还修改了 Windows 内核，通过在上下文切换时交换跟踪缓冲区来支持每线程跟踪。

其次，我们将 REPT 的离线二进制分析和反向调试作为一个包含 10 万行 C++ 代码的库来实现，并将其集成到 WinDbg [45] 中。我们还实现了代码和数据断点等常用调试功能，以方便调试过程。

我们增强了 Windows 错误报告 (WER) 服务 [30] 以支持 REPT。具体来说，开发人员可以在 WER 上请求英特尔 PT 丰富内存转储。然后，WER 选择用户机器来跟踪目标程序。当跟踪的程序发生故障时，就会捕获并向 WER 发回带有英特尔 PT 跟踪的内存转储。最后，开发人员可将丰富的内存转储加载到 WinDbg 中进行反向调试。

评估

在本节中，我们将对 REPT 进行评估，以回答以下四个问题： (1) REPT 恢复数据值的准确性如何？(2) REPT 恢复数据值的效率如何？(3) 使用 REPT 调试故障的效率如何？(4) 部署状况如何？接下来，我们将介绍我们的实验设置并描述实验结果，以回答这些问题。

我们对 REPT 在表 1 中列出的 16 个实际错误所导致的故障进行了评估。所有这些错误都来自开源软件。出于独立可重复性的考虑，我们将重点放在开源软件上。限制我们在更多错误上评估 REPT 的主要因素是，我们需要在 Microsoft Windows 上重现开源软件中的错误。在重现错误时，我们尽量从广泛使用的现实世界系统（如 Apache、Python、Chrome 和 PHP）和各种错误类型（如 NULL 指针取消引用、竞赛、类型混淆、无后用、整数溢出和缓冲区溢出）中挑选错误。

在实验中，我们将英特尔 PT 配置为每个线程使用 256K 字节的循环缓冲区，并打开最细粒度的时间戳记录（即 TSCEn=1、CYCEn=1、CycThresh=0 和 MTCFreq=0；详情请参见 [36]）。

讨论

在本节中，我们将讨论 REPT 的局限性以及我们计划如何在今后的工作中解决这些问题。

目前，开发人员在实际使用 REPT 时，不得不面对两个主要限制。首先，控制流跟踪的时间可能不够长，无法捕捉到缺陷（例如，free 调用不在 use-after-free 错误的跟踪中）。其次，无法恢复调试故障所需的数据值（例如，对于使用后释放错误，无法恢复传递给释放调用的堆地址）。我们不能简单地使用大型循环跟踪缓冲区来解决这个问题，因为随着跟踪大小的增加，数据恢复的准确性也会降低。

REPT 目前不会捕获程序执行过程中的任何数据。要从根本上解决这两个限制，我们需要记录更多数据，而不仅仅是内存转储。如何在在线数据记录、运行时开销和离线数据恢复之间取得良好的平衡，是一个有待研究的问题。一个潜在的方向是利用新的 PTWRITE 指令 [36] 来记录对 REPT 数据恢复非常重要的数据。

REPT 目前的实现仅支持用户模式执行的反向调试。虽然 REPT 的核心分析是针对机器指令的，因此与权限模式无关，但我们需要正确处理内核特有的人工制品（如中断），以支持内核模式执行的反向调试。

除了反向调试之外，我们认为还可以利用 REPT 恢复的执行历史记录进行自动根源分析。面临的挑战是 REPT 的数据恢复并不完美，因此研究问题是如何根据 REPT 提供的不完美信息进行自动根源分析。

我们对 REPT 的评估主要针对在单机上运行的软件。当开发人员调试分布式系统时，他们通常依赖于事件日志。研究如何将程序跟踪与事件日志相结合，以帮助开发人员调试分布式系统中的错误，是一个有趣的研究方向。我们一直未能将 REPT 应用于移动应用程序，因为在移动设备上还没有像英特尔 PT 这样的高效硬件跟踪技术。

总结

我们介绍了 REPT，这是一种用于反向调试已部署系统中软件故障的实用解决方案。REPT 可根据控制流跟踪和内存转储，通过执行正向和反向执行迭代纠错，准确高效地恢复数据值。我们在 Microsoft Windows 生态系统中实施并部署了 REPT，用于程序跟踪、故障报告和调试。我们的实验表明，REPT 能在数秒内高精度地恢复数据值，其反向调试能有效诊断出 16 个错误中的 14 个。有了 REPT，我们希望有一天开发人员会拒绝在没有反向调试的情况下调试故障。

阅读笔记：REPT: Reverse Debugging of Failures in Deployed Software