【论文笔记】SelectiveTaint: Efficient Data Flow Tracking With Static Binary Rewriting

2021-0727-SelectiveTaint

SelectiveTaint: Efficient Data Flow Tracking With Static Binary Rewriting

作者：Sanchuan Chen, Zhiqiang Lin, Yinqian Zhang

单位：The Ohio State University

会议：USENIX Security 2021

链接：https://www.usenix.org/system/files/sec21fall-chen-sanchuan.pdf

Introduction

污点分析已被广泛应用于许多的安全研究，例如漏洞检测、信息流追踪、恶意软件分析和协议逆向工程。dynamic taint analysis也被称为dynamic data flow tracking (DDFT)。State-of-the-art 的动态污点分析工具通常建立在动态二进制插桩之上，其会每条可能的指令进行插桩并依靠运行时信息来决定指令是否需要进行污点传播，因此具有很高的性能开销。例如使用libdft应用在gzip 解压一个文件上时会4x slowdown。

之前有一系列的工作旨在提高动态污点分析的性能，如应用类似编译器的优化来消除污点分析代码中的冗余逻辑[16]、污点逻辑与程序逻辑解耦并优化数据结构[15]、并行与流水线方案[25]、在线状态追踪与离线符号污点分析[24]。

目前的DDFT框架以及优化都是基于dynamic binary instrumentation (DBI)，尤其是使用Intel’s Pin，在运行时进行插桩。Pin中的VM、APIs会为污点分析工具带来额外的开销。

不像DBI，static binary instrumentation (SBI)会在将分析所用代码静态插入到native binary中，从而避免DBI中不必要的JIT和模拟带来的开销。SBI会减少context switch的次数。随着近年来静态二进制重写技术的发展（Uroboros, Ramblr, MultiVerse, and recently Datalog Disassembly）。因此值得回过头来研究通过静态二进制重写的方式进行污点分析。

本文中提出了SelectiveTaint，其直接减少了dynamic binary translation的开销，且能够在binary中扫描taint source。其利用value set analysis (VSA)，仅taint部分指令。

作者基于SBI实现了SelectiveTaint，并使用16组coreutils以及5个网络服务程序进行评估。实验结果表明SelectiveTaint 1.7x快与libdft。作者表示SelectiveTaint是soundy的，并使用real-world exploits确认soundness。

作者的贡献如下：

• 提出了SelectiveTaint，第一个基于静态二进制重写的选择性污点分析框架。
• 提出了一种保守的污点指令识别方法，通过使用 VSA 识别不会涉及污点内存或寄存器的指令。

Background

Taint Analysis

Value Set Analysis

Value set analysis (VSA)是一种静态程序分析技术，其会过估计程序中可能的值集。

Memory regions and abstract locations：global、stack、heap region

Abstract addresses and value sets：

Binary Instrumentation

Static binary rewriting 的三种实现方式：(1) trampoline-based, (2) lifting and recompiling, (3) symbolization [40] and reassembling

Dynamic binary instrumentation 实现方式：using a trampoline, or using just-in-time (JIT) compiling.

Challenges and Insights

Challenges

• 如何确定一条反汇编的指令是否需要被污点分析插桩
• ⇒如何在不执行binary的情况下，根据操作数中的内存地址、寄存器判断一条指令的taintedness

Insights

显然，解决上述挑战，需要在程序中的每个位置推断出寄存器和memory cells可能的值。一个可行的方案是使用VSA，VSA将计算每个可能的符号化内存地址和寄存器的值。因此，使用VSA，我们可以确定特点内存地址或寄存器是否设计污点传播。例如，它是否是我们感兴趣的地址的别名、它是否存在污点数据的传播。

ebx at 0x80486a9 and eax at 0x80486c6值相同，故为别名。事实上它们都指向buffer。

为了分析哪些指令可能参与污点传播，一个straw-man的方法是维护tainted value set，当发现污点进行传播时，将被污染的操作数加入set中。

但是在分析real-world binaries，VSA可能因各种原因丢失精度，例如不精确的CFG、复杂的静态points-to analysis以及未知输入。因此，如下图所示，通过VSA可能无法得到理想的被污染的指令集，VSA能够识别出must-tainted insn集合，且不会有误报。另一方面，可以通过VSA识别出must-not-tainted insn集合，这样就可以只对剩下的指令进行污点传播即可。最坏的情况是$I_u$为空，意味着会像其他基于DBI的污点分析一样分析所有指令。作者的目标是在不引入误报的情况下尽可能的扩大$I_u$。

在Table 1的示例中，在0x8048620之前，must-not-tainted value set与value set相等（VSA是流敏感的）。在taint source 0x8048620处，must-not-tainted value set去除掉value set (┴,[-0x410,0x3f0],┴)，buffer长度0x800。

因此最终SelectiveTaint会对深灰色及白色的五条指令进行插桩污点传播。

Scope and Assumptions

仅关注x86架构下Linux平台上的具有ELF格式的二进制文件，并且假设二进制代码没有被混淆，能够得到正确的反汇编。SelectiveTaint的二进制重写是基于DynInst。

Detailed Design

CFG Reconstruction

唯一的难点在于确定间接调用和间接跳转的目标地址。

处理间接调用：SelectiveTaint使用两中CFI识别方式（TypeArmor和tCFI）来恢复类型信息（参数数量及类型）。通过这些信息构建出一个过估计的CFG。

处理间接跳转：使用VSA分析目标地址，如果没有找到则考虑这个indirect是否使用到了外部数据引用（全局变量，跳转表？），如果又没有，则将函数哪所有可能的基本块起始地址作为潜在的跳转目标。否则将所有函数入口视为潜在的跳转目标（考虑到过程间跳转来自编译器优化）。同样得到一个过估计的CFG。

Value Set Analysis

作者使用的VSA是一个context-sensitive and flow-sensitive whole program analysis。首先初始化esp、heap以及memory cells。$VSA$使用类似worklist的方式不断迭代，直到到达不动点。并对于call/ret指令，执行过程间分析并调整上下文环境。

Practical Challenges，虽然想法很简单，但在实际数据流追踪时仍遇到诸多挑战，例如上下文敏感、流敏感、别名分析等

• Handling context-sensitivity

  作者使用cloning-based的context sensitive分析，为call graph中每个非循环的调用路径生成一个函数拷贝。

• Handling flow-sensitivity

  由于VSA是flow-sensitive并且对每条指令进行处理，在工程上比较麻烦。作者借用了符号执行翻译每一条指令并更新相应符号状态的想法。当执行作者的流敏感分析时，需要解释每条指令，并根据其语义更新VSA。由于符号执行已经有了很多开源工具，因此作者没有描述解释器是如何实现的。

• Handling a-locs with unknown values or addresses

  由于VSA缺乏运行时信息（如调用上下文、具体的内存地址），一个主要的问题是为初始化变量及其别名。有部分未初始化变量中，有一些是使用地址计算的，这就导致了a-locs。分析将假设未初始化变量拥有任意的值，即值集(┬,┬,┬)。在实现中，作者确定了以下三种情况无法确定对应的地址：CLI、missing caller、library function/system call。

Taint Instruction Identification

目标：尽可能多的扩大must-not-tainted value set

Must-not Tainted Analysis

• Identification Policy
  • a 从must-not-tainted set中移除
  • b 移除
  • c 加入must-not-tainted set
  • d 加入

• Resolving operand’s addresses，处理内存访问
  • 常数地址，很容易识别出是全局变量
  • based on ESP，栈上变量
  • without ESP，e.g. [eax]，比较棘手，使用VSA的结果来判断，如果无法确定访问的内存地址是否被污染，则保守地将其从must-not-tainted set中删除
• Resolving operand’s values，处理未初始化的操作数，due to：
  • CLI
  • missing caller
  • library function/system call。根据API语义来污染这些未知变量，例如fopen的返回指针被放入must-not tainted set中，并且指针指向堆上的一个特殊区域。
• Variable type inference
  • 为了更精确的识别污点分析相关指令，作者进行了一个简单的类型推断以确定一个变量是否为指针。基于识别其是否会解引用、作为指针类型参数传入函数、已知库函数的返回值
• Our Algorithm
  • 扫描二进制程序识别source，例如read、recv
  • 将每个source作为分析的起点，并确定初始污点缓冲区的起始地址及长度
  • work-list stylebing

Soundness Analysis of SelectiveTaint

定义：

• false negatives，漏报，SelectiveTaint认为未被污染但是实际上被污染
• false positives，误报，SelectiveTaint认为是被污染的但实际上未被污染

作者对SelectiveTaint的must-not analysis进行形式化的分析，以证明其是soundy的。

定义了四条primary inference rules以及剩下的auxiliary inference rules。

定理1：Must-not-tainted analysis is sound, except for the precision loss due to imprecise CFG and VSA results (thereby making it soundy or mostly sound).

归纳法证明…

Binary Rewriting

根据可能涉及污点传播的指令，进行重写。对libc函数设置污点传播规则。

Implementation

基于angr进行CFG恢复，自实现的flow-sensitive and context-sensitive whole program VSA。Binary Rewriting基于Dyninst的插桩即分析框架。

Evaluation

Effectiveness

Efficiency

Security Case Studies

Conclusion

本文提出了一种基于静态分析的数据流追踪框架SelectiveTaint，其通过识别不会涉及污点分析的指令，对其余部分进行插桩以实现较低开销的污点分析。