论文:Unleashing the Hidden Power of Compiler Optimization on Binary Code Difference: An Empirical Study (发表于PLDI2021)
论文链接:https://arxiv.org/ftp/arxiv/papers/2103/2103.12357.pdf
代码和数据集:https://github.com/BinTuner/Dev
研究动机
根据作者对二进制的调研,他们发现实际应用中的二进制文件并非全部都是源代码依照默认的优化选项编译而成。他们追踪了2018年开始一年内Mirai IT 僵尸网络家族软件的编译选项的变化,发现其中有接近42%的软件是由142种GCC的非默认选项编译出来的。而通常来讲,一边的二进制文章(binary diff)通常只针对默认选项下的二进制进行实现,深入理解非默认选项编译出的二进制对于已有二进制分析技术的影响具有重要意义。
文章即针对这种非默认选项编译出的二进制,展开了以下分析:
1.优化选项对二进制代码差异的影响
- 对句法层级的影响(syntactic level)
函数,基本块,控制流图是常用的二进制的三种表示方式,而很多二进制方法都依赖对以上表示的精准边界识别,这一部分将讨论优化选项对这三种表示的影响。
1.1 对函数的影响
主要在 函数内联 和 尾函数调用 的优化
另外,编译器的优化有时候还会影响到函数参数的识别。比如,正常情况下调用函数会将相关参数存入相关寄存器,但是优化之后,有可能这个寄存器已经存在相应的值,调用之前将不会重复存入操作。这种变化使得一些基于calling conventions的方法发生识别错误。
1.2 对基本块的影响
相比于函数级别的识别,基本块的识别要简单得多。这里主要会受到一些过程内优化的影响,比如loop unrolling, compound conditionals, 和 basic-block merging会倾向产生分枝较少的二进制。
像这种变化已经打破了传统基本块匹配的1对1或者n对n的匹配模式,势必会影响已有方法的效果。
1.3 对控制流图的影响
因为控制流图是基本块的组合,同时又表示了一个函数。所以以上对函数和基本块造成的优化选项都会对控制流图造成影响。 - 对语义级别的影响
主要如下:
2. BinTuner
作者们为了研究编译选项在多大程度会影响到二进制代码,提出了一种迭代式的编译方法以找到更好的编译选项的组合。由于最佳编译选项是极少的,而次优选项是很多的,作者因此提出了基于随机的搜索方法(如genetic algorithm)来生成编译选项。并且整个系统框架包括四个组件:
Makefile Analyzer: BinTuner 通过Makefile来驱动编译和链接, 这里通过使用“scan-build”来抽取源文件依赖,配置信息和初始的编译选项。
Constraints Verfication:像LLVM 和GCC都会给优化标识(optimization flag)施加一定的约束,包括互斥关系和依赖关系(adverse interactions and dependency relationships)。当随机生成的编译选项不符合约束时,就会发生编译错误。作者通过人工理解各个编译标识,从而设定了约束验证器,使得不符合约束的编译选项组合不参与后续的编译。
Compiler Interface:此组件是用作链接编译器,遗传算法,有效性计算函数的中间组件。
Fitness Function:用作计算一个编译选项组合有效性的函数。作者在这一部分着重介绍了已有方法(IDA,Bindiff, BinHunt)的时间复杂度上的不可行性,以及Normalized Compression Distance(NCD)的使用,即通过同时压缩两个二进制文件发现其相似部分占比的方法来衡量新生成二进制文件与初始文件差异性大小的方法。差异越大,说明该编译选项对binary diff的作用越好。
3.实验结果
- 差异大小 (LLVM, GCC)
相比传统的O0 vs.O3的差异,BinTuner带来了更大的差异
- 对函数,基本块,控制流图的影响
控制流图是最容易受到影响的。其中,对于LLVM编译的657.xz_s,控制流图边的匹配率从35% (“O1 vs. O0”) 降到了 8% (“BinTuner vs. O0” )。
NVD迭代次数对差异的影响:
- 编译选项的作用(Optimization Flag Potency)
在LLVM的编译中,loop unrolling, loop vectorization, switch- case optimization (-fjump-tables), and function inlining是造成差异的最重要的四个因素,同时tail call optimization(-fno-escaping-block-tail-calls)也在前10个因素中出现。
在GCC中,function inlining (-finline-small-functions) 是造成差异的最重要因素。而很多会影响到基本块的编译选项也出现在列表之中,如-freorder-blocks,-fbranch-count-reg 以及 -fpeephole2。 - 和其他工具的比较
- 对IoT恶意软件的作用