[PATCH] libsepol/cil: Give an error when constraint expressions exceed max depth

[PATCH] libsepol/cil: Give an error when constraint expressions exceed max depth

[James Carter]

CIL was not correctly determining the depth of constraint expressions
which prevented it from giving an error when the max depth was exceeded.
This allowed invalid policy binaries with constraint expressions exceeding
the max depth to be created.

Correctly calculate the depth of constraint expressions when building
the AST and give an error when the max depth is exceeded.

Reported-by: Jonathan Hettwer <j2468h@gmail.com>
Signed-off-by: James Carter <jwcart2@gmail.com>
---
 libsepol/cil/src/cil_build_ast.c | 19 ++++++++-----------
 1 file changed, 8 insertions(+), 11 deletions(-)

diff --git a/libsepol/cil/src/cil_build_ast.c b/libsepol/cil/src/cil_build_ast.c
index 60ecaaff..29a3d060 100644
--- a/libsepol/cil/src/cil_build_ast.c
+++ b/libsepol/cil/src/cil_build_ast.c
@@ -2738,7 +2738,7 @@ exit:
 	return SEPOL_ERR;
 }
 
-static int __cil_fill_constraint_expr(struct cil_tree_node *current, enum cil_flavor flavor, struct cil_list **expr, int *depth)
+static int __cil_fill_constraint_expr(struct cil_tree_node *current, enum cil_flavor flavor, struct cil_list **expr, int depth)
 {
 	int rc = SEPOL_ERR;
 	enum cil_flavor op;
@@ -2750,8 +2750,9 @@ static int __cil_fill_constraint_expr(struct cil_tree_node *current, enum cil_fl
 		goto exit;
 	}
 
-	if (*depth > CEXPR_MAXDEPTH) {
-		cil_log(CIL_ERR, "Max depth of %d exceeded for constraint expression\n", CEXPR_MAXDEPTH);
+	if (depth >= CEXPR_MAXDEPTH) {
+		/* Error occurs when depth == CEXPR_MAXDEPTH */
+		cil_log(CIL_ERR, "Max depth of %d exceeded for constraint expression\n", CEXPR_MAXDEPTH-1);
 		rc = SEPOL_ERR;
 		goto exit;
 	}
@@ -2769,14 +2770,13 @@ static int __cil_fill_constraint_expr(struct cil_tree_node *current, enum cil_fl
 	case CIL_CONS_DOM:
 	case CIL_CONS_DOMBY:
 	case CIL_CONS_INCOMP:
-		(*depth)++;
 		rc = __cil_fill_constraint_leaf_expr(current, flavor, op, expr);
 		if (rc != SEPOL_OK) {
 			goto exit;
 		}
 		break;
 	case CIL_NOT:
-		rc = __cil_fill_constraint_expr(current->next->cl_head, flavor, &lexpr, depth);
+		rc = __cil_fill_constraint_expr(current->next->cl_head, flavor, &lexpr, depth+1);
 		if (rc != SEPOL_OK) {
 			goto exit;
 		}
@@ -2785,11 +2785,11 @@ static int __cil_fill_constraint_expr(struct cil_tree_node *current, enum cil_fl
 		cil_list_append(*expr, CIL_LIST, lexpr);
 		break;
 	default:
-		rc = __cil_fill_constraint_expr(current->next->cl_head, flavor, &lexpr, depth);
+		rc = __cil_fill_constraint_expr(current->next->cl_head, flavor, &lexpr, depth+1);
 		if (rc != SEPOL_OK) {
 			goto exit;
 		}
-		rc = __cil_fill_constraint_expr(current->next->next->cl_head, flavor, &rexpr, depth);
+		rc = __cil_fill_constraint_expr(current->next->next->cl_head, flavor, &rexpr, depth+1);
 		if (rc != SEPOL_OK) {
 			cil_list_destroy(&lexpr, CIL_TRUE);
 			goto exit;
@@ -2801,8 +2801,6 @@ static int __cil_fill_constraint_expr(struct cil_tree_node *current, enum cil_fl
 		break;
 	}
 
-	(*depth)--;
-
 	return SEPOL_OK;
 exit:
 
@@ -2812,13 +2810,12 @@ exit:
 int cil_gen_constraint_expr(struct cil_tree_node *current, enum cil_flavor flavor, struct cil_list **expr)
 {
 	int rc = SEPOL_ERR;
-	int depth = 0;
 
 	if (current->cl_head == NULL) {
 		goto exit;
 	}
 
-	rc = __cil_fill_constraint_expr(current->cl_head, flavor, expr, &depth);
+	rc = __cil_fill_constraint_expr(current->cl_head, flavor, expr, 0);
 	if (rc != SEPOL_OK) {
 		goto exit;
 	}
-- 
2.25.4

Re: [PATCH] libsepol/cil: Give an error when constraint expressions exceed max depth

[Stephen Smalley]

On Thu, Sep 3, 2020 at 2:19 PM James Carter <jwcart2@gmail.com> wrote:
>
> CIL was not correctly determining the depth of constraint expressions
> which prevented it from giving an error when the max depth was exceeded.
> This allowed invalid policy binaries with constraint expressions exceeding
> the max depth to be created.
>
> Correctly calculate the depth of constraint expressions when building
> the AST and give an error when the max depth is exceeded.

Does a similar bug exist for conditional boolean expression depth checking?

Re: [PATCH] libsepol/cil: Give an error when constraint expressions exceed max depth

[James Carter]

On Thu, Sep 3, 2020 at 3:42 PM Stephen Smalley
<stephen.smalley.work@gmail.com> wrote:
>
> On Thu, Sep 3, 2020 at 2:19 PM James Carter <jwcart2@gmail.com> wrote:
> >
> > CIL was not correctly determining the depth of constraint expressions
> > which prevented it from giving an error when the max depth was exceeded.
> > This allowed invalid policy binaries with constraint expressions exceeding
> > the max depth to be created.
> >
> > Correctly calculate the depth of constraint expressions when building
> > the AST and give an error when the max depth is exceeded.
>
> Does a similar bug exist for conditional boolean expression depth checking?

Yes it does.
Jim

Re: [PATCH] libsepol/cil: Give an error when constraint expressions exceed max depth

[Stephen Smalley]

On Thu, Sep 3, 2020 at 2:19 PM James Carter <jwcart2@gmail.com> wrote:
>
> CIL was not correctly determining the depth of constraint expressions
> which prevented it from giving an error when the max depth was exceeded.
> This allowed invalid policy binaries with constraint expressions exceeding
> the max depth to be created.
>
> Correctly calculate the depth of constraint expressions when building
> the AST and give an error when the max depth is exceeded.
>
> Reported-by: Jonathan Hettwer <j2468h@gmail.com>
> Signed-off-by: James Carter <jwcart2@gmail.com>

The fix for conditional boolean expression depth checking can be a
separate patch.  For this one,

Acked-by: Stephen Smalley <stephen.smalley.work@gmail.com>

Re: [PATCH] libsepol/cil: Give an error when constraint expressions exceed max depth

[Stephen Smalley]

On Fri, Sep 4, 2020 at 8:49 AM Stephen Smalley
<stephen.smalley.work@gmail.com> wrote:
>
> On Thu, Sep 3, 2020 at 2:19 PM James Carter <jwcart2@gmail.com> wrote:
> >
> > CIL was not correctly determining the depth of constraint expressions
> > which prevented it from giving an error when the max depth was exceeded.
> > This allowed invalid policy binaries with constraint expressions exceeding
> > the max depth to be created.
> >
> > Correctly calculate the depth of constraint expressions when building
> > the AST and give an error when the max depth is exceeded.
> >
> > Reported-by: Jonathan Hettwer <j2468h@gmail.com>
> > Signed-off-by: James Carter <jwcart2@gmail.com>
>
> The fix for conditional boolean expression depth checking can be a
> separate patch.  For this one,
>
> Acked-by: Stephen Smalley <stephen.smalley.work@gmail.com>

Actually, this breaks selinux-testsuite. Will have to look into why.
/usr/sbin/semodule -i test_policy/test_policy.pp test_mlsconstrain.cil
test_overlay_defaultrange.cil test_add_levels.cil test_glblub.cil
Max depth of 4 exceeded for constraint expression
Bad expression tree for constraint
Bad constrain declaration at
/var/lib/selinux/targeted/tmp/modules/100/base/cil:919

Re: [PATCH] libsepol/cil: Give an error when constraint expressions exceed max depth

[Stephen Smalley]

On Tue, Sep 8, 2020 at 9:46 AM Stephen Smalley
<stephen.smalley.work@gmail.com> wrote:
>
> On Fri, Sep 4, 2020 at 8:49 AM Stephen Smalley
> <stephen.smalley.work@gmail.com> wrote:
> >
> > On Thu, Sep 3, 2020 at 2:19 PM James Carter <jwcart2@gmail.com> wrote:
> > >
> > > CIL was not correctly determining the depth of constraint expressions
> > > which prevented it from giving an error when the max depth was exceeded.
> > > This allowed invalid policy binaries with constraint expressions exceeding
> > > the max depth to be created.
> > >
> > > Correctly calculate the depth of constraint expressions when building
> > > the AST and give an error when the max depth is exceeded.
> > >
> > > Reported-by: Jonathan Hettwer <j2468h@gmail.com>
> > > Signed-off-by: James Carter <jwcart2@gmail.com>
> >
> > The fix for conditional boolean expression depth checking can be a
> > separate patch.  For this one,
> >
> > Acked-by: Stephen Smalley <stephen.smalley.work@gmail.com>
>
> Actually, this breaks selinux-testsuite. Will have to look into why.
> /usr/sbin/semodule -i test_policy/test_policy.pp test_mlsconstrain.cil
> test_overlay_defaultrange.cil test_add_levels.cil test_glblub.cil
> Max depth of 4 exceeded for constraint expression
> Bad expression tree for constraint
> Bad constrain declaration at
> /var/lib/selinux/targeted/tmp/modules/100/base/cil:919

Here is the failing cil module:
$ cat policy/test_mlsconstrain.cil
(mlsconstrain (peer (recv)) (or (dom l1 l2) (and (neq t1
mcs_constrained_type) (neq t2 mcs_constrained_type))))
(mlsconstrain (packet (recv)) (or (dom l1 l2) (and (neq t1
mcs_constrained_type) (neq t2 mcs_constrained_type))))

Maybe an off-by-one in your depth checking?

Re: [PATCH] libsepol/cil: Give an error when constraint expressions exceed max depth

[James Carter]

On Tue, Sep 8, 2020 at 9:50 AM Stephen Smalley
<stephen.smalley.work@gmail.com> wrote:
>
> On Tue, Sep 8, 2020 at 9:46 AM Stephen Smalley
> <stephen.smalley.work@gmail.com> wrote:
> >
> > On Fri, Sep 4, 2020 at 8:49 AM Stephen Smalley
> > <stephen.smalley.work@gmail.com> wrote:
> > >
> > > On Thu, Sep 3, 2020 at 2:19 PM James Carter <jwcart2@gmail.com> wrote:
> > > >
> > > > CIL was not correctly determining the depth of constraint expressions
> > > > which prevented it from giving an error when the max depth was exceeded.
> > > > This allowed invalid policy binaries with constraint expressions exceeding
> > > > the max depth to be created.
> > > >
> > > > Correctly calculate the depth of constraint expressions when building
> > > > the AST and give an error when the max depth is exceeded.
> > > >
> > > > Reported-by: Jonathan Hettwer <j2468h@gmail.com>
> > > > Signed-off-by: James Carter <jwcart2@gmail.com>
> > >
> > > The fix for conditional boolean expression depth checking can be a
> > > separate patch.  For this one,
> > >
> > > Acked-by: Stephen Smalley <stephen.smalley.work@gmail.com>
> >
> > Actually, this breaks selinux-testsuite. Will have to look into why.
> > /usr/sbin/semodule -i test_policy/test_policy.pp test_mlsconstrain.cil
> > test_overlay_defaultrange.cil test_add_levels.cil test_glblub.cil
> > Max depth of 4 exceeded for constraint expression
> > Bad expression tree for constraint
> > Bad constrain declaration at
> > /var/lib/selinux/targeted/tmp/modules/100/base/cil:919
>
> Here is the failing cil module:
> $ cat policy/test_mlsconstrain.cil
> (mlsconstrain (peer (recv)) (or (dom l1 l2) (and (neq t1
> mcs_constrained_type) (neq t2 mcs_constrained_type))))
> (mlsconstrain (packet (recv)) (or (dom l1 l2) (and (neq t1
> mcs_constrained_type) (neq t2 mcs_constrained_type))))
>
> Maybe an off-by-one in your depth checking?

The following policy, which should be equivalent, works fine.

(class CLASS (PERM))
(class C1a (P1))
(class C1b (P1))
(classorder (CLASS C1a C1b))
(sid SID)
(sidorder (SID))
(user USER)
(role ROLE)
(type TYPE)
(category CAT)
(categoryorder (CAT))
(sensitivity SENS)
(sensitivityorder (SENS))
(sensitivitycategory SENS (CAT))
(allow TYPE self (CLASS (PERM)))
(roletype ROLE TYPE)
(userrole USER ROLE)
(userlevel USER (SENS))
(userrange USER ((SENS)(SENS (CAT))))
(sidcontext SID (USER ROLE TYPE ((SENS)(SENS))))


(type T1a)
(type T1b)
(type T1c)
(type T1d)
(type T1e)
(type T1f)
(type T1g)
(type T1h)
(type T1i)
(type T1j)
(type T1k)
(type T1l)
(typeattribute A1a)
(typeattributeset A1a (T1a T1b T1c T1d T1e T1f T1g T1h T1i T1j T1k T1l))

(mlsconstrain (C1a (P1)) (or (dom l1 l2) (and (neq t1 A1a) (neq t2 A1a))))
(mlsconstrain (C1b (P1)) (or (dom l1 l2) (and (neq t1 A1a) (neq t2 A1a))))

I'll have to see what is going on in the testsuite.
Jim

Re: [PATCH] libsepol/cil: Give an error when constraint expressions exceed max depth

[Stephen Smalley]

On Tue, Sep 8, 2020 at 9:50 AM Stephen Smalley
<stephen.smalley.work@gmail.com> wrote:
>
> On Tue, Sep 8, 2020 at 9:46 AM Stephen Smalley
> <stephen.smalley.work@gmail.com> wrote:
> >
> > On Fri, Sep 4, 2020 at 8:49 AM Stephen Smalley
> > <stephen.smalley.work@gmail.com> wrote:
> > >
> > > On Thu, Sep 3, 2020 at 2:19 PM James Carter <jwcart2@gmail.com> wrote:
> > > >
> > > > CIL was not correctly determining the depth of constraint expressions
> > > > which prevented it from giving an error when the max depth was exceeded.
> > > > This allowed invalid policy binaries with constraint expressions exceeding
> > > > the max depth to be created.
> > > >
> > > > Correctly calculate the depth of constraint expressions when building
> > > > the AST and give an error when the max depth is exceeded.
> > > >
> > > > Reported-by: Jonathan Hettwer <j2468h@gmail.com>
> > > > Signed-off-by: James Carter <jwcart2@gmail.com>
> > >
> > > The fix for conditional boolean expression depth checking can be a
> > > separate patch.  For this one,
> > >
> > > Acked-by: Stephen Smalley <stephen.smalley.work@gmail.com>
> >
> > Actually, this breaks selinux-testsuite. Will have to look into why.
> > /usr/sbin/semodule -i test_policy/test_policy.pp test_mlsconstrain.cil
> > test_overlay_defaultrange.cil test_add_levels.cil test_glblub.cil
> > Max depth of 4 exceeded for constraint expression
> > Bad expression tree for constraint
> > Bad constrain declaration at
> > /var/lib/selinux/targeted/tmp/modules/100/base/cil:919
>
> Here is the failing cil module:
> $ cat policy/test_mlsconstrain.cil
> (mlsconstrain (peer (recv)) (or (dom l1 l2) (and (neq t1
> mcs_constrained_type) (neq t2 mcs_constrained_type))))
> (mlsconstrain (packet (recv)) (or (dom l1 l2) (and (neq t1
> mcs_constrained_type) (neq t2 mcs_constrained_type))))
>
> Maybe an off-by-one in your depth checking?

Actually, the depth computation logic doesn't seem consistent with
checkpolicy's define_constraint().

Re: [PATCH] libsepol/cil: Give an error when constraint expressions exceed max depth

[James Carter]

On Tue, Sep 8, 2020 at 11:27 AM Stephen Smalley
<stephen.smalley.work@gmail.com> wrote:
>
> On Tue, Sep 8, 2020 at 9:50 AM Stephen Smalley
> <stephen.smalley.work@gmail.com> wrote:
> >
> > On Tue, Sep 8, 2020 at 9:46 AM Stephen Smalley
> > <stephen.smalley.work@gmail.com> wrote:
> > >
> > > On Fri, Sep 4, 2020 at 8:49 AM Stephen Smalley
> > > <stephen.smalley.work@gmail.com> wrote:
> > > >
> > > > On Thu, Sep 3, 2020 at 2:19 PM James Carter <jwcart2@gmail.com> wrote:
> > > > >
> > > > > CIL was not correctly determining the depth of constraint expressions
> > > > > which prevented it from giving an error when the max depth was exceeded.
> > > > > This allowed invalid policy binaries with constraint expressions exceeding
> > > > > the max depth to be created.
> > > > >
> > > > > Correctly calculate the depth of constraint expressions when building
> > > > > the AST and give an error when the max depth is exceeded.
> > > > >
> > > > > Reported-by: Jonathan Hettwer <j2468h@gmail.com>
> > > > > Signed-off-by: James Carter <jwcart2@gmail.com>
> > > >
> > > > The fix for conditional boolean expression depth checking can be a
> > > > separate patch.  For this one,
> > > >
> > > > Acked-by: Stephen Smalley <stephen.smalley.work@gmail.com>
> > >
> > > Actually, this breaks selinux-testsuite. Will have to look into why.
> > > /usr/sbin/semodule -i test_policy/test_policy.pp test_mlsconstrain.cil
> > > test_overlay_defaultrange.cil test_add_levels.cil test_glblub.cil
> > > Max depth of 4 exceeded for constraint expression
> > > Bad expression tree for constraint
> > > Bad constrain declaration at
> > > /var/lib/selinux/targeted/tmp/modules/100/base/cil:919
> >
> > Here is the failing cil module:
> > $ cat policy/test_mlsconstrain.cil
> > (mlsconstrain (peer (recv)) (or (dom l1 l2) (and (neq t1
> > mcs_constrained_type) (neq t2 mcs_constrained_type))))
> > (mlsconstrain (packet (recv)) (or (dom l1 l2) (and (neq t1
> > mcs_constrained_type) (neq t2 mcs_constrained_type))))
> >
> > Maybe an off-by-one in your depth checking?
>
> Actually, the depth computation logic doesn't seem consistent with
> checkpolicy's define_constraint().

I don't really understand what checkpolicy is doing. I guess keeping
track of the postfix stack size?

The one difference that would be easy to fix is that checkpolicy ignores "not".

CIL has a max depth = 4, but checkpolicy has a max depth = 0 for these:
(constrain (C5 (P5)) (not (not (not (not (eq t1 T5a))))))
constrain C5 { P5 } not (not (not (not (t1 == T5a))));

Here is one pair of examples that would be hard for me to make CIL
agree with checkpolicy. These are essentially the same constraint:

Both see max depth = 2 for this one
(constrain (C6 (P6)) (or (eq t1 T6g) (and (neq t1 A6a) (neq t2 T6f))))
constrain C6 { P6 } (t1 == T6g or (t1 != A6a and t2 != T6f));

CIL sees max depth = 2 for this one, but checkpolicy has max depth = 1
(constrain (C7 (P7)) (or (and (neq t1 A7a) (neq t2 T7f)) (eq t1 T7g)))
constrain C7 { P7 } ((t1 != A7a and t2 != T7f) or t1 == T7g);

In most other examples that I have created, they had the same max depth.

Both have max depth = 2 for these:
(constrain (C1 (P1)) (or (eq t1 T1a) (and (eq t1 T1b) (eq t1 T1c))))
constrain C1 { P1 } (t1 == T1a or (t1 == T1b and t1 == T1c));

Both have max depth = 4 for these:
(constrain (C2 (P2)) (or (eq t1 T2a) (or (eq t1 T2b) (or (eq t1 T2c)
(and (eq t1 T2d) (eq t1 T2e))))))
constrain C2 { P2 } (t1 == T2a or (t1 == T2b or (t1 == T2c or (t1 ==
T2d and t1 == T2e))));

Both have max depth = 3 for these:
(constrain (C4 (P4)) (or (or (eq t1 T4a) (or (eq t1 T4b) (eq t1 T4c)))
(or (eq t1 T4d) (and (eq t1 T4e) (eq t1 T4f)))))
constrain C4 { P4 } ((t1 == T4a or (t1 == T4b or t1 == T4c)) or (t1 ==
T4d or (t1 == T4e and t1 == T4f)));

Both have max depth = 4 for these:
(constrain (C8 (P8)) (or (or (or (and (neq t1 T8a) (neq t1 T8b)) (and
(neq t1 T8c) (neq t1 T8d))) (or (and (neq t1 T8e) (neq t1 T8f)) (and
(neq t1 T8g) (neq t1 T8h)))) (or (or (and (neq t1 T8i) (neq t1 T8j))
(and (neq t1 T8k) (neq t1 T8l))) (or (and (neq t1 T8m) (neq t1 T8n))
(and (neq t1 T8o) (neq t1 T8p))))))
constrain C8 { P8 } ((((t1 != T8a and t1 != T8b) or (t1 != T8c and t1
!= T8d)) or ((t1 != T8e and t1 != T8f) or (t1 != T8g and t1 != T8h)))
or (((t1 != T8i and t1 != T8j) or (t1 != T8k and t1 != T8l)) or ((t1
!= T8m and t1 != T8n) or (t1 != T8o and t1 != T8p))));

I guess I can convert the expressions to postfix and then follow the
logic of checkpolicy, but that seems to be a lot of work. Instead, I
could add a second check when the binary is being created and the
constraint expression has been turned into postfix already.

Jim

Re: [PATCH] libsepol/cil: Give an error when constraint expressions exceed max depth

[Stephen Smalley]

On Tue, Sep 8, 2020 at 4:32 PM James Carter <jwcart2@gmail.com> wrote:
>
> On Tue, Sep 8, 2020 at 11:27 AM Stephen Smalley
> <stephen.smalley.work@gmail.com> wrote:
> >
> > On Tue, Sep 8, 2020 at 9:50 AM Stephen Smalley
> > <stephen.smalley.work@gmail.com> wrote:
> > >
> > > On Tue, Sep 8, 2020 at 9:46 AM Stephen Smalley
> > > <stephen.smalley.work@gmail.com> wrote:
> > > >
> > > > On Fri, Sep 4, 2020 at 8:49 AM Stephen Smalley
> > > > <stephen.smalley.work@gmail.com> wrote:
> > > > >
> > > > > On Thu, Sep 3, 2020 at 2:19 PM James Carter <jwcart2@gmail.com> wrote:
> > > > > >
> > > > > > CIL was not correctly determining the depth of constraint expressions
> > > > > > which prevented it from giving an error when the max depth was exceeded.
> > > > > > This allowed invalid policy binaries with constraint expressions exceeding
> > > > > > the max depth to be created.
> > > > > >
> > > > > > Correctly calculate the depth of constraint expressions when building
> > > > > > the AST and give an error when the max depth is exceeded.
> > > > > >
> > > > > > Reported-by: Jonathan Hettwer <j2468h@gmail.com>
> > > > > > Signed-off-by: James Carter <jwcart2@gmail.com>
> > > > >
> > > > > The fix for conditional boolean expression depth checking can be a
> > > > > separate patch.  For this one,
> > > > >
> > > > > Acked-by: Stephen Smalley <stephen.smalley.work@gmail.com>
> > > >
> > > > Actually, this breaks selinux-testsuite. Will have to look into why.
> > > > /usr/sbin/semodule -i test_policy/test_policy.pp test_mlsconstrain.cil
> > > > test_overlay_defaultrange.cil test_add_levels.cil test_glblub.cil
> > > > Max depth of 4 exceeded for constraint expression
> > > > Bad expression tree for constraint
> > > > Bad constrain declaration at
> > > > /var/lib/selinux/targeted/tmp/modules/100/base/cil:919
> > >
> > > Here is the failing cil module:
> > > $ cat policy/test_mlsconstrain.cil
> > > (mlsconstrain (peer (recv)) (or (dom l1 l2) (and (neq t1
> > > mcs_constrained_type) (neq t2 mcs_constrained_type))))
> > > (mlsconstrain (packet (recv)) (or (dom l1 l2) (and (neq t1
> > > mcs_constrained_type) (neq t2 mcs_constrained_type))))
> > >
> > > Maybe an off-by-one in your depth checking?
> >
> > Actually, the depth computation logic doesn't seem consistent with
> > checkpolicy's define_constraint().
>
> I don't really understand what checkpolicy is doing. I guess keeping
> track of the postfix stack size?

Yes, the whole point is to prevent overflowing the fixed-size stack
used by the kernel (and by libsepol) in evaluating constraints.
Originally I think it was to bound recursion in the function since the
original implementation was recursive and only later converted.  The
important thing is to match the kernel.

> The one difference that would be easy to fix is that checkpolicy ignores "not".
>
> CIL has a max depth = 4, but checkpolicy has a max depth = 0 for these:
> (constrain (C5 (P5)) (not (not (not (not (eq t1 T5a))))))
> constrain C5 { P5 } not (not (not (not (t1 == T5a))));
>
> Here is one pair of examples that would be hard for me to make CIL
> agree with checkpolicy. These are essentially the same constraint:
>
> Both see max depth = 2 for this one
> (constrain (C6 (P6)) (or (eq t1 T6g) (and (neq t1 A6a) (neq t2 T6f))))
> constrain C6 { P6 } (t1 == T6g or (t1 != A6a and t2 != T6f));
>
> CIL sees max depth = 2 for this one, but checkpolicy has max depth = 1
> (constrain (C7 (P7)) (or (and (neq t1 A7a) (neq t2 T7f)) (eq t1 T7g)))
> constrain C7 { P7 } ((t1 != A7a and t2 != T7f) or t1 == T7g);
>
> In most other examples that I have created, they had the same max depth.
>
> Both have max depth = 2 for these:
> (constrain (C1 (P1)) (or (eq t1 T1a) (and (eq t1 T1b) (eq t1 T1c))))
> constrain C1 { P1 } (t1 == T1a or (t1 == T1b and t1 == T1c));
>
> Both have max depth = 4 for these:
> (constrain (C2 (P2)) (or (eq t1 T2a) (or (eq t1 T2b) (or (eq t1 T2c)
> (and (eq t1 T2d) (eq t1 T2e))))))
> constrain C2 { P2 } (t1 == T2a or (t1 == T2b or (t1 == T2c or (t1 ==
> T2d and t1 == T2e))));
>
> Both have max depth = 3 for these:
> (constrain (C4 (P4)) (or (or (eq t1 T4a) (or (eq t1 T4b) (eq t1 T4c)))
> (or (eq t1 T4d) (and (eq t1 T4e) (eq t1 T4f)))))
> constrain C4 { P4 } ((t1 == T4a or (t1 == T4b or t1 == T4c)) or (t1 ==
> T4d or (t1 == T4e and t1 == T4f)));
>
> Both have max depth = 4 for these:
> (constrain (C8 (P8)) (or (or (or (and (neq t1 T8a) (neq t1 T8b)) (and
> (neq t1 T8c) (neq t1 T8d))) (or (and (neq t1 T8e) (neq t1 T8f)) (and
> (neq t1 T8g) (neq t1 T8h)))) (or (or (and (neq t1 T8i) (neq t1 T8j))
> (and (neq t1 T8k) (neq t1 T8l))) (or (and (neq t1 T8m) (neq t1 T8n))
> (and (neq t1 T8o) (neq t1 T8p))))))
> constrain C8 { P8 } ((((t1 != T8a and t1 != T8b) or (t1 != T8c and t1
> != T8d)) or ((t1 != T8e and t1 != T8f) or (t1 != T8g and t1 != T8h)))
> or (((t1 != T8i and t1 != T8j) or (t1 != T8k and t1 != T8l)) or ((t1
> != T8m and t1 != T8n) or (t1 != T8o and t1 != T8p))));
>
> I guess I can convert the expressions to postfix and then follow the
> logic of checkpolicy, but that seems to be a lot of work. Instead, I
> could add a second check when the binary is being created and the
> constraint expression has been turned into postfix already.

Re: [PATCH] libsepol/cil: Give an error when constraint expressions exceed max depth

[Dominick Grift]

Stephen Smalley <stephen.smalley.work@gmail.com> writes:

> On Tue, Sep 8, 2020 at 9:46 AM Stephen Smalley
> <stephen.smalley.work@gmail.com> wrote:
>>
>> On Fri, Sep 4, 2020 at 8:49 AM Stephen Smalley
>> <stephen.smalley.work@gmail.com> wrote:
>> >
>> > On Thu, Sep 3, 2020 at 2:19 PM James Carter <jwcart2@gmail.com> wrote:
>> > >
>> > > CIL was not correctly determining the depth of constraint expressions
>> > > which prevented it from giving an error when the max depth was exceeded.
>> > > This allowed invalid policy binaries with constraint expressions exceeding
>> > > the max depth to be created.
>> > >
>> > > Correctly calculate the depth of constraint expressions when building
>> > > the AST and give an error when the max depth is exceeded.
>> > >
>> > > Reported-by: Jonathan Hettwer <j2468h@gmail.com>
>> > > Signed-off-by: James Carter <jwcart2@gmail.com>
>> >
>> > The fix for conditional boolean expression depth checking can be a
>> > separate patch.  For this one,
>> >
>> > Acked-by: Stephen Smalley <stephen.smalley.work@gmail.com>
>>
>> Actually, this breaks selinux-testsuite. Will have to look into why.
>> /usr/sbin/semodule -i test_policy/test_policy.pp test_mlsconstrain.cil
>> test_overlay_defaultrange.cil test_add_levels.cil test_glblub.cil
>> Max depth of 4 exceeded for constraint expression
>> Bad expression tree for constraint
>> Bad constrain declaration at
>> /var/lib/selinux/targeted/tmp/modules/100/base/cil:919
>
> Here is the failing cil module:
> $ cat policy/test_mlsconstrain.cil
> (mlsconstrain (peer (recv)) (or (dom l1 l2) (and (neq t1
> mcs_constrained_type) (neq t2 mcs_constrained_type))))
> (mlsconstrain (packet (recv)) (or (dom l1 l2) (and (neq t1
> mcs_constrained_type) (neq t2 mcs_constrained_type))))
>
> Maybe an off-by-one in your depth checking?

That looks scary to me. Those constrains are simple compared to some of
the ones I currently successfully use and rely upon:

https://git.defensec.nl/?p=dssp3.git;a=blob;f=policy/constrain/rbacsep.cil;h=935c722167bcf214f286eb339e0793cd94d3edd0;hb=HEAD

-- 
gpg --locate-keys dominick.grift@defensec.nl
Key fingerprint = FCD2 3660 5D6B 9D27 7FC6  E0FF DA7E 521F 10F6 4098
https://sks-keyservers.net/pks/lookup?op=get&search=0xDA7E521F10F64098
Dominick Grift

Re: [PATCH] libsepol/cil: Give an error when constraint expressions exceed max depth

[bauen1]

So the limit for nested conditionals CEXPR_MAXDEPTH is 5.
Is there any specific reason for this number, e.g. limitation of the binary policy format or performance ?

The RBACSEP constraints in my policy, specifically the ones for fifo_file are quite complex and as a result of rewriting them readability I hit the original bug. [1]
While I should try to simplify the constraint I also wouldn't be surprised if I hit this limit in some form again.

[1]:  https://gitlab.com/bauen1/bauen1-policy/-/blob/dev2/policy/system/constraints/constraints_rbacsep.cil#L189-233

-- 
bauen1
https://dn42.bauen1.xyz/