[Bug c++/61601] C++11 regex resource exhaustion

[Bug c++/61601] C++11 regex resource exhaustion

[redi at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
   Last reconfirmed|                            |2014-06-25
     Ever confirmed|0                           |1

[Bug libstdc++/61601] C++11 regex resource exhaustion

[timshen at gcc dot gnu.org]

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

--- Comment #2 from Tim Shen <timshen at gcc dot gnu.org> ---
(In reply to Jonathan Wakely from comment #1)
> Tim, how hard would it be to hardcode limits somewhere for these cases?

It's easy. 6 lines. I'll propose a patch soon.

[Bug libstdc++/61601] C++11 regex resource exhaustion

[max at cert dot cx]

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

--- Comment #4 from Maksymilian Arciemowicz <max at cert dot cx> ---
cpu exhaustion not eliminated

PoC: (.*{100}{200}findme)

[Bug libstdc++/61601] C++11 regex resource exhaustion

[timshen at gcc dot gnu.org]

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

--- Comment #5 from Tim Shen <timshen at gcc dot gnu.org> ---
> cpu exhaustion not eliminated
>
> PoC: (.*{100}{200}findme)

I tried to run:

#include <regex>

using namespace std;

int main (int argc, char *argv[])
{
  string input;
  regex r(argv[1]);

  return 0;

}

Against '(.*{100}{200}findme)' and there's no cpu exhaustion.

Do you have any other testcases?

[Bug libstdc++/61601] C++11 regex resource exhaustion

[timshen at gcc dot gnu.org]

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

--- Comment #7 from Tim Shen <timshen at gcc dot gnu.org> ---
(In reply to Maksymilian Arciemowicz from comment #6)
> > Do you have any other testcases?
> 
> for trunk? maybe you have to use ::regex_match

std::regex_match("findme", std::regex("(.*{100}{200}findme)"));

there's no memory problem, it just takes exponentially long time to run (which
is expected when using backtracking).

To avoid it, you can use Thompson NFA:

#define _GLIBCXX_REGEX_USE_THOMPSON_NFA
#include <regex>

int main (int argc, char *argv[])
{
  std::regex_match("findme", std::regex("(.*{100}{200}findme)",
std::regex_constants::extended));

  return 0;

}

Notice that for now Thompson NFA doesn't support ECMAScript.

[Bug libstdc++/61601] C++11 regex resource exhaustion

[max at cert dot cx]

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

--- Comment #8 from Maksymilian Arciemowicz <max at cert dot cx> ---
> there's no memory problem, it just takes exponentially long time to run
> (which is expected when using backtracking).

call it cpu resource exhaustion (CWE-400)

> 
> To avoid it, you can use Thompson NFA:
> 
> #define _GLIBCXX_REGEX_USE_THOMPSON_NFA
> #include <regex>
> 
> int main (int argc, char *argv[])
> {
>   std::regex_match("findme", std::regex("(.*{100}{200}findme)",
> std::regex_constants::extended));
> 
>   return 0;
> 
> }
> 
> Notice that for now Thompson NFA doesn't support ECMAScript.

yeap.

try (.*{300}{100}) for _GLIBCXX_REGEX_USE_THOMPSON_NFA. occurs stack exhaustion
like in #61582

[Bug libstdc++/61601] C++11 regex resource exhaustion

[rguenth at gcc dot gnu.org]

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

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

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

[Bug libstdc++/61601] C++11 regex resource exhaustion

[egallager at gcc dot gnu.org]

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

Eric Gallager <egallager at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |egallager at gcc dot gnu.org,
                   |                            |fweimer at redhat dot com,
                   |                            |max at cert dot cx,
                   |                            |rasraizen at gmail dot com,
                   |                            |timshen at gcc dot gnu.org
             Status|ASSIGNED                    |NEW
           Assignee|timshen at gcc dot gnu.org         |unassigned at gcc dot gnu.org

--- Comment #11 from Eric Gallager <egallager at gcc dot gnu.org> ---
(In reply to Tim Shen from comment #10)
> (In reply to Eric Gallager from comment #9)
> > (In reply to Tim Shen from comment #7)
> > > (In reply to Maksymilian Arciemowicz from comment #6)
> > > > > Do you have any other testcases?
> > > > 
> > > > for trunk? maybe you have to use ::regex_match
> > > 
> > > std::regex_match("findme", std::regex("(.*{100}{200}findme)"));
> > > 
> > > there's no memory problem, it just takes exponentially long time to run
> > > (which is expected when using backtracking).
> > > 
> > > To avoid it, you can use Thompson NFA:
> > > 
> > > #define _GLIBCXX_REGEX_USE_THOMPSON_NFA
> > > #include <regex>
> > > 
> > > int main (int argc, char *argv[])
> > > {
> > >   std::regex_match("findme", std::regex("(.*{100}{200}findme)",
> > > std::regex_constants::extended));
> > > 
> > >   return 0;
> > > 
> > > }
> > > 
> > > Notice that for now Thompson NFA doesn't support ECMAScript.
> > 
> > Are you still working on this?
> 
> No, I'm not actively working on this.

moving from assignee to cc list, then (and redoing a few other lost ccs while
I'm at it)