From mboxrd@z Thu Jan 1 00:00:00 1970 X-Msuck: nntp://news.gmane.org/gmane.linux.lib.musl.general/7233 Path: news.gmane.org!not-for-mail From: Szabolcs Nagy Newsgroups: gmane.linux.lib.musl.general Subject: Re: buffer overflow in regcomp and a way to find more of those Date: Sat, 21 Mar 2015 02:23:41 +0100 Message-ID: <20150321012341.GG16260@port70.net> References: <20150320235227.GE16260@port70.net> <20150321002616.GF16260@port70.net> <20150321004637.GQ23507@brightrain.aerifal.cx> <20150321010043.GR23507@brightrain.aerifal.cx> Reply-To: musl@lists.openwall.com NNTP-Posting-Host: plane.gmane.org Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii X-Trace: ger.gmane.org 1426901051 4360 80.91.229.3 (21 Mar 2015 01:24:11 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Sat, 21 Mar 2015 01:24:11 +0000 (UTC) Cc: Rich Felker , musl@lists.openwall.com To: Konstantin Serebryany Original-X-From: musl-return-7246-gllmg-musl=m.gmane.org@lists.openwall.com Sat Mar 21 02:23:56 2015 Return-path: Envelope-to: gllmg-musl@m.gmane.org Original-Received: from mother.openwall.net ([195.42.179.200]) by plane.gmane.org with smtp (Exim 4.69) (envelope-from ) id 1YZ88p-0004KV-Bz for gllmg-musl@m.gmane.org; Sat, 21 Mar 2015 02:23:55 +0100 Original-Received: (qmail 21939 invoked by uid 550); 21 Mar 2015 01:23:53 -0000 Mailing-List: contact musl-help@lists.openwall.com; run by ezmlm Precedence: bulk List-Post: List-Help: List-Unsubscribe: List-Subscribe: Original-Received: (qmail 21921 invoked from network); 21 Mar 2015 01:23:53 -0000 Mail-Followup-To: Konstantin Serebryany , Rich Felker , musl@lists.openwall.com Content-Disposition: inline In-Reply-To: User-Agent: Mutt/1.5.23 (2014-03-12) Xref: news.gmane.org gmane.linux.lib.musl.general:7233 Archived-At: * Konstantin Serebryany [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 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)_"; > regmatch_t pmatch[2]; > if (0 == regcomp(&preg, s, 0)) { > regexec(&preg, s, 0, pmatch, 0); > regfree(&preg); > } > return 0; > } >