Why doesn't Linux randomize the address of the executable code segment?

Question

I've recently been learning about how ASLR (address space randomization) works on Linux. At least on Fedora and Red Hat Enterprise Linux, there are two kinds of executable programs:

• Position Independent Executables (PIEs) receive strong address randomization. Apparently, the location of everything is randomized, separately for each program. Apparently, network-facing daemons ought to be compiled as PIEs (using the -pie -fpie compiler flags), to ensure they receive the full-strength randomization.

• Other executables receive partial address randomization. The executable code segment is not randomized -- it is at a fixed, predictable address that is the same for all Linux systems. In contrast, shared libraries are randomized: they are loaded at a random position that's the same for all such programs on the system.

I think I understand why non-PIE executables have the weaker form of randomization for shared libraries (this is necessary for prelink, which speeds up linking and loading of executables). I also think I understand why non-PIE executables don't have their executable segment randomized at all: it looks like it's because the program must be compiled as a PIE, to be able to randomize the location of the executable code segment.

Still, leaving the location of the executable code segment un-randomized is potentially a security risk (for instance, it makes ROP attacks easier), so it would be good to understand whether it's feasible to provide full randomization for all binaries.

So, is there a reason not to compile everything as PIE? Is there a performance overhead to compiling as PIE? If so, how much is the performance overhead on different architectures, particularly on x86_64, where address randomization is most effective?

---

References:

• How Effective is ASLR on Linux Systems?

• Prelink and address space randomization

• Position Independent Code (PIC) in shared libraries on x64

Answer 1

Although the details greatly vary between architectures, what I say here applies equally well to 32-bit x86, 64-bit x86, but also ARM and PowerPC: faced with the same issues, about all architecture designers have used similar solutions.

---

There are (roughly speaking) four kinds of "accesses", at assembly level, which are relevant to the "position-independent" system: there are function calls (call opcodes) and data accesses, and both may target either an entity within the same object (where an object is a "shared object", i.e. a DLL, or the executable file itself) or within another object. Data accesses to stack variables are not relevant here; I am talking about data accesses to global variables or static constant data (in particular the contents of what appears, at source level, to be literal character strings). In a C++ context, virtual methods are referenced by what is, internally, function pointers in special tables (called "vtables"); for the purposes of this answer, these are data accesses as well, even though a method is code.

The call opcode uses a target address which is relative: it is an offset computed between the current instruction pointer (technically, the first byte after the argument to the call opcode) and the call target address. This means that function calls within the same object can be fully resolved at (static) link time; they don't show up in the dynamic symbol tables, and they are "position-independent". On the other hand, function calls to other objects (cross-DLL calls, or calls from the executable file to a DLL) must go through some indirection which is handled by the dynamic linker. The call opcode must still jump "somewhere", and the dynamic linker wants to dynamically adjust it. The format tries to achieve two characteristics:

• Lazy linking: the call target is looked for and resolved only when it is first used.
• Shared pages: at most as possible, in-memory structures should be kept identical to the corresponding bytes in executable files, to promote sharing across multiple invocations (if two processes load the same DLL, the code should be present only once in RAM) and easier paging (when RAM is tight, a page which is an unmodified copy of a chunk of data in a file can be evicted from physical RAM, since it can be reloaded at will).

Since sharing is on a per-page basis, this means that dynamically altering the call argument (the few bytes after the call opcode) should be avoided. Instead, the compiled code uses a Global Offsets Table (or several -- I simplify things a bit). Basically, the call jumps to a small piece of code which does the actual call, and is subject to modification by the dynamic linker. All such small wrappers, for a given object, are stored together in pages which the dynamic linker will modify; these pages are at a fixed offset from the code, so the argument to call is computed at static link time and needs not be modified from the source file. When the object is first loaded, all the wrappers point to a dynamic linker function which does the linking upon first invocation; that function modifies the wrapper itself to point to the resolved target, for subsequent invocations. The assembly-level juggling is intricate but works well.

Data accesses follow a similar pattern, but they don't have relative addressing. That is, a data access will use an absolute address. That address will be computed within a register, which will then be used for access. The x86 line of CPU can have the absolute address directly as part of the opcode; for RISC architectures, with fixed-size opcodes, the address will be loaded as two or three successive instructions.

In a non-PIE executable file, the target address of a data element is known to the static linker, who can hardcode it directly in the opcode which does the access. In a PIE executable, or in a DLL, this is not possible since the target address is not known before execution (it depends on other objects which will be loaded in RAM, and also on ASLR). Instead, the binary code must use the GOT again. The GOT address is dynamically computed into a base register. On 32-bit x86, the base register is conventionally %ebx and the following code is typical:

    call nextaddress
nextaddress:
    popl %ebx
    addl somefixedvalue, %ebx

The first call simply jumps to the next opcode (so the relative address here is just a zero); since this is a call, it pushes the return address (also that of the popl opcode) on the stack, and the popl extracts it. At that point, %ebx contains the address of popl, so a simple addition modifies that value to point to the start of the GOT. Data accesses can then be done relatively to %ebx.

---

So what is changed by compiling an executable file as PIE ? Actually not much. A "PIE executable" means making the main executable a DLL, and loading it and linking it just like any other DLL. This implies the following:

• Function calls are unmodified.
• Data accesses from code in the main executable, to data elements which also are in the main executable, incur some extra overhead. All other data accesses are unaltered.

The overhead from data accesses is due to the use of a conventional register to point at the GOT: one extra indirection, one register used for this functionality (this impacts register-starved architectures like 32-bit x86), and some extra code to recompute the pointer to the GOT.

However, data accesses are already somewhat "slow", when compared with accesses to local variables, so compiled code already caches such accesses when possible (the variable value is kept in a register and flushed only when needed; and even when flushed, the variable address is also kept in a register). This is made even more so by the fact that global variables are shared between threads, so most application code which uses such global data uses it only in a read-only way (when writes are performed, they are done under the protection of a mutex, and grabbing the mutex incurs a much bigger cost anyway). Most CPU-intensive code will work on registers and stack variables, and won't be impacted by making the code position-independent.

At most, compiling code as PIE will imply a size overhead of about 2% on typical code, with no measurable impact on code efficiency, so that's hardly a problem (I got that figure from discussing with people involved in the development of OpenBSD; the "+2%" was a problem for them in the very specific situation of trying to fit a barebone system on a boot floppy disc).

---

Non-C/C++ code may have trouble with PIE, though. When producing compiled code, the compiler must "know" whether it is for a DLL or for a static executable, to include the code chunks which find the GOT. There won't be many packages in a Linux OS which may incur issues, but Emacs would be a candidate for trouble, with its Lisp dump-and-reload feature.

Note that code in Python, Java, C#/.NET, Ruby... is completely out of scope of all this. PIE is for "traditional" code in C or C++.

Answer 2

One reason why some Linux distributions may be hesitant to compile all executables as Position-Independent Executables (PIE), so the executable code is randomized, is because of concerns about performance. The thing about performance concerns is that sometimes people worry about performance even when it's not an issue. So, it would be nice to have detailed measurements of the actual cost.

Fortunately, the following paper presents some measurements of the cost of compiling executables as PIE:

• Too much PIE is bad for performance. Mathias Payer. Technical Report 766, ETH Zurich, Switzerland, 2012.

The paper analyzed the performance overhead of enabling PIE on a set of CPU-intensive programs (namely, the SPEC CPU2006 benchmarks). Since we expect this class of executables to show the worst performance overheads due to PIE, this gives a conservative, worst-case estimate of the potential performance estimate.

To summarize the paper's main findings:

• On 32-bit x86 architectures, the performance overhead could be substantial: it is an average of about a 10% slowdown, for the SPEC CPU2006 benchmarks (CPU-intensive programs), and up to 25% slowdown or so for a few of the programs.

• On 64-bit x64 architectures, the performance overhead is much smaller: an average slowdown of about 3%, on the CPU-intensive programs. Likely the performance overhead would be even less for many programs that people use (as many programs are not CPU-intensive).

This suggests that enabling PIE for all executables on 64-bit architectures would be a reasonable step for security, and the performance impact is very small. However, enabling PIE for all executables on 32-bit architectures would be too costly.

Answer 3

Fairly obvious why the position-dependent executables aren't randomized.

"Position dependent" simply means that at least some addresses are hardcoded. In particular, this may apply to branch addresses. Moving the base address of the executable segment moves all branch destinations as well.

There are two alternatives for such hardcoded addresses: either replace them by IP-relative addresses (so the CPU can determine the absolute address at runtime), or fix them up at load time (when the base address is known).

You of course need a compiler which can generate such executables.