Fr3v1带你读论文-Similarity of Binaries through re-Optimization

阅读量    52839 |

分享到: QQ空间 新浪微博 微信 QQ facebook twitter

 

这是篇PLDI2017的论文,提供了一种静态检测二进制漏洞的方法,个人认为思路比较简单且实际执行的效率较高,但放在今天看来缺点也较为明显,或许可以进一步考虑代码相似性的检测方案。


引言

在对不含符号表等信息的二进制代码检测相似性时的主要难点是如何确定相似性,例如有时候代码是通过不同编译器、不同优化级别或者针对不同架构编译的。在尽量减少误报的情况下解决这个难题无论是对逆向工程还是定位漏洞代码都至关重要。
作者提出了一个可用于大规模检测且具有较高准确度的技术。其工作原理是将二进制代码过程分解为上下文无关的可比较片段,并将其统一为规范的形式,随后通过简单的比较来找到等价的片段。
结果表明该方案(称为GitZ)能够有效地执行大规模比较,且相似性比较的精度较高,误报率较少。

 

目前的技术缺陷

  1. 在受限(stripped)二进制文件、跨编译器、跨架构和跨优化选项的场景下效果不好
  2. 误报率高
  3. 无法应对百万级的大规模比较
  4. 在静态分析时需要动态分析进行配合

 

提出的方法

  1. 分割程序片段。将程序分解为strand,即基本块的数据流片段,作为相似性比较的基本单元
    strand:A strand is the list of all of the instructions from the basic block that affect the computation of a specific value.
  2. 通过重新优化找到等价的代码片段。通过在strands上重新进行编译优化器的优化过程,将代码片段引入新的规范化形式,从而在后续能够识别语法上不同但语义等价的strands
  3. 建立代码相似性。爬取部分语料库生成一个统计框架,来评估每一个strand在整个程序中的重要程度。

 

设计与实现

二进制代码规范化和一般化处理

将二进制代码提升为中间代码

这个步骤排除了编译器和链接器的干扰,使得后续工作可以关注于语义方面。该步骤有很多框架可以使用,作者在这里使用了angr的pyvex库将Intel的x86_64和ARM的AArch64指令(包括浮点指令)提升为VEX-IR作为原型。
值得一提的是这一步进行的不只是简单的反编译,而是使用变量表示相应机器的状态(包括内存、寄存器,包括标志寄存器),并用对这些变量的操作来表示指令的语义,因此在这个过程中并不关心任何优化,只需要专注于准确表示语义信息。

指令提升的过程对相似性的影响

会产生一些冗余和总体上的偏差。例如在图3中将aarch64的”mov x1,x21”转换为VEX-IR时产生了冗余的临时变量t14、t15、t16;将x86_64的”add rax,1”转换为BAP后,生成了临时变量T2。
如在图1中体现的,存在这种冗余的变量在进行相似性学习时是致命的,也会对后续在跨架构和优化级别的比较中造成严重干扰

从提升后的IR得到LLVM-IR strands

为了达到“Lifter无关”,作者使用了一个(自己写的)工具把VEX-IR转换为LLVM-IR。选择LLVM-IR的原因是它的稳定性、辅助扩展工具多且对多架构支持较好。(个人猜测主要是方便对代码进行统一优化)

提取strands

在这个阶段的目标是建立一个过程表达(procedure representation)以便在后续配合找到相似的程序片段
提取strand的步骤:生成CFG,分离出每个基本块,其中strand就是在一个基本块中和某个值计算相关的所有指令

以上是提取strands过程的伪代码,大概是“倒序取一条指令,判断其操作的变量与当前strand中记录的变量交集是否为空,如果不为空则将指令记录到该strand中”。其中Ref和Def函数返回一个指令所引用或定义的变量集合。这个算法在一个基本块上重复执行,直到把整个基本块完全覆盖。

将 LLVM-IR 的strands规范化

这个部分要解决的三个主要问题是:1.编译器造成的strand的语义差异,例如编译优化、运行时库和控制流的影响 2.不同机构造成的影响,例如通用寄存器数量、指令集表达差异等 3.提升器的造成的影响(如前面提到的冗余指令)

解决方案是利用编译器重新进行优化,变相进行统一规范。LLVM-IR对应的优化工具是CLang opt。作者将每个strand作为一个LLVM-IR函数片段,并对代码做了两步更改:1.将寄存器更改为全局变量 2.添加返回strand值的指令。用’-early-cse’和’-instcombine’选项