CVE-2019-11413: Uncontrolled Recursion (CWE-674)
value: An issue was discovered in Artifex MuJS 1.0.5. It has unlimited recursion because the match function in regexp.c lacks a depth check.
CWE description: The product does not properly control the amount of recursion that takes place,  consuming excessive resources, such as allocated memory or the program stack.
CVSS v3 base score: 7.5
Published: 2019-04-22T11:29Z
Repository: https://github.com/ccxvii/mujs
Language: C
Files changed: jsregexp.c, jsstring.c, regexp.c
Commit date: 2019-04-04 12:41:04 +0200
Commit message: Bug 700937: Limit recursion in regexp matcher.

Also handle negative return code as an error in the JS bindings.

Diff: diff --git a/jsregexp.c b/jsregexp.c
index 9f58e15..98b2a86 100644
--- a/jsregexp.c
+++ b/jsregexp.c
@@ -27,10 +27,11 @@ void js_newregexp(js_State *J, const char *pattern, int flags)
 	js_pushobject(J, obj);
 }
 
 void js_RegExp_prototype_exec(js_State *J, js_Regexp *re, const char *text)
 {
+	int result;
 	int i;
 	int opts;
 	Resub m;
 
 	opts = 0;
@@ -44,11 +45,14 @@ void js_RegExp_prototype_exec(js_State *J, js_Regexp *re, const char *text)
 			text += re->last;
 			opts |= REG_NOTBOL;
 		}
 	}
 
-	if (!js_regexec(re->prog, text, &m, opts)) {
+	result = js_regexec(re->prog, text, &m, opts);
+	if (result < 0)
+		js_error(J, "regexec failed");
+	if (result == 0) {
 		js_newarray(J);
 		js_pushstring(J, text);
 		js_setproperty(J, -2, "input");
 		js_pushnumber(J, js_utfptrtoidx(text, m.sub[0].sp));
 		js_setproperty(J, -2, "index");
@@ -69,10 +73,11 @@ void js_RegExp_prototype_exec(js_State *J, js_Regexp *re, const char *text)
 
 static void Rp_test(js_State *J)
 {
 	js_Regexp *re;
 	const char *text;
+	int result;
 	int opts;
 	Resub m;
 
 	re = js_toregexp(J, 0);
 	text = js_tostring(J, 1);
@@ -88,11 +93,14 @@ static void Rp_test(js_State *J)
 			text += re->last;
 			opts |= REG_NOTBOL;
 		}
 	}
 
-	if (!js_regexec(re->prog, text, &m, opts)) {
+	result = js_regexec(re->prog, text, &m, opts);
+	if (result < 0)
+		js_error(J, "regexec failed");
+	if (result == 0) {
 		if (re->flags & JS_REGEXP_G)
 			re->last = re->last + (m.sub[0].ep - text);
 		js_pushboolean(J, 1);
 		return;
 	}
diff --git a/jsstring.c b/jsstring.c
index 9ac46ef..29d2b8a 100644
--- a/jsstring.c
+++ b/jsstring.c
@@ -2,10 +2,18 @@
 #include "jsvalue.h"
 #include "jsbuiltin.h"
 #include "utf.h"
 #include "regexp.h"
 
+static int js_doregexec(js_State *J, Reprog *prog, const char *string, Resub *sub, int eflags)
+{
+	int result = js_regexec(prog, string, sub, eflags);
+	if (result < 0)
+		js_error(J, "regexec failed");
+	return result;
+}
+
 static const char *checkstring(js_State *J, int idx)
 {
 	if (!js_iscoercible(J, idx))
 		js_typeerror(J, "string function called on null or undefined");
 	return js_tostring(J, idx);
@@ -341,11 +349,11 @@ static void Sp_match(js_State *J)
 
 	len = 0;
 	a = text;
 	e = text + strlen(text);
 	while (a <= e) {
-		if (js_regexec(re->prog, a, &m, a > text ? REG_NOTBOL : 0))
+		if (js_doregexec(J, re->prog, a, &m, a > text ? REG_NOTBOL : 0))
 			break;
 
 		b = m.sub[0].sp;
 		c = m.sub[0].ep;
 
@@ -378,11 +386,11 @@ static void Sp_search(js_State *J)
 	else
 		js_newregexp(J, js_tostring(J, 1), 0);
 
 	re = js_toregexp(J, -1);
 
-	if (!js_regexec(re->prog, text, &m, 0))
+	if (!js_doregexec(J, re->prog, text, &m, 0))
 		js_pushnumber(J, js_utfptrtoidx(text, m.sub[0].sp));
 	else
 		js_pushnumber(J, -1);
 }
 
@@ -395,11 +403,11 @@ static void Sp_replace_regexp(js_State *J)
 	Resub m;
 
 	source = checkstring(J, 0);
 	re = js_toregexp(J, 1);
 
-	if (js_regexec(re->prog, source, &m, 0)) {
+	if (js_doregexec(J, re->prog, source, &m, 0)) {
 		js_copy(J, 0);
 		return;
 	}
 
 	re->last = 0;
@@ -469,11 +477,11 @@ loop:
 			if (*source)
 				js_putc(J, &sb, *source++);
 			else
 				goto end;
 		}
-		if (!js_regexec(re->prog, source, &m, REG_NOTBOL))
+		if (!js_doregexec(J, re->prog, source, &m, REG_NOTBOL))
 			goto loop;
 	}
 
 end:
 	js_puts(J, &sb, s + n);
@@ -574,21 +582,21 @@ static void Sp_split_regexp(js_State *J)
 
 	e = text + strlen(text);
 
 	/* splitting the empty string */
 	if (e == text) {
-		if (js_regexec(re->prog, text, &m, 0)) {
+		if (js_doregexec(J, re->prog, text, &m, 0)) {
 			if (len == limit) return;
 			js_pushliteral(J, "");
 			js_setindex(J, -2, 0);
 		}
 		return;
 	}
 
 	p = a = text;
 	while (a < e) {
-		if (js_regexec(re->prog, a, &m, a > text ? REG_NOTBOL : 0))
+		if (js_doregexec(J, re->prog, a, &m, a > text ? REG_NOTBOL : 0))
 			break; /* no match */
 
 		b = m.sub[0].sp;
 		c = m.sub[0].ep;
 
diff --git a/regexp.c b/regexp.c
index d683a28..3f800e3 100644
--- a/regexp.c
+++ b/regexp.c
@@ -14,10 +14,11 @@
 #define nelem(a) (int)(sizeof (a) / sizeof (a)[0])
 
 #define REPINF 255
 #define MAXSUB REG_MAXSUB
 #define MAXPROG (32 << 10)
+#define MAXREC 1024
 
 typedef struct Reclass Reclass;
 typedef struct Renode Renode;
 typedef struct Reinst Reinst;
 typedef struct Rethread Rethread;
@@ -965,102 +966,116 @@ static int strncmpcanon(const char *a, const char *b, int n)
 			return c;
 	}
 	return 0;
 }
 
-static int match(Reinst *pc, const char *sp, const char *bol, int flags, Resub *out)
+static int match(Reinst *pc, const char *sp, const char *bol, int flags, Resub *out, int depth)
 {
 	Resub scratch;
+	int result;
 	int i;
 	Rune c;
 
+	/* stack overflow */
+	if (depth > MAXREC)
+		return -1;
+
 	for (;;) {
 		switch (pc->opcode) {
 		case I_END:
-			return 1;
+			return 0;
 		case I_JUMP:
 			pc = pc->x;
 			break;
 		case I_SPLIT:
 			scratch = *out;
-			if (match(pc->x, sp, bol, flags, &scratch)) {
+			result = match(pc->x, sp, bol, flags, &scratch, depth+1);
+			if (result == -1)
+				return -1;
+			if (result == 0) {
 				*out = scratch;
-				return 1;
+				return 0;
 			}
 			pc = pc->y;
 			break;
 
 		case I_PLA:
-			if (!match(pc->x, sp, bol, flags, out))
-				return 0;
+			result = match(pc->x, sp, bol, flags, out, depth+1);
+			if (result == -1)
+				return -1;
+			if (result == 1)
+				return 1;
 			pc = pc->y;
 			break;
 		case I_NLA:
 			scratch = *out;
-			if (match(pc->x, sp, bol, flags, &scratch))
-				return 0;
+			result = match(pc->x, sp, bol, flags, &scratch, depth+1);
+			if (result == -1)
+				return -1;
+			if (result == 0)
+				return 1;
 			pc = pc->y;
 			break;
 
 		case I_ANYNL:
 			sp += chartorune(&c, sp);
 			if (c == 0)
-				return 0;
+				return 1;
 			pc = pc + 1;
 			break;
 		case I_ANY:
 			sp += chartorune(&c, sp);
 			if (c == 0)
-				return 0;
+				return 1;
 			if (isnewline(c))
-				return 0;
+				return 1;
 			pc = pc + 1;
 			break;
 		case I_CHAR:
 			sp += chartorune(&c, sp);
 			if (c == 0)
-				return 0;
+				return 1;
 			if (flags & REG_ICASE)
 				c = canon(c);
 			if (c != pc->c)
-				return 0;
+				return 1;
 			pc = pc + 1;
 			break;
 		case I_CCLASS:
 			sp += chartorune(&c, sp);
 			if (c == 0)
-				return 0;
+				return 1;
 			if (flags & REG_ICASE) {
 				if (!incclasscanon(pc->cc, canon(c)))
-					return 0;
+					return 1;
 			} else {
 				if (!incclass(pc->cc, c))
-					return 0;
+					return 1;
 			}
 			pc = pc + 1;
 			break;
 		case I_NCCLASS:
 			sp += chartorune(&c, sp);
 			if (c == 0)
-				return 0;
+				return 1;
 			if (flags & REG_ICASE) {
 				if (incclasscanon(pc->cc, canon(c)))
-					return 0;
+					return 1;
 			} else {
 				if (incclass(pc->cc, c))
-					return 0;
+					return 1;
 			}
 			pc = pc + 1;
 			break;
 		case I_REF:
 			i = out->sub[pc->n].ep - out->sub[pc->n].sp;
 			if (flags & REG_ICASE) {
 				if (strncmpcanon(sp, out->sub[pc->n].sp, i))
-					return 0;
+					return 1;
 			} else {
 				if (strncmp(sp, out->sub[pc->n].sp, i))
-					return 0;
+					return 1;
 			}
 			if (i > 0)
 				sp += i;
 			pc = pc + 1;
 			break;
@@ -1074,11 +1089,11 @@ static int match(Reinst *pc, const char *sp, const char *bol, int flags, Resub *
 				if (sp > bol && isnewline(sp[-1])) {
 					pc = pc + 1;
 					break;
 				}
 			}
-			return 0;
+			return 1;
 		case I_EOL:
 			if (*sp == 0) {
 				pc = pc + 1;
 				break;
 			}
@@ -1086,23 +1101,23 @@ static int match(Reinst *pc, const char *sp, const char *bol, int flags, Resub *
 				if (isnewline(*sp)) {
 					pc = pc + 1;
 					break;
 				}
 			}
-			return 0;
+			return 1;
 		case I_WORD:
 			i = sp > bol && iswordchar(sp[-1]);
 			i ^= iswordchar(sp[0]);
 			if (!i)
-				return 0;
+				return 1;
 			pc = pc + 1;
 			break;
 		case I_NWORD:
 			i = sp > bol && iswordchar(sp[-1]);
 			i ^= iswordchar(sp[0]);
 			if (i)
-				return 0;
+				return 1;
 			pc = pc + 1;
 			break;
 
 		case I_LPAR:
 			out->sub[pc->n].sp = sp;
@@ -1111,11 +1126,11 @@ static int match(Reinst *pc, const char *sp, const char *bol, int flags, Resub *
 		case I_RPAR:
 			out->sub[pc->n].ep = sp;
 			pc = pc + 1;
 			break;
 		default:
-			return 0;
+			return 1;
 		}
 	}
 }
 
 int regexec(Reprog *prog, const char *sp, Resub *sub, int eflags)
@@ -1128,11 +1143,11 @@ int regexec(Reprog *prog, const char *sp, Resub *sub, int eflags)
 
 	sub->nsub = prog->nsub;
 	for (i = 0; i < MAXSUB; ++i)
 		sub->sub[i].sp = sub->sub[i].ep = NULL;
 
-	return !match(prog->start, sp, sp, prog->flags | eflags, sub);
+	return match(prog->start, sp, sp, prog->flags | eflags, sub, 0);
 }
 
 #ifdef TEST
 int main(int argc, char **argv)
 {

Vulnerable code: 	if (!js_regexec(re->prog, text, &m, opts)) {
	if (!js_regexec(re->prog, text, &m, opts)) {
		if (js_regexec(re->prog, a, &m, a > text ? REG_NOTBOL : 0))
	if (!js_regexec(re->prog, text, &m, 0))
	if (js_regexec(re->prog, source, &m, 0)) {
		if (!js_regexec(re->prog, source, &m, REG_NOTBOL))
		if (js_regexec(re->prog, text, &m, 0)) {
		if (js_regexec(re->prog, a, &m, a > text ? REG_NOTBOL : 0))
static int match(Reinst *pc, const char *sp, const char *bol, int flags, Resub *out)
			return 1;
			if (match(pc->x, sp, bol, flags, &scratch)) {
				return 1;
			if (!match(pc->x, sp, bol, flags, out))
				return 0;
			if (match(pc->x, sp, bol, flags, &scratch))
				return 0;
				return 0;
				return 0;
				return 0;
				return 0;
				return 0;
				return 0;
					return 0;
					return 0;
				return 0;
					return 0;
					return 0;
					return 0;
					return 0;
			return 0;
			return 0;
				return 0;
				return 0;
			return 0;
	return !match(prog->start, sp, sp, prog->flags | eflags, sub);
Fixed code: 	int result;
	result = js_regexec(re->prog, text, &m, opts);
	if (result < 0)
		js_error(J, "regexec failed");
	if (result == 0) {
	int result;
	result = js_regexec(re->prog, text, &m, opts);
	if (result < 0)
		js_error(J, "regexec failed");
	if (result == 0) {
static int js_doregexec(js_State *J, Reprog *prog, const char *string, Resub *sub, int eflags)
{
	int result = js_regexec(prog, string, sub, eflags);
	if (result < 0)
		js_error(J, "regexec failed");
	return result;
}

		if (js_doregexec(J, re->prog, a, &m, a > text ? REG_NOTBOL : 0))
	if (!js_doregexec(J, re->prog, text, &m, 0))
	if (js_doregexec(J, re->prog, source, &m, 0)) {
		if (!js_doregexec(J, re->prog, source, &m, REG_NOTBOL))
		if (js_doregexec(J, re->prog, text, &m, 0)) {
		if (js_doregexec(J, re->prog, a, &m, a > text ? REG_NOTBOL : 0))
#define MAXREC 1024
static int match(Reinst *pc, const char *sp, const char *bol, int flags, Resub *out, int depth)
	int result;
	/* stack overflow */
	if (depth > MAXREC)
		return -1;

			return 0;
			result = match(pc->x, sp, bol, flags, &scratch, depth+1);
			if (result == -1)
				return -1;
			if (result == 0) {
				return 0;
			result = match(pc->x, sp, bol, flags, out, depth+1);
			if (result == -1)
				return -1;
			if (result == 1)
				return 1;
			result = match(pc->x, sp, bol, flags, &scratch, depth+1);
			if (result == -1)
				return -1;
			if (result == 0)
				return 1;
				return 1;
				return 1;
				return 1;
				return 1;
				return 1;
				return 1;
					return 1;
					return 1;
				return 1;
					return 1;
					return 1;
					return 1;
					return 1;
			return 1;
			return 1;
				return 1;
				return 1;
			return 1;
	return match(prog->start, sp, sp, prog->flags | eflags, sub, 0);