Memory safety issue in StackVec::extend

[ammaraskar]

Hi there, we (Rust group @sslab-gatech) are scanning crates on crates.io for potential soundness bugs. We noticed that in StackVec::extend, the size_hint's upper bound is used authoritatively to verify the capacity and then up to lower_bound elements are inserted directly into the StackVector:

rust-stackvector/src/lib.rs

Lines 897 to 915 in d0382d5

	let mut iter = iterable.into_iter();
	let (lower_bound, upper_bound) = iter.size_hint();
	let upper_bound = upper_bound.expect("iterable must provide upper bound.");
	assert!(self.len() + upper_bound <= self.capacity());
	unsafe {
	let len = self.len();
	let ptr = self.as_mut_ptr().padd(len);
	let mut count = 0;
	while count < lower_bound {
	if let Some(out) = iter.next() {
	ptr::write(ptr.padd(count), out);
	count += 1;
	} else {
	break;
	}
	}
	self.set_len(len + count);
	}

However, if an Iterator incorrectly reports a size_hint here with a upper bound smaller than the lower bound, it can cause that first loop to write beyond the capacity of the stack and overwrite the stack. Here's an example:

#![forbid(unsafe_code)]

use stackvector::StackVec;

// An iterator that reports an incorrect size hint.
// -----
struct IncorrectIterator(u32);

impl IncorrectIterator {
    pub fn new() -> Self { IncorrectIterator(0) }
}

impl Iterator for IncorrectIterator {
    type Item = u8;

    fn next(&mut self) -> Option<Self::Item> {
        self.0 += 1;
        if (self.0 >= 20) {
            None
        } else {
            Some(0x41)
        }
    }

    fn size_hint(&self) -> (usize, Option<usize>) {
        let lower_bound = 20;
        let upper_bound = Some(0);
        (lower_bound, upper_bound)
    }
}
// -----

fn main() {
    let mut stack_vec = StackVec::<[u8; 4]>::new();
    let i : i32 = 42;

    // Causes a stack overflow overwriting i.
    stack_vec.extend(IncorrectIterator::new());

    println!("i: {}", i);
    assert!(i == 42);
}

This outputs:

i: 1094795585
thread 'main' panicked at 'assertion failed: i == 42', src/main.rs:55:5
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace

Return code 101

As per the size_hint documentation:

It is not enforced that an iterator implementation yields the declared number of elements. A buggy iterator may yield less than the lower bound or more than the upper bound of elements.
size_hint() is primarily intended to be used for optimizations such as reserving space for the elements of the iterator, but must not be trusted to e.g., omit bounds checks in unsafe code. An incorrect implementation of size_hint() should not lead to memory safety violations.

[Shnatsel]

Heads up: this issue has been included in the RustSec advisory database. It will be surfaced by tools such as cargo-audit or cargo-deny from now on.

Once a fix is released to crates.io, please open a pull request to update the advisory with the patched version, or file an issue on the advisory database repository.

[plugwash]

Hi.

This bug has come to my attention because the Debian security team filed it as a release critical bug in response to the rustsec advisory and I am currently trying to keep the rust ecosystem in Debian testing/unstable in shape for the upcoming bullseye release.

while count < lower_bound {

Even if the hints are sane (i.e. lower_bound <= upper_bound) , this line just seems wrong to me, it seems that this method will only ever copy up to lower_bound elements from the iterator, despite having allocated space for upper_bound elements.

IMO it should be changed to.

while count < upper_bound {

but i'm no expert on this code so I would really like some feedback before proceeding to patch this in Debian.

[Alexhuszagh]

The Delay

@plugwash @Shnatsel Sorry for the lack of response, I've been taking a mental health break from open source work over the last year and had a few emergency maintainers doing minimal work on my projects. This isn't in practice an issue in the primary project using stack-vector (lexical, which provides sane size hints), but it is a security issue and should be patched soon.

I'll start working on a patch shortly, since this affects a few notable downstream projects. I've been meaning to move to bluss's arrayvec and yank all versions of this crate, however, I try to support older versions of Rustc which has been an issue with recent versions of arrayvec (that have features I wish to use).

Implementation Soundness (Or Lack Thereof)

@plugwash As for the actual implementation of extending from the iterator, the lower bound is the guarantee of the minimum length of the iterator, which we are then using to add items to the vector. If we have (lower, upper) = iter.size_hint();, and say lower == 3 and upper == 5, then we can only guarantee the iterator has 3 elements and then we iterate over and directly write this to uninitialized memory in the vector using ptr::write. In practice, this means that if let Some(out) = iter.next() should always be Some(out), and could produce more optimized code with a smart enough compiler. We then add all the remaining elements (in case there are more elements than lower in the iterator) by pushing them to the end of the vector, without any writes memory potentially exceeding the vector's bounds.

This was adapted from Servo's smallvec, which I believe had a similar security advisory.

The extended logic is effectively similar to this:

// Get an iterator object and get the bounds to do bounds-checking as few times as necessary.
let iter = iterable.into_iter();
let (lower, upper) = iter.size_hint();
// If we don't have an upper bound, this algorithm won't work
let upper= upper.expect("iterable must provide upper bound.");
// Ensure we have enough capacity in the vector to do direct writes to unintialized memory.
assert!(self.len() + upper_bound <= self.capacity());

// I'm eliding some unsafe blocks because the simplified functionality is more important, to explain the algorithm.
// Get a raw pointer to the `end` element, that is, 1-past the last element, and store a count for the number
// of elements.
let len = self.len();
let ptr = self.as_mut_ptr().padd(len);
let mut count = 0;

// Directly write as many elements as we know are guaranteed to be in the iterator, IE, the lower bound.
while count < lower_bound {
    // While this is true, if the size_hint is valid, this is guaranteed to not panic and the check could be theoretically elided.
    // Write this unsafely to the uninitialized memory and increment the count.
    let out = iter.next().unwrap();
    ptr::write(ptr.padd(count), out);
    count += 1;
}

// Add any extra elements in the iterator, as many as `upper - lower`.
for elem in iter {
    self.push(elem);
}

This is the line where the fundamental unsoundness comes from. If this pre-condition is true, then the rest of the algorithm is sound: however, there are no guarantees (within safe rust) the size_hint is valid.

assert!(self.len() + upper_bound <= self.capacity());

The lower bound effectively doesn't matter, since in the actual implementation, we just break the loop earlier if the lower bound provided is higher than the number of elements:

if let Some(out) = iter.next() {
    ptr::write(ptr.padd(count), out);
    count += 1;
} else {
    break;
}

[Alexhuszagh]

I'm pretty certain the only patch possible, since we depend on the trait Iterator (which has no intrinsic concept of its size) is the following:

impl<A: Array> Extend<A::Item> for StackVec<A> {
    fn extend<I: iter::IntoIterator<Item=A::Item>>(&mut self, iterable: I) {
        for elem in iter {
            self.push(elem);
        }
}

Not exactly optimal, but we could likely specialize it further for a TrustedLen iterator, which is currently not stable. Any other iterators depend on size_hint, which is not exactly safe.

[Alexhuszagh]

@Shnatsel @ammaraskar This commit should fix the above security issue. If you have any comments, please feel free to leave them. Tomorrow (or if the comments are positive), I'll increment the version, publish this to crates.io, ensure lexical is patched to use new versions of stackvector, yank the previous versions, and add a pull request on rust advisory-db.

[ammaraskar]

The fix commit looks good to me Alexander, thank you :)

[Alexhuszagh]

Ok this has been fixed, published to crates.io, and all prior versions have been yanked.