Borrow Checker's Revenge: Stacked Borrows Violation in Rust's `lru` Crate

Rust is famous for its promise of memory safety. It’s the language that holds your hand, checks your homework, and slaps your wrist if you try to access memory you shouldn't. But there is an escape hatch: unsafe. Inside an unsafe block, the compiler takes off the training wheels and says, "Okay, you claim you know what you're doing. Don't crash." The lru crate, a widely used implementation of a Least Recently Used cache, relies heavily on unsafe because implementing a doubly-linked list backed by a HashMap in Rust is widely considered a form of masochism.

In Rust, self-referential structures (like a node that needs to be in a list and a map simultaneously) fight against the borrow checker's strict ownership rules. To make it efficient, developers drop down to raw pointers. But raw pointers come with a hidden contract: The Stacked Borrows Model. It’s a set of rules defining which pointers are allowed to exist and access memory at any given time.

This vulnerability is a classic case of breaking that contract. The developers implemented IterMut (mutable iteration) and, in doing so, accidentally told the compiler, "I have exclusive access to this key." The compiler, trusting this assertion, invalidated all other pointers to that key—including the ones the lru cache needed to actually function. It's the digital equivalent of changing the locks on your house while your spouse is still inside, then wondering why they can't open the door.

To understand this bug, you need to understand the Stacked Borrows model. Think of a memory location as a nightclub. Access permissions are a stack of VIP passes. When you create a shared reference (&T), you add a pass to the stack. Many people can have read-only passes. However, when you create a mutable reference (&mut T), you are creating an exclusive pass. To enforce exclusivity, the model says: "When this &mut is created, pop everything above it off the stack. Nobody else gets in until this guy leaves."

The lru crate maintains two ways to reach a cache entry: via a pointer in a HashMap (for O(1) lookups) and via pointers in a LinkedList (for ordering). These are aliases. They point to the same memory.

In the vulnerable versions of lru, the next and next_back methods of IterMut did something fatal. They took a raw pointer to a node and cast it to a mutable reference (&mut K) to access the key. In Rust semantics, creating &mut K asserts uniqueness. The moment that code ran, the Stacked Borrows model looked at the memory location for that key and said, "Okay, this iterator has exclusive access. I am hereby invalidating the pointer inside the HashMap."

The problem? The HashMap didn't know its pointer was just voided. It still held the KeyRef. If the program later tried to use the HashMap to find that key (which is the whole point of an LRU cache), it would be dereferencing a pointer that the abstract machine considers "dead." This is Undefined Behavior (UB).

Let's look at the crime scene. The issue lived in the iterator implementation. The goal was simple: iterate over the cache and give the user mutable access to the values. However, getting access to the node involved touching the key.

Here is a simplified view of the vulnerable logic inside IterMut::next:

// The offending code (conceptual)
// We have a raw pointer to a node: self.ptr
// We want to yield the key and value.
 
// CRITICAL ERROR HERE:
// This casts the raw pointer to a mutable reference (&mut K).
// This acts as a "retag", asserting exclusive access to the key.
let key = unsafe { &mut (*(*self.ptr).key.as_mut_ptr()) as &mut K };
 
// Because the HashMap *also* has a pointer to this key,
// creating an exclusive &mut K here invalidates the HashMap's pointer.

When &mut K is created, it asserts that it is the only active way to access that memory. The pointer sitting inside the HashMap (wrapped in KeyRef) effectively dies. The fix, implemented in version 0.13.0, was to stop being so greedy. The iterator doesn't need exclusive mutable access to the key (keys in a map shouldn't be mutated anyway as it breaks the hash). It only needs shared access or raw pointer access.

The Fix:

// The fixed code avoids creating &mut K
// It uses a shared reference or raw pointer logic that doesn't trigger
// the "Unique" retagging event that kills aliases.
let key = unsafe { &*(*self.ptr).key.as_ptr() };

By downgrading the reference from &mut to &, or strictly using raw pointers until the last second, the code plays nice with the aliasing model, allowing the HashMap's pointer to coexist peacefully.

Exploiting Undefined Behavior in Rust is different from smashing a stack in C. You don't always get a crash. Sometimes, you get something worse: silent corruption or compiler optimizations that delete your code. The LLVM compiler assumes UB never happens. If it sees &mut, it applies the noalias metadata. It assumes it can cache values in registers because "nothing else can possibly write to this memory."

To "exploit" or prove this, we don't use Metasploit; we use Miri. Miri is an interpreter for Rust's mid-level intermediate representation (MIR) that checks for UB. It tracks the "borrow stack" for every byte of memory.

Here is the attack chain simulation:

1. Setup: Create an LruCache.
2. Iterate: Call .iter_mut(). This triggers the faulty code, creating the &mut reference to a key.
3. The Trigger: Inside Miri, this fires a "retag" event. Miri looks at the borrow stack for that key's memory address. It sees the HashMap's pointer and the new &mut request. To grant the &mut, it pops the HashMap's permission.
4. The Crash: If we then try to access that key via the map, Miri halts execution with:

error: Undefined Behavior: trying to retag from <tag> for SharedReadOnly permission...
but that tag does not exist in the borrow stack for this location

In a real-world release build, this could manifest as the HashMap returning None for a key that definitely exists, or returning garbage data because the compiler optimized away a reload from memory, assuming the value hadn't changed, while the aliasing pointer did change it.

You might be thinking, "Okay, so it's a theoretical violation of an experimental memory model. Who cares?" You should. Rust's safety guarantees are the only thing stopping it from being just C++ with uglier syntax. When you violate soundness rules, you break the contract with the compiler.

Consequences:

• Miscompilation: LLVM is aggressive. If it deduces that two pointers cannot alias (because you created a &mut), it might reorder instructions. It might move a write after a read, assuming they are independent. This leads to logical bugs that are impossible to debug with a debugger because the source code looks correct.
• Memory Corruption: In complex scenarios, if the lru cache is used in a multi-threaded context (even with Mutexes) or in async code, this pointer invalidation could lead to use-after-free scenarios if the compiler emits code that frees memory it thinks is dead.
• Security Vulnerabilities: If an attacker can trigger this state where the map and the list disagree on the validity of memory, they might be able to trick the application into overwriting valid data or reading sensitive memory leftovers.

The remediation is straightforward: Update lru to version 0.13.0. The maintainers have patched the iterator logic to respect Stacked Borrows.

For developers writing unsafe Rust, this is a wake-up call. You cannot simply trust that "it works on my machine." The x86 processor is forgiving; the Rust abstract machine is not.

Actionable Advice:

1. Audit unsafe blocks: If you are casting raw pointers to references (& or &mut), ask yourself: "Does anyone else have a pointer to this?"
2. Use Miri: CI pipelines for Rust projects using unsafe should include a cargo miri test step. It is the only reliable way to catch these kinds of aliasing violations before they turn into CVEs.
3. Avoid Self-References: If possible, use indices (like Vec indices) instead of pointers for graph-like structures. It's slower, but it keeps the borrow checker happy and your nights sleepless-free.