Group of Software Security In Progress

GoSSIP @ LoCCS.Shanghai Jiao Tong University

Cross-Architecture Bug Search in Binary Executables

今天要介绍的一篇论文 Cross-Architecture Bug Search in Binary Executables 来自SP’15,这篇论文主要讨论了现有软件在包含漏洞且被编译到三个热门的架构(x86/64,ARM和MIPS)时,如何利用某个架构的分析技术来帮助分析另外架构上代码实现的漏洞检测问题。

  • 出处:SP’15
  • 作者:Jannik Pewny, Behrad Garmany, Robert Gawlik, Christian Rossow, Thorsten Holz
  • 单位:波鸿鲁尔大学 & 萨尔大学

1 Abstract && Introduction

  • 现在越来越多的闭源软件会在不同架构上实现,这对漏洞查找带来了挑战
  • 过去的方法的问题:需要源码;单架构(x86);依赖动态分析(嵌入式设备难以应用)
  • 解决的问题:假设已知一个架构的漏洞,在其他架构上寻找相同的漏洞(IR相似性检测)
  • 假设没有混淆,但可以应对不同优化选项造成的差别
  • 贡献:
    • 使用IR抽取不同架构实现的语法信息(x86, ARM and MIPS)
    • 使用Sampling和MinHashing等高效方法实现(Testing and Jaccard)
    • 提出结构匹配标准,在CFG子图当中匹配
    • 在现实软件中实验

2 Approach

  • 目的是用相似代码标准找bug
  • 假设相似的代码只存在细小的差别,并有相同的bug

Workflow

  1. 产生 bug signature
  2. 转换成IR
  3. 产生 Semantic Hashes
  4. 穷举搜索,结合CFG局部调优,匈牙利算法
  5. 每条指令都表示成符号表达(symbolic expression),说明输出是如何被输入影响的

Bug Signatures

  • 签名长度难以限定,过长容易绝对化、过短容易误报

Unifying Cross-Architecture Instruction Sets

  • 先反汇编出代码结构(IDA)
  • 然后把指令转换成类似RISC的指令

Extracting Semantics via Sampling

  • 每个基本块产生(一系列)公式,并用prover简化,结果将输出表示成输入的函数
  • 产生公式后,随机产生输入,形成(输入, 输出)对(prover的效率较低,如果是要收集I/O对的话,可以用模拟执行的方法)

Similarity Metric via Semantic Hashes

  • I/O对数量太大,不利于大规模比较计算相似度
  • 使用 MinHash 算法,一种快速估算Jaccard系数的方法(相关数学证明可参考wiki)

Comparing Larger Binary Structures

  • 通过CFG把之前基本块的相似组合成更大规模的相似
  • 提出 Best Hit Broadening 算法(本质上是匈牙利算法)

3 Implementation

Common Ground: The IR Stage

  • 三个架构:x86, ARM, MIPS
  • 反汇编:IDA Pro
  • 中间语言:VEX-IR from Valgrind toolkit
  • 自动化:pyvex, a python framework bindings to the VEX-IR

Extracting Semantics: Sampling

从[-1000, 1000]区间产生输入向量,足够避免 collisions

Semantic Hash

  • 给每个基本块计算多个hash值;一个基本块有多个公式,按照输入数量分组
  • 然后按照相同输入数量分组比较,最后合成整体相似度

Bug Signature Matching

确定不动点,按照CFG上下匹配基本块,用匈牙利算法得到相似度最大的匹配组合(没有讨论优化、混淆造成的基本块合并、拆分的CFG改变的情况)

4 Evaluation

  • 三个架构都是32位
  • 编译器:gcc v4.6.2/v4.8.1 and clang v3.0
  • 函数级别的比较

False/True Positives Across Architectures

  • BusyBox 1.20.0 vs 1.21.1第一准确率有90.4%
  • 不同架构的结果就差多了,第一准确率30%左右
    • 作者的方法对CFG是敏感的
    • 混淆、优化会导致CFG改变
    • (不同架构的比较准确率比相同架构差太多,如果IR是语义保持的,那么作者的方法还需进一步改进)
    • (如果是因为转换成IR而导致信息损耗,那么就需要更好的IR了)

False/True Positives Across Compilers/Code Optimization

  • True Positive

  • False Positive
    • dir 和 ls 功能相近,误报反而说明方法是有效的

Bug Search in Closed-Source Software

  • 在现实程序中找 Heartblead
  • 目标是openssl库中的tlsl_process_heartbeat(TLS)和dtlsl_process_heartbeat(DTLS)两个函数

5 Discussion

Vulnerability Verification

无法自动化证明找到的代码片段是有问题的

False Negatives

这里的漏报是因为CFG改变、内联、优化造成的

6 Related Work

Code Similarity

  • 文章的亮点有二:跨平台、相似性比较找漏洞
  • 核心:代码相似性检测
  • 对Blanket Execution评价:
    • 只能检测函数级别的相似
    • 只支持 x64 ,而且因为PIN,其他架构也难以迁移