C++逆向之流程控制语句的识别

流程控制语句的识别是进行逆向分析和还原高级代码的基础。通过本篇的内容可以更好地理解高级语言中流程控制的内部机制,对于开发和调试大有裨益。

if语句

if语句是分支结构的重要组成部分。if语句的功能是先对运算条件进行比较,然后根据比较结果选择对应的语句块来执行。if语句只能判断两种情况:“0”为假值,“非0”为真值。如果为真值,则进入语句块内执行语句;如果为假值,则跳过if语句块,继续运行程序的其他语句。要注意的是,if语句转换的条件跳转指令于if语句的判断结果是相反的。我们以下代码为例:

1
2
3
4
5
6
7
8
9
10
#include<iostream>
using namespace std;
int main(int argc,char * argv[])
{
if(argc==0)
{
printf("%d\n",argc);
}
return 0;
}

使用cmp指令,将ebp+8地址处的4字节数据与0相减
结果不影响argc,但影响标志位CF、ZF、OF、AF和PF

1
00401637    837D 08 00      cmp dword ptr ss:[ebp+0x8],0x0

JNZ检查ZF标记位的值,如果值等于0,则跳转,表示此时argc不等于0
于是跳转到地址00401650处
这个地址为if语句块的结束地址,随后跳转出if语句

1
2
3
4
5
6
0040163B   /75 13           jnz short 1.00401650
0040163D |8B45 08 mov eax,dword ptr ss:[ebp+0x8]
00401640 |894424 04 mov dword ptr ss:[esp+0x4],eax
00401644 |C70424 45904000 mov dword ptr ss:[esp],1.00409045 ; ASCII "%d\n"
0040164B |E8 B0FFFFFF call 1.00401600
00401650 \B8 00000000 mov eax,0x0

C++源码中if的比较条件为“argc==0”,如果成立,即为真,则进入if语句块内执行语句。但是,转换后的汇编代码使用的条件跳转指令JNE判断结果为“不等于0则跳转”,这是为什么呢?因为按照if语句的规定,满足if判定的表达式才能执行if的语句块,而汇编语言的条件跳转却是满足某条件则跳转,绕过某些代码,这一点与C语言是相反的。
既然这样,那为什么C语言编译器不将else语句块提到前面去并把if语句块放到后面去呢?这样汇编语言和C语言中的判定条件不就一致了吗?
因为C语言是根据代码行的位置来决定编译后的二进制代码的地址高低的,也就是说,低行数对应低地址,高行数对应高地址,所有有时会使用标号相减得到代码段的长度。鉴于此,C语言的编译器不能随意改变代码在内存中的顺序。
根据这一特性,如果将if语句中的比较条件修改为“if(argc>0)”,则其对应的汇编语言所使用的条件跳转指令会是“小于等于0”。

1
2
3
4
5
6
7
8
9
10
#include<iostream>
using namespace std;
int main(int argc,char * argv[])
{
if(argc>0)
{
printf("%d\n",argc);
}
return 0;
}

查看反汇编代码,果然是jle(小于等于则跳转)
通过以上代码分析,可总结出if语句的转换规则:在转换成汇编代码后,由于当if比较结果为假时,需要跳过if语句块内的代码,因此使用了相反的条件跳转指令。

if…else…语句

if语句是一个单分支结构,if…else…组合后是一个双分支结构。两者完成的功能有所不同。从语法上看,if…else…只比if语句多出了个else。else有两个功能,如果if判断成功,则跳过else分支语句块;如果if判断失败,则进入else分支语句块中。有了else语句的存在,程序在进行流程选择时,必会经过两个分支中的一个。通过以下代码我们来分析else如何实现这两个功能。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include<iostream>
using namespace std;
int main(int argc,char * argv[])
{
if(argc==0)
{
printf("argc==0");
}
else
{
printf("argc!=0");
}
return 0;
}
1
2
3
4
5
6
7
00401637    837D 08 00      cmp dword ptr ss:[ebp+0x8],0x0
0040163B 75 0E jnz short 1.0040164B ; 跳转成立,跳转到地址0x40164B处,即else语句块的首地址
0040163D C70424 45904000 mov dword ptr ss:[esp],1.00409045 ; ASCII "argc==0"
00401644 E8 B7FFFFFF call 1.00401600 ; 调用printf函数
00401649 EB 0C jmp short 1.00401657 ; 直接跳转到地址0x00401657,当if语句执行后跳转过else语句块
0040164B C70424 4D904000 mov dword ptr ss:[esp],1.0040904D ; ASCII "argc!=0"
00401652 E8 A9FFFFFF call 1.00401600 ; 调用printf函数

在以上代码中,if语转换的条件跳转和单分支if语句相同,都是取相反的条件跳转指令。而在else处(地址00401649)多了一句jmp指令,这是为了在if语句比较后,如果结果为真,则程序流程执行if语句语句块并且跳过else语句块,反之执行else语句块。else处的jmp指令跳转的目标地址为else语句块结尾处的地址,这样的设计可以跳过else语句块,实现两个分支语句二选一的功能。

用if构成的多分支流程

前面介绍了由if与if…else…组成的分支结构。本节介绍它们的组合形式———多分支结构。多分支结构类似于if…else…的组合方式,在if…else…的else之后再添加一个else if进行二次比较,这样就可以进行多次比较,再次选择程序流程,形成了多分支结构的流程。它的C++语法格式为:if…else if…else if…,可重复后缀为else if。当最后为else时,便到了多分支结构的末尾处,不可再分支。通过以下代码示例查看多分支结构的组成。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include<iostream>
using namespace std;
int main(int argc,char * argv[])
{
if(argc>0)
{
printf("argc>0");
}
else if(argc==0)
{
printf("argc==0");
}
else
{
printf("argc<0");
}
return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
00401629    55              push ebp
0040162A 89E5 mov ebp,esp
0040162C 83E4 F0 and esp,-0x10
0040162F 83EC 10 sub esp,0x10
00401632 E8 19020000 call 1.00401850
//if比较转换
00401637 837D 08 00 cmp dword ptr ss:[ebp+0x8],0x0
//使用jle条件跳转指令,如果判断后的结果小于等于0,则跳转到地址0x0040164B
0040163B 7E 0E jle short 1.0040164B
0040163D C70424 45904000 mov dword ptr ss:[esp],1.00409045 ; ASCII "argc>0"
00401644 E8 B7FFFFFF call 1.00401600
//对应else,当上一条if语句被执行,执行jmp指令,跳转到地址0x0040166B处
//该为多分支结构结束地址,即最后一个else或else if的结束地址。
00401649 EB 20 jmp short 1.0040166B
//if转换比较,使用条件跳转指令jnz,不等于0则跳转到地址0x0040165F
0040164B 837D 08 00 cmp dword ptr ss:[ebp+0x8],0x0
0040164F 75 0E jnz short 1.0040165F
00401651 C70424 4C904000 mov dword ptr ss:[esp],1.0040904C ; ASCII "argc==0"
00401658 E8 A3FFFFFF call 1.00401600
//跳转到多分支结构的结束地址
0040165D EB 0C jmp short 1.0040166B
//此处无判定。当以上各个条件均不成立时,以下代码则无条件执行
//可将此处定义为最后的else块
0040165F C70424 54904000 mov dword ptr ss:[esp],1.00409054 ; ASCII "argc<0"
00401666 E8 95FFFFFF call 1.00401600
0040166B B8 00000000 mov eax,0x0
00401670 C9 leave
00401671 C3 retn

每条if语句由cmp和jxx组成,而else由一个jmp跳转到分支结构的最后一个语句块结束地址组成。由此可见,虽然它们组合在了一起,但是每个if和else又都是独立的,if仍然是cmp/test加jxx组成,我们仍然可以,利用jxx和jmp识别出if和else if语句块的边界,jxx指出了下一个else if语句的起点,而jmp指出了整个分支结构的末尾地址以及当前if或者else if语句块的末尾。最后的else块的边界也很容易识别,如果发现多分支块内的某一段代码在执行前没有判定,即可定义为else块。

switch的真相

switch是比较常用的多分支结构,使用起来也非常方便,并且效率上也高于if…else if多分支结构。同样是多分支结构,switch是如何进行比较并选择分支的?它和if…else if的处理过程一样吗?下面我们通过简单的switch多分支结构结构慢慢揭开它的神秘面纱。编写case语句不超过3条的switch多分支结构。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include<iostream>
using namespace std;
int main(int argc,char * argv[])
{
int nIndex=1;
scanf("%d",&nIndex);
switch(nIndex)
{
case 1:printf("nIndex=1"); break;
case 3:printf("nIndex==3"); break;
case 100:printf("nIndex==100");break;
}
return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
0040167C    8B4424 1C       mov eax,dword ptr ss:[esp+0x1C]          ; 把nIndex的数据赋值给eax
00401680 83F8 03 cmp eax,0x3 ; 将eax与3比较
00401683 74 18 je short 1.0040169D ; eax与3相等时,跳转到地址0x0040169D处
00401685 83F8 64 cmp eax,0x64 ; 将eax与64h比较
00401688 74 21 je short 1.004016AB ; eax与64h相等时,跳转到地址0x004016AB处
0040168A 83F8 01 cmp eax,0x1 ; 将eax与1比较
0040168D 75 29 jnz short 1.004016B8 ; 这里和if语句很相似,如果不相等则跳转到switch语句块的结尾
0040168F C70424 48004100 mov dword ptr ss:[esp],1.00410048 ; ASCII "nIndex=1"
00401696 E8 8EFFFFFF call 1.00401629
0040169B EB 1B jmp short 1.004016B8
0040169D C70424 51004100 mov dword ptr ss:[esp],1.00410051 ; ASCII "nIndex==3"
004016A4 E8 80FFFFFF call 1.00401629
004016A9 EB 0D jmp short 1.004016B8
004016AB C70424 5B004100 mov dword ptr ss:[esp],1.0041005B ; ASCII "nIndex==100"
004016B2 E8 72FFFFFF call 1.00401629

switch语句使用了3次条件跳转指令,分别与1、3、100进行了比较。如果比较条件成立,则跳转到对应的语句块中。这种结构与if…else if多分支结构非常相似,但仔细分析后发现,它们之间有很大的区别。
if…else if结构会在条件跳转后紧跟语句块;而switch结构则会将所有的条件跳转都放置在一起,并没有发现case语句块的踪影。通过条件跳转指令,跳转到相应case语句块中,因此每个case的执行是由switch比较结果引导“跳”过来的。所有case语句块都是连在一起的,这样是为了实现C语法的要求,在case语句块没有break语句时,可以顺序执行后续case语句块。
在switch分指数小于4的情况下,编译器采用模拟if…else if的方法。这样并没有发挥出switch的优势,在效率上也没有if…else if强。当分支数大于4,并且case的判定值存在明显的线性关系时,switch的优化特性便可以凸显出来。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include<iostream>
using namespace std;
int main(int argc,char * argv[])
{
int nIndex=1;
scanf("%d",&nIndex);
switch(nIndex)
{
case 1: printf("nIndex=1"); break;
case 2: printf("nIndex=2"); break;
case 3: printf("nIndex=3"); break;
case 5: printf("nIndex=5"); break;
case 6: printf("nIndex=6"); break;
case 7: printf("nIndex=7"); break;
}
return 0;
}

在此段代码中,case语句的标号为一个数值为1~7的有序序列。按照if…else if转换规则,会将1~7的数值依次比较一次,从而得到分支选择结果。这么做需要比较的次数过多,如何降低比较次数,提升效率呢?由于是有序线性的数值,可将每个case语句块的地址预先保存在数组中,考察switch语句的参数,并一次查询case语句块地址,从而得到对应case语句块的首地址。

对应的跳转表

对比可知,每个case语句块的首地址都在表中,但有两个地址却不上case语句块的首地址。0x00410080和0x00410090。这个地址是每句break跳转的一个地址值,显然这是switch结束的地址。这个地址值出现在表的第0项和第4项,而实际中却没有case 0和case 4这个语句块。为了达到线性有序,对于没有case对应的数值,编译器以switch的结束地址或者default语句块的首地址填充。
每一个break语句对应一个jmp指令,跳转到的地址都是switch的结束地址处,起到了跳出switch的作用。如果没有break语句,则会顺序执行代码,执行到下一句case语句块中,这便是case语句中没有break可以顺序执行的原因。
以上代码没有使用default语句块。当所有条件都不成立后,才会执行到default语句块,它和switch的末尾实质上是等价的。switch中出现default后,就会填写default语句块的首地址作为switch的结束地址。
如果每两个case值之间的差值小于等于6,并且case语句数大于等于4,编译器就会形成这种线性结构。在编写代码中无需有序排列case值,编译器会在编译过程中对case线性地址表进行排序,如case的顺序为3、2、1、4、5,在case线性地址表中,会将它们的语句块的首地址进行排序,将case 1语句块的首地址放在case线性地址表的第0项上,case 2语句块首地址放在表中第1项,以此类推,将首地址变为一个有序的表格进行存放。
这种switch的识别有两个关键点,取数值内容进行比较;比较跳转失败后,出现4字节的相对比例因子寻址方式。有了这两个特性,就可以从代码中正确分析出switch结构。

难以构成跳转表的switch

当switch为一个有序线性组合时,会对其case语句块制作地址表,以减少比较跳转次数。但并非所有switch结构都是有序线性的,当两个case值的间隔较大时,仍然使用switch的结尾地址或者default语句块的首地址来代替地址表中缺少的case地址,这样就会造成极大的空间浪费。
对于非线性的switch结构,可以采用制作索引表的方法来进行优化。索引表优化,需要两张表:一张case语句块首地址表,另一张为case语句块索引表。
地址表中的每一项保存一个case语句块的首地址,有几个case语句块就有几项。default语句块也在其中,如果没有则保存一个switch结束地址。这个结束地址在地址表中只会保存一份,不会像有序线性地址表那样,重复保存switch的结束地址。
索引表中保存地址表的编号,它的大小等于最大case值和最小case值的差。当差值大于255时,这种优化方案也会浪费空间,可通过树方式优化,这里就只讨论差值小于或等于255的情况。表中的每一项为一个字节大小,保存的数据为case语句块地址表中的索引编号。
首先将所有的case语句块首地址保存在一个地址表中。地址表中的表项数根据程序中case分支来决定。有多少个case分支,地址表就会有多少项,不会像有序线性那样过多浪费内存。但是,如何通过case值获取对应地址表中保存的case语句块首地址呢?为此建立了一张对应的索引表,索引表中保存了地址表的下标值。索引表中最多可以存储256项,每一项的大小为1字节,这决定了case值不可以超过1字节的最大表示范围(0~255),因此索引表也只能存储256项索引编号。
在数值间隔过多的情况下,与上节介绍的制作单一的case线性地址表相比,制作索引表的方式更加节省空间,但是由于在执行时需要通过索引表来查询地址表,会多出一次查询地址表的过程,因此效率会有所下降。
此方案所占用的内存空间如下:
索引表大小=(MAX-MIN)* 1字节
地址表大小=SUM * 4字节
占用总字节数=((MAX-MIN) * 1字节) + (SUM * 4字节)
看了这么多理论,你可能会觉得麻烦。通过实际调试,你会发现这个优化结构很简单,并没有想象中的那么复杂。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include<iostream>
using namespace std;
int main(int argc,char * argv[])
{
int nIndex=1;
scanf("%d",&nIndex);
switch(nIndex)
{
case 1: printf("nIndex=1"); break;
case 2: printf("nIndex=2"); break;
case 3: printf("nIndex=3"); break;
case 5: printf("nIndex=5"); break;
case 6: printf("nIndex=6"); break;
case 255: printf("nIndex=255"); break;
}
return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
00401066    8B55 F8         mov edx,dword ptr ss:[ebp-0x8]            ; 取出nIndex的值,放入edx中
00401069 83EA 01 sub edx,0x1 ; 索引表下标从0开始,case最小编号为1,需要进行减1跳转
0040106C 8955 F8 mov dword ptr ss:[ebp-0x8],edx
0040106F 817D F8 FE00000>cmp dword ptr ss:[ebp-0x8],0xFE ; 将临时变量与254进行无符号比较,若临时变量大于254则跳转
00401076 77 6A ja short test.004010E2 ; 跳转到0x004010E2,即switch的结尾
00401078 8B4D F8 mov ecx,dword ptr ss:[ebp-0x8] ; 把减一后的索引放入ecx中
0040107B 33C0 xor eax,eax ; 清空eax
0040107D 8A81 11114000 mov al,byte ptr ds:[ecx+0x401111] ; 从索引表中取出对应地址表的下标
00401083 FF2485 F5104000 jmp dword ptr ds:[eax*4+0x4010F5] ; 以eax作为下标,0x4010F5为基址进行寻址,跳转到该地址处
0040108A 68 5C304300 push test.0043305C
0040108F E8 CC720000 call test.printfgvdbgraits
00401094 83C4 04 add esp,0x4
00401097 EB 49 jmp short test.004010E2
00401099 68 50304300 push test.00433050
0040109E E8 BD720000 call test.printfgvdbgraits
004010A3 83C4 04 add esp,0x4
004010A6 EB 3A jmp short test.004010E2
004010A8 68 44304300 push test.00433044
004010AD E8 AE720000 call test.printfgvdbgraits
004010B2 83C4 04 add esp,0x4
004010B5 EB 2B jmp short test.004010E2
004010B7 68 38304300 push test.00433038
004010BC E8 9F720000 call test.printfgvdbgraits
004010C1 83C4 04 add esp,0x4
004010C4 EB 1C jmp short test.004010E2
004010C6 68 2C304300 push test.0043302C
004010CB E8 90720000 call test.printfgvdbgraits
004010D0 83C4 04 add esp,0x4
004010D3 EB 0D jmp short test.004010E2
004010D5 68 1C304300 push test.0043301C
004010DA E8 81720000 call test.printfgvdbgraits
004010DF 83C4 04 add esp,0x4
004010E2 33C0 xor eax,eax

代码首先查询索引表,索引表由数组组成,数组的每一项大小为1字节。从索引表中取出地址表的下标,根据下标值,找到跳转地址表中对应的case语句块的首地址,跳转到该地址处。这种查询方式会产生两次间接访问,在效率上低于线性表方式。
索引表
case语句块首地址表

总结:

1
2
3
4
5
6
7
8
9
mov reg,mem
sub reg,1
mov mem,reg
;影响标志位的指令
jxx xxx
mov reg,[mem]
xor eax,eax
mov al,byte ptr [reg+xxxx]
jmp dword ptr [eax*4+xxxx]

如果遇到以上代码块,可判定其是添加了索引表的switch结构。这里有两次查找地址的过程,先分析第一次查表代码,byte ptr指明了表中的元素类型为byte;然后分析是否使用在第一次查表中获取的单字节数据作为下标,从而决定是否使用相对比例因子的寻址方式进行第二次查表;最后检查基址是否指向了地址表。有了这些特征后,即可参考索引表中保存的下标值来恢复索引表的switch结构中的每一句case原型。

降低判断树的高度

前一节讲述了对非线性索引表的优化,讨论了最大case值和最小case值之差在255以内的情况。当最大case值与最小case值之差大于255,超出索引1字节的表达范围时,上述优化方案同样会造成空间的浪费,此时采用另一种优化方案——判定树;将每个case值作为一个节点,从这些节点中找到一个中间值作为跟节点,以此形成一个二叉平衡树,以每个节点为判定值,大于和小于关系分别对应左子树和右子树,这样可以提高效率。
如果打开O1选项——体积优先,由于有序线性优化和索引表优化都需要消耗额外的空间,因此在体积优先的情况下,这两种优化方案是不被允许的。编译器尽量以二叉判定树的方式来降低程序占用的体积。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<iostream>
using namespace std;
int main(int argc,char * argv[])
{
int nIndex=1;
scanf("%d",&nIndex);
switch(nIndex)
{
case 2: printf("nIndex=2"); break;
case 3: printf("nIndex=3"); break;
case 8: printf("nIndex=8"); break;
case 10: printf("nIndex=10"); break;
case 35: printf("nIndex=35"); break;
case 37: printf("nIndex=37"); break;
case 666: printf("nIndex=666"); break;
default: printf("default"); break;
}
return 0;
}

如果没有case 666这句代码,可以采用非线性索引表的方式进行优化。有了case 666这句代码后,便无法使用伪造if else优化、有序线性优化、非线性索引表优化等方式。需要使用更强大的优化方案,将switch做出树,Debug版代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
00401060  |.  8B4D FC       mov ecx,[local.1]
00401063 |. 894D F8 mov [local.2],ecx ; 取出变量nIndex进行比较
00401066 |. 837D F8 0A cmp [local.2],0xA
0040106A |. 7F 1D jg short test.00401089 ; 大于10进行跳转
0040106C |. 837D F8 0A cmp [local.2],0xA
00401070 |. 74 5B je short test.004010CD ; 等于10进行跳转
00401072 |. 837D F8 02 cmp [local.2],0x2
00401076 |. 74 28 je short test.004010A0 ; 等于2进行跳转
00401078 |. 837D F8 03 cmp [local.2],0x3
0040107C |. 74 31 je short test.004010AF ; 等于3进行跳转
0040107E |. 837D F8 08 cmp [local.2],0x8
00401082 |. 74 3A je short test.004010BE ; 等于8进行跳转
00401084 |. E9 80000000 jmp test.00401109 ; 前面都不成立跳转至default块首地址
00401089 |> 837D F8 23 cmp [local.2],0x23
0040108D |. 74 4D je short test.004010DC ; 等于35跳转
0040108F |. 837D F8 25 cmp [local.2],0x25
00401093 |. 74 56 je short test.004010EB ; 等于37跳转
00401095 |. 817D F8 9A020>cmp [local.2],0x29A
0040109C |. 74 5C je short test.004010FA ; 等于666跳转
0040109E |. EB 69 jmp short test.00401109 ; 前面都不成立跳转至default块首地址
004010A0 |> 68 74304300 push test.00433074
004010A5 |. E8 96710000 call test.printfgvdbgraits
004010AA |. 83C4 04 add esp,0x4
004010AD |. EB 67 jmp short test.00401116
004010AF |> 68 68304300 push test.00433068
004010B4 |. E8 87710000 call test.printfgvdbgraits
004010B9 |. 83C4 04 add esp,0x4
004010BC |. EB 58 jmp short test.00401116
004010BE |> 68 5C304300 push test.0043305C
004010C3 |. E8 78710000 call test.printfgvdbgraits
004010C8 |. 83C4 04 add esp,0x4
004010CB |. EB 49 jmp short test.00401116
004010CD |> 68 50304300 push test.00433050
004010D2 |. E8 69710000 call test.printfgvdbgraits
004010D7 |. 83C4 04 add esp,0x4
004010DA |. EB 3A jmp short test.00401116
004010DC |> 68 44304300 push test.00433044
004010E1 |. E8 5A710000 call test.printfgvdbgraits
004010E6 |. 83C4 04 add esp,0x4
004010E9 |. EB 2B jmp short test.00401116
004010EB |> 68 38304300 push test.00433038
004010F0 |. E8 4B710000 call test.printfgvdbgraits
004010F5 |. 83C4 04 add esp,0x4
004010F8 |. EB 1C jmp short test.00401116
004010FA |> 68 28304300 push test.00433028
004010FF |. E8 3C710000 call test.printfgvdbgraits
00401104 |. 83C4 04 add esp,0x4
00401107 |. EB 0D jmp short test.00401116
00401109 |> 68 1C304300 push test.0043301C
0040110E |. E8 2D710000 call test.printfgvdbgraits
00401113 |. 83C4 04 add esp,0x4

在switch的处理代码中,比较判断的次数非常多。首先与10进行了比较,大于10跳转到地址0x00401089处,这个地址又是条件跳转操作,比较的数值为35.如果不等于35,则与37比较;不等于37又再次与666进行比较;与66比较失败后会跳转到switch结尾或default块的首地址。到此为止,大于10的比较就全部结束了。从这几处比较可以发现,这类似一个if分支结构。
从以上可以发现这棵树的左右两侧并不平衡,而是两个if else结构。由于判断较少,平衡后的效果不明显,且进行树平衡的效率明显低于if else。这时,编译器采取的策略是,当树中的叶子节点数小于等于3时,就会形成一个if else结构。
当向子数中插入一个叶子节点10000时,左子树叶子节点大于4。此时if else的转换已经不合适了,优先查看是否可以匹配有序线性优化、非线性索引表优化,如果可以,则转换为相应的优化。在不符合以上两个优化规则的情况下,就做成平衡树。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<iostream>
using namespace std;
int main(int argc,char * argv[])
{
int nIndex=1;
scanf("%d",&nIndex);
switch(nIndex)
{
case 2: printf("nIndex=2"); break;
case 3: printf("nIndex=3"); break;
case 8: printf("nIndex=8"); break;
case 10: printf("nIndex=10"); break;
case 35: printf("nIndex=35"); break;
case 37: printf("nIndex=37"); break;
case 666: printf("nIndex=666"); break;
case 10000: printf("nIndex=10000"); break;
default: printf("default"); break;
}
return 0;
}

编译后Release版下,使用IDA载入,,右键-图表视图。得到树结构流程图。

根据流程走向可以看出,有一个根节点,左边的分支流程结构很像一个switch,而右边则是一个多次比较判断,和if else类似。
为了降低树的高度,在树的优化过程中,检测树的左子树或有子树能否满足if else优化、有序线性优化、非线性索引优化,利用这三种优化来降低树的高度。选择哪种优化也是有顺序的,谁的效率高,又满足匹配条件,就可以被优先使用。以上三种优化都无法匹配,就会选择使用判定树。

do/while/for的比较

C++使用三种语法来完成循环结构,分别为do、while、for。虽然它们完成的功能都是循环,但是每种语法有着不同的执行流程。

  • do循环:先执行循环体,后比较判断。
  • while循环:先比较判断,后执行循环体。
  • for循环:先初始化,再比较判断,最后执行循环体。

对每种结构进行分析,了解它们生成的汇编代码,它们之间的区别,以及如何根据每种循环结构的特性进行还原。

do循环

do循环的工作流程清晰,识别起来也相对简单。根据其特性,先执行语句块,再进行比较判断。当条件成立时,会继续执行语句块。C++中的goto语句也可以用来模拟do循环结构。代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
#include<iostream>
using namespace std;
int main(int argc,char * argv[])
{
int nSum=0;
int nIndex=0;
do
{
nSum+=nIndex;
nIndex++;
}while(nIndex<=argc);
return nSum;
}

代码演示了使用goto语句与if分支结构来实现do循环过程。程序执行流程是自上向下地顺序执行代码,通过goto语句向上跳转修改程序流程,实现循环。do循环结构也是如此。

1
2
3
4
5
6
7
8
9
10
11
00401048    C745 FC 0000000>mov dword ptr ss:[ebp-0x4],0x0           ; 初始化变量nSum
0040104F C745 F8 0000000>mov dword ptr ss:[ebp-0x8],0x0 ; 初始化变量nIndex
00401056 8B45 FC mov eax,dword ptr ss:[ebp-0x4]
00401059 0345 F8 add eax,dword ptr ss:[ebp-0x8]
0040105C 8945 FC mov dword ptr ss:[ebp-0x4],eax ; nSum+=nIndex;
0040105F 8B4D F8 mov ecx,dword ptr ss:[ebp-0x8]
00401062 83C1 01 add ecx,0x1
00401065 894D F8 mov dword ptr ss:[ebp-0x8],ecx ; nIndex++;
00401068 8B55 F8 mov edx,dword ptr ss:[ebp-0x8]
0040106B 3B55 08 cmp edx,dword ptr ss:[ebp+0x8]
0040106E ^ 7E E6 jle short test.00401056 ; 使用跳转指令,小于等于则跳转到地址0x00401056

循环的比较语句“while(nIndex<=argc)”转换成的汇编代码和if分支结构非常相似,分析后发现它们并不相同。if语句的比较逻辑是相反的,并且跳转地址大于当前代码的地址,是一个向下跳转的过程;而do中的跳转地址小于当前代码的地址,是一个向上跳转的过程,所以条件跳转的逻辑与源码中的逻辑相同。
总结:

1
2
3
4
DO_BEGIN:
.......//循环语句块
//影响标记位的指令
jxx DO_BEGIN //向上跳转

如果遇到以上代码块,即可判定它为一个do循环结构,只有do循环结构无需先检查,直接执行循环语句块。根据条件跳转指令所跳转到的地址,可以得到循环语句块的首地址,jxx指令的地址为循环语句块的结尾地址。在还原while比较时,应该注意,它与if不同,while的比较逻辑并不是相反,而是相同的。依次分析即可还原do循环结构的原形。

while循环

while循环和do循环正好相反,在执行循环语句块之前,必须要进行条件判断,根据比较结果再选择是否执行循环语句块。

1
2
3
4
5
6
7
8
9
10
11
12
13
#include<iostream>
using namespace std;
int main(int argc,char * argv[])
{
int nSum=0;
int nIndex=0;
while(nIndex<=argc)
{
nSum+=nIndex;
nIndex++;
}
return nSum;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
00401048    C745 FC 0000000>mov dword ptr ss:[ebp-0x4],0x0           ; 初始化变量nSum
0040104F C745 F8 0000000>mov dword ptr ss:[ebp-0x8],0x0 ; 初始化变量nIndex
00401056 8B45 F8 mov eax,dword ptr ss:[ebp-0x8]
00401059 3B45 08 cmp eax,dword ptr ss:[ebp+0x8]
0040105C 7F 14 jg short test.00401072 ; 条件判断比较,大于则跳转到地址0x00401072,和if语句一样
//0x00401072为while循环结束地址
0040105E 8B4D FC mov ecx,dword ptr ss:[ebp-0x4]
00401061 034D F8 add ecx,dword ptr ss:[ebp-0x8]
00401064 894D FC mov dword ptr ss:[ebp-0x4],ecx ; nSum+=nIndex;
00401067 8B55 F8 mov edx,dword ptr ss:[ebp-0x8]
0040106A 83C2 01 add edx,0x1
0040106D 8955 F8 mov dword ptr ss:[ebp-0x8],edx ; nIndex++;
00401070 ^ EB E4 jmp short test.00401056 ; 跳转到0x00401056地址处

转换后的while比较和if语句一样,比较逻辑也是相反的,向下跳转。如何区分代码中是分支结果还是循环结构呢?查看条件指令跳转地址0x00401072,如果这个地址上有一句jmp指令,并且此指令跳转到的地址小于当前代码地址,那么很明显是一个向上跳转。要完成语句循环,就需要修改程序流程,回到循环语句处,因此向上跳转就成了循环结构的明显特征。根据这些特征可知while循环结构的特征,在条件跳转到的地址附近会有jmp指令修改程序流程,向上跳转,回到条件比较指令处。
while循环结构使用了两次跳转指令完成循环,由于多使用了一次跳转指令,因此while循环要比do循环效率低一些。
总结:

1
2
3
4
5
6
WHILE_BEGIN:
//影响标记位的指令
jxx WHILE_END //条件成立跳转到循环语句结尾处
...... //循环语句块
jmp WHILE_BEGIN //跳转到取出条件比较数据处
WHILE_END:

遇到以上代码块,即可判定它为一个while循环结构。根据条件跳转指令,可以还原相反的while循环判断。循环语句块的结尾地址即为条件跳转指令的目标地址,在这个地址之前会有一条jmp跳转指令,指令的目标地址为while循环的起始地址。需要注意的是,while循环结构很可能会被优化成do循环结构,被转换后的while结构由于需要检查是否可以被还原成执行一次,通常会被嵌套在if单分支结构中,其还原的高级代码如下:

1
2
3
4
5
6
7
if(xxx)
{
do
{
....
}while(xxx);
}

for循环

for循环是三种循环结构中最复杂的一种。for循环由赋初值、设置循环条件、设置循环步长三条语句组成。由于for循环更符合人类的思维方式,在循环结构中被使用的频率也最高。

1
2
3
4
5
6
7
8
9
int LoopFor(int n)
{
int nSum=0;
for(int i=0;i<=n;i++)
{
nSum+=i;
}
return nSum;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
00401048    C745 FC 0000000>mov dword ptr ss:[ebp-0x4],0x0                      ; 初始化变量nSum
0040104F C745 F8 0000000>mov dword ptr ss:[ebp-0x8],0x0 ; 初始化变量i
00401056 EB 09 jmp short test.00401061 ; 跳转到地址0x00401061跳过步长操作
00401058 8B45 F8 mov eax,dword ptr ss:[ebp-0x8] ; 取出计数器变量i,用于循环步长
0040105B 83C0 01 add eax,0x1 ; 对计数器变量执行加1操作
0040105E 8945 F8 mov dword ptr ss:[ebp-0x8],eax ; 将加1后的步长值放回计数器变量
00401061 8B4D F8 mov ecx,dword ptr ss:[ebp-0x8]
00401064 3B4D 08 cmp ecx,dword ptr ss:[ebp+0x8]
00401067 7F 0B jg short test.00401074 ; 比较i与n,大于则跳转到地址0x00401074处,结束循环
00401069 8B55 FC mov edx,dword ptr ss:[ebp-0x4]
0040106C 0355 F8 add edx,dword ptr ss:[ebp-0x8]
0040106F 8955 FC mov dword ptr ss:[ebp-0x4],edx ; nSum+=i;
00401072 ^ EB E4 jmp short test.00401058 ; 跳转到0x00401058处,这是一个向上跳
00401074 8B45 FC mov eax,dword ptr ss:[ebp-0x4] ; 设置返回值nSum

代码演示了for循环结构在debug调试版下的汇编代码组成。需要3次跳转来完成循环过程,其中一次为条件比较跳转,另外两次为jmp跳转。for循环的流程如图所示。

for循环结构在debug版下的特性。
总结:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
mov mem/reg,xxx              ;赋初值
jmp FOR_CMP ;跳到循环条件判定部分
FOR_STEP: ;步长计算部分
;修改循环变量Step
mov reg,Step
add reg,xxxxx ;修改循环变量的计算过程,在实际分析中,视算法不同而不同
mov Step,eax
FOR_CMP:
mov ecx,dword ptr Step
;判定循环变量和循环终止条件StepEnd的关系,满足条件则退出for循环
cmp ecx,StepEnd
jxx FOR_END ;条件成立则结束循环
......
jmp FOR_STEP ;向上跳转,修改流程回到步长计算部分
FOR_END:

遇到以上代码块,即可判定它为一个for循环结构。这种结构是for循环独有的,在计数器变量被赋初值后,利用jmp跳过第一次步长计算。然后,可以通过三个跳转指令还原for循环的各个组成部分:第一个jmp指令之前的代码为初始化部分;从第一个jmp指令到循环条件比较处之间的代码为步长计算部分;在条件跳转指令jxx之后寻址一个jmp指令,这jmp指令必须是向上跳转,且目标是到步长计算的位置,在jxx和jmp之间的代码即为循环语句块。
在这三种循环结构中,while循环和for循环一样,都是先判断再循环。由于需要先判断,因此需要将判断语句放置在循环语句之前,这就使while循环和for循环在结构上没有do循环那么简洁。

编译器对循环结构的优化

3种循环结构,在执行效率上,do循环结构是最高的。由于do循环在结构上非常精简,利用了程序执行时由低地址到高地址的特点,只使用一个条件跳转指令就完成了循环,因此已经无需在结构上进行优化处理。
while循环结构的效率比do循环结构低。while循环结构先比较再循环,因此无法利用程序执行顺序来完成循环。同时,while循环结构使用了2个跳转指令,在程序流程上就弱于do循环结构。为了提升while循环结构的效率,可以将其转换成效率较高的do循环结构。
从结构特征上可知,for循环是执行速度最慢的,它需要三个跳转指令才能完成循环,因此也需要对其进行优化。从循环结构上看,其结构特征和while循环结构类似。由于赋初值部分不属于循环体,可以忽略。只要将比较部分放到循环体内,即是一个while循环结构。既然可以转换while循环结构,那么自然也能转换为do循环结构进行优化以提升效率。
由于在O2选项下,while循环和for循环都可以使用do循环进行优化,所以在分析经过O2选项优化的反汇编代码时,很难转换回相同的源码,只能尽量还原等价源码。

文章目录
  1. 1. if语句
  2. 2. if…else…语句
  3. 3. 用if构成的多分支流程
  4. 4. switch的真相
  5. 5. 难以构成跳转表的switch
  6. 6. 降低判断树的高度
  7. 7. do/while/for的比较
    1. 7.1. do循环
    2. 7.2. while循环
    3. 7.3. for循环
  8. 8. 编译器对循环结构的优化