Group of Software Security In Progress

GoSSIP @ LoCCS.Shanghai Jiao Tong University

安全论文每日读 2015.03.04

今天带来的是一篇引用率高到惊人的论文(有多惊人可以去看看Google Scholar的引用),来自PLDI’05的介绍Intel PIN instrumentation framework的论文Pin: Building Customized Program Analysis Tools with Dynamic Instrumentation

Abstract

Pin是由Intel开发的一个支持IA32(32bit x86), EM64T(64-bit x86), Itanium和ARM(Intel声称,但是现在也没见着~)四种平台的插桩工具。

Pin在运行时对于其所监控的程序来说是完全透明的(上帝视角),使用动态编译(JIT)的方法,结合内联、寄存器重分配、活跃性分析以及插桩指令的一些优化性的调度等策略,对程序进行动态监控,且相对于传统的工具DynammoRIO和Valgrind来说,更加高效。

0x0 Instrumentation with Pin

Pin能够看到进程所有的上下文,包括内存、寄存器和控制流。PIN开发的函数可分为Instrumentation routine和Analysis routine。详情请移步 pin入门资料

在Pin的开发过程中,将所有的程序分为3类:Pin, Pintool, APP。

  • Pin即INTEL官方提供的一个已经编译好的可执行程序
  • Pintool是开发者基于PIN官方的各种API开发出来的辅助工具,也即我们的主要debug战场,以及各种链接进来的需要与pin进行通信的库。
  • APP即为我们要用PIN来监控的程序或进程(可在pin参数中指定某个进程的pid,通过attach的方式来监控进程)。
  • 在linux下,在pin的执行过程中,有3份glibc的拷贝。pin与app不共享任何数据,避免重入问题发生(有的函数是不可重入的,若pin和app同时需要调用这个函数,则会发生冲突问题)

Pin拦截APP(进程)的第一条指令(当前指令),并生成从这条指令起的线性代码序列,然后将控制转到生成的序列上去,当遇到分支跳转时,pin重新获得控制权限。

转换和插桩后的代码被放在一个代码缓存中,以便以后再次执行时提高效率。

由于PIN良好的封装,使得我们能够跨体系结构进行开发,不论底层的机器指令集是RISC, CISC还是VLIW(very long instruction word),而无需更改底层的代码,非常的方便友好。

1 Design and Implementation

1.1 System Overview

从高层来看,PIN由VM, 代码缓存(code cache),以及一个由PINTOOL调用的插庄API组成。

overview

VM由JIT,一个模拟器和一个调度器(dispatcher)组成,在pin获得程序的控制权限后,VM负责协调所有的组件来执行程序。

  • JIT和程序的插桩代码都是由调度器来启动。编译过的代码存储于代码缓存中,只有代码缓存中的代码才是可执行的,这也意味着在用pin对程序进行动态插桩的过程中,即使程序原来的代码是可执行的,也将变得不可执行。每次在代码缓存和VM之间进行切换时都需要存储/恢复寄存器现场(所以可以看到开销是非常大的)。
  • 模拟器拦截不能被直接执行的指令(如syscall),pin只能捕获用户层面的代码。

1.2 Injecting Pin

pin的插入器使用ptrace来获取app的控制权限和程序运行时的上下文

injector将pin binary加载到app的地址空间中,开始运行,在自身初始化结束后,pin将Pintool加载到地址空间中并让其运行,在pintool初始化完成后,向pin发出请求,启动app,pin创建初始化上下文并在入口点开始jitting app(或进程)。

DynamoRIO依赖于环境变量LD_PRELOAD,迫使动态加载器先将这个共享库加载到地址空间中。pin的方法相对于此,好处有三: 1. LD_PRELOAD无法在静态链接bin中正常工作 2. 加载额外共享库可能将APP的所有共享库(以及一些动态链接库)移动到高地址,而pin尽量使其保留在原来的地址 3. 在共享库加载器部分加载后,这些插桩工具才能获得app的控制权,而pin可插在程序的第一条指令

1.3 The JIT Compiler

1.3.1 Basics

pin将一个ISA编译到同一个ISA(无法跨体系结构平台编译),且不需要经过一个中间行驶,编译好的代码存在一个基于软件的code cache上。

  • 只有在code cache上的code 是可执行的,原始code不可执行。
  • 一次编译一条trace,一个trace是一个指令的线性序列,终结于以下条件
    • 一个无条件跳转(branch, call 或 ret)
    • trace中的条件跳转数量已达到一个预定义的阈值
    • trace中的指令数量已达到一个预定义的阈值

除了最后一个exit,一条trace可能还有多个条件跳转exit,这些exit都分支到一个stub,并将控制权交回给VM,在VM确定目标地址后(预先通过静态的方式无法知道),生成一条新trace(假设在之后未生成过该条trace),并移动到目标trace上继续执行

1.3.2 Trace Linking

为了提高性能,pin将直接从一条trace出口跳转到目标trace,绕过Stub和VM,这个方法称为trace linking.连接一个直接jmp,就好像这个jmp只有一个目标target。这样做的原因在于间接跳转可能有多个目的地址,故需要目标预测机制。

pin1

  • 此处jecxz指令时为了避免影响eflag寄存器,若ecx为0则跳转
  • 使用一个predicted target链表的结构来储存一个间接跳转的所有可能目标地址。
  • 若在这个链表中找到了预期的跳转地址,则直接通过jecxz $matchX来跳转,避免了后续转VM执行
  • 若在前述链表中未找到预期跳转地址,则在一个LookupHtab_1中寻找,若仍未找到,则转VM继续执行。

这里的非间接跳转机制与DynamoRIO不同之处有三:

  1. DynamoRIO中,整个链是一次生成的,并直接将翻译后代码嵌在间接跳转出,因此之后无法再添加新的target addr。而pin可以在程序运行时动态增量式地插入新target(在链表头或者尾部插入),下一次再遇到这些target就不用去搜索hash table或转vm继续执行了。
  2. Dy使用的是全局的hash table,pin使用的是局部hash table,在Hardware Support for Control Transfers in Code Caches @ MICRO-36 中证明过,局部比全局更高效
  3. 使用函数克隆技术加速最常见的间接跳转:return. 若一个函数在多处被调用,则给这个函数做多份拷贝,在它的每个调用点都使用一份独一无二的拷贝,这样每个return 就相当于只有一个target(在大多数情况下),否则一个return由一个target chain,时间开销过大(也即空间换时间)。(在实现中,为每条trace关联一个call stack,每个调用栈都可记录最后4个调用点,并通过hash压缩成一个64-bit 整型数据).

pin2

1.3.3 Register Re-allocation

在jitting过程中,经常需要使用额外寄存器。不用于通过特殊渠道获取额外寄存器,pin使用线性扫描寄存器来重新分配的方法,对APP和pintool进行寄存器重分配。

pin分配器在做interprocedural分配时是唯一的,但在执行时增量发掘流图的过程中,必须一次编译一条trace. 相反,一次能编译一个文件的编译器和字节码JIT,都能一次编译整个方法。

Register Liveness Analysis trace exit出的精确reg活跃信息使得寄存器分配更有效。因为pin能在不导致register spill的情况下重用“已经死掉的”寄存器。

没有完整的流图,只能增量式计算活跃信息,在A地址处的trace被编译后,将A作为key,把trace开始时的活跃信息记录在hash table中,如果trace exit是一个静态已知的target,则从hash table中取出活跃信息,以便更精确计算当前trace活跃信息。

尽管有时空开销,但是这个方法很有效,能够减少register spill.

Reconciliation of Register Bindings 在进行寄存器重分配时,JIT需要保证在trace exit处的寄存器绑定信息与目标trace入口处的绑定信息相同。

pin3

若target trace未编译,则在编译时使用新的virtual-to-physical寄存器分配信息,若trace已编译且Be != Bt(Be为当前trace exit处reg分配信息,Bt为目标trace入口处reg分配信息),则加上转换代码。

valgrind采取的则是有些简单低效的做法,在每个基本块末尾,所有的virtual reg都被重新存入内存中。

在真实环境下,通常只有1~2个virtual reg不同,而因此pin比valgrind更有效。

在实践中还有一个问题就是,将virtual reg映射到physical reg的补偿代码应该放在何处?是在分支之前还是跳转之后。pin是选择将补偿代码放在分支之前,因为实验数据显示,这将导致更少的唯一绑定,因此减少了编译器的内存开销。

1.3.5 Optinmizing Instrumentation Performance

pin大部分的开销都是在执行Analysis rtn上,而不是编译的时空开销(包括插入instrumentation rtn)。故对a rtn的优化很重要,无论是调用a rtn的次数还是 a rtn本身的复杂性。

PIN的JIT优化使用的是内联技术,能够减少执行开销。没有内联的话,会调用1个bridge routine保存所有寄存器,设置 analysis rtn参数,并调用 a rtn, 通过inline消除bridge,省去了2次call和ret,也不再需要额外存储寄存器。因此需要重命名和重分配寄存器,以管理reg spill。

并且,Inlining之后,可以使用很多其他的优化技术,如 a rtn参数的常量折叠等。

另外对x86下访问eflag做特别的优化

在插桩过程中可使用IPOINT_ANYWHERE来优化,这样有更多的机会来优化,比如pin能找到个避免eflag spill的点来插入a rtn。