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

https://github.com/AbrarNitk/algorithmica/blob/d8fef1660e221eb4da0c97f3a8707239534d64cc/algorithmica/src/sort/merge_sort.rs#L9-L55

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 (e066a5ef332d724e3734ab9c16da92be4d1221f9). Please reopen.

[AbrarNitk]

@yvt, It is closed by mistake.