Bug #19537


Regexp caching algorithm since v3.2.0 causes invalid memory access

Added by jj1uzh (Futa Miyachi) 9 months ago. Updated about 1 month ago.

Target version:
ruby -v:
ruby 3.3.0dev (2023-03-17T09:50:55Z master c65d7b4bea) [x86_64-linux]


Some types of regular expressions causes invalid memory access on #match. Length of strings to match does not matter.
For example, for regex /^([ab]{1,3})(a?)*$/, "aac" can crash ruby.

This bug may be caused in caching algorithm since v3.2.0.
v3.1.3 is safe as far as I checked.

Linux 6.2.6-arch1-1 x86-64, 16GB RAM

Reproduce Process:

$> ruby -e 'p /^([ab]{1,3})(a?)*$/.match "aac"'
-e:1: [BUG] Segmentation fault at 0x0000560315993d90
ruby 3.3.0dev (2023-03-17T09:50:55Z master c65d7b4bea) [x86_64-linux]

Whole output is attached as output.txt.
Note that result may be nil correctly sometimes.

Part of backtrace:

#5  0x000055ff30b71ecb in sigsegv (sig=11, info=0x55ff31bd0e70, ctx=0x55ff31bd0d40) at ../signal.c:964
#6  <signal handler called>
#7  reset_match_cache (num_cache_table=<optimized out>, num_cache_size=3, table=0x55ff31e2d930, match_cache=0x55ff31e2aec0 "\300\f", pos=2, pend=<optimized out>, pbegin=0x55ff31dc7202 ">\030", reg=0x55ff31e199b0) at ../regexec.c:1292
#8  match_at (reg=reg@entry=0x55ff31e199b0, str=str@entry=0x7fb176c7f148 "aac", end=<optimized out>, end@entry=0x7fb176c7f14b "", sstart=sstart@entry=0x7fb176c7f148 "aac", sprev=<optimized out>, msa=msa@entry=0x7ffe40153d30)
    at ../regexec.c:3486


output.txt (17.4 KB) output.txt jj1uzh (Futa Miyachi), 03/17/2023 02:34 PM
ruby-19537.patch (1.77 KB) ruby-19537.patch jj1uzh (Futa Miyachi), 03/18/2023 02:33 PM
Actions #1

Updated by jj1uzh (Futa Miyachi) 9 months ago

  • Subject changed from Regexp caching algorithm since v3.2.1 causes invalid memory access to Regexp caching algorithm since v3.2.0 causes invalid memory access
Actions #2

Updated by jj1uzh (Futa Miyachi) 9 months ago

I have not understand the implementation in detail, but maybe this patch fixes the problem.
(No new tests have been added, existing tests pass.)

Actions #3

Updated by alanwu (Alan Wu) 9 months ago

  • Assignee set to make_now_just (Hiroya Fujinami)
Actions #4

Updated by make_now_just (Hiroya Fujinami) 9 months ago

Thank you for your report. I am sorry that I missed your report.

I checked the patch, and it seems not the correct fix because the binary search should be performed on num_cache_table. I will tackle this problem in a week.

Updated by jeremyevans0 (Jeremy Evans) about 1 month ago

  • Status changed from Open to Closed

Also available in: Atom PDF