【博文笔记】Restructuring the Binary Ninja Decompiler

原博客文章链接：https://binary.ninja/2024/06/19/restructuring-the-decompiler.html

概述

Binary Ninja在4.1版本重构了反编译器，主要集中在其控制流结构化的策略上。这篇博文简单介绍了设计变化，同时这也是一篇挺好的介绍反编译器的主流控制流结构化策略的文章，值得记录一下。

所谓控制流结构化，就是识别控制流图模式，并将其转化/折叠为高级线性表示，例如C语言中的if...else...语句。

一般来说，在没有优化的情况下识别经典的C语言控制流语句生成的控制流图是非常容易的。但是在编译优化的影响下，函数控制流图的节点和边会被添加/删除/合并等，导致无法与经典控制流图模式相匹配。反编译器在面对控制流结构化时，最主要的挑战就是当控制流子图无法与现有模式匹配时，怎么做才能最大程度提高反编译结果的可读性和准确性？

主流的几个策略

遇事不决添加goto

这个策略算是所有反编译器都会采用的手段，主打一个无脑。**当控制流图无法与已知模式匹配时，反编译器会为节点添加goto语句，并删除其出边来简化图结构，从而与已知模式相匹配。**当然，编译优化会生成大量无规则的控制流图，如果不与经典控制流图模式相匹配的话，那就会产生可怕的goto地狱了！所以，主要采用这种策略的反编译器往往会预先保存大量的新模式，而不局限于几个经典的图模式，来简化反编译结果。

**这种方法的优点是灵活。开发人员可以根据需要添加任意数量的规则，以涵盖最新编译器中发现的新的或不常见的模式。缺点是需要维护大量这些规则才能获得良好的反编译结果。**几十年来，使用这些技术的产品一直在迭代其控制流解析规则。

看到图里最后的结果是不是有种熟悉的感觉？没错，无论从最后生成的结果来看，还是从其诞生的年代来看，IDA的控制流结构化策略很明显就是这种简单粗暴、力大砖飞的设计。一直以来，hex-ray收集的这些图模式都是他们的护城河。

添加/复制虚拟节点

第一种方法需要不断添加新模式，以适应不断迭代的编译优化产生的新控制流图模式。有没有一些更简单的方法可以不那么经常维护，也可以获得高可读性和准确性的匹配结果？

论文《No More Gotos》描述了一种方法：探索到达每个节点所需要的条件，生成条件图，再根据条件图来生成高级代码。这种方案最终产生的结果会没有goto语句，取而代之的是它会大量复制条件语句，来填补因编译优化而缺失的边。Binary Ninja在旧版本就使用这种方案。

除此之外，论文《A Comb for Decompiled C Code》（也就是最初版本的revng反编译器）描述了另外一种方法：编译器优化经常删除重复代码，并添加更多的边来减小函数尺寸，那么可以将入度大于一的节点进行复制，从而消除这种优化，使新的控制流图能够与已知模式匹配。

Binary Ninja此前的策略

如前面所述，Binary Ninja此前主要使用论文《No More Gotos》描述的方法。当一个代码区域无法简单地解析为一组简单的 if 条件时，Binary Ninja 将获取组成该区域的节点并计算到达每个节点所需的条件，以保持程序顺序的方式遍历节点。一旦构造了条件图，就对其应用规则以简化图。这包括合并常见条件、检测 if/else 结构以及解析 switch 语句。一旦不再可以应用优化，Binary Ninja 就会将条件图转换为高级 IL，并用包含该高级 IL 的单个节点替换该图的整个区域。

这种方法的优点在于当编译器优化主要在于删除重复的到达条件时，可以很大程度上避免使用 goto 语句来解析优化图，从而生成更自然的代码。作为对比，以下是使用更传统方法的其他主要反编译器将为上图的示例构造生成的内容：

if (!A) {
    C
    goto label;
}

if (B) {
    D
} else {
label:
    E
}

但这种方法也有很大的缺点：不仅会生成大量嵌套的if/else，并且当遇到编译器删除重复代码而不是条件的代码时，或者当原作者使用 goto 语句手动组合两个或多个路径时，条件图解析器可能无法生成可读条件。

例如这个示例，switch 语句有一条额外的边从其他地方进入构成默认情况的代码块：

在默认情况下生成 H 的条件时，条件图会生成一个大条件：

if (x == 4 || (x <= 0 && y != 0 && y != 1 && y != 2 && y != 3 && y != 4 && y != 5 && y != 6))

如果 switch 语句包含在另一个 if 语句中，则条件会复合并产生极难读取的条件。经过优化的大型复杂软件通常会创建复杂的控制流图，这些控制流图产生的条件比此处显示的条件要差几个数量级。

虽然Binary Ninja会在生成的条件过于复杂时添加goto语句来规避，但引入goto语句又会导致更多的问题，例如条件图解析进一步出现错误等，所以单纯使用这种方法已经不足以进一步提高反编译结果的可读性和准确性。

修改后的策略

可以很容易地发现在解析成条件图后可以简单地重新将其组合成一个新的控制流图。这意味着我们可以直接在控制流图本身应用条件图算法，甚至可以与其它控制流结构化算法相结合进行使用！

新的控制流结构化策略可以看作是一个框架，在这个框架里，我们可以对控制流图应用多种变化来进行简化，而不单单只是使用条件图算法。

它的主要思路：*图被分成具有单个入边和单个出边的区域，并且构成这些区域的图被单独解析。首先解析最里面的区域，使图形解析尽可能简单。循环的解析方式与之前相同，即循环体被提取到要解析的子图中。新算法没有构建条件图，而是首先创建一个包含区域内节点的子图。*解析区域的最终目标是制作一张图，其中不存在入度大于一的节点。每个节点入度至多为一的图很容易解析为已知的控制流结构。当节点具有多个入边时，有一组可应用于图的转换原语以减少传入边的数量。Binary Ninja应用转换直到达到目标，然后为结果图生成结构化的高级 IL。然后该区域被包含 IL 的单个代码替换。

一起看看Binary Ninja准备了哪些转换原语吧。

&& 和 || 转换

最简单的转换采用嵌套条件并将它们转换为单个条件。

条件复制

这个就是条件图算法所做的事，也是Binary Ninja旧算法。执行这个转换后，仍然有可能出现一个节点具有多个入边，这时候就需要下一个转换来进一步进行解析。

子区域解析

在应用变换来简化图之后，最终可能会得到具有单个入边和单个出边的图的新区域。这些区域是可独立解析的。如果这些子区域之一出现在图中，则可以将其提取到一个新图中并使用相同的算法对其进行解析。结果是一个具有结构化 IL 的节点，可以用单个节点替换整个区域，然后该过程继续使用简化图。

可以明显注意到，这个解析原语可以弥补原条件图算法的一个缺点，即过度嵌套的if/else语句。这个解析原语会消除大量else语句的使用。

代码节点复制

这个方法就是前面提到的论文《A Comb for Decompiled C Code》指示的方法，不过多赘述。

跳转表转换

由于编译器生成跳转表的方式， switch 语句几乎总是前面有一个 if 语句，以确保永远不会越界访问跳转表。此 if 语句仍然显示在控制流图中，但它通常会在默认情况下产生额外的边，如下所示：

此转换查找带有“无法访问的默认值”标志的 switch 语句，并检查周围的条件。如果存在一个节点，其中条件中的边覆盖了除 switch 语句中的其他边之外的所有可能情况，它会重写控制流图以将该节点转换为 default 情况，并且删除条件。

合并相邻代码块

这个很直观了.jpg

goto语句插入

当其它方案均不适合时（例如“条件复制”可能会导致条件图解析复杂度爆炸等），就会使用最后的方式：插入goto语句以删除边。就如前面介绍的那样。

总览

可以看到，这样设计框架的好处是可以混合多种图模式处理，但随之而来的挑战就是**在什么时候应用哪些策略及其顺序是效果最好的？**这个问题似乎没有标准答案，只能通过不断添加的启发式规则来尽可能贴近了。

测试与效果

Vector35的人为新编译器设计实现了一个新的测试生成器框架，用以生成各种奇怪的控制流图来测试新编译器的控制流结构化效果。不过他们好像没有开源，真遗憾，不然还能抄一抄借鉴一下。

最后贴个转换效果对比。

Binary Ninja 4.0的输出：

if (allocated == 0xf)
    puts(str: "Nothing more!")
else
    allocated += 1
    printf(format: "Choose an index: ")
    int64_t index
    __isoc99_scanf(format: "%lu", &index)

    if (weapons[index].detail_size != 0 || weapons[index].details != 0 || index u> 0xe)
        puts(str: "[-] Invalid!")
    else
        printf(format: "\nHow much space do you need for it: ")
        uint64_t n
        __isoc99_scanf(format: "%lu", &n)

        if (n u<= 0x1f || n u> 0x38)
            puts(str: "[-] Your inventory cannot provide this type of space!")
        else
            weapons[index].detail_size = n
            weapons[index].details = calloc(n, elem_size: 1)

            if (weapons[index].details == 0)
                puts(str: "[-] Something didn't work out...")
                exit(status: 0xffffffff)
                noreturn

            puts(str: "Input your weapon's details: ")
            read(fd: 0, buf: weapons[index].details, nbytes: n + 1)

Binary Ninja 4.1的输出：

if (allocated == 0xf)
    puts(str: "Nothing more!")
    return

allocated += 1
printf(format: "Choose an index: ")
int64_t index
__isoc99_scanf(format: "%lu", &index)

if (weapons[index].detail_size != 0 || weapons[index].details != 0 || index u> 0xe)
    puts(str: "[-] Invalid!")
    return

printf(format: "\nHow much space do you need for it: ")
uint64_t n
__isoc99_scanf(format: "%lu", &n)

if (n u<= 0x1f || n u> 0x38)
    puts(str: "[-] Your inventory cannot provide this type of space!")
    return

weapons[index].detail_size = n
weapons[index].details = calloc(n, elem_size: 1)

if (weapons[index].details == 0)
    puts(str: "[-] Something didn't work out...")
    exit(status: 0xffffffff)
    noreturn

puts(str: "Input your weapon's details: ")
read(fd: 0, buf: weapons[index].details, nbytes: n + 1)

补充链接

对反编译感兴趣的可以看看这个，虽然目前内容好像还很少：https://decompilation.wiki/