* [Bug c++/61601] C++11 regex resource exhaustion
[not found] <bug-61601-4@http.gcc.gnu.org/bugzilla/>
@ 2014-06-25 9:46 ` redi at gcc dot gnu.org
2014-06-26 6:37 ` [Bug libstdc++/61601] " timshen at gcc dot gnu.org
` (6 subsequent siblings)
7 siblings, 0 replies; 8+ messages in thread
From: redi at gcc dot gnu.org @ 2014-06-25 9:46 UTC (permalink / raw)
To: gcc-bugs
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
^ permalink raw reply [flat|nested] 8+ messages in thread
* [Bug libstdc++/61601] C++11 regex resource exhaustion
[not found] <bug-61601-4@http.gcc.gnu.org/bugzilla/>
2014-06-25 9:46 ` [Bug c++/61601] C++11 regex resource exhaustion redi at gcc dot gnu.org
@ 2014-06-26 6:37 ` timshen at gcc dot gnu.org
2014-07-01 19:28 ` max at cert dot cx
` (5 subsequent siblings)
7 siblings, 0 replies; 8+ messages in thread
From: timshen at gcc dot gnu.org @ 2014-06-26 6:37 UTC (permalink / raw)
To: gcc-bugs
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.
^ permalink raw reply [flat|nested] 8+ messages in thread
* [Bug libstdc++/61601] C++11 regex resource exhaustion
[not found] <bug-61601-4@http.gcc.gnu.org/bugzilla/>
2014-06-25 9:46 ` [Bug c++/61601] C++11 regex resource exhaustion redi at gcc dot gnu.org
2014-06-26 6:37 ` [Bug libstdc++/61601] " timshen at gcc dot gnu.org
@ 2014-07-01 19:28 ` max at cert dot cx
2015-02-01 8:31 ` timshen at gcc dot gnu.org
` (4 subsequent siblings)
7 siblings, 0 replies; 8+ messages in thread
From: max at cert dot cx @ 2014-07-01 19:28 UTC (permalink / raw)
To: gcc-bugs
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)
^ permalink raw reply [flat|nested] 8+ messages in thread
* [Bug libstdc++/61601] C++11 regex resource exhaustion
[not found] <bug-61601-4@http.gcc.gnu.org/bugzilla/>
` (2 preceding siblings ...)
2014-07-01 19:28 ` max at cert dot cx
@ 2015-02-01 8:31 ` timshen at gcc dot gnu.org
2015-02-02 0:37 ` timshen at gcc dot gnu.org
` (3 subsequent siblings)
7 siblings, 0 replies; 8+ messages in thread
From: timshen at gcc dot gnu.org @ 2015-02-01 8:31 UTC (permalink / raw)
To: gcc-bugs
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?
^ permalink raw reply [flat|nested] 8+ messages in thread
* [Bug libstdc++/61601] C++11 regex resource exhaustion
[not found] <bug-61601-4@http.gcc.gnu.org/bugzilla/>
` (3 preceding siblings ...)
2015-02-01 8:31 ` timshen at gcc dot gnu.org
@ 2015-02-02 0:37 ` timshen at gcc dot gnu.org
2015-02-02 18:01 ` max at cert dot cx
` (2 subsequent siblings)
7 siblings, 0 replies; 8+ messages in thread
From: timshen at gcc dot gnu.org @ 2015-02-02 0:37 UTC (permalink / raw)
To: gcc-bugs
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.
^ permalink raw reply [flat|nested] 8+ messages in thread
* [Bug libstdc++/61601] C++11 regex resource exhaustion
[not found] <bug-61601-4@http.gcc.gnu.org/bugzilla/>
` (4 preceding siblings ...)
2015-02-02 0:37 ` timshen at gcc dot gnu.org
@ 2015-02-02 18:01 ` max at cert dot cx
2021-05-04 12:31 ` rguenth at gcc dot gnu.org
2021-05-04 16:35 ` egallager at gcc dot gnu.org
7 siblings, 0 replies; 8+ messages in thread
From: max at cert dot cx @ 2015-02-02 18:01 UTC (permalink / raw)
To: gcc-bugs
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
^ permalink raw reply [flat|nested] 8+ messages in thread
* [Bug libstdc++/61601] C++11 regex resource exhaustion
[not found] <bug-61601-4@http.gcc.gnu.org/bugzilla/>
` (5 preceding siblings ...)
2015-02-02 18:01 ` max at cert dot cx
@ 2021-05-04 12:31 ` rguenth at gcc dot gnu.org
2021-05-04 16:35 ` egallager at gcc dot gnu.org
7 siblings, 0 replies; 8+ messages in thread
From: rguenth at gcc dot gnu.org @ 2021-05-04 12:31 UTC (permalink / raw)
To: gcc-bugs
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
^ permalink raw reply [flat|nested] 8+ messages in thread
* [Bug libstdc++/61601] C++11 regex resource exhaustion
[not found] <bug-61601-4@http.gcc.gnu.org/bugzilla/>
` (6 preceding siblings ...)
2021-05-04 12:31 ` rguenth at gcc dot gnu.org
@ 2021-05-04 16:35 ` egallager at gcc dot gnu.org
7 siblings, 0 replies; 8+ messages in thread
From: egallager at gcc dot gnu.org @ 2021-05-04 16:35 UTC (permalink / raw)
To: gcc-bugs
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)
^ permalink raw reply [flat|nested] 8+ messages in thread