# 5.类型推导 所谓类型推导，就是从低级语言中还原出高级语言的类型信息；但是由于编译期间的信息损失，低级语言例如C语言的很多信息是不可能准确还原的。 反而是高级语言，尤其是支持包管理/自动内存管理/垃圾回收/高级数据结构的高级语言，其编译损失的信息更少，进行类型和语意的推导更为准确。 本章暂不涉及较为复杂的高级语言的类型还原，先分析目前通用的反编译器的类型还原技术，总得来说分为两步：类型推导和类型传播。 ## 反编译器中的“类型” 现有的通用反编译器，无论是IDA、Ghidra、JEB还是其它的，目标都是还原出C-like的高层伪代码，因此他们的类型系统设计时也是C-like形态。 ref: 同时，考虑到不同架构上的int整形长度可能有差别，为了避免歧义，反编译器定义的类型同时往往会带上具体字段长度。 例如，在Ghidra推导支持的类型信息在“Ghidra\Features\Decompiler\src\decompile\cpp\\[typeop.cc](http://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](http://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）的分析效率是个难题，随着程序规模的增大，全局指针分析技术的性能消耗也会指数级增加。现在反编译器的做法是不处理全局对象；也不使用全局的程序分析技术。