From owner-freebsd-bugs@FreeBSD.ORG Thu Jun 21 20:30:14 2012 Return-Path: Delivered-To: freebsd-bugs@hub.freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [69.147.83.52]) by hub.freebsd.org (Postfix) with ESMTP id 975E01065724 for ; Thu, 21 Jun 2012 20:30:14 +0000 (UTC) (envelope-from gnats@FreeBSD.org) Received: from freefall.freebsd.org (freefall.freebsd.org [IPv6:2001:4f8:fff6::28]) by mx1.freebsd.org (Postfix) with ESMTP id 69DF38FC16 for ; Thu, 21 Jun 2012 20:30:14 +0000 (UTC) Received: from freefall.freebsd.org (localhost [127.0.0.1]) by freefall.freebsd.org (8.14.5/8.14.5) with ESMTP id q5LKUEZr056757 for ; Thu, 21 Jun 2012 20:30:14 GMT (envelope-from gnats@freefall.freebsd.org) Received: (from gnats@localhost) by freefall.freebsd.org (8.14.5/8.14.5/Submit) id q5LKUEHW056754; Thu, 21 Jun 2012 20:30:14 GMT (envelope-from gnats) Resent-Date: Thu, 21 Jun 2012 20:30:14 GMT Resent-Message-Id: <201206212030.q5LKUEHW056754@freefall.freebsd.org> Resent-From: FreeBSD-gnats-submit@FreeBSD.org (GNATS Filer) Resent-To: freebsd-bugs@FreeBSD.org Resent-Reply-To: FreeBSD-gnats-submit@FreeBSD.org, Zak Blacher Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2001:4f8:fff6::34]) by hub.freebsd.org (Postfix) with ESMTP id DFBB8106564A for ; Thu, 21 Jun 2012 20:27:19 +0000 (UTC) (envelope-from nobody@FreeBSD.org) Received: from red.freebsd.org (red.freebsd.org [IPv6:2001:4f8:fff6::22]) by mx1.freebsd.org (Postfix) with ESMTP id CA8DF8FC0C for ; Thu, 21 Jun 2012 20:27:19 +0000 (UTC) Received: from red.freebsd.org (localhost [127.0.0.1]) by red.freebsd.org (8.14.4/8.14.4) with ESMTP id q5LKRJn6065729 for ; Thu, 21 Jun 2012 20:27:19 GMT (envelope-from nobody@red.freebsd.org) Received: (from nobody@localhost) by red.freebsd.org (8.14.4/8.14.4/Submit) id q5LKRJwH065728; Thu, 21 Jun 2012 20:27:19 GMT (envelope-from nobody) Message-Id: <201206212027.q5LKRJwH065728@red.freebsd.org> Date: Thu, 21 Jun 2012 20:27:19 GMT From: Zak Blacher To: freebsd-gnats-submit@FreeBSD.org X-Send-Pr-Version: www-3.1 Cc: Subject: misc/169302: Applied MidnightBSD regex memory consumption limits X-BeenThere: freebsd-bugs@freebsd.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: Bug reports List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Thu, 21 Jun 2012 20:30:15 -0000 >Number: 169302 >Category: misc >Synopsis: Applied MidnightBSD regex memory consumption limits >Confidential: no >Severity: non-critical >Priority: low >Responsible: freebsd-bugs >State: open >Quarter: >Keywords: >Date-Required: >Class: sw-bug >Submitter-Id: current-users >Arrival-Date: Thu Jun 21 20:30:14 UTC 2012 >Closed-Date: >Last-Modified: >Originator: Zak Blacher >Release: 8.2 >Organization: Sandvine Inc. >Environment: FreeBSD hostname.xxxxxxxx 8.82.0213-RELEASE-p5 FreeBSD 8.82.0213-RELEASE-p5 #124: Tue Jun 19 10:21:28 EDT 2012 root@hostname.xxxxxxxx:/path/ amd64 >Description: re: http://seclists.org/fulldisclosure/2011/Nov/53 Applied MidnightBSD patch to regex library. Asserts an upper limit on memory and recursion depth one regular expression can consume. >How-To-Repeat: >Fix: Patch attached with submission follows: --- src/lib/libc/regex/regcomp.c 2008/10/30 20:39:06 1.1.1.2 +++ src/lib/libc/regex/regcomp.c 2011/11/04 17:42:29 1.3 @@ -81,11 +81,11 @@ extern "C" { #endif /* === regcomp.c === */ -static void p_ere(struct parse *p, wint_t stop); -static void p_ere_exp(struct parse *p); +static void p_ere(struct parse *p, wint_t stop, size_t reclimit); +static void p_ere_exp(struct parse *p, size_t reclimit); static void p_str(struct parse *p); -static void p_bre(struct parse *p, wint_t end1, wint_t end2); -static int p_simp_re(struct parse *p, int starordinary); +static void p_bre(struct parse *p, wint_t end1, wint_t end2, size_t reclimit); +static int p_simp_re(struct parse *p, int starordinary, size_t reclimit); static int p_count(struct parse *p); static void p_bracket(struct parse *p); static void p_b_term(struct parse *p, cset *cs); @@ -97,7 +97,7 @@ static wint_t othercase(wint_t ch); static void bothcases(struct parse *p, wint_t ch); static void ordinary(struct parse *p, wint_t ch); static void nonnewline(struct parse *p); -static void repeat(struct parse *p, sopno start, int from, int to); +static void repeat(struct parse *p, sopno start, int from, int to, size_t reclimit); static int seterr(struct parse *p, int e); static cset *allocset(struct parse *p); static void freeset(struct parse *p, cset *cs); @@ -109,7 +109,7 @@ static sopno dupl(struct parse *p, sopno static void doemit(struct parse *p, sop op, size_t opnd); static void doinsert(struct parse *p, sop op, size_t opnd, sopno pos); static void dofwd(struct parse *p, sopno pos, sop value); -static void enlarge(struct parse *p, sopno size); +static int enlarge(struct parse *p, sopno size); static void stripsnug(struct parse *p, struct re_guts *g); static void findmust(struct parse *p, struct re_guts *g); static int altoffset(sop *scan, int offset); @@ -162,6 +162,13 @@ static int never = 0; /* for use in ass #define never 0 /* some s have bugs too */ #endif +#define MEMLIMIT 0x8000000 +#define MEMSIZE(p) \ +((p)->ncsalloc / CHAR_BIT + \ +(p)->ncsalloc * sizeof(cset) + \ +(p)->ssize * sizeof(sop)) +#define RECLIMIT 256 + /* Macro used by computejump()/computematchjump() */ #define MIN(a,b) ((a)<(b)?(a):(b)) @@ -244,11 +251,11 @@ regcomp(regex_t * __restrict preg, EMIT(OEND, 0); g->firststate = THERE(); if (cflags®_EXTENDED) - p_ere(p, OUT); + p_ere(p, OUT, 0); else if (cflags®_NOSPEC) p_str(p); else - p_bre(p, OUT, OUT); + p_bre(p, OUT, OUT, 0); EMIT(OEND, 0); g->laststate = THERE(); @@ -289,19 +296,25 @@ regcomp(regex_t * __restrict preg, */ static void p_ere(struct parse *p, - int stop) /* character this ERE should end at */ + int stop, /* character this ERE should end at */ + size_t reclimit) { char c; sopno prevback; sopno prevfwd; sopno conc; int first = 1; /* is this the first alternative? */ + + if (reclimit++ > RECLIMIT || p->error == REG_ESPACE) { + p->error = REG_ESPACE; + return; + } for (;;) { /* do a bunch of concatenated expressions */ conc = HERE(); while (MORE() && (c = PEEK()) != '|' && c != stop) - p_ere_exp(p); + p_ere_exp(p, reclimit); (void)REQUIRE(HERE() != conc, REG_EMPTY); /* require nonempty */ if (!EAT('|')) @@ -333,7 +346,7 @@ p_ere(struct parse *p, == static void p_ere_exp(struct parse *p); */ static void -p_ere_exp(struct parse *p) +p_ere_exp(struct parse *p, size_t reclimit) { char c; wint_t wc; @@ -356,7 +369,7 @@ p_ere_exp(struct parse *p) p->pbegin[subno] = HERE(); EMIT(OLPAREN, subno); if (!SEE(')')) - p_ere(p, ')'); + p_ere(p, ')', reclimit); if (subno < NPAREN) { p->pend[subno] = HERE(); assert(p->pend[subno] != 0); @@ -460,7 +473,7 @@ p_ere_exp(struct parse *p) count2 = INFINITY; } else /* just a single number */ count2 = count; - repeat(p, pos, count, count2); + repeat(p, pos, count, count2, reclimit); if (!EAT('}')) { /* error heuristics */ while (MORE() && PEEK() != '}') NEXT(); @@ -504,8 +517,15 @@ p_str(struct parse *p) static void p_bre(struct parse *p, int end1, /* first terminating character */ - int end2) /* second terminating character */ + int end2, /* second terminating character */ + size_t reclimit) { + + if (reclimit++ > RECLIMIT || p->error == REG_ESPACE) { + p->error = REG_ESPACE; + return; + } + sopno start = HERE(); int first = 1; /* first subexpression? */ int wasdollar = 0; @@ -516,7 +536,7 @@ p_bre(struct parse *p, p->g->nbol++; } while (MORE() && !SEETWO(end1, end2)) { - wasdollar = p_simp_re(p, first); + wasdollar = p_simp_re(p, first, reclimit); first = 0; } if (wasdollar) { /* oops, that was a trailing anchor */ @@ -535,7 +555,8 @@ p_bre(struct parse *p, */ static int /* was the simple RE an unbackslashed $? */ p_simp_re(struct parse *p, - int starordinary) /* is a leading * an ordinary character? */ + int starordinary, /* is a leading * an ordinary character? */ + size_t reclimit) { int c; int count; @@ -575,7 +596,7 @@ p_simp_re(struct parse *p, EMIT(OLPAREN, subno); /* the MORE here is an error heuristic */ if (MORE() && !SEETWO('\\', ')')) - p_bre(p, '\\', ')'); + p_bre(p, '\\', ')', reclimit); if (subno < NPAREN) { p->pend[subno] = HERE(); assert(p->pend[subno] != 0); @@ -636,7 +657,7 @@ p_simp_re(struct parse *p, count2 = INFINITY; } else /* just a single number */ count2 = count; - repeat(p, pos, count, count2); + repeat(p, pos, count, count2, reclimit); if (!EATTWO('\\', '}')) { /* error heuristics */ while (MORE() && !SEETWO('\\', '}')) NEXT(); @@ -995,7 +1016,8 @@ static void repeat(struct parse *p, sopno start, /* operand from here to end of strip */ int from, /* repeated from this number */ - int to) /* to this number of times (maybe INFINITY) */ + int to, /* to this number of times (maybe INFINITY) */ + size_t reclimit) { sopno finish = HERE(); # define N 2 @@ -1018,7 +1040,7 @@ repeat(struct parse *p, case REP(0, INF): /* as x{1,}? */ /* KLUDGE: emit y? as (y|) until subtle bug gets fixed */ INSERT(OCH_, start); /* offset is wrong... */ - repeat(p, start+1, 1, to); + repeat(p, start+1, 1, to, reclimit); ASTERN(OOR1, start); AHEAD(start); /* ... fix it */ EMIT(OOR2, 0); @@ -1038,7 +1060,7 @@ repeat(struct parse *p, ASTERN(O_CH, THERETHERE()); copy = dupl(p, start+1, finish+1); assert(copy == finish+4); - repeat(p, copy, 1, to-1); + repeat(p, copy, 1, to-1, reclimit); break; case REP(1, INF): /* as x+ */ INSERT(OPLUS_, start); @@ -1046,11 +1068,11 @@ repeat(struct parse *p, break; case REP(N, N): /* as xx{m-1,n-1} */ copy = dupl(p, start, finish); - repeat(p, copy, from-1, to-1); + repeat(p, copy, from-1, to-1, reclimit); break; case REP(N, INF): /* as xx{n-1,INF} */ copy = dupl(p, start, finish); - repeat(p, copy, from-1, to); + repeat(p, copy, from-1, to, reclimit); break; default: /* "can't happen" */ SETERROR(REG_ASSERT); /* just in case */ @@ -1104,9 +1126,13 @@ static cset * allocset(struct parse *p) { cset *cs, *ncs; + + if (MEMSIZE(p) > MEMLIMIT) + goto oomem; ncs = realloc(p->g->sets, (p->g->ncsets + 1) * sizeof(*ncs)); if (ncs == NULL) { + oomem: SETERROR(REG_ESPACE); return (NULL); } @@ -1246,8 +1272,8 @@ dupl(struct parse *p, assert(finish >= start); if (len == 0) return(ret); - enlarge(p, p->ssize + len); /* this many unexpected additions */ - assert(p->ssize >= p->slen + len); + if (!enlarge(p, p->ssize + len)) /* this many unexpected additions */ + return ret; (void) memcpy((char *)(p->strip + p->slen), (char *)(p->strip + start), (size_t)len*sizeof(sop)); p->slen += len; @@ -1274,8 +1300,8 @@ doemit(struct parse *p, sop op, size_t o /* deal with undersized strip */ if (p->slen >= p->ssize) - enlarge(p, (p->ssize+1) / 2 * 3); /* +50% */ - assert(p->slen < p->ssize); + if (!enlarge(p, (p->ssize+1) / 2 * 3)) /* +50% */ + return; /* finally, it's all reduced to the easy case */ p->strip[p->slen++] = SOP(op, opnd); @@ -1336,21 +1362,27 @@ dofwd(struct parse *p, sopno pos, sop va - enlarge - enlarge the strip == static void enlarge(struct parse *p, sopno size); */ -static void +static int enlarge(struct parse *p, sopno size) { sop *sp; + sopno osize; if (p->ssize >= size) - return; - + return 1; + osize = p->ssize; + p->ssize = size; + if (MEMSIZE(p) > MEMLIMIT) + goto oomem; sp = (sop *)realloc(p->strip, size*sizeof(sop)); if (sp == NULL) { +oomem: + p->ssize = osize; SETERROR(REG_ESPACE); - return; + return 0; } p->strip = sp; - p->ssize = size; + return 1; } /* >Release-Note: >Audit-Trail: >Unformatted: