Unsoundness in `num_bits_sorted` and `num_bits_strictly_sorted`

[shinmao]

Intro to Unsoundness

Hello, we are PhD researchers focusing on Rust from George Mason University. While we are doing some code auditing on the usage of unsafe code, we found the unsoundness behind the safe API methods num_bits_sorted and num_bits_strictly_sorted, which could both trigger undefined behavior when called with slices shorter than expected BLOCK_LEN. This violate Rust's safety guarantees, as safe code should never cause undefined behaviors.

Root cause

bitpacking/src/macros_simple.rs

Lines 424 to 438 in eec95b2

	unsafe fn num_bits_sorted(initial: u32, decompressed: &[u32]) -> u8 {
	let initial_vec = set1(initial as i32);
	let data: *const DataType = decompressed.as_ptr().cast::<DataType>();
	let first = load_unaligned(data);
	let mut accumulator = compute_delta(load_unaligned(data), initial_vec);
	let mut previous = first;
	for i in 1..31 {
	let current = load_unaligned(data.add(i));
	let delta = compute_delta(current, previous);
	accumulator = op_or(accumulator, delta);
	previous = current;
	}
	let current = load_unaligned(data.add(31));

load_unaligned here could access the memory without checking bound. num_bits_strictly_sorted also has the same issue.

PoC

use bitpacking::{BitPacker, BitPacker4x};

fn main() {
    let bitpacker = BitPacker4x::new();

    // BitPacker4x:: BLOCK_LEN = 128 while only 10 elements given
    let data = vec![1u32; 10];

    println!("Testing num_bits_sorted with {} elements (expected {})",
             data.len(), BitPacker4x::BLOCK_LEN);

    // let result = bitpacker. num_bits_sorted(0, &data);
    // println!("Result: {}", result);

    println!("\nTesting num_bits_strictly_sorted.. .");
    let result2 = bitpacker.num_bits_strictly_sorted(Some(0), &data);
    println!("Result: {}", result2);
}

when run with Miri,

error: Undefined Behavior: memory access failed: attempting to access 16 bytes, but got alloc233+0x20 which is only 8 bytes from the end of the allocation
  --> /home/user/.cargo/registry/src/index.crates.io-1949cf8c6b5b557f/bitpacking-0.9.2/src/bitpacker4x_simple.rs:55:9
   |
55 |         ptr::read_unaligned(addr)
   |         ^^^^^^^^^^^^^^^^^^^^^^^^^ Undefined Behavior occurred here
   |

Affected impls

All BitPacker implementations are affected: BitPacker1x, BitPacker4x, and BitPacker8x.

Suggestion

We find that num_bits have done the proper validation by adding assert_eq!, so these two functions could follow the same ways to fix the bugs.