数组分配和访问

C语言中的数组是一种将标量数据聚集成更大数据类型的方式。

基本原则

对于数据类型T和整型常数N，声明如下：

T A[N]；

起始位置表示为Xa。它在内存上分配一个L N字节的连续区域，这里L是数据类型T的大小（单位为字节）。其次，它引入了标识符A，可以用A来作为指向数组开头的指针，这个指针的值为Xa。可以用0~N - 1的整数索引来访问该数组元素。数组元素i会被存放在地址为Xa + L i的地方。

指针运算

C语言允许对指针进行运算，计算出的值会根据该指针引用的数据类型大小进行伸缩。

其中，xE是数组的起始地址。注意，指针运算时，若最终结果为指针，则指针的值会根据引用的数据类型进行拉伸。若最终结果为数值，则结果会被压缩，如最后一行所示，算出的结果不是4i，是4i/4=i。（两个地址之差除以该数据类型的大小）

其他数组

对于多维数组，以二维数组为例，如int A[5][3],实际上等价于：typedef int row3_t[3]; row3_t A[5];

此外，数组元素在内存中存储时以“行优先”的顺序排列，以上面的A为例，先存A[0][0],随后A[0][1]，A[0][2]…..,A[1][0],A[1][1]….,A[4][2]

某些情况下，数组声明时无需显示地标明维度，传统情况下，声明数组时，至少需要表明列数，比如 int A[][5]。

而

int var_ele(long n,int A[n][n],long i,long j)
{
　　return A[i][j];
}

这种情况下，声明数组A时列维度用了表达式n来表示，它有一个限制，就是参数n排在参数A之前。

数据结构

C语言提供两种将不同类型的对象组合到一起创建数据类型的机制：

结构（structure），用关键字struct表明，将多个对象集合到一个单位中。
联合（union），用关键字union表明，云霄用几种不同的类型来引用一个对象。

结构

struct的所有组成部分都存放在内存中一段连续的区域内，指向结构的指针就是结构第一个字节的地址。编译器维护关于每个结构类型的信息，指示每个字段的字节偏移，以这些偏移作为内存引用指令中的偏移，从而产生对结构元素的引用。

结构的各个字段的选取完全是在编译时处理的，机器代码不包含关于字段申明或字段名字的信息。

联合

union则是使用不同的字段来引用相同的内存块。总的大小等于最大字段的大小。当知道一种数据结构中的两种不同字段的使用是互斥的，将这两个字段声明为union的一部分，就能减少分配空间的总量。

数据对齐

计算机要求某种类型对象的地址必须是某个值K（通常是2、4、8）的倍数。这种对齐限制简化了形成处理器和内存系统之间接口的硬件设计。

比如一次取4个字节，若有个int存在0x01-0x04，则一次就能取出，若存在0x03-0x06,则需要分两次才能取到(第一次0x01-0x04,第二次0x05-0x08)，这样会降低CPU效率，更何况还有像short,char之类的不是4个字节的数据。因此，编译器会对数据进行强制对齐。

对齐规则：

任何K字节的基本对象的地址必须是K的倍数
在结构末尾根据需要会做一些填充，使其一旦被拓展为数组时可以满足条件1

例子如下：

struct S1
{
　　int i;
　　char c;
　　int j;
};

假设编译器用最小的9字节分配，那么i起始地址偏移量为0，占用4个字节；c起始地址偏移量为4，占用1个字节；j起始地址偏移量为5，占用4个字节。

如果这样，j不满足4字节对齐要求，所以为了满足条件1，编译器会在c后面填充3个字节，使j起始地址偏移量为8，另外j占用4个字节，所以S1一共占用12个字节。

另一个例子：

struct S2
{
　　int i;
　　int j;
　　char c;
};

i起始地址偏移量为0，占用4个字节，j起始地址偏移量为4，占用4个字节，c起始地址偏移量为8，占用1个字节，所以S2一共占用9个字节。

看一下是否满足条件2：一旦声明了 struct S2[2]，第二个结构体的第一个元素i的起始地址偏移量为9，不满足条件2，因此结构体需在c后面填充3个字节，这样第二个结构体的第一个元素i的起始地址偏移量变为12，满足条件2，综上S2一共占用12个字节，最后3个字节是浪费的空间。

控制与数据

（这里我们开始接触到Pwn的一些内容，但是真正的入门还要一段时间）

指针

指针和其映射到机器代码的一些原则：

每个指针都对应一个类型。
每个指针都有一个值。这个值是某个指定类型对象的地址。特殊的NULL(0)值表示该指针没有指向任何地方。
指针用‘&’运算符创建。
*操作符用于间接引用指针。其结果是一个值，它的类型与该指针的类型一致。
将指针从一种类型强制转换为另一种类型，只改变它的类型，而不改变它的值。
指针的优先级较低：

char (*p)[3]，括号中优先级最高，所以p是一个指针，指向一个3个元素的char数组。

char p[3]，因为指针优先级较低，所以与char结合，p代表一个3个元素的数组，每个元素都是一个char
指针也可以指向函数。

缓冲区溢出

C对于数组引用不进行任何边界检查，而且局部变量和状态信息（例如保存的寄存器值和返回地址）都存放在栈中。这两种情况结合到一起就能导致严重的程序错误，对越界的数组元素的写操作会破坏存储在栈中的状态信息。当程序使用这个被破坏的状态，试图重新加载寄存器或执行ret指令时，就会出现很严重的错误。

一种特别常见的状态破坏称为缓冲区溢出。通常，在栈中分配某个字符数来保存一个字符串，但是字符串的长度超出了为数组分配的空间。

例子如下：

char *gets(char *s)
{
    int c;
    char *dest  = s;
    while ((c = getchar()) != '\n' && c != EOF)
        *dest++ = c;
    if (c == EOF && dest == s)
        return NULL;
    *dest++ = '\0';
    return s;
}

void echo()
{
    char buf[8];
    gets(buf);
    puts(buf);
}

gets函数从标准输入读入一行，在遇到一个回车换行字符或某个错误情况时停止。它将这个字符串复制到参数s指明的位置，并在字符串结尾加上null字符。在函数echo中，我们使用了gets，这个函数只是简单的从标准输入中读入一行，再把它送回标准输出。

汇编如下：

echo:
	subq	$24, %rsp
	movq	%rsp, %rdi
	call	gets
	movq	%rsp, %rdi
	call	puts
	addq	$24, %rsp
	ret

该程序把栈指针减去了24（第2行），在栈上分配了24个字节。字符数组buf位于栈顶，可以看到，%rsp被复制到%rdi作为调用gets和puts的参数。这个调用的参数和存储的返回指针之间的16字节是未被使用的。只要用户输入不超过7个字符，gets返回的字符串（包括结尾的null）就能够放进为buf分配的空间里。不过，长一些的字符串就会导致gets覆盖栈上存储的某些信息。随着字符串变长，下面的信息会被破坏。

输入的字符数量	附加的被破坏的状态
0~7	无
9~23	未被使用的栈空间
24~31	返回地址
32+	caller中保存的状态

字符串到23个字符之前都没有严重后果，但是超过以后，返回指针的值以及更多可能的保存状态会被破坏。如果存储的返回地址的值被破坏了，那么ret指令（第8行）会导致程序跳转到一个完全意想不到的位置。如果只看C代码，根本看不出会有上面的行为。

更好一点是使用fgets函数。它包括一个参数，限制待读入的最大字节数。

但很多常用的库函数，包括strcpy、strcat和sprintf都有一个属性——不需要告诉它们目标缓冲区的大小，就产生一个字节序列.这样的情况就会导致缓冲区溢出漏洞。

对抗缓冲区溢出攻击

1.栈随机化，即程序开始时，在栈上随机分配一段0-n字节间的随机大小的空间(可用alloca实现)，程序不使用这段空间，这样，通过浪费一段空间，可以使程序每次执行时后续的栈位置发生变化。然而这种方式仍有着被破解的可能，攻击者可以在攻击代码前放许多nop指令，这些指令唯一的作用就是指向下一条指令，假设本来栈随机化后栈空间地址的变化范围达到了223个字节，本来要精确地将返回地址改到攻击代码入口的对应的地址需要“精确投放”，即要尝试枚举223种可能，现在攻击代码加上这一堆nop指令，假设达到了28=256个字节，代表只要返回地址指向这些指令中的任何一条，都会导致最后进入攻击代码，因此只要枚举215种可能就行了，因此栈随机化不大保险。

2.栈破坏检测，基本思路是在栈的局部缓冲区插入一个哨兵值，它在程序每次运行时随机产生(比如可以从内存中某个地方取得)，在函数返回以及恢复寄存器的值之前，程序会先检测哨兵值是否被改变，若改变了则程序异常终止。最近的GCC版本会自动插入溢出检测，所以之前的例子进行汇编时，需要用“-fno-stack-protector”来阻止GCC产生这种代码。

3.限制可执行代码区域，即限制只有保存编译器产生的代码的那部分内存才是可执行的，其他内存区域被限制为只允许读和写。

（以后的Pwn学习会介绍以上保护，并学习如何攻击它们。）

变长栈帧

很多函数，编译器能够预先确定需要为栈帧分配多少空间。但是有些函数，需要的局部存储是变长的。

例子如下：

long vframe(long n,long idx,long *q){
    long i;
    long *p[n];
    for (i=1; i < n; i++)
        p[i] = q;
    return *p[idx];
}

该函数声明了n个指针的局部数组p，这里n由第一个参数给出。这要求在栈上分配8n个字节，这里n的值每次调用该函数时都会不同。因此编译器无法确定要给该函数的栈帧分配多少空间。此外，该程序还产生一个对局部变量i的地址引用，因此该变量必须存储在栈中。在执行过程中，程序必须能够访问局部变量i和数组p中的元素。返回时，该函数必须释放这个栈帧，并将栈指针设置为存储返回地址的位置。

x86-64代码使用寄存器%rbp作为帧指针（有时称为基指针（base pointer），这就是%rbp中bp两个字母的由来）。当使用帧指针时，栈帧的组织结构如图：

可以看到代码必须把%rbp之前的值保存到栈中，因为它是一个被调用者保存寄存器。然后在函数的整个执行过程中，都使得%rbp指向那个时刻栈的位置，然后用固定长度的局部变量（例如i）相对于%rbp的偏移量来引用它们。

汇编代码如下：

vframe:
	pushq	%rbp
	movq	%rsp, %rbp
	subq	$16, %rsp
	leaq	22(,%rdi,8), %rax
	andq	$-16, %rax
	subq	%rax, %rsp
	leaq	7(%rsp), %rax
	shrq	$3, %rax
	leap	0(,%rax,8), %r8
	movq	%r8, %rcx
.L3:
	movq	%rdx, (%rcx,%rax,8)
	addq	$1, %rax
	movq	%rax, -8(%rbp)
.L2:
	movq	-8(%rbp), %rax
	cmpq	%rdi, %rax
	jl	.L3
	leave
	ret

函数的开始，代码建立栈帧，并为数组p分配空间。首先把%rbp的当前值压入栈中，将%rbp设置为指向当前栈位置（第2-3行）。然后，在栈上分配16个字节，其中前八个字节是未被使用的。接着，为数组p分配空间（第5-11行）。当程序到11行时，已经在栈上分配8n个字节，并在伊分配的区域内放置好数组p，至少有8n个字节可供其使用。

第13行表明数组元素p[i]被设置为q。该指令用寄存器%rcx中的值作为p的起始地址。第15和17行，i的地址是引用-8（%rbp），也就是相对于帧指针偏移量为-8的地方。

在函数结尾，leave指令将帧指针恢复到它之前的值（第20行）。这条指令不需要参数，等价于执行下面两条指令：

1 2	movq %rbq, %rsp popq %rbp

也就是，首先把栈指针设置为保存%rbp值的位置，然后把该值从栈中弹出到%rbp。这个指令组合具有释放整个栈帧的效果。