[Bug libstdc++/61582] New: C11 regex memory corruption

[Bug libstdc++/61582] New: C11 regex memory corruption

[max at cert dot cx]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=61582

            Bug ID: 61582
           Summary: C11 regex memory corruption
           Product: gcc
           Version: unknown
            Status: UNCONFIRMED
          Severity: major
          Priority: P3
         Component: libstdc++
          Assignee: unassigned at gcc dot gnu.org
          Reporter: max at cert dot cx

Hi,

Tested on GCC 4.8.1

----------
#include <regex>

using namespace std;

int main (int argc, char *argv[])
{
      regex r(argv[1]);
      return 0;
}
----------

# g++ c11RE.cpp -o c11RE -std=c++11 -Wall 
# ./c11RE '.*'
# ./c11RE '(|'
Segmentation fault (core dumped)
# ./c11RE '((x|'
*** Error in `./c11RE': malloc(): memory corruption: 0x00007fffa0cb8670 ***

Expected (regex_error):
# ./c11RE '(x}' 
terminate called after throwing an instance of 'std::regex_error'
  what():  regex_error
Aborted (core dumped)

------------
(gdb) r '(|'
The program being debugged has been started already.
Start it from the beginning? (y or n) y
Starting program: /home/cx/c11RE '(|'

Program received signal SIGSEGV, Segmentation fault.
0x00000000004022cc in
std::__detail::_StateSeq::_StateSeq(std::__detail::_StateSeq const&) ()
(gdb) bt
#0  0x00000000004022cc in
std::__detail::_StateSeq::_StateSeq(std::__detail::_StateSeq const&) ()
#1  0x0000000000404a05 in std::__detail::_Compiler<char const*,
std::regex_traits<char> >::_M_disjunction() ()
#2  0x0000000000407901 in std::__detail::_Compiler<char const*,
std::regex_traits<char> >::_M_atom() ()
#3  0x00000000004069cb in std::__detail::_Compiler<char const*,
std::regex_traits<char> >::_M_term() ()
#4  0x000000000040567e in std::__detail::_Compiler<char const*,
std::regex_traits<char> >::_M_alternative() ()
#5  0x00000000004049c8 in std::__detail::_Compiler<char const*,
std::regex_traits<char> >::_M_disjunction() ()
#6  0x0000000000403ef2 in std::__detail::_Compiler<char const*,
std::regex_traits<char> >::_Compiler(char const* const&, char const* const&,
std::regex_traits<char>&, unsigned int) ()
#7  0x0000000000403297 in std::shared_ptr<std::__detail::_Automaton>
std::__detail::__compile<char const*, std::regex_traits<char> >(char const*
const&, char const* const&, std::regex_traits<char>&, unsigned int) ()
#8  0x0000000000402abb in std::basic_regex<char, std::regex_traits<char>
>::basic_regex(char const*, unsigned int) ()
#9  0x0000000000401767 in main ()
(gdb) x/i $rip
=> 0x4022cc <_ZNSt8__detail9_StateSeqC2ERKS0_+16>:    mov    (%rax),%rdx
(gdb) x/x $rax
0xffffffffffffffe8:    Cannot access memory at address 0xffffffffffffffe8
(gdb) x/x $rdx
0xffffffffffffffe8:    Cannot access memory at address 0xffffffffffffffe8
------------

BR,
Maksymilian
http://cxsecurity.com/

[Bug libstdc++/61582] C11 regex memory corruption

[redi at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=61582

Jonathan Wakely <redi at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |RESOLVED
         Resolution|---                         |INVALID
           Severity|major                       |normal

--- Comment #1 from Jonathan Wakely <redi at gcc dot gnu.org> ---
*sigh* <regex> is not implemented prior to GCC 4.9.0, I thought the whole world
was aware of that by now.

[Bug libstdc++/61582] C++11 regex memory corruption

[redi at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=61582

Jonathan Wakely <redi at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|RESOLVED                    |NEW
   Last reconfirmed|                            |2014-06-25
         Resolution|INVALID                     |---
            Summary|C11 regex memory corruption |C++11 regex memory
                   |                            |corruption
     Ever confirmed|0                           |1

--- Comment #3 from Jonathan Wakely <redi at gcc dot gnu.org> ---
(In reply to Maksymilian A from comment #2)
> cx@cx:~/REstd11/kozak5$ ./c11re '((x|'
> terminate called after throwing an instance of 'std::regex_error'
>   what():  regex_error
> Przerwane (core dumped)

I think this is by design.

> cx@cx:~/REstd11/kozak5$ ./c11re '((.*)()?*{100})'
> Naruszenie ochrony pamięci (core dumped)

That's a bug.

(It would be helpful if you didn't put C11 in the subject, this has nothing to
do with C)
>From gcc-bugs-return-454862-listarch-gcc-bugs=gcc.gnu.org@gcc.gnu.org Wed Jun 25 09:59:39 2014
Return-Path: <gcc-bugs-return-454862-listarch-gcc-bugs=gcc.gnu.org@gcc.gnu.org>
Delivered-To: listarch-gcc-bugs@gcc.gnu.org
Received: (qmail 6848 invoked by alias); 25 Jun 2014 09:59:38 -0000
Mailing-List: contact gcc-bugs-help@gcc.gnu.org; run by ezmlm
Precedence: bulk
List-Id: <gcc-bugs.gcc.gnu.org>
List-Archive: <http://gcc.gnu.org/ml/gcc-bugs/>
List-Post: <mailto:gcc-bugs@gcc.gnu.org>
List-Help: <mailto:gcc-bugs-help@gcc.gnu.org>
Sender: gcc-bugs-owner@gcc.gnu.org
Delivered-To: mailing list gcc-bugs@gcc.gnu.org
Received: (qmail 6808 invoked by uid 48); 25 Jun 2014 09:59:34 -0000
From: "redi at gcc dot gnu.org" <gcc-bugzilla@gcc.gnu.org>
To: gcc-bugs@gcc.gnu.org
Subject: [Bug c++/61597] Unexpected behavior at runtime
Date: Wed, 25 Jun 2014 09:59:00 -0000
X-Bugzilla-Reason: CC
X-Bugzilla-Type: changed
X-Bugzilla-Watch-Reason: None
X-Bugzilla-Product: gcc
X-Bugzilla-Component: c++
X-Bugzilla-Version: 4.9.0
X-Bugzilla-Keywords:
X-Bugzilla-Severity: normal
X-Bugzilla-Who: redi at gcc dot gnu.org
X-Bugzilla-Status: UNCONFIRMED
X-Bugzilla-Priority: P3
X-Bugzilla-Assigned-To: unassigned at gcc dot gnu.org
X-Bugzilla-Target-Milestone: ---
X-Bugzilla-Flags:
X-Bugzilla-Changed-Fields:
Message-ID: <bug-61597-4-4yCzI5WxlS@http.gcc.gnu.org/bugzilla/>
In-Reply-To: <bug-61597-4@http.gcc.gnu.org/bugzilla/>
References: <bug-61597-4@http.gcc.gnu.org/bugzilla/>
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: 7bit
X-Bugzilla-URL: http://gcc.gnu.org/bugzilla/
Auto-Submitted: auto-generated
MIME-Version: 1.0
X-SW-Source: 2014-06/txt/msg01944.txt.bz2
Content-length: 167

https://gcc.gnu.org/bugzilla/show_bug.cgi?ida597

--- Comment #10 from Jonathan Wakely <redi at gcc dot gnu.org> ---
Thank you - that test case is much more useful

[Bug libstdc++/61582] C++11 regex memory corruption

[redi at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=61582

Jonathan Wakely <redi at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |timshen at gcc dot gnu.org

--- Comment #4 from Jonathan Wakely <redi at gcc dot gnu.org> ---
That segfault is already fixed on trunk, although possibly just latent

[Bug libstdc++/61582] C++11 regex memory corruption

[max at cert dot cx]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=61582

--- Comment #5 from Maksymilian Arciemowicz <max at cert dot cx> ---
Thanks for feedback. I'm going verify this on trunk

[Bug libstdc++/61582] C++11 regex memory corruption

[max at cert dot cx]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=61582

--- Comment #6 from Maksymilian Arciemowicz <max at cert dot cx> ---
@Jonathan: true but check this case

cx@cx:~/REtrunk/kozak5$ ~/gccTRUNK/bin/g++ -v
Using built-in specs.
COLLECT_GCC=/home/cx/gccTRUNK/bin/g++
COLLECT_LTO_WRAPPER=/home/cx/gccTRUNK/libexec/gcc/x86_64-unknown-linux-gnu/4.10.0/lto-wrapper
Target: x86_64-unknown-linux-gnu
Configured with: ../trunk/configure --prefix=/home/cx/gccTRUNK/
--disable-multilib
Thread model: posix
gcc version 4.10.0 20140625 (experimental) (GCC) 
cx@cx:~/REtrunk/kozak5$ ~/gccTRUNK/bin/g++ c11re.c -o c11re -std=c++11
cx@cx:~/REtrunk/kozak5$ ./c11re '(.*{100}{100}{100})'
Naruszenie ochrony pamięci (core dumped)

Program received signal SIGSEGV, Segmentation fault.
0x000000000041014e in std::__detail::_Executor<char const*,
std::allocator<std::sub_match<char const*> >, std::regex_traits<char>,
true>::_State_info<std::integral_constant<bool, true>,
std::vector<std::sub_match<char const*>, std::allocator<std::sub_match<char
const*> > > >::_M_visited(long) const ()

BR,
Maksymilian
http://cxsecurity.com/
>From gcc-bugs-return-454965-listarch-gcc-bugs=gcc.gnu.org@gcc.gnu.org Wed Jun 25 23:38:42 2014
Return-Path: <gcc-bugs-return-454965-listarch-gcc-bugs=gcc.gnu.org@gcc.gnu.org>
Delivered-To: listarch-gcc-bugs@gcc.gnu.org
Received: (qmail 17001 invoked by alias); 25 Jun 2014 23:38:42 -0000
Mailing-List: contact gcc-bugs-help@gcc.gnu.org; run by ezmlm
Precedence: bulk
List-Id: <gcc-bugs.gcc.gnu.org>
List-Archive: <http://gcc.gnu.org/ml/gcc-bugs/>
List-Post: <mailto:gcc-bugs@gcc.gnu.org>
List-Help: <mailto:gcc-bugs-help@gcc.gnu.org>
Sender: gcc-bugs-owner@gcc.gnu.org
Delivered-To: mailing list gcc-bugs@gcc.gnu.org
Received: (qmail 16965 invoked by uid 48); 25 Jun 2014 23:38:37 -0000
From: "gerald at pfeifer dot com" <gcc-bugzilla@gcc.gnu.org>
To: gcc-bugs@gcc.gnu.org
Subject: [Bug other/49342] asm goto documentation error in code snippet
Date: Wed, 25 Jun 2014 23:38:00 -0000
X-Bugzilla-Reason: CC
X-Bugzilla-Type: changed
X-Bugzilla-Watch-Reason: None
X-Bugzilla-Product: gcc
X-Bugzilla-Component: other
X-Bugzilla-Version: 4.7.0
X-Bugzilla-Keywords:
X-Bugzilla-Severity: normal
X-Bugzilla-Who: gerald at pfeifer dot com
X-Bugzilla-Status: RESOLVED
X-Bugzilla-Priority: P3
X-Bugzilla-Assigned-To: unassigned at gcc dot gnu.org
X-Bugzilla-Target-Milestone: ---
X-Bugzilla-Flags:
X-Bugzilla-Changed-Fields: bug_status cc resolution
Message-ID: <bug-49342-4-yiqYMlgNuj@http.gcc.gnu.org/bugzilla/>
In-Reply-To: <bug-49342-4@http.gcc.gnu.org/bugzilla/>
References: <bug-49342-4@http.gcc.gnu.org/bugzilla/>
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: 7bit
X-Bugzilla-URL: http://gcc.gnu.org/bugzilla/
Auto-Submitted: auto-generated
MIME-Version: 1.0
X-SW-Source: 2014-06/txt/msg02047.txt.bz2
Content-length: 925

https://gcc.gnu.org/bugzilla/show_bug.cgi?idI342

Gerald Pfeifer <gerald at pfeifer dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |RESOLVED
                 CC|                            |gccbugzilla@limegreensocks.
                   |                            |com, gerald at pfeifer dot com
         Resolution|---                         |FIXED

--- Comment #1 from Gerald Pfeifer <gerald at pfeifer dot com> ---
Hi Benjamin,

apologies that nobody got back to you re this fix of yours.

I verified, and it turns out this example no longer is in the GCC
documentation, so the bug is "fixed", alas in a different manner.

Thanks for the patch, and if you copy me on future doc patches (which
I hope you'll still provide) I'll see what I can do to expedite those.

[Bug libstdc++/61582] C++11 regex memory corruption

[max at cert dot cx]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=61582

--- Comment #8 from Maksymilian Arciemowicz <max at cert dot cx> ---
(In reply to Tim Shen from comment #7)
> "(.*{100}{100}{100})" seems to be a stack overflow. It's because regex
> executor uses recursion. It could be fixed (not segfault but memory
> exhaustion) by using a std::stack and simulate recursion; IMH, however,
> directly throwing regex_error::error_space is the right thing here to do.

Yeap it's stack overflow. Why regex_error::error_space? Not better
regex_error::error_stack?

[Bug libstdc++/61582] C++11 regex memory corruption

[timshen at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=61582

--- Comment #9 from Tim Shen <timshen at gcc dot gnu.org> ---
(In reply to Maksymilian Arciemowicz from comment #8)
> (In reply to Tim Shen from comment #7)
> > "(.*{100}{100}{100})" seems to be a stack overflow. It's because regex
> > executor uses recursion. It could be fixed (not segfault but memory
> > exhaustion) by using a std::stack and simulate recursion; IMH, however,
> > directly throwing regex_error::error_space is the right thing here to do.
> 
> Yeap it's stack overflow. Why regex_error::error_space? Not better
> regex_error::error_stack?

Sorry for not clarify that: I prefer throwing error_space when constructing
(complaining about too many states) instead of throwing error_stack when
matching. To solve the latter problem, as I said, we can use a std::stack or
something to avoid a stack overflow.

[Bug libstdc++/61582] C++11 regex memory corruption

[max at cert dot cx]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=61582

--- Comment #10 from Maksymilian Arciemowicz <max at cert dot cx> ---
There is also one other alternative like this

http://cvsweb.netbsd.org/bsdweb.cgi/src/lib/libc/regex/regcomp.c.diff?r1=1.29&r2=1.30&f=h

[Bug libstdc++/61582] C++11 regex memory corruption

[timshen at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=61582

--- Comment #11 from Tim Shen <timshen at gcc dot gnu.org> ---
Author: timshen
Date: Tue Jul  1 03:05:45 2014
New Revision: 212185

URL: https://gcc.gnu.org/viewcvs?rev=212185&root=gcc&view=rev
Log:
    PR libstdc++/61061
    PR libstdc++/61582
    * include/bits/regex_automaton.h (_NFA<>::_M_insert_state): Add
    a NFA state limit. If it's exceeded, regex_constants::error_space
    will be throwed.
    * include/bits/regex_automaton.tcc (_StateSeq<>::_M_clone): Use
    map (which is sparse) instead of vector. This reduce n times clones'
    cost from O(n^2) to O(n).
    * include/std/regex: Add map dependency.
    * testsuite/28_regex/algorithms/regex_match/ecma/char/61601.cc: New
    testcase.


Added:
   
trunk/libstdc++-v3/testsuite/28_regex/algorithms/regex_match/ecma/char/61601.cc
Modified:
    trunk/libstdc++-v3/ChangeLog
    trunk/libstdc++-v3/include/bits/regex_automaton.h
    trunk/libstdc++-v3/include/bits/regex_automaton.tcc
    trunk/libstdc++-v3/include/std/regex

[Bug libstdc++/61582] C++11 regex memory corruption

[max at cert dot cx]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=61582

--- Comment #12 from Maksymilian Arciemowicz <max at cert dot cx> ---
Ups. Check this (.*{100}{300})

gcc version 4.10.0 20140701 (experimental) (GCC)
--------
Starting program: /home/cx/REtrunk/kozak5/t3 '(.*{100}{300})'

Program received signal SIGSEGV, Segmentation fault.
0x000000000040c22a in std::__detail::_Executor<char const*,
std::allocator<std::sub_match<char const*> >, std::regex_traits<char>,
true>::_M_dfs(std::__detail::_Executor<char const*,
std::allocator<std::sub_match<char const*> >, std::regex_traits<char>,
true>::_Match_mode, long) ()
--------

[Bug libstdc++/61582] C++11 regex memory corruption

[max at cert dot cx]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=61582

--- Comment #13 from Maksymilian Arciemowicz <max at cert dot cx> ---
@Tim: do you need help?

[Bug libstdc++/61582] C++11 regex memory corruption

[timshen at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=61582

--- Comment #14 from Tim Shen <timshen at gcc dot gnu.org> ---
(In reply to Maksymilian Arciemowicz from comment #13)
> @Tim: do you need help?

This is what I'm going to do:
https://gcc.gnu.org/ml/libstdc++/2014-07/msg00008.html

Please send to libstdc++ ml if you have any ideas.

[Bug libstdc++/61582] C++11 regex memory corruption

[timshen at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=61582

Tim Shen <timshen at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |morandidodo at gmail dot com

--- Comment #15 from Tim Shen <timshen at gcc dot gnu.org> ---
*** Bug 66456 has been marked as a duplicate of this bug. ***

[Bug libstdc++/61582] C++11 regex memory corruption

[timshen at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=61582

Tim Shen <timshen at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |antialize at gmail dot com

--- Comment #16 from Tim Shen <timshen at gcc dot gnu.org> ---
*** Bug 67212 has been marked as a duplicate of this bug. ***

[Bug libstdc++/61582] C++11 regex memory corruption

[rguenth at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=61582

Richard Biener <rguenth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |ASSIGNED

[Bug libstdc++/61582] C++11 regex memory corruption

[redi at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=61582

--- Comment #23 from Jonathan Wakely <redi at gcc dot gnu.org> ---
(In reply to M Welinder from comment #22)
> FWIW, there is an excellent overview of regular expression engine pitfalls
> and methods here:
> 
> https://swtch.com/~rsc/regexp/regexp1.html
> https://swtch.com/~rsc/regexp/regexp2.html
> https://swtch.com/~rsc/regexp/regexp3.html

Yes, there have been links to the first one in libstdc++ headers since 2013.

[Bug libstdc++/61582] C++11 regex memory corruption

[redi at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=61582

Jonathan Wakely <redi at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Last reconfirmed|2014-06-25 00:00:00         |2021-12-16
           Assignee|timshen at gcc dot gnu.org         |redi at gcc dot gnu.org

--- Comment #24 from Jonathan Wakely <redi at gcc dot gnu.org> ---
(In reply to Maksymilian Arciemowicz from comment #12)
> Ups. Check this (.*{100}{300})

This one still results in a stack overflow on trunk, with an 8MB stack. That
is:

std::regex_match("a", std::regex("(.*{100}{300})"));

I have a proof-of-concept patch replacing the recursion in _Executor. The
example above runs successfully with a 16k stack limit.