逆向工程——switch()

Posted on Edited on In

[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