Dropping Objects Created with IdMap::from_iter May Free Uninitialized Memory

[GeorgeAndrou]

Hello,

We are @purseclab, and we are fuzzing Rust crates to identify memory violation bugs. While analyzing this crate, we discovered that objects created with the IdMap::from_iter constructor may lead to deallocation of uninitialized memory.

The PoC below triggers a segmentation fault.

PoC:

#![forbid(unsafe_code)]

use id_map::*;
struct CustomType0(String);


fn main() {
    let mut entries = Vec::new();
    entries.push(CustomType0(String::from("Hello")));
    entries.push(CustomType0(String::from("World")));
    let _ = IdMap::from_iter(entries);
}

Bug Description:

The function IdMap::from_iter (see line 431) uses the capacity of the values vector to initialize the ids field of the resulting IdMap object.

id-map/src/lib.rs

Lines 425 to 438 in a2fa8d4

	impl<T> FromIterator<T> for IdMap<T> {
	#[inline]
	fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self {
	let mut values = Vec::from_iter(iter);
	unsafe { values.set_len(0) }
	let space = values.capacity();
	let ids = IdSet::new_filled(values.capacity());
	IdMap {
	values,
	space,
	ids,
	}
	}
	}

When the IdMap is dropped, the drop_values method is invoked to deallocate each element in the ids field.

id-map/src/lib.rs

Lines 326 to 330 in a2fa8d4

	unsafe fn drop_values(&mut self) {
	for id in &self.ids {
	ptr::drop_in_place(self.values.get_unchecked_mut(id))
	}
	}

However, drop_values iterates over ids and uses each id as an index into the values vector.
If values.len() < values.capacity(), then id may exceed the length of values, resulting in an attempt to drop uninitialized memory, leading to undefined behavior and a segmentation fault.

Output:

AddressSanitizer:DEADLYSIGNAL
=================================================================
==647802==ERROR: AddressSanitizer: SEGV on unknown address (pc 0x55a827600582 bp 0x000000000000 sp 0x7fff36f1d9c0 T0)
==647802==The signal is caused by a READ memory access.
==647802==Hint: this fault was caused by a dereference of a high value address (see register values below).  Disassemble the provided pc to learn which register was used.
    #0 0x55a827600582  (/home/user/id-map_from_iter_bug/target/debug/id-map_from_iter_bug+0x11582) (BuildId: dff809c9a31a3137db2de49565e329d1e844f67c)
    #1 0x55a8276863cb  (/home/user/id-map_from_iter_bug/target/debug/id-map_from_iter_bug+0x973cb) (BuildId: dff809c9a31a3137db2de49565e329d1e844f67c)
    #2 0x55a8276b10ff  (/home/user/id-map_from_iter_bug/target/debug/id-map_from_iter_bug+0xc20ff) (BuildId: dff809c9a31a3137db2de49565e329d1e844f67c)
    #3 0x55a8276c281c  (/home/user/id-map_from_iter_bug/target/debug/id-map_from_iter_bug+0xd381c) (BuildId: dff809c9a31a3137db2de49565e329d1e844f67c)
    #4 0x55a8276c1409  (/home/user/id-map_from_iter_bug/target/debug/id-map_from_iter_bug+0xd2409) (BuildId: dff809c9a31a3137db2de49565e329d1e844f67c)
    #5 0x55a8276c12f6  (/home/user/id-map_from_iter_bug/target/debug/id-map_from_iter_bug+0xd22f6) (BuildId: dff809c9a31a3137db2de49565e329d1e844f67c)
    #6 0x55a8276c1189  (/home/user/id-map_from_iter_bug/target/debug/id-map_from_iter_bug+0xd2189) (BuildId: dff809c9a31a3137db2de49565e329d1e844f67c)
    #7 0x55a8276c1419  (/home/user/id-map_from_iter_bug/target/debug/id-map_from_iter_bug+0xd2419) (BuildId: dff809c9a31a3137db2de49565e329d1e844f67c)
    #8 0x55a8276c3738  (/home/user/id-map_from_iter_bug/target/debug/id-map_from_iter_bug+0xd4738) (BuildId: dff809c9a31a3137db2de49565e329d1e844f67c)
    #9 0x55a8276c1d19  (/home/user/id-map_from_iter_bug/target/debug/id-map_from_iter_bug+0xd2d19) (BuildId: dff809c9a31a3137db2de49565e329d1e844f67c)
    #10 0x55a8276c1827  (/home/user/id-map_from_iter_bug/target/debug/id-map_from_iter_bug+0xd2827) (BuildId: dff809c9a31a3137db2de49565e329d1e844f67c)
    #11 0x55a8276c2f31  (/home/user/id-map_from_iter_bug/target/debug/id-map_from_iter_bug+0xd3f31) (BuildId: dff809c9a31a3137db2de49565e329d1e844f67c)
    #12 0x55a8276c111a  (/home/user/id-map_from_iter_bug/target/debug/id-map_from_iter_bug+0xd211a) (BuildId: dff809c9a31a3137db2de49565e329d1e844f67c)
    #13 0x55a8276c3f7d  (/home/user/id-map_from_iter_bug/target/debug/id-map_from_iter_bug+0xd4f7d) (BuildId: dff809c9a31a3137db2de49565e329d1e844f67c)
    #14 0x55a8276c33a4  (/home/user/id-map_from_iter_bug/target/debug/id-map_from_iter_bug+0xd43a4) (BuildId: dff809c9a31a3137db2de49565e329d1e844f67c)
    #15 0x55a8276ed3b0  (/home/user/id-map_from_iter_bug/target/debug/id-map_from_iter_bug+0xfe3b0) (BuildId: dff809c9a31a3137db2de49565e329d1e844f67c)
    #16 0x55a8276c324f  (/home/user/id-map_from_iter_bug/target/debug/id-map_from_iter_bug+0xd424f) (BuildId: dff809c9a31a3137db2de49565e329d1e844f67c)
    #17 0x55a8276c30cd  (/home/user/id-map_from_iter_bug/target/debug/id-map_from_iter_bug+0xd40cd) (BuildId: dff809c9a31a3137db2de49565e329d1e844f67c)
    #18 0x7ff7d4160d8f  (/lib/x86_64-linux-gnu/libc.so.6+0x29d8f) (BuildId: 490fef8403240c91833978d494d39e537409b92e)
    #19 0x7ff7d4160e3f  (/lib/x86_64-linux-gnu/libc.so.6+0x29e3f) (BuildId: 490fef8403240c91833978d494d39e537409b92e)
    #20 0x55a8275ff6f4  (/home/user/id-map_from_iter_bug/target/debug/id-map_from_iter_bug+0x106f4) (BuildId: dff809c9a31a3137db2de49565e329d1e844f67c)

AddressSanitizer can not provide additional info.
SUMMARY: AddressSanitizer: SEGV (/home/user/id-map_from_iter_bug/target/debug/id-map_from_iter_bug+0x11582) (BuildId: dff809c9a31a3137db2de49565e329d1e844f67c) 
==647802==ABORTING

How to Build and Run the PoC:

RUSTFLAGS="-Zsanitizer=address" cargo +nightly-2024-02-01-x86_64-unknown-linux-gnu run

Details:

• Compiler Version: rustc 1.77.0-nightly (11f32b73e 2024-01-31)
• Library Version: id-map-0.2.1
• OS: Ubuntu 22.04.5 LTS

[djc]

@andrewhickman friendly ping?

[andrewhickman]

@djc Version 0.2.2 removes all unsafe code and fixes this vulnerability.

I would generally recommend a more widely-used crate like https://crates.io/crates/slotmap or https://crates.io/crates/slab for this purpose.

[djc]

@andrewhickman awesome, thanks. Are you okay with publishing the advisory as proposed in rustsec/advisory-db#2366? Should the advisory include the recommendation to use your proposed alternatives?

[andrewhickman]

@djc Yes, I'm happy for that advisory to be published, and for it to include the suggested alternatives.