Buffer overflow in insert_many()

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)

Fix potential buffer overflow in `insert_many`

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.

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

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.)

Fix potential buffer overflow in `insert_many`

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.

Fix potential buffer overflow in `insert_many`

Auto merge of #254 - mbrubeck:overflow, r=emilio

Fixed in smallvec 0.6.14 and 1.6.1.

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

Update SmallVec to 1.6.1

Merge #2506

Update smallvec to 1.6

Update smallvec to 1.6.1

Navigation Menu

Repository navigation

Buffer overflow in `insert_many()` #252

Issue Description

Reproduction

Tested Environment

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

	/// 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);
	}

Buffer overflow in insert_many() #252

Description

Issue Description

Reproduction

Tested Environment

Activity

mbrubeck commented on Jan 8, 2021

qwaz commented on Jan 8, 2021

mbrubeck commented on Jan 8, 2021

qwaz commented on Jan 8, 2021

mbrubeck commented on Jan 8, 2021

Metadata

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Issue actions

Buffer overflow in `insert_many()` #252