From: Rich Felker <dalias@libc.org>
To: Konstantin Serebryany <konstantin.s.serebryany@gmail.com>,
musl@lists.openwall.com
Subject: Re: buffer overflow in regcomp and a way to find more of those
Date: Fri, 20 Mar 2015 21:30:16 -0400 [thread overview]
Message-ID: <20150321013016.GS23507@brightrain.aerifal.cx> (raw)
In-Reply-To: <20150321012341.GG16260@port70.net>
On Sat, Mar 21, 2015 at 02:23:41AM +0100, Szabolcs Nagy wrote:
> * Konstantin Serebryany <konstantin.s.serebryany@gmail.com> [2015-03-20 18:10:18 -0700]:
> > After your fix the fuzzer did not find anything else so far, but it
> > suffers from slow performance on some cases.
> > Not sure if this qualifies for a bug, but the following example takes
> > ~2 seconds to run (runs instantly with glibc):
>
> i think the problem is stacked repetitions
> tre doesnt handle them in a sane way
> and uses huge amount of ram
Sadly there doesn't seem to be any sane way to handle them...
> for * it would be easy to solve, but
> the general case is theoretically impossible to
> solve: x{255}{255} will be a 255*255 state machine
>
> this is the only part in the musl regex
> engine that's allowed to have super linear
> space/time complexity
>
> (you might want to add some logic to avoid
> such stacked repetitions to speed up the search)
>
> (btw the standard does not allow these, but if
> the pattern is parenthesized around every repetition
> then that's ok: (x*)* is a valid pattern, x** is not,
> so there is not much point rejecting these patterns
> the problem does not go away since grouping is allowed)
>
> > int main() {
> > regex_t preg;
> > const char *s = ".****\\Z$<\\0)_";
Isn't the \0 an invalid backreference? Could it be getting processed
in a way that's causing the slowdown, but simply rejected by glibc?
Rich
next prev parent reply other threads:[~2015-03-21 1:30 UTC|newest]
Thread overview: 42+ messages / expand[flat|nested] mbox.gz Atom feed top
2015-03-20 20:17 Konstantin Serebryany
2015-03-20 20:40 ` Rich Felker
2015-03-20 21:28 ` Szabolcs Nagy
2015-03-20 23:48 ` Szabolcs Nagy
2015-03-20 22:32 ` Rich Felker
2015-03-20 23:52 ` Szabolcs Nagy
2015-03-21 0:06 ` Konstantin Serebryany
2015-03-21 0:26 ` Szabolcs Nagy
2015-03-21 0:46 ` Rich Felker
2015-03-21 0:54 ` Konstantin Serebryany
2015-03-21 1:00 ` Rich Felker
2015-03-21 1:05 ` Konstantin Serebryany
2015-03-21 1:10 ` Konstantin Serebryany
2015-03-21 1:23 ` Szabolcs Nagy
2015-03-21 1:30 ` Rich Felker [this message]
2015-03-21 2:10 ` Szabolcs Nagy
2015-03-21 2:17 ` Rich Felker
2015-03-21 1:32 ` Rich Felker
2015-03-21 1:37 ` Konstantin Serebryany
2015-03-21 1:56 ` Rich Felker
2015-03-21 2:14 ` Konstantin Serebryany
2015-03-21 2:20 ` Rich Felker
2015-03-21 6:05 ` Konstantin Serebryany
2015-03-21 13:28 ` Szabolcs Nagy
2015-03-21 21:03 ` Szabolcs Nagy
2015-03-21 21:38 ` Szabolcs Nagy
2015-03-21 22:13 ` Szabolcs Nagy
2015-03-22 6:36 ` Justin Cormack
2015-03-23 5:02 ` Konstantin Serebryany
2015-03-23 12:25 ` Szabolcs Nagy
2015-03-23 15:56 ` Konstantin Serebryany
2015-03-23 4:55 ` Konstantin Serebryany
2015-03-23 12:35 ` Szabolcs Nagy
2015-03-23 14:40 ` stephen Turner
2015-03-23 14:53 ` Szabolcs Nagy
2015-03-23 15:46 ` stephen Turner
2015-03-23 16:28 ` Rich Felker
2015-03-23 17:21 ` Nathan McSween
2015-03-28 22:00 ` Szabolcs Nagy
2015-03-28 22:32 ` Konstantin Serebryany
2015-03-28 22:38 ` Rich Felker
2015-03-28 23:15 ` Szabolcs Nagy
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=20150321013016.GS23507@brightrain.aerifal.cx \
--to=dalias@libc.org \
--cc=konstantin.s.serebryany@gmail.com \
--cc=musl@lists.openwall.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
Code repositories for project(s) associated with this public inbox
https://git.vuxu.org/mirror/musl/
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).