Use after free bug in lru crate

[oherrala]

I think I discovered use after free bug in lru crate. Code looked complicated for my skill level so better give you what I have before spending more time trying to understand everything. I tested this with both release 0.6.6 and git master (commit 09f68c6, same as 0.7.0 release?).

Consider this piece of code:

extern crate lru;

use lru::LruCache;

fn main() {
    let mut cache = LruCache::new(100);

    cache.put(1, String::from("Hello world"));
    cache.put(2, String::from("How are you?"));
    cache.put(3, String::from("It's a great day!"));

    for (key, value) in cache.iter() {
        cache.pop(key);
        println!("{}", value);
    }
}

This compiles fine, but when ran (in macOS) it crashed with segmentation fault:

% cargo run -q --example use-after-free
zsh: segmentation fault  cargo run -q --example use-after-free

The reason probably being that iterator gives us references to key and value, pop might remove and free the value, and then println tries to access the reference of value which is already dropped. However, I didn't take deep dive into lru source code yet so I'm not sure what pop actually does.

I ran this with Address Sanitizer (using git master) and got the following report:

% RUSTFLAGS="-Z sanitizer=address" cargo +nightly run --example use-after-free
   Compiling libc v0.2.102
   Compiling version_check v0.9.3
   Compiling cfg-if v1.0.0
   Compiling once_cell v1.8.0
   Compiling stats_alloc v0.1.8
   Compiling scoped_threadpool v0.1.9
   Compiling ahash v0.7.4
   Compiling getrandom v0.2.3
   Compiling hashbrown v0.11.2
   Compiling lru v0.7.0 (/Users/oherrala/rust/lru-rs)
    Finished dev [unoptimized + debuginfo] target(s) in 9.21s
     Running `/tmp/rust/target/debug/examples/use-after-free`
=================================================================
==31235==ERROR: AddressSanitizer: heap-use-after-free on address 0x604000000490 at pc 0x00010c700792 bp 0x7ffee35376d0 sp 0x7ffee35376c8
READ of size 8 at 0x604000000490 thread T0
    #0 0x10c700791 in alloc::raw_vec::RawVec$LT$T$C$A$GT$::ptr::h5b52a5e22cadae0b+0x31 (use-after-free:x86_64+0x100039791)
    #1 0x10c7006c0 in alloc::vec::Vec$LT$T$C$A$GT$::as_ptr::ha2d9c9e7d714e8da+0x10 (use-after-free:x86_64+0x1000396c0)
    #2 0x10c7006f4 in _$LT$alloc..vec..Vec$LT$T$C$A$GT$$u20$as$u20$core..ops..deref..Deref$GT$::deref::h6bb849d264bca999+0x14 (use-after-free:x86_64+0x1000396f4)
    #3 0x10c6f0ff0 in _$LT$alloc..string..String$u20$as$u20$core..ops..deref..Deref$GT$::deref::h7755ec760d24422c string.rs:2322
    #4 0x10c6f0fa8 in _$LT$alloc..string..String$u20$as$u20$core..fmt..Display$GT$::fmt::hca63d28c3617b69f string.rs:2137
    #5 0x10c6fb59b in _$LT$$RF$T$u20$as$u20$core..fmt..Display$GT$::fmt::haea6ded2ffff63ce mod.rs:2087
    #6 0x10c743e4a in core::fmt::write::h2d5ecb4b9764759c+0x1ca (use-after-free:x86_64+0x10007ce4a)
    #7 0x10c72caa2 in _$LT$$RF$std..io..stdio..Stdout$u20$as$u20$std..io..Write$GT$::write_fmt::hae817ec54eda9acf+0x72 (use-after-free:x86_64+0x100065aa2)
    #8 0x10c72d09d in std::io::stdio::_print::h47ad1a1323ba12e2+0x15d (use-after-free:x86_64+0x10006609d)
    #9 0x10c6f7359 in use_after_free::main::h958fdec6a3bbdb76 use-after-free.rs:14
    #10 0x10c6eb26d in core::ops::function::FnOnce::call_once::h02aaef19690c38dd function.rs:227
    #11 0x10c6f9573 in std::sys_common::backtrace::__rust_begin_short_backtrace::hc637aa44d1f7110e backtrace.rs:123
    #12 0x10c6f994f in std::rt::lang_start::_$u7b$$u7b$closure$u7d$$u7d$::hd59701f272e69e79 rt.rs:145
    #13 0x10c72f623 in std::rt::lang_start_internal::he76135267df4563a+0x2c3 (use-after-free:x86_64+0x100068623)
    #14 0x10c6f9899 in std::rt::lang_start::hfcb0fd33957d1beb rt.rs:144
    #15 0x10c6f74e5 in main+0x15 (use-after-free:x86_64+0x1000304e5)
    #16 0x10c6cb9e3 in start+0x33 (use-after-free:x86_64+0x1000049e3)

0x604000000490 is located 0 bytes inside of 48-byte region [0x604000000490,0x6040000004c0)
freed by thread T0 here:
    #0 0x10c80eec9 in wrap_free+0xa9 (librustc-nightly_rt.asan.dylib:x86_64+0x46ec9)
    #1 0x10c6db87c in alloc::alloc::dealloc::hac7cca683dc65791 alloc.rs:105
    #2 0x10c6dba98 in _$LT$alloc..alloc..Global$u20$as$u20$core..alloc..Allocator$GT$::deallocate::hdd1265caf1c71abf alloc.rs:242
    #3 0x10c6ed875 in alloc::alloc::box_free::h5953255913b50392 alloc.rs:336
    #4 0x10c6d7b8b in lru::LruCache$LT$K$C$V$C$S$GT$::pop::ha15bc84e57123038 lib.rs:547
    #5 0x10c6f71f7 in use_after_free::main::h958fdec6a3bbdb76 use-after-free.rs:13
    #6 0x10c6eb26d in core::ops::function::FnOnce::call_once::h02aaef19690c38dd function.rs:227
    #7 0x10c6f9573 in std::sys_common::backtrace::__rust_begin_short_backtrace::hc637aa44d1f7110e backtrace.rs:123
    #8 0x10c6f994f in std::rt::lang_start::_$u7b$$u7b$closure$u7d$$u7d$::hd59701f272e69e79 rt.rs:145
    #9 0x10c72f623 in std::rt::lang_start_internal::he76135267df4563a+0x2c3 (use-after-free:x86_64+0x100068623)
    #10 0x10c6f9899 in std::rt::lang_start::hfcb0fd33957d1beb rt.rs:144
    #11 0x10c6f74e5 in main+0x15 (use-after-free:x86_64+0x1000304e5)
    #12 0x10c6cb9e3 in start+0x33 (use-after-free:x86_64+0x1000049e3)

previously allocated by thread T0 here:
    #0 0x10c80ed80 in wrap_malloc+0xa0 (librustc-nightly_rt.asan.dylib:x86_64+0x46d80)
    #1 0x10c6db05b in alloc::alloc::alloc::h0f9b323acc874539 alloc.rs:87
    #2 0x10c6db328 in alloc::alloc::Global::alloc_impl::ha5c4a44f32d2adaf alloc.rs:169
    #3 0x10c6dbdb1 in _$LT$alloc..alloc..Global$u20$as$u20$core..alloc..Allocator$GT$::allocate::h402423fe20c59713 alloc.rs:229
    #4 0x10c6dad31 in alloc::alloc::exchange_malloc::ha89e8e0f96da4557 alloc.rs:318
    #5 0x10c6d8b36 in lru::LruCache$LT$K$C$V$C$S$GT$::put::h1d91d7e9e745a7be lib.rs:326
    #6 0x10c6f6f86 in use_after_free::main::h958fdec6a3bbdb76 use-after-free.rs:10
    #7 0x10c6eb26d in core::ops::function::FnOnce::call_once::h02aaef19690c38dd function.rs:227
    #8 0x10c6f9573 in std::sys_common::backtrace::__rust_begin_short_backtrace::hc637aa44d1f7110e backtrace.rs:123
    #9 0x10c6f994f in std::rt::lang_start::_$u7b$$u7b$closure$u7d$$u7d$::hd59701f272e69e79 rt.rs:145
    #10 0x10c72f623 in std::rt::lang_start_internal::he76135267df4563a+0x2c3 (use-after-free:x86_64+0x100068623)
    #11 0x10c6f9899 in std::rt::lang_start::hfcb0fd33957d1beb rt.rs:144
    #12 0x10c6f74e5 in main+0x15 (use-after-free:x86_64+0x1000304e5)
    #13 0x10c6cb9e3 in start+0x33 (use-after-free:x86_64+0x1000049e3)

SUMMARY: AddressSanitizer: heap-use-after-free (use-after-free:x86_64+0x100039791) in alloc::raw_vec::RawVec$LT$T$C$A$GT$::ptr::h5b52a5e22cadae0b+0x31
Shadow bytes around the buggy address:
  0x1c0800000040: fa fa 00 00 00 00 00 07 fa fa 00 00 00 00 00 00
  0x1c0800000050: fa fa 00 00 00 00 00 00 fa fa 00 00 00 00 00 00
  0x1c0800000060: fa fa 00 00 00 00 00 05 fa fa 00 00 00 00 00 00
  0x1c0800000070: fa fa 00 00 00 00 00 00 fa fa 00 00 00 00 00 00
  0x1c0800000080: fa fa 00 00 00 00 00 00 fa fa 00 00 00 00 00 00
=>0x1c0800000090: fa fa[fd]fd fd fd fd fd fa fa fa fa fa fa fa fa
  0x1c08000000a0: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x1c08000000b0: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x1c08000000c0: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x1c08000000d0: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x1c08000000e0: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
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
==31235==ABORTING
zsh: abort      RUSTFLAGS="-Z sanitizer=address" cargo +nightly run --example use-after-free

[jeromefroe]

Thanks for the bug report @oherrala! I just made #121 to address the issue. Your suspicion is exactly correct, the example code shouldn't be allowed to compile because we can't modify the cache while we also have an iterator.

[oherrala]

Thanks for quick fix @jeromefroe! I tested #121 and it indeed now gives compiler error for my test code:

error[E0502]: cannot borrow `cache` as mutable because it is also borrowed as immutable
  --> examples/use-after-free.rs:13:9
   |
12 |     for (key, value) in cache.into_iter() {
   |                         -----------------
   |                         |
   |                         immutable borrow occurs here
   |                         immutable borrow later used here
13 |         cache.pop(key);
   |         ^^^^^^^^^^^^^^ mutable borrow occurs here

I think this is worth reporting to RustSec after release.