Group of Software Security In Progress

GoSSIP @ LoCCS.Shanghai Jiao Tong University

Inference of Peak Density of Indirect Branches to Detect ROP Attacks

论文下载

发表于CGO’16

Introduction

本文介绍一种通过计算indirect branches的密度来检测ROP攻击的方法

  • 展示了使用 a window of 32 instructions 足以检测在 Exploit Database 选取的15个exp的ROP攻击
  • 这种检测机制可以借助改变编译选项的方法来避免绕过
  • 一种静态分析程序indirect branches的密度的方法

Universal ROP-Detection Thresholds

Fig

In search of a universal threshold

  • 使用pin生产trace
  • 选取了15exp,10 windows, 5 Linux

Fig

实验环境

  • 10 exp on windows
  • programs available in the SPEC CPU2006 benchmark suite
  • compiled with Visual Studio 7 in 32-bit mode to a x86 machine running Windows 7 Ultimate
  • 3天

结论:

  • ROP-based exp 有较高的indirect branches的密度
  • 大的window比较容易模糊辨别界限
  • 至少对我们测试的bencmarks来说,可以确认一个 universal threshold(13 per window of 32 ins)

同时进行64 windows和 Linux的实验,和上面的结果相似

Fig

Evading universal thresholds

使用no-op gadget来绕过检测:

  • no-op gadget:不会影响exp中要用的寄存器或栈或内存的指令
  • 使用Mona进行no-op gadget 搜索

选取no-op gadget标准:

  • > 5 条指令
  • 没有指令会改变栈(push, pop, add esp, etc)
  • 没有只能在privileged mode的指令(cli, ltr, smsw, and 21 more)
  • 不会写在exp中使用的寄存器

对选取出的no-op gadget排序:

  • 间接内存引用升序(避免访问到非法地址)
  • 指令数降序

验证no-op gadget是否可用:

  • Audio Extractor
  • CD to MP3 Converter

因为他们含有最少合法的no-op gadget(21+52)

测试花费时间:>70 man-hours of work

测试结果:3+6

所有可以用的no-op gadget可以分为两类:

  • static initialization sequences
  • alignment blocks

gcc: -falign-labels -falign-jumps 调整alignment

可以通过改变编译器来去除这些no-op gadget

  • 在static initialization sequences中插入写寄存器的指令
  • replace the padding code by no-ops of up to nine bytes (减少指令数)

Using specific thresholds to improve protections

为每个程序建立不同的thresholds

  • the use of specific thresholds reduces by 75% the availability of no-op gadgets

Static Inference of Specific Thresholds

  • IPD:Inference of Peak Density of Indirect Branches

  • (IPD) Given a program P , and two integers: K and R, is there an execution trace of P with no more than K instructions that contains R indirect branches?

δ-CFG: the supporting data-structure

The δ-CFG has three kinds of nodes:

  • BBL:以direct branch指令结尾
  • RET:以return指令结尾
  • FUN:以function call指令结尾

Fig

Algorithm to estimate the peak density of returns

Fig

  • function deduce performs an ex- haustive search bounded by the window size K starting from any node in the program.
  • Function explore receives a trip budget T , a return stack and a node of the δ-CFG.

Fig

  • weight of a path is the sum of all the weights on the edges that constitute this path
  • The IPD problem asks for a path weight K containing R indirect branches

算法实现

  • x86 back-end available in the LLVM compiler
  • our actual implementation of deduce works at the intermediate repre- sentation of the LLVM compilation infra-structure(only analyze code that we can compile)

算法复杂度

  • O(NK+1), N:ins num, K: window size
  • O(N × (2K)), 当所有指令都是2-target branches

Experiments

Specific thresholds lead to less available gadgets

Fig

Fig

On the Accuracy of our Estimates

Fig

Performance of the inference algorithm

Fig