Group of Software Security In Progress

GoSSIP @ LoCCS.Shanghai Jiao Tong University

Static Binary Rewriting Without Supplemental Information

论文下载

作者:University of Maryland的Matthew Smithson, Khaled ElWazeer, Kapil Anand, Aparna Kotha, Rajeev Barua

同年,他们针对SecondWrite这个工具在PLDI,EuroSys以及WCRE中发表了三篇文章。

Abs & Intro

一个好的二进制重写工具需要满足如下的四个要求: * Complete code coverage * Guaranteed correctness * Analysis and transformation ability * Should work on stripped binaries

现有的重写工具存在各式各样的缺陷的关键问题就在于,如何区分二进制程序中的代码段以及数据段。文章将这类问题成为内容分类问题(content classification problem)。 文章指出先前的工作基本上集中在 automatic parallelization,symbol promotion,variable and function argument recognition以及security check insertion,这些逆向工作都需要重定向信息的支持

  • Dynamic Rewriting
    • 重写的二进制代码被保存在一个临时的cache中
    • content classification在执行的时候能够轻松完成
    • 复杂的分析任务会带来巨大的时间开销,即使没有额外的分析也存在比较大的时间开销,DynamoRIO:20%,Pin:54%
    • 只重写执行过程中执行到的指令语句,代码覆盖率得到限制
  • Static Rewriting
    • rewriting code offline,所以有足够的时间完成复杂的分析以及代码转换
    • 受content classification问题的限制
    • 确定程序中一段字节是机器指令的有效方法是,保证存在一条从程序入口处到达这段字节序列的控制流,即recursive traversal
    • 由于存在indirect CTI(control-flow transfer instruction),无法确定跳转地址导致一些代码序列无法识别
    • 另一个问题就是重写过程带来的指令移动所导致的重定向问题,尤其是在重定向信息以及符号表缺失的情况下。
  • Minimally-Invasive Rewriting
    • 主要用于stripped binary,但是牺牲了代码覆盖率以及进行复杂转换的能力(?)
    • only minimal transformations are allowed, such as the insertion of ‘trampolines’ to jump into and out of instrumentation blocks, and peephole optimizations affecting small sequences of instructions.

本文给出了一种二进制重写技术,不基于任何不安全的假设前提,能够支持任意复杂的二进制代码转换,并且达到100%的代码覆盖率。本技术的关键就是针对无法识别的字节序列(记为speculative code),在重写代码中被保存为两份,一份作为指令进行翻译,一份作为data重新写回原地址。

System Design

Relocating Instruction

与传统修改跳转地址的重写方式不同,对于间接跳转,引入一个call translator函数,类似于一个switch结构,根据计算出的原程序中的跳转地址进行case分类 例如针对一个间接调用’call *fp’, 给出了如下的rewritten code:

1
2
3
4
5
6
7
  if (fp == 0x8300):
    fp_modified = &foo;
  else if (fp == 0x8400):
    fp_modified = &bar;
  else:
    assert(false);
  call *fp_modified;

Relocating Data

将data段的数据重写回原来的内存地址处,这样就可以避免d2d不会因为重定向产生错误。

Code Discovery

现有的代码发现算法主要为线性遍历以及递归遍历。

为了获取完整的代码覆盖率,作者给出了这么一个前提假设:indirect CTIs could target any location. 由于这个保守的前提假设,在代码发现过程中无法确定是指令还是数据的字节序列,也可能是间接跳转的一个目标地址。

对于这样的字节序列,作者提出了speculative recursive traversal disassembly的方法。 如果碰到无法确定是指令还是数据的字节序列的时候,那么就将这个序列拷贝为两份,一份作为数据直接存储在rewritten binary中,另一份作为指令序列进行反汇编。 在反汇编的同时,这段指令序列也会被验证是否为有效指令,例如存在一个跳转指令跳转到一个非法地址。

Optimizing Target sets

在翻译间接跳转指令的时候,会首先给出一个可能的目标地址集合,这个集合中必然存在着一些无效的地址。

这一节介绍了通过数据流的分析,来精简这个目标地址集合:

  • Constant Propagation;the use of a variable assigned to only a single constant is replaced by that constant.
  • Binary Characterization:间接跳转在计算目标地址时,需要一个绝对地址作为操作数。通过分析这一个过程,能够给出一精确的目标地址集合。
  • leverage the results of Andersen’s algorithm [28] for alias analysis by examining each indirect CTI operand against each entry in the reduced set of CTI targets provided by binary characterization.

Callbacks

回调发生在一个函数指针被作为一个参数传给了an external library function。 为了处理这种函数指针,文章给出了两种方法:

  • 由于动态链入的库函数,我们是可以识别的。通过这些库函数信息,查找其中的函数指针参数,并针对这些参数参数进行重写。
  • 作者发现82%的callback arguments是常数,那么这些callback arguments是可以直接翻译的
  • 针对剩下的部分,register a custom segmentation handler during startup which translates all original code addresses to rewritten code addresses using our translator and then restores control flow to the proper location within the rewritten code segment.

Evaluation

作者利用LLVM-IR实现了这个binary rewriter,并从三个方面对这个工具的功能进行了说明

  • the number of indirect CTI in each binary as discovered by SecondWrite
  • Translator runtime overhead casued by translating the target address or pushing memory arguments onto the stack
  • the increase in the size of the rewritten binary