阅读笔记：RETracer: Triaging Crashes by Reverse Execution from Partial Memory Dumps

RETracer: Triaging Crashes by Reverse Execution from Partial Memory Dumps

• 设计了一种新的崩溃分流方法，无需执行轨迹即可执行后向污点分析，并根据后向数据流图识别出受指责的函数。
• 找到函数，将不同崩溃分组，不需要找到根本原因。（RETracer 的分流目标是将同一错误导致的崩溃归为一组，这并不需要找到根本原因。）
• RETracer 的输入是崩溃的内存转储、内存转储中识别出的模块二进制文件及其调试符号。
• 选择在二进制层面进行分析。

摘要

许多软件提供商都提供崩溃报告服务，以自动收集来自数百万客户的崩溃信息并提交错误报告。对软件提供商来说，精确分流崩溃是必要且重要的，因为每天可能报告的数百万次崩溃对于识别高影响错误至关重要。然而，现有系统的分流准确性有限，因为它们仅依赖于崩溃时堆栈跟踪的语法信息，而不分析程序语义。

在本文中，我们介绍了 RETracer，这是首个基于内存转储重建的程序语义来分流软件崩溃的系统。RETracer 是为满足大规模崩溃报告服务的要求而设计的。RETracer 在没有执行跟踪记录的情况下执行二进制级别的后向污点分析，以了解堆栈上的函数是如何导致崩溃的。主要挑战在于，由于大多数指令都会破坏信息，因此无法从内存转储中完全恢复早期的机器状态。

我们为 x86 和 x86-64 本机代码实现了 RETracer，并将其与微软使用的现有崩溃分流工具进行了比较。根据对微软 Windows 和 Office 中已修复的 140 个错误的人工分析，我们发现 RETracer 可消除三分之二的分流错误。RETracer 已被部署为微软崩溃报告服务的主要崩溃分流系统。

引言

许多软件供应商，包括 Adobe [2]、Apple [6]、Google [16]、Microsoft [15]、Mozilla [28] 和 Ubuntu [41]，都提供崩溃报告服务，自动收集来自数百万客户的崩溃信息，并根据这些信息提交错误报告。此类服务对软件提供商至关重要，因为它们能让软件提供商快速识别对客户影响较大的错误，针对正确的软件开发商提交错误报告，并验证其修复措施。最近，苹果公司为 iOS 和 Mac 应用商店中的应用程序增加了崩溃报告功能，以帮助应用程序开发人员找出用户遇到的主要问题[5]。崩溃报告不仅被传统的桌面平台所依赖，也被最新的移动平台所依赖。

崩溃报告服务中最关键的任务之一是对软件崩溃进行分流，即对可能由相同错误引起的崩溃进行分组。大型服务每天可能会收到数以百万计的崩溃报告。开发人员不可能只检查其中的一小部分。良好的分流可以将可能属于同一软件错误的大量崩溃报告集中在一起，从而减少需要检查的崩溃报告数量。它还有助于按用户影响优先处理最关键的错误（即崩溃报告数量最多的错误），并将其提交给正确的软件开发人员。

精确的崩溃分级是一个难题。一个错误可能会以各种方式表现出来，并产生大量外观相似的崩溃报告。崩溃报告中包含的有限信息更加剧了这一困难。一份典型的报告（或核心转储或内存转储 [45]）最多包含崩溃线程的上下文（堆栈和处理器寄存器）以及崩溃时机器内存内容的子集。由于受到各种限制（从尽量减少客户机器的开销到保护客户隐私），软件提供商无法在报告中提供更丰富的信息。特别是，报告中没有导致崩溃的程序执行信息。大规模崩溃报告服务所面临的巨大工作量又增加了一个问题，因为分析崩溃通常需要一定的时间预算。

鉴于这些挑战，崩溃报告服务仅限于以 “语法 “方式使用堆栈跟踪来分流崩溃。Ubuntu [40] 通过使用根据崩溃线程堆栈上的前五个函数计算出的崩溃签名对崩溃进行分组（除非另有说明，本文其余部分将把它称为 “堆栈”）。微软的 Windows 错误报告（WER）服务[15]使用一种名为 !analyze (bang analyze [23])的工具，根据在堆栈上识别出的受指责函数对崩溃进行分组。!analyze 默认将顶层函数选为受指责的函数，但会使用大量函数和模块白名单以及额外的启发式方法来选择堆栈下层的不同函数。此类分流方法不考虑函数的 “语义”，即它们如何导致崩溃。这大大限制了它们的分流准确性和崩溃报告服务的整体有效性。

在本文中，我们介绍了 RETracer，这是第一个根据从内存转储中重建的程序语义来分流软件崩溃的系统。RETracer 是为满足大规模崩溃报告服务的要求而设计的。从概念上讲，RETracer 模仿开发人员通常通过反向分析代码和堆栈来调试崩溃，从而找出错误值（如损坏的指针）是如何传递的。RETracer 仅根据内存转储实现了二元级反向污点分析，从而自动完成了这一调试过程。

逆向污点分析从执行结束时的污点数据项（如损坏的指针）开始，对指令进行反向分析，以逆向传播污点，并确定污点数据在较早时间的来源。对已记录的执行跟踪进行这种分析非常简单 [14, 8, 9]。然而，记录执行轨迹并不是崩溃分流服务的一种选择，因为它会在正常执行过程中带来巨大的跟踪开销[8]。

在没有执行跟踪的情况下进行后向污点分析具有挑战性。由于大多数指令都会破坏信息，因此无法完全恢复早期的机器状态。例如，执行 XOR EAX, EAX 后，寄存器 EAX 的原始值将丢失。在机器状态不完整的情况下，当污点内存位置的地址无法恢复时，向后的污点传播可能不得不提前停止。

RETracer 是第一个在没有执行跟踪的情况下成功执行二元级反向污点分析的系统，用于崩溃分流。为了恢复内存地址，它结合了具体的反向执行和静态的正向分析来跟踪寄存器值。

给定一个从反向污点分析中推断出的反向数据流图，如何找到归咎函数并不明显。我们设计了一种直观的算法来解决这个问题。RETracer 会责备首次导出坏内存地址的函数。其背后的直觉是，第一个获得坏值的函数应该是确保该值正确性的函数。

我们已将 RETracer 开发成一个可运行的系统，用于分流 x86 和 x86-64 本机代码的崩溃，并将其与 WER 使用的现有崩溃分流工具 !analyze 进行了比较。我们手动分析了 Microsoft Windows 8 和 Office 2013 中修复的 140 个漏洞的崩溃情况。除 22 个错误外，RETracer 能正确识别所有错误的受责函数，而 !analyze 则在 73 个错误中失效。因此，RETracer 将分流错误的数量减少了三分之二。我们在随机选取的 3000 个崩溃案例中对 RETracer 进行了评估，发现其运行时间的中位数、平均值和最大值分别为 1.1 秒、5.8 秒和 44.8 秒。RETracer 已被部署为 WER 上的主要碰撞分流系统。对部署数据的研究表明，RETracer 被用于分析微软软件中约一半的 x86 和 x86-64 崩溃报告。

贡献

• 我们设计了一种新的崩溃分流方法，无需执行轨迹即可执行后向污点分析，并根据后向数据流图识别出受指责的函数（第 3 节）。
• 我们实施了 RETracer，用于分流 x86 和 x86-64 本机代码的崩溃（第 4 节）。
• 我们将 RETracer 与 WER 使用的现有崩溃分流工具 !analyze 在 140 个已修复的错误上进行了比较，并研究了 RETracer 在 WER 上的部署情况（第 5 节）。(第 5 节）。

概述

在本节中，我们将概述 RETracer 的设计，并讨论其设计选择。

除了堆栈溢出（即堆栈空间不足）、未加载模块和位翻转导致的崩溃外，RETracer 可以分析所有由违规访问导致的崩溃[29]。这三种例外并不是严重的限制，因为它们都有有效的解决方案。对于堆栈溢出，直接的解决办法就是指责占用堆栈空间最大的函数。对于卸载模块，直接的解决方案是将责任归咎于调用卸载模块的函数。文献 [29] 提出了一种检测位翻转的解决方案。在微软软件的 x86 和 x86-64 崩溃中，RETracer 正在分析的崩溃约占一半（见第 5 节）。

RETracer 可执行后向污点分析来分流崩溃。这基本上模仿了开发人员分析崩溃的方式。开发人员经常问的第一个问题是，损坏的指针来自哪里。为了回答这个问题，他们通常会向后跟踪代码和堆栈，找出损坏指针是如何传递的。RETracer 中的向后污点分析可自动完成这一调试过程。

与现有的分流解决方案 [15, 40]类似，RETracer 专注于崩溃线程的堆栈：它会将责任归咎于堆栈中的一个函数。一个常见问题是，如果崩溃涉及多个线程，该怎么办？答案有两个方面。首先，很大一部分错误只涉及崩溃线程。例如，对 ECLIPSE 项目的实证研究[36]表明，超过 60% 的错误是在崩溃堆栈上的函数中修复的。其次，RETracer 的分流目标是将同一错误导致的崩溃归为一组，这并不需要找到根本原因。例如，假设线程 1 中的函数 A 向指针写入了一个坏值。线程 2 中的函数 B 读取了坏指针并取消引用，导致访问违规。在这种情况下，根本原因是函数 A。但如果函数 B 是使用坏指针的唯一函数或少数函数之一，那么根据函数 B 对崩溃进行分组就能达到分流的目的。

逆向数据流分析原则上可以在源代码（例如 [22, 37]）或二进制文件上进行。源代码分析具有许多理想的特性，包括不受处理器指令集复杂性的影响。然而，我们唯一的崩溃信息来源是崩溃报告。它们所包含的数据（CPU 寄存器值、存储在原始虚拟地址上的值）可直接用于二进制分析。虽然我们可以考虑将这些信息转换成适合源代码级分析的形式，但这种转换必须克服各种复杂问题。崩溃报告中的寄存器和内存位置必须映射到源代码中的变量。难点在于临时变量没有调试信息。例如，给定 VarB = VarA->FieldB->FieldC，没有调试信息表明 VarA->FieldB 的值存储在哪个寄存器或堆栈位置。此外，编译器的优化可能会使从机器状态到源代码的映射变得更加困难。考虑到这些复杂性，我们选择在二进制层面进行分析。

这种选择的另一个好处是使 RETracer 独立于原始编程语言。这样，我们就可以使用单一分析引擎来分析本地代码（如由 C/C++ 编译而成）和 jitted 代码（如由 C# 或 JavaScript 编译而成）的崩溃。在本文中，我们将重点分析本地代码的崩溃。

污点分析将元数据（污点）分配给数据项（寄存器或内存位置）。给定一个指令序列和一组初始污点数据项，污点分析会将与指令源操作数相关的任何污点传播到其目标操作数。逆向污点分析从执行结束时的污点数据项开始，试图确定污点数据在较早时间的来源。它对指令进行反向分析，将污点向后传播。这种技术已被应用于记录的执行跟踪[9]，在这种跟踪中，可获得完整的执行指令序列和大量可从中推导出的状态。

RETracer 是第一个在没有执行跟踪的情况下进行二进制逆向污点分析的系统。RETracer 的输入是崩溃的内存转储、内存转储中识别出的模块二进制文件及其调试符号。在 Windows 系统中，二进制文件是一个 PE 文件，其调试符号存储在相应的 PDB 文件中。RETracer 不要求内存转储是完整的。相反，它只需要崩溃线程在崩溃时的堆栈内存和 CPU 上下文。转储中的其他内存信息可能会改进分析，但并非必要。

RETracer 从导致崩溃的损坏指针开始，使用后向污点分析找到坏值产生的程序位置。内存转储的信息量有限（与执行跟踪相比），这是 RETracer 必须克服的一个重大复杂问题。后向污点分析的结果是一个后向数据流图，它显示了损坏指针是如何产生的。RETracer 会对该图进行分析，以确定首次产生损坏指针的归咎函数。

RETracer 的反向污点分析使用具体地址而非符号表达式来表示内存位置。使用具体地址的主要限制是，如果无法恢复污点内存位置的地址，污点就无法传播。使用符号表达式的主要限制是，如果污点内存位置的符号表达式的别名集是一个过度近似集，污点就会传播得太远。在 RETracer 中，我们选择具体地址而非符号表达式，因为我们宁愿责备一个与崩溃接近的函数，也不愿责备一个完全无关的函数。为了恢复内存位置的具体地址，RETracer 将具体反向执行与正向静态分析相结合，以跟踪寄存器和内存位置的值。

一个简单的例子如清单 1 所示。在本例中，崩溃发生在函数 h 第 16 行。通过逆向污点分析，RETracer 可以发现，坏指针 r 最初是在第 4 行的函数 f 中设置的。因此，RETracer 将这次崩溃归咎于函数 f。

设计

本节将详细介绍 RETracer 的设计。首先，我们将介绍后向污点分析的基本方案。然后，我们将介绍如何使用静态前向分析来缓解不可逆转指令导致的寄存器值缺失问题。最后，我们将介绍从反向数据流图中识别被篡改函数的算法。

RETracer 的分析是在二进制层面进行的。我们用一种非常简单的汇编语言来描述设计。这样，我们在描述 RETracer 时就不会受到任何具体处理器特异性的影响。第 4 节将介绍我们如何为 x86-64 处理器实现 RETracer。

我们语言中的程序是一串指令，其形式为 opcode dest,src，其中 opcode 指定指令类型（如 mov 或 xor），src 和 dest 是源操作数和目的操作数。操作数是立即操作数（常量）、处理器寄存器（编号为 R0、R1、…）或指定为 [Rb +c-Ri +d] 的内存地址，其中 c∈{0, 1, 2, 4, 8} 是常量，d 是常量位移，Rb 和 Ri 是任意寄存器。我们称 Rb 为基数寄存器，Ri 为索引寄存器。

逆向污点分析

对于污点分析，我们需要回答两个问题：如何引入污点和如何传播污点。我们在寄存器和具体内存位置上都保留了污点信息。对于内存位置，我们以字节粒度保留污点。对于寄存器，我们以寄存器粒度保留污点。

接下来，我们首先介绍污点引入、污点传播和具体的反向执行。然后，我们将解释如何在函数内部和跨函数执行逆向分析。

污点介绍

崩溃报告会记录崩溃指令和违规访问类型（即读取、写入或执行）。对于写入违规，我们会检查崩溃指令的目标操作数。如果是内存操作数，我们会污点传染到其基数寄存器和索引寄存器，因为基数寄存器可能包含已损坏的指针值，而索引寄存器可能包含已损坏的数组索引。对于读取违规操作，我们对源操作数进行类似处理。对于执行违规，我们会检查调用者是否调用了函数指针。如果是，我们就会污点传染到函数指针内存操作数的基寄存器和索引寄存器。

污点传播

从引发崩溃的指令开始，我们逐条指令向后移动。第 3.1.5 节将解释我们如何将程序的控制流纳入这一分析。对于每条指令，我们都会根据指令的语义传播污点。默认情况下，我们首先检查目的操作数是否被污染。如果是，我们首先解除目标操作数的污点，然后再污点源操作数。例如，MOV 指令将源操作数的值复制到目的操作数，可按默认规则处理。第 4 节包含需要更复杂污点处理规则的 x86 指令示例。

向寄存器传播污点时，我们不需要知道它们的值。当向内存位置传播污点时，我们必须知道它们的地址。即使内存地址未知，如果存在内存操作数的基寄存器和索引寄存器，我们也会将污点传播到它们。通过对这些寄存器进行污点处理，我们就能追踪到指向被破坏值的指针是如何递归得出的，并构建出多层取消引用的后向数据流图。在第 3.2 节中，我们将介绍如何使用这种后向数据流图来确定导致崩溃的函数。

具体的反向执行

要计算内存位置的地址，我们需要知道内存操作数的基寄存器和索引寄存器的值。在 RETracer 中，我们执行具体的反向执行，以跟踪寄存器和内存位置的值。与污点跟踪类似，我们以寄存器粒度保留寄存器的值，以字节粒度保留内存位置的值。

我们可以将指令视为函数 f，即 dst = f (src)（例如 MOV dst, src）或 dst = f (src, dst)（例如 ADD dst, src）。在前一种情况下，指令的具体反向执行试图计算 src = f -1(dst) 的值。如果我们知道 dst 的值，并且 f 是可逆的（即 f -1(dst) 是一个单一值），计算就会成功。在后一种情况下，我们试图在指令执行前确定 dst 的值。如果我们知道指令执行后 src 和 dst 的值，并且 f 是可逆的，那么这就是可能的。在这两种情况下，如果我们能得到值，就更新与操作数相关的寄存器或内存位置，然后向后执行下一条指令。

由于许多指令是不可逆的，因此问题变得更加复杂。例如 XOR R0, R0 和 MOV R0, [R0]。在这些情况下，我们将寄存器或内存位置的值设置为未知。在 MOV R0, [R0] 等情况下，我们也无法将污点传播到内存位置 [R0]，因为 R0 的值是未知的。

值得注意的是，堆栈和帧指针[43]上的指令大多是可逆的。这使得 RETracer 几乎可以完全跟踪堆栈内存位置上的污点。另一方面，寄存器值缺失问题严重影响了不受堆栈或帧指针控制的内存位置的污点传播。下一小节将介绍我们如何使用静态前向分析来缓解这一问题。

静态前向分析

静态前向分析的主要思路是对单个函数进行二进制分析，以确定寄存器值是如何产生的。

MOV R0,R1
MOV R0,[R0]

在上述两条指令的示例中，我们的前向分析会发现，在执行第一条指令后，我们建立了 R0 与 R1 具有相同值的值关系。在对第二条指令进行后向分析时，我们可以利用这种值关系计算 R0 的原始值（假设 R1 的值已知），并将污点传播到 [R0]。这种查找是递归进行的。例如，如果我们不知道 R1 的值，我们将检查是否可以从其他寄存器或内存位置计算出 R1 的值。

这与传统的使用定义分析类似。但有一个重要区别。我们的目标是找到依赖于当前寄存器值的值关系。

MOV R0,R1
MOV R1,R2
MOV R0,[R0]

在上述三条指令的示例中，执行第二条指令后，我们将使基于 R1 的所有值关系无效，因为 R1 的值发生了变化。然后，我们为 R1 和 R2 添加新的值关系。因此，在执行第三条指令时，我们不会使用 R1 恢复 R0 的值。与此相反，传统的使用定义分析法会认为 R0 是由 R1（在第一条指令中）定义的。

我们的静态前向分析是保守的，因为如果无法确定内存写入的目的地，我们就会使所有内存位置的值关系无效。为了确定内存写入堆栈的目的地，我们会跟踪堆栈指针是如何更新的。具体来说，我们使用两个符号表达式来表示指向堆栈的寄存器值。第一个符号表达式是 stack0，表示堆栈指针在函数入口处的值。第二个符号表达式是 stack1，表示堆栈对齐（例如对齐到 8 字节）后堆栈指针的值。我们需要第二个符号表达式，因为栈对齐指令的效果无法静态确定。在我们的静态前向分析中，堆栈指针及其派生的其他寄存器都由 stack0 或 stack1 加上偏移量来表示。

基于栈 0 和栈 1 跟踪寄存器的另一个优势是，我们可以直接判断内存操作数中的寄存器是否指向栈。如果是，我们就不会将污点传播到该寄存器（因为 RETracer 不会处理堆栈溢出）。如果不这样做，不正确的污点最终会传播到堆栈指针。虽然这个问题可以解决，但会使我们的后向污点分析复杂化。

Intra-Procedural Analysis

我们已经介绍了后向污点分析和静态前向分析的基本思想。接下来，我们将介绍如何在函数中进行这两种分析。给定一个函数，我们首先将其划分为基本模块，并构建控制流图。

静态前向分析只进行一次，然后再对函数进行后向污点分析。我们的目标是在每条指令之前计算所有寄存器的值关系。对于每个程序块，我们首先通过合并控制流图中所有前面程序块的值关系来初始化值关系。然后，我们分析基本程序块中的每条指令，更新值关系，详见第 3.1.4 节。我们通过迭代所有程序块来重复这一过程，直到值关系收敛为止。当我们合并多个代码块的值关系时，如果某个寄存器的值关系存在冲突，我们就会将该寄存器的值标记为无效。这样可以确保静态前向分析收敛。

在具体的反向执行中，我们会保留每条指令的寄存器和内存位置的当前值。我们从崩溃指令的函数开始。我们利用崩溃报告获取寄存器和内存位置的初始值。然后，我们从崩溃指令块中的崩溃指令开始反向执行。对于每条指令，我们都会按照第 3.1.3 节所述更新寄存器和内存位置的具体值。必要时，我们还会利用从静态前向分析中推断出的值关系来恢复寄存器的值。对于每个代码块，我们首先合并控制流图中所有后续代码块的值和污点。如果寄存器或内存位置的具体值不一致，我们就将其值设为未知。我们通过迭代崩溃指令可向后到达的所有区块来重复这一过程，直到值趋于一致。

如果崩溃指令块处于循环中，上述分析将合并多次迭代的值。这可能会覆盖导致崩溃的原始值。为了更好地捕捉这些重要值，我们创建了一个新块，在其块中包含崩溃指令之前的指令。我们反向执行这个新块，只在开始时将值传播到其前面的块一次。

如第 3.1.2 节所述。对于每个程序块，我们首先合并控制流图中所有后续程序块的污点。由于一个寄存器或内存位置可能在多个地方被玷污，因此我们将其玷污点保留为其被玷污的程序位置的集合。在合并寄存器或内存位置的污点时，我们只需更新这一组即可。我们通过迭代所有可从崩溃指令向后到达的区块来重复这一过程，直到污点收敛为止。我们还对崩溃指令块进行了与具体反向执行相同的优化，以捕捉崩溃前的原始污点传播。

完成对崩溃函数的分析后，我们将其在函数入口处的值和污点作为其调用者在堆栈上的初始值和污点。然后，我们从调用者调用崩溃函数的调用指令开始，对调用者函数进行后向污点分析。我们在调用指令块中应用前面所述的优化方法，以便更好地捕捉函数调用前的值和污点。完成对该函数的分析后，我们将继续对堆栈中的调用者进行分析。

Inter-Procedural Analysis

我们刚刚介绍了如何在函数内执行后向污点分析和静态前向分析。接下来，我们将详细介绍如何在这两种分析中处理函数调用。

我们的静态前向分析是程序内分析。在这种分析中，我们不分析被调用函数。相反，在给定一条调用指令时，我们会根据调用约定[44]对易失性寄存器以及内存位置的值关系进行无效化处理。如果被调用者根据函数的调用约定负责清理堆栈，我们还会更新堆栈指针。

我们的后向污点分析是跨程序的。除了如前所述分析堆栈上的函数外，我们还对这些函数调用的函数进行反向污点分析。我们的程序间分析必然是不完整的，因为在反向执行过程中，我们可能无法找到所有间接调用的目标函数。此外，在崩溃堆栈上的函数与未在崩溃堆栈上的函数的主要区别在于，后者的堆栈不可用，因为它们已经被弹出。如果没有堆栈，当寄存器值在典型函数结束时从堆栈中 “弹出 “时，就很难恢复丢失的寄存器值。这意味着我们跟踪不在崩溃堆栈上的函数中内存污点的能力有限。

基于这两个原因，我们只对有污点返回值或改变堆栈指针（如异常处理代码）的受调函数进行后向污点分析。在对被调用者函数进行后向污点分析之前，我们先对其进行静态前向分析。我们从受调用者函数的返回指令开始分析。

对于我们没有分析其目标的调用指令（因为我们找不到目标或目标不符合我们的条件），我们会根据函数的定义检查其返回值和参数是否被玷污。一般来说，我们没有关于函数如何更改参数的规范，因此我们的参数检查只是一种近似值。具体来说，我们假设被调用者函数可以修改参数指向的目标数据结构，并检查该数据结构覆盖的任何内存是否被污染。如果返回值或参数被玷污，我们将解除玷污并标记其值是由被调用者函数设置的。

受指责功能的识别

在本节中，我们将介绍如何根据后向污点分析构建后向数据流图，以及如何根据该图识别归咎函数。

后向数据流图

当寄存器或内存位置受到污染时，就会在我们的逆向数据流图中创建一个节点。当常量或调用被调用函数时停止污点时，也会创建一个节点。为了区分不同指令或同一指令的不同调用中相同寄存器和内存位置的实例，我们将节点定义为三个元组，包括堆栈上函数的帧级别、指令地址、寄存器或内存位置、常量或代表对被调用函数调用的符号。崩溃函数的帧级别为零，因为它位于栈顶。向下移动堆栈时，当移动一帧时，帧级别增加一帧。对于不在栈上的被调用函数，我们使用栈上调用函数的帧级别。后向数据流示例图如图 1 所示。

我们的后向数据流图有两种边：赋值边和取消引用边。当我们将污点从目的操作数传播到源操作数时，就会添加一条赋值边。当我们将污点从内存位置传播到其基寄存器和索引寄存器（即内存基地址和数组索引）时，就会添加一条取消引用边。赋值边和取消引用边都是有方向的。对于赋值边，方向是从目标操作数到源操作数。对于取消引用边，方向是从内存位置到基寄存器和索引寄存器。

我们在图中添加一个特殊节点（称为崩溃节点）。我们还从崩溃节点向接收到初始污点的基寄存器和/或索引寄存器添加取消引用边。我们将节点的取消引用级别定义为从崩溃节点到该节点的任何路径上取消引用边的最小数量。崩溃节点的解除引用级别为 0。

受指责功能的识别

我们的识别算法分为两个步骤。第一步是识别有不良值的节点。第二步是找到造成这些坏值的归咎函数。

第一步，我们默认选取崩溃地点的基础寄存器和索引寄存器节点作为坏值节点。这些节点通过取消引用边与崩溃节点相连。图 1 中只有一个坏值节点 [0,gdi32+f78d,{REG:RCX}]。这条规则有两个例外。一个与数组操作有关。另一个与白名单模块有关。

编译器通常以 [Rb + c - Ri + d] 的形式实现数组运算，我们要寻找这种类型的操作数。如果崩溃指令没有索引寄存器，而它的基寄存器（即损坏的指针）来自数组操作，我们就会选择数组操作的基寄存器和索引寄存器的节点作为坏值的节点。这种例外情况背后的直觉是，如果损坏的指针是从数组访问中获得的，那么数组访问中出现问题（由于坏的数组基寄存器或坏的数组索引）的可能性要比数组中包含错误值的可能性大。

我们有条件地将 ntdll.dll 等库模块列入白名单。一方面，此类模块的崩溃通常是由模块外调用者的错误引起的。另一方面，简单地忽略白名单模块中的函数是有问题的，因为这样会阻止开发人员检测库模块中的错误。由于库模块的广泛使用，这些错误往往具有很大的影响。忽略它们可能会导致大量未解决的崩溃。

我们借助后向数据流图来解决这一难题。如果图中的所有节点都来自白名单模块的函数，那么崩溃很可能是由于白名单模块中的错误造成的，因为白名单模块之外的调用者没有传递与崩溃直接相关的参数。在这种情况下，我们会将白名单模块作为普通模块处理。否则，我们会选择白名单模块之外且具有最小取消引用级别的节点作为坏值节点。它们基本上代表了传递给白名单模块的污染参数。

在算法的第二步中，我们按如下方法确定一个自责函数。首先，我们仅通过赋值边来识别可从坏值节点到达的节点。所有这些节点都处于相同的取消引用级别。然后，我们选取包含这些节点且具有最大帧级别的函数作为受指责函数。这种算法背后的直觉是，第一个获得坏值的函数应该是确保该值正确性的函数。

要修复调用中的错误参数，可以在传入参数前在调用方或在使用参数前在被调用方中进行。对于这类错误，我们的算法总是归咎于调用者。我们这样做有两个原因。首先，我们在实践中观察到的大多数错误修复都是在调用者中进行的。其次，调用方函数中的调用站点比被调用方函数揭示了更多信息。开发人员可以利用更丰富的信息来决定实际修复的位置。

默认情况下，我们使用归咎函数的名称及其模块名称进行分流。但有一个例外。如果我们的分析停在一个没有符号信息的堆栈帧上，我们就没有函数名。在这种情况下，我们只使用模块名称。这样，RETracer 就能正确归咎于第三方模块（传递了错误参数），而不是正确的第一方代码。

在图 1 所示的示例中，RETracer 正确归咎于 mshtml.dll 模块中的一个函数，而崩溃发生在堆栈上三帧的另一个模块（gdi32.dll）中的一个函数。坏值首先来自 [3,mshtml.dll+6a7879,{MEM:(RSI+10)}]。

实现

我们针对本地 x86 和 x86-64 Windows 二进制程序的崩溃实施了 RETracer。RETracer 使用 Windows 崩溃转储（.dmp）文件，并以 WinDbg [24] 扩展 [33] 的形式实现。原型包括大约 66,000 行 C 和 C++ 代码。

RETracer 不支持未处理异常导致的崩溃，以及堆栈溢出、未加载模块和位翻转导致的访问违规。它只需检查异常代码即可识别未处理异常。它通过检查堆栈指针是否超过堆栈限制来识别堆栈溢出。RETracer 通过检查堆栈帧是否来自未加载模块来识别未加载模块。它依靠 [29] 的现有实现来检测位翻转。

RETracer 使用 Windows 库（MSDIA 和 MSDIS）从 Windows 符号（.pdb）文件中提取调试信息，并反汇编 Windows 可移植可执行文件（PE）中的机器指令。MSDIA 和 MSDIS 在 Microsoft Visual Studio [25] 中发布。给定 PE 文件中的偏移量后，RETracer 会基于 MSDIA 和 MSDIS 实现自己的逻辑，以识别包含该偏移量的函数，找到函数的代码范围，将其反汇编为指令，并构建基本模块的控制流图。

RETracer 目前依赖存储在 PDB 文件中的调试信息来可靠地反汇编二进制文件。IDA [18] 等优秀反汇编器可以根据启发式方法，在没有调试信息的情况下反汇编二进制文件。虽然在没有调试信息的情况下可能无法实现完美的反汇编，但如果 RETracer 能够正确反汇编大多数二进制文件，就有可能与这类反汇编器很好地合作。这种整合有待未来的探索。

对于每条指令，RETracer 都会将其解析为中间表示形式，其中指定操作码以及源操作数和目的操作数。RETracer 可以解析所有 x86/x86-64 指令。这允许 RETracer 在分析中对所有指令应用默认操作。反向污点分析的默认操作是清除目标操作数的污点，并将其传播到源操作数。具体反向执行的默认操作是将目标操作数的值设置为未知。前向静态分析中的默认操作是使所有基于目的操作数的值关系无效。

图 2 显示了 RETracer 根据其特殊语义单独处理的 x86/x86-64 指令。回顾一下，RETracer 的主要目标是恢复损坏的指针或数组索引是如何产生的。这就是 RETracer 只对位指令和浮点指令（如 SAL 和 FLD）执行默认操作的原因。

有些指令（如 CMOV）是有条件的。我们处理这类指令的方式与分支类似。我们假设两个条件都有可能发生，分析每个条件下的指令，并合并它们的结果。对于 CMOV，我们会采取以下措施。对于反向污点分析，我们保留目的操作数的污点，如果目的操作数有污点，则将污点传播到源操作数。对于具体的反向执行，我们将目的操作数设置为未知数，不更新源操作数。对于静态正向分析，我们将目的操作数的值标记为无效。

对于遵循 stdcall 调用约定[44]的函数调用，如果我们不对其进行分析，就需要代表被调用者解除堆栈。这对于正确跟踪堆栈至关重要。要解除堆栈，我们需要调用站点信息，以便知道是否需要解除堆栈，如果需要，堆栈指针应该调整多少。然而，PDB 文件并不包含所有间接调用的这些信息。为了缓解这一问题，我们开发了以下启发式方法来推断需要解除的堆栈大小。首先，对于对不同模块中函数的间接调用，我们确定实现该函数的模块，并使用该模块的 PDB 文件来检索函数信息。其次，对于对虚拟函数的间接调用，我们会根据 PDB 文件中的调试信息构建虚拟函数表，并使用二进制分析来推断虚拟函数表中的哪个函数正在被调用。第三，如果这两种方法都失败，我们会分析间接调用前的 PUSH 指令，以推断出需要解压缩的堆栈大小。

尾调用 [46] 是一种常见的编译器优化，可以避免在调用堆栈中添加新的堆栈帧。基于帧指针的简单栈走行无法正确识别尾调用。如果不能识别尾调用，RETracer 的后向分析就会错过跳转到被调用子程序之前的重要参数传递数据流。在 RETracer 中，我们通过检查基于调用程序中调用指令的被调用函数是否与堆栈上的被调用函数相匹配来检测尾调用。如果不匹配，我们会进一步检查第一个被调用函数的末尾是否有 JMP 指令，或者第一个和第二个被调用函数是否连续（在这种情况下，甚至连 JMP 指令也会被保存）。如果是，我们就将其视为尾调用，并一并分析两个被调用函数。

在 RETracer 中，我们目前将 11 个 Windows 模块和命名空间 std 中的所有函数列入白名单，因为它们被静态链接到每个模块中。这远远少于 !analyze 使用的数百个白名单模块和函数。更重要的是，如第 3.2.2 节所述，RETracer 会有条件地处理白名单，这让我们能够捕捉到白名单模块中的罕见错误。