Docs of optimizers

项目使用LLVM Pass框架来进行反编译中的中间代码优化。

LLVM Pass入门资料

入门教程banach-space/llvm-tutor: A collection of out-of-tree LLVM passes for teaching and learning (github.com)

中文文章[翻译]现代化地编写LLVM Pass -- part I-外文翻译-看雪论坛-安全社区|安全招聘|bbs.pediy.com (kanxue.com)

变量恢复

  • 优化：wasm解析为IR后先优化一下，对后续反编译有好处。运行LLVM的一系列代码优化，包括SSA构建（Promote）。
  • 全局栈指针识别：在第一个基本块，在任何内存访问之前，是否对全局变量进行了一读一写的修改，且写的是读出的值加一个常量。是的话就认为是栈指针。如果大于等于一半的函数是同一个栈指针，则标记它为全局的栈指针。
  • 指针识别：基于已有的指针类型，运行基于Datalog规则的指针类型分析，将所有替换为指针。
  • 类型识别：基于Retypd，

栈指针识别

背景：根据《An Empirical Study of Real-World WebAssembly Binaries: Security, Languages, Use Cases.》这篇paper，有约一半的wasm都使用global 0作为栈指针。这说明针对栈指针的分析的重要性。这也是向更通用的算法拓展的一步。

算法：在第一个基本块，在任何内存访问之前，是否对全局变量进行了一读一写的修改，且写的是读出的值加一个常量。是的话就认为是栈指针。

局限性：可能出现加载栈指针后，先存在局部变量里读出再sub的情况。我们通过在分析前调用 Promote 这个SSA构建的pass，缓解这个问题。

指针类型识别

为了简化考虑，把一切都平坦化，假定栈大小固定，则可以看作栈上都是普通的基本类型变量。不考虑数组，把数组看作是结构体的特殊情况。不考虑数组下标，都看作是指针的整数加减运算。

背景：在二进制层数字和指针是混在一起的。因此往往需要把未经分析的值看作比如undef32类型，然后在分析过程中设置为更细分的数字类型和指针类型。可以看作是一个类型的lattice。

类型分析是少数可以用数据流术语表达的问题之一，并且是真正双向的。

  1. 定义的类型影响使用的类型
  2. 使用的类型影响定义的类型：
  3. 库函数调用（看作使用）影响之前的定义，已知返回值类型的赋值影响之前的定义。引用参数调用影响之前的定义。

wasm指针：现在内存不是直接访问的：即load和store指令会在加载和保存的时候，将偏移加上mem0的基地址。但是，如果一旦引入了类似于直接alloca的这种情况，则它将是直接地址，而不是直接加上mem0的基地址。问题在于，可能会有指针混指的情况，即可能指向全局变量或者栈空间变量。这样在后面load/store的时候，无论是加上mem0的基址还是不加都有问题。因此引入地址空间的概念。将wasm的内存指针单独分离出来，成为独立的地址空间。

算法：双向的传播问题，可以用传统的数据流分析实现，但是较为复杂。先使用Datalog进行原型设计，后期再改进。

  • 加法运算：数字加数字，指针加数字，数字加指针，三种情况。
    • 如果运算的参数中有指针，则结果也是指针。
    • 如果发现了一边是指针，另一边大概率是整数类型，同时结果类型也是指针类型。
    • 反向推导：如果运算的结果是指针类型，则里面至少有一个指针类型。
      • 如果已知某个参数是整数，则另一个参数为指针类型
      • 如果已知某个参数是指针类型，则另外一个参数为整数类型。
  • 减法运算：数字减数字，指针减数字，指针减指针（小概率），指针减法运算
    • （如果不考虑指针减去指针）第二个参数是数字类型。
    • （如果不考虑指针减去指针）第一个参数是指针类型，结果也是指针类型。
    • （a-b=c）如果a是指针，b是数字，则c是指针
    • （a-b=c）如果a是数字，则b和c都是数字
    • （a-b=c）如果b是指针，则a是指针，c是数字

变量访问识别

进一步识别每个内存访问，以及涉及的加法运算。

  • 加法运算：某个类型的某个偏移出

结构体的识别的关键在于，我是从谁那里，加了一个偏移。一般是从栈指针，但是一旦是从别的变量那边加出来的，这时候可能就代表着结构体。

实现

  • 识别并消除函数开头和结尾的栈指针操作
  • 把对mem0的取下标+load/store操作，根据全局变量还是局部变量，转变为（新创建的）局部变量或者全局变量的操作。

清除IR中的全局栈指针，并对其使用处的指令操作数(局部变量地址)进行转换，转换为对alloca里的东西的使用，把对mem0的使用，其中的使用mem0的栈部分，改为使用我们的alloca。

变量分为全局变量，局部变量，堆变量，堆变量一般直接调函数分配，暂时不考虑。

  • 全局变量的访问：对mem0取下标的这个值是常量（范围大致在1024到一个很大的值之间）【可能存在偏移运算】
  • 局部变量的访问：对mem0取下标的值，是栈指针（取global 0）【可能存在偏移运算】
  • 也可能直接把地址存入变量里，即取地址。

其中偏移运算可能是常量也可能是变量，是变量时甚至可能存在乘法运算。 （如果把栈指针存到了结构体里怎么办？假装它没有定义结构体，定义了很多零散的变量？）结构体的问题在于，成员地址可能基于结构体自身的指针计算得到

  • 如何判断global0是不是栈指针
  • 如何匹配函数开头的栈指针的sub操作
  • 如何判断哪些值是栈内存的指针

如何判断哪些值是栈内存的"抽象解释"算法

和传统的数据流分析不同的地方在于，LLVM是SSA形式，每个值只有一个赋值点。因此，一个值要么是栈指针，要么不是。因此只需要直接循环迭代。但是LLVM里还是有变量，即alloca出来的值，可能因为控制流的跳转而来自不同的取值，从而导致基于变量计算出来的值，依赖于这个变量是不是和栈指针有关的东西。

要分析清楚对mem0取下标的这个值，是不是来自stackpointer的运算。

  1. 一定来自stack pointer
  2. 可能来自stack pointer
  3. 一定不来自stack pointer

为每个llvm的Value维护一个bool类型变量表示是否是栈指针。 遍历所有基本块（可能拓扑排序会高效一点），直到某次完全遍历也没有任何变化 初始化：算法开始前已经判断了函数开头的栈指针值，对应的bool设置为true 如果遇到了运算，任意一个输入值对应true的话，结果也设置为true。

把变量也标为是栈指针类型？所有对这个变量的load都是栈指针？

union怎么办？先不考虑。

目前的解决方法： 遇到内存访问指令沿着use-def向上回溯，构造一条chain 看是否可达sp,如果可达，那么就是栈地址，并把它放在栈相关集合中。 如果存进去的值也是栈地址，那么就把对应偏移的放在另一个栈相关集合中。

TODO:

1.需要实现过程间分析，如果call指令的参数和返回值都是栈地址，需要把它们放到栈相关集合中。

能否保证语义安全？因为我们现在转出来的IR是能跑的，如果变量恢复后，是不是就不能跑了？比如部分变量识别失败，还是存到mem里去了。