Buffer overflow in insert_many()

[Qwaz]

Hello fellow Rustacean,
we (Rust group @sslab-gatech) found a memory-safety/soundness issue in this crate while scanning Rust code on crates.io for potential vulnerabilities.

Issue Description

rust-smallvec/src/lib.rs

Lines 1009 to 1070 in 9cf1176

	/// Insert multiple elements at position `index`, shifting all following elements toward the
	/// back.
	pub fn insert_many<I: IntoIterator<Item = A::Item>>(&mut self, index: usize, iterable: I) {
	let iter = iterable.into_iter();
	if index == self.len() {
	return self.extend(iter);
	}
	let (lower_size_bound, _) = iter.size_hint();
	assert!(lower_size_bound <= core::isize::MAX as usize); // Ensure offset is indexable
	assert!(index + lower_size_bound >= index); // Protect against overflow
	self.reserve(lower_size_bound);
	unsafe {
	let old_len = self.len();
	assert!(index <= old_len);
	let start = self.as_mut_ptr();
	let mut ptr = start.add(index);
	// Move the trailing elements.
	ptr::copy(ptr, ptr.add(lower_size_bound), old_len - index);
	// In case the iterator panics, don't double-drop the items we just copied above.
	self.set_len(0);
	let mut guard = DropOnPanic {
	start,
	skip: index..(index + lower_size_bound),
	len: old_len + lower_size_bound,
	};
	let mut num_added = 0;
	for element in iter {
	let mut cur = ptr.add(num_added);
	if num_added >= lower_size_bound {
	// Iterator provided more elements than the hint. Move trailing items again.
	self.reserve(1);
	let start = self.as_mut_ptr();
	ptr = start.add(index);
	cur = ptr.add(num_added);
	ptr::copy(cur, cur.add(1), old_len - index);
	guard.start = start;
	guard.len += 1;
	guard.skip.end += 1;
	}
	ptr::write(cur, element);
	guard.skip.start += 1;
	num_added += 1;
	}
	mem::forget(guard);
	if num_added < lower_size_bound {
	// Iterator provided fewer elements than the hint
	ptr::copy(
	ptr.add(lower_size_bound),
	ptr.add(num_added),
	old_len - index,
	);
	}
	self.set_len(old_len + num_added);
	}

insert_many() overflows the buffer when an iterator yields more items than the lower bound of size_hint().

The problem is in line 1044. reserve(n) reserves capacity for n more elements to be inserted. This is done by comparing the length and the capacity. Since the length of the buffer is set to 0 in line 1032, line 1044 will be always no-op and the following code will overflow the buffer.

Reproduction

Below is an example program that exhibits undefined behavior using safe APIs of smallvec.

#![forbid(unsafe_code)]

use smallvec::SmallVec;

fn main() {
    let mut v: SmallVec<[u8; 0]> = SmallVec::new();

    // Spill on heap
    v.push(123);

    // Allocate string on heap
    let s = String::from("Hello!");
    println!("{}", s);

    // Prepare an iterator with small lower bound
    let mut iter = (0u8..=255).filter(|n| n % 2 == 0);
    assert_eq!(iter.size_hint().0, 0);

    // Triggering the bug
    v.insert_many(0, iter);

    // Uh oh, heap overflow made smallvec and string to overlap
    assert!(v.as_ptr_range().contains(&s.as_ptr()));

    // String is corrupted
    println!("{}", s);
}

Output:

Hello!
@BDFHJ
double free or corruption (out)

Terminated with signal 6 (SIGABRT)

Tested Environment

• Crate: smallvec
• Version: 1.6.0
• OS: Ubuntu 20.04.1 LTS
• Rustc version: rustc 1.48.0 (7eac88abb 2020-11-16)

[mbrubeck]

Thanks for the report! I have submitted a fix in #254. I can submit a RustSec advisory after the fixed version is released, or if you would like to write the advisory, that would be fine too.

[Qwaz]

I believe the bug is older than that. Passing 0 as index will call self.set_len(0) and trigger the same bug.

[mbrubeck]

You're right. This was introduced in #103, commit 26b2490, so it affects version 0.6.3 through 1.6.0.

(I deleted a previous comment where I said it was introduced in #213, because I realized it was wrong right after posting it.)

[Qwaz]

I agree that that commit introduced the bug. Thank you for the quick fix!
Regarding the RustSec advisory, I think it's better to be written by the crate maintainer if possible.

[mbrubeck]

Fixed in smallvec 0.6.14 and 1.6.1.

RustSec advisory submitted in rustsec/advisory-db#552.