ViK: practical mitigation of temporal memory safety violations through object ID inspection

A use-after-free exploit needs three things to go right — a stale pointer, a new object landing on the freed memory, and a dereference through the stale pointer — and defences have attacked the first two by tracking every pointer or refusing to reuse addresses, both too expensive for an operating system kernel; this paper (Arizona State and Samsung) attacks the third instead, hiding a random identifier for each object in the sixteen bits of every pointer that hardware ignores, then checking it before use — and because a static analysis proves 96 percent of dereferences cannot be attacked, the check runs rarely enough to ship, at 2 percent on phone hardware.

Why this problem is worth solving

The attack has a fixed shape, and knowing it tells you where a defence can stand.

The mechanism turns on a spare resource that architectures happen to leave lying around.

What people did before, and where it broke

• Pointer invalidation. Track which pointers name which object, and on free either overwrite them all or refuse to free while any exist. This is the most complete answer in principle.

• The gap. The metadata is shared state that must be updated on pointer operations and kept thread-safe, which is expensive. And it misses what data-flow analysis cannot see — pointers in registers, spilled to the stack, or laundered through type-unsafe casts — each of which is a working exploit.

• Safe memory allocation. Refuse to reuse freed memory, either by quarantining it until nothing points there or by never recycling a virtual address. Recent versions of both are fast.

• The gap. Memory. Giving each object a unique address or holding freed blocks back costs footprint, sometimes enormously, and the memory comparison in this paper is the axis on which this approach loses.

• Access validation. Check at the point of dereference that the pointer is still valid, which is where this paper also stands.

• The gap. The received view was that checking every dereference is unaffordable, and the measurements supported it — the closest prior system costs 26 percent on a subset of one benchmark suite and does not support multithreaded programs at all.

• Hardware pointer tagging. Some processors now attach a small tag to allocations and to pointers and check them in hardware, which would make this nearly free.

• The gap. Tags are 4 bits, so 16 possible values, and an attacker who can retry gets through. Kernel support was not available, and the enormous installed base of processors without the feature would get nothing.

How a check becomes cheap enough for a kernel

The idea

Identity that lives in the pointer needs no tracking. The reason pointer invalidation is both slow and leaky is that it maintains a separate map from pointers to objects, which must be updated as pointers move and which can only be as complete as the analysis that finds them. Putting the identifier inside the pointer dissolves both problems at once. The identifier is copied when the pointer is copied, survives being loaded into a register or spilled to the stack, and passes through a cast that erases the type, because it is not metadata about the pointer but part of its value. So there is no shared structure to keep consistent between threads, which is the property that lets this scale to a kernel, and no category of pointer that escapes protection because the compiler could not see it. A 16-bit identifier splits into two parts: a random code that identifies the allocation, and a base identifier that lets the runtime recover an object’s start address from a pointer aimed into its middle, which matters because real code holds interior pointers constantly. This is the opposite bet from the quarantine-based defence covered elsewhere on this site, which lets a stale pointer keep pointing at memory but guarantees nothing else is ever placed there.

The static analysis is where the performance comes from. A kernel of this vintage contains about 2.3 million pointer dereferences, and instrumenting all of them would be absurd. So the paper spends most of its engineering on proving dereferences safe. The argument is a lifetime one: a pointer whose value never leaves the stack, never gets stored into the heap or a global variable, exists only briefly and is reachable only by a small amount of code, so an attacker cannot realistically arrange for the object to be freed and replaced in that window. That analysis marks 83 percent of pointer operations as unattackable outright. A second optimisation observes that once a pointer has been checked within a function, checking it again on each subsequent use adds little, so only the first use is instrumented — which takes the instrumented fraction down to 4 percent, and the hardware variant to a fraction of that again. The paper is candid that this second step is where the guarantee weakens, since a racing thread could free the object between the check and a later use. Spending the engineering on getting an overhead under the threshold at which people actually switch a defence on, rather than on strengthening the guarantee, is the same argument the software fault isolation work covered elsewhere on this site makes explicitly — and here it ends with the mitigation shipping in production devices.

A check with no branch, and failure delegated to the hardware. The inspection has to be tiny because it runs on the hot path. It loads the identifier stored with the object, combines it with the one carried in the pointer using only bitwise operations, and produces the address to dereference. When they match, the result is the ordinary address with the tag removed. When they do not, the result is an address that cannot be valid, and the subsequent dereference faults — so there is no comparison, no branch, and no error-handling path in the instrumented code, because the memory management unit raises the exception. In a kernel that means a panic, which is also the security argument: an attacker gets exactly one attempt, since a wrong guess crashes the machine rather than silently failing. With a 10-bit random code the collision probability is about 0.09 percent, comparable to the entropy of kernel address randomisation. Reaching for hardware pointer tagging where it exists cuts the cost further, which is the same lever the capability-hardware revocation work covered elsewhere on this site pulls much harder, at the price of needing processors that do not yet exist everywhere.

Watching one exploit fail

The alignment is what makes interior pointers work. Because object addresses are aligned to a known boundary, the base identifier carried in the pointer is enough to recover the start of the object, and therefore where its stored identifier lives, from a pointer aimed anywhere inside it.

Why it works

• Identity carried inside the value cannot be lost. Storing the identifier in the pointer rather than in a side table → it survives copies, register allocation, stack spills, and type-unsafe casts → the whole class of false negatives that comes from a data-flow analysis failing to find a pointer simply does not arise.
• No shared metadata means no synchronisation. Nothing has to be updated when a pointer moves → threads never contend over defence state → the approach scales to a kernel, where every prior mitigation had failed on exactly this point.
• Most dereferences are provably not worth defending. Proving that a pointer never escapes the stack means an attacker has no window to free and replace the object → 83 percent of pointer operations need no check → the remaining instrumentation is small enough that the overhead is a fifth rather than a multiple.
• A branchless check costs almost nothing on the hot path. Reducing validation to bitwise operations plus one load, with a mismatch producing an unmappable address → no comparison, no branch, no error path → failure detection is delegated to the memory management unit, which was going to translate the address anyway.
• Failing loudly turns weak entropy into a strong deterrent. A wrong identifier crashes the kernel rather than returning quietly → an attacker gets one attempt rather than unlimited retries → 10 bits of randomness is enough in practice even though 10 bits alone would not survive a guessing attack.

What it costs (trade-offs and scope)

• The safety argument is probabilistic, not absolute. Two live objects can receive the same identifier, at roughly 0.09 percent in the configuration tested. The defence is a mitigation that makes exploitation unreliable, not a proof that use-after-free cannot happen.
• The cheap optimisation opens a race. Checking only the first use of a pointer in each function means another thread can free and replace the object between that check and a later dereference. The paper shows the case and argues the pointer is usually caught later elsewhere.
• Stack pointers are out of scope. Pointers into stack frames are not protected, on the argument that their lifetime is bounded by a function call and they are hard to attack, with one known exception that the deallocation check happens to catch.
• Alignment costs memory. Objects must be aligned so their base can be recovered, and aligning everything to 64 bytes cost about 42 percent. A mixed policy brings this down, but choosing the constants well per object size is left as future work.
• Everything must be compiled with it. The instrumentation is a compiler pass, so pointers arriving from a library that was not compiled with it carry no identifier and are not protected — the same limitation every compiler-based defence in this area has.

The evaluation

Check yourself

Sources

ViK: Practical Mitigation of Temporal Memory Safety Violations through Object ID Inspection. Haehyun Cho, Jinbum Park, Adam Oest, Tiffany Bao, Ruoyu Wang, Yan Shoshitaishvili, Adam Doupé, Gail-Joon Ahn. ASPLOS 2022, pages 271 to 284. DOI 10.1145/3503222.3507780. Full text read from the first author’s copy hosted at their academic page.