CVE-2021-25900: Rust smallvec heap overflow

SmallVec::insert_many trusted size_hint’s lower bound; if an iterator yielded more, it overflowed the heap buffer. Fixed in 0.6.14 and 1.6.1.

💡 Plain English Explainer (ELI5)

A warehouse is famously safe because a robot double-checks every shelf before anything is placed on it. For a few specific tasks the robot is switched off and a human works by hand, promising to be careful. One of those humans asked a delivery driver "roughly how many boxes are you bringing?", built a shelf that size, and started stacking. The driver's estimate was a guess, not a guarantee — and when more boxes arrived than promised, the stack ran off the end of the shelf.

Core Concepts & Subsystem Terms

SmallVec: A Rust collection that keeps a small number of elements inline and moves to a heap buffer when it grows. Its speed comes from unsafe code that manages that buffer by hand.
size_hint: An Iterator method that reports estimated lower and upper bounds on how many items remain. It is a hint: safe code may return any value, even a wrong one.
Unsafe Rust: Code inside an unsafe block may do things the compiler cannot check, such as writing through raw pointers; the author must uphold memory safety for every possible safe caller.
Soundness: A safe API is sound if no safe code, however unusual, can cause undefined behaviour through it. insert_many was unsound because a legal size_hint could corrupt memory.

Framework mappings

CWE reference for the weakness described in this guide: CWE-122 CWE-787

Incident Timeline

2021-01-08

Yechan Bae and the Rust group at Georgia Tech's SSLab report the bug; RustSec publishes RUSTSEC-2021-0003 and smallvec 0.6.14 and 1.6.1 ship the fix.

2021-01

CVE-2021-25900 is assigned; cargo audit starts flagging affected versions in dependency trees.

Step-by-Step Attack Flow

Step 1

An iterator under-reports its length

insert_many is called with an iterator whose size_hint lower bound is smaller than the number of items it actually yields. Safe code is allowed to do this.

Step 2

Space is reserved from the hint

insert_many reserves room for the lower bound only and shifts existing elements by that amount.

Step 3

Every item is written anyway

Inside an unsafe block the loop writes each item through a raw pointer, so extra items land past the end of the allocation.

Step 4

The heap is corrupted

The overflow overwrites neighbouring heap memory. Programs that pass iterators influenced by untrusted input to insert_many are exposed.

Source Code: Flaw vs. Secure Implementation

UNPATCHED FLAW

// Allocate based on a *hint*...
let (lower, _) = iter.size_hint();
self.reserve(lower);

unsafe {
    let ptr = self.as_mut_ptr().add(index);
    for (i, item) in iter.enumerate() {
        // ...but write however many
        // items actually arrive.
        ptr::write(ptr.add(i), item);
    }
}

HARDENED SECURE PATCH

// Re-check capacity for every item.
// Never let a value from safe code
// determine a bound used by unsafe.
for (i, item) in iter.enumerate() {
    self.reserve(1);
    unsafe {
        let ptr = self.as_mut_ptr()
                      .add(index + i);
        ptr::write(ptr, item);
    }
}

// The real fix also shrank the
// unsafe surface substantially.

Engineering & System Hardening Checklist

✓Never size a buffer used by unsafe code from a safe trait method such as size_hint, len on a trait object, or a comparator; re-check capacity before each write.
✓Write a // SAFETY: comment for every unsafe block stating the invariant it relies on, and reject reviews where the invariant depends on untrusted safe code.
✓Run Miri in CI on tests that use adversarial implementations, such as an iterator whose size_hint lies, a Drop that panics and a non-total comparator.
✓Keep unsafe blocks as small as possible; the smallvec fix also reduced the amount of unsafe code in insert_many so it could be verified.
✓Run cargo audit (or cargo deny) in CI so dependencies with RustSec advisories, like smallvec before 0.6.14 or 1.6.1, fail the build.