Fix assorted security-grade bugs in the regex engine. All of these problems

are shared with Tcl, since it's their code to begin with, and the patches
have been copied from Tcl 8.5.0.  Problems:

CVE-2007-4769: Inadequate check on the range of backref numbers allows
crash due to out-of-bounds read.
CVE-2007-4772: Infinite loop in regex optimizer for pattern '($|^)*'.
CVE-2007-6067: Very slow optimizer cleanup for regex with a large NFA
representation, as well as crash if we encounter an out-of-memory condition
during NFA construction.

Part of the response to CVE-2007-6067 is to put a limit on the number of
states in the NFA representation of a regex.  This seems needed even though
the within-the-code problems have been corrected, since otherwise the code
could try to use very large amounts of memory for a suitably-crafted regex,
leading to potential DOS by driving the system into swap, activating a kernel
OOM killer, etc.

Although there are certainly plenty of ways to drive the system into effective
DOS with poorly-written SQL queries, these problems seem worth treating as
security issues because many applications might accept regex search patterns
from untrustworthy sources.

Thanks to Will Drewry of Google for reporting these problems.  Patches by Will
Drewry and Tom Lane.

Security: CVE-2007-4769, CVE-2007-4772, CVE-2007-6067

3 files changed, 18 insertions, 4 deletions

diff --git a/src/include/regex/regerrs.h b/src/include/regex/regerrs.h
index 77baf97f4bb..85307b526fc 100644
--- a/src/include/regex/regerrs.h
+++ b/src/include/regex/regerrs.h
@@ -1,5 +1,5 @@
 /*
- * $PostgreSQL: pgsql/src/include/regex/regerrs.h,v 1.3 2003/11/29 22:41:10 pgsql Exp $
+ * $PostgreSQL: pgsql/src/include/regex/regerrs.h,v 1.3.6.1 2008/01/03 20:48:57 tgl Exp $
  */
 
 {
@@ -73,3 +73,7 @@
 {
 	REG_BADOPT, "REG_BADOPT", "invalid embedded option"
 },
+
+{
+	REG_ETOOBIG, "REG_ETOOBIG", "nfa has too many states"
+},
diff --git a/src/include/regex/regex.h b/src/include/regex/regex.h
index 9cda1c23ebc..b52152d139c 100644
--- a/src/include/regex/regex.h
+++ b/src/include/regex/regex.h
@@ -29,7 +29,7 @@
  * OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
  * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  *
- * $PostgreSQL: pgsql/src/include/regex/regex.h,v 1.28 2005/10/15 02:49:46 momjian Exp $
+ * $PostgreSQL: pgsql/src/include/regex/regex.h,v 1.28.2.1 2008/01/03 20:48:57 tgl Exp $
  */
 
 /*
@@ -151,6 +151,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/src/include/regex/regguts.h b/src/include/regex/regguts.h
index 18712b4090d..7a2676eea9c 100644
--- a/src/include/regex/regguts.h
+++ b/src/include/regex/regguts.h
@@ -27,7 +27,7 @@
  * OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
  * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  *
- * $PostgreSQL: pgsql/src/include/regex/regguts.h,v 1.5 2005/10/15 02:49:46 momjian Exp $
+ * $PostgreSQL: pgsql/src/include/regex/regguts.h,v 1.5.2.1 2008/01/03 20:48:57 tgl Exp $
  */
 
 
@@ -272,6 +272,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
@@ -311,6 +312,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 */
 };
@@ -343,7 +347,12 @@ struct cnfa
 #define ZAPCNFA(cnfa)	((cnfa).nstates = 0)
 #define NULLCNFA(cnfa)	((cnfa).nstates == 0)
 
-
+/*
+ * Used to limit the maximum NFA size to something sane. [Tcl Bug 1810264]
+ */
+#ifndef REG_MAX_STATES
+#define REG_MAX_STATES	100000
+#endif
 
 /*
  * subexpression tree