Memory safety issues in compact::Vec

[Qwaz]

Hello, we have noticed a soundness issue and/or a potential security vulnerability in this crate while performing a security scan on crates.io.

Description

compact::Vec contains multiple memory safety issues.

1. It mishandles large capacity and causes out-of-bound access in 32-bit / allocator layout mismatch in 64-bit.
2. remove() is not panic-safe and causes double-free when an index larger than the length is provided.

Demonstration

• Crate: ordnung
• Version: 0.0.1
• OS: Ubuntu 18.04.5 LTS
• Rust: rustc 1.46.0 (04488afe3 2020-08-24)

#![forbid(unsafe_code)]

mod boilerplate;

use ordnung::compact::Vec as CompactVec;

struct DropDetector(u32);

impl Drop for DropDetector {
    fn drop(&mut self) {
        println!("Dropping {}", self.0);
    }
}

fn main() {
    boilerplate::init();

    #[cfg(target_pointer_width = "32")]
    {
        println!("1. OOB is possible because MASK_HI is 0 in 32-bit build.");

        boilerplate::trace_alloc(move || {
            let mut vec: Vec<u8> = Vec::with_capacity(1);
            vec.push(1);

            // https://github.com/maciejhirsz/ordnung/blob/e1f1e3bda332dae33b76ca4be00dba46265e4cbe/src/compact.rs#L281-L282
            // len / cap packing doesn't work in 32-bit environment and cap will be always zero.
            // Admittedly, this is not a real security threat as the code will scream and panic in the debug build.
            // However, it is still a soundness issue since it allows UB in safe Rust code.
            // This crate doesn't seem to support 32-bit, so it would be better to make it an error at the compile time.
            let mut compact_vec = CompactVec::from(vec);
            println!("pointer: {:p}", compact_vec.as_ptr());
            println!("len: {}", compact_vec.len());
            println!("capacity: {}", compact_vec.capacity());

            // https://github.com/maciejhirsz/ordnung/blob/e1f1e3bda332dae33b76ca4be00dba46265e4cbe/src/compact.rs#L48
            // Allows us to push elements over the boundary because `len != cap`
            for i in 0..4 {
                compact_vec.push(i);
                println!("Pushed {}", i);
            }
            println!("len: {}", compact_vec.len());
            println!("capacity: {}", compact_vec.capacity());

            // cap is 0, so no deallocation
        });
    }

    #[cfg(target_pointer_width = "64")]
    {
        println!("2. Allocator layout mismatch in 64-bit build with large capacity.");

        boilerplate::trace_alloc(|| {
            // https://github.com/maciejhirsz/ordnung/blob/e1f1e3bda332dae33b76ca4be00dba46265e4cbe/src/compact.rs#L35-L37
            // Allocation is done with capacity `(1 << 32) + 4`,
            let _ = CompactVec::<u8>::with_capacity((1 << 32) + 4);
            // https://github.com/maciejhirsz/ordnung/blob/e1f1e3bda332dae33b76ca4be00dba46265e4cbe/src/compact.rs#L185-L193
            // but deallocation is done with capacity `4`.
            // This may corrupt the internal state of the allocator, which can cause the memory safety violation.
        });
    }

    {
        println!("3. `Vec::remove()` causes double-free when panicking.");

        let mut compact_vec = CompactVec::with_capacity(32);
        compact_vec.push(DropDetector(123));
        compact_vec.push(DropDetector(456));

        // https://github.com/maciejhirsz/ordnung/blob/e1f1e3bda332dae33b76ca4be00dba46265e4cbe/src/compact.rs#L139-L152
        // Panic in line 144 frees a temporary vector created in line 142,
        // and the same vector is freed again when `compact_vec` is dropped while stack unwinding.
        compact_vec.remove(123);
    }
}

Output:

2. Allocator layout mismatch in 64-bit build with large capacity.
[TRACE] > alloc [address=0x7f9b011c0010, size=4294967300, align=1]
[TRACE] > dealloc [address=0x7f9b011c0010, size=4, align=1]
3. `Vec::remove()` causes double-free when panicking.
thread 'main' panicked at 'removal index (is 123) should be < len (is 2)', src/liballoc/vec.rs:1062:13
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace
Dropping 123
Dropping 456
Dropping 0
Dropping 0

Return Code: 101

[Qwaz]

Run result in 32-bit with cargo run --target i686-unknown-linux-musl --release

1. OOB is possible because MASK_HI is 0 in 32-bit build.
[TRACE] > alloc [address=0x9fb15d0, size=1, align=1]
pointer: 0x9fb15d0
len: 1
capacity: 0
Pushed 0
Pushed 1
Pushed 2
Pushed 3
len: 5
capacity: 0
3. `Vec::remove()` causes double-free when panicking.
thread 'main' panicked at 'removal index (is 123) should be < len (is 34)', src/liballoc/vec.rs:1062:13
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace
Dropping 134859000
Dropping 134859000
Dropping 0
Dropping 0
Dropping 0
Dropping 0
Dropping 0
Dropping 0
Dropping 0
Dropping 0
Dropping 0
Dropping 0
Dropping 0
Dropping 0
Dropping 0
Dropping 0
Dropping 0
Dropping 0
Dropping 0
Dropping 0
Dropping 0
Dropping 0
Dropping 0
Dropping 0
Dropping 0
Dropping 0
Dropping 0
Dropping 0
Dropping 0
Dropping 0
Dropping 0
Dropping 0
Dropping 123
Dropping 456
Dropping 134859000
Dropping 134859000
Dropping 0
Dropping 0
Dropping 0
Dropping 0
Dropping 0
Dropping 0
Dropping 0
Dropping 0
Dropping 0
Dropping 0
Dropping 0
Dropping 0
Dropping 0
Dropping 0
Dropping 0
Dropping 0
Dropping 0
Dropping 0
Dropping 0
Dropping 0
Dropping 0
Dropping 0
Dropping 0
Dropping 0
Dropping 0
Dropping 0
Dropping 0
Dropping 0
Dropping 0
Dropping 0
Dropping 123
Dropping 456

[Qwaz]

In addition, creating a reference that points to an invalid value is already an undefined behavior, even if it is not dereferenced.

ordnung/src/compact.rs

Line 161 in e1f1e3b

let ptr = slice_from_raw_parts_mut(ptr, len & MASK_LO | (cap & MASK_LO) << 32);

ordnung/src/compact.rs

Lines 295 to 298 in e1f1e3b

	NonNull::new_unchecked(slice_from_raw_parts_mut(
	ptr as *mut T,
	(len & MASK_LO) | ((capacity & MASK_LO) << 32),
	))

I don't see any location where [T] field is directly used. Maybe a tuple (*ptr: *mut T, len: u32, cap: u32) has the same semantics and the performance while less error-prone.