PIE.md

Position Independent Executables Without Dynamic Relocations

Recall that the process of turning source files into executables usually consists of the following steps:

1. A compiler generates assembly code from source code;
2. An assembler turns assembly code into object files;
3. A static linker resolves the interdependency between object files and produces an executable;
4. A dynamic loader resolves the external dependencies of the executable and builds a complete program image.

When the dynamic loader builds the program image, it needs to decide where to map the executable file and the dynamic libraries it depends on. Traditionally, executable files had the luxury of choosing where to map itself, and can assume that it will always be mapped to that location. This simplifies assembly code generation in a number of ways. The resulting executable is called position-dependent because it will not run unless mapped to the assumed position.

However, there are several scenarios that require position-independent executables (PIE), which are programs that will work regardless of their memory location. Most notable:

• Most modern operating systems employ address space layout randomization (ASLR) as a technique for deterring attacks based on specific memory locations. Clearly this requires the executable to support memory relocation.
• The dynamic loader itself is usually loaded into the same address space as the program it is going to process. Since the memory location requested by the executable could collide with that of the dynamic loader, the loader must be prepared that the OS could load it into a different location.

The second point requires further attention. Most PIEs contain a table of relocations which are patches to be applied when the actual memory location becomes known. These patches are usually implemented by the dynamic loader. However, the dynamic loader itself does not have another loader to resolve its own relocations. Therefore, the loader must resolve these patches by itself.

This problem plagues every C library developer. For example the dynamic loader of musl requires several stages of bootstrapping to reach a fully functional state. This is too much hacking and not really elegant.

In this document I will present a way to write position-independent C programs that do not contain a single entry of dynamic relocation. Such programs can be relocated to anywhere in memory, and do not need any patches to fix its memory references.

Our technique boils down to five points:

• Stay within the small code model;
• Use static linking;
• Each object file exports only functions, not variables (all global variables are static);
• Each object file never takes function pointers of external or non-static local functions.
• The initializer of each static global variable should never contain pointers to other static global variables.

This implies that:

• Every global variable must be declared static. They can only be indirectly accessed via getter/setter functions;
• When an object file wishes to pass an external or non-static local function to a function that accepts a function pointer, it must do so by declaring a local static stub function that indirectly calls the target function, and taking the pointer to this local stub.
• The point above assumes that function pointers are only ever used for calling. In some cases function pointers might be compared to determine whether they are the same function. If this is the case the object file providing the function should declare the function as a static local one, and export another function that returns a pointer to this function.
• If a static global variable must refer to other static global variables, leave the address field empty and fill it in via an initialization function.

Examples (AArch64)

# crt.asm
# Compile with as -o crt.o crt.asm

.text
.global _start
.type _start, function
_start:
	mov x29, #0
	mov x30, #0
	mov x0, sp
	and sp, x0, #-16
	b main

/* syscall.h */
#define __NR_exit 93

static inline long syscall1 (long arg1, long number) {
    register long _arg1 __asm__ ("x0") = arg1;
    register long _num __asm__ ("x8") = number;

    __asm__ volatile (
    "svc 0\n"
    : "=r"(_arg1)
    : "0"(_arg1), "r"(_num)
    : "memory", "cc"
    );

    return _arg1;
}

void exit (int status) {
  syscall1 (status, __NR_exit);
}

/* obj1.c
   Compile with gcc -ffreestanding -fPIC -c -o obj1.o obj1.c
 */

#include "syscall.h"

int status = 3;

void main (void) {
    exit (status);
}

Link the object files with ld -pie -o a.out crt.o obj1.o. Then inspect a.out with readelf and objdump. We observe that a relocation of type R_AARCH64_RELATIV is generated.

To fix this, we quality the global variable int status with static:

/* obj1.c
   Compile with gcc -ffreestanding -fPIC -c -o obj1.o obj1.c
 */

#include "syscall.h"

static int status = 3;

void main (void) {
    exit (status);
}

Now the relocation disappears.

As another example, we show the effect of taking addresses of external functions. Again we show two examples. In the first example, obj1.c takes the address of a function from obj2.c. This results in a relocation. In the second example, obj2.c exports a function that returns the address of the function obj1.c wants. This eliminates the relocation.

/* obj1.c
   Compile with gcc -ffreestanding -fPIC -c -o obj1.o obj1.c
 */

#include "syscall.h"

typedef int (*my_func_type) (void);

int some_func (void);
void do_something (my_func_type f);

void main (void) {
    do_something (&some_func);
    exit (0);
}

/* obj2.c
   Compile with gcc -ffreestanding -fPIC -c -o obj2.o obj2.c
 */

typedef int (*my_func_type) (void);

int some_func (void) { return 42; }
void do_something (my_func_type f) { f (); }

Link the object files with ld -pie -o a.out crt.o obj1.o obj2.o. Again a relocation is generated.

To eliminate this relocation, we make obj2.c export the function address rather than obj1.c taking it:

/* obj1.c
   Compile with gcc -ffreestanding -fPIC -c -o obj1.o obj1.c
 */

#include "syscall.h"

typedef int (*my_func_type) (void);

my_func_type get_func (void);
void do_something (my_func_type f);

void main (void) {
    do_something (get_func ());
    exit (0);
}

/* obj2.c
   Compile with gcc -ffreestanding -fPIC -c -o obj2.o obj2.c
 */

typedef int (*my_func_type) (void);

static int some_func (void) { return 42; }
void do_something (my_func_type f) { f (); }

my_func_type get_func (void) { return &some_func; }