Lecture 08: Linking

和学过的pwn的一部分重合了，所以只记录新的知识。

符号和符号表

符号表.symtab中的每个条目具有以下格式：

1
2
3
4
5
6
7
8
9

typedef strcut{
    int name;
    char type:4,
    	 binding:4;
    char reserved;
    short section;
    long value;
    long size;
}Elf64_Symbol;

• **name：**保存符号的名字，是.strtab的字节偏移量
• **type：**说明该符号的类型，是函数、变量还是数据节等等
• **binding：**说明该符号是局部还是全局的
• **value：**对于可重定位目标文件而言，是定义该符号的节到该符号的偏移量（比如函数就是在.text中，初始化的变量在.data，未初始化的变量在.bss中）；对于可执行目标文件而言，是绝对运行形式地址。
• **size：**是符号的值的字节数目。（通过value和size就能获得该符号的值）
• **section：**说明该符号保存在哪个节中，是节头部表中的偏移量。

对于像Linux LD这样的静态链接器（Static Linker），是以一组可重定位目标文件和命令参数为输入，生成一个完全链接的、可以加载和运行的可执行目标文件作为输出。为了构造可执行目标文件，链接器有两个任务：

• **符号解析（Symbol Resolution）：**将每个符号引用和一个符号定义关联起来
• **重定位（Relocation）：编译器和汇编器生成从地址0开始的代码和数据节，链接器会对代码、数据节、符号分配内存地址，然后使用汇编器产生的重定位条目（Relocation Entry）**的指令，修改所有对这些符号的引用，使得它们指向正确的内存位置。

符号解析

链接器符号解析是将每个符号引用与输入的所有可重定位目标文件的符号表中的一个确定的符号定义关联起来。

编译器会向汇编器输出每个全局符号是强（Strong）还是弱（Weak），而汇编器会把这些信息隐式编码在可重定位目标文件的符号表中。函数和已初始化的全局符号是强符号，未初始化的全局符号是弱符号。

然后链接器通过以下规则来处理在多个可重定位目标文件中重复定义的全局符号：

1. 不允许有多个同名的强符号，如果存在，则链接器会报错
2. 如果有一个强符号和多个弱符号同名，则符号选择强符号的定义
3. 如果有多个弱符号同名，符号就随机选择一个弱符号的定义

关于这部分，书上举了很多例子便于理解。

判断符号采用哪种定义：

• 在各个文件中确定同名全局符号的强弱，其中符号和初始化的全局符号为强符号，未初始化的全局符号为弱符号

静态库的链接与解析引用

在符号解析阶段，链接器会维护一个可重定位目标文件的集合E，一个引用了但是还未定义的符号集合U，一个前面输入文件中已经定义的符号集合D，然后在命令行中从左到右依次扫描可重定位目标文件和存档文件：

• 如果输入文件是可重定位目标文件，链接器就将其添加到E中，然后根据该文件的符号表来修改U和D，然后继续下一个输入文件。
• 如果输入文件是存档文件，则链接器会依次扫描存档文件中的成员m，如果m定义了U中的一个符号，则将m添加到E中，然后根据m的符号表来修改U和D。最后没有包含在E中的成员就会被丢弃，然后继续下一个输入文件。
• 如果链接器扫描完毕，U中还存在没有确定定义的符号，则链接器会报错并终止，否则链接器会合并和重定位E中的目标文件，得到可执行目标文件。

根据以上过程的描述，我们需要小心命令行上库和目标文件的顺序，要保证前面输入文件中未解析的符号能在后续输入文件中进行解析，否则会出现链接错误，一般是将库放在后面，如果库之间存在依赖，也要注意库之间的顺序，并且为了满足依赖关系，可以在命令行上重复库。

重定位

当链接器完成符号解析时，就能确定在多个目标文件中重定义的全局符号的解析，以及获得静态库中需要的目标模块，此时所有符号引用都能和一个符号定义关联起来了。此时开始重定位步骤，包括：

• 链接器将所有目标模块中相同类型的节合并成同一类型的新的聚合节，比如将所有输入目标模块的.data节聚合成可执行文件中的.data节，其他节也如此操作。
• 此时链接器知道代码节和数据节的确切大小，就将运行时内存地址赋给新的聚合节，以及输入模块定义的每个符号。此时程序的每条指令和全局变量都有唯一的运行时内存地址了。
• 记得之前可重定位目标文件中，由于编译器和汇编器并不知道符号的运行时内存地址，所以使用一个占位符来设置符号引用的地址，而当前链接器已为符号分配了内存地址，所以链接器需要修改代码节和数据节中对每个符号的引用，使它们指向正确的运行时内存地址。

当汇编器生成目标模块时，它无法确定数据和代码最终会放在内存的什么位置，也无法确定该模块引用外部定义的函数和全局变量的位置，所以汇编器先用占位符来占领位置，然后对地址未知的符号产生一个重定位条目（Relocation Entry），代码的重定位条目会保存在.rel.text节中，已初始化数据的重定位条目会保存在rel.data.节中。

1
2
3
4
5
6

typedef struct{
    long offset;
    long type:32;
    	 symbol:32;
    long addend;
}Elf_Rela;

其中，offset表示要修改符号引用的内存地址，type表示重定位的类型，symbol是符号表的索引值，表示引用的符号，可以通过该符号获得真实的内存地址，addend是一个有符号常数，有些重定位需要使用这个参数来修改引用位置。

1
2
3
4
5
6
7
8
9

int sum(int *a, int n);

int array[2] = {1, 2};

int main()
{
	int val = sum(array, 2);
	return val;
}

我们可以通过objdump -dx main.o来得到main.o的反汇编代码，可以发现该函数中无法确定array和其他目标模块中定义的函数sum在内存中的地址，所以会对array和sum产生重定位条目

1
2
3
4
5
6
7
8

	sub	$0x8,%rsp
	mov $0x2,%esi
	mov	$0x0,%edi
a:R_X86_64_32 array
	callq 13<main+0x13>
f:R_X86_64_PC32 sum-0x4
	add	$0x8,%rsp
	retq

• R_X86_64_PC32

该重定位条目主要用来产生32位PC相对地址的引用，即函数调用时的重定位。

其中call指令的开始地址处于节偏移0xe处，然后有一个字节的操作码e8，后面跟着的就是函数sum的32位PC相对引用的占位符，所以链接器修改的位置在当前节偏移0xf处。该重定位条目r包含以下字段

1
2
3
4

r.offset = 0xf //该值是当前节的偏移量，定位到重定位的位置
r.symbol = sum //保存的是要重定位的符号
r.type = R_X86_64_PC32 //保存的是重定位的类型
r.addend = -4 

当前链接器已经确定了各个节和符号的的内存地址，该代码处于.text节中，则我们可以通过.text和r.offset的值来确定占位符的内存地址

1
2
3
4

ADDR(s) = ADDR(.text) = 0x4004d0
refaddr = ADDR(s) + r.offset
        = 0x4004d0 + 0xf
        = 0x4004df

然后我们需要计算占位符的内容，根据相对地址的计算方法，可以知道占位符的内容是目标地址减去当前PC的下一条指令的地址。可以通过ADDR(r.symbol)来获得目标地址，即sum函数的地址，可以通过refaddr减去4字节来获得下一指令的地址，然后可以通过以下计算公式来计算占位符内容

1
2
3
4
5

refptr = s + r.offset //占位符的指针
ADDR(r.symbol) = ADDR(sum) = 0x4004e8
*refptr = (unsigned)(ADDR(s.symbol) + r.addend - refaddr)
        = (unsigned)(0x4004e8 + (-4) - 0x4004df)
        = (unsigned) 0x5

• R_X86_64_32

该重定位条目主要用来产生32位绝对地址的引用，即数组的重定位。

使用数组array的指令处于.text节偏移0x9处，后面有一个字节的操作码，后面跟着的就是数组array的32位绝对地址的引用的占位符，所以链接器修改的位置在当前节偏移0xa处。该重定位条目r包含以下字段

1
2
3
4

r.offset = 0xa
r.symbol = array
r.type = R_X86_64_32
r.added = 0

我们可以通过r.symbol的地址来确定数组array的内存地址，然后直接将该内存地址保存到占位符中，即

1
2
3

refptr = s + r.offset //占位符的指针
*refptr = (unsigned)(ADDR(r.symbol) + r.addend)
        = (unsigned) 0x601018 

库打桩

Linux链接器支持**库打桩（Library Interpositioning）**技术，允许你截获对共享库函数的调用，替换成自己的代码。基本思想为：创建一个与共享库函数相同函数原型的包装函数，使得系统调用包装函数，而不是调用目标函数。