5.类型推导

通用方法的类型还原

所谓类型推导，就是从低级语言中还原出高级语言的类型信息；但是由于编译期间的信息损失，低级语言例如C语言的很多信息是不可能准确还原的。

反而是高级语言，尤其是支持包管理/自动内存管理/垃圾回收/高级数据结构的高级语言，其编译损失的信息更少，进行类型和语意的推导更为准确。

本章暂不涉及较为复杂的高级语言的类型还原，先分析目前通用的反编译器的类型还原技术，总得来说分为两步：类型推导和类型传播。

反编译器中的“类型”

现有的通用反编译器，无论是IDA、Ghidra、JEB还是其它的，目标都是还原出C-like的高层伪代码，因此他们的类型系统设计时也是C-like形态。

ref: https://www.geeksforgeeks.org/data-types-in-c/

同时，考虑到不同架构上的int整形长度可能有差别，为了避免歧义，反编译器定义的类型同时往往会带上具体字段长度。

例如，在Ghidra推导支持的类型信息在“Ghidra\Features\Decompiler\src\decompile\cpp\typeop.cc”中进行了定义，具体如下，注意Ghidra的类型具体长度是与程序的架构相关的:

/// The core meta-types supported by the decompiler. These are sizeless templates
/// for the elements making up the type algebra.  Index is important for Datatype::base2sub array.
enum type_metatype {
  TYPE_VOID = 14,		///< Standard "void" type, absence of type
  TYPE_SPACEBASE = 13,		///< Placeholder for symbol/type look-up calculations
  TYPE_UNKNOWN = 12,		///< An unknown low-level type. Treated as an unsigned integer.
  TYPE_INT = 11,		///< Signed integer. Signed is considered less specific than unsigned in C
  TYPE_UINT = 10,		///< Unsigned integer
  TYPE_BOOL = 9,		///< Boolean
  TYPE_CODE = 8,		///< Data is actual executable code
  TYPE_FLOAT = 7,		///< Floating-point

  TYPE_PTR = 6,			///< Pointer data-type
  TYPE_PTRREL = 5,		///< Pointer relative to another data-type (specialization of TYPE_PTR)
  TYPE_ARRAY = 4,		///< Array data-type, made up of a sequence of "element" datatype
  TYPE_STRUCT = 3,		///< Structure data-type, made up of component datatypes
  TYPE_UNION = 2,		///< An overlapping union of multiple datatypes
  TYPE_PARTIALSTRUCT = 1,	///< Part of a structure, stored separately from the whole
  TYPE_PARTIALUNION = 0		///< Part of a union
};

IDA 也是类似，但更加直观，直接把类型限制死了，管你是哪个平台算出来都是这么几个。这也是为什么在ida无法正确判断变量类型是，会使用__intXXX 来进行标记的原理。

ref：https://hex-rays.com/blog/igors-tip-of-the-week-45-decompiler-types/

推导初始类型

在反编译中通过两个维度推导一个变量的初始类型：操作长度和操作类型

例如，mov rax, [rbx] 这个指令会对rbx进行取址，那么此时rbx就是一个长度为64bit的指针类型（这好像是废话，64位程序的指针长度只能是64位），rax是一个64bit的未知类型。

首先，反编译会对中间语言的各个操作符预先定义好类型信息。

我们以Ghidra为例，在\Ghidra\Features\Decompiler\src\decompile\cpp\typeop.cc一开头就有一段很长的代码，把所有涉及到的中间语言操作对应的预制类型信息初始化了。

初始化将类型分为有符号、算数、逻辑操作、浮点等几类（指针类型的操作判断是在类型传播过程中完成的）

enum {
    inherits_sign = 1,		///< Operator token inherits signedness from its inputs
    inherits_sign_zero = 2,	///< Only inherits sign from first operand, not the second
    shift_op = 4,		///< Shift operation
    arithmetic_op = 8,		///< Operation involving addition, multiplication, or division
    logical_op = 0x10,		///< Logical operation
    floatingpoint_op = 0x20	///< Floating-point operation
  };

传播类型与类型约束

介绍基于”格”理论的类型传播与约束系统：参考下图，所有的变量的类型都是从上到下变换。其中，上界(T) == unknow-类型未推导，下界(⊥) == conflict-类型冲突

每当一个变量进行了某些操作，就会在这个图上走下来。在上图中，类型有且只能从上往下走，最终对一个变量的所有操作都执行过后，它最终停留的点就是推断的类型。

例如，读取内存和写入内存的中间语言很明显就意味着指针类型。这意味着某个变量很可能是指针

ref: https://www.ndss-symposium.org/wp-content/uploads/2017/09/lee2.pdf

展示类型和类型转换

所有的变量类型都已经完成推导，现在假定我们已经到了伪代码最终还原的阶段，那还存在两个问题

• 类型操作存在冲突怎么办

• 已有的信息不足以推导出有用的类型，那如何展示

第一个问题，如果推断的类型存在冲突，通用的处理方法：插入类型转换的提示信息。

第二个问题就比较麻烦了，目前来说有这么两种方案。

第一种就直接啥都不管直接输出一个unknow、undefine或者推断的上界（也就是T）；

Ghidra就是这样做的，我觉得这种做法十分的糟糕，尤其是大型程序里看到这种东西，十分令人不舒服。

第二种，展示有效的信息，比如IDA就会展示变量的_BYTE、_WORD、_DWORD等宽度信息：

反编译器预置的类型信息

为了缓解反编译器不支持结构体识别的缺陷，主流的做法是预置各种常用的结构体类型信息。

比如常用系统调用返回的结构体、JNI的各种结构体等等。最为典型的做法，就是在逆向android-native-lib时手动定义的JNIEnv。

通用方案缺陷

通用方案有很多很多的缺陷，甚至可以说，反编译F5的结果看的很累，很大程度上也是因为类型系统还原技术的不足。

当然，也不能全怪反编译器，因为这个功能的确很难做，很多问题还是无解的。

因此，接下来的补充章节，将介绍这10多年来学术界对这方面的探索，希望有落地的那一天，解放逆向工作者。

缺陷1：无法全自动的识别结构体

当前的反编译器的方式是不会自动还原任何自定义的结构体，大部分的结构题都是预置的，然后通过特殊的系统函数进行传播。

缺陷2：不支持面向对象语言

和结构体问题类似，当前通用反编译器的反编译层级是“函数”，这是典型的过程间抽象语言的概念。考虑到IDA与Ghidra等通用反编译器的设计是在30年前，那时候没有什么高层级抽象的语言。这也可以理解。

但是，现代的程序有很多使用Go、Rust、现代C++等“高级语言”进行编写。

这一类的语言的反编译器开发的工作量更为复杂，尤其是还原其中的各种class的类型等等工作；甚至说:“我们已经没有必要把所有程序都还原成C-like的形态”

缺陷3：无法获得全局以及指针传播的间接类型

考虑到对于大型二进制（超过100M）的分析效率是个难题，随着程序规模的增大，全局指针分析技术的性能消耗也会指数级增加。现在反编译器的做法是不处理全局对象；也不使用全局的程序分析技术。