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

1 files changed, 11 insertions, 2 deletions

diff --git a/src/include/regex/regguts.h b/src/include/regex/regguts.h
index 18712b4090d..327808338a0 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.6 2008/01/03 20:47:55 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