A use-after-free bug only becomes an exploit once the freed memory is handed to someone else, so the defence is to hold every freed block back until no pointer to it survives anywhere — the trouble being that proving that has always meant a garbage-collector-style traversal of the whole reference graph, which costs too much to deploy; this paper (Cambridge) observes that the question is far narrower than reachability, and that zeroing memory when the programmer frees it collapses the graph to a single level, so one flat linear scan of memory suffices — 5.4 percent slower with 11.1 percent more memory, cheap enough to actually turn on.
The argument in one glance
-
Problem
Freed memory that gets reused is an attacker's foothold
In a language with manual memory management, a program can release an object while still holding pointers to it. Those pointers are now stale, and reading through one is a bug. It becomes a weapon when the allocator gives that same memory to a new object, because an attacker who can make the program allocate and can fill what it allocates then controls what the stale pointer sees. Write a fake table of function addresses there, wait for the program to call through the stale pointer, and control transfers wherever the attacker chose. As other bug classes were closed off, this became the easiest way in, and the reported counts rose steadily.
-
What people did
Hold freed memory back until no pointer to it survives
The defence follows directly. Do not return a freed block to the allocator immediately. Put it in a quarantine, and release it only once nothing in the program can still name it. That converts the dangerous case into a harmless one — the stale pointer now refers to memory nobody else owns, so using it either does nothing interesting or trips a protection fault and stops the program cleanly.
-
Why it fell short
Proving nothing points at it has meant paying for a collector
Deciding which quarantined blocks are safe looks like the question a garbage collector answers, so previous systems answered it the same way — start from a root set and transitively mark everything reachable. That traversal is expensive, it must chase pointer chains through the quarantine itself, and cyclic structures inside the quarantine can never be released at all. The resulting systems paid either a large slowdown or a large memory increase, and the honest summary was that none of them was cheap enough to switch on in production.
-
This paper's idea
The question is narrower than reachability, so scan once and flatly
This paper (Márton Erdős, Sam Ainsworth and Timothy M. Jones) points out that a quarantine does not need reachability. Everything outside the quarantine can simply be assumed reachable, so the only thing that must be found is whether any word anywhere holds a pointer into a quarantined block — one flat pass over memory, no chains to follow. Zeroing each block as it enters quarantine makes that exactly true by deleting the pointers inside the quarantine, which also destroys the cycles that stalled earlier systems.
Why this problem is worth solving
The bug and the exploit are two different events, and only the second one matters.
USING
a pointer after its object was freed is, by itself, usually uninteresting. The memory is
still mapped and still holds the old contents, so the program reads stale data, or the
region has been returned to the operating system and the access faults and the program
dies cleanly. The exploitable situation is narrower. It requires that the allocator has
since given that same memory to a new object, and that an attacker controls the contents
of the new object — which they often can, by feeding the program input that makes it
allocate. Now the stale pointer and the attacker’s data name the same bytes. The classic
sequence writes a fake table of function pointers there and waits for the program to make
a virtual call through the stale pointer, which transfers control to an address the
attacker chose. Everything in this paper follows from attacking that second event instead
of the first — memory that is never reallocated while a pointer to it survives cannot be
used this way, whatever bugs the program contains.
The second thing to fix is what separates this from garbage collection.
A
garbage collector decides on the program’s behalf that an object is dead and reclaims it.
That decision is unsound for C and C++, because a program may hold the only pointer to an
object in a form no scan can recognise — two pointers combined arithmetically into one
word, an address written to a file and read back, an offset stored instead of an address.
A collector that misses such a pointer frees a live object and breaks a correct program.
A quarantine never makes that decision. It only ever releases memory the programmer
explicitly asked to free, so the worst outcome of missing a pointer is that protection is
not extended to that one case, never that a working program is broken. The same logic
runs the other way too. Because arbitrary data cannot be distinguished from pointers, an
integer that happens to equal an address keeps that block quarantined a while longer,
which costs a little memory and nothing else. A quarantine can afford to be wrong in both
directions in a way a collector cannot.
What people did before, and where it broke
-
Transitive marking, borrowed from collectors. The strongest prior drop-in system quarantines freed memory and runs a mark phase from a root set, following pointer chains to determine which quarantined blocks are still referenced. It gives a genuine guarantee and it works on unmodified programs.
-
The gap. The traversal is the expensive part, it must follow chains through the quarantine, and pointer cycles inside the quarantine keep each other alive forever. The measured cost in time and memory kept it out of production.
-
Never reuse an address at all. A different tactic — hand out fresh virtual addresses and never recycle one, so a stale pointer can never name a new object. This is elegant and fast, with the lowest slowdown of any scheme compared here.
-
The gap. Memory. Measured on the same benchmarks, its footprint overhead averaged 244 percent and reached over 1,000 percent, and it grows steadily over a long run, which is exactly the wrong shape for a long-lived server.
-
Pointer nullification. Track every pointer to every object and overwrite them all at the moment of free, so no stale pointer can exist.
-
The gap. Tracking every copy of every pointer requires instrumenting the program and maintaining metadata proportional to pointer traffic, which is costly, and it needs recompilation rather than working on the binary you already have.
-
Hardware capabilities. Make pointers unforgeable and bounds-checked in the architecture, then revoke them when memory is freed. This gives the strongest guarantees available.
-
The gap. It requires a processor that does not yet exist in most machines, and recompilation of everything. It solves a problem this paper deliberately restricts — running on the hardware and binaries people already have.
How a freed block earns its way out of quarantine
The life-cycle of one allocation under a quarantine layer
-
-
new
-
new
-
new
-
new
-
new
The idea
The problem is not reachability, and noticing that removes the traversal. A collector must answer which objects are reachable from a root set, which is a question about paths through a graph and therefore demands a transitive walk. A quarantine needs something much weaker. Assume that everything outside the quarantine is reachable — an assumption that is wrong only for leaked memory, which is rare, and wrong in the safe direction, since it can only delay a release and never cause an unsafe one. Under that assumption, all that matters is whether any edge ends inside the quarantine, and edges can be found by looking at every word once, in address order, with no chains to follow and no work list. This is a sequential scan of memory rather than a pointer chase, which the hardware handles far better. Reducing a general graph problem to a flat pass by exploiting what the specific setting guarantees is the same kind of move as the capability-hardware revocation work covered elsewhere on this site, which reaches the same goal by making the hardware intercept every pointer load instead.
Zeroing on free is what makes the flat scan correct. The catch in the reduction is that quarantined blocks may themselves contain pointers, including pointers to other quarantined blocks. Those would be found by the scan and would keep their targets quarantined, and worse, two quarantined blocks pointing at each other would hold each other hostage forever. So the system overwrites each block with zeros as it enters quarantine. That deletes every edge leaving the quarantine, which is exactly what flattens a multi-level, potentially cyclic reference graph into a single level where the only edges that exist run from live memory into the quarantine. It is a small implementation detail with a large algorithmic consequence, and the ablation shows it clearly — without zeroing, two benchmarks exhaust 32 GB of memory and are killed. The interaction with the allocator matters just as much, since the quarantine changes the pattern of free memory that the allocator sees; the warehouse-scale allocator study covered elsewhere on this site is a long argument for how sensitive real allocators are to exactly that.
Every remaining cost is engineering, and the engineering is the contribution. The base idea would still be too slow to deploy, so most of the paper is about making the constant factors payable. The sweep runs concurrently with the program on background threads, in two variants — one takes a brief pause to re-examine pages the program modified mid-sweep, and the other drops the pause and accepts a slightly weaker guarantee, on the reasoning that an attacker cannot make the program shuffle its stale pointers around. Large quarantined blocks have their physical pages released immediately, since only the address range needs to be withheld, not the memory behind it. The allocator is made to purge its free structures after every sweep, without which fragmentation from the quarantine dominates. Each of these moves the numbers substantially, and the point of all of them is a deployability threshold rather than a benchmark score — the same standard applied by the software fault isolation work covered elsewhere on this site, where the whole argument is that a defence nobody can afford to enable protects nobody.
One sweep, from trigger to release
How a quarantined block is proved safe to reuse
Following one sweep from the moment the quarantine grows large enough to the moment memory is recycled.
Step 1 of 5
The quarantine crosses its threshold
A sweep starts once quarantined memory reaches about 15 percent of the heap. Blocks that failed to be released in a previous sweep are subtracted from both sides of that comparison.
Without that subtraction a program holding one long-lived stale pointer would push the quarantine over the threshold permanently and sweep on every single free. The earlier system used a 25 percent threshold; a cheaper sweep allows a more aggressive one, which trades time for a smaller memory footprint.
Why it works
- Assuming everything outside quarantine is live is safe. Treating non-quarantined memory as reachable without checking → the only possible error is failing to release a block that a leak still points at → the approximation can waste memory but can never release memory that something still names.
- A flat scan matches the machine better than a pointer chase. Replacing a transitive mark with one pass in address order → sequential access that prefetchers handle well, with no work list and no dependent loads → sweeps become cheap enough to run often, which in turn allows a lower quarantine threshold and a smaller footprint.
- Zeroing removes the edges that would stall the algorithm. Overwriting each block as it enters quarantine → no pointers exist inside the quarantine, so no cycles and no chains within it → the reference graph is one level deep, which is the precondition the flat scan needs.
- Only the address range must be withheld, not the memory. Releasing the physical pages of large quarantined blocks while keeping their addresses reserved → the footprint drops without weakening the guarantee → one benchmark falls from being killed after 30 GB to 1.4 times its baseline.
- Being wrong about pointers costs memory rather than correctness. Treating every word as a possible address and missing pointers stored in disguised forms → the first only delays a release, the second only forgoes protection in a rare case → the system never frees anything the programmer did not free, which is what lets it run on unmodified programs.
What it costs (trade-offs and scope)
- The real cost is delayed reuse, not the sweep. Breaking the overhead down shows that quarantining alone accounts for most of it, because memory the program just freed is no longer immediately reused and so falls out of the caches. The worst benchmark slows by about 2 times for exactly that reason, not because of the sweeper.
- Heap only, and mitigation only. Spatial bugs such as buffer overflows are untouched, stack temporal bugs are out of scope, and the system does not report the bug. It converts an exploitable use-after-reallocate into a harmless use-after-free or a clean crash, which is not the same as finding the defect.
- Accesses to quarantined memory are still possible. The block is withheld from reallocation, but nothing prevents the program from reading or writing it through the stale pointer while it waits.
- Pointers the scan cannot see are not protected. Addresses stored in a disguised form — combined arithmetically with other data, or written out and read back — are missed. The paper argues this is rare and that an attacker cannot induce it, but it is a real hole in the guarantee.
- The fully concurrent mode relaxes the guarantee slightly. Dropping the brief pause means a stale pointer that the program moves around after its object was freed could be missed. The recommended mode accepts this; the stricter mode costs about three more percent of run time.
The evaluation
| Property | What was measured | The result | What it tells you |
|---|---|---|---|
| Cost on a standard benchmark suite | |||
| Against the previous best drop-in schemes | |||
| Where the overhead comes from | |||
| Which optimisations carry the result | |||
| Behaviour under extreme allocation pressure |
Check yourself
Check your understanding
1. Why does assuming that all memory outside the quarantine is reachable make the algorithm both simpler and still safe?
2. What breaks if freed blocks are not zeroed when they enter the quarantine?
3. The breakdown shows that quarantining alone costs about 18 percent in time before any sweeping is performed. What does that tell you?
4. Predict what happens if a program stores an integer that happens to equal the address of a quarantined block.
Sources
MineSweeper: A “Clean Sweep” for Drop-In Use-after-Free Prevention. Márton Erdős, Sam Ainsworth, Timothy M. Jones. ASPLOS 2022, pages 212 to 225. DOI 10.1145/3503222.3507712. Full text read from the authors’ copy hosted at the University of Cambridge.