逆向工程——栈

Posted on Edited on In

[TOC]

栈

栈是计算机科学李最重要的且最基础的数据结构之一。
从技术上讲，栈就是CPU寄存器里面的某个指针所指向的一片内存区域。这里所说的某个指针通常位于x86/x64平台的ESP寄存器/RSP寄存器，以及ARM平台的SP寄存器。
操作站最常见的指令是PUSH和POP，在 x86 和 ARM Thumb 模式的指令集里都有这两条指令。
PUSH指令会对ESP/RSP/SP寄存器的值进行减法运算，使之减去4(32位）或8(64位），然后将操作数写到上述寄存器里的指针所指向的内存中。
POP指令是PUSH的逆操作：他先从栈指针（Stack Pionter,上面三个寄存器之一）指向的内存中读取数据，用以备用（通常是写到其他寄存器里面），然后再将栈指针的数值加上4或8.
在分配栈的空间之后，栈指针，即Stack Pointer所指向的地址是栈的底部。PUSH将减少栈指针的数值，而POP会增加它的数值。栈的“底”实际上使用的是整个栈的最低地址，即是整个栈的启始内存地址。
ARM的栈分为递增栈和递减栈。递减栈（descending stack)的首地址是栈的最高地址，栈向低地址增长，栈指针的值随栈的增长而减少，如STMFA/LMDFA、STMFD/LDMFD、STMED、LDMEA等指令，都是递增栈的操作指令。

栈的用途

保存函数结束时的返回地址

x86

当程序使用call指令调用其他函数时，call指令结束后的返回地址将被保存到栈里，在call所调用的函数结束之后，程序将执行无条件跳转指令，跳转到这个返回地址。
call指令等价于“PUSH返回地址”和“JMP函数地址”的指令对
被调用函数里的RET指令，会从栈中读取返回地址，然后跳转到这个这个地址，就相当于“POP返回地址”+“JMP返回地址”指令。
栈是有限的，溢出它很容易。直接使用无线递归，栈就会满：

1
2
3
4
void f()
{
	f();
}

如果使用MSVC2008编译上面的问题程序，就会得到报告：
​
​ c:\tmp6>cl ss.cpp /Fass.asm
​ Microsoft (R) 32-bit C/C++ Optimizing Compiler Version 15.00.21022.08 for 80x86
​ Copyright (C) Microsoft Corporation. All rights reserved.
​ ss.cpp
​ c:\tmp6\ss.cpp(4) : warning C4717:’f’ : recursive on all control paths. Function will cause runtime stack overflow
但它还是会生成汇编文件

1
2
3
4
5
6
7
8
9
10
11
12
?f@@YAXXZ PROC              ; f
; File c:\tmp6\ss.cpp
; Line 2
	push ebp
	mov ebp, esp
; Line 3
	call ?f@@YAXXZ         ; f
; Line 4
	pop ebp
	ret 0
?f@@YAXXZ ENDP                 ; f

有趣的是,如果打开优化选项“/Ox”,生成的程序反而不会出现栈溢出的问题,而且还会运行得很“好”

1
2
3
4
5
6
7
?f@@YAXXZ PROC                    ; f
; File c:\tmp6\ss.cpp
; Line 2
$LL3@f:
; Line 3
	jmp SHORT $LL3@f
?f@@YAXXZ ENDP                    ; f

无论是否开启优化选项,GCC 4.4.1 生成的代码都和 MSVC 生成的代码相似,只是 GCC 不会发布任何警告。

ARM

ARM程序也使用栈保存返回地址，只是略有不同。之前课程中我们看到“hello world”程序的返回地址保存在LR寄存器里。但是如果程序还会继续调用其它函数，就需要在调用函数之前保存LR寄存器里面的值。通常函数会在启动过程中（序言处）保存LR寄存器的值。我们同通常在函数序言中看到PUSH R4-R7,LR,并在尾声处看到POP R4-R7,PC。这些指令会对函数自身将要用到的寄存器进行保护，把它们的值存放到栈中————当然，这其中也包括LR寄存器
如果一个函数不调用其它函数，它就像书上枝杈末端的叶子一样，这种函数被叫做叶函数（leaf function）。叶函数的特点是：它不必保存LR寄存器的值。如果叶函数的代码短到用不到几个寄存器,那么它也可能根本不会使用数据栈。所以调用叶函数的时候确实可能不会涉及栈操作。由于这种代码不在外部内存RAM进行与栈有关的操作,所以它的运行速度有可能超过x86 系统，在没有分配栈或者不可能用栈的时候,这类函数就会显现出“寸有所长”的优势。

参数的传递

在x86 平台的程序中,最常用的参数传递约定是cdecl 。以cdecl方式处理参数,其上下文大体是这个样子:
​
​ push arg3
​ push arg2
​ push arg1
​ call f
​ add esp,12 4*3=12
被调用方函数（Callee functiongs)通过栈指针获取其所需的参数。
在运行f()函数之前，传递给他的参数将以以下格式存储到内存里：

ESP 返回地址
ESP+4 arg1,它在IDA里面记为arg0
ESP+8 arg2,它在IDA里面记为arg4
ESP+0xC arg4,它在IDA里面记为arg8

相关的调用约定会在之后的课件中介绍，需要注意的是，程序员可以使用栈来传递参数，也可以不使用栈来传递参数。参数处理方面并没有相关的硬性规定。
例如，程序员可以在堆（heap）中分配内存并用之传递参数。在堆中放入参数之后,可以利用EAX寄存器为函数传递参数。这种做法确实行得通。只是在x86 系统和ARM系统上,使用栈处理参数已经成为了约定俗成的习惯,而且它的确十分方便。另外,被调用方函数并不知晓外部向它传递了多少个参数。如果函数可处理的参数数量可变,它就需
要说明符(多数以%号开头)进行格式化说明、明确参数信息。拿我们常见的 printf()函数来说:printf("%d %d %d", 1234);，这个命令不仅会让 printf()显示 1234,而且还会让它显示数据栈内 1234 之后的两个地址的随机数。
由此可知,声明 main()函数的方法并不是那么重要。我们可以将之声明为 main(),main(int argc, char
*argv[])或 main(int argc, char *argv[], char *envp[])。
实际上 CRT 中调用 main()的指令大体上是下面这个样子的：

1
2
3
4
5
push envp
push argv
push argc
call main
-

即使我们没有在程序里声明 main()函数便用哪些参数,程序还可以照常运行;参数依旧保存在栈里,只是不会被主函数调用罢了。如果将 main()函数声明为main(int argc,char*argv[]),程序就能够访问到前两个参数,但仍然无法使用第三个参数。除此以外,也可以声明为 main( int argc),主函数同样可以运行。

存储局部变量

通过向栈底调整栈指针的方法，函数即可在数据栈里分配出一片可用于存储局部变量的内存空间。可见，无论函数声明了多少个变量，都不影响它分配栈空间的速度。
虽然可以在栈外的任何地方存储局部变量，但是用数据栈来存储局部变量已经是一种约定俗成的习惯了。

x86：alloca()函数

alloca（0函数直接使用栈来分配内存，除此之外，它与malloc()函数没有显著的区别.
函数尾声的代码还会还原ESP的值，把数据栈还原为函数启动之前的状态，直接抛弃由alloca（）函数分配的内存，所以程序不需要特地使用free函数来释放由这个函数申请的内存。
alloca()函数将以所需数据空间的大小为幅度、向栈底调整ESP的值，此时ESP就成了新的数据空间的指针：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#ifdef __GNUC__
#include <alloca.h> // GCC
#else
#include <malloc.h> // MSVC
#endif
#include <stdio.h>
void f()
{
char *buf=(char*)alloca (600);
#ifdef __GNUC__
snprintf (buf, 600, "hi! %d, %d, %d\n", 1, 2, 3); // GCC
#else
_snprintf (buf, 600, "hi! %d, %d, %d\n", 1, 2, 3); // MSVC
#endif
puts (buf);
}

snprint（）函数的功能和printf（0函数的功能差不多。prinf函数将输出结果输出到stdout（也就是终端terminal或console一类的输出设备上），而snprintf（）则将结果输出到buf数组（人工设定的缓冲区）、我们需要通过puts（）函数才能将buf的内容输出到stdout。当然printf（）函数就足以完成_snprintf（）和1puts（）两个函数的功能。主要为了演示缓冲区的用法，所以才可以将它拆分为两个函数。
MSVC
现在使用 MSVC 2010 编译上面的代码,得到的代码段如下所示。
指令清单 5.1 MSVC 2010

1
2
3
4
5
6
7
8
9
10
11
12
13
...
	mov eax,600      ;00000258H
	call __alloca_probe_16
	mov esi,esp
	push 3
	push 2
	push 1
	push SFFSET $SG2672
	push 600          ;00000258H
	push esi
	call _puts
	add esp,28        ;000001cH
...

由于alloca()函数是编译器固有函数，并非常规函数的缘故，这个程序并没有使用栈，而是使用EAX寄存器来传递alloca（）函数唯一的参数。在调用alloca()寒素之后，ESP将指向600字节大小的内存区域，用以存储数组buf。
GCC Intel语体
在编译上述代码时，GCC 4.4.1 同样不会调用外部函数
指令清单 5.2 GCC 4.7.3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
.LC0:
	.string "hi!%d,%d,%d\n"
f:
	pushebp
	mov ebp,esp
	push ebx
	sub esp,660
	lea ebx,[esp+39]
	and ebx,-16               ;align pointer by 16-bit border
	mov DWORD PTR [esp],ebx   ;s
	mov DWORD PTR [esp+20],3
	mov DWORD PTR [esp+16],2
	mov DWORD PTR [esp+12],1
	mov DWORD PTR [esp+8],OFFSET FLAT:.LCO ;"hi! %d,%d,%d\n"
	mov DWORD PTR [esp+4],600  ;maxlen
	call _snprintf
	mov DWORD PTR [esp],ebx    ;s
	call puts
	mov ebx,DWORD PTR [esp-4]
	leave
	ret

GCC+ AT&T语体
我们来看看AT&T语体的指令

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
.LC0:
	.string "hi! %d, %d, %d\n"
f:
	push1 %ebp
	mov1 %esp, %ebp
	push1 %ebx
	sub1 $660, %esp
	lea1 39(%esp), %ebx
	and1 $-16, %ebx
	mov1 %ebx, (%esp)
	mov1 $3, 20(%esp)
	mov1 $2, 16(%esp)
	mov1 $1, 12(%esp)
	mov1 $.LC0, 8(%esp)
	mov1 $600, 4(%esp)
	call _snprintf
	mov1 %ebx, (%esp)
	call puts
	mov1 -4(%ebp), %ebx
	leave
	ret

它与Intel语体的代码没有实质区别
其中，movl $3, 20(%esp)对应 Intel 语体的mov DWORD PTR [esp+20], 3指令。在以“寄存器+偏移量”的方式寻址时,AT&T 语体将这个寻址表达式显示为偏移量(%寄存器)。

(Windows)SEH 结构化异常处理

如果程序里存在 SEH 记录,那么相应记录会保存在栈里。

典型的栈的内存存储格式

在 32 位系统中,在程序调用函数之后、执行它的第一条指令之前,栈在内存中的存储格式一般如下表所示。

… …
ESP-0xC 第 2 个局部变量,在 IDA 里记为 var_8
ESP-8 第 1 个局部变量,在 IDA 里记为 var_4
ESP-4 保存的 EBP 值
ESP 返回地址
ESP+4 arg1, 在 IDA 里记为 arg_0
ESP+8 arg2, 在 IDA 里记为 arg_4
ESP+0xC arg3, 在 IDA 里记为 arg_8
… …

栈的噪音

本书会经常使用噪音、脏数据这些词汇。它们怎么产生的呢?待函数退出以后,原有栈空间里
的局部变量不会被自动清除。它们就成为了栈的“噪音”、
“脏数据”。我们来看下面这段代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <stdio.h>
void f1()
{
	int a=1, b=2, c=3;
}

void f2()
{
	int a,b,c;
	printf("%d,%d,%d\n",a,b,c);
}
int main()
{
	f1();
	f2();
}

使用MSVC2010编译后可以得到如下所示的代码
指令清单 5.4 Non-optimizing MSVC 2010：

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
$SG2752 DB '%d, %d, %d', 0aH, 00H
_c$ = -12         ;size=4
-b$ = -8          ;size=4
-a$ = -4          ;size=4
_f1 PROC
	push ebp
	mov ebp,esp
	sub esp,12
	mov DWORD PTR _a$[ebp],1
	mov DWORD PTR _b$[ebp],2
	mov DWORD PTR _c$[ebp],3
	mov esp,ebp
	pop ebp
	ret 0
_f1 ENDP
	
_c$ = -12            ;size=4
_b$ = -8             ;size=4
_a$ = -4             ;size=4
_f2 PROC
	push ebp
	mov ebp,esp
	sub esp,12
	mov eax,DWORD PTR _c$[ebp]
	push eax
	mov ecx,DWORD PTR _c$[ebp]
	push ecx
	mov edx,DWORD PTR _c$[ebp]
	push edx
	push OFFSET $SG2752   ;"%d,%d,%d"
	call DWORD PTR __imp__printf
	add esp,16
	mov esp,ebp
	pop ebp
	ret 0
_f2 ENDP

main PROC
	push ebp
	mov ebp,esp
	call _f1
	call _f2
	xor eax,eax
	pop ebp
	ret 0
_main ENDP

编译器会给出提示：

1
2
3
4
5
6
7
8
9
10
11
c:\Polygon\c>cl st.c /Fast.asm /MD
Microsoft (R) 32-bit C/C++ Optimizing Compiler Version 16.00.40219.01 for 80x86
Copyright (C) Microsoft Corporation. All rights reserved.
st.c
c:\polygon\c\st.c(11) : warning C4700: uninitialized local variable 'c' used
c:\polygon\c\st.c(11) : warning C4700: uninitialized local variable 'b' used
c:\polygon\c\st.c(11) : warning C4700: uninitialized local variable 'a' used
Microsoft (R) Incremental Linker Version 10.00.40219.01
Copyright (C) Microsoft Corporation. All rights reserved.
/out:st.exe
st.obj

可是运行它的结果却是:

1
2
c:\Polygon\c>st
1, 2, 3

f2()函数的三个变量的地址,和 f1()函数的三个变量的地址相同。因为没有对这个空间进行重新赋值,所以那三个变量会因为地址相同的原因获得前三个变量的值。
在这个特例里,第二个函数在第一个函数之后执行,而第二个函数变量的地址和 SP 的值又与第一个函数的情况相同。所以,相同地址的变量获得的值相同。
总而言之,在运行第二个函数时,栈中的所有值(即内存中的单元)受前一个函数的影响,而获得了前一个函数的变量的值。严格地说,这些地址的值不是随机值,而是可预测的伪随机值。
我们可以在每个函数执行之前清除其开辟的栈空间的数据。不过,即使这是一种技术上可行的方法,但是因为这种方法开销太大、而且必要性很低,所以没有人这样做。

作业

学习笔记