Stack-buffer-overflow in HashTable Struct

[ydongyeon]

Summary

An unsafe memory access vulnerability in the get_bucket method of the HashTable struct allows arbitrary memory access, potentially triggering undefined behavior, even if it is protected by assert function.

Details

Hi,

First, I want to extend my gratitude for maintaining this excellent crate. I’ve identified a potential security vulnerability: Stack-buffer-overflow.

Environment:

• OS: Ubuntu 22.04.4 LTS
• Rust Compiler: rustc 1.83.0-nightly (9c01301c5, 2024-09-05)
• Cargo: cargo 1.83.0-nightly (c1fa840a8, 2024-08-29)
• xmas-elf: Latest version (commit 7011c19, 2024-08-29)

Steps to reproduce:

(1) Replace xmas-elf/src/hash.rs with the modified hash.rs file as below.

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_hash() {
        let buckets = [100, 200, 300, 400, 500]; 
        let hash_table = HashTable {
            bucket_count: buckets.len() as u32,
            chain_count: 0, 
            first_bucket: buckets[0], 
        };
        println!("{:?}", hash_table.get_bucket(0));
        println!("{:?}", hash_table.get_bucket(1));

    }

}

(2) Run the test using the ASan flag.

RUSTFLAGS="-Zsanitizer=address" cargo +nightly test test_hash --target x86_64-unknown-linux-gnu -- --nocapture

---

Details:
// xmas-elf/src/hash.rs

pub fn get_bucket(&self, index: u32) -> u32 {
    assert!(index < self.bucket_count);
    unsafe {
        let ptr = (&self.first_bucket as *const u32).offset(index as isize);
        *ptr
    }
}

In this case, the get_bucket method within the HashTable struct uses the unsafe keyword to access memory with assert function protection. However, it is still vulnerable because bucket_count and index values can be manipulated by users. When bucket_count is set bigger value than first_bucket's actual length, it can lead to invalid memory access which violates Rust’s memory safety guarantees. Also, as hash.rs is public module, it can be used externally, which means that it is an actual vulnerability.

Actual results :
running 1 test
==1322584==ERROR: AddressSanitizer: stack-buffer-overflow on address 0x7ffff42ff12c at pc 0x55555566e171 bp 0x7ffff4cfe340 sp 0x7ffff4cfe338
READ of size 4 at 0x7ffff42ff12c thread T1
#0 0x55555566e170 in xmas_elf::hash::HashTable::get_bucket::h3f7b0479b638b3dc /home/dy3199/Fuzzing-Test/xmas-elf/src/hash.rs:32:13
#1 0x555555670dd1 in xmas_elf::hash::tests::test_hash::h967f7adbdf25ce34 /home/dy3199/Fuzzing-Test/xmas-elf/src/hash.rs:66:26
#2 0x55555566d7c6 in xmas_elf::hash::tests::test_hash::$u7b$$u7b$closure$u7d$$u7d$::h598a27a44dc720e4 /home/dy3199/Fuzzing-Test/xmas-elf/src/hash.rs:58:19
#3 0x55555566d465 in core::ops::function::FnOnce::call_once::h9e81445744e0ef01 /home/dy3199/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/core/src/ops/function.rs:250:5
#4 0x5555556b0a0a in core::ops::function::FnOnce::call_once::h556141b0b8fdbb6d /rustc/18b1161ec9eeab8927f91405bca0ddf59a4a26c9/library/core/src/ops/function.rs:250:5
#5 0x5555556b0a0a in test::__rust_begin_short_backtrace::h0db03bcef8350635 /rustc/18b1161ec9eeab8927f91405bca0ddf59a4a26c9/library/test/src/lib.rs:621:18
#6 0x5555556b0337 in test::run_test_in_process::$u7b$$u7b$closure$u7d$$u7d$::h2b26e78103d00faf /rustc/18b1161ec9eeab8927f91405bca0ddf59a4a26c9/library/test/src/lib.rs:644:60
#7 0x5555556b0337 in $LT$core..panic..unwind_safe..AssertUnwindSafe$LT$F$GT$$u20$as$u20$core..ops..function..FnOnce$LT$$LP$$RP$$GT$$GT$::call_once::h9b9bdb051f35126f /rustc/18b1161ec9eeab8927f91405bca0ddf59a4a26c9/library/core/src/panic/unwind_safe.rs:272:9
#8 0x5555556b0337 in std::panicking::try::do_call::he60eac3431009064 /rustc/18b1161ec9eeab8927f91405bca0ddf59a4a26c9/library/std/src/panicking.rs:557:40
#9 0x5555556b0337 in std::panicking::try::h557550d22ddb3954 /rustc/18b1161ec9eeab8927f91405bca0ddf59a4a26c9/library/std/src/panicking.rs:520:19
#10 0x5555556b0337 in std::panic::catch_unwind::hdcc5278601cde996 /rustc/18b1161ec9eeab8927f91405bca0ddf59a4a26c9/library/std/src/panic.rs:358:14
#11 0x5555556b0337 in test::run_test_in_process::h8aa3c0adb7acfe05 /rustc/18b1161ec9eeab8927f91405bca0ddf59a4a26c9/library/test/src/lib.rs:644:27
#12 0x5555556b0337 in test::run_test::$u7b$$u7b$closure$u7d$$u7d$::he4cb7f7454d67ec7 /rustc/18b1161ec9eeab8927f91405bca0ddf59a4a26c9/library/test/src/lib.rs:565:43
#13 0x555555674553 in test::run_test::_$u7b$$u7b$closure$u7d$$u7d$::hbf7c34f88a9b7c99 /rustc/18b1161ec9eeab8927f91405bca0ddf59a4a26c9/library/test/src/lib.rs:595:41

...

SUMMARY: AddressSanitizer: stack-buffer-overflow /home/dy3199/Fuzzing-Test/xmas-elf/src/hash.rs:32:13 in xmas_elf::hash::HashTable::get_bucket::h3f7b0479b638b3dc
Shadow bytes around the buggy address:
0x7ffff42fee80: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x7ffff42fef00: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x7ffff42fef80: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x7ffff42ff000: f1 f1 f1 f1 04 f2 00 00 f2 f2 00 00 00 00 00 00
0x7ffff42ff080: f2 f2 f2 f2 f8 f2 f8 f8 f2 f2 f8 f8 f8 f8 f8 f8
=>0x7ffff42ff100: f2 f2 f2 f2 00[04]f3 f3 00 00 00 00 00 00 00 00
0x7ffff42ff180: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x7ffff42ff200: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x7ffff42ff280: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x7ffff42ff300: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x7ffff42ff380: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
Shadow byte legend (one shadow byte represents 8 application bytes):
Addressable: 00
Partially addressable: 01 02 03 04 05 06 07
Heap left redzone: fa
Freed heap region: fd
Stack left redzone: f1
Stack mid redzone: f2
Stack right redzone: f3
Stack after return: f5
Stack use after scope: f8
Global redzone: f9
Global init order: f6
Poisoned by user: f7
Container overflow: fc
Array cookie: ac
Intra object redzone: bb
ASan internal: fe
Left alloca redzone: ca
Right alloca redzone: cb
==1314890==ABORTING

Recommended Patch:
Given the potential memory safety issues, I would suggest: Providing safe HashTable constructor that sets bucket_count and first_bucket's length equally.

Impact

The get_bucket method in the HashTable struct of the xmas-elf introduces an unsafe vulnerability by allowing arbitrary memory access without proper bounds checking. This flaw can lead to undefined behavior.

Although these bugs may be difficult to exploit in practice, I understand that the Rust community reports such issues to RUSTSEC in an effort to further enhance memory safety. Rust considers these issues critical to memory safety, regardless of whether they have been exploited, and takes proactive measures to either fix or report them. I have included references to similar cases below for your consideration.

Panic on overflow in subtraction
RUSTSEC-2023-0078
RUSTSEC-2022-0078
RUSTSEC-2022-0012
RUSTSEC-2021-0122