Symbolic Execution

知乎上有一篇对符号执行近些年的前沿研究较为详细的综述:

【论文总结】The Evolution of Symbolic Execution Engines - 知乎 (zhihu.com)

近些年学术界符号执行引擎优化的主要思路大体可以分为以下两类:

  1. 解释型:在程序执行过程中,对程序代码(通常是中间语言(IR)机器指令)进行解释来构建这种映射关系。一般而言,对程序指令进行这类解释执行,相比直接执行程序速度会变慢。故有些符号执行引擎会区分指令操作数是否包含符号值,如果包含,则解释执行;否则直接执行源程序代码。
  2. 编译型:在程序编译过程中,将这种映射过程编译到程序代码中,在程序执行时进行符号表达式的构建。相较于解释型,这种方法将“解释”过程移动到编译时,只解释程序代码一次。由于在执行过程中速度接近原始代码,这种设计显著提高了速度。

我们比较熟悉的Angr,KLEE都属于解释型,但编译型才是前沿的主流关注点

SymCC

把 QSYM 解释执行 LLVM IR 的函数,通过动态链接库,链接进来,到 binary 层去执行。

白泽带你读论文丨Symbolic execution with SYMCC: Don’t interpret, compile!_黑客技术

SymQEMU

借用并扩展了 QEMU 中的 TCG (Tiny Code Generator),以支持 Symbolic Execution。对比 SymCC,这次插桩的是 QEMU 的 TCG 而不是 LLVM IR;对比 S2E (也用了 TCG),把符号执行的 runtime 也 compile 进 QEMU 去执行了从而加速(思路和 SymCC 是一样的)。

SymSAN

SymSAN 在SymCC的基础上,将符号执行看作是数据流分析的一种特殊形式,结合基于LLVM的数据流分析框架DFSAN,对符号表达式的管理进行优化,提高了执行速度

作者 BLOG Kirenenko: Dynamic Symbolic Execution as Taint Analysis | Chengyu Song’s Blog

【论文阅读】SYMSAN: Time and Space Efficient Concolic Execution via Dynamic Data-flow Analysis (USENIX'22) - 知乎 (zhihu.com)

SymFusion

SymFusion 分析了编译型(编译时插桩)和解释型(执行时插桩)两类技术的优缺点:

解释型:

优点:

  1. 不需要重新编译程序
  2. 现代DBT(动态二进制转换工具)工具会生成架构依赖的IR来进行插桩,很容易支持大规模指令集
  3. 在二进制层面,程序语言设计的高维度概念被简化了,如在pointer、unsigned value、unsigned struct field之间并无区别

缺点:

  1. 插桩代码效率低下,通常在指令级或基本块级;DBT在JIT(即时编译)过程中优化能力有限;DBT会差异如一些无分支代码,当触发条件时让executor去调用helpers执行
  2. DBT使用内存中的virtual CPU来跟踪原始程序状态,需要额外内存访问来更新
  3. DBT的IR并不显示支持专用指令,而是在运行时去调用helper函数处理,如QEMU在处理x86的division operations、vectorized instructions和floating-point operations时。KLEE使用function models,比如klee-clibc,很容易编写但容易出错;S2E 将helper函数也转换成LLVM IR并使用KLEE去解释执行
  4. 即使executor能够对专用指令进行插桩,生成的符号表达式可能非常复杂以至于SMT solver无法求解

编译型:

优点:

  1. 执行时无插桩带来的开销
  2. 针对IR进行插桩,不仅能进行更复杂的代码转化,而且能够受益于原有的编译优化手段
  3. 支持跨架构

缺点:

  1. 需要引入自定义的编译工具链
  2. 新增编译工具链在原始编译过程中放置的位置难以确定。放到前面能够受益于之后的优化,但最终代码与之前差异过大,如替换一些call为inline code,可能导致它们不被插桩而影响符号执行分析
  3. 当一个函数未插桩时,需要创建一个函数模型来模仿这个函数的行为
  4. IR继承了很多复杂专用的数据类型,如array、vector、struct,增大了编写pass的复杂度

SymFusion结合两类技术,对不同的代码使用不同的插桩方式,如下图。internal code主要是用户程序代码,而external code时其他编译时未插桩的、采用动态链接的代码

SymFusion的执行流程,核心问题是如何协调两种插桩代码的执行(包括程序执行的具体数据、DBT需要的virtual CPU状态以及生成的符号表达式)