use-after-realloc in `mrb_ary_sort_bang`

[tim-becker]

Description: In Array#sort! (mrb_ary_sort_bang), the heap sort captures the raw data pointer (variable `a`) once at the start and continues to use it for element accesses even if the user’s comparator block mutates the array (e.g. calls slice!), which can shrink or reallocate the underlying storage. After such a mutation frees or relocates the buffer, the sort routine dereferences the stale pointer and feeds invalid mrb_value entries into cmpnum, which then calls mrb_obj_is_kind_of on garbage data and crashes.

Trigger conditions: Triggered by sorting an array larger than SMALL_ARRAY_SORT_THRESHOLD with a custom block that modifies the array during comparison—specifically, a Ruby fuzzer input `a=(0..99).to_a; a.sort!{|x,y| a.slice!(1,98); (x<y)? -1 : 1 }` causes slice! to shrink/reallocate the array storage while heap sort still uses the old pointer, leading to a use-after-free crash.

Harness name: mruby_fuzzer

Crashing input:

a=(0..99).to_a; a.sort!{|x,y| a.slice!(1,98); (x<y)? -1 : 1 }

Crash output:

+ FUZZER=mruby_fuzzer
+ shift
+ '[' '!' -v TESTCASE ']'
+ TESTCASE=/testcase
+ '[' '!' -f /testcase ']'
+ export RUN_FUZZER_MODE=interactive
+ RUN_FUZZER_MODE=interactive
+ export FUZZING_ENGINE=libfuzzer
+ FUZZING_ENGINE=libfuzzer
+ export SKIP_SEED_CORPUS=1
+ SKIP_SEED_CORPUS=1
+ run_fuzzer mruby_fuzzer /testcase
sysctl: setting key "vm.mmap_rnd_bits", ignoring: Read-only file system
Dictionary: 102 entries
/out/mruby_fuzzer: Running 1 inputs 1 time(s) each.
Running: /testcase
UndefinedBehaviorSanitizer:DEADLYSIGNAL
==43==ERROR: UndefinedBehaviorSanitizer: SEGV on unknown address (pc 0x562071c2ae0d bp 0x7ffec38313a0 sp 0x7ffec38312b0 T43)
==43==The signal is caused by a READ memory access.
==43==Hint: this fault was caused by a dereference of a high value address (see register values below).  Disassemble the provided pc to learn which register was used.
Stack Frame #0 in mrb_obj_is_kind_of (/out/mruby_fuzzer+0x5ece0d)
Stack Frame #1 in cmpnum numeric.c
Stack Frame #2 in num_lt numeric.c
Stack Frame #3 in mrb_vm_exec (/out/mruby_fuzzer+0x52b71c)
Stack Frame #4 in mrb_vm_run (/out/mruby_fuzzer+0x5091b5)
Stack Frame #5 in mrb_run vm.c
Stack Frame #6 in yield_with_attr vm.c
Stack Frame #7 in mrb_yield_argv (/out/mruby_fuzzer+0x50e462)
Stack Frame #8 in sort_cmp array.c
Stack Frame #9 in heapify array.c
Stack Frame #10 in mrb_ary_sort_bang array.c
Stack Frame #11 in mrb_vm_exec (/out/mruby_fuzzer+0x52b71c)
Stack Frame #12 in mrb_vm_run (/out/mruby_fuzzer+0x5091b5)
Stack Frame #13 in mrb_top_run (/out/mruby_fuzzer+0x58e618)
Stack Frame #14 in mrb_load_exec (/out/mruby_fuzzer+0x48ab09)
Stack Frame #15 in mrb_load_nstring_cxt (/out/mruby_fuzzer+0x48bacc)
Stack Frame #16 in mrb_load_string_cxt (/out/mruby_fuzzer+0x48bc00)
Stack Frame #17 in mrb_load_string (/out/mruby_fuzzer+0x48bc78)
Stack Frame #18 in LLVMFuzzerTestOneInput (/out/mruby_fuzzer+0x448807)
Stack Frame #19 in fuzzer::Fuzzer::ExecuteCallback(unsigned char const*, unsigned long) /src/llvm-project/compiler-rt/lib/fuzzer/FuzzerLoop.cpp:614:13
Stack Frame #20 in fuzzer::RunOneTest(fuzzer::Fuzzer*, char const*, unsigned long) /src/llvm-project/compiler-rt/lib/fuzzer/FuzzerDriver.cpp:327:6
Stack Frame #21 in fuzzer::FuzzerDriver(int*, char***, int (*)(unsigned char const*, unsigned long)) /src/llvm-project/compiler-rt/lib/fuzzer/FuzzerDriver.cpp:862:9
Stack Frame #22 in main /src/llvm-project/compiler-rt/lib/fuzzer/FuzzerMain.cpp:20:10
Stack Frame #23 in __libc_start_main /build/glibc-B3wQXB/glibc-2.31/csu/../csu/libc-start.c:308:16
Stack Frame #24 in _start (/out/mruby_fuzzer+0x38e0fd)

DEDUP_TOKEN: mrb_obj_is_kind_of--cmpnum--num_lt--mrb_vm_exec--mrb_vm_run
UndefinedBehaviorSanitizer can not provide additional info.
SUMMARY: UndefinedBehaviorSanitizer: SEGV (/out/mruby_fuzzer+0x5ece0d) in mrb_obj_is_kind_of
==43==ABORTING

/out/mruby_fuzzer -rss_limit_mb=2560 -timeout=25 /testcase -dict=mruby.dict -only_ascii=1 < /dev/null

Patch:

--- a/src/array.c
+++ b/src/array.c
@@ -1887,9 +1887,13 @@
     mrb_int right_index = left_index + 1;
 
     if (left_index < size && sort_cmp(mrb, ary, a, a[left_index], a[max], blk)) {
+      /* Refresh array pointer after potential modification */
+      a = RARRAY_PTR(ary);
       max = left_index;
     }
     if (right_index < size && sort_cmp(mrb, ary, a, a[right_index], a[max], blk)) {
+      /* Refresh array pointer after potential modification */
+      a = RARRAY_PTR(ary);
       max = right_index;
     }
 
@@ -1903,6 +1907,8 @@
     a[max] = a[index];
     a[index] = tmp;
 
+    /* Refresh array pointer for next iteration */
+    a = RARRAY_PTR(ary);
     /* Continue with the affected child subtree */
     index = max;
   }
@@ -1917,6 +1923,8 @@
 
     /* Move elements that are greater than key to one position ahead */
     while (j >= 0 && sort_cmp(mrb, ary, a, a[j], key, blk)) {
+      /* Refresh array pointer after potential modification */
+      a = RARRAY_PTR(ary);
       a[j + 1] = a[j];
       j--;
     }
@@ -1943,23 +1951,33 @@
   ary_modify(mrb, mrb_ary_ptr(ary));
   mrb_get_args(mrb, "&", &blk);
 
-  mrb_value *a = RARRAY_PTR(ary);
-
   /* Algorithm selection based on array size */
   if (n <= SMALL_ARRAY_SORT_THRESHOLD) {
     /* Use insertion sort for small arrays */
+    mrb_value *a = RARRAY_PTR(ary);
     insertion_sort(mrb, ary, a, n, blk);
   }
   else {
     /* Use heap sort for larger arrays */
+    mrb_value *a = RARRAY_PTR(ary);
     for (mrb_int i = n / 2 - 1; i >= 0; i--) {
       heapify(mrb, ary, a, i, n, blk);
+      /* Check if array was modified during heapify */
+      if (RARRAY_LEN(ary) != n) {
+        mrb_raise(mrb, E_RUNTIME_ERROR, "array modified during sort");
+      }
+      a = RARRAY_PTR(ary);
     }
     for (mrb_int i = n - 1; i > 0; i--) {
+      a = RARRAY_PTR(ary);
       mrb_value tmp = a[0];
       a[0] = a[i];
       a[i] = tmp;
       heapify(mrb, ary, a, 0, i, blk);
+      /* Check if array was modified during heapify */
+      if (RARRAY_LEN(ary) != n) {
+        mrb_raise(mrb, E_RUNTIME_ERROR, "array modified during sort");
+      }
     }
   }
   return ary;

[tim-becker]

note: the crash output here shows a wild-pointer dereference, but the root cause is believed to be the described use of a reallocated backing array

[matz]

hmm,sort_cmp function raises an exception when a != RARRAY_PTR(ary). This use-after-free should never happen. At least your patch does not make any change.

[tim-becker]

Hm, please allow me to investigate more. It is possible this code has changed since we ran our analysis.

For context: this report was generated in July and reported via email (due to potential security implications). We are only now posting them here because the emails went unanswered.

[tim-becker]

The crash does reproduce on the latest code (nondeterministically, it seems to depend on the values in memory during the faulty comparison)

Here is a backtrace from gdb:

Program received signal SIGSEGV, Segmentation fault.
0x00005555555b3e4d in mrb_vm_exec (mrb=<optimized out>, begin_proc=<optimized out>, iseq=<optimized out>)
    at /home/user/mruby/src/vm.c:2961
2961	      OP_CMP(<,lt);
(gdb) bt
#0  0x00005555555b3e4d in mrb_vm_exec (mrb=<optimized out>, begin_proc=<optimized out>, iseq=<optimized out>)
    at /home/user/mruby/src/vm.c:2961
#1  0x00005555555b7a29 in mrb_vm_run (mrb=<optimized out>, proc=<optimized out>, self=..., stack_keep=<optimized out>)
    at /home/user/mruby/src/vm.c:1613
#2  0x00005555555b98e0 in mrb_run (self=..., proc=<optimized out>, mrb=<optimized out>) at /home/user/mruby/src/vm.c:3411
#3  0x00005555555b9e91 in mrb_yield_argv (mrb=mrb@entry=0x5555556952a0, b=b@entry=..., argc=argc@entry=2,
    argv=argv@entry=0x7fffffffd9f0) at /home/user/mruby/src/vm.c:1288
#4  0x0000555555578a5e in sort_cmp (blk=..., b_val=..., a_val=..., p=0x5555556c7090, ary=..., mrb=0x5555556952a0)
    at /home/user/mruby/src/array.c:2085
#5  heapify (mrb=mrb@entry=0x5555556952a0, ary=..., ary@entry=..., a=a@entry=0x5555556c7090, index=index@entry=9, size=size@entry=100,
    blk=...) at /home/user/mruby/src/array.c:2112
#6  0x00005555555792b9 in mrb_ary_sort_bang (mrb=0x5555556952a0, ary=...) at /home/user/mruby/src/array.c:2179
#7  0x00005555555b2ea2 in mrb_vm_exec (mrb=<optimized out>, begin_proc=<optimized out>, iseq=<optimized out>)
    at /home/user/mruby/src/vm.c:2254
#8  0x00005555555b7a29 in mrb_vm_run (mrb=<optimized out>, proc=<optimized out>, self=..., stack_keep=<optimized out>)
    at /home/user/mruby/src/vm.c:1613
#9  0x00005555555b9f77 in mrb_top_run (mrb=<optimized out>, proc=<optimized out>, self=..., stack_keep=<optimized out>)
    at /home/user/mruby/src/vm.c:3441
#10 0x00005555555d1bcd in mrb_load_exec (mrb=mrb@entry=0x5555556952a0, p=p@entry=0x5555556b5700, c=c@entry=0x5555556b45c0)
    at mrbgems/mruby-compiler/core/parse.y:7342
#11 0x00005555555d2000 in mrb_load_detect_file_cxt (mrb=mrb@entry=0x5555556952a0, fp=fp@entry=0x5555556b43c0, c=c@entry=0x5555556b45c0)
    at mrbgems/mruby-compiler/core/parse.y:7255
#12 0x0000555555575838 in main (argc=<optimized out>, argv=0x7fffffffe328)
    at /home/user/mruby/mrbgems/mruby-bin-mruby/tools/mruby/mruby.c:353

However, this doesn't confirm that the root cause given in the report is accurate. I will investigate deeper tomorrow.

[tim-becker]

I believe the root-cause is mostly accurate, but perhaps more accurately described as "use-after-realloc".

The a != RARRAY_PTR(ary) check in sort_cmp is insufficient, because when shrinking an allocation, realloc is permitted to (and often does) split the provided heap chunk in two parts and return the original pointer.

So, detecting an allocation modification may also require a length check.