Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

heap-buffer-overflow in S_regmatch (regexec.c:5439) #15634

Closed
p5pRT opened this issue Sep 28, 2016 · 18 comments
Closed

heap-buffer-overflow in S_regmatch (regexec.c:5439) #15634

p5pRT opened this issue Sep 28, 2016 · 18 comments

Comments

@p5pRT
Copy link

p5pRT commented Sep 28, 2016

Migrated from rt.perl.org#129377 (status was 'resolved')

Searchable as RT129377$

@p5pRT
Copy link
Author

p5pRT commented Sep 28, 2016

From @geeknik

perl -e '(x)!~/0|()0|()\1/&0' triggers a heap-buffer-overflow in
Perl v5.25.6 (v5.25.5-42-g850e14d).

==22476==ERROR​: AddressSanitizer​: heap-buffer-overflow on address
0x60200000e20f at pc 0x000000b9fa1b bp 0x7fffca51b370 sp 0x7fffca51b368
READ of size 1 at 0x60200000e20f thread T0
  #0 0xb9fa1a in S_regmatch /root/perl/regexec.c​:5439​:9
  #1 0xb7314c in S_regtry /root/perl/regexec.c​:3621​:14
  #2 0xb4ba5d in Perl_regexec_flags /root/perl/regexec.c​:3488​:7
  #3 0x8c2b98 in Perl_pp_match /root/perl/pp_hot.c​:1837​:10
  #4 0x7f4473 in Perl_runops_debug /root/perl/dump.c​:2239​:23
  #5 0x5a11d6 in S_run_body /root/perl/perl.c​:2526​:2
  #6 0x5a11d6 in perl_run /root/perl/perl.c​:2449
  #7 0x4de5fd in main /root/perl/perlmain.c​:123​:9
  #8 0x7fcbc548cb44 in __libc_start_main
/build/glibc-daoqzt/glibc-2.19/csu/libc-start.c​:287
  #9 0x4de26c in _start (/root/perl/perl+0x4de26c)

0x60200000e20f is located 1 bytes to the left of 10-byte region
[0x60200000e210,0x60200000e21a)
allocated by thread T0 here​:
  #0 0x4c0beb in malloc (/root/perl/perl+0x4c0beb)
  #1 0x7f82b7 in Perl_safesysmalloc /root/perl/util.c​:153​:21

SUMMARY​: AddressSanitizer​: heap-buffer-overflow /root/perl/regexec.c​:5439
S_regmatch
Shadow bytes around the buggy address​:
  0x0c047fff9bf0​: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0c047fff9c00​: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0c047fff9c10​: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0c047fff9c20​: fa fa fd fd fa fa fd fd fa fa fd fd fa fa 00 00
  0x0c047fff9c30​: fa fa fd fa fa fa fd fd fa fa fd fd fa fa fd fd
=>0x0c047fff9c40​: fa[fa]00 02 fa fa 00 02 fa fa fd fd fa fa fd fd
  0x0c047fff9c50​: fa fa 02 fa fa fa 00 02 fa fa 00 07 fa fa 00 fa
  0x0c047fff9c60​: fa fa 00 02 fa fa 05 fa fa fa 00 02 fa fa 06 fa
  0x0c047fff9c70​: fa fa 00 02 fa fa 05 fa fa fa 00 05 fa fa 04 fa
  0x0c047fff9c80​: fa fa 05 fa fa fa 05 fa fa fa 00 00 fa fa 00 02
  0x0c047fff9c90​: fa fa 05 fa fa fa 00 02 fa fa 00 fa fa fa 00 04
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
  Heap right redzone​: fb
  Freed heap region​: fd
  Stack left redzone​: f1
  Stack mid redzone​: f2
  Stack right redzone​: f3
  Stack partial redzone​: f4
  Stack after return​: f5
  Stack use after scope​: f8
  Global redzone​: f9
  Global init order​: f6
  Poisoned by user​: f7
  Container overflow​: fc
  ASan internal​: fe
==22476==ABORTING

Perl 5.20.2 doesn't crash, but this happens while running under Valgrind​:

==25966== Invalid read of size 1
==25966== at 0x4F60CBB​: ??? (in
/usr/lib/x86_64-linux-gnu/libperl.so.5.20.2)
==25966== by 0x4F6D13A​: Perl_regexec_flags (in
/usr/lib/x86_64-linux-gnu/libperl.so.5.20.2)
==25966== by 0x4EFEC7D​: Perl_pp_match (in
/usr/lib/x86_64-linux-gnu/libperl.so.5.20.2)
==25966== by 0x4EFB055​: Perl_runops_standard (in
/usr/lib/x86_64-linux-gnu/libperl.so.5.20.2)
==25966== by 0x4E8B73D​: perl_run (in
/usr/lib/x86_64-linux-gnu/libperl.so.5.20.2)
==25966== by 0x400E18​: main (in /usr/bin/perl)
==25966== Address 0x5f358df is 1 bytes before a block of size 10 alloc'd
==25966== at 0x4C28C20​: malloc (vg_replace_malloc.c​:296)
==25966== by 0x4EDCE21​: Perl_safesysmalloc (in
/usr/lib/x86_64-linux-gnu/libperl.so.5.20.2)
==25966== by 0x4F10EFF​: Perl_sv_grow (in
/usr/lib/x86_64-linux-gnu/libperl.so.5.20.2)
==25966== by 0x4F138B2​: Perl_sv_setpvn (in
/usr/lib/x86_64-linux-gnu/libperl.so.5.20.2)
==25966== by 0x4F13C51​: Perl_newSVpvn_flags (in
/usr/lib/x86_64-linux-gnu/libperl.so.5.20.2)
==25966== by 0x4EA4C00​: Perl_yylex (in
/usr/lib/x86_64-linux-gnu/libperl.so.5.20.2)
==25966== by 0x4EB1A47​: Perl_yyparse (in
/usr/lib/x86_64-linux-gnu/libperl.so.5.20.2)
==25966== by 0x4E8A427​: perl_parse (in
/usr/lib/x86_64-linux-gnu/libperl.so.5.20.2)
==25966== by 0x400D7A​: main (in /usr/bin/perl)
==25966==

@p5pRT
Copy link
Author

p5pRT commented Oct 5, 2016

From @hvds

This pattern is causing it to read before the start of the string when we hit the backreference, as can be seen from the offsets and failure output under debug​:

% perl -Mre=Debug,EXECUTE -e '"x"=~/()y|()\1/' 2>&1 | grep -
  -1 <> <%0x> | 17​: END(0)
Match possible, but length=-1 is smaller than requested=0, failing!
  -1 <> <%0x> | 17​: END(0)
Match possible, but length=-2 is smaller than requested=-1, failing!
%

(Note that we get an additional bad read in pv_escape when debug is turned on.)

I /think/ it's not possible for the negative offsets to leak out to something that'd cause us to write; if that's correct, I don't believe this is a security issue. I'd welcome others' opinions.

Patch attached should fix it; test checks for the negative offset in debug output (where available), not sure if there's a better way to do that.

Hugo

@p5pRT
Copy link
Author

p5pRT commented Oct 5, 2016

From @hvds

perl-129377

@p5pRT
Copy link
Author

p5pRT commented Oct 5, 2016

The RT System itself - Status changed from 'new' to 'open'

@p5pRT
Copy link
Author

p5pRT commented Oct 10, 2016

From @geeknik

Found in Perl v5.25.6 (v5.25.5-72-g2814f4b) with AFL + ASAN. Minimizing
with afl-tmin caused the crash to go away, so the un-minimized testcase is
attached.

==6272==ERROR​: AddressSanitizer​: heap-use-after-free on address
0x60200000dc50 at pc 0x000000b9fdcb bp 0x7ffe3cd2e7b0 sp 0x7ffe3cd2e7a8
READ of size 1 at 0x60200000dc50 thread T0
  #0 0xb9fdca in S_regmatch /root/perl/regexec.c​:5440​:9
  #1 0xb734ec in S_regtry /root/perl/regexec.c​:3622​:14
  #2 0xb4b96d in Perl_regexec_flags /root/perl/regexec.c​:3489​:7
  #3 0x8c2998 in Perl_pp_match /root/perl/pp_hot.c​:1818​:10
  #4 0x7f44f3 in Perl_runops_debug /root/perl/dump.c​:2246​:23
  #5 0x5a1216 in S_run_body /root/perl/perl.c​:2526​:2
  #6 0x5a1216 in perl_run /root/perl/perl.c​:2449
  #7 0x4de5cd in main /root/perl/perlmain.c​:123​:9
  #8 0x7f4d5bf8fb44 in __libc_start_main
/build/glibc-daoqzt/glibc-2.19/csu/libc-start.c​:287
  #9 0x4de23c in _start (/root/perl/perl+0x4de23c)

0x60200000dc50 is located 0 bytes inside of 10-byte region
[0x60200000dc50,0x60200000dc5a)
freed by thread T0 here​:
  #0 0x4c0eae in realloc (/root/perl/perl+0x4c0eae)
  #1 0x7f8a26 in Perl_safesysrealloc /root/perl/util.c​:274​:18

previously allocated by thread T0 here​:
  #0 0x4c0bbb in malloc (/root/perl/perl+0x4c0bbb)
  #1 0x7f8337 in Perl_safesysmalloc /root/perl/util.c​:153​:21

SUMMARY​: AddressSanitizer​: heap-use-after-free /root/perl/regexec.c​:5440
S_regmatch
Shadow bytes around the buggy address​:
  0x0c047fff9b30​: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0c047fff9b40​: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0c047fff9b50​: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0c047fff9b60​: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0c047fff9b70​: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
=>0x0c047fff9b80​: fa fa fa fa fa fa 00 00 fa fa[fd]fd fa fa 00 02
  0x0c047fff9b90​: fa fa 00 02 fa fa fd fa fa fa 00 02 fa fa fd fd
  0x0c047fff9ba0​: fa fa fd fa fa fa fd fd fa fa fd fd fa fa fd fa
  0x0c047fff9bb0​: fa fa fd fd fa fa fd fd fa fa 00 02 fa fa fd fd
  0x0c047fff9bc0​: fa fa 01 fa fa fa fd fd fa fa fd fd fa fa 05 fa
  0x0c047fff9bd0​: fa fa fd fd fa fa 00 05 fa fa fd fd fa fa fd fd
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
  Heap right redzone​: fb
  Freed heap region​: fd
  Stack left redzone​: f1
  Stack mid redzone​: f2
  Stack right redzone​: f3
  Stack partial redzone​: f4
  Stack after return​: f5
  Stack use after scope​: f8
  Global redzone​: f9
  Global init order​: f6
  Poisoned by user​: f7
  Container overflow​: fc
  ASan internal​: fe
==6272==ABORTING

@p5pRT
Copy link
Author

p5pRT commented Oct 10, 2016

From @geeknik

test00.gz

@p5pRT
Copy link
Author

p5pRT commented Oct 10, 2016

From @tonycoz

On Sun Oct 09 21​:28​:51 2016, brian.carpenter@​gmail.com wrote​:

Found in Perl v5.25.6 (v5.25.5-72-g2814f4b) with AFL + ASAN. Minimizing
with afl-tmin caused the crash to go away, so the un-minimized testcase is
attached.

Be careful running this case, it consumed a large amount of memory when I attempted to reproduce it under valgrind.

Tony

@p5pRT
Copy link
Author

p5pRT commented Oct 10, 2016

The RT System itself - Status changed from 'new' to 'open'

@p5pRT
Copy link
Author

p5pRT commented Oct 10, 2016

From @hvds

There are two parts to this, plus a lot of non-contributory garbage.

The first part, which is triggering valgrind, is repeatedly doubling a variable in place while matching over it​:

  my $len = 5; # eventual length $len * (2 ** $len)
  my $frag = 'x' x $len;
  $frag =~ m{ ((?{ $frag .= $frag }).)+$ }x;

At some point the doubling causes a realloc, and the string we're matching over moves under us. It might be possible for us to spot this on return from an EVAL node, but I'm not sure what we'd want to do at that point - I doubt it's as simple as updating some pointers to point to the new buffer, though it might be reasonable to just panic() instead. It'd be kinda nice if we had a more generic solution that lets you flag a PV to say "hey, I'm looking at this buffer; if you should want to free it best mortalize it instead".

The second part busts the stack​: the string is actually many copies of '(xxx?' (where xxx is your gid, ${')'}; in my case it tries to become 2 ** 33 copies of a 33-byte string), and attempting to parse it adds 4 stack frames for every copy; if short enough it does eventually die with "Unmatched ( in regex ...", otherwise it either terminates "Out of memory!" or busts the stack and segfaults.

My inclination is that both of these are primarily programmer problems rather than security issues, though I'd class both as nice-to-fix. (Umm, not sure though​: if there's a possibility turning the first part into s/// could cause it to write into the freed buffer, that might be a bigger concern. It still needs the program to be stupid enough to do that though.)

Hugo

@p5pRT
Copy link
Author

p5pRT commented Oct 15, 2016

From @geeknik

I have a smaller test case for this issue​:

perl -e '$q0=q/00|0()0|0()\1/;0=~$q0'

==19699==ERROR​: AddressSanitizer​: heap-buffer-overflow on address
0x60200000dfcf at pc 0x000000b9fd2b bp 0x7ffde9f7a2f0 sp 0x7ffde9f7a2e8
READ of size 1 at 0x60200000dfcf thread T0
  #0 0xb9fd2a in S_regmatch /root/perl/regexec.c​:5440​:9
  #1 0xb7340c in S_regtry /root/perl/regexec.c​:3622​:14
  #2 0xb6187e in S_find_byclass /root/perl/regexec.c​:2693​:44
  #3 0xb4b17c in Perl_regexec_flags /root/perl/regexec.c​:3371​:13
  #4 0x8c2978 in Perl_pp_match /root/perl/pp_hot.c​:1818​:10
  #5 0x7f44b3 in Perl_runops_debug /root/perl/dump.c​:2246​:23
  #6 0x5a12b6 in S_run_body /root/perl/perl.c​:2526​:2
  #7 0x5a12b6 in perl_run /root/perl/perl.c​:2449
  #8 0x4de60d in main /root/perl/perlmain.c​:123​:9
  #9 0x7fe73ece4b44 in __libc_start_main
/build/glibc-daoqzt/glibc-2.19/csu/libc-start.c​:287
  #10 0x4de27c in _start (/root/perl/perl+0x4de27c)

0x60200000dfcf is located 1 bytes to the left of 10-byte region
[0x60200000dfd0,0x60200000dfda)
allocated by thread T0 here​:
  #0 0x4c0bfb in malloc (/root/perl/perl+0x4c0bfb)
  #1 0x7f82f7 in Perl_safesysmalloc /root/perl/util.c​:153​:21

SUMMARY​: AddressSanitizer​: heap-buffer-overflow /root/perl/regexec.c​:5440
S_regmatch
Shadow bytes around the buggy address​:
  0x0c047fff9ba0​: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0c047fff9bb0​: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0c047fff9bc0​: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0c047fff9bd0​: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0c047fff9be0​: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
=>0x0c047fff9bf0​: fa fa fa fa fa fa fa fa fa[fa]00 02 fa fa fd fd
  0x0c047fff9c00​: fa fa fd fd fa fa fd fd fa fa 00 00 fa fa fd fd
  0x0c047fff9c10​: fa fa 00 fa fa fa 05 fa fa fa 00 fa fa fa 00 02
  0x0c047fff9c20​: fa fa fd fa fa fa 00 01 fa fa fd fd fa fa fd fd
  0x0c047fff9c30​: fa fa fd fd fa fa 00 07 fa fa fd fd fa fa fd fd
  0x0c047fff9c40​: fa fa 00 02 fa fa fd fd fa fa fd fd fa fa 02 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
  Heap right redzone​: fb
  Freed heap region​: fd
  Stack left redzone​: f1
  Stack mid redzone​: f2
  Stack right redzone​: f3
  Stack partial redzone​: f4
  Stack after return​: f5
  Stack use after scope​: f8
  Global redzone​: f9
  Global init order​: f6
  Poisoned by user​: f7
  Container overflow​: fc
  ASan internal​: fe
==19699==ABORTING

==12629== Invalid read of size 1
==12629== at 0x5B454A​: S_regmatch (regexec.c​:5440)
==12629== by 0x5B454A​: S_regtry (regexec.c​:3622)
==12629== by 0x5BFBD4​: S_find_byclass (regexec.c​:2693)
==12629== by 0x5C7A80​: Perl_regexec_flags (regexec.c​:3371)
==12629== by 0x505CFC​: Perl_pp_match (pp_hot.c​:1818)
==12629== by 0x4D71A1​: Perl_runops_debug (dump.c​:2246)
==12629== by 0x453156​: S_run_body (perl.c​:2526)
==12629== by 0x453156​: perl_run (perl.c​:2449)
==12629== by 0x421984​: main (perlmain.c​:123)
==12629== Address 0x5f80edf is 1 bytes before a block of size 10 alloc'd
==12629== at 0x4C28C20​: malloc (vg_replace_malloc.c​:296)
==12629== by 0x4D9500​: Perl_safesysmalloc (util.c​:153)
==12629== by 0x525977​: Perl_sv_grow (sv.c​:1605)
==12629== by 0x5268CF​: Perl_sv_2pv_flags (sv.c​:3095)
==12629== by 0x5066D1​: Perl_pp_match (pp_hot.c​:1741)
==12629== by 0x4D71A1​: Perl_runops_debug (dump.c​:2246)
==12629== by 0x453156​: S_run_body (perl.c​:2526)
==12629== by 0x453156​: perl_run (perl.c​:2449)
==12629== by 0x421984​: main (perlmain.c​:123)
==12629==

@p5pRT
Copy link
Author

p5pRT commented Oct 17, 2016

From @hvds

On Fri Oct 14 18​:21​:08 2016, brian.carpenter@​gmail.com wrote​:

I have a smaller test case for this issue​:

perl -e '$q0=q/00|0()0|0()\1/;0=~$q0'

This is rather another case of #129377, and is fixed by my proposed patch there.

Hugo

@p5pRT
Copy link
Author

p5pRT commented Jan 17, 2017

From @tonycoz

On Wed, 05 Oct 2016 05​:03​:45 -0700, hv wrote​:

This pattern is causing it to read before the start of the string when
we hit the backreference, as can be seen from the offsets and failure
output under debug​:

% perl -Mre=Debug,EXECUTE -e '"x"=~/()y|()\1/' 2>&1 | grep -
-1 <> <%0x> | 17​: END(0)
Match possible, but length=-1 is smaller than requested=0, failing!
-1 <> <%0x> | 17​: END(0)
Match possible, but length=-2 is smaller than requested=-1, failing!
%

(Note that we get an additional bad read in pv_escape when debug is
turned on.)

I /think/ it's not possible for the negative offsets to leak out to
something that'd cause us to write; if that's correct, I don't believe
this is a security issue. I'd welcome others' opinions.

Patch attached should fix it; test checks for the negative offset in
debug output (where available), not sure if there's a better way to do
that.

That looks sensible to me.

Your patch seems to be from git show rather than git format-patch, which makes it harder to apply.

Tony

@p5pRT
Copy link
Author

p5pRT commented Jan 19, 2017

From @hvds

On Tue, 17 Jan 2017 15​:24​:46 -0800, tonyc wrote​:

That looks sensible to me.

Thanks Tony, now pushed as 2dfc11e; will move to open queue.

Your patch seems to be from git show rather than git format-patch,
which makes it harder to apply.

Sorry, it didn't occur to me someone might actually apply it. :)

Hugo

@p5pRT
Copy link
Author

p5pRT commented Jan 19, 2017

@hvds - Status changed from 'open' to 'pending release'

@p5pRT
Copy link
Author

p5pRT commented Jan 25, 2017

From @tonycoz

On Fri, 14 Oct 2016 18​:21​:08 -0700, brian.carpenter@​gmail.com wrote​:

I have a smaller test case for this issue​:

perl -e '$q0=q/00|0()0|0()\1/;0=~$q0'

Your original test case produced a stack overflow (deep recursion) for me before or after Hugo's 129377 patch in 2dfc11e.

This test case is fixed by Hugo's patch.

On Mon, 17 Oct 2016 04​:02​:43 -0700, hv wrote​:

On Fri Oct 14 18​:21​:08 2016, brian.carpenter@​gmail.com wrote​:

I have a smaller test case for this issue​:

perl -e '$q0=q/00|0()0|0()\1/;0=~$q0'

This is rather another case of #129377, and is fixed by my proposed
patch there.

So merging this into 129377.

Tony

@p5pRT
Copy link
Author

p5pRT commented Jan 25, 2017

From @hvds

On Tue, 24 Jan 2017 19​:45​:35 -0800, tonyc wrote​:

On Fri, 14 Oct 2016 18​:21​:08 -0700, brian.carpenter@​gmail.com wrote​:

I have a smaller test case for this issue​:

perl -e '$q0=q/00|0()0|0()\1/;0=~$q0'

Your original test case produced a stack overflow (deep recursion) for
me before or after Hugo's 129377 patch in
2dfc11e.

This test case is fixed by Hugo's patch.

On Mon, 17 Oct 2016 04​:02​:43 -0700, hv wrote​:

On Fri Oct 14 18​:21​:08 2016, brian.carpenter@​gmail.com wrote​:

I have a smaller test case for this issue​:

perl -e '$q0=q/00|0()0|0()\1/;0=~$q0'

This is rather another case of #129377, and is fixed by my proposed
patch there.

So merging this into 129377.

I'm not sure merging was the right thing to do - the "another case of #129377" applies only to Brian's followup claim to have a smaller test case, not to the original report.

That's fine though, I can create a clearer new ticket based on the first half of my original analysis - I think we already have ample references to the second (stackbusting) issue there.

Hugo

@p5pRT
Copy link
Author

p5pRT commented May 30, 2017

From @khwilliamson

Thank you for filing this report. You have helped make Perl better.

With the release today of Perl 5.26.0, this and 210 other issues have been
resolved.

Perl 5.26.0 may be downloaded via​:
https://metacpan.org/release/XSAWYERX/perl-5.26.0

If you find that the problem persists, feel free to reopen this ticket.

@p5pRT
Copy link
Author

p5pRT commented May 30, 2017

@khwilliamson - Status changed from 'pending release' to 'resolved'

@p5pRT p5pRT closed this as completed May 30, 2017
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

1 participant