diff --git a/libsepol/src/policydb_validate.c b/libsepol/src/policydb_validate.c
index 735c7a33..86d40686 100644
--- a/libsepol/src/policydb_validate.c
+++ b/libsepol/src/policydb_validate.c
@@ -223,90 +223,174 @@ bad:
 	return -1;
 }
 
-static int validate_constraint_nodes(sepol_handle_t *handle, unsigned int nperms, constraint_node_t *cons, validate_t flavors[])
+/*
+ * Follow evaluation of expressions to find invalid ones.
+ * Keep in sync with kernel source security/selinux/ss/services.c::constraint_expr_eval()
+ */
+static int validate_expression(sepol_handle_t *handle, constraint_expr_t *e, validate_t flavors[])
 {
-	constraint_expr_t *cexp;
-
-	for (; cons; cons = cons->next) {
-		if (nperms > 0 && cons->permissions == 0)
-			goto bad;
-		if (nperms > 0 && nperms != PERM_SYMTAB_SIZE && cons->permissions >= (UINT32_C(1) << nperms))
-			goto bad;
+	int sp = -1;
 
-		for (cexp = cons->expr; cexp; cexp = cexp->next) {
-			if (cexp->attr & CEXPR_USER) {
-				if (validate_ebitmap(&cexp->names, &flavors[SYM_USERS]))
-					goto bad;
-				if (validate_empty_type_set(cexp->type_names))
-					goto bad;
-			} else if (cexp->attr & CEXPR_ROLE) {
-				if (validate_ebitmap(&cexp->names, &flavors[SYM_ROLES]))
-					goto bad;
-				if (validate_empty_type_set(cexp->type_names))
-					goto bad;
-			} else if (cexp->attr & CEXPR_TYPE) {
-				if (validate_ebitmap(&cexp->names, &flavors[SYM_TYPES]))
-					goto bad;
-				if (validate_type_set(cexp->type_names, &flavors[SYM_TYPES]))
-					goto bad;
-			} else {
-				if (!ebitmap_is_empty(&cexp->names))
-					goto bad;
-				if (validate_empty_type_set(cexp->type_names))
-					goto bad;
-			}
+	for (; e; e = e->next) {
+		/* validate symbols (implied in kernel source) */
+		if (e->attr & CEXPR_USER) {
+			if (validate_ebitmap(&e->names, &flavors[SYM_USERS]))
+				goto bad;
+			if (validate_empty_type_set(e->type_names))
+				goto bad;
+		} else if (e->attr & CEXPR_ROLE) {
+			if (validate_ebitmap(&e->names, &flavors[SYM_ROLES]))
+				goto bad;
+			if (validate_empty_type_set(e->type_names))
+				goto bad;
+		} else if (e->attr & CEXPR_TYPE) {
+			if (validate_ebitmap(&e->names, &flavors[SYM_TYPES]))
+				goto bad;
+			if (validate_type_set(e->type_names, &flavors[SYM_TYPES]))
+				goto bad;
+		} else {
+			if (!ebitmap_is_empty(&e->names))
+				goto bad;
+			if (validate_empty_type_set(e->type_names))
+				goto bad;
+		}
 
-			if (cexp->expr_type == CEXPR_ATTR || cexp->expr_type == CEXPR_NAMES) {
-				switch (cexp->op) {
-				case CEXPR_EQ:
-				case CEXPR_NEQ:
+		switch (e->expr_type) {
+		case CEXPR_NOT:
+			if(sp < 0)
+				goto bad;
+			break;
+		case CEXPR_AND:
+			if(sp < 0)
+				goto bad;
+			sp--;
+			break;
+		case CEXPR_OR:
+			if(sp < 0)
+				goto bad;
+			sp--;
+			break;
+		case CEXPR_ATTR:
+			if (sp == (CEXPR_MAXDEPTH - 1))
+				return 0;
+			switch (e->attr) {
+			case CEXPR_USER:
+				break;
+			case CEXPR_TYPE:
+				break;
+			case CEXPR_ROLE:
+				switch (e->op) {
 				case CEXPR_DOM:
+					++sp;
+					continue;
 				case CEXPR_DOMBY:
+					++sp;
+					continue;
 				case CEXPR_INCOMP:
-					break;
+					++sp;
+					continue;
 				default:
-					goto bad;
-				}
-
-				switch (cexp->attr) {
-				case CEXPR_USER:
-				case CEXPR_USER | CEXPR_TARGET:
-				case CEXPR_USER | CEXPR_XTARGET:
-				case CEXPR_ROLE:
-				case CEXPR_ROLE | CEXPR_TARGET:
-				case CEXPR_ROLE | CEXPR_XTARGET:
-				case CEXPR_TYPE:
-				case CEXPR_TYPE | CEXPR_TARGET:
-				case CEXPR_TYPE | CEXPR_XTARGET:
-				case CEXPR_L1L2:
-				case CEXPR_L1H2:
-				case CEXPR_H1L2:
-				case CEXPR_H1H2:
-				case CEXPR_L1H1:
-				case CEXPR_L2H2:
 					break;
-				default:
-					goto bad;
 				}
-			} else {
-				switch (cexp->expr_type) {
-				case CEXPR_NOT:
-				case CEXPR_AND:
-				case CEXPR_OR:
-					break;
+				break;
+			case CEXPR_L1L2:
+				goto mls_ops;
+			case CEXPR_L1H2:
+				goto mls_ops;
+			case CEXPR_H1L2:
+				goto mls_ops;
+			case CEXPR_H1H2:
+				goto mls_ops;
+			case CEXPR_L1H1:
+				goto mls_ops;
+			case CEXPR_L2H2:
+				goto mls_ops;
+mls_ops:
+				switch (e->op) {
+				case CEXPR_EQ:
+					++sp;
+					continue;
+				case CEXPR_NEQ:
+					++sp;
+					continue;
+				case CEXPR_DOM:
+					++sp;
+					continue;
+				case CEXPR_DOMBY:
+					++sp;
+					continue;
+				case CEXPR_INCOMP:
+					++sp;
+					continue;
 				default:
 					goto bad;
 				}
+				break;
+			default:
+				goto bad;
+			}
 
-				if (cexp->op != 0)
-					goto bad;
+			switch (e->op) {
+			case CEXPR_EQ:
+				++sp;
+				break;
+			case CEXPR_NEQ:
+				++sp;
+				break;
+			default:
+				goto bad;
+			}
+			break;
+		case CEXPR_NAMES:
+			if (sp == (CEXPR_MAXDEPTH-1))
+				return 0;
+			if (e->attr & CEXPR_USER)
+				;
+			else if (e->attr & CEXPR_ROLE)
+				;
+			else if (e->attr & CEXPR_TYPE)
+				;
+			else
+				goto bad;
 
-				if (cexp->attr != 0)
-					goto bad;
+			switch (e->op) {
+			case CEXPR_EQ:
+				++sp;
+				break;
+			case CEXPR_NEQ:
+				++sp;
+				break;
+			default:
+				goto bad;
 			}
+			break;
+		default:
+			goto bad;
 		}
 	}
 
+	if (sp != 0)
+		goto bad;
+
+	return 0;
+
+bad:
+	ERR(handle, "Invalid expression");
+	return -1;
+}
+
+static int validate_constraint_nodes(sepol_handle_t *handle, unsigned int nperms, constraint_node_t *cons, validate_t flavors[])
+{
+	for (; cons; cons = cons->next) {
+		if (nperms > 0 && cons->permissions == 0)
+			goto bad;
+		if (nperms > 0 && nperms != PERM_SYMTAB_SIZE && cons->permissions >= (UINT32_C(1) << nperms))
+			goto bad;
+
+		if (validate_expression(handle, cons->expr, flavors))
+			goto bad;
+	}
+
 	return 0;
 
 bad:
