[原创]反编译原理之If-Else条件跳转合并
条件分支合并
反编译器进行控制流重建时，如何最小化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规则归约合并表示如下：if( C0 || C2 ) { SeqT; } else { SeqF; }则图中所示的规则一般的可能的表示
L1: if ( C0 ) goto LT; else goto L2; L2: if ( C2 ) goto LT; else goto LF; LT: SeqT; goto Exit; LF: SeqF; Exit:graphviz脚本dot表示
// C0 || C2 digraph G { Entry[shape=box,style=filled,color=white,label="Entry"]; L1[label="C0"]; L2[label="C2"]; SeqT[label="SeqT"]; SeqF[label="SeqF"]; Exit[shape=box,style=filled,color=white,label="Exit"]; subgraph cluster_1 { style=filled; label="C0 || C2"; Entry:s -> L1:n[style=bold,color=yellow]; L1:w -> SeqT:n[style=bold,color=green,taillabel="T"]; L1:e -> L2:n[style=dashed,color=red,taillabel="F"]; L2:w -> SeqT:n[style=bold,color=green,taillabel="T"]; L2:e -> SeqF:n[style=dashed,color=red,taillabel="F"]; SeqT:s -> Exit:n[style=bold,color=yellow]; SeqF:s -> Exit:n[style=bold,color=yellow]; } }Type 2
少量反编译器有对此规则进行归约合并，该规则是基础规则Type 1的改版：
规则C0 ? C1 : C2 和规则C0 ? !C1 : C2
Type 3
几乎没有反编译器有对此规则进行归约合并，通常情况下编译器不会生成这种规则的代码，只有代码混淆时有可能生成。该规则是基础规则Type 1或基础规则Type 2的改版：
根据流图可知，如果SeqInst块没有改变比较语句C0,则合并归约的可能表示：
if( C0 ){ SeqInst; } if( C0 || C2 ){ SeqT; } else{ SeqF; }没有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
Type 12
规则(C0 ? C1 : C2) ? (C3 ? C4 : C5) :(C6 || C7)
Type 13
规则(C0 ? C1 : C2) ? (C3 ? C4 : C5) :(C6 ? C7 :C8)
测试
测试规则(C1 && C2) ? ((C3 ? C4 : C5) || (C8 || C9)) : ((C6 || C7) && (C8 || C9))
测试规则c代码：
int test ( int C1, int C2, int C3, int C4, int C5,
int C6, int C7, int C8, int C9,int C16 )
{
Entry:
int res = 0;
L1:
if ( C1 == 1 )
goto L2;
else
goto L6;
L2:
if ( C2 == 2 )
goto L3;
else
goto L6;
L3:
if ( C3 == 3 )
goto L4;
else
goto L5;
L4:
if ( C4 == 4 )
goto SeqT;
else
goto L8;
L5:
if ( C5 == 5 )
goto SeqT;
else
goto L8;
L6:
if ( C6 == 6 )
goto L8;
else
goto L7;
L7:
if ( C7 == 7 )
goto L8;
else
goto SeqF;
L8:
if ( C8 == 8 )
goto SeqT;
else
goto L9;
L9:
if ( C9 == 9 )
goto SeqT;
else
goto SeqF;
SeqT:
res = C16 + 1;
goto Exit;
SeqF:
res = C16 - 1;
Exit:
return res;
}
流程图:
graphviz脚本dot表示:
digraph G{
Entry[shape=box,style=filled,color=white,label="res = 0"];
L1[label="C1 == 1"];
L2[label="C2 == 2"];
L3[label="C3 == 3"];
L4[label="C4 == 4"];
L5[label="C5 == 5"];
L6[label="C6 == 6"];
L7[label="C7 == 7"];
L8[label="C8 == 8"];
L9[label="C9 == 9"];
SeqT[label="res = C16 + 1"]
SeqF[label="res = C16 - 1"];
Exit[shape=box,style=filled,color=white,label="return res"];
subgraph cluster_1{
style=filled;
Entry:s -> L1:n[style=bold,color=yellow];
L1:w -> L2:n[style=bold,color=green,taillabel="T"];
L1:e -> L6:n[style=dashed,color=red,taillabel="F"];
L2:w -> L3:n[style=bold,color=green,taillabel="T"];
L2:e -> L6:n[style=dashed,color=red,taillabel="F"];
L3:w -> L4:n[style=bold,color=green,taillabel="T"];
L3:e -> L5:n[style=dashed,color=red,taillabel="F"];
L4:w -> SeqT:n[style=bold,color=green,taillabel="T"];
L4:e -> L8:n[style=dashed,color=red,taillabel="F"];
L5:w -> SeqT:n[style=bold,color=green,taillabel="T"];
L5:e -> L8:n[style=dashed,color=red,taillabel="F"];
L6:w -> L8:n[style=bold,color=green,taillabel="T"];
L6:e -> L7:n[style=dashed,color=red,taillabel="F"];
L7:w -> L8:n[style=bold,color=green,taillabel="T"];
L7:e -> SeqF:n[style=dashed,color=red,taillabel="F"];
L8:w -> SeqT:n[style=bold,color=green,taillabel="T"];
L8:e -> L9:n[style=dashed,color=red,taillabel="F"];
L9:w -> SeqT:n[style=bold,color=green,taillabel="T"];
L9:e -> SeqF:n[style=dashed,color=red,taillabel="F"];
SeqT:s -> Exit:n[style=bold,color=yellow];
SeqF:s -> Exit:n[style=bold,color=yellow];
}
}
可以生成未优化编译的x86汇编代码，然后用IDA 7.0/7.1/7.2反编译，查看F5后反编译代码中goto语句的数量
根据流图可知，归约合并后的反编译可能表示：
int test ( int C1, int C2, int C3, int C4, int C5,
int C6, int C7, int C8, int C9,int C16 )
{
int res = 0;
bool C10 = ( C1 ==1 ) && ( C2 == 2 );
bool C11 = ( C3 ==3 ) ? ( C4 == 4 ) : ( C5 == 5 );
bool C12 = ( C6 == 6 ) || ( C7 == 7 );
bool C13 = ( C8 == 8 ) || ( C9 == 9 );
bool C14 = C10 ? ( C11 || C13 ) : ( C12 && C13 );
if( C14 ) {
res = C16 + 1;
}
else {
res = C16 - 1;
}
return res;
}
总结
虽然可以根据规则进行模式匹配归约合并条件跳转语句，但该方法由于不可能覆盖所有的规则，因此归约后的流图的goto语句数量不可能最小化，还有，如果条件跳转语句在循环体内，情况会变得更加复杂，因此Path-Sensitive Control Flow Analysis/Data Flow Analysis应该是目前条件分支合并的最新方法，论文"No More Gotos: Decompilation Using Pattern-Independent Control-Flow Structuring and Semantics-Preserving Transformations"就是采用了类似的方法。
