Detect “Use-after-free” with address sanitizer

[dearblue]

When built with conf.enable_debug and conf.defines << %w(MRB_GC_STRESS MRB_HEAP_PAGE_SIZE=169), the test in mruby-enumerator reports “Use-after-free”.
I went back through the commit log and found that the problem started with commit 5bd63d6. However, I didn't see any problem with the code written.

I don't know where the tail of the cause is, but I will try to find out more.

% cat test_config.rb
MRuby::Build.new do
  toolchain
  enable_test
  enable_debug
  defines << %w(MRB_HEAP_PAGE_SIZE=169)
  defines << %w(MRB_GC_STRESS)
  enable_sanitizer "address,undefined"
  gem core: "mruby-enumerator"
  # gembox "full-core"
end

% rake -mv MRUBY_CONFIG=test_config.rb test

...SNIP...

Enumerator.class : .
Enumerator.superclass : .
Enumerator.new : .
Enumerator#initialize_copy : .
=================================================================
==72465==ERROR: AddressSanitizer: heap-use-after-free on address 0x525000033ff0 at pc 0x00000042fcc5 bp 0x7ffffffdce90 sp 0x7ffffffdce88
READ of size 4 at 0x525000033ff0 thread T0
    #0 0x42fcc4 in obj_free /var/tmp/mruby/src/gc.c:782:23
    #1 0x434de2 in incremental_sweep_phase /var/tmp/mruby/src/gc.c:1036:11
    #2 0x43174f in incremental_gc /var/tmp/mruby/src/gc.c:1112:20
    #3 0x42b41b in incremental_gc_finish /var/tmp/mruby/src/gc.c:1128:5
    #4 0x4242ea in mrb_full_gc /var/tmp/mruby/src/gc.c:1224:3
    #5 0x42529e in mrb_obj_alloc /var/tmp/mruby/src/gc.c:489:3
    #6 0x4f1ce9 in str_new /var/tmp/mruby/src/string.c:147:27
    #7 0x4f1bdc in mrb_str_new /var/tmp/mruby/src/string.c:187:24
    #8 0x5e07bc in mrb_vm_exec /var/tmp/mruby/src/vm.c:2839:19
    #9 0x567655 in mrb_vm_run /var/tmp/mruby/src/vm.c:1365:12
    #10 0x55e438 in mrb_top_run /var/tmp/mruby/src/vm.c:3135:10
    #11 0x456a7c in load_irep /var/tmp/mruby/src/load.c:682:10
    #12 0x4566fd in mrb_load_irep_cxt /var/tmp/mruby/src/load.c:690:10
    #13 0x456b18 in mrb_load_irep /var/tmp/mruby/src/load.c:702:10
    #14 0x3b23b9 in GENERATED_TMP_mrb_mruby_enumerator_gem_test /var/tmp/mruby/build/host/mrbgems/mruby-enumerator/gem_test.c:1448:3
    #15 0x3af9b5 in mrbgemtest_init /var/tmp/mruby/build/host/mrbgems/mruby-test/mrbtest.c:19:5
    #16 0x3ab09f in main /var/tmp/mruby/mrbgems/mruby-test/driver.c:299:3
    #17 0x8007f3a69 in __libc_start1 (/lib/libc.so.7+0x85a69)
    #18 0x2faa7f in _start /usr/src/lib/csu/amd64/crt1_s.S:83

0x525000033ff0 is located 7920 bytes inside of 8144-byte region [0x525000032100,0x5250000340d0)
freed by thread T0 here:
    #0 0x374476 in free /usr/src/contrib/llvm-project/compiler-rt/lib/asan/asan_malloc_linux.cpp:52:3

previously allocated by thread T0 here:
    #0 0x374817 in realloc /usr/src/contrib/llvm-project/compiler-rt/lib/asan/asan_malloc_linux.cpp:82:3

SUMMARY: AddressSanitizer: heap-use-after-free /var/tmp/mruby/src/gc.c:782:23 in obj_free
Shadow bytes around the buggy address:
  0x525000033d00: fd fd fd fd fd fd fd fd fd fd fd fd fd fd fd fd
  0x525000033d80: fd fd fd fd fd fd fd fd fd fd fd fd fd fd fd fd
  0x525000033e00: fd fd fd fd fd fd fd fd fd fd fd fd fd fd fd fd
  0x525000033e80: fd fd fd fd fd fd fd fd fd fd fd fd fd fd fd fd
  0x525000033f00: fd fd fd fd fd fd fd fd fd fd fd fd fd fd fd fd
=>0x525000033f80: fd fd fd fd fd fd fd fd fd fd fd fd fd fd[fd]fd
  0x525000034000: fd fd fd fd fd fd fd fd fd fd fd fd fd fd fd fd
  0x525000034080: fd fd fd fd fd fd fd fd fd fd fa fa fa fa fa fa
  0x525000034100: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x525000034180: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x525000034200: 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
==72465==ABORTING

...SNIP...

[dearblue]

🐈‍⬛ In my previous comment I mentioned that I couldn't find any problems, but that was a lie.

The sort_cmp() function calls mrb_cmp() or mrb_yield_argv(), but then it needs to call mrb_ary_modify(), RARRAY_LEN() or RARAY_PTR().

I don't know if this is the same cause of the problem I commented earlier, but the problem also occurs with those built with build_config/default.rb.

• segmentation fault

  % bin/mruby -e 'a = [1, 2, 3]; a.sort! { a[20] = 0 }'
  zsh: segmentation fault (core dumped)  bin/mruby -e 'a = [1, 2, 3]; a.sort! { a[20] = 0 }'

• Use-after-free

  % valgrind -- bin/mruby -e 'a = [1, 2, 3, 4]; a.sort! { a.clear; GC.start; 0 }'
  ==12977== Memcheck, a memory error detector
  ==12977== Copyright (C) 2002-2024, and GNU GPL'd, by Julian Seward et al.
  ==12977== Using Valgrind-3.23.0 and LibVEX; rerun with -h for copyright info
  ==12977== Command: bin/mruby -e a\ =\ [1,\ 2,\ 3,\ 4];\ a.sort!\ {\ a.clear;\ GC.start;\ 0\ }
  ==12977==
  ==12977== Invalid read of size 8
  ==12977==    at 0x264DBD: sort_cmp (array.c:0)
  ==12977==    by 0x264DBD: heapify (array.c:1436)
  ==12977==    by 0x264A55: mrb_ary_sort_bang (array.c:1471)
  ==12977==    by 0x2959A6: mrb_vm_exec (vm.c:0)
  ==12977==    by 0x2B8B83: mrb_load_exec (parse.y:6919)
  ==12977==    by 0x25F4BD: main (mruby.c:358)
  ==12977==  Address 0x54dabd8 is 8 bytes inside a block of size 32 free'd
  ==12977==    at 0x484F2EC: free (vg_replace_malloc.c:993)
  ==12977==    by 0x282188: mrb_default_allocf (allocf.c:22)
  ==12977==    by 0x263461: mrb_ary_clear (array.c:1176)
  ==12977==    by 0x263461: mrb_ary_clear_m (array.c:1192)
  ==12977==    by 0x2959A6: mrb_vm_exec (vm.c:0)
  ==12977==    by 0x28DCED: mrb_run (vm.c:3126)
  ==12977==    by 0x28DCED: mrb_funcall_with_block (vm.c:749)
  ==12977==    by 0x28D684: mrb_funcall_argv (vm.c:760)
  ==12977==    by 0x28D684: mrb_funcall_id (vm.c:560)
  ==12977==    by 0x264DDD: sort_cmp (array.c:1421)
  ==12977==    by 0x264DDD: heapify (array.c:1436)
  ==12977==    by 0x264A55: mrb_ary_sort_bang (array.c:1471)
  ==12977==    by 0x2959A6: mrb_vm_exec (vm.c:0)
  ==12977==    by 0x2B8B83: mrb_load_exec (parse.y:6919)
  ==12977==    by 0x25F4BD: main (mruby.c:358)
  ==12977==  Block was alloc'd at
  ==12977==    at 0x4852321: realloc (vg_replace_malloc.c:1806)
  ==12977==    by 0x26E688: mrb_realloc_simple (gc.c:197)
  ==12977==    by 0x26E688: mrb_realloc (gc.c:211)
  ==12977==    by 0x26E688: mrb_malloc (gc.c:227)
  ==12977==    by 0x25F7EE: ary_new_capa (array.c:54)
  ==12977==    by 0x25F871: ary_new_from_values (array.c:99)
  ==12977==    by 0x25F871: mrb_ary_new_from_values (array.c:110)
  ==12977==    by 0x29C574: mrb_vm_exec (vm.c:2716)
  ==12977==    by 0x2B8B83: mrb_load_exec (parse.y:6919)
  ==12977==    by 0x25F4BD: main (mruby.c:358)
  ==12977==
  
  ...SNIP...
  
  ==12977==
  ==12977== HEAP SUMMARY:
  ==12977==     in use at exit: 0 bytes in 0 blocks
  ==12977==   total heap usage: 759 allocs, 759 frees, 203,934 bytes allocated
  ==12977==
  ==12977== All heap blocks were freed -- no leaks are possible
  ==12977==
  ==12977== For lists of detected and suppressed errors, rerun with: -s
  ==12977== ERROR SUMMARY: 22 errors from 12 contexts (suppressed: 0 from 0)

[matz]

752ebe6 cheks if the array is modified in the block. I am not sure it resolves the original issue.

[dearblue]

I think the problem with giving blocking arguments in the second comment has been resolved.
However, mrb_cmp() calls the obj.cmp method internally, so it looks like the same treatment is needed.

% valgrind -- bin/mruby -e 'e = Object.new; $ary = [e] * 4; class << e; def <=>(other) $ary.clear; 0; end; end; $ary.sort!'

...SNIP...

==22005== Invalid read of size 8
==22005==    at 0x244332: sort_cmp (array.c:1591)
==22005==    by 0x24422D: heapify (array.c:1613)
==22005==    by 0x243AC9: mrb_ary_sort_bang (array.c:1648)
==22005==    by 0x28C04D: mrb_vm_exec (vm.c:1934)
==22005==    by 0x28853E: mrb_vm_run (vm.c:1349)
==22005==    by 0x28731F: mrb_top_run (vm.c:3081)
==22005==    by 0x2A825C: mrb_load_exec (parse.y:6919)
==22005==    by 0x2A8794: mrb_load_nstring_cxt (parse.y:6991)
==22005==    by 0x2A8830: mrb_load_string_cxt (parse.y:7003)
==22005==    by 0x23BC2B: main (mruby.c:358)
==22005==  Address 0x54ce578 is 8 bytes inside a block of size 32 free'd
==22005==    at 0x484F2EC: free (vg_replace_malloc.c:993)
==22005==    by 0x2740FB: mrb_default_allocf (allocf.c:22)
==22005==    by 0x252CFB: mrb_free (gc.c:259)
==22005==    by 0x23F7CD: mrb_ary_clear (array.c:1263)
==22005==    by 0x2410DC: mrb_ary_clear_m (array.c:1279)

...SNIP...

[dearblue]

For the first problem, the cause was clearly different.
After commit 22518b5, git cherry-pick 5bd63d623 did not reproduce the problem, but after commit 7edbff8 (#6253), it did.

% git checkout 22518b5b7 && git cherry-pick 5bd63d623 && ...
## => no problems

% git checkout 7edbff8c8 && git cherry-pick 5bd63d623 && ...
## => reproduced problems

Currently under investigation.

[dearblue]

Ah, I understand now at last.
I need to call heap_p() before calling is_dead().

mruby/src/gc.c

Line 791 in 58c7083

if (e && !is_dead(&mrb->gc, (struct RBasic*)e) &&

I will check some more and send a pull-request.