反编译器 - 如何构建循环结构

10

我正在编写一个简单脚本语言的反编译器。以下是我的工作内容:

基本块

按照此处描述,创建了基本块的集合:

http://www.backerstreet.com/decompiler/basic_blocks.php

控制流图、支配树和循环集

然后,我可以从中创建控制流图。

http://www.backerstreet.com/decompiler/control_flow_graph.php

从CFG中,我创建了支配树,这进而允许我按照此处描述找到CFG中的循环集:

http://www.backerstreet.com/decompiler/loop_analysis.php

下面的图片包含了我迄今为止的所有数据:

Control flow diagram

循环结构

我的下一步应该是:

http://www.backerstreet.com/decompiler/creating_statements.php

这就是我卡住的地方了。在我的给定数据中,如何应用循环结构算法?我不明白为什么它会尝试将所有内容都结构化为do while循环-在我的示例中,这意味着块3中的"temp5_14 = temp5_14 + 16"至少会被执行一次,这完全不是原始代码所做的。

这该怎么做,下一步将其从do-while转换为while循环应该如何实现?对于以块6结束的Loop 3,它看起来应该是一个while(true) - 但是当它的头部块是if语句时,这将如何运作呢?

简而言之 - 请有人用示例解释“结构化循环”算法的工作原理。

2个回答

8

结构化是反编译开发中最难的部分(至少对于高级语言而言)。这是一个相当简单的算法,所以它是一个很好的起点,但如果你正在开发一个真正的反编译器,你可能想使用更好的算法或者自己编写算法。

除此之外,关于如何使用do-while循环而不是while循环的实际问题,答案已经在你链接到的页面上回答过了。

每个循环都可以用“do-while”语句来描述。

“while”循环(前测试循环)是“do-while”循环的一种特殊情况,其中底部条件始终为真,并且循环的第一条语句是一个“if”,用于跳出循环。

假设你有这样的东西:

beforeloop
while(foo) {
stmt1
stmt2
}
afterloop

它将被编译成类似以下的内容。
beforeloop

LOOPBEGIN:
if !foo goto LOOPEND
stmt1
stmt2
goto LOOPBEGIN

LOOPEND:
afterloop

反编译算法将其转换为:
beforeloop
do {
if (!foo) {break}
stmt1
stmt2
} while (true)
afterloop

我希望这能让问题得到解决。如果不能,可以随意提出其他问题。
编辑:示例2,展示如何折叠具有相同入口点的多个循环。
for(;;) { while(foo) {} while(bar){} }

首先,for(;;) 相当于 while(true),因此我将使用以下(伪)代码

while(true) { while(foo) {stmt1} while(bar){stmt2} }

让外层循环称为循环A,内层循环称为循环B和C。这将编译成类似于以下伪汇编代码的东西。

LOOP_A_BEGIN:
LOOP_B_BEGIN:
if !foo goto LOOP_B_END
stmt1
goto LOOP_B_BEGIN
LOOP_B_END:
LOOP_C_BEGIN:
if !bar goto LOOP_C_END
stmt2
goto LOOP_C_BEGIN
LOOP_C_END:
goto LOOP_A_BEGIN

当然,标签不会占用任何空间。因此,如果折叠相同的标签,则变为:
POINT1:
if !foo goto POINT2
stmt1
goto POINT1
POINT2:
if !bar goto POINT3
stmt2
goto POINT2
POINT3
goto POINT1

现在,有两个带有反向边的点 - 点1和点2。我们可以为每个节点创建一个循环,并使用标记的中断以增强清晰度。转换并不是非常直接,因为你需要稍微修改if语句,但这仍然相当容易。

LOOP1: while(true) {
    IF1: if (!foo) {
        break IF1;
    }
    else {
        stmt1;
        continue LOOP1;
    }

    LOOP2: while(true) {
        if (!bar) {
            break LOOP2;
        }
        else {
            stmt2;
            continue LOOP2;
        }
    }

    continue LOOP1;
}

现在,同样的代码已经简化,去掉了不必要的标签。
while(true) {
    if (!foo) {
    }
    else {
        stmt1;
        continue;
    }

    while(true) {
        if (!bar) {
            break;
        }
        else {
            stmt2;
        }
    }
}

现在,if语句已经简化。
while(true) {
    if (foo) {
        stmt1;
        continue;
    }

    while(true) {
        if (!bar) {
            break;
        }
        stmt2;
    }
}

最后,您可以将 while(true) if(!x) 转换应用于内部循环。由于是合并循环的结果,外部循环无法像这样进行转换,因为它不是简单的 while(cond) 循环。

while(true) {
    if (foo) {
        stmt1;
        continue;
    }

    while(bar) {
        stmt2;
    }
}

希望这能展示如何通过将多个循环合并为一个循环来处理具有相同入口点的情况,但可能需要重新排列一些if语句。

@paulm 他们的方法对我来说没有太多意义。但是一种做法是A)将所有内容转换为while(true),然后B)查找模式while(true) {if(foo) {break} ...),并将其转换为while(foo) {...}。 - Antimony
现在我更加困惑了 :) 我的CFG逻辑不是if(foo) break;,它必须转换为if(!foo) break吗?还有,对于B3到B2和B6到B2,这该如何工作,因为两个循环头都是同一个块,但一个实际上是嵌套循环? - paulm
翻译:哎呀,我搞砸了。你纠正一下应该是if(!foo) break。你不应该有相同起始块的嵌套循环,因为如果它们都有条件,那么它们都会以不同的if语句开始。如果它们没有条件,那么你可以通过生成一个循环来简化它。 - Antimony
@paulm for(;;) 相当于 while(true)。因此,您有一个嵌套在没有条件的循环中的带条件的循环。但由于外部循环没有条件,它可以简化并与第一个内部 while 循环合并。如果您仍然感到困惑,我可以发布该示例的演示。 - Antimony
谢谢,这非常有帮助! - paulm
显示剩余4条评论

7

有一篇名为 No More Gotos的论文,提出了一种无需模式依赖的控制流结构算法。要理解和实现它需要付出很大的努力,但我正在将其用于我的毕业项目中,看起来它有效。

我的实现可以在GitHub上找到,链接为 zneak/fcd。该项目使用LLVM IR作为中间表示。


编辑 在一个非常高的层面上,算法是这样工作的:

支配

为了确保这些概念被理解:如果从图的入口到Z的任何路径都必须通过A,则节点A支配节点Z。同样地,如果从A到图的结尾的任何路径都必须通过Z,则节点Z后支配节点A。

区域

该算法结构化区域。区域是图的一部分,具有单个入口边和单个出口边。我个人将此定义扩展到基本块(区域具有单个入口块和单个出口块),并使其排除了出口块。

我使用的区域定义如下:

  • 入口节点支配出口节点;
  • 出口节点后支配入口节点;
  • 一旦到达出口,任何带您返回区域的路径都要经过入口节点。(这最后一点非常重要,可以解决与循环相关的问题。)

该定义意味着入口节点支配通过出口节点的每个节点,而出口节点后支配从入口开始的每个节点。

规范化循环

循环是一个带有“回边”的区域(如果您按深度优先遍历图形,则具有指向已访问节点的边)。

确保将循环表示为具有单个入口和单个后继的单入口单出口区域,其中后退边也只有一个入口节点。当不满足此条件时,您可以引入一个新的入口块,并使所有边都指向它,然后使用Φ节点从那里转发执行(换句话说,引入一个变量,在每个传入块的末尾设置该变量,然后从新块中执行if(var == 0){第一个入口} else if(var == 1){第二个入口})。

在我的实现中,这是在StructurizeCFG通道中发生的,截至撰写本文时,它在主分支中。然而,它产生了很差的结果,因为它比它需要做的工作更加努力。我只需要它来构造循环,但它也会构造if-else结构,虽然它不会破坏算法,但它引入了太多的Φ节点,使输出变得不美观。截至本文撰写时,还有一个名为seseloop的分支,其中包含一个自定义通道,以确保循环是单入口单出口的。如果没有必要,此通道不会触及if-else结构。

将函数进行结构化

以后序方式遍历基本块图。识别从该块开始的区域。您可以使用后继支配树加速这个过程,因为一个区域必须以块的后继支配者结束(因此对于每个块,只需检查块的后继支配者)。

如果入口块有指向它的反向边,则将其构造为一个循环。如果没有,则将其构造为一个区域。当一个区域被结构化后,将其作为一个折叠的单个节点放回到您的图中,该节点可以包含在另一个更大的结构化区域中。
这发生在ast/ast_backend.cpp中。
结构化区域
对区域进行深度优先遍历(跳过循环)以识别导致执行任何块的条件。例如:

Graph describing an if-then-else sequence. Node A is the entry node; node B is the true node; node C is the false node, and node D is the exit node.

节点A没有条件。如果节点A的结尾条件为真,则到达节点B。如果为假,则到达节点C。如果条件为真或假,则到达节点D。

(A);
if (a_cond) (B);
if (!a_cond) (C);
if (a_cond || !a_cond) (D);

你需要简化这些条件语句,但不幸的是这是一个NP完全问题。通常情况下,通过折叠“a_cond ||!a_cond”并按顺序比较条件项,应该很容易回到类似于“A; if(a_cond) B; else C; D;”的形式。
结构化循环:
基本上你做的就像结构化一个区域一样,不必在意它是一个循环,但之后你需要在可以退出循环的块末尾添加break语句(如果相关则带有条件),并将该区域包装在while true块中。然后,作者们已经确定了6种可以用更易读的模式替换的模式(例如,以“if(cond) break”开头的“while true”可以转换为“while!cond”)。
大致就是这样。

你会以前端不可知的方式编写吗?也就是说,任何类型的字节码都可以插入其中? - paulm
我不这么认为。老实说,我手头已经有足够多的问题需要解决了!我正在使用LLVM IR。 - zneak
1
@paulm,源代码已经发布。 - zneak
@zneak,论文链接已失效。 - Earthcomputer
1
一份新的文件链接:https://www.ndss-symposium.org/wp-content/uploads/2017/09/11_4_2.pdf - Antonio Noack

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接