Large lookahead/behind range repetitions use excessive stack during JIT compilation

[addisoncrump]

I confirmed that this is not related to #156. Discovered by #322.

The pattern (?=x){,2500}, with x as any sequence of literals (including none), blows out the JIT compiler stack.

$ ./pcre2test -jit
PCRE2 version 10.43-DEV 2023-04-14 (8-bit)
  re> /(?=x){,2500}/
AddressSanitizer:DEADLYSIGNAL
=================================================================
==555324==ERROR: AddressSanitizer: stack-overflow on address 0x7ffe2a1d5cc8 (pc 0x7f77a315f3b1 bp 0x7ffe2a1d6340 sp 0x7ffe2a1d5cd0 T0)
    #0 0x7f77a315f3b1 in emit_cum_binary /home/addisoncrump/git/pcre2/./src/sljit/sljitNativeX86_common.c:1816:10
    #1 0x7f77a3135145 in sljit_emit_op2 /home/addisoncrump/git/pcre2/./src/sljit/sljitNativeX86_common.c:2478:10
    #2 0x7f77a318709e in compile_charn_matchingpath /home/addisoncrump/git/pcre2/src/pcre2_jit_compile.c:9247:3
    #3 0x7f77a313f361 in compile_matchingpath /home/addisoncrump/git/pcre2/src/pcre2_jit_compile.c:12399:12
    #4 0x7f77a31948af in compile_assert_matchingpath /home/addisoncrump/git/pcre2/src/pcre2_jit_compile.c:10173:3
    #5 0x7f77a3140297 in compile_matchingpath /home/addisoncrump/git/pcre2/src/pcre2_jit_compile.c:12526:10
    #6 0x7f77a319d222 in compile_bracket_matchingpath /home/addisoncrump/git/pcre2/src/pcre2_jit_compile.c:11062:1
    #7 0x7f77a3140650 in compile_matchingpath /home/addisoncrump/git/pcre2/src/pcre2_jit_compile.c:12562:12
    #8 0x7f77a319d222 in compile_bracket_matchingpath /home/addisoncrump/git/pcre2/src/pcre2_jit_compile.c:11062:1
    #9 0x7f77a3140650 in compile_matchingpath /home/addisoncrump/git/pcre2/src/pcre2_jit_compile.c:12562:12
...

I assume this is a result of lookahead range repetitions being implemented recursively in the JIT compiler. Note that the same occurs with negative lookaheads, lookbehinds, and negative lookbehinds.

[carenas]

that is not a "variable" lookaround, but rather just a lookaround with a very large range, which is not very useful by itself, hence I presume not a practical concern.

Can't reproduce (while using ASAN) with an stack size of 8MB (the default in my setup) or even 4MB; AFAIK, really small stacks and regex don't mix well.

  re> /(?=x){,2500}/jit,memory
Memory allocation (code space): 37501
Memory allocation (JIT code): 1330956

[addisoncrump]

Ah, in this case, you would likely need a much larger repetition count. Address sanitizer takes up a lot of stack space.

Working from a clean build (no ASAN) I can't reproduce -- the test utility reports that the expression is too large when I supply it with values >5000. Regardless, it does indicate that the JIT compiler is using excessive amounts of stack for this particular case and might affect downstream users who compile JIT in an already deep stack frame.

[carenas]

it does indicate that the JIT compiler is using excessive amounts of stack for this particular case

Sorry, I should had been clearer.

When I wrote "not a pratical concern", I meant that no one would want to write that expression, unless their only objective is to crash PCRE2. The documentation explains why you must be careful with these kind of expressions, and indeed the output from pcre2test shows that BOTH the interpreted and JIT code are huge, so even in the case were the expression was valid, it would be too slow to use, and so it would have to be rewritten in a more optimal way.

If your concern is "PCRE2 shouldn't crash" regardless, then as you pointed out, the stack size (ulimit -s or equivalent) the process was using would need to be adjusted based on its expected usage (which includes the overhead of using ASAN, if that is what you would prefer).

FWIW, in the worst possible version of this expression for the 8bit library, JIT would just politely refuse (pcre2_jit_compile returns -48), as the private_area will be larger than 64K:

% ./configure CC='clang -fsanitize=address' --enable-jit  --with-link-size=4
...
% ./pcre2test -tm 1
PCRE2 version 10.43-DEV 2023-04-14 (8-bit)
  re> /(?=x){,65535}/jit,memory
Memory allocation (code space): 1507306
Memory allocation (JIT code): 0
data> x
Match time 38963.0000 microseconds
 0: 

[zherczeg]

As far as I remember assertions and repetitions don't mix. Only the (0,1) repetition is allowed, and supporting that is a lot of effort unfortunately.

[carenas]

Only the (0,1) repetition is allowed,

That kind of make more sense, but then it seems there is a compiler bug that prevents the invalid expression from raising an error instead.

FWIW, perl doesn't raise an error either, but IMHO returns a non sense match as well, even if at least their code might seem to be a little more efficient too:

% perl -Mre=debug -e 'shift =~ /(?<=x){2}a/' axa
Compiling REx "(?<=x){2}a"
Final program:
   1: CURLYX[0]{1,1} (12)
   5:   IFMATCH[-1] (11)
   7:     EXACT <x> (9)
   9:     LOOKBEHIND_END (0)
  10:   TAIL (11)
  11: WHILEM (0)
  12: NOTHING (13)
  13: EXACT <a> (15)
  15: END (0)
anchored "a" at 0..0 (checking anchored) minlen 1 
Matching REx "(?<=x){2}a" against "axa"
Intuit: trying to determine minimum start position...
  doing 'check' fbm scan, [0..3] gave 0
  Found anchored substr "a" at offset 0 (rx_origin now 0)...
  (multiline anchor test skipped)
Intuit: Successfully guessed: match at offset 0
   0 <> <axa>                |   0| 1:CURLYX[0]{1,1}(12)
   0 <> <axa>                |   1|  11:WHILEM(0)
                             |   1|  WHILEM: matched 0 out of 1..1
   0 <> <axa>                |   2|   5:IFMATCH[-1](11)
                             |   2|   failed...
                             |   1|  failed...
                             |   0| failed...
   2 <ax> <a>                |   0| 1:CURLYX[0]{1,1}(12)
   2 <ax> <a>                |   1|  11:WHILEM(0)
                             |   1|  WHILEM: matched 0 out of 1..1
   2 <ax> <a>                |   2|   5:IFMATCH[-1](11)
   1 <a> <xa>                |   3|    7:EXACT <x>(9)
   2 <ax> <a>                |   3|    9:LOOKBEHIND_END(0)
                             |   3|    SUCCEED: subpattern success...
   2 <ax> <a>                |   2|   11:WHILEM(0)
                             |   2|   WHILEM: matched 1 out of 1..1
                             |   2|   WHILEM: empty match detected, trying continuation...
   2 <ax> <a>                |   3|    12:NOTHING(13)
   2 <ax> <a>                |   3|    13:EXACT <a>(15)
   3 <axa> <>                |   3|    15:END(0)
Match successful!
Freeing REx: "(?<=x){2}a"

Is anyone clear on what is the "correct" way to apply repetitions to a constrain?, specially one that is potentially zero sized like the lookarounds used here?

[zherczeg]

The story is the usual. Assertions did not support repetitions, because it is pointless. Then somebody complained, and Philip did some changes in the interpreter, which unfortunately complicated things in jit. Anyway for me the (?=P){rep} is the same as (?:(?=P)){rep}.

Normally bracket repetitions are repeated byte code sequences, which are detected by jit and collapsed to iterations. This case might have some uncommon byte code.

For me it would be the best if repeated assertions would be packed inside normal (?:(?...)){repetition} blocks. This could simplify the jit code a lot. Maybe not needed for *napla / *naplb, because they are already handled by the normal bracket code path.

[addisoncrump]

I recognise this is not super pressing for normal usage, but it makes testing a lot less false-positive prone. Can I help with this?

[carenas]

Can I help with this?

of course; you should add (just like pcre2test has) a -S parameter to the fuzzer and make sure to run it with a higher value than it will use by default in your environment.

pcre2test uses 64MB but you are likely going to be able to use something much smaller; you never said how much your test environment uses, but at least on mine 4MB was working fine, even with ASAN.

[addisoncrump]

Awesome, thanks. I just made its default behaviour to set the stack size to 32MB.

[addisoncrump]

Hm, this was not enough with larger link sizes. I am using 256MB now (which is unreasonably large), but at least it doesn't stack overflow.