逆向工程——栈

[TOC]

栈是计算机科学李最重要的且最基础的数据结构之一。
从技术上讲,栈就是CPU寄存器里面的某个指针所指向的一片内存区域。这里所说的某个指针通常位于x86/x64平台的ESP寄存器/RSP寄存器,以及ARM平台的SP寄存器
操作站最常见的指令是PUSHPOP,在 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 的值又与第一个函数的情况相同。所以,相同地址的变量获得的值相同。
总而言之,在运行第二个函数时,栈中的所有值(即内存中的单元)受前一个函数的影响,而获得了前一个函数的变量的值。严格地说,这些地址的值不是随机值,而是可预测的伪随机值。
我们可以在每个函数执行之前清除其开辟的栈空间的数据。不过,即使这是一种技术上可行的方法,但是因为这种方法开销太大、而且必要性很低,所以没有人这样做。

作业

学习笔记