# 4.反编译的中间语言设计 现在，我们将进入反编译器中最重要的部分：中间语言和程序分析以及优化的章节。 **注意：** **这一章有太多的我的臆想以及不知道对不对的理论内容（毕竟我不是中间表示设计的专家），可以跳过不看。** 这一章作为第四节的开篇，涉及到很多也许没什么用的理论知识：反编译器中的中间语言设计的理论知识。 但是，样本量太少了，没法判断哪个是最佳实践，而且我不是编译器或者中间语言的专家，说的可能不对，因此看着也就图一乐。 ## 中间语言与反编译器 目前，通用反编译器全部使用的是龙书系的三地址码形态的中间语言 dest = op(src1, src2)。 因此，本文不对中间语言的其它表示方式进行讨论（例如波兰式、树状等其它情况），一律使用三地址码或者类似的中间语言。 ### 底层 底层的中间语言的目标是适配多种指令集与架构，并识别出具体的函数开头与结尾，分离指令和数据，处理间接跳转，将各种语言、架构归一化到一个指令集中； 使用中间语言，链接了指令集与反编译优化的实现。在后续若要支持新的指令集，只需要完成从指令到中间语言的翻译步骤，大大省略了其它工作。 Ghidra使用了来自于SLED、SSL的描述类语言，IDA则需要编写代码。 SLED-RED: ### 中层 中层优化，是中间语言最为复杂，工作内容最为多的步骤；中层主要目标是从汇编级别的中间语言，向上还原（lift）立体的高级语言抽象。比如控制流、变量、类型系统、语义等等。 IDA中间语言使用了8层转换完成这一步，每向上一层中间语言就能缩减一部分，从下到上依次为： * MMAT\_GENERATED：等价于汇编 * MMAT\_PREOPTIMIZED：在basic-block上构造def+use+kill关系 * MMAT\_LOCOPT：在basic-block完成局部优化，构造CFG，处理基于规则的窥孔优化 * MMAT\_CALLS：基于调用约定识别函数调用、参数、返回值 * MMAT\_GLBOPT1：将call的各种block进行合并，全局优化，全局死代码消除 * MMAT\_GLBOPT2：全局优化，全局常量传播与条件优化 * MMAT\_GLBOPT3：全局窥孔优化 * MMAT\_LVARS：局部变量还原 因为IDA给源码给的很少，很难细化分析每个阶段的内部细节 ida-micorocode-ref: Ghidra的反编译器在编写时，没有相对明确的层次； 我按照个人的经验，将Ghidra的反编译器中端从里到外、从前到后整理，依次为： * action-base：通过流敏感技术，将机器码翻译成中间语言，识别函数，处理间接跳转等等。 * action-stackstall：抽象操作栈信息，恢复栈变量 * Varnode：还原高层变量信息 * action-rule：窥孔优化，通过预置的规则对语义进行等价还原 * typerecovery：还原类型信息 * struct: 还原控制流信息 ghidra-decompiler-ref: ### 高层 高层次的中间语言，其实已经和中间语言没有太多的关系了，更像是抽象语法树（AST）的形态。 此时，高层次的抽象还原都已经完成；最终输出为人类可读的语言。 典型的任务就是生成变量名、函数名：对于反编译器来说局部变量没有名字，有很多种方法进行取名。 如果粗暴一点，那就分为：全局变量、函数参数、栈上局部变量、寄存器局部变量、指针、数组。通过变量的特征进行分类，加个前后缀就完成了。 对于字节码等有更多信息的反编译器结果，就有更好的选择方案，可以识别语义命名变量与函数。 ## 反编译器的中间语言设计 这是一个很有意思的话题，如何设计通用反编译器的中间语言。但我也不是这方面的专家，说的不一定对，因此如果觉得有问题，请和我进行交流。 我列出了反编译器中间语言设计的关键决策的点；抛砖引玉，希望能有大佬帮忙看看我说的对不对。 ref: ### 是否使用一套IR贯穿整个反编译器设计？ 这个问题很难回答，因为现有的反编译器中IDA和Ghidra使用了一整个IR贯穿式的流程，即所有的优化都在这个IR上； 而就我所知，只有binary-ninja使用了上中下的完整的三层IR（这是不是又用力过猛了？）； 还有jadx这种为了最大程度的保留语义，几乎不转换IR，直接在原有的字节码上开整的。 我观察了binary-ninja的实现，并不认为完整的三层IR对于反编译器有特别大的好处，反而是一些同样的工作需要在各层上重复实现。 较为合理的做法，应该是学习Ghidra，在底层使用SSL描述形语言实现多指令集架构的支持，并使用一套IR贯穿整个中层优化，最后在上层特化的编写高级语言的输出。 ### 多层显示中间表示？单层显示中间表示？ 这也是一个很重要的话题，多层还是单层的选择，直接决定了后续反编译器优化功能的设计。尤其是如果选择了多层的显示中间表示，优化步骤在哪一层执行十分重要。 在编译优化中，LLVM就使用了单层显示中间表示；方舟编译器Maple使用多层显示中间表示（待确认）。 在反编译器中Ghidra使用了单层显示中间表示，而IDA选择多层显示中间表示。 **1、单层中间表示** 单层显示中间表示：意味着所有的优化工作都在一个层上完成，整个中间层是一个大状态，每个反编译组件维护自己的小状态。 * 没有明确的层次区分，优化之间可以嵌套，整个中层优化是一个整体，无法单独展示单个优化。 * 各个优化循环的执行，直到状态不再改变，意味着无法继续优化，即反编译结束。 典型的实现就是Ghidra，可以参考后续章节中对Ghidra架构的说明（在写了，在写了） **2、多层中间表示** 多层中间表示，意味者将优化显示的分为几个层次，每层只干自己的事情。 * 越在底层，越扁平，信息越少，越接近机器语言（汇编）。 * 越到高层，中间表示的抽象程度越高，越立体，越接近高级语言； * 只能从底层到高层单向执行，每一层有独立的状态，每一次都能单独输出并展示。 * 每一个优化功能，有明确的层级，只能在对应的层级执行，使用对应层级的资源。 典型实现就是IDA，看下面的截图，很好的描述了IDA反编译内部的分层。后续将在IDA中间语言优化插件编写章节更为详细的讨论这一部分。 ida-ref:
### SSA（**静态单赋值形式**） 这个属于编译原理基础，如果有需要可以看下面这个链接： {% embed url="" %} ### 中间语言与SSA 反编译器的中间语言优化要不要使用SSA？ 目前来看，IDA的中间优化没有使用SSA技术（IDA只在最后一步MMAT\_LVARS变量还原中使用了类似于SSA构造的技术），为什么呢？ **我个人猜测**： 第一个原因，因为IDA中间语言设计的时间大概在1993年左右，那时候和现在不一样，并不流行以SSA作为中间语言的表达形式。IDA的设计受到了Cristina Cifuentes的博士论文《Reverse Compilation Techniques》和这一论文提出的DCC反编译器原型的影响。 第二个原因，Mike Van Emmerik的博士论文《Static Single Assignment for Decompilation》 很好的说清楚了在反编译器上使用SSA形态的好处。这篇论文也深刻的影响了后续反编译工具，例如Ghidra的中间优化的设计。但是这篇论文发表举距离IDA的出现晚了10多年。 **我用自己的话来描述一下，《Static Single Assignment for Decompilation》这个论文的关键思想：** ```c 你写个反编译器，最常用的优化就是各种dead-code-elimnation 以及 各种propagation，包括你的变量还原。这么多的功能，都要在中间语言上去算define与use关系。 如果不用SSA，就要去在basic-block上算下面这个数据流方程： Data-flow equations in[n] = use[n] ∪ (out[n] – def[n]) out[n] = ∪ in[s] 这个方程可不好算，代码不好写，看起来也不直接（是的IDA就是用这个方程做的） 既然这样，不如用我论文提出来的方法，计算use-define-chain同时，把寄存器和内存的使用转换为SSA形式。这样，后面的各种优化工作写起来就方便多了。输出的东西也直观。 ``` 因此，后续反编译器的设计，将大多数优化步骤都在SSA中间语言完成 ### 什么时候进入SSA的形式？什么时候退出SSA形式? IDA只有在最后进行变量识别与整合的时候，会使用类似与SSA形式转换的算法。这是因为的寄存器分配算法和反编译器的变量还原算法，有太多的相似的地方。 Ghidra则是一旦进入数据流分析，在完成基于调用约定的函数原型绑定后，立即进入SSA形式，直到变量还原工作完成，在控制流还原前才不再对SSA进行操作。 Binary-ninja更为特别，它的前端、中端、后端都有独立的中间语言，三层的中间语言又有各自的SSA形态。也就是说，它会反复横跳+多次转换。 ### SSA要和寄存器和局部变量同步处理吗？ * IDA的做法：完全不使用SSA，寄存器和栈做为变量，再生成一些临时变量。这种做法的好处是，反编译可以优化到十分的准确，坏处是每一种指令集架构都要重头开始写转换代码，十分的痛苦。 * Ghidra的做法：寄存器和SSA并列同步处理，好处很明显，将对SSA的处理同步到CPU架构上，可以脱离各个指令集，只编写一套处理机制的代码；并且一定程度上复用代码。缺点是实现算法特别难写，反编译效果往往也没想像中好。 * RetDec的做法（待确认）：抛弃寄存器完全使用SSA，通过一系列的规则，将所有的内容转化为一种SSA的中间语言（比如LLVM）后，和以前的二进制进行切割完全没有关系了。我觉得这种做法的唯一好处是，工作量比较小，因为LLVM这种中间语言已经有很多人写了各种优化算法了，直接拿来用就行。 ## IDA的中间语言-micorocode 不使用SSA形式，而是自己内部在每个basic-block上实现了use-define-kill的功能，和SSA形态的能力类似；但是在30年后今天，这种做法已不这么流行。有点像**Testarossa**的设计 ref： 很不幸IDA的中间语言的资料十分少，唯一能看的是IDA创始人的演讲 Ilfak's presentation at Recon 2018： ## Ghidra的中间语言-pcode Ghidra的中间语言相比之下，资源就比较多了，毕竟是开源的。 ref: ## 其它的中间语言 截至目前，世界上的中间语言太多太多了，看看下面这个表：
经过几十年的发展，似乎每一种优化工具、编译器。都自己做一套中间语言，这已经是一种流行的趋势了。 当然，看看世界上的上千种编程语言，中间语言的数量可能还算少？