Use after free in unicode wildcard property matching

[lightsey]

Description
handle_names_wildcard() creates a variable "must" for the re_intuit_string() of a regex it will repeatedly match. The initial evaluation of the regex may free the SV this "must" pointer refers to, causing handle_names_wildcard() to dereference a dangling pointer.

Steps to Reproduce
Compile blead with clang and ASAN:

./Configure -des -Dusedevel -DDEBUGGING=-g -Doptimize=-O0 -Dcc=clang -Accflags="-g -O0 -m32 -fsanitize=address -fno-omit-frame-pointer" -Aldflags="-g -O0 -m32 -fsanitize=address -fno-omit-frame-pointer" -Alddlflags="-shared -g -O0 -m32 -fsanitize=address  -fno-omit-frame-pointer"

Example regex:

jd@toucan:~/src/git/lab/perl5 (blead)$ PERL5LIB=lib ./perl -e 'my $re = q<[[\p{name=/[Y-]+Z/}]]>; eval { "" =~ /$re/ }; print $@ if $@; print "Done\n";'
The Unicode property wildcards feature is experimental at -e line 1.
=================================================================
==16600==ERROR: AddressSanitizer: heap-use-after-free on address 0xf5a31e30 at pc 0x080985db bp 0xff9eeca8 sp 0xff9ee868
READ of size 1 at 0xf5a31e30 thread T0
    #0 0x80985da in strspn (/home/jd/src/git/lab/perl5/perl+0x80985da)
    #1 0x8660053 in S_handle_names_wildcard /home/jd/src/git/lab/perl5/regcomp.c:25226:16
    #2 0x8650818 in S_parse_uniprop_string /home/jd/src/git/lab/perl5/regcomp.c:23857:25
    #3 0x85e4172 in S_regclass /home/jd/src/git/lab/perl5/regcomp.c:17704:44
    #4 0x856cef9 in S_regatom /home/jd/src/git/lab/perl5/regcomp.c:13478:15
    #5 0x8557987 in S_regpiece /home/jd/src/git/lab/perl5/regcomp.c:12591:11
    #6 0x8527b46 in S_regbranch /home/jd/src/git/lab/perl5/regcomp.c:12511:18
    #7 0x849b76c in S_reg /home/jd/src/git/lab/perl5/regcomp.c:12213:10
    #8 0x843ffd1 in Perl_re_op_compile /home/jd/src/git/lab/perl5/regcomp.c:7845:9
    #9 0x895b7ff in Perl_pp_regcomp /home/jd/src/git/lab/perl5/pp_ctl.c:114:14
    #10 0x879288f in Perl_runops_standard /home/jd/src/git/lab/perl5/run.c:41:26
    #11 0x825092d in S_run_body /home/jd/src/git/lab/perl5/perl.c:2759:2
    #12 0x824e546 in perl_run /home/jd/src/git/lab/perl5/perl.c:2682:2
    #13 0x8154029 in main /home/jd/src/git/lab/perl5/perlmain.c:127:9
    #14 0xf7be7b40 in __libc_start_main (/lib/i386-linux-gnu/libc.so.6+0x1ab40)
    #15 0x807fd11 in _start (/home/jd/src/git/lab/perl5/perl+0x807fd11)

0xf5a31e30 is located 0 bytes inside of 10-byte region [0xf5a31e30,0xf5a31e3a)
freed by thread T0 here:
    #0 0x81231f3 in __interceptor_free (/home/jd/src/git/lab/perl5/perl+0x81231f3)
    #1 0x86a3ac6 in Perl_safesysfree /home/jd/src/git/lab/perl5/util.c:399:2
    #2 0x884f0b8 in Perl_sv_clear /home/jd/src/git/lab/perl5/sv.c:6830:7
    #3 0x8854501 in Perl_sv_free2 /home/jd/src/git/lab/perl5/sv.c:7132:9
    #4 0x8aca464 in Perl_SvREFCNT_dec /home/jd/src/git/lab/perl5/./inline.h:235:6
    #5 0x8a959ca in Perl_re_intuit_start /home/jd/src/git/lab/perl5/regexec.c:1654:6
    #6 0x8a866dd in Perl_regexec_flags /home/jd/src/git/lab/perl5/regexec.c:3390:6
    #7 0x866269d in S_execute_wildcard /home/jd/src/git/lab/perl5/regcomp.c:23193:14
    #8 0x865eba7 in S_handle_names_wildcard /home/jd/src/git/lab/perl5/regcomp.c:25086:16
    #9 0x8650818 in S_parse_uniprop_string /home/jd/src/git/lab/perl5/regcomp.c:23857:25
    #10 0x85e4172 in S_regclass /home/jd/src/git/lab/perl5/regcomp.c:17704:44
    #11 0x856cef9 in S_regatom /home/jd/src/git/lab/perl5/regcomp.c:13478:15
    #12 0x8557987 in S_regpiece /home/jd/src/git/lab/perl5/regcomp.c:12591:11
    #13 0x8527b46 in S_regbranch /home/jd/src/git/lab/perl5/regcomp.c:12511:18
    #14 0x849b76c in S_reg /home/jd/src/git/lab/perl5/regcomp.c:12213:10
    #15 0x843ffd1 in Perl_re_op_compile /home/jd/src/git/lab/perl5/regcomp.c:7845:9
    #16 0x895b7ff in Perl_pp_regcomp /home/jd/src/git/lab/perl5/pp_ctl.c:114:14
    #17 0x879288f in Perl_runops_standard /home/jd/src/git/lab/perl5/run.c:41:26
    #18 0x825092d in S_run_body /home/jd/src/git/lab/perl5/perl.c:2759:2
    #19 0x824e546 in perl_run /home/jd/src/git/lab/perl5/perl.c:2682:2
    #20 0x8154029 in main /home/jd/src/git/lab/perl5/perlmain.c:127:9
    #21 0xf7be7b40 in __libc_start_main (/lib/i386-linux-gnu/libc.so.6+0x1ab40)

previously allocated by thread T0 here:
    #0 0x8123555 in malloc (/home/jd/src/git/lab/perl5/perl+0x8123555)
    #1 0x86a32b3 in Perl_safesysmalloc /home/jd/src/git/lab/perl5/util.c:155:21
    #2 0x87f8300 in Perl_sv_grow /home/jd/src/git/lab/perl5/sv.c:1616:17
    #3 0x880cf1c in Perl_sv_setpvn /home/jd/src/git/lab/perl5/sv.c:4993:12
    #4 0x8868db5 in Perl_newSVpvn /home/jd/src/git/lab/perl5/sv.c:9445:5
    #5 0x844529d in Perl_re_op_compile /home/jd/src/git/lab/perl5/regcomp.c:8178:24
    #6 0x8662499 in S_compile_wildcard /home/jd/src/git/lab/perl5/regcomp.c:23130:21
    #7 0x865e74c in S_handle_names_wildcard /home/jd/src/git/lab/perl5/regcomp.c:25070:21
    #8 0x8650818 in S_parse_uniprop_string /home/jd/src/git/lab/perl5/regcomp.c:23857:25
    #9 0x85e4172 in S_regclass /home/jd/src/git/lab/perl5/regcomp.c:17704:44
    #10 0x856cef9 in S_regatom /home/jd/src/git/lab/perl5/regcomp.c:13478:15
    #11 0x8557987 in S_regpiece /home/jd/src/git/lab/perl5/regcomp.c:12591:11
    #12 0x8527b46 in S_regbranch /home/jd/src/git/lab/perl5/regcomp.c:12511:18
    #13 0x849b76c in S_reg /home/jd/src/git/lab/perl5/regcomp.c:12213:10
    #14 0x843ffd1 in Perl_re_op_compile /home/jd/src/git/lab/perl5/regcomp.c:7845:9
    #15 0x895b7ff in Perl_pp_regcomp /home/jd/src/git/lab/perl5/pp_ctl.c:114:14
    #16 0x879288f in Perl_runops_standard /home/jd/src/git/lab/perl5/run.c:41:26
    #17 0x825092d in S_run_body /home/jd/src/git/lab/perl5/perl.c:2759:2
    #18 0x824e546 in perl_run /home/jd/src/git/lab/perl5/perl.c:2682:2
    #19 0x8154029 in main /home/jd/src/git/lab/perl5/perlmain.c:127:9
    #20 0xf7be7b40 in __libc_start_main (/lib/i386-linux-gnu/libc.so.6+0x1ab40)

Perl configuration

Summary of my perl5 (revision 5 version 31 subversion 11) configuration:
  Commit id: c3ac3d3a0cd6dfd27ca304bfa677a49ca62fd76d
  Platform:
    osname=linux
    osvers=4.19.0-8-amd64
    archname=x86_64-linux
    uname='linux toucan 4.19.0-8-amd64 #1 smp debian 4.19.98-1 (2020-01-26) x86_64 gnulinux '
    config_args='-des -Dusedevel -DDEBUGGING=-g -Doptimize=-O0 -Dcc=clang -Accflags=-g -O0 -m32 -fsanitize=address -fno-omit-frame-pointer -Aldflags=-g -O0 -m32 -fsanitize=address -fno-omit-frame-pointer -Alddlflags=-shared -g -O0 -m32 -fsanitize=address  -fno-omit-frame-pointer'
    hint=recommended
    useposix=true
    d_sigaction=define
    useithreads=undef
    usemultiplicity=undef
    use64bitint=undef
    use64bitall=undef
    uselongdouble=undef
    usemymalloc=n
    default_inc_excludes_dot=define
    bincompat5005=undef
  Compiler:
    cc='clang'
    ccflags ='-g -O0 -m32 -fsanitize=address -fno-omit-frame-pointer -fno-strict-aliasing -pipe -fstack-protector-strong -I/usr/local/include -D_LARGEFILE_SOURCE -D_FILE_OFFSET_BITS=64 -D_FORTIFY_SOURCE=2'
    optimize='-O0 -g'
    cppflags='-g -O0 -m32 -fsanitize=address -fno-omit-frame-pointer -fno-strict-aliasing -pipe -fstack-protector-strong -I/usr/local/include'
    ccversion=''
    gccversion='4.2.1 Compatible Clang 7.0.1 (tags/RELEASE_701/final)'
    gccosandvers=''
    intsize=4
    longsize=4
    ptrsize=4
    doublesize=8
    byteorder=1234
    doublekind=3
    d_longlong=define
    longlongsize=8
    d_longdbl=define
    longdblsize=12
    longdblkind=3
    ivtype='long'
    ivsize=4
    nvtype='double'
    nvsize=8
    Off_t='off_t'
    lseeksize=8
    alignbytes=4
    prototype=define
  Linker and Libraries:
    ld='clang'
    ldflags =' -g -O0 -m32 -fsanitize=address -fno-omit-frame-pointer -fstack-protector-strong -L/usr/local/lib'
    libpth=/usr/local/lib /usr/lib/llvm-7/lib/clang/7.0.1/lib /usr/include/x86_64-linux-gnu /usr/lib /lib/x86_64-linux-gnu /lib/../lib /usr/lib/x86_64-linux-gnu /usr/lib/../lib /lib
    libs=-lpthread -lnsl -lgdbm -ldl -lm -lcrypt -lutil -lc
    perllibs=-lpthread -lnsl -ldl -lm -lcrypt -lutil -lc
    libc=libc-2.28.so
    so=so
    useshrplib=false
    libperl=libperl.a
    gnulibc_version='2.28'
  Dynamic Linking:
    dlsrc=dl_dlopen.xs
    dlext=so
    d_dlsymun=undef
    ccdlflags='-Wl,-E'
    cccdlflags='-fPIC'
    lddlflags=' -shared -g -O0 -m32 -fsanitize=address -fno-omit-frame-pointer -L/usr/local/lib -fstack-protector-strong'


Characteristics of this binary (from libperl): 
  Compile-time options:
    HAS_TIMES
    PERLIO_LAYERS
    PERL_COPY_ON_WRITE
    PERL_DONT_CREATE_GVSV
    PERL_MALLOC_WRAP
    PERL_OP_PARENT
    PERL_PRESERVE_IVUV
    PERL_USE_DEVEL
    USE_LARGE_FILES
    USE_LOCALE
    USE_LOCALE_COLLATE
    USE_LOCALE_CTYPE
    USE_LOCALE_NUMERIC
    USE_LOCALE_TIME
    USE_PERLIO
    USE_PERL_ATOF
  Built under linux
  Compiled at Apr 20 2020 22:58:24
  %ENV:
    PERL5LIB="lib"
  @INC:
    lib
    /usr/local/lib/perl5/site_perl/5.31.11/x86_64-linux
    /usr/local/lib/perl5/site_perl/5.31.11
    /usr/local/lib/perl5/5.31.11/x86_64-linux
    /usr/local/lib/perl5/5.31.11

[khwilliamson]

The root cause of this is that the function re_intuit_string() was returning an SV without giving clear title to the caller. And that SV was getting freed by executing the regex engine. It turns out that no place in core had been using this function, which dates to at least 1999, until this new use of it was recently made.

The solutipm @lightsey proposed works, but doesn't fix the root cause. Instead I propose changing the function to increment the ref count, and the caller can decrement it when done. This protects any future use of the function.

I'm proposing instead #17738

[hvds]

The root cause of this is that the function re_intuit_string() was returning an SV without giving clear title to the caller. And that SV was getting freed by executing the regex engine. It turns out that no place in core had been using this function, which dates to at least 1999, until this new use of it was recently made.

The solutipm @lightsey proposed works, but doesn't fix the root cause. Instead I propose changing the function to increment the ref count, and the caller can decrement it when done. This protects any future use of the function.

I'm proposing instead #17738

I think re_intuit_string() is used via CALLREG_INTUIT_STRING, by way of the regexp_engine structure. It may be better to add a macro that wraps that with a refcount-inc.

The engine structure has suddenly become relevant several times in recent weeks; for 5.34 we should maybe consider revisiting it a bit more formally to see if its definition, documentation and implementation are fit for purpose - and also to consider whether having it as part of the public API makes sense.

[khwilliamson]

I think re_intuit_string() is used via CALLREG_INTUIT_STRING, by way of the regexp_engine structure. It may be better to add a macro that wraps that with a refcount-inc.

You-re right. I should have seen that reference. And that macro is called once in the core. And not at all in CPAN, nor is the function called directly or through the structure in CPAN. perlreapi refers to this function in the structure, but doesn't indicate that its return can be freed without notice. embed.fnc indicates the function is core-only., so that is wrong.

I see the following options:

1. Keep the macro and code as-is, and document that the function result is volatile, and apply something like @lightsey's patch.

2. Apply my patch, changing the single core use of the macro to decrement the ref count. And change perlreapi to indicate that this is needed.

3. Change the function to instead return a mortalized copy, and document this in perlreapi. I don't know what an expected life span of the return value is? I think there is the possibility of it being longer than this would provide as it doesn't get zapped until the pattern is executed, which could be a long time later than when it is inspected. Maybe it shouldn't be getting zapped, and option 4) would be to not do that.

Doing 2) or 3) or 4) would potentially fix bugs in darkpan.

I'd rather do 3) than add another wrapping macro since it would be too easy to forget to decrement the ref count and thereby leak.

The engine structure has suddenly become relevant several times in recent weeks; for 5.34 we should maybe consider revisiting it a bit more formally to see if its definition, documentation and implementation are fit for purpose - and also to consider whether having it as part of the public API makes sense.

This feature is actually used. I have no idea how extensively. @demerphq may have a better feel for this. But I'm sure we can't get rid of it.

[khwilliamson]

I have done some more research. I think @iabyn can shed some light on this, as he was the last person to touch the code in regexec.c for re_intuit_start()

The pattern match execution engine keeps track of the utility of the heuristics used as to where in the matched string to actually start looking. It uses the macro BmUSEFUL for this by incrementing and decrementing a counter. When that counter reaches 0, it decides it wasn't of much use, and frees two SV's to indicate to not rely on them in the future. One of those SV's is the one whose freeing is the cause of this bug.

My guess is that no one involved realized that that SV is publicly accessible via an API that doesn't indicate it is a volatile value.

Further, when those SV's are freed, it also clears a flag that indicates to look at them, and potentially to look at other heuristics. There is a comment saying this is redundant and a relic of an earlier implementation.

My first inclination is: Why free these scalars that are being relied on by outside code. Why not just use another flag to indicate whether re_intuit_start should be using them or not. There are some flag bits available. Then I looked further. It turns out that the current flag is already a combination of two flags RXf_USE_INTUIT_NOML and RXf_USE_INTUIT_ML, neither of which is referred to individually in core nor in CPAN. I presume they are also relics of earlier implementation.

And the only time this combo flag is cleared is when these scalars are freed, there actually isn't any other independent heuristic currently in use. Thus this bug would go away if re_intuit_start removed its freeing of this SV's, and then change to use the flag in the single instance in regexec.c that look at if it is extant or not.

[hvds]

Sorry to be slow responding here: I do not think it would be reasonable to change the behaviour of the regexp engine interface for 5.32, which I believe your proposed option 3 implies - hence the suggestion of a wrapping macro as a stopgap. I'm perfectly happy to consider the behavour change for 5.34.