CVE-2021-31996

Vulnerability

The algorithmica crate (up to version 0.1.0, through 2021-03-07) contains a double-free vulnerability in the merge_sort::merge() function. The function copies items from the input slice into local vectors using read(), creating duplicate ownership. When it writes back to the list via list[k] = ..., the old value is dropped, potentially dropping the same value multiple times. Additionally, a panic within the comparison function compare() can trigger a double-free of items whose ownership was duplicated via read() [1]. This issue affects all versions of the crate prior to any patch (none exist) [3].

Exploitation

An attacker can exploit this vulnerability by providing a Vec where T implements the Drop trait and passing a comparison closure that panics. The panic during compare() will cause the function to unwind, dropping the local vectors that still hold duplicated ownership of elements, resulting in a double-free. No special privileges or network access are required; the attacker only needs to invoke the vulnerable function with appropriate types and a panic-causing comparison.

Impact

Successful exploitation leads to a double-free, which is undefined behavior in Rust. This can cause memory corruption, leading to program crashes, data corruption, or potentially arbitrary code execution. The RustSec advisory categorizes this as a memory-corruption issue [3].

Mitigation

As of the last advisory update (June 2023), no patched version of the algorithmica crate exists [3]. The crate appears unmaintained. The only mitigation is to avoid using the merge_sort::merge() function with types that implement Drop, or to replace the crate entirely with a safe alternative.