Better fix for the "unbounded recursion case", for example

\(b*\)\(a*\1\)*, more cases in regress/lib/libc/regexp/test.
Only stop evaluation of a back reference if the match lenght is
zero and the recursion level is too deep. With help from jaredy@
Problem case found by Andrew Brown in NetBSD PR 28126.
ok deraadt@ millert@

1 files changed, 18 insertions, 17 deletions

diff --git a/lib/libc/regex/engine.c b/lib/libc/regex/engine.c
index 035c2f7153a..fd02dca60ee 100644
--- a/lib/libc/regex/engine.c
+++ b/lib/libc/regex/engine.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: engine.c,v 1.11 2004/10/17 17:58:54 otto Exp $	*/
+/*	$OpenBSD: engine.c,v 1.12 2004/11/29 16:49:50 otto Exp $	*/
 
 /*-
  * Copyright (c) 1992, 1993, 1994 Henry Spencer.
@@ -36,7 +36,7 @@
  */
 
 #if defined(SNAMES) && defined(LIBC_SCCS) && !defined(lint)
-static char enginercsid[] = "$OpenBSD: engine.c,v 1.11 2004/10/17 17:58:54 otto Exp $";
+static char enginercsid[] = "$OpenBSD: engine.c,v 1.12 2004/11/29 16:49:50 otto Exp $";
 #endif /* SNAMES and LIBC_SCCS and not lint */
 
 /*
@@ -96,10 +96,11 @@ extern "C" {
 /* === engine.c === */
 static int matcher(struct re_guts *g, char *string, size_t nmatch, regmatch_t pmatch[], int eflags);
 static char *dissect(struct match *m, char *start, char *stop, sopno startst, sopno stopst);
-static char *backref(struct match *m, char *start, char *stop, sopno startst, sopno stopst, sopno lev);
+static char *backref(struct match *m, char *start, char *stop, sopno startst, sopno stopst, sopno lev, int);
 static char *fast(struct match *m, char *start, char *stop, sopno startst, sopno stopst);
 static char *slow(struct match *m, char *start, char *stop, sopno startst, sopno stopst);
 static states step(struct re_guts *g, sopno start, sopno stop, states bef, int ch, states aft);
+#define MAX_RECURSION	100
 #define	BOL	(OUT+1)
 #define	EOL	(BOL+1)
 #define	BOLEOL	(BOL+2)
@@ -238,7 +239,7 @@ matcher(struct re_guts *g, char *string, size_t nmatch, regmatch_t pmatch[],
 				return(REG_ESPACE);
 			}
 			NOTE("backref dissect");
-			dp = backref(m, m->coldp, endp, gf, gl, (sopno)0);
+			dp = backref(m, m->coldp, endp, gf, gl, (sopno)0, 0);
 		}
 		if (dp != NULL)
 			break;
@@ -261,7 +262,7 @@ matcher(struct re_guts *g, char *string, size_t nmatch, regmatch_t pmatch[],
 			}
 #endif
 			NOTE("backoff dissect");
-			dp = backref(m, m->coldp, endp, gf, gl, (sopno)0);
+			dp = backref(m, m->coldp, endp, gf, gl, (sopno)0, 0);
 		}
 		assert(dp == NULL || dp == endp);
 		if (dp != NULL)		/* found a shorter one */
@@ -488,7 +489,7 @@ dissect(struct match *m, char *start, char *stop, sopno startst, sopno stopst)
  */
 static char *			/* == stop (success) or NULL (failure) */
 backref(struct match *m, char *start, char *stop, sopno startst, sopno stopst,
-    sopno lev)			/* PLUS nesting level */
+    sopno lev, int rec)			/* PLUS nesting level */
 {
 	int i;
 	sopno ss;	/* start sop of current subRE */
@@ -594,7 +595,7 @@ backref(struct match *m, char *start, char *stop, sopno startst, sopno stopst,
 			return(NULL);
 		assert(m->pmatch[i].rm_so != -1);
 		len = m->pmatch[i].rm_eo - m->pmatch[i].rm_so;
-		if (len == 0)
+		if (len == 0 && rec++ > MAX_RECURSION)
 			return(NULL);
 		assert(stop - m->beginp >= len);
 		if (sp > stop - len)
@@ -604,28 +605,28 @@ backref(struct match *m, char *start, char *stop, sopno startst, sopno stopst,
 			return(NULL);
 		while (m->g->strip[ss] != SOP(O_BACK, i))
 			ss++;
-		return(backref(m, sp+len, stop, ss+1, stopst, lev));
+		return(backref(m, sp+len, stop, ss+1, stopst, lev, rec));
 		break;
 	case OQUEST_:		/* to null or not */
-		dp = backref(m, sp, stop, ss+1, stopst, lev);
+		dp = backref(m, sp, stop, ss+1, stopst, lev, rec);
 		if (dp != NULL)
 			return(dp);	/* not */
-		return(backref(m, sp, stop, ss+OPND(s)+1, stopst, lev));
+		return(backref(m, sp, stop, ss+OPND(s)+1, stopst, lev, rec));
 		break;
 	case OPLUS_:
 		assert(m->lastpos != NULL);
 		assert(lev+1 <= m->g->nplus);
 		m->lastpos[lev+1] = sp;
-		return(backref(m, sp, stop, ss+1, stopst, lev+1));
+		return(backref(m, sp, stop, ss+1, stopst, lev+1, rec));
 		break;
 	case O_PLUS:
 		if (sp == m->lastpos[lev])	/* last pass matched null */
-			return(backref(m, sp, stop, ss+1, stopst, lev-1));
+			return(backref(m, sp, stop, ss+1, stopst, lev-1, rec));
 		/* try another pass */
 		m->lastpos[lev] = sp;
-		dp = backref(m, sp, stop, ss-OPND(s)+1, stopst, lev);
+		dp = backref(m, sp, stop, ss-OPND(s)+1, stopst, lev, rec);
 		if (dp == NULL)
-			return(backref(m, sp, stop, ss+1, stopst, lev-1));
+			return(backref(m, sp, stop, ss+1, stopst, lev-1, rec));
 		else
 			return(dp);
 		break;
@@ -634,7 +635,7 @@ backref(struct match *m, char *start, char *stop, sopno startst, sopno stopst,
 		esub = ss + OPND(s) - 1;
 		assert(OP(m->g->strip[esub]) == OOR1);
 		for (;;) {	/* find first matching branch */
-			dp = backref(m, sp, stop, ssub, esub, lev);
+			dp = backref(m, sp, stop, ssub, esub, lev, rec);
 			if (dp != NULL)
 				return(dp);
 			/* that one missed, try next one */
@@ -655,7 +656,7 @@ backref(struct match *m, char *start, char *stop, sopno startst, sopno stopst,
 		assert(0 < i && i <= m->g->nsub);
 		offsave = m->pmatch[i].rm_so;
 		m->pmatch[i].rm_so = sp - m->offp;
-		dp = backref(m, sp, stop, ss+1, stopst, lev);
+		dp = backref(m, sp, stop, ss+1, stopst, lev, rec);
 		if (dp != NULL)
 			return(dp);
 		m->pmatch[i].rm_so = offsave;
@@ -666,7 +667,7 @@ backref(struct match *m, char *start, char *stop, sopno startst, sopno stopst,
 		assert(0 < i && i <= m->g->nsub);
 		offsave = m->pmatch[i].rm_eo;
 		m->pmatch[i].rm_eo = sp - m->offp;
-		dp = backref(m, sp, stop, ss+1, stopst, lev);
+		dp = backref(m, sp, stop, ss+1, stopst, lev, rec);
 		if (dp != NULL)
 			return(dp);
 		m->pmatch[i].rm_eo = offsave;