shithub: libmujs

Download patch

ref: fa3d30fd18c348bb4b1f3858fb860f4fcd4b2045
parent: 77ab465f1c394bb77f00966cd950650f3f53cb24
author: Tor Andersson <tor.andersson@gmail.com>
date: Thu Jan 12 10:13:14 EST 2017 

Fix 697448: Limit the maximum program size to something reasonable.

A regular expression with lots of nested repetition can lead to
integer overflow when calculating the size of the program.

Check max program size when counting the number of instructions required
for a loop, so we can bail before integer overflow can happen.


--- a/regexp.c
+++ b/regexp.c
@@ -16,6 +16,7 @@
 #define REPINF 255
 #define MAXTHREAD 1000
 #define MAXSUB REG_MAXSUB
+#define MAXPROG (32 << 10)
 
 typedef struct Reclass Reclass;
 typedef struct Renode Renode;
@@ -595,23 +596,25 @@
 	Reinst *y;
 };
 
-static int count(Renode *node)
+static int count(struct cstate *g, Renode *node)
 {
-	int min, max;
+	int min, max, n;
 	if (!node) return 0;
 	switch (node->type) {
 	default: return 1;
-	case P_CAT: return count(node->x) + count(node->y);
-	case P_ALT: return count(node->x) + count(node->y) + 2;
+	case P_CAT: return count(g, node->x) + count(g, node->y);
+	case P_ALT: return count(g, node->x) + count(g, node->y) + 2;
 	case P_REP:
 		min = node->m;
 		max = node->n;
-		if (min == max) return count(node->x) * min;
-		if (max < REPINF) return count(node->x) * max + (max - min);
-		return count(node->x) * (min + 1) + 2;
-	case P_PAR: return count(node->x) + 2;
-	case P_PLA: return count(node->x) + 2;
-	case P_NLA: return count(node->x) + 2;
+		if (min == max) n = count(g, node->x) * min;
+		else if (max < REPINF) n = count(g, node->x) * max + (max - min);
+		else n = count(g, node->x) * (min + 1) + 2;
+		if (n < 0 || n > MAXPROG) die(g, "program too large");
+		return n;
+	case P_PAR: return count(g, node->x) + 2;
+	case P_PLA: return count(g, node->x) + 2;
+	case P_NLA: return count(g, node->x) + 2;
 	}
 }
 
@@ -813,7 +816,7 @@
 	struct cstate g;
 	Renode *node;
 	Reinst *split, *jump;
-	int i;
+	int i, n;
 
 	g.pstart = NULL;
 	g.prog = NULL;
@@ -847,8 +850,17 @@
 	if (g.lookahead != 0)
 		die(&g, "syntax error");
 
+#ifdef TEST
+	dumpnode(node);
+	putchar('\n');
+#endif
+
+	n = 6 + count(&g, node);
+	if (n < 0 || n > MAXPROG)
+		die(&g, "program too large");
+
 	g.prog->nsub = g.nsub;
-	g.prog->start = g.prog->end = alloc(ctx, NULL, (count(node) + 6) * sizeof (Reinst));
+	g.prog->start = g.prog->end = alloc(ctx, NULL, n * sizeof (Reinst));
 	if (!g.prog->start)
 		die(&g, "cannot allocate regular expression instruction list");
 
@@ -864,8 +876,6 @@
 	emit(g.prog, I_END);
 
 #ifdef TEST
-	dumpnode(node);
-	putchar('\n');
 	dumpprog(g.prog);
 #endif