Fixes for problems created when processing regular expressions that

generate very large automata. An enormous number of thanks to Will
Drewry <wad@google.com>, Tavis Ormandy <taviso@google.com>, and Tom
Lane <tgl@sss.pgh.pa.us> from the Postgresql crowd for their help in
tracking these problems down. [Bug 1810264]

7 files changed, 120 insertions, 16 deletions

diff --git a/ChangeLog b/ChangeLog
index 322a551..9aa147d 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,12 @@
+2007-12-18  Donal K. Fellows  <donal.k.fellows@manchester.ac.uk>
+
+	* generic/regguts.h, generic/regc_color.c, generic/regc_nfa.c:
+	Fixes for problems created when processing regular expressions that
+	generate very large automata. An enormous number of thanks to Will
+	Drewry <wad@google.com>, Tavis Ormandy <taviso@google.com>, and Tom
+	Lane <tgl@sss.pgh.pa.us> from the Postgresql crowd for their help in
+	tracking these problems down. [Bug 1810264]
+
 2007-12-17  Don Porter	<dgp@users.sourceforge.net>
 
 	*** 8.5.0 TAGGED FOR RELEASE ***
diff --git a/generic/regc_color.c b/generic/regc_color.c
index 003f5fc..ba1f668 100644
--- a/generic/regc_color.c
+++ b/generic/regc_color.c
@@ -611,12 +611,9 @@ okcolors(
 	    scd->sub = NOSUB;
 	    while ((a = cd->arcs) != NULL) {
 		assert(a->co == co);
-		/* uncolorchain(cm, a); */
-		cd->arcs = a->colorchain;
+		uncolorchain(cm, a);
 		a->co = sco;
-		/* colorchain(cm, a); */
-		a->colorchain = scd->arcs;
-		scd->arcs = a;
+		colorchain(cm, a);
 	    }
 	    freecolor(cm, co);
 	} else {
@@ -648,7 +645,11 @@ colorchain(
 {
     struct colordesc *cd = &cm->cd[a->co];
 
+    if (cd->arcs != NULL) {
+	cd->arcs->colorchainRev = a;
+    }
     a->colorchain = cd->arcs;
+    a->colorchainRev = NULL;
     cd->arcs = a;
 }
 
@@ -662,20 +663,20 @@ uncolorchain(
     struct arc *a)
 {
     struct colordesc *cd = &cm->cd[a->co];
-    struct arc *aa;
+    struct arc *aa = a->colorchainRev;
 
-    aa = cd->arcs;
-    if (aa == a) {		/* easy case */
+    if (aa == NULL) {
+	assert(cd->arcs == a);
 	cd->arcs = a->colorchain;
     } else {
-	assert(aa != NULL);
-	for (; aa->colorchain!=a ; aa=aa->colorchain) {
-	    assert(aa->colorchain != NULL);
-	    continue;
-	}
+	assert(aa->colorchain == a);
 	aa->colorchain = a->colorchain;
     }
+    if (a->colorchain != NULL) {
+	a->colorchain->colorchainRev = aa;
+    }
     a->colorchain = NULL;	/* paranoia */
+    a->colorchainRev = NULL;
 }
 
 /*
diff --git a/generic/regc_nfa.c b/generic/regc_nfa.c
index 741887f..19dbe63 100644
--- a/generic/regc_nfa.c
+++ b/generic/regc_nfa.c
@@ -58,13 +58,14 @@ newnfa(
     nfa->nstates = 0;
     nfa->cm = cm;
     nfa->v = v;
+    nfa->size = 0;
     nfa->bos[0] = nfa->bos[1] = COLORLESS;
     nfa->eos[0] = nfa->eos[1] = COLORLESS;
+    nfa->parent = parent;	/* Precedes newfstate so parent is valid. */
     nfa->post = newfstate(nfa, '@');	/* number 0 */
     nfa->pre = newfstate(nfa, '>');	/* number 1 */
-    nfa->parent = parent;
 
-    nfa->init = newstate(nfa);	/* may become invalid later */
+    nfa->init = newstate(nfa);	/* May become invalid later. */
     nfa->final = newstate(nfa);
     if (ISERR()) {
 	freenfa(nfa);
@@ -85,6 +86,61 @@ newnfa(
 }
 
 /*
+ - TooManyStates - checks if the max states exceeds the compile-time value
+ ^ static int TooManyStates(struct nfa *);
+ */
+static int
+TooManyStates(
+    struct nfa *nfa)
+{
+    struct nfa *parent = nfa->parent;
+    size_t sz = nfa->size;
+
+    while (parent != NULL) {
+	sz = parent->size;
+	parent = parent->parent;
+    }
+    if (sz > REG_MAX_STATES) {
+	return 1;
+    }
+    return 0;
+}
+
+/*
+ - IncrementSize - increases the tracked size of the NFA and its parents.
+ ^ static void IncrementSize(struct nfa *);
+ */
+static void
+IncrementSize(
+    struct nfa *nfa)
+{
+    struct nfa *parent = nfa->parent;
+
+    nfa->size++;
+    while (parent != NULL) {
+	parent->size++;
+	parent = parent->parent;
+    }
+}
+
+/*
+ - DecrementSize - increases the tracked size of the NFA and its parents.
+ ^ static void DecrementSize(struct nfa *);
+ */
+static void
+DecrementSize(
+    struct nfa *nfa)
+{
+    struct nfa *parent = nfa->parent;
+
+    nfa->size--;
+    while (parent != NULL) {
+	parent->size--;
+	parent = parent->parent;
+    }
+}
+
+/*
  - freenfa - free an entire NFA
  ^ static VOID freenfa(struct nfa *);
  */
@@ -120,6 +176,11 @@ newstate(
 {
     struct state *s;
 
+    if (TooManyStates(nfa)) {
+	/* XXX: add specific error for this */
+	NERR(REG_ETOOBIG);
+	return NULL;
+    }
     if (nfa->free != NULL) {
 	s = nfa->free;
 	nfa->free = s->next;
@@ -152,6 +213,12 @@ newstate(
     }
     s->prev = nfa->slast;
     nfa->slast = s;
+
+    /*
+     * Track the current size and the parent size.
+     */
+
+    IncrementSize(nfa);
     return s;
 }
 
@@ -222,6 +289,7 @@ freestate(
     s->prev = NULL;
     s->next = nfa->free;	/* don't delete it, put it on the free list */
     nfa->free = s;
+    DecrementSize(nfa);
 }
 
 /*
@@ -688,6 +756,9 @@ duptraverse(
 
     for (a=s->outs ; a!=NULL && !NISERR() ; a=a->outchain) {
 	duptraverse(nfa, a->to, NULL);
+	if (NISERR()) {
+	    break;
+	}
 	assert(a->to->tmp != NULL);
 	cparc(nfa, a, s->tmp, a->to->tmp);
     }
diff --git a/generic/regerrs.h b/generic/regerrs.h
index a3d98b6..259c0cb 100644
--- a/generic/regerrs.h
+++ b/generic/regerrs.h
@@ -16,3 +16,4 @@
 { REG_INVARG,	"REG_INVARG",	"invalid argument to regex function" },
 { REG_MIXED,	"REG_MIXED",	"character widths of regex and string differ" },
 { REG_BADOPT,	"REG_BADOPT",	"invalid embedded option" },
+{ REG_ETOOBIG,	"REG_ETOOBIG",	"nfa has too many states" },
diff --git a/generic/regex.h b/generic/regex.h
index b8498ab..fa86092 100644
--- a/generic/regex.h
+++ b/generic/regex.h
@@ -277,6 +277,7 @@ typedef struct {
 #define	REG_INVARG	16	/* invalid argument to regex function */
 #define	REG_MIXED	17	/* character widths of regex and string differ */
 #define	REG_BADOPT	18	/* invalid embedded option */
+#define	REG_ETOOBIG	19	/* nfa has too many states */
 /* two specials for debugging and testing */
 #define	REG_ATOI	101	/* convert error-code name to number */
 #define	REG_ITOA	102	/* convert error-code number to name */
diff --git a/generic/regguts.h b/generic/regguts.h
index cbf6615..67e3d03 100644
--- a/generic/regguts.h
+++ b/generic/regguts.h
@@ -267,6 +267,7 @@ struct arc {
 #define	freechain	outchain
     struct arc *inchain;	/* *to's ins chain */
     struct arc *colorchain;	/* color's arc chain */
+    struct arc *colorchainRev;	/* back-link in color's arc chain */
 };
 
 struct arcbatch {		/* for bulk allocation of arcs */
@@ -303,6 +304,9 @@ struct nfa {
     struct colormap *cm;	/* the color map */
     color bos[2];		/* colors, if any, assigned to BOS and BOL */
     color eos[2];		/* colors, if any, assigned to EOS and EOL */
+    size_t size;		/* Current NFA size; differs from nstates as
+				 * it also counts the number of states created
+				 * by children of this state. */
     struct vars *v;		/* simplifies compile error reporting */
     struct nfa *parent;		/* parent NFA, if any */
 };
@@ -332,6 +336,14 @@ struct cnfa {
 #define	NULLCNFA(cnfa)	((cnfa).nstates == 0)
 
 /*
+ * Used to limit the maximum NFA size to something sane. [Bug 1810264]
+ */
+
+#ifndef REG_MAX_STATES
+#   define REG_MAX_STATES	100000
+#endif
+
+/*
  * subexpression tree
  */
 
diff --git a/tests/reg.test b/tests/reg.test
index 40b8766..63d4d3d 100644
--- a/tests/reg.test
+++ b/tests/reg.test
@@ -9,7 +9,7 @@
 #
 # Copyright (c) 1998, 1999 Henry Spencer.  All rights reserved.
 #
-# RCS: @(#) $Id: reg.test,v 1.23 2006/11/03 00:34:53 hobbs Exp $
+# RCS: @(#) $Id: reg.test,v 1.24 2007/12/18 10:53:16 dkf Exp $
 
 if {[lsearch [namespace children] ::tcltest] == -1} {
     package require tcltest 2
@@ -1057,6 +1057,15 @@ test reg-33.11 {Bug 840258} {
     regsub {(^|[\n\r]+)\.*\?<.*?(\n|\r)+} \
 	    "TQ\r\n.?<5000267>Test already stopped\r\n" {} tmp
 } 1
+test reg-33.12 {Bug 1810264 - bad read} {
+    regexp {\3161573148} {\3161573148}
+} 0
+test reg-33.13 {Bug 1810264 - infinite loop} {
+    regexp {($|^)*} {x}
+} 1
+test reg-33.14 {Bug 1810264 - super-expensive expression} {
+    regexp {(x{200}){200}$y} {x}
+} 0
 
 # cleanup
 ::tcltest::cleanupTests