Quartz 4

反编译

7分钟阅读

历史

1994-Dr. Cristina Cifuentes: Reverse Compilation Techniques

在 Cifuentes 的工作中，她重申了这样的想法：在我们以控制流图（CFG）的形式有了反汇编程序之后，我们还有更多的工作要做：

控制流图……没有关于高级语言控制结构的信息，例如 if..then..elses 和 while() 循环。 这样的图可以通过结构化算法转换为结构化的高级语言图。

不断地自下而上地识别结构，直到用完可识别的结构。 请注意，由于特殊的 goto 结构，所以总是可以穷尽图中的模式并生成 C 代码。goto 结构可以从任何有边的节点构建，必须谨慎使用以获得合适的代码。 我一般将 Cifuentes 的论文总结为（隐含地）确定了反编译的三个基本支柱：

  1. CFG recovery (through disassembling) & Lifting
  2. Variable recovery (including type inferencing)
  3. Control flow structuring

HexRays, Reko,(2007), Snowman and fcd,binary ninja(2015),ghidra,(?, mayby same as hexrays)

TIE: Principled reverse engineering of types in binary programs (2011-the Carnegie Mellon team)

2024: USENIX   - Ahoy SAILR! There is No Need to DREAM of C: A Compiler-Aware Structuring Algorithm for Binary Decompilation
2024: USENIX   - A Taxonomy of C Decompiler Fidelity Issues
2024: IEEE S&P - "Len or index or count, anything but v1": Predicting Variable Names in Decompilation Output with Transfer Learning
2022: USENIX   - Decomperson: How Humans Decompile and What We Can Learn From It.
2022: USENIX   - Augmenting Decompiler Output with Learned Variable Names and Types.
2016: IEEE S&P - Helping Johnny to Analyze Malware: A Usability-Optimized Decompiler and Malware Analysis User Study.
2015: NDSS     - No More Gotos: Decompilation Using Pattern-Independent Control-Flow Structuring and Semantic-Preserving Transformations.
2013: USENIX   - Native x86 Decompilation Using Semantics-Preserving Structural Analysis and Iterative Control-Flow Structuring.

Of all the decompiler papers, only four are on control flow strucuturing:
在所有反编译器论文中，只有四篇是关于控制流结构化的：

2024: USENIX   - Ahoy SAILR! There is No Need to DREAM of C: A Compiler-Aware Structuring Algorithm for Binary Decompilation
2020: Asia CCS - A Comb for Decompiled C Code
2015: NDSS     - No More Gotos: Decompilation Using Pattern-Independent Control-Flow Structuring and Semantic-Preserving Transformations. 
2013: USENIX   - Native x86 Decompilation Using Semantics-Preserving Structural Analysis and Iterative Control-Flow Structuring

Phoenix: 条件感知模式匹配 Condition-Aware Schema Matching

  1. 当你无法找到合适的模式进行匹配时，你必须使用goto。将边转换为goto的过程称为虚拟化(virtualization)。
  2. 反编译中的跳转是不好的，减少它们。
  3. Coreutils is a good dataset for the evaluation of decompilers. Coreutils是对反编译器进行评估的良好数据集。

2的方法：

“… remove edges whose source does not dominate its target, nor whose target dominates its source.” 有向图中的支配

当今最受欢迎的反编译器遵循的原则与Phoenix中概述的相同。包括Ghidra，IDA Pro，和Binary Ninja。“我”认为它们输出结果的差异要么是基于更好的架构（IDA），要么是基于更好的提升（Ghidra）。Scheme和Lifting

DREAM: 无模式条件化结构 Schemaless Condition-Based Structuring

在进行反编译时不需要模式。相反，可以利用语句的条件生成语义上等效的代码。

A();
if (~x)
  B();
if ((~x && y) || x)
  C();
if (~x && ~y)
  D();
E();

再化简

A();
if (~x)
  B();
if (x || y) {
  C();
}
else {
  D();
}
E();

DREAM实现了一种非常有趣和有效的方法，使得代码始终没有goto语句。然而，梦想的方法也带来了两个基本的缺点：

  1. 简化任意布尔表达式是NP困难的
  2. 消除每一个goto意味着源代码中存在的goto将被消除

rev.ng: 代码克隆模式匹配 Code Cloning Schema-Matching

the paper “A Comb for Decompiled C Code” 0 goto DREAM在结果上通过复制条件消除goto，而rev.ng通过复制实际代码（块），称为Combing算法。 它试图将每个图形转换为一系列分层的菱形，从而产生结构良好的if-else树。 使用与Phoenix相同的结构化算法基础，但在结构化之前修复CFG。

→ 也会导致原有的goto也被消除

SAILR: 编译器感知结构化 Compiler-Aware Structuring

在Phoenix中，我们通过更多的模式减少了goto语句。在DREAM中，我们通过复制条件来减少了goto语句。在rev.ng中，我们通过复制代码来减少了goto语句。但是，一个问题从未得到解答，为什么反编译中会存在goto语句？此外，goto语句的减少是否是衡量反编译器改进的最佳方式？ 《Ahoy SAILR! There is No Need to DREAM of C: A Compiler-Aware Structuring Algorithm for Binary Decompilation》 大多数go的原因只是9种编译器优化 这一认识很重要，因为直到这一点，我们一直在不知道原因的情况下从反编译中移除了goto。在不理解根本原因的情况下做一些事情总会导致副作用，就像在DREAM和rev.ng中看到的那样。然而，什么也不做会导致反编译出现在源代码中不存在的goto，就像在Phoenix中看到的那样。 总结起来，SAILR可以归纳为三个要点：

  1. goto由编译器优化引起，其中许多可以还原。
  2. CFGED是一种新的算法，用于公平地衡量您与源头的距离。
  3. 并不是所有的goto语句都是邪恶的。

关系图谱