'merge_sort::merge()' crashes with double-free for T: Drop

[JOE1994]

Hello,
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

The implementation of merge_sort::merge() freely duplicates ownership of items from list, and invokes drop of the duplicated items via list[k] = ...

Also, panic within compare() can trigger double-free of items whose ownership was duplicated via .read().

algorithmica/algorithmica/src/sort/merge_sort.rs

Lines 9 to 55 in d8fef16

	fn merge<T: Debug, F>(list: &mut [T], start: usize, mid: usize, end: usize, compare: &F)
	where
	F: Fn(&T, &T) -> bool,
	{
	let mut left = Vec::with_capacity(mid - start + 1);
	let mut right = Vec::with_capacity(end - mid);
	unsafe {
	let mut start = start;
	while start <= mid {
	left.push(get_by_index(list, start as isize).read());
	start += 1;
	}
	while start <= end {
	right.push(get_by_index(list, start as isize).read());
	start += 1;
	}
	}
	let mut left_index = 0;
	let mut right_index = 0;
	let mut k = start;
	unsafe {
	while left_index < left.len() && right_index < right.len() {
	if compare(&left[left_index], &right[right_index]) {
	list[k] = get_by_index(&left, left_index as isize).read();
	left_index += 1;
	} else {
	list[k] = get_by_index(&right, right_index as isize).read();
	right_index += 1;
	}
	k += 1;
	}
	while left_index < left.len() {
	list[k] = get_by_index(&left, left_index as isize).read();
	left_index += 1;
	k += 1;
	}
	while right_index < right.len() {
	list[k] = get_by_index(&right, right_index as isize).read();
	right_index += 1;
	k += 1;
	}
	}
	}

Reproduction

Below is an example program that exhibits undefined behavior using safe APIs of algorithmica. Simply calling merge_sort::sort() on an array of T: Drop triggers
double-free.

Show Detail

#![forbid(unsafe_code)]
use algorithmica::sort::merge_sort::sort;

fn main() {
    let mut arr = vec![
        String::from("Hello"),
        String::from("World"),
        String::from("Rust"),
    ];

    // Calling `merge_sort::sort` on an array of `T: Drop` triggers double drop
    algorithmica::sort::merge_sort::sort(&mut arr);
    dbg!(arr);
}

Output:

free(): double free detected in tcache 2

Terminated with signal 6 (SIGABRT)

Tested Environment

• Crate: algorithmica
• Version: 0.1.8
• OS: Ubuntu 18.04.5 LTS
• Rustc version: rustc 1.50.0 (cb75ad5db 2021-02-10)

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

[yvt]

Why was this issue closed?

[andersk]

This still reproduces with the given test case using the current release on crates.io (algorithmica 0.1.9) or the current Git master (e066a5e). Please reopen.

[AbrarNitk]

@yvt, It is closed by mistake.