POMP: Postmortem Program Analysis with Hardware-Enhanced Post-Crash Artifacts

对二进制程序进行分析，从汇编语言角度对每一条指令分析，从故障点用到的数据反向传播，遇到地址假名的情况下就进行假设分析，如果出现故障就视为不同的地址。还要单独处理一些系统调用。用到了英特尔的设备来获取运行时信息。

开源代码：https://github.com/junxzm1990/pomp.git

摘要

虽然内核转储（core dump）携带了大量信息，但在定位软件故障时，它几乎起不到信息调试辅助作用，因为它携带的信息只能显示程序到达崩溃点的部分时间顺序。最近，这种情况有了明显改善。随着硬件辅助处理器跟踪技术的出现，软件开发人员和安全分析人员可以跟踪程序的执行情况，并将其整合到内核转储中。与普通的内核转储相比，新的崩溃后人工制品为软件开发人员和安全分析人员提供了更多有关程序崩溃的线索。不过，要利用它来进行故障诊断，仍需要付出艰苦的人工努力。

在这项工作中，我们提出了 POMP，这是一种便于分析崩溃后工件的自动化工具。更具体地说，POMP 引入了一种新的反向执行机制，用于构建程序崩溃前的数据流。通过使用数据流，POMP 可以执行反向污点分析，并突出显示那些真正导致崩溃的程序语句。

为了证明 POMP 在精确定位与程序崩溃真正相关的程序语句方面的有效性，我们在 x86-32 平台的 Linux 系统上实施了 POMP，并针对 31 个不同的真实世界安全漏洞导致的各种程序崩溃进行了测试。测试结果表明，POMP 能够准确、高效地找出真正导致程序崩溃的程序语句，大大方便了故障诊断。

引言

尽管软件开发人员尽了最大努力，但软件仍不可避免地存在缺陷。当缺陷被触发时，程序通常会崩溃或异常终止。要找出软件崩溃的根本原因，软件开发人员和安全分析人员需要识别与崩溃有关的程序语句、分析这些语句，最终找出为什么会有一个坏值（如无效指针）被传递到崩溃点。一般来说，如果同时给出控制流和数据流，就能大大简化（甚至自动化）这一过程。因此，有关死后程序分析的研究主要集中在找出崩溃程序的控制流和数据流上。在所有死后程序分析技术中，记录与重放（如[10, 12, 14]）和核心转储分析（如[16, 26, 36]）最为常见。

记录和重放是一种技术，通常是对程序进行仪器化处理，以便自动记录非确定性事件（即程序的输入以及线程的内存访问交错），然后利用日志对程序进行确定性重放。从理论上讲，这种技术对程序崩溃的根本原因诊断大有裨益，因为开发人员和安全分析人员可以完全重建程序崩溃前的控制流和数据流。但在实践中，由于需要对程序进行检测，而且在正常运行过程中开销较大，因此这种技术并未被广泛采用。

与记录和回复相比，核心转储分析是一种诊断程序崩溃的轻量级技术。它不需要程序仪器，也不依赖程序执行日志。相反，它通过使用更通用的信息（即操作系统在每次进程崩溃时自动捕获的核心转储）来促进程序故障诊断。然而，核心转储只提供了故障的快照，核心转储分析技术只能从中推断出与程序崩溃有关的部分控制流和数据流。因此，核心转储并没有成为软件调试的首选。

最近，硬件辅助处理器追踪技术的发展大大改善了这种状况。英特尔 PT [6]是英特尔 CPU 的一项全新硬件功能，它的出现使软件开发人员和安全分析人员可以跟踪所执行的指令，并将其保存在循环缓冲区中。在程序崩溃时，操作系统会将这些跟踪信息纳入内核转储。由于这种崩溃后的人工制品同时包含崩溃内存的状态和执行历史，软件开发人员不仅可以检查崩溃时的程序状态，还可以完全重建导致崩溃的控制流，从而使软件调试更加翔实高效。

虽然英特尔 PT 能够帮助软件开发人员获得更多有关软件崩溃的信息线索，并将其用于软件故障的根本原因诊断，但它仍然非常耗时，而且需要大量的人工操作。正如我们将在第 2 节中讨论的那样，崩溃后工件1 通常包含大量指令。即使它所包含的执行历史可以让我们完全重建崩溃程序所遵循的控制流—如果没有自动化工具来消除那些与故障无关的指令—软件开发人员和安全分析人员仍然需要手动检查工件中的每条指令，并找出那些真正导致崩溃的指令。

为了解决这个问题，最近的研究[22]提出了一种技术方法来识别与软件故障有关的程序语句。从技术上讲，它将静态程序分析与使用英特尔 PT 的动态程序分析的合作和自适应形式相结合。虽然这种技术在促进故障诊断（尤其是由并发错误引起的故障诊断）方面被证明是有效的，但在分析由内存损坏漏洞（如缓冲区溢出或释放后使用）引起的崩溃方面，这种技术可能不太有效。这是由于内存损坏漏洞允许攻击者操纵控制流（或数据流），而静态程序分析严重依赖于程序执行不违反控制流或数据流完整性的假设。鉴于[22]中提出的技术需要使用硬件观察点以协作方式跟踪数据流，因此该技术也不太适合无法以众包方式轻松收集程序崩溃信息的情况。

在这项工作中，我们设计并开发了 POMP，这是一种新的自动化工具，可分析崩溃后的工件并找出与崩溃有关的语句。考虑到程序的控制流可能会被劫持，而且静态分析并不可靠，因此 POMP 的设计完全基于崩溃后人工制品中的信息。具体而言，POMP 引入了一种反向执行机制，该机制将崩溃后工件作为输入，分析崩溃内存并反向执行工件中的指令。有了这种反向执行的支持、POMP重建数据流，程序崩溃前所遵循的指令，然后利用逆向污点分析找出导致程序崩溃的关键指令。

本研究提出的反向执行是一种新方法。在以往的研究中，反向执行的设计都是假定内存崩溃时数据的完整性[16, 37]，或者严重依赖于内存中记录关键对象的能力[7-9, 13]。在这项工作中，考虑到软件漏洞可能会导致内存损坏，而对象记录会对正常操作造成开销，我们放宽了这一假设和数据对象记录的能力，并引入了一种递归算法。具体来说，该算法通过构建崩溃前的数据流来恢复内存足迹。反过来，它还利用恢复的内存足迹来改进数据流的构建。如有必要，该算法还会验证内存别名，确保数据流构建不会引入错误或不确定性。我们将在第 4 节详细介绍该算法。

据我们所知，POMP 是第一个可以恢复程序崩溃前数据流的工具。由于 POMP 仅依赖于崩溃后的人工制品，因此不会对正常运行造成干扰，更重要的是，即使不能以合作的方式收集崩溃报告，它也普遍适用于任何环境。最后但并非最不重要的一点是，应该指出的是，这项工作的影响不仅限于分析内存损坏漏洞导致的程序异常终止。我们提出的技术普遍适用于由其他软件漏洞（如取消引用空指针）导致的程序崩溃。我们将在第 6 节中演示这种能力。

本文接下来的内容安排如下。第 2 节定义了我们研究的问题范围。第 3 节介绍 POMP 概述。第 4 节和第 5 节详细介绍了 POMP 的设计和实现。第 6 节展示了 POMP 的实用性。第 7 节总结了与我们最相关的工作，第 8 节讨论了 POMP。最后，我们在第 9 节中结束这项工作。

贡献

总之，本文做出了以下贡献。

我们设计了 POMP，这是一种通过反向执行残留在工件中的指令来分析碰撞后工件的新技术。
我们在 32 位 Linux 上实施了 POMP，以帮助软件开发人员（或安全分析人员）找出软件缺陷，尤其是内存损坏漏洞。
我们利用可归因于 31 个不同现实世界安全漏洞的各种崩溃后工件，展示了 POMP 在促进软件调试方面的有效性。

问题范围

在本节中，我们将确定研究的问题范围。我们首先描述我们的威胁模型。然后，我们将讨论为什么即使崩溃后的工件所携带的信息能让软件开发人员完全重建程序崩溃前的控制流，故障诊断也可能是乏味而艰难的。

void test(void){
    
}
int child(int *a){
    a[0]=1;
    a[1]=2;
    return 0;
}

int main(){
    void (*func)(void);
    int var;
    func=&test;
    child(&var);
    func();
}

威胁模型

在这项工作中，我们的重点是诊断进程崩溃。因此，我们排除了不会导致运行进程意外终止的程序崩溃（如 Java 程序崩溃）。由于这项工作是通过分析崩溃后的人工制品来诊断进程崩溃的，因此我们进一步排除了那些通常不会产生人工制品的进程崩溃。例如，在 Linux 2.2 之前（包括 Linux 2.2），CPU 时限超限时的默认操作是终止进程，而不会产生崩溃后工件[3]。

如上所述，崩溃后人工制品不仅包含崩溃程序的内存快照，还包含程序崩溃前所遵循的指令。（虽然英特尔 PT 不记录无条件跳转和线性代码，但可以很容易地从崩溃后工件中的执行轨迹重建完整的执行轨迹。在没有进一步说明的情况下，我们所说的崩溃后工件中的执行跟踪是指包括条件分支、无条件跳转和线性代码在内的跟踪。）回想一下，这项工作的目标是识别与崩溃实际相关的程序语句（即指令）。因此，我们假定记录在工件中的指令跟踪足够长，而且程序失败的根本原因总是被包含在内。换句话说，我们假设崩溃后的工件中包含了所有实际导致崩溃的指令。我们认为这是一个切合实际的假设，因为软件缺陷通常靠近崩溃地点 [19, 27, 39] 。操作系统很容易分配一个内存区域来存储从缺陷触发到实际崩溃的执行轨迹。由于安全分析人员可能无法获得崩溃程序的源代码，他们只能通过崩溃后留下的执行轨迹来确定软件缺陷，因此需要注意的是，我们并不假定崩溃程序的源代码是可用的。

挑战

如前所述，英特尔 PT 在循环缓冲区中记录程序的执行情况。当软件缺陷被触发并导致崩溃时，循环缓冲区通常已经积累了大量的条件分支。在对这些分支进行控制流重构后，一个完整的执行跟踪可能会携带十亿条以上的指令。即使将从故障触发处到崩溃发生处的跟踪放大，软件开发人员（或安全分析人员）也可能要面对数以万计的指令。因此，对于软件开发人员来说，通过执行跟踪来诊断软件故障的根本原因是一件乏味而艰巨的工作。

事实上，即使执行轨迹简明扼要，对于通常采用的人工诊断策略（如逆向分析）来说仍然具有挑战性。在此，我们使用表 1 中的一个玩具示例来详细说明这一挑战。如表所示，由于第 7 行出现溢出，程序在第 16 行崩溃。程序崩溃后，在图 1 所示的崩溃后工件中留下了执行跟踪。除跟踪外，该工件还捕获了崩溃内存的状态，如第 T20 列所示的值。

要通过逆向分析诊断图 1 所示程序崩溃的根本原因，软件开发人员或安全分析人员通常会反向跟踪执行轨迹，检查寄存器 eax 中的坏值是如何传递到崩溃位置的（即图 1 中所示的指令 A20）。在此过程中，当分析到指令 A19 时，他的分析工作可能会过早受阻。在该指令中，mov 覆盖了寄存器 eax，而针对该指令的反向操作缺乏恢复其先前值的信息。

要解决这个问题，一个简单直接的办法是在反向分析到不可反转指令时执行前向分析。以指令 A19 为例。通过使用定义链，我们可以构建一个数据流。然后，我们可以很容易地观察到，指令 A15 指定了寄存器 eax 的定义，并且该定义可以到达指令 A19，而没有任何其他定义介入。因此，我们可以恢复寄存器 eax 的值，从而完成指令 A19 的逆操作。

虽然前向和后向分析为安全分析人员提供了构建数据流的有效方法，但这还不足以完成程序故障诊断。还是以图 1 所示的执行跟踪为例。当后向分析经过指令 A15 到达指令 A14 时，通过前向分析，安全分析人员可以很快发现，执行 A14 后寄存器 eax 中的值取决于指令 A12 和 A13。因此，本能的反应是检索指令 A12 中 [ebp+0x8] 指定的内存区域中存储的值。然而，指令 A14 中 [ebp+0x8] 和 [eax] 所指示的内存可能互为别名。如果没有解决内存别名的方法，就无法确定指令 A14 中的定义是否中断了指令 A12 和 A13 的数据流。因此，程序故障诊断只能无果而终。

概述

在本节中，我们首先介绍本研究的目标。然后，我们讨论我们的设计原则，接着介绍 POMP 如何进行程序死后分析的基本思想。

目标

软件故障诊断的目标是从执行跟踪所包含的指令中找出故障的根本原因。然而，如果崩溃后的工件包含了程序崩溃前执行过的大量指令的执行轨迹，那么轨迹中的任何指令都有可能导致程序崩溃。正如我们在上一节中所述，对于软件开发人员（或安全分析人员）来说，通过跟踪挖掘并找出程序崩溃的根本原因是一件繁琐而艰难的工作。因此，这项工作的目标是只找出那些真正导致程序崩溃的指令。换句话说，给定崩溃后的工件，我们的目标是突出并向软件开发人员（或安全分析人员）展示导致程序崩溃的最少指令集。在这里，我们的假设是，实现这一目标可以大大减少人工查找软件故障根源的工作量。

设计原则

为了实现上述目标，我们将 POMP 设计为对二进制文件进行死后分析（尽管原则上也可以在源代码层面上进行分析），因为这一设计原则可以为软件开发人员和安全分析人员带来以下好处。我们的设计原则无需将 POMP 与以特定编程语言编写的程序集绑定，首先允许软件开发人员使用单一工具分析以不同语言（如汇编代码、C/C++ 或 JavaScript）编写的程序的崩溃情况。其次，我们的设计选择消除了源代码和二进制文件之间的转换所带来的复杂性，因为崩溃后的工件带有二进制文件中的执行跟踪，可直接用于二进制层面的分析。第三，由于选择了我们的设计，POMP 可以普遍应用于软件故障分流或分类，在这种情况下，崩溃后工件是唯一的分析资源，而崩溃程序的源代码通常是不可用的[16, 18]。

技术路线

如第 1 节所述，如果软件开发人员和安全分析人员能够获得程序崩溃前的控制流和数据流，那么识别与程序崩溃有关的指令就会非常方便。

我们依靠英特尔 PT 来跟踪程序的控制流，并将其整合到崩溃后的人工制品中。PT 是近期英特尔处理器（如 Skylake 系列）的一项低开销硬件功能。它的工作原理是捕获每个硬件线程上的软件执行信息[6]。捕获到的信息被整理成不同类型的数据包。关于程序流程的数据包编码了控制流的传输（如间接分支的目标和条件直接分支的已执行/未执行指示）。有了控制流传输和程序二进制文件，我们就能完全重建已执行指令的轨迹。第 5 节将详细介绍我们的配置和 PT 的使用。

由于崩溃后的人工制品已经承载了崩溃程序所遵循的控制流，因此重点是从崩溃程序留下的崩溃后人工制品中重建数据流。

为了重建与程序故障有关的数据流，POMP 引入了反向执行机制，以恢复崩溃程序的内存足迹。这是因为，如果程序崩溃前的机器状态都可用，数据流就很容易推导出来。下面，我们将简要介绍如何通过反向执行恢复内存足迹和建立数据流，以及如何利用该数据流完善真正与程序崩溃有关的指令。

我们的反向执行机制是上述正反向分析的延伸。它不仅能自动进行前后向分析，使指令的反向操作变得毫不费力，还能自动验证内存别名，确保反向操作不会引入错误或不确定性。

利用这种反向执行机制，POMP 可以轻松恢复每条指令执行前的机器状态。在此，我们以图 1 所示的示例进行说明。反向执行通过上述正向和反向分析完成指令 A19 的反向操作后，可以轻松还原寄存器 eax 中的值，从而还原指令 A19 执行前的内存足迹（参见 T18 时刻的内存足迹）。有了这个内存足迹，指令 A18 执行前的内存足迹也就很容易恢复了，因为算术指令不会对内存产生不可逆转的影响（见 T17 时刻的内存足迹）。

由于指令 A17 可被视为 mov eip, [esp] 然后添加 esp, 0x4，而指令 A16 则等同于 mov ebp, [esp] 然后添加 esp, 0x4，因此反向执行可以按照上述处理 mov 和算术指令的方案，进一步还原它们执行前的内存足迹。图 1 展示了这两条指令执行前的内存足迹。

回想一下，在对指令 A15 执行反向操作时，正向和反向分析无法确定指令 A12 中指定的 [ebp+0x8] 的使用是否能在指令 A15 执行之前到达该位置，因为 A14 中的 [eax] 和 A12 中的 [ebp+0x8] 可能只是访问同一内存位置中数据的不同符号名。

为了解决这个问题，一种本能的反应是使用 [11] 中提出的值集分析算法。然而，值集分析假设执行符合标准编译规则。当发生内存损坏并导致崩溃时，这些规则通常会被违反，因此，值集分析很可能会出错。此外，值集分析产生的信息不够精确，不适合反向执行来验证内存别名。在这项工作中，我们采用假设检验来验证可能的内存别名。具体来说，我们的反向执行创建了两个假设，一个假设两个符号名称互为别名，另一个假设相反。然后，它通过模拟指令的反向操作来测试每个假设。

让我们继续图 1 中的示例。现在，反向执行可以产生两种假设，一种假设 [eax] 和 [ebp+0x8] 互为别名，另一种假设则相反。对于第一种假设，在对指令 A15 执行反向操作后，T14 处的内存足迹所携带的信息将有三个约束，包括 eax = ebp + 0x8、eax = [ebp + 0x8] + 0x4 和 [eax] = 0x2。对于第二个假设，约束集包括 eax != ebp + 0x8、eax = [ebp + 0x8] + 0x4 和 [eax] = 0x2。通过观察 T14 处的内存足迹和检查这两个约束集，逆向执行可以轻松地拒绝第一个假设，接受第二个假设，因为第一个假设的约束 eax = ebp + 0x8 不成立。这样，反向执行就能高效、准确地恢复 T14 时刻的内存足迹。在 T14 时恢复内存足迹后，逆向执行可以使用我们上面讨论的方案进一步恢复早期的内存足迹，图 1 展示了这些内存足迹的一部分。

有了恢复的内存足迹，软件开发人员和安全分析人员就能轻松推导出相应的数据流，从而准确找出真正导致崩溃的指令。在我们的工作中，POMP 通过使用反向污点分析实现了这一过程的自动化。为了说明这一点，我们继续前面提到的例子，以图 1 所示的内存足迹为例。如前所述，在本例中，寄存器 eax 中的坏值是通过指令 A19 传递的，该指令将内存 [ebp-0xC] 中的坏值复制到寄存器 eax 中。通过检查恢复的内存足迹，POMP 很容易发现 [ebp-0xC] 所指示的内存与指令 A14 中 [eax] 所指示的内存地址相同。这意味着坏值实际上是从指令 A14 传播过来的。因此，POMP 突出显示了指令 A19 和 A14，并认为它们是导致崩溃的真正原因。我们将在第 4 节详细阐述后向污点分析。

设计

反向执行

在此，我们将介绍 POMP 在执行反向执行时所遵循的算法。具体来说，我们的算法有两个步骤—使用定义链构建和内存别名验证。下面，我们将依次阐述这两个步骤。

使用-定义链条结构

第一步，算法首先对执行跟踪进行反向解析。对于跟踪中的每条指令，它都会根据该指令的语义提取相应变量的用途和定义，然后将它们与之前构建的用途定义链链接起来。例如，给定图 1 所示由指令 A20 和 A19 衍生出的初始使用定义链，POMP 从指令 A18 中提取使用和定义，并将它们链接到该链的头部（见图 2）。

从图中我们可以看到，定义（或使用）包括三个要素—指令 ID、使用（或定义）说明和变量值。此外，我们还可以看到，使用-定义关系不仅包括操作数之间的关系，还包括操作数与所包含的基寄存器和索引寄存器之间的关系（见图 2 中指令 A19 的使用和定义）。

每次添加使用（或定义）时，我们的算法都会检查相应变量的可达性，并尝试解析链上的这些变量。更具体地说，算法会检查链上的每个使用和定义，并确定相应变量的值是否可以解析。所谓解析，是指变量满足以下条件之一：该变量的定义（或使用）可以到达链的末尾，而不需要任何其他定义的介入；二：在连续使用时，相应变量的值是可用的；三：在前端有相应的解析定义，就可以使用该变量； 四：该变量的值可以直接从该指令的语义中得出（例如，指令 mov eax, 0x00 时，变量 eax 等于 0x00）。

为了说明这一点，我们以图 2 中的例子为例。在我们的算法将定义 def:esp=esp+4 连接到链上后，大多数变量都已被解析，可达性检查显示该定义可以到达链的末端。因此，算法会从崩溃后工件中获取值，并将其赋值给 esp（见圆圈中的值）。完成赋值后，我们的算法会将更新后的定义在链中进一步传播，并尝试使用更新来解析变量，而这些变量的值尚未分配。在这种情况下，链上的所有定义和使用都不会从这一传播中受益。传播完成后，我们的算法会进一步追加 use use:esp，并重复这一过程。与定义 def:esp=esp+4 的过程略有不同的是，对于这一用途，变量 esp 无法通过上述可达性检查进行解析。因此，我们的算法从指令 A18 的语义中推导出 esp 的值（即 esp=esp-4）。

在使用定义链构建过程中，我们的算法还通过两种方式跟踪约束。一种方法是，我们的算法通过检查指令语义来提取约束。以指令 A19 和虚指令序列 cmp eax, ebx; ⇒ ja target; ⇒ inst_at_target 为例。我们的算法分别提取了相等约束 eax=[ebp-0xc]和不等式约束 eax>ebx。从另一个角度看，我们的算法是通过检查 usedefine 关系来提取约束的。特别是，一：当一个变量的定义可以达到其连续的使用而不需要中间的定义时，我们的算法会提取一个约束，表明该定义中的变量与使用中的变量共享相同的值。二：当一个变量的两次连续使用之间没有遇到定义时，我们的算法会提取一个约束条件，表明两次使用中的变量具有相同的值。三： 变量被解析后，我们的算法会提取一个约束，表示该变量等于解析后的值。维护这些约束的原因是为了能够执行下一节讨论的内存别名验证。

在解析变量和传播定义（或使用）的过程中，我们的算法通常会遇到这样的情况：指令试图为内存区域所代表的变量赋值，但利用链上的信息无法解析该区域的地址。例如，图 1 中的指令 A14 代表内存写入，其地址由寄存器 eax 表示。从图 3 所示的与此示例相关的使用定义链中，我们可以很容易地观察到 A13 def:eax 节点不携带任何值，尽管它的影响可以传播到 A14 def:[eax] 节点，而不需要任何其他介入定义。

从图 3 所示的示例中我们可以看到，当出现这种情况时，像 A14 def:[eax] 这样的定义有可能会中断对内存访问所代表的其他变量的定义和使用。例如，考虑到 [ebp+0x08] 和 [eax] 所表示的内存可能是彼此的别名，定义 A14 def:[eax] 可能会阻止 A12 use:[ebp+0x08] 的可达性。因此，在构建使用定义链的步骤中，我们的算法会将这些未知的内存写入视为中间标记，并相应地阻止先前的定义和使用。这种保守的设计原则确保了我们的算法不会给内存足迹恢复带来错误。

上述前后向分析主要是为了发现使用定义关系。其他技术，如静态程序切片[34]，也能识别使用定义关系。然而，我们的分析是新颖的。具体来说，我们的分析能发现使用定义关系，并利用它们来恢复内存足迹。反过来，它又利用恢复的内存足迹进一步查找使用定义关系。这种交错方法可以识别出更多的使用定义关系。此外，我们的分析以保守的方式处理内存别名，并以无差错的方式进行验证。这有别于以往通常采用不太严格的方法（如值集分析）的技术。下一节将详细介绍我们如何解决内存别名问题。

内存别名问题

虽然上述设计原则可以防止在恢复内存足迹时引入错误，但这种保守的策略会阻碍数据流的构建，并限制变量的解析能力（见图 3 所示的流块和不可恢复变量）。因此，我们算法的第二步就是尽量减少上述策略带来的副作用。

由于上述保守设计的根源在于 “不可判定 “的内存别名，我们解决这一问题的方法是引入一种假设检验机制，检验一对符号名称是否指向相同的内存位置。更具体地说，在给定一对符号名称后，该机制会提出两个假设，一个假设它们互为别名，另一个假设相反。根据假设，我们的算法会相应地调整使用定义链和约束条件。例如，假设 [eax] 不是 [ebp+0x8] 的别名，我们的算法就会提取不等式约束 eax !=ebp+0x8 并释放图 3 所示的代码块，使 A12 use:[ebp+0x8] 进一步传播。

在传播过程中，我们的算法会遍历链上的每个节点，检查新传播的数据流是否会导致冲突。冲突通常有两种类型。最常见的是不一致的数据依赖，在这种情况下，约束条件与上面传播的数据不匹配（例如第 3 节中讨论的例子）。除了常见的冲突外，另一种类型的冲突是无效数据依赖，即变量携带无效值，而该值本应使崩溃程序提前终止或遵循不同的执行路径。例如，在某个假设下建立的使用定义链中，演练发现某个寄存器携带了一个无效地址，而该无效值应使崩溃程序在实际崩溃地点之前的某个地点终止。

不容置疑的是，一旦观察到约束冲突，我们的算法就可以轻松地拒绝相应的假设，并认为这对符号名称互为别名（或非别名）。但是，如果这些假设都没有产生约束冲突，这就意味着我们的假设检验缺乏证据。一旦出现这种情况，我们的算法就会保留当前假设，并执行额外的假设检验。原因在于，新的假设检验可能有助于移除第一步中保守放置的额外干扰标记，从而为保持检验提供更多信息证据，以拒绝相应的假设。

为了说明这一点，我们以图 4 所示的一个简单例子为例。第一步完成后，我们假设算法保守地将 A2 def:[R2] 和 A4 def:[R5] 视为阻碍数据流传播的中间标记。按照上述步骤，我们反向分析踪迹并做出假设，即[R4]和[R5]不是别名。有了这个假设，中间标签之间的数据流就可以传播，我们的算法就可以据此检查冲突。假设新传播的数据流不足以否定我们的假设。我们的算法会保留当前的假设，并提出一个额外的假设，即 [R1] 和 [R2] 互不别名。有了这个新假设，就会有更多数据流通过，我们的算法就能获得更多信息，从而有可能帮助我们拒绝假设。值得注意的是，如果任何一个假设未能被拒绝，我们的算法会保留第一步保守放置的中间标记。

不难发现，我们的假设检验可以很容易地扩展为递归过程，即提出更多的假设，直到可以拒绝这些假设为止。然而，递归假设检验的计算复杂度是指数级的。更糟糕的情况是，在反向执行时，每条指令的反向操作都可能需要别名验证，而每次验证都可能需要进一步的别名检查。当出现这种情况时，上述算法就成了不切实际的解决方案。因此，这项工作根据经验强制假设检验最多遵循两个递归深度。正如我们将在第 6 节中展示的，这种设置允许我们不在以下情况下执行反向执行

讨论

在程序执行过程中，它可能会调用系统调用，从而将执行过程拖入内核空间。正如我们将在第 6 节讨论的那样，我们并没有将英特尔 PT 设置为跟踪内核空间的执行情况。因此，直觉告诉我们，失去执行跟踪可能会给我们的反向执行带来问题。但实际上，大多数系统调用都不会修改用户空间的寄存器和内存。因此，我们的逆向执行可以简单地忽略这些系统调用的逆操作。对于有可能影响崩溃程序内存足迹的系统调用，我们的逆向执行将按以下方式处理。

一般来说，系统调用只有在操作崩溃程序存储的寄存器值或触及用户空间的内存区域时，才会影响内存足迹。因此，我们以不同的方式处理系统调用。对于可能影响为崩溃程序保存值的寄存器的系统调用，我们的算法只需在使用定义链上引入一个定义。例如，系统调用 read 会覆盖寄存器 eax 的返回值，我们的算法会相应地在使用定义链中添加 def:eax=? 的定义。对于在用户空间操作内存内容的系统调用（如 write 和 recv），我们的算法会检查受该调用影响的内存区域。具体来说，它试图通过调用前执行的指令来确定内存区域的起始地址和大小。这是因为起始地址和大小通常由参数指示，而这些参数在调用前已由这些指令处理过。按照这一步骤，如果我们的算法确定了该内存区域的大小，就会相应地将定义添加到链中。否则，我们的算法就会将该系统调用视为中间标记，阻止通过该调用的传播3。这样做的原因是，非确定内存区域有可能与用户空间中的任何内存区域重叠。

逆向污点分析

回顾一下，这项工作的目标是找出真正与程序崩溃有关的指令。在第 3 节中，我们简要介绍了后向污点分析如何在实现这一目标的过程中发挥作用。下面，我们将介绍更多细节。

要进行后向污点分析，POMP 首先要确定一个汇。一般来说，程序崩溃源于两种情况—执行无效指令或引用无效地址。对于第一种情况，POMP 将程序计数器 (eip) 视为汇，因为执行无效指令表明 eip 带有坏值。对于第二种情况，POMP 将普通寄存器视为汇，因为它持有指向无效地址的值。以图 1 所示为例。POMP 将寄存器 eax 视为寄存器汇，因为从寄存器 eax 保存的地址获取无效指令会导致程序崩溃。

POMP 在确定了 “汇 “之后，就会对 “汇 “进行 “污点 “处理，并向后进行 “污点 “传播。在向后传播的过程中，POMP 会查找上述使用定义链，并确定污点变量的定义。这种识别的标准是确保该定义可以到达污点变量，而没有任何其他定义介入。继续上面的例子。将汇值 eax 作为初始污点变量，POMP 在链上选择 A19 def:eax=[ebp-0xc]，因为该定义可以在没有干预的情况下到达污点变量 eax。

POMP 会根据确定的定义解析该定义，并将污点传递给新变量。由于定义中包含的任何变量都有可能导致污点变量损坏，因此 POMP 选择并将污点传递给的变量包括所有操作数、基数和索引寄存器（如果有）。例如，通过解析定义 A19 def:eax=[ebp-0xc]，POMP 确定了变量 ebp 和 [ebp-0xc]，并将污点传递给这两个变量。我们不难发现，这种污点传播策略可以保证 POMP 不会漏掉程序崩溃的根本原因，尽管它过度获取了一些实际上并没有导致程序崩溃的变量。在第 6 节中，我们将评估并讨论过度污染的效果。

在向内存访问（如[R0]）指示的变量传递污点时，需要注意的是 POMP 可能无法识别与内存相对应的地址（如变量[R0]的未知 R0）。因此，一旦出现这种情况，POMP 就会停止对该变量的污点传播，因为污点有可能传播到定义为 def:[Ri]（其中 Ri 是寄存器）的任何变量。

与反向执行中的情况类似，在反向执行污点传播时，POMP 可能会遇到链上的定义干扰传播。例如，给定一个污点变量[R0]和一个 R1 未知的定义 def:[R1]，POMP 无法确定 R0 和 R1 是否具有相同的值，因此 POMP 应将污点传递给变量[R1]。出现这种情况时，POMP 会遵循上述假设检验的思路，检查两个变量是否共享相同的地址。理想情况下，我们希望通过假设检验来解决未知地址的问题，这样 POMP 就能相应地传递该污点。然而，在实际操作中，假设检验可能会拒绝失败。因此，当 “拒绝失败 “发生时，POMP 会在中间定义中对变量进行过度污染。同样，这也可以确保 POMP 不会漏掉根本原因。

实现

我们为 Linux 32 位系统实现了 POMP 原型，该系统采用 Linux 内核 4.4，运行于配备 16 GB 内存的英特尔 i76700HQ 四核处理器（第六代 Skylake 处理器）上。我们的原型由两个主要部分组成一：实现上述反向执行和反向污点分析的子系统，以及二：利用英特尔 PT 跟踪程序执行的子系统。我们的实现总共包含约 22,000 行 C 代码，我们将在 https://github.com/junxzm1990/pomp.git 上公开这些代码。下面，我们将介绍一些重要的实现细节。

根据上述设计说明，我们实现了 65 个不同的指令处理程序，以执行反向执行和反向污点分析。除了这些处理程序，我们还分别在 libelf [2] 和 libdisasm [1] 的基础上构建了内核转储器和指令解析器。请注意，对于具有相同语义的指令（如 je、jne 和 jg），我们用一个唯一的处理程序来处理它们的反向操作。为了跟踪约束条件并进行验证，我们重新使用了 Z3 定理验证器 [5, 17]。

为了使英特尔 PT 能够以正确、可靠的方式记录执行情况，我们实施了如下第二个子系统。我们使英特尔 PT 能够在物理地址表 (ToPA) 模式下运行，这种模式允许我们在多个不连续的物理内存区域中存储 PT 数据包。我们在 ToPA 中添加了一个指向 16 MB 物理内存缓冲区的入口。在我们的实现中，我们使用该缓冲区来存储数据包。为了跟踪缓冲区是否被完全占用，我们清除了 END 位并设置了 INT 位。通过这种设置，英特尔 PT 可以在缓冲区被完全占用时发出性能监控中断信号。考虑到中断可能会导致 PT 数据包的潜在丢失，我们进一步分配了一个 2 MB 的物理内存缓冲区来保存那些可能被丢弃的数据包。在 ToPA 中，我们引入了一个额外的条目来引用该缓冲区。

在硬件层面，英特尔 PT 缺乏区分每个进程内线程的能力。因此，我们还拦截了上下文切换。这样，我们的系统就能检查切换进来和切换出去的线程，并单独存储线程的 PT 数据包。具体来说，对于软件开发人员和安全分析人员感兴趣的每个线程，我们都会在其用户空间分配一个 32MB 的循环缓冲区。每次切换线程时，我们都会将存储在上述物理内存缓冲区中的 PT 数据包迁移到用户空间中相应的圆形缓冲区。迁移后，我们还会重置相应的寄存器，确保物理内存缓冲区可用于为其他相关线程保存数据包。我们的经验实验表明，在连续的上下文切换之间，上述 16 MB 缓冲区不可能被完全占用，而 POMP 在切换之间保存所有数据包并不困难。

考虑到英特尔 CPU 利用监控模式访问防御（SMAP）来限制从内核到用户空间的访问，我们的实现在数据包迁移之间切换 SMAP。此外，我们对英特尔 PT 进行了配置，以排除与控制流切换无关的数据包（如定时信息），并在执行陷阱进入内核空间时暂停跟踪。这样，POMP 就能记录足够长的执行跟踪日志。最后，我们在 Linux 内核中引入了新的资源限制 PT_LIMIT。有了它，软件开发人员和安全分析人员不仅可以选择跟踪哪些进程，还可以方便地配置循环缓冲区的大小。

评估

在本节中，我们将利用现实世界中的漏洞所导致的崩溃来证明 POMP 的实用性。更具体地说，我们将介绍 POMP 的效率和有效性，并讨论 POMP 未能正确处理的崩溃问题。

设置

为了证明 POMP 的实用性，我们从 Offensive Security Exploit Database Archive [4] 中获取的 31 个真实世界 PoCs 中选择了 28 个程序，并以其崩溃情况对 POMP 进行了基准测试。表 2 显示了这些崩溃程序，并总结了相应的漏洞。我们可以看到，所选程序涵盖的范围很广，既有像 BinUtils 这样代码行数超过 690K 的复杂软件，也有像 stftp 和 psutils 这样代码行数不到 2K 的轻量级软件。

关于导致崩溃的漏洞，我们的测试语料库不仅包括内存损坏漏洞（即堆栈和堆溢出），还包括空指针取消引用和无效释放等常见软件缺陷。之所以这样选择，是为了证明，除了内存损坏漏洞，POMP 还可以普遍适用于其他类型的软件缺陷。

在32个PoC中，有11个进行了代码注入（如nginx-1.4.0），一个进行了返回到libc的攻击（aireplay-ng-1.2b3），另一个通过面向返回编程进行了利用（mcrypt-2.5.8）。这些漏洞要么因为没有考虑执行环境的动态变化（如ASLR），要么在接管控制流之前错误地污染了关键数据（如指针），从而导致易受攻击程序崩溃。其余 18 个 PoC 是为了简单地触发缺陷而创建的，如在堆栈缓冲区中溢出大量随机字符（如 BinUtils-2.15）或导致执行时使用空指针（如 gdb-7.5.1）。这些 PoC 引起的崩溃与随机练习中发生的崩溃类似。

实验设计

对于表 2 中显示的每个程序崩溃，我们都进行了人工分析，目的是找出真正导致该程序崩溃的最小指令集。我们将人工分析结果作为基本事实，并与 POMP 的输出结果进行比较。通过这种方式，我们验证了 POMP 在促进故障诊断方面的有效性。更具体地说，我们将人工识别的指令与 POMP 确定的指令进行了比较。这种比较的重点包括：一：检查该崩溃的根本原因是否包含在 POMP 自动识别的指令集中；二：研究 POMP 的输出是否涵盖了我们手动追踪到的最小指令集；以及三：探索 POMP 是否能显著减少软件开发人员（或安全分析人员）必须手动检查的执行跟踪。

为了评估 POMP 的效率，我们记录了它发现真正与每个程序崩溃有关的指令所花费的时间。对于每个测试用例，我们还记录了 POMP 反向执行的指令，以便研究效率与反向执行指令数量之间的关系。

考虑到找出根本原因并不需要反向执行英特尔 PT 记录的全部跟踪，值得注意的是，我们只选择并利用了部分执行跟踪进行评估。在这项工作中，我们的选择策略遵循一种迭代程序，即首先引入崩溃函数的指令进行反向执行。如果部分跟踪不足以发现根本原因，我们就回溯先前调用的函数，然后逐个函数引入指令，直到 POMP 可以覆盖根本原因为止。

实验结果

表 2 显示了我们的实验结果。除了测试用例 0verkill 和 aireplay-ng，我们观察到每个根本原因都包含在 POMP 确定的指令集中。通过上述比较，我们还发现每组指令都包含了我们手动识别的相应指令（即基本事实）。这些观察结果表明，POMP 能够有效定位真正导致程序崩溃的指令。

与 POMP 需要反向执行的指令相比，我们发现最终被玷污的指令要少得多。例如，反向分析需要检查 10905 条指令，才能找出 Unalz 程序崩溃的根本原因，而 POMP 只突出显示了 14 条指令，其中一半与崩溃真正相关。鉴于反向污点分析模仿了软件开发人员（或安全分析人员）诊断程序故障根源的典型方式，这一观察结果表明 POMP 在减少故障诊断的人工工作量方面具有巨大潜力。

除测试用例 coreutils 外，POMP 生成的指令集一般都包含一定数量实际上不会导致崩溃的指令。还是以 Unalz 为例。POMP 过度篡改了 7 条指令，并将其包含在所识别的指令集中。在使用 POMP 的过程中，虽然这意味着软件开发人员需要投入额外的精力来处理那些与崩溃无关的指令，但这并不意味着 POMP 发现真正与崩溃有关的指令的能力较弱。事实上，与在故障诊断中需要手动检查的数百条甚至数千条指令相比，过度污染带来的额外工作量微乎其微，可以忽略不计。

回想一下，为了捕捉根本原因，POMP 的设计对所有可能导致坏值传播的变量都进行了污点分析。随着我们的反向污点分析越来越多地遍历指令，不难想象，越来越多的变量可能被污点化，导致与这些变量相对应的指令被视为真正与程序崩溃有关的指令。因此，在这些测试用例中，我们通常会观察到更多的指令被过度污染，在这些测试用例中，POMP 需要反向执行更多的指令，以覆盖故障的根本原因。

正如我们在第 4 节中所讨论的，理想情况下，POMP 可以采用递归假设检验来对未知内存访问指令执行逆操作。然而，出于计算复杂性的考虑，我们将递归深度限制在最多两个深度。因此，反向执行会留下一定量的无法解决的内存。在表 2 中，我们说明了在执行 2 深度假设检验后仍无法解决的内存地址数量。令人惊讶的是，我们发现即使 POMP 无法恢复一定量的内存，它仍能有效地发现与程序崩溃有关的指令。这意味着我们的设计合理地平衡了 POMP 的实用性及其计算复杂性。

直觉表明，无法解析的内存数量应与 POMP 反向执行的指令数量相关。这是因为不可解内存的影响可能会随着反向执行指令的增多而扩大。虽然这通常是正确的，但从 corehttp 测试用例中观察到的结果表明，执行轨迹过长并不一定会扩大未知内存访问的影响。随着更多指令被反向执行，POMP 可能会获得更多证据来拒绝它无法确定的假设，从而使未知内存访问问题得到解决。有鉴于此，我们推测 POMP 不仅能有效促进故障诊断，或许还有助于反向执行较长的跟踪指令。因此，在未来的工作中，我们将在不同的环境中探索这种能力。

在表 2 中，我们还说明了 POMP 在反向执行和反向污点分析过程中所花费的时间。我们可以很容易地观察到，POMP 通常在几分钟内完成计算，所花费的时间一般与 POMP 需要反向执行的指令数量成正比。这一观察结果背后的原因很简单。当反向执行处理的指令越多，通常会遇到更多的内存别名。在验证内存别名时，POMP 需要进行假设检验，而假设检验的计算量和耗时都稍显密集。

在测试用例 aireplay-ng 中，POMP 无法帮助进行故障诊断，我们仔细观察了被污染的指令和反向执行的指令。在 aireplay-ng 崩溃之前，我们发现程序调用了系统调用 sys_read，将数据块写入某个内存区域。由于数据块的大小和内存地址都是在寄存器中指定的，而反向执行无法还原这些寄存器，因此 POMP 将 sys_read 视为一个 “超级 “干预标记，它阻止了许多定义的传播，使得 POMP 的输出对故障诊断的参考价值降低。

与 aireplay-ng 不同，0verkill 的失败原因是 PT 日志不足。如表 2 所示，这种情况对应的漏洞是整数溢出。为了触发这一安全漏洞，我们在实验中使用的 PoC 会主动累积一个整数变量，使 PT 日志中充满算术计算指令，但却没有与根本原因相对应的指令。因此，我们观察到 POMP 只能玷污与崩溃相关的一条指令。我们相信，如果软件开发人员（或安全分析人员）能够扩大 PT 缓冲区的容量，这种情况就会很容易解决。

讨论

在本节中，我们将讨论当前设计的局限性、我们的心得体会以及未来可能的发展方向。

多个线程。POMP 只关注分析崩溃线程产生的崩溃后工件。因此，我们假定崩溃的根本原因就在该线程执行的指令中，而且在该线程崩溃之前，其他线程不会干预该线程的执行。但实际上，这一假设可能并不成立，崩溃后工件中包含的信息对于根本原因诊断可能并不充分，甚至会产生误导。

虽然多线程问题确实限制了使用 POMP 的安全分析人员找出程序崩溃根本原因的能力，但这并不意味着 POMP 的失败，也不会因为以下原因而大大降低 POMP 的实用性。首先，先前的一项研究[31]已经表明，软件崩溃的很大一部分只涉及崩溃线程。因此，我们认为 POMP 仍有利于软件故障诊断。其次，POMP 的失败根源在于执行跟踪不完整。因此，我们相信，只要增强进程跟踪功能，记录执行时序，POMP 就能合成完整的执行跟踪，使 POMP 正常工作。作为未来工作的一部分，我们将在下一版 POMP 中集成这一扩展功能。

即时本地代码。英特尔 PT 记录了执行分支指令的地址。使用这些地址作为索引，POMP 可从可执行文件和库文件中检索指令。不过，程序也可以使用即时编译（JIT）功能，在编译过程中即时生成二进制代码。对于使用这种 JIT 功能组装的程序（如 JavaScript 引擎），POMP 不太可能有效，尤其是当崩溃后人工制品无法捕获映射到内存中的 JIT 本地代码时。

为了使 POMP 能够处理这类程序，我们将在未来增强 POMP 的功能，跟踪和记录运行时生成的本地代码。例如，我们可以监控可执行内存，并相应地转储 JIT 本地代码。请注意，这种扩展并不需要对反向执行和反向污点分析进行任何重新设计，因为对 JIT 本地代码的限制也是由不完整的执行跟踪（即无法重建程序崩溃前执行的所有指令）造成的。

结论

在本文中，我们在 Linux 系统上开发了 POMP，用于分析崩溃后的人工痕迹。我们的研究表明，POMP 可以大大减少程序故障诊断的人工工作量，使软件调试更加翔实高效。由于 POMP 的设计完全基于崩溃后工件中的信息，因此所提出的技术可普遍应用于诊断由各种软件缺陷导致的各种编程语言编写的程序崩溃。

我们利用真实世界中与 31 个软件漏洞相关的程序崩溃来证明 POMP 的有效性。我们发现，POMP 可以反向重建崩溃程序的内存足迹，并准确识别真正导致程序崩溃的程序语句（即指令）。根据这一发现，我们有把握地得出结论：POMP 可以大大减少软件开发人员（或安全分析人员）需要手动检查的程序语句。

阅读笔记: Postmortem Program Analysis with Hardware-Enhanced Post-Crash Artifacts