Adelie: continuous address space layout re-randomization for Linux drivers

The kernel scrambles where its code sits at boot (KASLR) so attackers cannot find the "gadgets" they chain together for a return-oriented-programming (ROP) exploit — but Linux's version is weak on three counts — x86 instructions only carry 32-bit address offsets, so the whole kernel is crammed into a 2GB window with just ~19 bits of randomness (brute-forceable in about 512K tries); almost every internal pointer is static, so leaking ONE address exposes the whole layout; and it randomizes only once at boot, so an attacker who leaks addresses at runtime can still build a gadget chain; this defensive paper (Stony Brook and collaborators) builds Adelie, which switches kernel modules to position-independent code so they can live anywhere in the full 64-bit space (raising entropy from about 2^19 to 2^44), encrypts return addresses with a key that rotates on every re-randomization, and continuously re-scrambles a running driver's layout every few milliseconds by cheaply remapping its pages — so any leaked address is stale before an attacker can use it — all focused on drivers, the third-party, less-tested modules where kernel attacks usually start, at under 2% CPU overhead.

The argument in one glance

Problem

The kernel hides its code by randomizing where it sits — but the kernel does this badly

A powerful class of exploit never injects new code at all. Instead it finds short snippets of EXISTING code that already end in a return or jump — "gadgets" — and chains them together to do whatever it wants; this is return-oriented programming (ROP). The standard defense is to randomize where code sits in memory (ASLR), so the attacker cannot predict where the gadgets are. For ordinary user programs this works well. But the kernel is the highest-value target of all, and its version — KASLR — is far weaker. Worse, the easiest way into the kernel is usually through device drivers: they are typically written by third parties, less tested than the core kernel, and so more likely to contain the bug an attacker uses as a foothold.
What people did

Randomize the kernel and module base addresses once, at boot

Linux ships KASLR: at boot, it picks a random offset and places the kernel image (and later each loaded module) at a randomized base address, so gadget locations differ from one boot to the next. An attacker who hard-coded gadget addresses for one machine would find them wrong on another. On paper this raises the bar against ROP.
Why it fell short

Low entropy, static pointers, and one-shot randomization make it easy to defeat

KASLR has three compounding weaknesses. First, LOW ENTROPY: most x86-64 instructions can only encode a 32-bit address offset, so the kernel and all its modules must live within a single 2GB window — leaving only about 19 bits of randomness after page alignment, which a brute-force ROP attack can defeat in roughly 512 thousand tries. Second, STATIC POINTERS: nearly every pointer inside the kernel never moves after boot, so if the attacker can leak just one address (through some information-disclosure bug), the entire layout falls out and the rest of the pointers are computable. Third, ONE-SHOT: the layout is randomized only at boot and then frozen, so a just-in-time ROP attacker who leaks addresses at RUNTIME can, within milliseconds, assemble a working gadget chain before anything changes. Nothing re-randomizes to make that leaked knowledge go stale. For drivers — the likely foothold — this is exactly the wrong combination.
This paper's idea

Escape the 2GB cap, rotate the secret, and never stop moving

This paper (Stony Brook University and collaborators — Nikolaev et al.) builds Adelie, a defensive kernel mechanism that attacks all three weaknesses, focused on the modules where attacks start. First, it switches kernel modules to POSITION-INDEPENDENT CODE (PIC) — RIP-relative addressing plus a Global Offset Table — so a module runs correctly at ANY address in the full 64-bit space, at any distance from the kernel, removing the 2GB cap and raising entropy from about 2^19 to about 2^44. Second, for the pointers that cannot be moved — return addresses on the stack — it ENCRYPTS them (XOR with a key) using a key that is regenerated on every re-randomization, and it swaps stacks at module entry, so a leaked or tampered return address is worthless after the next rotation. Third, it performs CONTINUOUS re-randomization: a background thread periodically remaps a running module to fresh virtual addresses — cheaply, by pointing new page-table entries at the same physical pages rather than copying — and retires the old mapping only after every in-flight call has drained. The result is a moving target that closes the just-in-time ROP window to milliseconds, applied to drivers at under 2% CPU overhead.

Why this problem is worth solving

Kernel exploits are the highest-stakes exploits there are — a compromised kernel owns the whole machine — and the technique that makes modern kernel exploitation practical is worth understanding first. A

RETURN-ORIENTED PROGRAMMING (ROP) is a way to hijack a program without injecting any new code, which defeats defenses like non-executable memory that only stop injected code. The attacker scans the existing code for “gadgets” — short instruction sequences that each end in a return (or indirect jump) — and, by writing a series of addresses onto the stack, chains gadgets together so that each one’s ending return jumps to the next, composing arbitrary behavior out of code that was already there. This requires knowing WHERE the gadgets are. JUST-IN-TIME ROP (JIT-ROP) is the runtime version: rather than relying on a fixed, pre-computed layout, the attacker exploits an information-disclosure bug to leak actual code addresses while the target runs, then builds the gadget chain on the fly from the real layout — within milliseconds, before anything changes. JIT-ROP is what makes randomization defenses fragile, because it does not need to guess the layout; it reads it

is the adversary Adelie is built to stop. The reason it matters is that ROP sidesteps the defenses most people think of first, and JIT-ROP sidesteps the one defense — randomization — that was supposed to catch ROP.

The defense that was supposed to help, in the kernel, is where the trouble concentrates. A

KASLR (kernel address space layout randomization) is ASLR applied to the kernel: at boot it places the kernel image and modules at randomized base addresses so gadget locations are not predictable. Its central weakness is architectural. On x86-64, most instructions can encode only a 32-bit immediate or displacement — a signed offset reaching about 2GB — so to let the kernel call into a module (and vice versa) with ordinary instructions, Linux confines the entire kernel plus all modules to one 2GB virtual window. That cap is what strangles the entropy: within 2GB, after 4KB page alignment, only about 19 bits of the address are actually random, so an attacker needs at most around 512 thousand attempts to brute-force a base — feasible, especially since a wrong guess in the kernel often just crashes-and-retries. And because the range is fixed and the pointers inside it are static, a single leaked pointer collapses the whole scheme

reveals why merely doing KASLR “harder” is not enough — the 2GB cap, the static pointers, and the boot-only timing are three separate holes. Adelie is worth studying because it plugs all three at once, and does so precisely where kernel attacks tend to begin.

What people did before, and where it broke

User-space ASLR. Randomize a process’s layout on each launch. Strong, because 64-bit user programs have huge entropy and a crashed process just dies — but it says nothing about the kernel that every process shares.
Linux KASLR (boot-time). Randomize the kernel and module base addresses once at boot. Confined to a 2GB window by the 32-bit instruction-offset limit, so entropy is only about 19 bits — brute-forceable — and the layout never changes afterward.
Fixed / static in-kernel pointers. The kernel keeps function and data pointers at fixed offsets. Convenient and fast, but it means one leaked address deanonymizes the entire layout, since everything else is a known distance away.
Whole-kernel re-randomization (in principle). Periodically re-randomize everything to defeat JIT-ROP. But naively this means copying all kernel code and data and fixing every pointer — far too expensive to run continuously, and still stuck inside the 2GB range.
The gap. No deployed approach gives the kernel high entropy AND makes leaked pointers expire AND re-randomizes continuously at low cost — especially for the third-party drivers that are the most likely entry point. That is the gap Adelie fills.

How Adelie keeps a driver’s layout unpredictable

Escape the address cap, encrypt what cannot move, and remap continuously without copying

The threat and the weak defense

A JIT-ROP attacker leaks real code addresses at runtime and chains existing gadgets. KASLR randomizes only once at boot, confines the kernel to a 2GB window (about 19 bits of entropy), and keeps pointers static — so one leak plus a little brute force is enough, and drivers are the usual foothold.
↓ →
Switch modules to position-independent code new

Adelie compiles modules as PIC: absolute addresses become RIP-relative (offset-from-the-instruction-pointer) references and a Global Offset Table holds external symbols. Now a module runs correctly at ANY 64-bit address, any distance from the kernel — removing the 2GB cap and raising entropy from about 2^19 to about 2^44. Module-local references are patched back to direct offsets where they are provably within 2GB, so the GOT indirection is avoided where it is not needed.
↓ →
Encrypt the pointers that cannot be moved new

Return addresses live on the stack and cannot be relocated, so each re-randomizable function's prologue and epilogue XOR-encrypt and decrypt the return address with a key stored in the module's local GOT. The key is regenerated on every re-randomization, so a leaked or overwritten return address decrypts to garbage after the next rotation. Adelie also swaps in a fresh stack (from a per-CPU lock-free list) at each module entry.
↓ →
Re-randomize continuously, without copying new

A background re-randomizer kernel thread periodically gives a running module a new virtual location by creating fresh page-table entries that point at the SAME physical pages — no copying of code or data — and updating the local GOT entries to the new addresses. Fixed GOT entries that point into the immovable core kernel stay constant.
↓ →
Drain in-flight calls before unmapping the old layout new

Wrapper functions mark module entry and exit (mr_start / mr_finish), and a Hyaline-based reclamation scheme retires the old virtual mapping only after every pending call through the module has completed. So no in-flight call ever dereferences a stale address, and the old gadget addresses become unmapped and unusable promptly.
↓ →
Focus the expensive defense on the weak link new

All of this is applied to modules and drivers — the third-party, less-tested, likely-foothold code — not to the whole kernel, keeping the cost low. The re-randomizer thread uses about 0.4% of a CPU at a 20ms period shared across modules, scaling to hundreds of modules, and total overhead stays under 2% CPU on real workloads.

Implemented for the Linux kernel on x86-64 with a GCC plugin that wraps module functions and fixes relocations, plus a modified module loader and a re-randomizer thread. Evaluated with sysbench, Kernbench, ApacheBench, MySQL OLTP, and NVMe throughput. Presented as a defensive mechanism.

The idea

A leaked secret is only dangerous while it stays valid — so keep rotating it. The deepest problem with boot-time KASLR is not that its entropy is low (though it is); it is that once the layout is known, it stays known forever. Adelie’s central move is to make the layout a MOVING TARGET: re-randomize the module continuously, and rotate the return-address encryption key on every cycle, so any address an attacker leaks is stale within milliseconds — long before a JIT-ROP chain can be assembled and fired. This expire-the-leaked-secret discipline is one the site’s security pages keep circling: the branch-predictor-attack page, having shown how thoroughly leakable a hidden CPU register is, points to exactly this remedy — periodically re-randomize the state and change the key so a read is worthless by the time it is used — and the broader lesson across those pages is that a static secret is a liability the moment any leak exists. Where noise-is-not-a-defense on the cache-side-channel page is a warning, continuous re-randomization is the constructive form of the same insight: do not hope the secret stays hidden; assume it leaks, and make the leak expire.

Remove the constraint at the representation level, not by fighting it. The 2GB cap is not a law of nature; it is an artifact of using instructions that carry only 32-bit offsets. Rather than squeeze more entropy out of a 2GB window, Adelie changes the CODE MODEL to position-independent code, whose RIP-relative and GOT-based addressing has no 2GB horizon, and the entropy jumps from about 19 bits to about 44 almost for free. This change-the-representation-to-remove-an-artificial- limit move is one the site rewards elsewhere — the orientation-learning page escapes a coordinate singularity by choosing a representation that does not have one, and the non-GEMM-accelerator page reframes where the real cost lives instead of accepting the obvious framing. The pattern is the same: a painful limit that looks fundamental is often an accident of how something was encoded, and swapping the encoding dissolves it.

Change the address, not the bytes — and know when it is safe to let go. Continuous re-randomization sounds ruinously expensive if you picture copying a running driver’s code and data every few milliseconds. Adelie makes it cheap with virtual-memory indirection: it maps the SAME physical pages at a new virtual address and only fixes the pointers that must change, so re-randomization is a page-table edit, not a data copy — the same re-map-do-not-copy trick the site’s memory-systems pages use when they migrate or remap data by manipulating the address layer instead of moving bytes. The remaining hard part is concurrency: you can only unmap the OLD address once every call that might still be using it has finished. Adelie borrows a reclamation scheme (Hyaline) to wait for all in-flight calls to drain before retiring the old mapping — the same wait-for-the-readers-to-drain reasoning behind safe memory reclamation and the “can this ever still be reached?” liveness question the Go-concurrency page answers for stuck goroutines. Cheap movement plus safe reclamation is what makes “never stop moving” actually affordable.

Making a leaked address worthless

Closing the just-in-time ROP window

Hardening Linux drivers against JIT-ROP on x86-64. Numbers from the paper's evaluation.

Step 1 of 5

Why one leak breaks KASLR

Boot-time KASLR confines the kernel to a 2GB window (about 19 bits of entropy) and keeps pointers static, randomized once. So an attacker leaks a single address at runtime, computes the rest of the layout from fixed offsets (or brute-forces the base), and chains gadgets — a just-in-time ROP attack the frozen layout cannot resist.

brute-forcing a base within 2GB after page alignment takes at most about 512 thousand attempts
drivers are the usual foothold: third-party, less tested, and often carrying exploitable bugs

Why it works

Most x86-64 instructions carry only 32-bit offsets, which forced KASLR into a 2GB window → switching modules to position-independent code removes that cap → entropy rises from about 2^19 to 2^44 and brute force becomes infeasible.
A boot-time layout stays valid forever once leaked → continuously re-randomizing and rotating the encryption key makes any leaked address stale within milliseconds → the just-in-time ROP window closes before a chain can be built.
Return addresses on the stack cannot be relocated → XOR-encrypting them with a per-cycle key neutralizes leaked or overwritten return addresses → stack-based hijacking fails even though the addresses stay in place.
Copying a running driver every few milliseconds would be ruinous → remapping the same physical pages to new virtual addresses makes re-randomization a page-table edit, not a data copy → continuous movement becomes affordable.
Unmapping an old layout while a call still uses it would crash → a reclamation scheme drains all in-flight calls before retiring the old mapping → old gadget addresses vanish promptly and safely.

What it costs (trade-offs and scope)

PIC adds indirection and even more gadgets. Position-independent code introduces GOT machinery, so PIC modules actually contain MORE ROP gadgets than non-PIC ones — accepted because PIC is precisely what enables the 64-bit entropy and continuous re-randomization that neutralize gadgets regardless of where they come from.
Overhead is workload-dependent. It is near zero for I/O-bound and compile workloads, but a CPU-bound path that constantly crosses the module boundary pays about 4% from the function wrappers plus about 6% from stack re-randomization, and shorter periods or many simultaneously-randomized modules raise CPU further.
It needs real toolchain and kernel surgery. A GCC plugin wraps module functions and rewrites relocations, and assembly files, non-standard calling conventions, inline-assembly macros, exception handlers, and hypervisor interactions all need special handling — it is not a transparent, drop-in flag.
Scope is modules, not the core kernel. A gadget chain living entirely within the non-re-randomized core kernel is not moved by module re-randomization; the argument is that drivers are where attacks START, and encryption plus stack re-randomization block injecting gadgets THROUGH modules — but the core kernel remains a separate problem.
Correctness is intricate and unforgiving. Every pointer, GOT entry, and stack reference to relocated code must be found and fixed on each cycle; a single missed pointer means a crash, and the reclamation must never retire a mapping a call still needs — a demanding invariant to maintain continuously.

The evaluation

A Linux x86-64 implementation with a GCC plugin, a modified module loader, per-CPU stack lists, and a re-randomizer thread, measuring PIC overhead, continuous re-randomization overhead at periods down to 1ms, security (entropy and gadget analysis with a proof-of-concept), and CPU scaling, using sysbench file I/O and OLTP, Kernbench, ApacheBench, and NVMe throughput.

Defending the kernel against just-in-time ROP

Property	Linux KASLR (boot-only)	Whole-kernel re-randomization (naive)	Adelie (this work)
Entropy
A leaked pointer stays useful for
Re-randomization cost
Protected scope
Runtime overhead

Boot-time KASLR is cheap but low-entropy, static, and one-shot; naive whole-kernel re-randomization is secure-in-principle but too expensive and still range-capped. Adelie escapes the 2GB cap with position-independent code, expires leaked pointers by rotating encryption keys and remapping continuously, and keeps cost under 2% CPU by protecting only the drivers where attacks begin.Underlined values explain themselves when clicked.

Where this stops working

What to keep in mind

Read the scope precisely. Adelie hardens MODULES and drivers, not the core kernel, so a ROP chain built entirely from gadgets in the non-re-randomized core is not moved by module re-randomization; the claim is that drivers are the likely foothold and that encryption and stack re-randomization block injecting gadgets through them, not that the whole kernel becomes ROP-proof. Position-independent code adds GOT indirection and actually increases the raw gadget count — the defense comes from entropy and continuous movement, not from having fewer gadgets. Overhead is real on CPU-bound paths that cross the module boundary often (about 4% from wrappers plus about 6% from stack re-randomization) and grows with shorter periods and more modules, even though it is near zero on I/O and compile workloads and stays under 2% CPU overall. And it demands substantial toolchain and kernel engineering — a GCC plugin, relocation rewriting, and careful handling of assembly, exception handlers, and hypervisor paths — with an unforgiving correctness requirement that every pointer be fixed on every cycle. Within that scope the message is strong and general: do not treat the memory layout as a secret you can keep; assume it leaks, raise the entropy by removing the architectural cap, and make the leak EXPIRE by continuously re-randomizing and rotating keys — cheaply, by remapping pages rather than copying them, and safely, by draining in-flight calls before retiring the old layout.

Background

Expire the leaked secret, remove the artificial cap, and re-map instead of copy

This paper sits in the site’s systems-security cluster and rhymes with several ideas covered elsewhere on this site. Its central move is to treat the memory layout as a secret that WILL leak and to make the leak expire — continuously re-randomizing and rotating the return-address key so a disclosed address is stale within milliseconds. That is the constructive twin of the branch-predictor-attack page, which after showing how completely a hidden CPU register can be read points to exactly this defense (re-randomize the state, change the key every cycle), and the sharp opposite of the cache-side-channel page’s warning that a static assumption of secrecy is no defense — here the response is not to hope the secret holds but to rotate it faster than it can be used. Its entropy win comes from removing an artificial constraint at the representation level: the 2GB cap is an artifact of 32-bit instruction offsets, and switching to position-independent code dissolves it, the same change-the-encoding-to-escape-a-built-in-limit move the orientation- representation page uses to escape a coordinate singularity and the non-GEMM-accelerator page uses to reframe where the real cost lives. Its efficiency comes from re-mapping rather than copying — moving a running driver by editing page tables to point at the same physical pages — the same manipulate-the-address-layer-not-the-bytes trick the site’s tiered-memory and runtime-optimization pages use to migrate data cheaply. And its safety rests on draining all in-flight calls before retiring an old mapping, the same wait-for-the-readers-to-drain reclamation reasoning, and the same “can this still be reached?” liveness question, that the Go-concurrency page answers when it decides whether a blocked goroutine can ever proceed. Together they make Adelie a case study in assuming the leak and engineering the secret to expire before it is worth anything.

If you remember only three things

1. The kernel defends against return-oriented programming (ROP) by randomizing where its code sits (KASLR), but Linux's KASLR is weak on three fronts: most x86-64 instructions carry only 32-bit offsets, so the kernel and modules are crammed into a 2GB window with only about 19 bits of entropy (brute-forceable in about 512 thousand tries); in-kernel pointers are static, so leaking one address exposes the whole layout; and randomization happens only once at boot, so a just-in-time ROP attacker who leaks addresses at runtime can build a gadget chain before anything changes. Drivers — third-party and less tested — are the usual foothold.
2. Adelie fixes all three by (1) compiling modules as POSITION-INDEPENDENT CODE (RIP-relative plus a GOT) so they can live anywhere in the 64-bit space, removing the 2GB cap and raising entropy from about 2^19 to 2^44; (2) ENCRYPTING return addresses (which cannot be moved) with a key regenerated every cycle, plus swapping stacks at module entry; and (3) CONTINUOUSLY re-randomizing a running module every few milliseconds — cheaply, by remapping the same physical pages to new virtual addresses instead of copying, and safely, by draining all in-flight calls (via Hyaline reclamation) before unmapping the old layout.
3. The result is a moving target that makes any leaked address stale within milliseconds, focused on the drivers where kernel attacks start, at under 2% CPU overhead (re-randomizer thread about 0.4% of a CPU at a 20ms period), scaling to over 950 modules. The transferable lessons: assume your secret (here the memory layout) will leak and make the leak EXPIRE by rotating it; remove a painful limit by changing the representation (the 2GB cap was an artifact of 32-bit offsets, not a law); move things cheaply by editing the address layer rather than copying bytes; and reclaim the old state only after all users have drained.

Check yourself

Check your understanding

1. Boot-time KASLR randomizes the kernel layout once and freezes it. Predict why that is fundamentally inadequate against a just-in-time ROP attacker, and what Adelie does instead.
2. Linux confines the kernel and all modules to a 2GB window, capping KASLR entropy at about 19 bits. Predict how Adelie escapes that cap.
3. Re-randomizing a running driver every few milliseconds sounds ruinously expensive. Predict how Adelie makes it cheap, and what makes it safe.
4. Adelie encrypts return addresses on the stack rather than relocating them like other pointers. Predict why encryption is the right tool specifically here.

Sources

Adelie: Continuous Address Space Layout Re-randomization for Linux Drivers (arXiv:2201.08378) — ASPLOS 2022 (full text read via ar5iv).
ar5iv HTML rendering — the version read for this explainer.
arXiv PDF — full paper.