【论文笔记】Ahoy SAILR! There is No Need to DREAM of C A Compiler-Aware Structuring Algorithm for Binary Decompilation

概要

这是目前已知的第一篇探究编译优化是如何具体影响反编译器控制流结构化并试图逆转这种优化的论文。

ASU（shellphish）的研究团队认为，反编译器的结果质量衡量最重要的不是降低复杂度或者消除goto，是尽可能接近原始源代码。而**产生不可控制流结构化的控制流图的根本原因，就是编译器优化以及反编译器和编译器之间的知识差距。**为此，反编译器必须是“编译器感知”的，能够知道当前没能正确匹配的控制流子图是由哪些编译优化引起的，又该如何“反优化”。

为了验证这一目标，作者探究了具体的编译优化选项会导致怎样的异常控制流图，同时在angr的反编译器上开发了第一个“编译器感知”的控制流结构化算法：SAILR。并且经过测试，发现SAILR的CFGED等指标可以与IDA Pro相接近，并且领先于先前的研究成果，如DREAM、revng等。

介绍

在恢复C控制流结构时，原始的控制流结构会被编译器优化所扭曲和破坏。这在反编译器的输出上表现为虚假的goto语句。

文中认为，产生不可结构化代码的根本原因是：编译器优化以及反编译器与编译器的知识差距。

反编译器常常使用图模式匹配来结构化控制流子图，但由于编译器优化导致不可能穷举所有可能的控制流模式，所以反编译器采用删除边并添加goto创建新子图，来与已知模式匹配。

SAILR对GCC不同的编译优化选项进行测试，得出了几类关键的改变控制流子图的类型，并将其分为三大类，针对每一类进行不同的优化。

测试上，采用GED和CFGED来作为指标衡量。

前人工作与动机

文章把先前的控制流结构化算法分为两类：图模式匹配和无goto算法。具体参见：https://janlittle.github.io/2024/07/06/【博文笔记】Binary-Ninja-4-1-Decompiler-Design/

第一类算法需要不断添加新的图模式来保持反编译效果，但新的编译优化产生的图模式是不可能穷尽的；第二类算法看起来很好，但论文作者认为：如果假设在一个流行的和积极维护的代码库(比如GNU包中的代码)中的C源代码是程序逻辑的高质量实现，那么，当反编译由高质量代码编译的二进制文件时，结构上接近源代码的反编译是高质量的。根据这个假设，作者手动评估了DREAM和Phoenix两个算法的结果，发现它们生成的伪代码在结构上与源代码差距较大，从假设出发，这样的反编译结果质量不高。究其原因，就是因为单纯的无goto算法无法还原编译器优化所带来的控制流改变。

具体类型划分

在没有任何优化和除了本身就在源代码中的goto之外，每一个C控制语句生成的控制流结构都可以用一个单入边、单出边的图来表示，其节点就是基本块。编译优化在不保留图模式的情况下拆分、合并或复制图上的节点。这些优化创建了新的图模式，使得结构化算法无法详尽地枚举优化可能生成的所有可能的图模式。

为了找到反编译器缺失的图模式，作者采用以下方法：

1. 使用带优化编译（O2）的GCC编译器来编译测试文件，同时启用save-temps和dump-tree-all标志保存预处理和优化过程中生成的中间文件。
2. 然后反编译所有函数，并在反编译结果中记录goto的数量与位置。
3. 最后在中间文件中进行搜索，以确定哪个优化传递改变了函数以引起goto。这标识了优化传递的GCC源，并且这些传递带有关于所使用模式的信息的注释。

作者不断禁用优化并重复上述方法，计算优化前后反编译中的所有goto，以衡量其影响，并将所有使goto消失的被禁用优化分组为一个优化算法或一组紧耦合算法。

[!CAUTION]

这个方法对于GCC O2优化集中的大多数优化都非常有效。但有些优化选项无法简单禁用，只能通过未记录的开发人员选项完全禁用。

作者把导致goto出现的优化分为以下几类（tm也不配个图，每一类都是抽象解释，鬼知道长什么样啊）：

类型	描述
(ISD) Jump Threading (A)	When one branch’s conditions superset a future branch’s conditions, the statements contained between the two may be duplicated into the first and end with a jump to avoid extra conditional instructions. Gotos appear between duplicated statements.
(ISC) Common Subexpression Elimination (B)	The compiler finds common statements among multiple blocks and reduces them into one use of the expression and a series of jumps to that expression. Gotos occur between condensed statements.
(ISC) Switch Conversion ©	The compiler replaces simple assignments on switch statements in cases with assignments from scalars. Gotos can occur between cases that share a common expression for assignment.
(ISC) Cross Jumping (D)	Unifies equivalent code (e.g., repeated statements) across regions and replaces duplicates with a jump to the unification. A goto corresponds to the new jump.
(ISD) Software Thread Cache Reordering (E)	The compiler estimates the likelihood of executing a set of paths and clusters those frequently executed together through code duplication.
(ISD) Loop Header Optimizations (F)	The compiler moves branches that are always true or true only once to avoid executing a conditional instruction many times. The edge leaving the loop body (for the copied header) becomes a goto.
Builtin Inlining (G)	The compiler replaces special built-in functions, e.g., strcmp, with optimized inlining and propagation. Gotos can occur when inlining happens inside a short-circuit Boolean expression.
Switch Lowering (H)	A highly-coupled optimization that is non-disablable in GCC. The compiler optimizes switchstatements by breaking them into clusters and applying heuristics to avoid large jump tables. Gotos occur when the switch statement is fully transformed into a nested if statement.
Nonreturning Functions (I)	Some functions, such as exit and abort, may not (always) return, and GCC uses this knowledge to transform the CFG. When the decompiler lacks knowledge of these functions’ ability to not return, it can cause successors to be incorrectly added during CFG recovery, causing goto edges to those successors.

Irreducible Statement Duplication (ISD) converts a statement into many statements that are semantically equivalent to the original.

Irreducible Statement Condensing (ISC) converts many statements into a condensed version with introduced graphedges.

如何解决？

angr反编译流程

先lift到通用的VEX IR，再lift成更适合表示C伪代码的中间语言AIL：

angr控制流结构化流程

angr不断对AIL CFG循环以下四个步骤，直到到达固定点：

1. Region identification. angr使用基于DREAM采用的算法来识别AIL CFG中所有单入边、单出边的区域。
2. Schema matching. angr将每个子图与已知图模式匹配，当无法匹配时，则删除边并使用goto进行替代以匹配已知图模式。匹配时会将其转化为C伪代码结构并替代子图，并迭代对父子图进行匹配。
3. Region simplification. 对已匹配的AIL CFG进行优化。
4. Deoptimization. 对已匹配的AIL CFG进行反优化，不停迭代运行后面的反优化策略，直到满足限制。这个过程是goto引导的，angr假设需要反优化的优化都会导致goto，所以只对goto所代表的边周围的块进行处理。在这个过程中，搜索目标区域将会花费大部分资源。

ISD优化的反优化

ISD优化主要是指编译器会自动计算每个语句的到达条件，在某些情况下，编译器会复制语句并将其放置在到达条件相同的块内来优化执行速度等。如下图，如果满足first print的条件，就相当于满足third print的条件，为了避免多次条件判断，编译器复制了second print的语句，并新增了直接到third print的跳转。

ISD反优化步骤：

1. Finding duplicate statements. 也就是寻找重复语句。angr先遍历AIL CFG中两个语句的所有组合，寻找一组存在于同一区域且**“存储等效”** *（当两个语句的所有读写位置相同时，它们在存储上是相等的。对于一对调用语句，存储等价意味着所有参数共享相同的存储位置，并且函数地址相同。）*的候选语句对。再从候选语句对出发，使用BFS迭代展开对应子图，并使用KMP算法匹配语句。最后将每个候选图扩展到最大的图相似度为止，找到每个重复图的尾节点。

   这些节点在每个图中必须共享相同的后继节点。至少其中一个图必须具有在结构化过程中识别出的连接到共同后继的跳转边。下图的左图是一个简单的目标示例。

2. Condensing duplicates. 也就是合并重复。合并的关键在于合并前后的候选子图的到达条件一致。这个步骤简单来说就是**将所有前向节点重定向到新合并的节点，将重复的节点合并为一个节点。因为合并节点可能代表着一个复杂的、有多起始节点的子图，所以这个过程尤其要注意前向节点到达合并节点的条件分配，以及合并节点连接到后向节点的条件分配。**下图的右图表示简单合并示例，同时作者给出了ISD反优化算法的伪代码：

def deoptimize_isd(duplicate_graph_pair, graph):
    merged_graph = merge_pair_graphs(duplicate_graph_pair)
    remove_pair_nodes_from_graph(graph_pair, graph)
    graph = compose_graphs_of_many(graph, merged_graph)
    for head_node in heads_of_graphs(merged_graph):
    	point_old_predecessors_to_node(head_head)
    for leaf_node in ends_of_graphs(merged_graph):
        conditional_node = make_reaching_cond_node(leaf_node)
        graph.add_edge(leaf_node, conditional_node)
    for node in new_conditional_nodes(graph):
        original_leafs = leaf_nodes(duplicate_graph_pair)
        for leaf in original_leafs:
            graph.add_edge(
                node,
                original_edge_by_condition(leaf)
            )
    for node in new_conditional_nodes(graph):
    	simplify_and_merge_adjacent_conditionals(node)
    return graph

ISC优化的反优化

类似于ISD优化，编译器在计算每个语句的到达条件后，在某些情况下，会将完全相同的语句只保留其中部分，其余删除之后留下一个跳转。如下图，是Cross Jumping (D)优化的一个示例：

ISC反优化步骤：

1. Finding condensed statements. 也就是寻找合并的语句。**angr将任何通过goto连接到另一个语句的语句视为ISC去优化候选者。**由于ISC优化经常与其它优化相叠加，所以ISC去优化会在其它以goto为导向的反优化运行之后再运行。下图的左图是一个匹配的简单示例。
2. Reverting condensed statements. 即恢复合并的语句。**定位语句之后，目标节点作为复制的头节点，从头节点开始复制单后继节点链。**下图的右图是一个恢复示例。如果节点链中的最后一个节点不是退出节点，则此反优化可能不会删除goto。相反，angr会将图转化为一种更容易配合其它反优化的形式。这一点很重要，因为在编译过程中，ISC优化通常会叠加在其他触发goto的优化之上，类似于ISD优化。SAILR必须一个接一个地迭代地恢复这些优化。ISC反优化的伪代码如下：

def deoptimize_isc(target_node, graph):
    exit_regions = get_exit_regions(graph)
    node_chain = []
    next_node = graph.successors(target_node)[0]
    graph.remove_edge(target_node, next_node)
    while next_node is not None:
        node_chain.append(next_node)
        successors = graph.successors(next_node)
        if len(successors) > 1:
        	break
        next_node = successors[0]
    last_node = target_node
    for node in node_chain
        if is_region_head(node, exit_regions):
            new_nodes = copy_region_nodes(node)
            graph.add_edges(last_node, new_nodes)
            break
        else:
            graph.add_edge(last_node, copy(node))
            last_node = node
    return graph

杂项优化

主要讲了编译器对switch的一些特殊优化、永不返回函数、缺失的一些特殊图模式等的处理，不是重点，没什么好说的。

结果评估

参数选择

前人的工作通常将控制流结构化的有效性与最终生成代码的复杂性联系起来，并使用goto数量、麦凯布圈复杂度（McCabe Cyclomatic Code Complexity，MCC）、代码行数（LoC）作为指标进行衡量，但这是有缺陷的。

为了让最终结果能与源代码产生更强的关联性，作者使用**反编译代码与源代码之间的图编辑距离（Graph Edit Distance，GED）**作为指标来衡量效果，当GED越小，说明两者差距越小，反编译结果越接近源代码。

但计算GED是NP-hard问题，为了减少计算量，作者开发了适用于CFG比较的CFGED算法：核心思想是利用之前结构化过程中所划分出来的各个子图信息，计算对应的两个子图之间的GED（仍然过大就进行估算），最终GED是各子图的GED之和。

评估流程

直接复制粘贴：

[!IMPORTANT]

在每个实验中，我们编译软件包中的所有 .c 文件，并使用编译器输出经过预处理的中间源文件。接下来，我们编译时添加调试符号，禁用内联，并保存目标文件。然后，我们记录每个目标文件的地址与行号的映射，然后剥离调试信息。该映射将用于与 CFGED 进行评估。每个目标文件都有一个相关的中间 (.i) 文件和地址映射。

在编译后，我们使用每个反编译器对每个目标文件进行反编译，该目标文件是最终可执行文件的未链接版本，并使用 Joern 解析输出。我们利用Joern从每个反编译器收集度量指标以及控制流图（CFG），以便进行可能无法重新编译的反编译工作。我们评估Hex-Rays 8.0（IDA Pro）、Ghidra 10.1和实现SAILR、Phoenix、DREAM以及rev.ng的Combing的ANGR DECOMPILER。每种结构化算法的评估基于Structuredness（结构化程度，以goto数量为指标）和Faithfulness（正确率，以CFGED为指标）。为了确保对所有结构化算法的公平评估，我们仅报告在所有反编译器上成功反编译且未在我们的测量流程中崩溃的函数的度量指标。

评估的几个问题：

• 在反编译过程中，SAILR 结构化算法对控制流图 (CFGs) 的恢复与最先进的结构算法相比如何？
• 鉴于SAILR是基于GCC 9.5的研究结果进行指导的，那么它在较旧和较新版本的GCC上表现如何？
• 鉴于SAILR是基于GCC 9.5的研究结果进行指导的，它在不同C编译器生成的二进制文件上的表现如何？

评测结果接近IDA，但goto数比IDA少很多。

结论

缺陷：

• 还是存在goto语句。主要是因为(a) 某些函数调用未返回，但angr对此并不知情，导致CFG不正确；(b) 反编译器在多个候选边中选择了错误的边进行虚拟化，从而阻止SAILR在预期位置应用去优化技术；© SAILR对未受到编译器中的ISD优化影响的代码块进行了合并。后两者可以通过SAILR在选择虚拟化边和去优化代码部分时执行迭代搜索来解决。
• 反编译结果达到最佳时仍可能产生高CFGED。可能需要修改CFGED算法，另外不同的结构选择差异也可能导致不同，可能需要使用统计技术，例如机器学习来进行加强。
• 不同的架构、平台、和编译器。
• 复合ISC和ISD优化并不总是导致goto语句。在少数情况下，复合ISC和ISD优化可能会生成与已知图形模式相匹配的子图。因此，不会产生不可结构化的代码区域。一个与图形模式匹配的反编译器将生成一个无goto的反编译结果，然而它在结构上并不与源代码匹配。从根本上讲，这种情况是由于合法C源代码与二进制代码之间的多对一映射所造成的。使用机器学习方法来预测二进制控制流图及其上下文中最合适的结构化结果是一种自然的解决方案。
• 使用Hex-Rays研究Coreutils二进制文件中的goto。由于Hex-Rays有着更多的图形模式来匹配，所以会消除更多的goto导致无法识别所有goto源。使用一个简单的图形模式匹配反编译器可以帮助提高所有goto源的准确性。

rev.ng作者的回应

https://pad.rev.ng/s/T3RdsvKNx#

• 反编译器的输出应以可读性为主，不必与原始代码百分百接近。所以只要能提高可读性，适当的goto和重复都不是问题。
• 针对编译器优化进行反优化是不实际的，一方面需要根据不同的编译器、架构、平台等进行特别地改动，另一方面编译器优化会进行多轮迭代并与其它优化相互作用，不能简单地“反转”。
• 使用平均GED作为指标并不好，因为可能在小函数上表现出色，但在大函数上表现很差。同时，相同GED的函数可能反编译结果的可读性会相差甚远。
• 给出了一个可能更有前途的指标：https://www.sonarsource.com/docs/CognitiveComplexity.pdf

参考

• [Phoenix] Native x86 decompilation using semantics-preserving structural analysis and iterative control-flow structuring.
• [rev.ng] A comb for decompiled C code.
• [DREAM] No more gotos: Decompilation using patternindependent control-flow structuring and semantic-preserving transformations.