4.反编译的中间语言设计

过渡章节

注意：

这一章有太多的我的臆想以及不知道对不对的理论内容（毕竟我不是中间表示设计的专家），可以跳过不看。

这一章作为第三节与第四节的过渡章节，涉及到很多也许没什么用的理论知识：反编译器中的中间语言设计的理论知识。

但是，样本量太少了，没法判断哪个是最佳实践，而且我不是编译器或者中间语言的专家，说的可能不对，因此看着也就图一乐。

中间语言与反编译器

目前，通用反编译器全部使用的是龙书系的三地址码形态的中间语言 dest = op(src1, src2)。

因此本文不对中间语言的表示方式进行讨论（不讨论波兰式、树状等其它情况），一律使用三地址码或者类似的中间语言。

底层

底层的中间语言的目标是适配多种指令集与架构，并识别出具体的函数开头与结尾，分离指令和数据，处理间接跳转，将各种语言、架构归一化到一个指令集中；

使用中间语言，链接了指令集与反编译优化的实现。在后续若要支持新的指令集，只需要完成从指令到中间语言的翻译步骤，大大省略了其它工作。

Ghidra使用了来自于SLED、SSL的描述类语言，IDA则需要编写代码。

SLED-RED:https://dl.acm.org/doi/abs/10.1145/256167.256225

中层

中层优化，是中间语言最为复杂，工作内容最为多的步骤；中层主要目标是从汇编级别的中间语言，向上还原（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: https://gist.github.com/icecr4ck/6c744d489efbb07a32bb22e8a3c748e3

Ghidra的反编译器在编写时，没有相对明确的层次；

我按照个人的经验，将Ghidra的反编译器中端从里到外、从前到后整理，依次为：

  • action-base：通过流敏感技术，将机器码翻译成中间语言，识别函数，处理间接跳转等等。

  • action-stackstall：抽象操作栈信息，恢复栈变量

  • Varnode：还原高层变量信息

  • action-rule：窥孔优化，通过预置的规则对语义进行等价还原

  • typerecovery：还原类型信息

  • struct: 还原控制流信息

ghidra-decompiler-ref: https://www.lockshaw.io/static/ghidra/decompiler/doc/index.html

高层

高层次的中间语言，其实已经和中间语言没有太多的关系了，更像是抽象语法树（AST）的形态。

此时，高层次的抽象还原都已经完成；最终输出为人类可读的语言。

典型的任务就是生成变量名、函数名：对于反编译器来说局部变量没有名字，有很多种方法进行取名。

如果粗暴一点，那就分为：全局变量、函数参数、栈上局部变量、寄存器局部变量、指针、数组。通过变量的特征进行分类，加个前后缀就完成了。

对于字节码等有更多信息的反编译器结果，就有更好的选择方案，可以识别语义命名变量与函数。

反编译器的中间语言设计

这是一个很有意思的话题，如何设计通用反编译器的中间语言。但我也不是这方面的专家，说的不一定对，因此如果觉得有问题，请和我进行交流。

我列出了反编译器中间语言设计的关键决策的点；抛砖引玉，希望能有大佬帮忙看看我说的对不对。

ref:https://jonpalmisc.com/assets/slides/0x41con-2023-GetToKnowYourDecompiler.PUBLIC.pdf

是否使用一套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: https://github.com/gaasedelen/lucid

SSA（静态单赋值形式）

这个属于编译原理基础，如果有需要可以看下面这个链接：

中间语言与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》这个论文的关键思想：

你写个反编译器，最常用的优化就是各种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：https://zhuanlan.zhihu.com/p/22508731

很不幸IDA的中间语言的资料十分少，唯一能看的是IDA创始人的演讲

Ilfak's presentation at Recon 2018：https://recon.cx/2018/brussels/resources/slides/RECON-BRX-2018-Decompiler-internals-microcode.pdf

Ghidra的中间语言-pcode

Ghidra的中间语言相比之下，资源就比较多了，毕竟是开源的。

ref:

https://www.riverloopsecurity.com/blog/2019/05/pcode/

https://www.anquanke.com/post/id/196851

https://spinsel.dev/assets/2020-06-17-ghidra-brainfuck-processor-1/ghidra_docs/language_spec/html/pcoderef.html

其它的中间语言

截至目前，世界上的中间语言太多太多了，看看下面这个表：

经过几十年的发展，似乎每一种优化工具、编译器。都自己做一套中间语言，这已经是一种流行的趋势了。

当然，看看世界上的上千种编程语言，中间语言的数量可能还算少？

Previous3.汇总-反编译器中的反汇编Next4.调用约定识别-参数与返回值

Last updated