Group of Software Security In Progress

GoSSIP @ LoCCS.Shanghai Jiao Tong University

StraightTaint: Decoupled Offline Symbolic Taint Analysis

论文下载

Abstract & Introduction

现有的DTA普遍带来巨大的时间开销,例如libdft一般会产生六倍的额外开销,最坏可以达到20到30倍。 难以提高DTA性能的关键因素在于程序执行和taint tracking logic code之间的强连接:taint tracking code和程序执行是相互交错导致了经常的“context switches”,这就带来了大量的开销。

大部分现有的提高DTA性能的方法就主要是应用多核的技术,将taint tracking code分配给另一个CPU来完成:

  • 一种是在多核系统上并行执行DTA,而在另一个核心执行程序并记录用于污点分析的运行时数据;
  • 另一种是首先记录应用的执行,随后才在另一个CPU重新进行相应的污点分析

由于传统DTA工具受限于计算资源的限制,往往他们会采用incomplete taint propagation strategies,但是这策略也带来了缺陷:

  • single-tag propagation虽然简化了shadow memory的设置,但是极易导致over-tainting。multi-tag taint propagation在一些逆向分析中是必不可少的,例如恢复未知的协议格式恢复或者检测恶意软件中的编码函数,但是这就需要更大的shadow memory空间,以及更高的runtime overhead。
  • 先前的DTA工具采用了简单保守的污染策略,但是也导致了precision loss in many scenarios.

Overview

StraightTaint由两个部分组成:online logging和offline analysis

Efficient Online Logging

  • 当预定义的taint seeds被引入时,开启online trace logging。
  • 为了避免在离线分析时会导致的symbolic taint variables explosion,会记录下taint seeds被引入时的concrete execution state。

Three design goals guide us to achieving low online logging overhead:

  • the logged data representation should be compact so that trace buffer holds as much data as possible;
  • the application (i.e. producer) should not be blocked when the full buffers are being consumed, that is, processing the buffers asynchronously;
  • instrumentation overhead should be minimized.

Trace Profiling

在32位机器中,往往需要4字节的tag(基本块的起始地址)来标注一个基本块,本文利用DEP的方法来简化这个tag.

Detailed Execution Profile

  • DEP使用2-字节的tag来记录大部分执行到的基本块。
  • DEP将4字节的地址分割为H-tag(两个高位字节)和L-tag(两个低位字节)。
  • 在control flow profiling的过程中,如果基本块地址与前一个执行基本块拥有同样的H-tag,那么只需记录L-tag,如果不同,那么profiler会记录一个escape tag 0x0000,再记录下这个基本块的H-tag。

Multithreaded Fast Buffering Scheme

类似于经典的进程同步模型:生产者-消费者问题。

当在执行记录过程中填满一个buffer时,一个callback函数会被调用,来完成后续的两个工作:

  1. 将这个填满的buffer添加到全局的full-buffer队列中,唤醒一个worker线程来进行处理;
  2. 返回一个空的buffer给profiler进行记录。

这其中worker线程的数量以及buffer的大小会影响记录过程的性能,在后续的evaluation中给出了一个最优解。

Offline Symbolic Taint Analysis

Reconstruction of Straight-line Code

  • 利用记录的基本块tag,将执行的代码序列恢复,并将x86指令转化为BIL(BAP的IR),来明显地表达出指令中副作用的影响。
  • 同时BIL只给出了25种指令,简化了后续的分析工作。

Symbolic Taint Analysis

  • 从引入pre-defined taint seeds开始进行符号执行。本文的工作将taint seed初始化为符号变量,而利用一个process dump来将其他变量值初始化为一个具体的值。
  • 在执行结束后,检查taint sink的符号表达式。

Memory Reference Address Resolution

  • 由于引用了具体数值,所以在符号执行过程中有些地址是可以直接计算的。
  • 对于一个无法直接计算得到的地址(例如堆内存分配得到的地址),就分派一个符号变量来表示这个地址
  • 如果一个符号变量被用作一个memory lookup的index,那么根据path condition计算index的范围,然后这个范围内的所有内存上的值都会被污染

Optimization

  • 采用类似于pin的做法,将会被经常使用连续的block组合在一起,当做一个sub-trace。这些block在整个执行过程中都只有一个predecessor以及一个successor。
  • 然后给出这个sub-trace所有符号等式的集合,当下次遇到这样的sub-trace的时候,直接调用这个集合,完成这个sub-trace的Symbolic Taint Analysis。