`Lru` stores dangling key pointers and triggers stack-use-after-scope.

[kaixinlalala]

Description:

The issue happens because Lru stores raw pointers to keys inside its internal HashMap. During push, the stored KeyRef points to the local key variable in Lru::push, not to the key stored inside the linked-list node. After push returns, that stack variable is no longer valid, but the HashMap may still dereference it during hashing or equality checks.

Environment:

algorithmica version: 0.1.10
rustc version: 1.94.1
OS: Ubuntu 20.04.6 LTS
Command:

RUSTFLAGS="-Z sanitizer=address" cargo +nightly run --target x86_64-unknown-linux-gnu

PoC

extern crate algorithmica;

fn main() {
    let mut lru = algorithmica::lru::Lru::<String, i32>::new(2);
    lru.push("alpha".to_string(), 1);
    println!("{:?}", lru.get(&"alpha".to_string()));
}

Expected behavior:

The program should run successfully and print:

Some(1)

Actual behavior

==143360==ERROR: AddressSanitizer: stack-use-after-scope on address 0x7b0d5c9de0c8 at pc 0x55f8eaf6f0f8 bp 0x7ffc4ef7b810 sp 0x7ffc4ef7b808
READ of size 8 at 0x7b0d5c9de0c8 thread T0
    #0 0x55f8eaf6f0f7  (/Rust-Lib-Testing/replay_files/algorithmica-0.1.10/replay_algorithmica1/target/x86_64-unknown-linux-gnu/debug/replay_algorithmica1+0x11a0f7) (BuildId: d7238e595cdde57240dd3f9b79aa7462ad24209b)
    #1 0x55f8eaf6f392  (/Rust-Lib-Testing/replay_files/algorithmica-0.1.10/replay_algorithmica1/target/x86_64-unknown-linux-gnu/debug/replay_algorithmica1+0x11a392) (BuildId: d7238e595cdde57240dd3f9b79aa7462ad24209b)
    #2 0x55f8eaf67a33  (/Rust-Lib-Testing/replay_files/algorithmica-0.1.10/replay_algorithmica1/target/x86_64-unknown-linux-gnu/debug/replay_algorithmica1+0x112a33) (BuildId: d7238e595cdde57240dd3f9b79aa7462ad24209b)
    #3 0x55f8eaf67861  (/Rust-Lib-Testing/replay_files/algorithmica-0.1.10/replay_algorithmica1/target/x86_64-unknown-linux-gnu/debug/replay_algorithmica1+0x112861) (BuildId: d7238e595cdde57240dd3f9b79aa7462ad24209b)
    #4 0x55f8eaf6a872  (/Rust-Lib-Testing/replay_files/algorithmica-0.1.10/replay_algorithmica1/target/x86_64-unknown-linux-gnu/debug/replay_algorithmica1+0x115872) (BuildId: d7238e595cdde57240dd3f9b79aa7462ad24209b)
    #5 0x55f8eaf5fa59  (/Rust-Lib-Testing/replay_files/algorithmica-0.1.10/replay_algorithmica1/target/x86_64-unknown-linux-gnu/debug/replay_algorithmica1+0x10aa59) (BuildId: d7238e595cdde57240dd3f9b79aa7462ad24209b)
    #6 0x55f8eaf5e53b  (/Rust-Lib-Testing/replay_files/algorithmica-0.1.10/replay_algorithmica1/target/x86_64-unknown-linux-gnu/debug/replay_algorithmica1+0x10953b) (BuildId: d7238e595cdde57240dd3f9b79aa7462ad24209b)
    #7 0x55f8eaf6a6c0  (/Rust-Lib-Testing/replay_files/algorithmica-0.1.10/replay_algorithmica1/target/x86_64-unknown-linux-gnu/debug/replay_algorithmica1+0x1156c0) (BuildId: d7238e595cdde57240dd3f9b79aa7462ad24209b)
    #8 0x55f8eaf6f3f2  (/Rust-Lib-Testing/replay_files/algorithmica-0.1.10/replay_algorithmica1/target/x86_64-unknown-linux-gnu/debug/replay_algorithmica1+0x11a3f2) (BuildId: d7238e595cdde57240dd3f9b79aa7462ad24209b)
    #9 0x55f8eaf64fca  (/Rust-Lib-Testing/replay_files/algorithmica-0.1.10/replay_algorithmica1/target/x86_64-unknown-linux-gnu/debug/replay_algorithmica1+0x10ffca) (BuildId: d7238e595cdde57240dd3f9b79aa7462ad24209b)
    #10 0x55f8eaf6948f  (/Rust-Lib-Testing/replay_files/algorithmica-0.1.10/replay_algorithmica1/target/x86_64-unknown-linux-gnu/debug/replay_algorithmica1+0x11448f) (BuildId: d7238e595cdde57240dd3f9b79aa7462ad24209b)
    #11 0x55f8eaf67e0a  (/Rust-Lib-Testing/replay_files/algorithmica-0.1.10/replay_algorithmica1/target/x86_64-unknown-linux-gnu/debug/replay_algorithmica1+0x112e0a) (BuildId: d7238e595cdde57240dd3f9b79aa7462ad24209b)
    #12 0x55f8eaf60efd  (/Rust-Lib-Testing/replay_files/algorithmica-0.1.10/replay_algorithmica1/target/x86_64-unknown-linux-gnu/debug/replay_algorithmica1+0x10befd) (BuildId: d7238e595cdde57240dd3f9b79aa7462ad24209b)
    #13 0x55f8eaf6b380  (/Rust-Lib-Testing/replay_files/algorithmica-0.1.10/replay_algorithmica1/target/x86_64-unknown-linux-gnu/debug/replay_algorithmica1+0x116380) (BuildId: d7238e595cdde57240dd3f9b79aa7462ad24209b)
    #14 0x55f8eaf967f5  (/Rust-Lib-Testing/replay_files/algorithmica-0.1.10/replay_algorithmica1/target/x86_64-unknown-linux-gnu/debug/replay_algorithmica1+0x1417f5) (BuildId: d7238e595cdde57240dd3f9b79aa7462ad24209b)
    #15 0x55f8eaf6b2ef  (/Rust-Lib-Testing/replay_files/algorithmica-0.1.10/replay_algorithmica1/target/x86_64-unknown-linux-gnu/debug/replay_algorithmica1+0x1162ef) (BuildId: d7238e595cdde57240dd3f9b79aa7462ad24209b)
    #16 0x55f8eaf696ad  (/Rust-Lib-Testing/replay_files/algorithmica-0.1.10/replay_algorithmica1/target/x86_64-unknown-linux-gnu/debug/replay_algorithmica1+0x1146ad) (BuildId: d7238e595cdde57240dd3f9b79aa7462ad24209b)
    #17 0x7f0d5e50a082  (/lib/x86_64-linux-gnu/libc.so.6+0x24082) (BuildId: 5792732f783158c66fb4f3756458ca24e46e827d)
    #18 0x55f8eaea1d2d  (/Rust-Lib-Testing/replay_files/algorithmica-0.1.10/replay_algorithmica1/target/x86_64-unknown-linux-gnu/debug/replay_algorithmica1+0x4cd2d) (BuildId: d7238e595cdde57240dd3f9b79aa7462ad24209b)

Address 0x7b0d5c9de0c8 is located in stack of thread T0 at offset 200 in frame
    #0 0x55f8eaf6926f  (/Rust-Lib-Testing/replay_files/algorithmica-0.1.10/replay_algorithmica1/target/x86_64-unknown-linux-gnu/debug/replay_algorithmica1+0x11426f) (BuildId: d7238e595cdde57240dd3f9b79aa7462ad24209b)

  This frame has 6 object(s):
    [32, 48) '_16' (line 6)
    [64, 80) 'args' (line 6)
    [96, 120) '_13' (line 6)
    [160, 168) '_10' (line 6)
    [192, 216) '_4' (line 5) <== Memory access at offset 200 is inside this variable
    [256, 336) 'lru' (line 4)
HINT: this may be a false positive if your program uses some custom stack unwind mechanism, swapcontext or vfork
      (longjmp and C++ exceptions *are* supported)
SUMMARY: AddressSanitizer: stack-use-after-scope (/Rust-Lib-Testing/replay_files/algorithmica-0.1.10/replay_algorithmica1/target/x86_64-unknown-linux-gnu/debug/replay_algorithmica1+0x11a0f7) (BuildId: d7238e595cdde57240dd3f9b79aa7462ad24209b) 
Shadow bytes around the buggy address:
  0x7b0d5c9dde00: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x7b0d5c9dde80: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x7b0d5c9ddf00: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x7b0d5c9ddf80: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x7b0d5c9de000: f1 f1 f1 f1 f8 f8 f2 f2 f8 f8 f2 f2 00 00 00 f2
=>0x7b0d5c9de080: f2 f2 f2 f2 00 f2 f2 f2 f8[f8]f8 f2 f2 f2 f2 f2
  0x7b0d5c9de100: 00 00 00 00 00 00 00 00 00 00 f3 f3 f3 f3 f3 f3
  0x7b0d5c9de180: f3 f3 f3 f3 f3 f3 f3 f3 f3 f3 f3 f3 f3 f3 f3 f3
  0x7b0d5c9de200: f5 f5 f5 f5 f5 f5 f5 f5 f5 f5 f5 f5 f5 f5 f5 f5
  0x7b0d5c9de280: f5 f5 f5 f5 f5 f5 f5 f5 f5 f5 f5 f5 f5 f5 f5 f5
  0x7b0d5c9de300: f5 f5 f5 f5 f5 f5 f5 f5 f5 f5 f5 f5 f5 f5 f5 f5
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
==143360==ABORTING

Root cause:

The problem is in src/lru/mod.rs. KeyRef stores a raw pointer. Its Hash and PartialEq implementations dereference that pointer.

algorithmica/algorithmica/src/lru/mod.rs

Lines 162 to 176 in fa2f691

	struct KeyRef<K> {
	key: *const K,
	}
	impl<K: std::hash::Hash> std::hash::Hash for KeyRef<K> {
	fn hash<H: std::hash::Hasher>(&self, state: &mut H) {
	unsafe { (*self.key).hash(state) }
	}
	}
	impl<K: PartialEq> PartialEq for KeyRef<K> {
	fn eq(&self, other: &KeyRef<K>) -> bool {
	unsafe { (*self.key).eq(&*other.key) }
	}
	}

During insertion, Lru::push creates a KeyRef that points to the local key variable.

algorithmica/algorithmica/src/lru/mod.rs

Lines 209 to 211 in fa2f691

	let key_ref = KeyRef { key: &key };
	let node = self.dll.push_front(key, value);
	self.map.insert(key_ref, node);

After key is moved into the linked-list node, the original stack location is no longer valid.
However, the HashMap stores key_ref, so later HashMap operations may dereference a dangling stack pointer.