Undefined behavior from stack overflow on wasm32 targets

On wasm32 targets, a stack overflow might cause the invalid reads or writes to the upper addresses of Wasm memory leading to undefined behavior. The issue here is that LLVM produces a shadow stack (for values which are required to have an address) which uses the first 1 MiB of Wasm memory and grows down (to lower addresses). Since the top of this stack is stored as Wasm i32 global, it can underflow and cause the stack to corrupt heap memory if the Wasm module has grown memory to the maximum 4 GiB.

Here is an example (full repo available here):

const SIZE: usize = 16;

fn overflow_stack(count: u64, prev: &mut [[u8; SIZE]; SIZE]) -> u8 {
    let mut next = [[0; SIZE]; SIZE];
    next[0][0] = 0xab;
    let _dummy = [0_i32; SIZE];
    if count == 0 {
        return prev[0][0];
    }
    overflow_stack(count - 1, &mut next)
}

fn allocate_zeros() -> Vec<Vec<u8>> {
    let mut vecs = vec![];
    let mut current_max = 0;
    loop {
        let mut new_vec: Vec<u8> = Vec::new();
        if let Err(_) = new_vec.try_reserve_exact(4096) {
            println!("current highest address {:x}", current_max);
            break;
        }
        new_vec.extend_from_slice(&[0; 4096]);
        if new_vec.as_ptr() as usize > current_max {
            current_max = new_vec.as_ptr() as usize;
        }
        vecs.push(new_vec);
    }
    loop {
        let mut new_vec: Vec<u8> = Vec::new();
        if let Err(_) = new_vec.try_reserve_exact(1) {
            println!("current highest address {:x}", current_max);
            break;
        }
        new_vec.extend_from_slice(&[0; 1]);
        if new_vec.as_ptr() as usize > current_max {
            current_max = new_vec.as_ptr() as usize;
        }
        vecs.push(new_vec);
    }
    vecs
}

#[no_mangle]
pub fn main() {
    let vecs = allocate_zeros();
    // Stack preloader
    // Useful for aligning offset before underflow
    let _dummy = [0_i32; 368 * 500 + 364];

    let mut init = [[0_u8; SIZE]; SIZE];
    let count = 900;
    overflow_stack(count, &mut init);

    println!("checking vecs");
    for v in vecs {
        for b in v {
            assert_eq!(b, 0, "Vector has non-zero value 0x{:x}", b);
        }
    }
}

I expected to see this happen:
Since all the vectors created in allocate_zeros are initialized to 0 and the vectors are immutable, the final assertion should pass.

Instead, this happened:
Compiling this in debug mode to wasm32-wasi or wasm32-unknown-unknown targets and running it in most Wasm engines causes the assertion to fail:

thread '<unnamed>' panicked at src/lib.rs:61:13:
assertion `left == right` failed: Vector has non-zero value 0xab
  left: 171
 right: 0

This occurs because stack_overflow has caused the shadow stack to write into heap memory.

Meta

rustc --version --verbose:

rustc 1.78.0 (9b00956e5 2024-04-29)
binary: rustc
commit-hash: 9b00956e56009bab2aa15d7bff10916599e3d6d6
commit-date: 2024-04-29
host: x86_64-unknown-linux-gnu
release: 1.78.0
LLVM version: 18.1.2

The error occurs when running the Wasm in wasmtime, wasmedge, Firefox, Chrome, Safari, and Node with the default settings.

Proposed Solution

One possible fix that would catch many of these cases without imposing additional costs would be to generate a maximum size of 65535 Wasm pages for the main memory (one less than the default maximum of 65536). This would essentially create a 64 KiB guard page to catch stack overflows.

We'd be happy to help with implementing such a change.

cc @venkkatesh-sekar

Start by reproducing the failure with the linked wasm-underflow example on wasm32-wasi or wasm32-unknown-unknown in the listed Wasm engines. Then trace wasm32 memory-limit handling and the shadow-stack setup in the compiler and LLVM integration. Done should prevent stack overflow from corrupting heap memory, with the example's vector assertions remaining valid.