反编译器进行控制流重建时，如何最小化goto语句的数量，条件分支的合并非常关键。有两种方法进行条件分支的合并：第一种，根据规则进行模式匹配合并，该方法最大的问题是不可能覆盖所有的规则；第二种，Path-Sensitive/Path-Find，不进行规则匹配合并，该方法有些类似于数据流分析自顶向下（Top-Down）向前问题（Forward）的到达-定值(Reaching Definitions)分析，论文"No More Gotos: Decompilation Using Pattern-Independent Control-Flow Structuring and Semantics-Preserving Transformations"中所使用的条件归约合并方法就是这种方法，论文有些晦涩，并不容易理解。本文讨论第一种方法。(注意每个规则的流程图并没有完全定义了此规则，流程图中绿边代表True Edge，红边代表False Edge，黄边代表Virtual Edge或Jump Edge。)

跳转语句分成间接跳转语句和非间接跳转语句，这里只考虑非间接跳转语句，大概有以下两种情况：

Type 1

条件跳转语句的下一条语句Fall Through块是True基本块
短跳转语句：
bneq SeqF
SeqT:

长跳转语句1：
beq SeqT
b SeqF
SeqT：

长跳转语句2：
bneq SeqInst
b SeqT
SeqInst:
b SeqF
SeqT:

Type 2
条件跳转语句的下一条语句Fall Through块是False基本块
短跳转语句：
beq SeqT
SeqF:

长跳转语句1：
bneq SeqF
b SeqT
SeqF：

长跳转语句2：
beq SeqInst
b SeqF
SeqInst:
b SeqT
SeqF:

Type 1

最基础的规则，几乎所有的反编译器都有对此规则进行归约合并：
规则C0 || C2和规则C0 && C2

规则C0 || !C2和规则C0 && !C2

以规则C0 || C2进行说明:

假设C0 || C2规则归约合并表示如下：

则图中所示的规则一般的可能的表示

graphviz脚本dot表示

Type 2

少量反编译器有对此规则进行归约合并，该规则是基础规则Type 1的改版：
规则C0 ? C1 : C2 和规则C0 ? !C1 : C2

Type 3

几乎没有反编译器有对此规则进行归约合并，通常情况下编译器不会生成这种规则的代码，只有代码混淆时有可能生成。该规则是基础规则Type 1或基础规则Type 2的改版：

根据流图可知，如果SeqInst块没有改变比较语句C0,则合并归约的可能表示：

没有goto语句。

Type 4

Type 1、Type 2、Type 3都是Type 4的特例改版
规则(C0 ? C1 : C2) || C3和规则(C0 ? C1 : C2) && C3

规则(C0 ? C1 : !C2) || C3和规则(C0 ? !C1 : C2) && C3

规则(C0 ? C1 : !C2) && C3和规则(C0 ? !C1 : C2) || C3

规则C0 ? ( C1 | | C3 ) : ( C2 && C3 )

规则(C0 ? v1 : v2) == val

当某区域有两个以上的基础规则时，根据合并规则进行归约合并大概流程是在控制树上根据基础规则归约符合规则的区域，转化成抽象的单一节点，迭代此过程。(注意先不考虑基础规则Type 3，流程图并没有没有经过真值表验证，有可能是错误的。)

Type 1

规则(C0 || C1) || C3和规则(C0 && C1) && C3

规则(C0 || C1) && C3和规则(C0 && C1) || C3

Type 2

规则(C0 || C1) || (C3 || C4)和规则(C0 && C1) && (C3 && C4)

规则(C0 || C1) && (C3 || C4)和规则(C0 && C1) || (C3 && C4)

Type 3
规则(C0 ? C1 : C2) || (C3 || C4)和规则(C0 ? C1 : C2) && (C3 && C4)

规则(C0 ? C1 : C2) || (C3 && C4)和规则(C0 ? C1 : C2) && (C3 || C4)

规则C0 ? (C1 || (C3 || C4)) : (C2 && (C3 || C4))

Type 4
规则(C0 ? C1 : C2) || (C3 ? C4 : C5)和规则(C0 ? C1 : C2) && (C3 ? C4 : C5)

Type 5
规则(C0 || C1) ? C3 : C4和规则(C0 && C1) ? C3 : C4

规则C0 ? (C1 || C2) : C4和规则C0 ? (C1 && C2) : C4

规则C0 ? C1 : (C3 || C4)和规则C0 ? C1 : (C3 && C4)

Type 6
规则(C0 || C1) ? (C2 && C3）: C4和规则(C0 || C1) ? C4 : (C2 && C3)

规则(C0 && C1) ? C2 : (C3 || C4) 和规则(C0 && C1) ? (C3 || C4) : C2

Type 7
规则((C0 || C1) ? C2 : C3）|| C4和规则((C0 || C1) ? C2 : C3）&& C4

规则((C0 && C1) ? C2 : C3）|| C4和规则((C0 && C1) ? C2 : C3）&& C4

规则(C0 || C1) ? (C2 || C4) : (C3 && C4)

规则(C0 && C1) ? (C2 || C4) : (C3 && C4)

Type 8
规则(C0 ? C1 : C2) ? C3 : C4

规则C0 ? (C1 ? C2 : C3) : C4

规则C0 ? C1 : (C2 ? C3 : C4)

Type 9
规则(C0 ? C1 : C2) ? (C3 && C4) : C6

规则C0 ? (C1 ? C2 : C3) : (C5 && C6)

规则C0 ? (C1 && C2) : (C4 ? C5: C6)

Type 10
规则(C0 || C1) ? (C2 && C3）: (C4 ? C5: C6)

规则(C0 && C1) ? (C2 || C3）: (C4 ? C5: C6)

Type 11
规则(C0 ? C1 : C2) ? (C3 ? C4 : C5) :C6

[培训]内核驱动高级班，冲击BAT一流互联网大厂工作，每周日13:00-18:00直播授课