首页
论坛
课程
招聘
[原创]第一章:1.5、switch-case识别技巧初探
2010-6-4 04:31 16983

[原创]第一章:1.5、switch-case识别技巧初探

2010-6-4 04:31
16983
要问接触C++逆向之前最有趣的知识点是什么?笔者认为非switch-case结构莫属了……
    但是不得不说的是,有关于switch-case逆向真的可谓博大精深了(相对于基础薄弱者),因此笔者在提笔之前做了很多假设,并且自己也推翻了几种方案。最后得出的结论是此知识点一定要深入讲解,特别是到后面的东西更是要涉及到一些数据结构相关的知识,笔者会尽力用最简洁、最简单的语言为大家阐述清楚,我想既然我都有信心使各位读者能看懂本小节,那么各位读者就更因该努力了。
    下面我们进入主题,我们都知道switch-case的诞生其实就是为了避免出现大量的、高重复if-else语句,换句话说,switch-case语句其实就是if-else语句的另一种体现形式,但是事实真的是这样吗?让我们一起为这个观点求证……

1.5.1、简单switch-case分支识别技巧

    我们先看一段代码:

int _tmain(int argc, _TCHAR* argv[])
{
    int nNum = 2;
    switch (nNum)
    {
    case 0:
        printf("nNum=0");
        break;
    case 1:
        printf("nNum=1");
        break;
    case 2:
        printf("nNum=2");
        break;
    default:
        printf("nNum=%d,error!",nNum);
    }
    return 0;
}

    看完这段代码,在看完本小节的标题,有些读者可能会产生一些疑问,例如switch-case的不可达分支会被剪掉吗、switch-case分支以常量为判断条件的优化效果与if-else有多大区别、以变量为判断条件的switch-case分支优化效果与if-else分支有多大区别等等问题。
    现在就让我们带着这些问题继续,让我们一一为其找到答案。
    先看Debug版的反汇编代码:

004133AE  MOV DWORD PTR SS:[EBP-8], 2              ; 给局部变量赋值
004133B5  MOV EAX, DWORD PTR SS:[EBP-8]
004133B8  MOV DWORD PTR SS:[EBP-D0], EAX
004133BE  CMP DWORD PTR SS:[EBP-D0], 0             ; 比较是否等于0
004133C5  JE SHORT Test_0.004133DB                 ; 如果等于0则跳到相应分支,否则继续
004133C7  CMP DWORD PTR SS:[EBP-D0], 1
004133CE  JE SHORT Test_0.004133F4                 ; 同上
004133D0  CMP DWORD PTR SS:[EBP-D0], 2
004133D7  JE SHORT Test_0.0041340D                 ; 同上
004133D9  JMP SHORT Test_0.00413426                ; 都不符合则直接跳转到最后一个分支处
004133DD  PUSH Test_0.00415808                     ; /format = "nNum=0"
004133E2  CALL DWORD PTR DS:[<&MSVCR90D.printf>]   ; \printf
004133E8  ADD ESP, 4
004133F2  JMP SHORT Test_0.00413441
004133F6  PUSH Test_0.004157B0                     ; /format = "nNum=1"
004133FB  CALL DWORD PTR DS:[<&MSVCR90D.printf>]   ; \printf
00413401  ADD ESP, 4
0041340B  JMP SHORT Test_0.00413441
0041340F  PUSH Test_0.00415C18                     ; /format = "nNum=2"
00413414  CALL DWORD PTR DS:[<&MSVCR90D.printf>]   ; \printf
0041341A  ADD ESP, 4
00413424  JMP SHORT Test_0.00413441
00413428  MOV EAX, DWORD PTR SS:[EBP-8]
0041342B  PUSH EAX                                 ; /<%d>
0041342C  PUSH Test_0.004157A0                     ; |format = "nNum=%d,error!"
00413431  CALL DWORD PTR DS:[<&MSVCR90D.printf>]   ; \printf
00413437  ADD ESP, 8

    通过以上反汇编代码我们可以总结出以下特点:

cmp XXX,XXX
jXX CASE1_TAG
cmp XXX,XXX
jXX CASE2_TAG
cmp XXX,XXX
jXX CASE3_TAG
......
CMP XXX,XXX
JXX CASEN_TAG
......
JMP DEFAULT
CASE1_TAG:
......
CASE2_TAG:
......
CASE3_TAG:
......
......
CASEN_TAG:
......
......
DEFAULT:
......
SWITCH_END_TAG:

    我们可以看到Debug版的反汇编指令与我们的源代码的相似度还是非常高的,都是通过开始的一连串判断,然后确定接下来走哪个Case分支。下面我们再看看Release版的反汇编代码:

00401000  PUSH Test_0.004020F4                     ; /format = "nNum=2"
00401005  CALL DWORD PTR DS:[<&MSVCR90.printf>]    ; \printf
0040100B  ADD ESP, 4
0040100E  XOR EAX, EAX
00401010  RETN

    瞧瞧,简单至极呀!由此可见switch-case语句与我们之前接触的if-else语句一样,不可达分支都会被编译器优化掉,那么如果如果其部分分支相同,是否仍会像if-else分之一样呢?先看源码:

int _tmain(int argc, _TCHAR* argv[])
{
    switch (argc)
    {
    case 0:
        printf("argc=0",argc);
        break;
    case 1:
        printf("argc=%d",argc);
        break;
    case 2:
        printf("argc=%d",argc);
        break;
    default:
        printf("argc=%d,error!",argc);
    }
    return 0;
}

    按照if-esle的优化逻辑,case 1 与 csae 2 会指向同一处,真的是这样吗?我们直接看Release版反汇编代码:

00401000  /$>MOV ECX, DWORD PTR SS:[ESP+4]
00401004  |.>MOV EAX, ECX
00401006  |.>SUB EAX, 0                               ;  Switch (cases 0..2)
00401009  |.>JE SHORT Test_0.0040104D
0040100B  |.>SUB EAX, 1                               ; 注意这里用的是减法
0040100E  |.>JE SHORT Test_0.0040103A
00401010  |.>SUB EAX, 1
00401013  |.>JE SHORT Test_0.00401027
00401015  |.>PUSH ECX                                 ; /<%d>; Default case of switch 00401006
00401016  |.>PUSH Test_0.00402104                     ; |format = "argc=%d,error!"
0040101B  |.>CALL DWORD PTR DS:[<&MSVCR90.printf>]    ; \printf
00401021  |.>ADD ESP, 8
00401024  |.>XOR EAX, EAX
00401026  |.>RETN                                     ; 执行完某一个分支后会直接返回
00401027  |>>PUSH 2                                   ; /<%d> = 2; Case 2 of switch 00401006
00401029  |.>PUSH Test_0.004020FC                     ; |format = "argc=%d"
0040102E  |.>CALL DWORD PTR DS:[<&MSVCR90.printf>]    ; \printf
00401034  |.>ADD ESP, 8
00401037  |.>XOR EAX, EAX
00401039  |.>RETN
0040103A  |>>PUSH 1                                   ; /<%d> = 1; Case 1 of switch 00401006
0040103C  |.>PUSH Test_0.004020FC                     ; |format = "argc=%d"
00401041  |.>CALL DWORD PTR DS:[<&MSVCR90.printf>]    ; \printf
00401047  |.>ADD ESP, 8
0040104A  |.>XOR EAX, EAX
0040104C  |.>RETN
0040104D  |>>PUSH 0                                   ;  Case 0 of switch 00401006
0040104F  |.>PUSH Test_0.004020F4                     ; /format = "argc=0"
00401054  |.>CALL DWORD PTR DS:[<&MSVCR90.printf>]    ; \printf
0040105A  |.>ADD ESP, 8
0040105D  |.>XOR EAX, EAX
0040105F  \.>RETN

    看来switch-case并没有将相同的分支合并,我们可以很清楚的看到它的4个分支仍都存在。
    既然它的分支并没有合并,那么我们就讨论点其他的,请各位读者回头仔细观察反汇编代码的第1-9行,我们可以发现Release在条件跳转前用的不再是cmp,而是sub,很显然编译器这样优化是有其理由的,但是这个理由究竟是什么?
    我们通过阅读这块代码可知程序先将main函数的参数1传递给EAX,然后减0,这有点让人迷糊,我们接着看下面的那个跳转:

00401009  |.>JE SHORT Test_0.0040104D

    让我们回顾一下汇编语言,我们应该都记得JE的跳转条件是ZF=1,因此当我们的EAX为0时,那么将其减0肯定会使ZF位置1,因此其实这就是一个变形的CMP指令,只不过这么做程程的代码体积更小、效率更高。
    知道这些后,后面的优化自然就肯好理解了,现在假设我们的EAX等于2,因此按照上面代码的流程走会先将其减0,此时ZF位不变,接着下面又对其减1,此时ZF位仍然没变化,而当走到第三步时,此时EAX的值为1,又将其减1后肯定就等于0了,ZF位置为1,后面的JZ跳转生效……
    我们可以看到其实就是做了一连串的减法,到哪等于0后,就证明这个值原先为多少,由此可见微软的编译器还是很聪明的。不过这些代码从本质上来说还是属于if-esle范畴内的。

   
1.5.2、多分支的switch-case识别

    我们平时在写程序时都会遇到一些问题,而这些问题肯定必须要用多分支的switch-case才能解决,但是你知道这种情况在反汇编状态下应该怎么去识别吗?下面我们就一起看看switch-case的另外一种体现方式,我们先看代码:

int _tmain(int argc, _TCHAR* argv[])
{
    switch (argc)
    {
    case 0:
        printf("argc=0",argc);
        break;
    case 1:
        printf("argc=%d",argc);
        break;
    case 6:
        printf("argc=%d",argc);
        break;
    case 7:
        printf("argc=%d",argc);
        break;
    case 9:
        printf("argc=%d",argc);
        break;
    default:
        printf("argc=%d,error!",argc);
    }
    return 0;
}

    注意上面的case条件并不是有规律的,我们直接看它的Release版反汇编代码:

00401000  MOV EAX, DWORD PTR SS:[ESP+4]
00401004  CMP EAX, 9                               ;  Switch (cases 0..9)
00401007  JA SHORT Test_0.0040106F                 ;  如果大于最大值9则直接跳到Default处
00401009  JMP DWORD PTR DS:[EAX*4+401084]          ;  注意这里!!
00401010  PUSH 0                                   ;  Case 0 of switch 00401004
00401012  PUSH Test_0.004020F4                     ; /format = "argc=0"
00401017  CALL DWORD PTR DS:[<&MSVCR90.printf>]    ; \printf
0040101D  ADD ESP, 8
00401020  XOR EAX, EAX
00401022  RETN
00401023  PUSH 1                                   ; /<%d> = 1; Case 1 of switch 00401004
00401025  PUSH Test_0.004020FC                     ; |format = "argc=%d"
0040102A  CALL DWORD PTR DS:[<&MSVCR90.printf>]    ; \printf
00401030  ADD ESP, 8
00401033  XOR EAX, EAX
00401035  RETN
00401036  PUSH 6                                   ; /<%d> = 6; Case 6 of switch 00401004
00401038  PUSH Test_0.004020FC                     ; |format = "argc=%d"
0040103D  CALL DWORD PTR DS:[<&MSVCR90.printf>]    ; \printf
00401043  ADD ESP, 8
00401046  XOR EAX, EAX
00401048  RETN
00401049  PUSH 7                                   ; /<%d> = 7; Case 7 of switch 00401004
0040104B  PUSH Test_0.004020FC                     ; |format = "argc=%d"
00401050  CALL DWORD PTR DS:[<&MSVCR90.printf>]    ; \printf
00401056  ADD ESP, 8
00401059  XOR EAX, EAX
0040105B  RETN
0040105C  PUSH 9                                   ; /<%d> = 9; Case 9 of switch 00401004
0040105E  PUSH Test_0.004020FC                     ; |format = "argc=%d"
00401063  CALL DWORD PTR DS:[<&MSVCR90.printf>]    ; \printf
00401069  ADD ESP, 8
0040106C  XOR EAX, EAX
0040106E  RETN
0040106F  PUSH EAX                                 ; /<%d>; Default case of switch 00401004
00401070  PUSH Test_0.00402104                     ; |format = "argc=%d,error!"
00401075  CALL DWORD PTR DS:[<&MSVCR90.printf>]    ; \printf
0040107B  ADD ESP, 8
0040107E  XOR EAX, EAX
00401080  RETN

    看完上段反汇编代码后有些读者可能感觉很奇怪,难道那个位于第4行的JMP指令就能解决这些问题吗?当然不会这么简单……
    我们现在就仔细分析一下头几条反汇编指令:

00401000  MOV EAX, DWORD PTR SS:[ESP+4]            ; 取得局部变量后传递给EAX
00401004  CMP EAX, 9                               ; 与9作比较,我们通过源代码可知这个switch-case分支的最大值“case 9”,因
                                                   ; 此如果传入的值大于9就肯定会执行Default处代码了。
00401007  JA SHORT Test_0.0040106F
00401009  JMP DWORD PTR DS:[EAX*4+401084]          ; EAX此时保存的是输入的值,将其乘以4后再加上一个地址,这其实就是一个典型
                                                   ; 的数组寻址,由于我们还没学数组寻址,所以这块先放一放。我们现在只需要要
                                                   ; 知道这是一个读取int型的数组,里面保存的是地址指针。

    那么目标地址里究竟保存了什么数据?这个机制的原理又是怎么回事呢?我们看看如下内容便可以猜出一二了……

Address   Data      Tag
00401084  00401010  Test_0.00401010   ; Case0
00401088  00401023  Test_0.00401023   ; Case1
0040108C  0040106F  Test_0.0040106F   ; Case2
00401090  0040106F  Test_0.0040106F   ; Case3
00401094  0040106F  Test_0.0040106F   ; Case4
00401098  0040106F  Test_0.0040106F   ; Case5
0040109C  00401036  Test_0.00401036   ; Case6
004010A0  00401049  Test_0.00401049   ; Case7
004010A4  0040106F  Test_0.0040106F   ; Case8
004010A8  0040105C  Test_0.0040105C   ; Case9

    通过上面表格的地址可以知道这就是我们上面提到的“数组指针”了,里面保存的内容是各个Case块的地址,我们将之称为“跳转表”。跳转表的作用就是通过数组的寻址运算代替复杂的if-else分支,这样可以大大提供程序的执行效率。
    它的基本原理是建立一张表格,里面保存着从case1到caseN的所有分支应该到达的地址。以上面程序的情况为例子,我们可以看出从case2至case5里保存的地址都是跳向Default分支的地址,这就证明这几个case在程序的源代码中是属于未处理(或称为非正常)的状态。
    但是什么时候编译器才会决定用跳转表的方式来优化程序呢?这显然不是我等简单的用个什么公式就能计算出来的,这需要综合各种条件、因素来决定是否使用跳转表。在这里我可以给出一个反例,既如果我们的最大case块为999999的话,难道程序还会用这个方法解决吗?肯定不会!
    下一节我将阐述编译器是怎样解决这类复杂的Switch-case组合的。

【返回到目录】:http://bbs.pediy.com/showthread.php?t=113689

[2022冬季班]《安卓高级研修班(网课)》月薪三万班招生中~

收藏
点赞0
打赏
分享
最新回复 (27)
雪    币: 779
活跃值: 活跃值 (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
RogerWood 活跃值 2010-6-4 09:12
2
0
第一时间顶贴
雪    币: 202
活跃值: 活跃值 (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
zzycqok 活跃值 2010-6-4 09:16
3
0
先顶后看是好习惯。
雪    币: 779
活跃值: 活跃值 (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
RogerWood 活跃值 2010-6-4 09:31
4
0
楼上的怎么这么多kx
雪    币: 6
活跃值: 活跃值 (25)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
keren_1985 活跃值 2010-6-4 10:04
5
0
看看自己有多少KX....
雪    币: 219
活跃值: 活跃值 (59)
能力值: ( LV13,RANK:530 )
在线值:
发帖
回帖
粉丝
foxabu 活跃值 13 2010-6-4 10:13
6
0
http://www.openrce.org/blog/view/1319/Switch_as_Binary_Search,_Part_0

http://www.openrce.org/blog/view/1320/Switch_as_Binary_Search,_Part_1

供参考。
雪    币: 202
活跃值: 活跃值 (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
zzycqok 活跃值 2010-6-4 10:53
7
0
学习了,感谢楼主。
雪    币: 202
活跃值: 活跃值 (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
zzycqok 活跃值 2010-6-4 10:57
8
0
呵呵,我也不知道kx是怎么来的。
反正也没有怎么用它,而且还比默认200增加了2kx
雪    币: 779
活跃值: 活跃值 (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
RogerWood 活跃值 2010-6-4 11:11
9
0
估计是注册时间早,注册当时论坛送的吧.增加的是在线送的.
我们注册的晚的就没这么好了
雪    币: 318
活跃值: 活跃值 (11)
能力值: ( LV4,RANK:50 )
在线值:
发帖
回帖
粉丝
CYBER涛 活跃值 1 2010-6-4 13:13
10
0
这一次的很好啊,以前switch很扰人的,现在从新看看的说
雪    币: 154
活跃值: 活跃值 (11)
能力值: ( LV4,RANK:50 )
在线值:
发帖
回帖
粉丝
install 活跃值 1 2010-6-4 15:42
11
0
Switch块分支条件不适合用表实现的话,编译器会用二叉树实现Switch块优化。
可能会是下一节要讲解的内容。
雪    币: 21
活跃值: 活跃值 (11)
能力值: ( LV4,RANK:50 )
在线值:
发帖
回帖
粉丝
梵听 活跃值 1 2010-6-4 17:12
12
0
一口气看到这里,感谢楼主!!!!
Mark!
雪    币: 794
活跃值: 活跃值 (90)
能力值: ( LV9,RANK:280 )
在线值:
发帖
回帖
粉丝
A1Pass 活跃值 5 2010-6-4 17:28
13
0
谢谢提供,没事经常去那里的,不错的地方。
雪    币: 794
活跃值: 活跃值 (90)
能力值: ( LV9,RANK:280 )
在线值:
发帖
回帖
粉丝
A1Pass 活跃值 5 2010-6-4 17:29
14
0
被猜到了呀,现在正在想怎样让初学者理解二叉树。
雪    币: 215
活跃值: 活跃值 (24)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
manbug 活跃值 2010-6-5 20:58
15
0
楼主的文章很精彩,学习中,呵呵,希望楼主多出这类文章!
雪    币: 794
活跃值: 活跃值 (90)
能力值: ( LV9,RANK:280 )
在线值:
发帖
回帖
粉丝
A1Pass 活跃值 5 2010-6-5 22:36
16
0
这位朋友可能没从头看我的教程,我在第一篇中介绍了,凡是Debug版生成的代码我都会给剔除掉。

那句其实是,保存相关信息以备检查的,证明:

004133D9  JMP SHORT Test_0.00413426                ; 都不符合则直接跳转到最后一个分支处
004133DD  PUSH Test_0.00415808                     ; /format = "nNum=0"

D9到DD是4个字节,但请注意上面的是一个短跳,也就是2字节,呢剩下的两个字节跑哪里去了呢?
很明显是我删除了一贴指令。
雪    币: 215
活跃值: 活跃值 (24)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
manbug 活跃值 2010-6-5 23:03
17
0
哦,不好意思,没有注意分析,唉!!!
惭愧!!
雪    币: 1869
活跃值: 活跃值 (514)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
Crakme 活跃值 2010-6-6 07:35
18
0
很好的科普文章
雪    币: 283
活跃值: 活跃值 (12)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
polk 活跃值 2010-6-7 08:47
19
0
这个是C吧?
雪    币: 65
活跃值: 活跃值 (10)
能力值: ( LV3,RANK:20 )
在线值:
发帖
回帖
粉丝
yasm 活跃值 2010-6-8 21:28
20
0
好久没有网络,今天终于能上来支持一下。
雪    币: 221
活跃值: 活跃值 (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
baronpan 活跃值 2010-6-10 14:41
21
0
一直在关注,不知道下一篇何时能够出现,期待啊
雪    币: 230
活跃值: 活跃值 (15)
能力值: ( LV4,RANK:50 )
在线值:
发帖
回帖
粉丝
lonkil 活跃值 1 2010-6-14 23:29
22
0
学习后,留名并支持楼主。
雪    币: 794
活跃值: 活跃值 (90)
能力值: ( LV9,RANK:280 )
在线值:
发帖
回帖
粉丝
A1Pass 活跃值 5 2010-7-5 11:19
23
0
没什么,非常感谢你对这个教程的关注,即便是这种反馈,也会给我以非常大的鼓励!
雪    币: 578
活跃值: 活跃值 (25)
能力值: ( LV9,RANK:140 )
在线值:
发帖
回帖
粉丝
monsterok 活跃值 3 2010-7-6 16:07
24
0
珲哥,我来看你喽
雪    币: 237
活跃值: 活跃值 (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
流浪蚂蚁 活跃值 2010-7-8 20:55
25
0
顶了再看 习惯更好
游客
登录 | 注册 方可回帖
返回