逆向工程——switch()

[TOC]

case陈述式较少的情况

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <stdio.h>

voif f( int a)
{
switch (a)
{
case 0: printf("zero\n"); break;
case 1: printf("one\n"); break;
case 2: printf("two\n"); break;
default: printf("sth unknown\n"); break;
}
}

int main()
{
f(2);
}

x86

未优化的MSVC

指令清单如下:

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
tv64 = -4			; size = 4
_a$ = 8 ; size = 4
_f PROC
push ebp
mov ebp,esp
push ecx
mov eax, DWORD PTR _a$[ebp]
mov DWORD PTR tv64[ebp], eax
cmp DWORD PTR tv64[ebp], 0
je SHORT $LN4@f
cmp DWORD PTR tv64[ebp], 1
je SHORT $LN3@f
cmp DWORD PTR tv64[ebp], 2
je SHORT $LN2@f
jmp SHORT $LN1@f
$LN4@f:
push OFFSET $SG739 ; 'zero', 0aH, 00H
call _printf
add esp,4
jmp SHORT $LN7@f
$LN3@f:
push OFFSET $SG741 ; 'one', 0aH, 00H
call _printf
add esp,4
jmp SHORT $LN7@f
$LN2@f:
push OFFSET $SG743 ; 'two', 0aH, 00H
call _printf
add esp,4
jmp SHORT $LN7@f
$LN1@f:
push OFFSET $SG745 ; 'sth unknown', 0aH, 00H
call _printf
add esp,4
jmp SHORT $LN7@f
$LN7@f:
mov esp, ebp
pop ebp
ret 0
_f ENDP

上面这个函数的源程序相当于:

1
2
3
4
5
6
7
8
9
void f (int a)
{
if (a==0)
printf ("zero\n");
else if (a==1)
printf ("one\n");
else if (a==2)
printf ("two\n");
elseprintf ("sth unknown\n"); };

如果仅从汇编代码入手,那么我们无法判断上述函数是一个判断表达式较少的switch()语句、还是一组 if()语句。确实可以认为,switch()语句是一种旨在简化大量嵌套if()语句而设计的语法糖。
若用GCC 4.4.1编译器编译这个程序,无论是否启用其最大程度优化的选项-O3,生成的汇编代码也和 MSVC 编译出来的代码没有什么区别。

优化的MSVC

若经指令cl 1.c /Fa1.asm /Ox编译上述程序,可得到如下指令清单:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
_a$ = 8 	; size = 4
_f PROC
mov eax, DWORD PTR _a$[esp-4]
sub eax, 0
je SHORT $LN4@f
sub eax, 1
je SHORT $LN3@f
sub eax, 1
je SHORT $LN2@f
mov DWORD PTR _a$[esp-4], OFFSET $SG791 ; 'sth unknown', 0aH, 00H
jmp _printf
$LN2@f:
mov DWORD PTR _a$[esp-4], OFFSET $SG789 ; 'two', 0aH, 00H
jmp _printf
$LN3@f:
mov DWORD PTR _a$[esp-4], OFFSET $SG787 ; 'one', 0aH, 00H
jmp _printf
$LN4@f:
mov DWORD PTR _a$[esp-4], OFFSET $SG785 ; 'zero', 0aH, 00H
jmp _printf
_f ENDP

我们看到,它有以下两处不同。

  1. 程序把变量 a 存储到 EAX 寄存器之后,又用 EAX 的值减去零。似乎这样做并没有什么道理。但是 这两条指令可以检查 EAX 寄存器的值是否是零。如果 EAX 寄存器的值是零,ZF 标志寄存器会被置 1(也就是说 0−0=0,这就可以提前设置 ZF 标志位),并会触发第一条条件转移指令 JE,使程序跳转到 $LN4@f,继而在屏幕 上打印Zero。如果 EAX 寄存器的值仍然不是零,则不会触发第一条跳转指令、做EAX=EAX-1的运算, 若计算结果是零则做相应输出;若此时 EAX 寄存器的值仍然不是零,就会再做一次这种减法操作和条件判断。
    如果三次运算都没能使 EAX 寄存器的值变为零,那么程序会输出最后一条信息something unknown
  2. 在把字符串指针存储到变量 a 之后,函数使用 JMP 指令调用 printf()函数。在调用 printf()函 数的时候,调用方函数而没有使用常规的 call 指令。这点不难解释:调用方函数把参数推送入栈之后,的确通常通过 CALL 指令调用其他函数。这种情况下,CALL 指令会把返回地址推送入栈、并通过无条件转移的手段启用被调用方函数。就本例而言,在被调用方函数运行的任意时刻,栈的内存存储结构为:
  • ESP——指向 RA。
  • ESP+4——指向变量 a。

这个程序把函数的第一个参数替换为字符串的指针,然后跳转到 printf()函数的地址,就好像程序没有 调用f()函数、直接转移printf()函数一般。当 printf()函数完成输出的使命以后,它会执行 RET 返回指令。RET 指令会从栈中读取(POP)返回地址 RA、并跳转到 RA。不过这个 RA 不是其调用方函数—— f()函数内的某个地址,而是调用 f()函数的函数即 main()函数的某个地址。换而言之,跳转到这个 RA 地址后,printf()函数会伴随其调用方函数 f()一同结束。
除非每个case从句的最后一条指令都是调用printf()函数,否则编译器就做不到这种程度的优化。某种意义上说这与longjmp()函数 十分相似。当然,这种优化的目的无非就是提高程序的运行速度。

ARM/MIPS

请参考《RE4B》对应篇章。

总结

在case分支较少的情况下,switch()if/else语句的编译结果基本相同。

case陈述式较多的情况

在 switch()语句存在大量case()分支的情况下,编译器就不能直接套用大量JE/JNE指令了。否则程序代码肯定会非常庞大。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <stdio.h>
void f (int a)
{
switch (a)
{
case 0: printf ("zero\n"); break;
case 1: printf ("one\n"); break;
case 2: printf ("two\n"); break;
case 3: printf ("three\n"); break;
case 4: printf ("four\n"); break;
default: printf ("something unknown\n"); break;
}
}
int main()
{
f(2); // test
}

x86

未优化的MSVC

在MSVC上编译的指令清单如下:

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
52
53
tv64 = -4 ; size=4 
_a$ = 8 ;size=4
_f PROC
push ebp
mov ebp, esp
push ecx
mov eax, DWORD PTR _a$[ebp]
mov DWORD PTR tv64[ebp], eax
cmp DWORD PTR tv64[ebp], 4
ja SHORT $LN1@f
mov ecx, DWORD PTR tv64[ebp]
jmp DWORD PTR $LN11@f[ecx*4]
$LN6@f:
push OFFSET $SG739 ; 'zero', 0aH, 00H
call _printf
add esp, 4
jmp SHORT $LN9@f
$LN5@f:
push OFFSET $SG741 ; 'one', 0aH, 00H
call _printf
add esp, 4
jmp SHORT $LN9@f
$LN4@f:
push OFFSET $SG743 ; 'two', 0aH, 00H
call _printf
add esp, 4
jmp SHORT $LN9@f
$LN3@f:
push OFFSET $SG745 ; 'three', 0aH, 00H
call _printf
add esp, 4
jmp SHORT $LN9@f
$LN2@f:
push OFFSET $SG747 ; 'four', 0aH, 00H
call _printf
add esp, 4
jmp SHORT $LN9@f
$LN1@f:
push OFFSET $SG749 ; 'something unknown', 0aH, 00H
call _printf
add esp, 4
$LN9@f:
mov esp, ebp
pop ebp
ret 0
npad 2 ;align next lable
$LN11@f:
DD $LN6@f ; 0
DD $LN5@f ; 1
DD $LN4@f ; 2
DD $LN3@f ; 3
DD $LN2@f ; 4
_f ENDP

这段代码可被分为数个调用printf()函数的指令组,而且每组指令传递给printf()函数的参数还各不相 同。这些指令组在内存中拥有各自的起始地址,也就被编译器分配到了不同的符号标签(symbolic label) 之后。总的来看,程序通过$LN11@f 处的一组数据调派这些符号标签。

函数最初把变量a的值与数字4进行比较。如果 a 大于 4,函数则跳转到$LN1@f 处,把字符串something unknown的指针传递给 printf()函数。

如果变量 a 小于或等于 4,则会计算a 乘以 4的积,再计算积与$LN11@f 的偏移量的和(表查询), 并跳转到这个结果所指向的地址上。
以变量 a 等于 2 的情况来说,2×4=8(由于 x86 系统的内存地址都是 32 位数据,所以$LN11@f 表中的每个地址都占用 4 字节)。在计算8$LN11@f 的偏移量的和之后,再跳转到这个和指向的标签——即$LN4@f 处。JMP 指令最终跳转到$LN4@f 的地址。

$LN11@f标签(偏移量)开始的表,叫作转移表jumptable,也叫作转移(输出)表branchtable
当 a 等于 2 的时候,程序分配给 printf()的参数是two。实际上,此时的 switch 语句的分支指令等效于jmp DWORD PTR $LN11@f[ecx*4]。它会进行间接取值的操作,把指针PTR{表达式}所指向的数据读取出来,当作 DWORD 型数据传递给 JMP 指令。在这个程序里,表达式的值为 $LN11@f+ecx*4

此后出现的npad指令属于汇编宏。它的作用是把紧接其后的标签地址向 4 字节(或 16 字节)边界对齐。npad 的地址对齐功能可提高处理器的 IO 读写效率,通过一次操作即可完成内存总线、缓冲内存等设备的数据操作。

开启优化的MSVC

请参考《RE4B》对应章节。此处省略,因为编译出来的代码几乎相同,只是用左移操作来做乘法。

ARM/MIPS

请参考《RE4B》对应章节。

case从句多对一的情况

考虑如下程序:

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
#include <stdio.h>
void f (int a)
{
switch (a)
{
case 1:
case 2:
case 7:
case 10:printf ("1, 2, 7, 10\n");
break;
case 3:
case 4:
case 5:
case 6:printf ("3, 4, 5\n");
break;
case 8:
case 9:
case 20:
case 21:printf ("8 9, 21\n");
break;
case 22:printf ("22\n");
break;
default:printf ("default\n");
break;
}
}

int main ()
{
f(4);
}

一般而言,编译器会通过某种派发机制来降低代码的冗余度。

MSVC

指令清单如下:

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
52
53
54
55
56
57
58
59
60
$SG2798 DB '1, 2, 7, 10', 0aH, 00H
$SG2800 DB '3, 4, 5', 0aH, 00H
$SG2802 DB '8, 9, 21', 0aH, 00H
$SG2804 DB '22', 0aH, 00H
$SG2806 DB 'default', 0aH, 00H

_ a $ = 8
_f PROC
mov eax, DWORD PTR _a$[esp-4]
dec eax
cmp eax, 21
ja SHORT $LN1@f
movzx eax, BYTE PTR $LN10@f[eax]
jmp DWORD PTR $LN11@f[eax*4]
$LN5@f:
mov DWORD PTR _a$[esp-4], OFFSET $SG2798 ; '1, 2, 7, 10'
jmp DWORD PTR __imp__printf
$LN4@f:
mov DWORD PTR _a$[esp-4], OFFSET $SG2800 ; '3, 4, 5'
jmp DWORD PTR __imp__printf
$LN3@f:
mov DWORD PTR _a$[esp-4], OFFSET $SG2802 ; '8, 9, 21'
jmp DWORD PTR __imp__printf
$LN2@f:
mov DWORD PTR _a$[esp-4], OFFSET $SG2804 ; '22'
jmp DWORD PTR __imp__printf
$LN1@f:
mov DWORD PTR _a$[esp-4], OFFSET $SG2806 ; 'default'
jmp DWORD PTR __imp__printf
npad 2 ; align $LN11@f table on 16-byte boundary
$LN11@f:
DD $LN5@f ; print '1, 2, 7, 10'
DD $LN4@f ; print '3, 4, 5'
DD $LN3@f ; print '8, 9, 21'
DD $LN2@f ; print '22'
DD $LN1@f ; print 'default'
$LN10@f:
DB 0 ;a=1
DB 0 ;a=2
DB 1 ;a=3
DB 1 ;a=4
DB 1 ;a=5
DB 1 ;a=6
DB 0 ;a=7
DB 2 ;a=8
DB 2 ;a=9
DB 0 ;a=10
DB 4 ;a=11
DB 4 ;a=12
DB 4 ;a=13
DB 4 ;a=14
DB 4 ;a=15
DB 4 ;a=16
DB 4 ;a=17
DB 4 ;a=18
DB 4 ;a=19
DB 2 ;a=20
DB 2 ;a=21
DB 3 ;a=22
_f ENDP

这个程序用到了两个表:一个是索引表$LN10@f;另一个是转移表$LN11@f。
第 13 行的movzx指令在索引表里查询输入值。
索引表的返回值又分为 0(输入值为 1、2、7、10)、1(输入值为 3、4、5)、2(输入值为 8、9、21)、3(输入值为 22)、4(其他值)这 5 种情况。
程序把索引表的返回值作为关键字,再在第二个转移表里进行查询,以完成相应跳转(第 14 行指令的作用)。
需要注意的是,输入值为 0 的情况没有相应的 case 从句。如果 a=0,则“dec eax”指令会继续进行计算,而$LN10@f 表的查询是从 1 开始的。可见,没有必要为 0 的特例设置单独的表。
在这种双表结构中,索引表采用的是byte型数据,所以双表结构比前面那种单表结构更为紧凑。

Fall-through