Author: Jun Xu, The Pennsylvania State University;
Code: https://github.com/junxzm1990/pomp
Topic: Root Cause, Taint
URL: https://www.usenix.org/conference/usenixsecurity17/technical-sessions/presentation/xu-jun
Where: 26th USENIX Security Symposium
Year: 2017
Introducetion: 根因分析：使用了数据流、反向污点分析

本文只是学习并记录笔记，如有错误或不足请谅解指正，谢谢！

摘要

core dump（核心转储）拥有许多信息，但不能作为定位程序崩溃的调试信息，因为它携带的信息只说明了程序到达崩溃点的部分时间顺序。

随着硬件辅助处理器跟踪的出现，可以跟踪程序执行，并将其集成至core dump中，并提供了更多的有关程序崩溃的线索，但这依然需要许多的人工工作来完成崩溃诊断。

POMP：自动化地对crash进行分析（引入了一种新的逆向执行机制来构造程序崩溃之前所遵循的数据流），通过使用数据流，POMP执行向后的污点分析，并突出显示那些实际上导致崩溃的程序语句。

背景与问题

对程序的崩溃分析主要集中在找出程序造成crash的控制流与数据流。

崩溃分析的主要技术：

• Record-and-replay 方法：记录程序崩溃的过程，之后回放这一过程记录。（例如：PANDA-RE） 优点：对程序崩溃的根因分析有很大的好处，可以在崩溃之前重构控制流和数据流 缺点：实际上，对程序插桩以及开销要求较大，未被广泛采用
• core dump分析 方法：直接使用程序崩溃时产生的core dump进行进行分析 优点：不需要程序插桩，也不依赖程序执行的记录 缺点：由于只有故障的快照，因此只能推断出与程序崩溃有关的部分控制流和数据流信息

硬件辅助处理器跟踪方面的进步改善了这一情况（Intel PT 一个新的硬件特性的出现），使得可以跟踪执行的指令，并保存在一个循环的缓冲区中。这不仅可以检查崩溃时的程序状态，还可以完全重构导致崩溃的控制流。但由于指令数量庞大，还是需要手动分析哪些是导致崩溃的指令。

已有的方案：

结合静态程序分析和使用Intel PT的动态程序分析的合作和自适应形式。但在分析内存破坏漏洞(例如缓冲区溢出或UAF)导致的崩溃时不太有效。因为内存破坏漏洞允许攻击者操纵控制或数据流，而静态程序分析严重依赖于程序执行不会违反控制或数据流完整性的假设。

方法

本文提出POMP：自动化精确定位与崩溃相关的语句。考虑到静态分析不可靠（流会被劫持）。POMP“逆向执行”机制，通过crash，重建程序崩溃之前执行的数据流，然后利用反向污染分析来确定导致崩溃的关键指令。

假设一个崩溃后的工件携带了所有实际导致崩溃的指令。

例子：

对于该存在crash的程序，由于第7行的溢出，第16行会产生崩溃，崩溃后，执行跟踪，并捕获内存状态。如下图所示：

其中，A18和test代表指令和函数的地址。

但这里存在内存别名问题，例如：A14执行后寄存器eax中的值同时依赖于指令A12和A13，但是，指令A12和A14中显示的[ebp+0x8]和[eax]指示的内存可能是彼此的别名，就无法确定A14中的定义是否中断了来自A12和A13的数据流。

步骤

1. 依靠Intel PT来跟踪程序的控制流，并将其集成到崩溃后的工件中。
   1. PT通过捕获每个硬件线程上的软件执行信息来工作，有了控制流传输和程序二进制，就可以完全重建执行指令的跟踪
2. 重构数据流（与程序崩溃有关的数据流）
   1. 引入一种逆向执行机制来恢复内存占用

使用这种逆向执行机制，POMP可以轻松地在执行每条指令之前恢复机器状态，还能自动验证内存别名

以上图为例：在逆向执行完成A19指令的操作后，可以恢复eax寄存器的值，从而恢复A19之前的内存占用（即T18时的内存占用情况）；而A18是一个算术指令，因此又可以恢复A18之前（T17）时的内存占用情况……

A17：ret 等价于 mov eip ,[esp] add esp ,0x4

A16：pop ebp等价于 mov ebp, [esp] add esp ,0x4

通过上述处理指令的方案，逆向执行可以进一步恢复内存占用。

而对于A15 mov eax, 0x0，由于A14中的[eax]和A12中的[ebp+0x8]可能访问的是同一内存地址，不能确定A12中的[ebp+0x8]能否在指令A15执行之前到达现场？（内存别名问题）

解决内存别名的方法：

1. 值集分析算法（value-set analysis algorithm）：不可用，因为其要求符合标准的编译规则，但程序产生崩溃通常违反这一规则
2. 假设验证：使用逆向执行创建两个假设（①是同一个地址的不同别名；②与一相反），然后模拟指令的逆运算测试这两种假设
   1. 假设① 是同一个地址，则对于A14与A15来说，T14的信息约束为：
      1. eax = ebp + 0x8
      2. eax = [ebp + 0x8] + 0x4
      3. [eax] = 0x2
   2. 假设② 不是同一个地址：
      1. eax ≠ ebp + 0x8
      2. eax = [ebp + 0x8] + 0x4
      3. [eax] = 0x2
   通过查看T14的内存占用，可以发现假设②成立，因为假设①第i条不成立。

POMP使用反向污点分析自动化完成这一过程。

例如：本例最后的eax错误值来自于A19的传递，将[ebp-0xC]复制到eax中，而通过检查恢复的内存占用情况，可以发现[ebp-0xC]与A14中的[eax]指向同一个地址（0xff1c），这就意味着这个错误值实际上是从A14传播来的，因此就找到了造成崩溃的相关指令：A19与A14

1、逆向执行

Use-Define链

首先解析执行路径。对于路径中的每条指令，根据指令的语义提取相应的变量的Use-Define。然后将它们链接到先前构造的Use-Define链中。

例如：

一个定义包括三个元素：指令ID、Use-Define的变量、变量的值。每次在Use-Define链上增加时，会检查相应的定义与使用，并确定是否可以获取相应的值。

例如，在上图中，A18红圆圈内的值是通过T18内存状态获取的，而use:esp的值是通过语义推导计算获取的（esp = esp -0x4）

在Use-Define使用过程中，会遇到以下问题：试图给一个由内存区域表示的变量赋值，但该区域的地址不能通过使用链上的信息来解析

例如：A14的内存写操作中，地址由eax表示，但在这个示例的Use-Define中：

可以看到A13中的def: eax没有任何值，但它影响到了A14的节点。这样的话，A14的def: [eax]就有可能阻塞A12中的use: [ebp+0x08]，因为他们可能是同一个地址。

这里作者选择：对于这些未知的内存写入，作为一个插入标记，并阻塞之前的Use-Def的使用。确保不会给内存占用的恢复过程引入错误。

静态切片也可以用于发现Use-Def。但作者利用恢复的内存占用来进一步查找Use-Def关系，并处理了内存别名问题。

内存别名验证

针对内存别名问题，作者采用的方法是：

遍历链上的每个节点，检查新传播的数据流是否导致冲突，一般有两种冲突类型：①不一致的数据依赖 ②无效的数据依赖关系（会使程序在实际崩溃点之前出错）

假设A2 def[R2]与A4 def[R5]作为阻碍数据流传播的中间标签，在假设[R4]与[R5]不是同一个地址基础上，中间标签之间的数据流可以传播，如果证明[R4]与[R5]不是同一个地址，则继续假设[R1]与[R2]不是同一个地址……以此类推。最坏的情况是，在逆向执行的过程中，每条指令的反向操作都需要别名验证。因此作者对这种情况进行了限制（最多两次递归），相对高效。

其他问题

程序执行会调用系统调用，这会锁定到内核空间中，但作者没有将Inter PT设置为跟踪内核空间，通常来说逆向执行会产生路径丢失的问题。然鹅大多数系统调用不会对用户空间的寄存器和内存做出改变，因此可以忽略，对于会影响内存空间的系统调用：

• 对于可能影响寄存器的系统调用，作者只是在use-define链上引入一个定义 例如：系统调用read会把返回值保存在eax中，就会在use-define链相应的位置添加：def: eax = ?
• 对于可能影响内存内容的系统调用，检查受该调用影响的内存区域 通过使用在调用之前执行的指令来确定起始地址以及内存区域的大小，因为起始地址和大小通常由参数表示，这些参数在调用之前由这些指令处理。（按照这个过程，如果我们的算法确定了内存区域的大小，它将相应地向链追加定义。否则，将该系统调用视为一个中间标记，它将阻止通过该调用的传播3。这背后的原因是，非确定性内存区域可能与用户空间中的任何内存区域重叠。）

2、反向污点分析 Backward Taint Analysis

确定真正与程序崩溃有关的指令。

通常，程序崩溃原因：

①执行无效命令：eip是一个错误的值

②引用无效地址：通用寄存器指向错误的地址（例如最上面的表格 中的eax）

标识了错误点（eip或通用寄存器）后，POMP会污染这个错误点，并进行反向污点传播。

在这个过程中：

1. POMP使用获取的Use-Def链，并识别污染变量的定义Def（这种识别的标准是确保定义可以在没有任何其他干预定义的情况下到达污点变量）
   1. 例如：在上表中，将eax作为初试污点变量后，POMP会选择链上的A19：def：eax = [ebp - 0xc]，因为这里不会受到干预而达到污染变量eax。
2. 从确定的定义中，POMP解析该定义并将污染传递给新变量
   1. 由于定义中包含的任何变量都可能导致污染变量的破坏，POMP选择传递污染变量包括所有操作数、基寄存器和索引寄存器
   2. 例如：通过解析Def A19：def：eax = [ebp - 0xc]，POMP标识变量ebp和[ebp-0xc]，并将污染传递给这两个变量。

特点：这种污染传播策略可以保证POMP不会遗漏程序崩溃的根本原因，尽管它会过度污染一些实际上不会导致崩溃的变量。

注意：

• 当将污点传递给由内存访问指示的变量（例如[R0]）时，注意 POMP 可能无法识别与内存对应的地址（R0的值可能未知），出现这种情况，POMP 就会停止该变量的污点传播，因为污点可能会传播到具有 def:[Ri] 形式定义的任何变量
• 反向污点传播过程中，POMP可能会遇到链上的一个定义，该定义会干预传播。
  • 例如：已知污点变量[R0]和定义 def：[R1]，其中R1未知，此时不能缺点R0和R1是否是同一个值，即是否将污点从R0传播至R1？
  • 解决方法：采用前面的假设验证思想，但实际上这种方法不一定有效，当无法判断时，只能对变量采用“过度污染”，以确保不会遗漏崩溃的根本原因。

实验过程

POMP两部分

① 逆向执行 和 逆反向污点分析

65个不同的指令处理程序来执行反向执行和反向污染分析

构建了核心转储和指令解析器（基于libelf和libdisasm）

② 使用Intel PT跟踪程序执行

使Inter PT 在物理地址表模式（ToPA）下运行，这可以在多个不连续的物理内存区域中存储PT数据包。

效果：

把人工分析作为基本事实，并将它们与Pomp得到的指令进行了比较。验证了POMP在故障诊断中的有效性。

检测有效性的重点包括：

1. 检查崩溃的根本原因是否包含在Pomp自动识别的指令集中
2. 调查Pomp的输出是否覆盖了我们手动跟踪的最小指令集
3. Pomp是否可以显著削减软件开发人员手动检查的消耗

不足：

• 过度污染问题：存在，但微不足道