逆向工程——栈[三]

栈

栈是计算机科学里最重要的且最基础的数据结构之一。 从技术上讲，栈就是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返回地址”指令。 栈是有限的，溢出它很容易。直接使用无线递归，栈就会满：

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

但它还是会生成汇编文件

?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”,生成的程序反而不会出现栈溢出的问题,而且还会运行得很“好”

?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()函数之前，传递给他的参数将以以下格式存储到内存里：

相关的调用约定会在之后的课件中介绍，需要注意的是，程序员可以使用栈来传递参数，也可以不使用栈来传递参数。参数处理方面并没有相关的硬性规定。 例如，程序员可以在堆（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()的指令大体上是下面这个样子的：

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就成了新的数据空间的指针：

#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

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

.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语体的指令

.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 位系统中,在程序调用函数之后、执行它的第一条指令之前,栈在内存中的存储格式一般如下表所示。

栈的噪音

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

#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：

$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

编译器会给出提示：

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

可是运行它的结果却是:

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

f2()函数的三个变量的地址,和 f1()函数的三个变量的地址相同。因为没有对这个空间进行重新赋值,所以那三个变量会因为地址相同的原因获得前三个变量的值。

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