Where Address-Space Randomisation Gets Its Entropy

Randomisation is a defence measured in bits. A region placed at a random offset from a range of 2^n possible positions requires n bits of guessing to locate, and every address in that region inherits the same n bits. When an attack needs a specific address, the cost of the attack is set by the smallest of those n values, not the largest. That is why the interesting questions about randomisation are not whether it exists but which regions get how many bits, and where a leak can convert an n-bit guess into a known address.

The regions and their ranges

On x86-64 Linux, several mappings are randomised independently. The executable itself, when built position-independent, is loaded at a random base in the low address space. Shared libraries and the heap are placed relative to a random mmap base. The stack has its own random offset near the top of the user range. The vDSO and the environment block move with them.

The granularity is a page, 4096 bytes, because the loader cannot place a mapping at an offset that is not page-aligned. That is why the low twelve bits of every randomised address are fixed: the page offset within a mapping is determined by the file layout, not by the loader. A two-byte partial overwrite reaches anywhere in the same 64 KiB window regardless of randomisation, which is the reason such overwrites are a standard technique rather than a curiosity.

The number of bits varies by region and by kernel configuration. The mmap base on 64-bit x86 gets on the order of 28 bits in the common configuration, which is roughly a range of 256 GiB at page granularity. The stack receives fewer, on the order of 22 bits, because its range is bounded by the address space reserved for it and by the requirement that it stay near the top of the user half. The executable base under PIE is randomised across a comparable but separately derived range. On 32-bit x86 the totals are far smaller, eight to sixteen bits for the major regions, which is why 32-bit systems fell to brute force long before 64-bit ones did.

These figures are configuration-dependent and have changed across kernel versions. The stable statement is the relationship: the entropy is bounded by the size of the range the region may occupy divided by the page size, and the range is chosen to leave room for the region to grow.

Why the regions are independently randomised

A single random offset applied to the whole address space would be cheaper to implement and much weaker. If every region moved together, one leaked address would reveal all of them at once, and the entropy would be the entropy of the base alone. Independent offsets mean that knowing the library base says nothing about the stack, which is what makes the defence survive a partial leak.

The cost of independence is that the loader must keep track of each region’s placement and must ensure the regions do not collide. It also means the relative distance between a function in libc and a variable in the executable is not fixed, so a chain cannot be built from offsets relative to one known address unless both addresses are in the same mapping.

The heap sits inside the mmap region, so it inherits the mmap base’s randomisation rather than receiving its own. That is a detail with consequences: a leaked heap pointer discloses the mmap base, and therefore the location of every shared library mapped in the same region. The heap exploitation techniques that read a freed chunk’s metadata are, in effect, reading the mmap base out of the allocator’s own structures.

The leak, and why one is usually enough

Randomisation does not hide anything from the process itself. The process must know where its own code and data are in order to run, so the addresses are present in registers, on the stack, in the GOT, and in structures the program can read. Any bug that discloses memory contents discloses addresses.

The common leaks are unremarkable in isolation. A printf with a format string supplied by input reads successive stack slots, which contain saved frame pointers and return addresses. An uninitialised buffer copied to output carries whatever the previous user of that memory left there, often a pointer. An error message that prints a pointer, a length-prefixed read that returns more than was written, and a use-after-free that returns a chunk containing a freed pointer all do the same job.

The economic asymmetry is the point. Randomisation with 28 bits of entropy means a blind attempt succeeds with probability around 2^-28 per try, which for a remote target with no retry is negligible and for a local target with a crash-and-restart loop is a denial of service at best. A leak converts that to certainty. The defender’s position is therefore not “is the layout random” but “can the program be made to reveal a pointer”, and the second question is much harder to answer because it depends on every code path that touches memory.

The partial overwrite as a way around the leak requirement

An overwrite of the low bytes of a saved return address does not need a leak when the target is in the same mapping as the overwritten value. The saved return address already points into the executable or a library; overwriting its low two bytes moves it within the same 64 KiB region, and the high bytes stay correct because they were never touched. The attacker needs to know only the offset of a useful instruction within that region relative to the function that was returning.

This works because the low twelve bits are not randomised and because the region is large enough to contain useful code within a 64 KiB window. It fails when the target is in a different mapping, which is the usual case for a chain that wants to reach a library function from a return address in the executable.

The same property applies to pointers in the heap and the GOT. A one-byte overwrite of a function pointer shifts it within a 256-byte window; whether anything useful lies in that window depends on the binary’s layout, and the answer is version-specific.

What the kernel randomises that the attacker cannot see

Two details are often overlooked. First, the order in which libraries are mapped is itself a source of variation. The dynamic loader maps dependencies in the order the link map requires, but the base address for each is chosen by the kernel’s mmap calls, and those calls are interleaved with the loader’s own allocations. The result is that the offset between two libraries is not fixed, only the offset from each library’s base to its own contents.

Second, the kernel randomises the location of the stack’s initial contents, which include the argument vector, the environment, and the auxiliary vector. Those strings are what a system call often reads when the argument points into the environment rather than into a buffer. The environment is not at a fixed offset from the stack pointer, because the kernel places a random gap between the top of the stack and the initial frame.

The auxiliary vector is also the channel through which the program learns where things are. AT_PHDR, AT_BASE, and AT_ENTRY describe the executable and the interpreter, and AT_RANDOM supplies sixteen random bytes the loader uses to derive the stack canary. A program that prints the auxiliary vector has disclosed its own layout, and a leak of those values is as good as a leak of any address.

When randomisation is absent or degraded

Several common situations reduce the entropy to zero. A non-PIE executable is loaded at a fixed address, which is why PIE is a default on most current toolchains and why binaries linked without it remain valuable targets. A program built with -no-pie still has randomised libraries, so the executable’s own gadgets are at known addresses even when the libraries are not.

/proc/sys/kernel/randomize_va_space controls the global policy: 0 disables it, 1 randomises the mmap base, the stack, and the vDSO page, and 2 additionally randomises the heap. The value is readable by any process, so an attacker with local access knows the setting without guessing.

Containers and some sandboxing environments disable randomisation for reproducibility, and some debugging setups do the same. Emulators and translation layers may randomise differently or not at all. A binary analysed under one of those conditions yields addresses that do not hold on the target.

The defence has one structural weakness that no amount of entropy fixes: it is a per-process value, and a process that crashes and restarts gets a new one. An attacker who can make the target restart without losing the ability to try again faces a fresh guess each time, which is a denial-of-service channel. Systems that fork a server from a parent inherit the parent’s layout, so the child’s addresses are the parent’s addresses; the entropy is paid once at startup and then shared by every connection the parent serves. That is why pre-forking servers weaken randomisation in a way that a threaded server does not, and why the leak that matters most is the one that happens before the fork.