[PATCH 0/5] Another round of secilc-fuzzer problems fixed

[PATCH 0/5] Another round of secilc-fuzzer problems fixed

[James Carter]

Patch 1 fixes the check for self-referential loops that didn't work in all cases
Patches 2 and 3 fix a couple of bugs
Patches 4 and 5 make it harder to create small policies that expand into large
policies that consume all of a system's memory.

James Carter (5):
  libsepol/cil: Properly check for loops in sets
  libsepol/cil: Fix syntax checking of defaultrange rule
  libsepol/cil: Check for empty list when marking neverallow attributes
  libsepol/cil: Reduce the initial symtab sizes for blocks
  libsepol/cil: Improve degenerate inheritance check

 libsepol/cil/src/cil.c             |   2 +-
 libsepol/cil/src/cil_build_ast.c   |   2 +-
 libsepol/cil/src/cil_internal.h    |   5 +-
 libsepol/cil/src/cil_post.c        |   4 +
 libsepol/cil/src/cil_resolve_ast.c | 229 +++++++++++++++++++----------
 libsepol/cil/src/cil_verify.c      |  48 ++++--
 6 files changed, 191 insertions(+), 99 deletions(-)

-- 
2.26.3

[PATCH 1/5] libsepol/cil: Properly check for loops in sets

[James Carter]

Commit 61fbdce666f24c4a118b249ece6b014d54b65074 (ibsepol/cil: Check
for self-referential loops in sets) added checks for self-referential
loops in user, role, type, and category sets. Unfortunately, this
check ends up in an infinite loop if the set with the self-referential
loop is used in a different set that is checked before the bad set.

The problem with the old check is that only the initial datum is used
for the check. Instead, use a stack to track all of the set datums
that are currently involved as the check is made. A self-referential
loop occurs if a duplicate datum is found for any of the datums in the
stack.

Signed-off-by: James Carter <jwcart2@gmail.com>
---
 libsepol/cil/src/cil_verify.c | 48 +++++++++++++++++++++++------------
 1 file changed, 32 insertions(+), 16 deletions(-)

diff --git a/libsepol/cil/src/cil_verify.c b/libsepol/cil/src/cil_verify.c
index 8e15a0e6..59397f70 100644
--- a/libsepol/cil/src/cil_verify.c
+++ b/libsepol/cil/src/cil_verify.c
@@ -44,6 +44,7 @@
 #include "cil_tree.h"
 #include "cil_list.h"
 #include "cil_find.h"
+#include "cil_stack.h"
 
 #include "cil_verify.h"
 
@@ -430,9 +431,9 @@ int cil_verify_decl_does_not_shadow_macro_parameter(struct cil_macro *macro, str
 	return SEPOL_OK;
 }
 
-static int cil_verify_no_self_reference(enum cil_flavor flavor, struct cil_symtab_datum *datum, struct cil_symtab_datum *orig);
+static int cil_verify_no_self_reference(enum cil_flavor flavor, struct cil_symtab_datum *datum, struct cil_stack *stack);
 
-static int __verify_no_self_reference_in_expr(struct cil_list *expr, struct cil_symtab_datum *orig)
+static int __verify_no_self_reference_in_expr(struct cil_list *expr, struct cil_stack *stack)
 {
 	struct cil_list_item *item;
 	int rc = SEPOL_OK;
@@ -444,9 +445,9 @@ static int __verify_no_self_reference_in_expr(struct cil_list *expr, struct cil_
 	cil_list_for_each(item, expr) {
 		if (item->flavor == CIL_DATUM) {
 			struct cil_symtab_datum* datum = item->data;
-			rc = cil_verify_no_self_reference(FLAVOR(datum), datum, orig);
+			rc = cil_verify_no_self_reference(FLAVOR(datum), datum, stack);
 		} else if (item->flavor == CIL_LIST) {
-			rc = __verify_no_self_reference_in_expr(item->data, orig);
+			rc = __verify_no_self_reference_in_expr(item->data, stack);
 		}
 		if (rc != SEPOL_OK) {
 			return SEPOL_ERR;
@@ -456,36 +457,47 @@ static int __verify_no_self_reference_in_expr(struct cil_list *expr, struct cil_
 	return SEPOL_OK;
 }
 
-static int cil_verify_no_self_reference(enum cil_flavor flavor, struct cil_symtab_datum *datum, struct cil_symtab_datum *orig)
+static int cil_verify_no_self_reference(enum cil_flavor flavor, struct cil_symtab_datum *datum, struct cil_stack *stack)
 {
+	struct cil_stack_item *item;
+	int i = 0;
 	int rc = SEPOL_OK;
 
-	if (datum == orig) {
-		cil_tree_log(NODE(orig), CIL_ERR, "Self-reference found for %s", orig->name);
-		return SEPOL_ERR;
-	} else if (orig == NULL) {
-		orig = datum;
+	cil_stack_for_each(stack, i, item) {
+		struct cil_symtab_datum *prev = item->data;
+		if (datum == prev) {
+			cil_tree_log(NODE(datum), CIL_ERR, "Self-reference found for %s", datum->name);
+			return SEPOL_ERR;
+		}
 	}
 
 	switch (flavor) {
 	case CIL_USERATTRIBUTE: {
 		struct cil_userattribute *attr = (struct cil_userattribute *)datum;
-		rc = __verify_no_self_reference_in_expr(attr->expr_list, orig);
+		cil_stack_push(stack, CIL_DATUM, datum);
+		rc = __verify_no_self_reference_in_expr(attr->expr_list, stack);
+		cil_stack_pop(stack);
 		break;
 	}
 	case CIL_ROLEATTRIBUTE: {
 		struct cil_roleattribute *attr = (struct cil_roleattribute *)datum;
-		rc = __verify_no_self_reference_in_expr(attr->expr_list, orig);
+		cil_stack_push(stack, CIL_DATUM, datum);
+		rc = __verify_no_self_reference_in_expr(attr->expr_list, stack);
+		cil_stack_pop(stack);
 		break;
 	}
 	case CIL_TYPEATTRIBUTE: {
 		struct cil_typeattribute *attr = (struct cil_typeattribute *)datum;
-		rc = __verify_no_self_reference_in_expr(attr->expr_list, orig);
+		cil_stack_push(stack, CIL_DATUM, datum);
+		rc = __verify_no_self_reference_in_expr(attr->expr_list, stack);
+		cil_stack_pop(stack);
 		break;
 	}
 	case CIL_CATSET: {
 		struct cil_catset *set = (struct cil_catset *)datum;
-		rc = __verify_no_self_reference_in_expr(set->cats->datum_expr, orig);
+		cil_stack_push(stack, CIL_DATUM, datum);
+		rc = __verify_no_self_reference_in_expr(set->cats->datum_expr, stack);
+		cil_stack_pop(stack);
 		break;
 	}
 	default:
@@ -1826,9 +1838,13 @@ int __cil_pre_verify_helper(struct cil_tree_node *node, uint32_t *finished, __at
 	case CIL_USERATTRIBUTE:
 	case CIL_ROLEATTRIBUTE:
 	case CIL_TYPEATTRIBUTE:
-	case CIL_CATSET:
-		rc = cil_verify_no_self_reference(node->flavor, node->data, NULL);
+	case CIL_CATSET: {
+		struct cil_stack *stack;
+		cil_stack_init(&stack);
+		rc = cil_verify_no_self_reference(node->flavor, node->data, stack);
+		cil_stack_destroy(&stack);
 		break;
+	}
 	default:
 		rc = SEPOL_OK;
 		break;
-- 
2.26.3

Re: [PATCH 1/5] libsepol/cil: Properly check for loops in sets

[Nicolas Iooss]

On Mon, Jun 14, 2021 at 5:05 PM James Carter <jwcart2@gmail.com> wrote:
>
> Commit 61fbdce666f24c4a118b249ece6b014d54b65074 (ibsepol/cil: Check
> for self-referential loops in sets) added checks for self-referential
> loops in user, role, type, and category sets. Unfortunately, this
> check ends up in an infinite loop if the set with the self-referential
> loop is used in a different set that is checked before the bad set.
>
> The problem with the old check is that only the initial datum is used
> for the check. Instead, use a stack to track all of the set datums
> that are currently involved as the check is made. A self-referential
> loop occurs if a duplicate datum is found for any of the datums in the
> stack.
>
> Signed-off-by: James Carter <jwcart2@gmail.com>

For this patch:

Acked-by: Nicolas Iooss <nicolas.iooss@m4x.org>

Thanks!

> ---
>  libsepol/cil/src/cil_verify.c | 48 +++++++++++++++++++++++------------
>  1 file changed, 32 insertions(+), 16 deletions(-)
>
> diff --git a/libsepol/cil/src/cil_verify.c b/libsepol/cil/src/cil_verify.c
> index 8e15a0e6..59397f70 100644
> --- a/libsepol/cil/src/cil_verify.c
> +++ b/libsepol/cil/src/cil_verify.c
> @@ -44,6 +44,7 @@
>  #include "cil_tree.h"
>  #include "cil_list.h"
>  #include "cil_find.h"
> +#include "cil_stack.h"
>
>  #include "cil_verify.h"
>
> @@ -430,9 +431,9 @@ int cil_verify_decl_does_not_shadow_macro_parameter(struct cil_macro *macro, str
>         return SEPOL_OK;
>  }
>
> -static int cil_verify_no_self_reference(enum cil_flavor flavor, struct cil_symtab_datum *datum, struct cil_symtab_datum *orig);
> +static int cil_verify_no_self_reference(enum cil_flavor flavor, struct cil_symtab_datum *datum, struct cil_stack *stack);
>
> -static int __verify_no_self_reference_in_expr(struct cil_list *expr, struct cil_symtab_datum *orig)
> +static int __verify_no_self_reference_in_expr(struct cil_list *expr, struct cil_stack *stack)
>  {
>         struct cil_list_item *item;
>         int rc = SEPOL_OK;
> @@ -444,9 +445,9 @@ static int __verify_no_self_reference_in_expr(struct cil_list *expr, struct cil_
>         cil_list_for_each(item, expr) {
>                 if (item->flavor == CIL_DATUM) {
>                         struct cil_symtab_datum* datum = item->data;
> -                       rc = cil_verify_no_self_reference(FLAVOR(datum), datum, orig);
> +                       rc = cil_verify_no_self_reference(FLAVOR(datum), datum, stack);
>                 } else if (item->flavor == CIL_LIST) {
> -                       rc = __verify_no_self_reference_in_expr(item->data, orig);
> +                       rc = __verify_no_self_reference_in_expr(item->data, stack);
>                 }
>                 if (rc != SEPOL_OK) {
>                         return SEPOL_ERR;
> @@ -456,36 +457,47 @@ static int __verify_no_self_reference_in_expr(struct cil_list *expr, struct cil_
>         return SEPOL_OK;
>  }
>
> -static int cil_verify_no_self_reference(enum cil_flavor flavor, struct cil_symtab_datum *datum, struct cil_symtab_datum *orig)
> +static int cil_verify_no_self_reference(enum cil_flavor flavor, struct cil_symtab_datum *datum, struct cil_stack *stack)
>  {
> +       struct cil_stack_item *item;
> +       int i = 0;
>         int rc = SEPOL_OK;
>
> -       if (datum == orig) {
> -               cil_tree_log(NODE(orig), CIL_ERR, "Self-reference found for %s", orig->name);
> -               return SEPOL_ERR;
> -       } else if (orig == NULL) {
> -               orig = datum;
> +       cil_stack_for_each(stack, i, item) {
> +               struct cil_symtab_datum *prev = item->data;
> +               if (datum == prev) {
> +                       cil_tree_log(NODE(datum), CIL_ERR, "Self-reference found for %s", datum->name);
> +                       return SEPOL_ERR;
> +               }
>         }
>
>         switch (flavor) {
>         case CIL_USERATTRIBUTE: {
>                 struct cil_userattribute *attr = (struct cil_userattribute *)datum;
> -               rc = __verify_no_self_reference_in_expr(attr->expr_list, orig);
> +               cil_stack_push(stack, CIL_DATUM, datum);
> +               rc = __verify_no_self_reference_in_expr(attr->expr_list, stack);
> +               cil_stack_pop(stack);
>                 break;
>         }
>         case CIL_ROLEATTRIBUTE: {
>                 struct cil_roleattribute *attr = (struct cil_roleattribute *)datum;
> -               rc = __verify_no_self_reference_in_expr(attr->expr_list, orig);
> +               cil_stack_push(stack, CIL_DATUM, datum);
> +               rc = __verify_no_self_reference_in_expr(attr->expr_list, stack);
> +               cil_stack_pop(stack);
>                 break;
>         }
>         case CIL_TYPEATTRIBUTE: {
>                 struct cil_typeattribute *attr = (struct cil_typeattribute *)datum;
> -               rc = __verify_no_self_reference_in_expr(attr->expr_list, orig);
> +               cil_stack_push(stack, CIL_DATUM, datum);
> +               rc = __verify_no_self_reference_in_expr(attr->expr_list, stack);
> +               cil_stack_pop(stack);
>                 break;
>         }
>         case CIL_CATSET: {
>                 struct cil_catset *set = (struct cil_catset *)datum;
> -               rc = __verify_no_self_reference_in_expr(set->cats->datum_expr, orig);
> +               cil_stack_push(stack, CIL_DATUM, datum);
> +               rc = __verify_no_self_reference_in_expr(set->cats->datum_expr, stack);
> +               cil_stack_pop(stack);
>                 break;
>         }
>         default:
> @@ -1826,9 +1838,13 @@ int __cil_pre_verify_helper(struct cil_tree_node *node, uint32_t *finished, __at
>         case CIL_USERATTRIBUTE:
>         case CIL_ROLEATTRIBUTE:
>         case CIL_TYPEATTRIBUTE:
> -       case CIL_CATSET:
> -               rc = cil_verify_no_self_reference(node->flavor, node->data, NULL);
> +       case CIL_CATSET: {
> +               struct cil_stack *stack;
> +               cil_stack_init(&stack);
> +               rc = cil_verify_no_self_reference(node->flavor, node->data, stack);
> +               cil_stack_destroy(&stack);
>                 break;
> +       }
>         default:
>                 rc = SEPOL_OK;
>                 break;
> --
> 2.26.3
>

[PATCH 2/5] libsepol/cil: Fix syntax checking of defaultrange rule

[James Carter]

The syntax array that cil_gen_defaultrange() called __cil_verify_syntax()
with was wrong. It had the range (which should be low, high, or low-high)
as optional when it is not.

Use the correct syntax array to check the syntax of the defaultrange rule.

Signed-off-by: James Carter <jwcart2@gmail.com>
---
 libsepol/cil/src/cil_build_ast.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/libsepol/cil/src/cil_build_ast.c b/libsepol/cil/src/cil_build_ast.c
index 71f14e20..a5f617d8 100644
--- a/libsepol/cil/src/cil_build_ast.c
+++ b/libsepol/cil/src/cil_build_ast.c
@@ -5862,7 +5862,7 @@ int cil_gen_defaultrange(struct cil_tree_node *parse_current, struct cil_tree_no
 		CIL_SYN_STRING,
 		CIL_SYN_STRING | CIL_SYN_LIST,
 		CIL_SYN_STRING,
-		CIL_SYN_STRING | CIL_SYN_END,
+		CIL_SYN_STRING,
 		CIL_SYN_END
 	};
 	int syntax_len = sizeof(syntax)/sizeof(*syntax);
-- 
2.26.3

Re: [PATCH 2/5] libsepol/cil: Fix syntax checking of defaultrange rule

[Nicolas Iooss]

On Mon, Jun 14, 2021 at 5:05 PM James Carter <jwcart2@gmail.com> wrote:
>
> The syntax array that cil_gen_defaultrange() called __cil_verify_syntax()
> with was wrong. It had the range (which should be low, high, or low-high)
> as optional when it is not.
>
> Use the correct syntax array to check the syntax of the defaultrange rule.
>
> Signed-off-by: James Carter <jwcart2@gmail.com>
> ---
>  libsepol/cil/src/cil_build_ast.c | 2 +-
>  1 file changed, 1 insertion(+), 1 deletion(-)
>
> diff --git a/libsepol/cil/src/cil_build_ast.c b/libsepol/cil/src/cil_build_ast.c
> index 71f14e20..a5f617d8 100644
> --- a/libsepol/cil/src/cil_build_ast.c
> +++ b/libsepol/cil/src/cil_build_ast.c
> @@ -5862,7 +5862,7 @@ int cil_gen_defaultrange(struct cil_tree_node *parse_current, struct cil_tree_no
>                 CIL_SYN_STRING,
>                 CIL_SYN_STRING | CIL_SYN_LIST,
>                 CIL_SYN_STRING,
> -               CIL_SYN_STRING | CIL_SYN_END,
> +               CIL_SYN_STRING,
>                 CIL_SYN_END
>         };
>         int syntax_len = sizeof(syntax)/sizeof(*syntax);
> --
> 2.26.3

Hello,
This patch will break selinux-testsuite with:

/usr/sbin/semodule -i test_policy/test_policy.pp test_mlsconstrain.cil
test_overlay_defaultrange.cil test_userfaultfd.cil test_add_levels.cil
test_glblub.cil
Invalid syntax
Bad defaultrange declaration at
/var/lib/selinux/targeted/tmp/modules/400/test_glblub/cil:1
Failed to build AST
/usr/sbin/semodule: Failed!

... because it currently uses, in
https://github.com/SELinuxProject/selinux-testsuite/blob/0b78a9d433e8c4f956d18dc0db901f0a1a58c003/policy/test_glblub.cil
:

    (defaultrange db_table glblub)

If I understand the commit message correctly, a range (low, high or
low-high) has to be added to this statement. I am not familiar with
glbulb and do not know how the testsuite should be modified. Could the
policy used by the testsuite be fixed before applying this patch?

Cheers,
Nicolas

(PS : I was quite busy last month but now I have some time again to
catch up with SELinux patches :) )

Re: [PATCH 2/5] libsepol/cil: Fix syntax checking of defaultrange rule

[James Carter]

On Sat, Jun 19, 2021 at 9:36 AM Nicolas Iooss <nicolas.iooss@m4x.org> wrote:
>
> On Mon, Jun 14, 2021 at 5:05 PM James Carter <jwcart2@gmail.com> wrote:
> >
> > The syntax array that cil_gen_defaultrange() called __cil_verify_syntax()
> > with was wrong. It had the range (which should be low, high, or low-high)
> > as optional when it is not.
> >
> > Use the correct syntax array to check the syntax of the defaultrange rule.
> >
> > Signed-off-by: James Carter <jwcart2@gmail.com>
> > ---
> >  libsepol/cil/src/cil_build_ast.c | 2 +-
> >  1 file changed, 1 insertion(+), 1 deletion(-)
> >
> > diff --git a/libsepol/cil/src/cil_build_ast.c b/libsepol/cil/src/cil_build_ast.c
> > index 71f14e20..a5f617d8 100644
> > --- a/libsepol/cil/src/cil_build_ast.c
> > +++ b/libsepol/cil/src/cil_build_ast.c
> > @@ -5862,7 +5862,7 @@ int cil_gen_defaultrange(struct cil_tree_node *parse_current, struct cil_tree_no
> >                 CIL_SYN_STRING,
> >                 CIL_SYN_STRING | CIL_SYN_LIST,
> >                 CIL_SYN_STRING,
> > -               CIL_SYN_STRING | CIL_SYN_END,
> > +               CIL_SYN_STRING,
> >                 CIL_SYN_END
> >         };
> >         int syntax_len = sizeof(syntax)/sizeof(*syntax);
> > --
> > 2.26.3
>
> Hello,
> This patch will break selinux-testsuite with:
>
> /usr/sbin/semodule -i test_policy/test_policy.pp test_mlsconstrain.cil
> test_overlay_defaultrange.cil test_userfaultfd.cil test_add_levels.cil
> test_glblub.cil
> Invalid syntax
> Bad defaultrange declaration at
> /var/lib/selinux/targeted/tmp/modules/400/test_glblub/cil:1
> Failed to build AST
> /usr/sbin/semodule: Failed!
>
> ... because it currently uses, in
> https://github.com/SELinuxProject/selinux-testsuite/blob/0b78a9d433e8c4f956d18dc0db901f0a1a58c003/policy/test_glblub.cil
> :
>
>     (defaultrange db_table glblub)
>
> If I understand the commit message correctly, a range (low, high or
> low-high) has to be added to this statement. I am not familiar with
> glbulb and do not know how the testsuite should be modified. Could the
> policy used by the testsuite be fixed before applying this patch?
>

No, the policy is correct. I forgot about glbulb and misread the
source code. I will have to check the syntax in a different way.

Thanks,
Jim


> Cheers,
> Nicolas
>
> (PS : I was quite busy last month but now I have some time again to
> catch up with SELinux patches :) )
>

[PATCH 3/5] libsepol/cil: Check for empty list when marking neverallow attributes

[James Carter]

When marking a type attribute as used in a neverallow (to help determine
whether or not it should be expanded), check if the attribute's expression
list is empty (no attributes are associated with it) before iterating
over the list.

Signed-off-by: James Carter <jwcart2@gmail.com>
---
 libsepol/cil/src/cil_post.c | 4 ++++
 1 file changed, 4 insertions(+)

diff --git a/libsepol/cil/src/cil_post.c b/libsepol/cil/src/cil_post.c
index 05842b64..38544aef 100644
--- a/libsepol/cil/src/cil_post.c
+++ b/libsepol/cil/src/cil_post.c
@@ -1494,6 +1494,10 @@ static void __mark_neverallow_attrs(struct cil_list *expr_list)
 {
 	struct cil_list_item *curr;
 
+	if (!expr_list) {
+		return;
+	}
+
 	cil_list_for_each(curr, expr_list) {
 		if (curr->flavor == CIL_DATUM) {
 			if (FLAVOR(curr->data) == CIL_TYPEATTRIBUTE) {
-- 
2.26.3

Re: [PATCH 3/5] libsepol/cil: Check for empty list when marking neverallow attributes

[Nicolas Iooss]

On Mon, Jun 14, 2021 at 5:05 PM James Carter <jwcart2@gmail.com> wrote:
>
> When marking a type attribute as used in a neverallow (to help determine
> whether or not it should be expanded), check if the attribute's expression
> list is empty (no attributes are associated with it) before iterating
> over the list.
>
> Signed-off-by: James Carter <jwcart2@gmail.com>

For this patch:

Acked-by: Nicolas Iooss <nicolas.iooss@m4x.org>

Thanks!

> ---
>  libsepol/cil/src/cil_post.c | 4 ++++
>  1 file changed, 4 insertions(+)
>
> diff --git a/libsepol/cil/src/cil_post.c b/libsepol/cil/src/cil_post.c
> index 05842b64..38544aef 100644
> --- a/libsepol/cil/src/cil_post.c
> +++ b/libsepol/cil/src/cil_post.c
> @@ -1494,6 +1494,10 @@ static void __mark_neverallow_attrs(struct cil_list *expr_list)
>  {
>         struct cil_list_item *curr;
>
> +       if (!expr_list) {
> +               return;
> +       }
> +
>         cil_list_for_each(curr, expr_list) {
>                 if (curr->flavor == CIL_DATUM) {
>                         if (FLAVOR(curr->data) == CIL_TYPEATTRIBUTE) {
> --
> 2.26.3
>

[PATCH 4/5] libsepol/cil: Reduce the initial symtab sizes for blocks

[James Carter]

It is possible to create bad behaving policy that can consume all
of a system's memory (one way is through the use of inheritance).
Analyzing these policies shows that most of the memory usage is for
the block symtabs.

Most of the nineteen symtabs will most likely never be used, so give
these symtabs an initial size of 1. The others are given more
appropriate sizes.

Signed-off-by: James Carter <jwcart2@gmail.com>
---
 libsepol/cil/src/cil.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/libsepol/cil/src/cil.c b/libsepol/cil/src/cil.c
index 0d351b49..c6674fc1 100644
--- a/libsepol/cil/src/cil.c
+++ b/libsepol/cil/src/cil.c
@@ -54,7 +54,7 @@
 
 int cil_sym_sizes[CIL_SYM_ARRAY_NUM][CIL_SYM_NUM] = {
 	{64, 64, 64, 1 << 13, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64},
-	{64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64},
+	{8, 8, 8, 32, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1},
 	{1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1},
 	{1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1},
 	{1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1}
-- 
2.26.3

Re: [PATCH 4/5] libsepol/cil: Reduce the initial symtab sizes for blocks

[Nicolas Iooss]

On Mon, Jun 14, 2021 at 5:05 PM James Carter <jwcart2@gmail.com> wrote:
>
> It is possible to create bad behaving policy that can consume all
> of a system's memory (one way is through the use of inheritance).
> Analyzing these policies shows that most of the memory usage is for
> the block symtabs.
>
> Most of the nineteen symtabs will most likely never be used, so give
> these symtabs an initial size of 1. The others are given more
> appropriate sizes.
>
> Signed-off-by: James Carter <jwcart2@gmail.com>

For this patch:

Acked-by: Nicolas Iooss <nicolas.iooss@m4x.org>

Thanks!

> ---
>  libsepol/cil/src/cil.c | 2 +-
>  1 file changed, 1 insertion(+), 1 deletion(-)
>
> diff --git a/libsepol/cil/src/cil.c b/libsepol/cil/src/cil.c
> index 0d351b49..c6674fc1 100644
> --- a/libsepol/cil/src/cil.c
> +++ b/libsepol/cil/src/cil.c
> @@ -54,7 +54,7 @@
>
>  int cil_sym_sizes[CIL_SYM_ARRAY_NUM][CIL_SYM_NUM] = {
>         {64, 64, 64, 1 << 13, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64},
> -       {64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64},
> +       {8, 8, 8, 32, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1},
>         {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1},
>         {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1},
>         {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1}
> --
> 2.26.3
>

[PATCH 5/5] libsepol/cil: Improve degenerate inheritance check

[James Carter]

The commit 74d00a8decebf940d95064ff60042dcb2cbcc2c0 (libsepol/cil:
Detect degenerate inheritance and exit with an error) detects the
use of inheritance (mostly by the secilc-fuzzer and not in any real
policies) that results in the exponential growth of the policy through
the copying of blocks that takes place with inheritance in CIL.
Unfortunately, the check takes place during the pass when all the
blocks are being copied, so it is possible to consume all of a system's
memory before an error is produced.

The new check happens in two parts. First, a check is made while the
block inheritance is being linked to the block it will inherit. In
this check, all of the parent nodes of the inheritance rule up to the
root node are checked and if enough of these blocks are being inherited
(>= CIL_DEGENERATE_INHERITANCE_DEPTH), then a flag is set for a more
in-depth check after the pass. This in-depth check will determine the
number of potential inheritances that will occur when resolving the
all of the inheritance rules. If this value is greater than
CIL_DEGENERATE_INHERITANCE_GROWTH * the original number of inheritance
rules and greater than CIL_DEGENERATE_INHERITANCE_MINIMUM (which is
set to 0x1 << CIL_DEGENERATE_INHERITANCE_DEPTH), then degenerate
inheritance is determined to have occurred and an error result will
be returned.

Since the potential number of inheritances can quickly be an extremely
large number, the count of potential inheritances is aborted as soon
as the threshold for degenerate inheritance has been exceeded.

Normal policies should rarely, if ever, have the in-depth check occur.

Signed-off-by: James Carter <jwcart2@gmail.com>
---
 libsepol/cil/src/cil_internal.h    |   5 +-
 libsepol/cil/src/cil_resolve_ast.c | 229 +++++++++++++++++++----------
 2 files changed, 153 insertions(+), 81 deletions(-)

diff --git a/libsepol/cil/src/cil_internal.h b/libsepol/cil/src/cil_internal.h
index a77c9520..b8610976 100644
--- a/libsepol/cil/src/cil_internal.h
+++ b/libsepol/cil/src/cil_internal.h
@@ -48,8 +48,9 @@
 
 #define CIL_MAX_NAME_LENGTH 2048
 
-#define CIL_DEGENERATE_INHERITANCE_DEPTH 12
-#define CIL_DEGENERATE_INHERITANCE_BREADTH (0x1 << CIL_DEGENERATE_INHERITANCE_DEPTH)
+#define CIL_DEGENERATE_INHERITANCE_DEPTH 10UL
+#define CIL_DEGENERATE_INHERITANCE_MINIMUM (0x01 << CIL_DEGENERATE_INHERITANCE_DEPTH)
+#define CIL_DEGENERATE_INHERITANCE_GROWTH 10UL
 
 enum cil_pass {
 	CIL_PASS_INIT = 0,
diff --git a/libsepol/cil/src/cil_resolve_ast.c b/libsepol/cil/src/cil_resolve_ast.c
index 77ffe0ff..baf6fc0d 100644
--- a/libsepol/cil/src/cil_resolve_ast.c
+++ b/libsepol/cil/src/cil_resolve_ast.c
@@ -62,6 +62,7 @@ struct cil_args_resolve {
 	struct cil_list *catorder_lists;
 	struct cil_list *sensitivityorder_lists;
 	struct cil_list *in_list;
+	int *inheritance_check;
 };
 
 static struct cil_name * __cil_insert_name(struct cil_db *db, hashtab_key_t key, struct cil_tree_node *ast_node)
@@ -2306,40 +2307,7 @@ exit:
 	return rc;
 }
 
-int cil_resolve_blockinherit_link(struct cil_tree_node *current, void *extra_args)
-{
-	struct cil_blockinherit *inherit = current->data;
-	struct cil_symtab_datum *block_datum = NULL;
-	struct cil_tree_node *node = NULL;
-	int rc = SEPOL_ERR;
-
-	rc = cil_resolve_name(current, inherit->block_str, CIL_SYM_BLOCKS, extra_args, &block_datum);
-	if (rc != SEPOL_OK) {
-		goto exit;
-	}
-
-	node = NODE(block_datum);
-
-	if (node->flavor != CIL_BLOCK) {
-		cil_log(CIL_ERR, "%s is not a block\n", cil_node_to_string(node));
-		rc = SEPOL_ERR;
-		goto exit;
-	}
-
-	inherit->block = (struct cil_block *)block_datum;
-
-	if (inherit->block->bi_nodes == NULL) {
-		cil_list_init(&inherit->block->bi_nodes, CIL_NODE);
-	}
-	cil_list_append(inherit->block->bi_nodes, CIL_NODE, current);
-
-	return SEPOL_OK;
-
-exit:
-	return rc;
-}
-
-void cil_print_recursive_blockinherit(struct cil_tree_node *bi_node, struct cil_tree_node *terminating_node)
+static void cil_print_recursive_blockinherit(struct cil_tree_node *bi_node, struct cil_tree_node *terminating_node)
 {
 	struct cil_list *trace = NULL;
 	struct cil_list_item *item = NULL;
@@ -2377,7 +2345,7 @@ void cil_print_recursive_blockinherit(struct cil_tree_node *bi_node, struct cil_
 	cil_list_destroy(&trace, CIL_FALSE);
 }
 
-int cil_check_recursive_blockinherit(struct cil_tree_node *bi_node)
+static int cil_check_recursive_blockinherit(struct cil_tree_node *bi_node)
 {
 	struct cil_tree_node *curr = NULL;
 	struct cil_blockinherit *bi = NULL;
@@ -2410,53 +2378,68 @@ exit:
 	return rc;
 }
 
-/*
- * Detect degenerate inheritance of the form:
- * ...
- * (blockinherit ba)
- * (block ba
- *    (block b1
- *      (blockinherit bb)
- *    )
- *    (block bb
- *      (block b2
- *        (blockinherit bc)
- *      )
- *      (block bc
- *      ...
- */
-static int cil_check_for_degenerate_inheritance(struct cil_tree_node *current)
+static int cil_possible_degenerate_inheritance(struct cil_tree_node *node)
 {
-	struct cil_block *block = current->data;
-	struct cil_tree_node *node;
-	struct cil_list_item *item;
-	unsigned depth;
-	unsigned breadth = 0;
-
-	cil_list_for_each(item, block->bi_nodes) {
-		breadth++;
-	}
+	unsigned depth = 1;
 
-	if (breadth >= CIL_DEGENERATE_INHERITANCE_BREADTH) {
-		node = current->parent;
-		depth = 0;
-		while (node && node->flavor != CIL_ROOT) {
-			if (node->flavor == CIL_BLOCK) {
-				block = node->data;
-				if (block->bi_nodes != NULL) {
-					depth++;
-				}
+	node = node->parent;
+	while (node && node->flavor != CIL_ROOT) {
+		if (node->flavor == CIL_BLOCK) {
+			if (((struct cil_block *)(node->data))->bi_nodes != NULL) {
+				depth++;
 			}
-			node = node->parent;
 		}
+		node = node->parent;
+	}
 
-		if (depth >= CIL_DEGENERATE_INHERITANCE_DEPTH) {
-			cil_tree_log(current, CIL_ERR, "Degenerate inheritance detected (depth=%u, breadth=%u)", depth, breadth);
-			return SEPOL_ERR;
-		}
+	if (depth >= CIL_DEGENERATE_INHERITANCE_DEPTH) {
+		return CIL_TRUE;
+	}
+
+	return CIL_FALSE;
+}
+
+int cil_resolve_blockinherit_link(struct cil_tree_node *current, void *extra_args)
+{
+	struct cil_args_resolve *args = extra_args;
+	struct cil_blockinherit *inherit = current->data;
+	struct cil_symtab_datum *block_datum = NULL;
+	struct cil_tree_node *node = NULL;
+	int rc = SEPOL_ERR;
+
+	rc = cil_resolve_name(current, inherit->block_str, CIL_SYM_BLOCKS, extra_args, &block_datum);
+	if (rc != SEPOL_OK) {
+		goto exit;
+	}
+
+	node = NODE(block_datum);
+
+	if (node->flavor != CIL_BLOCK) {
+		cil_log(CIL_ERR, "%s is not a block\n", cil_node_to_string(node));
+		rc = SEPOL_ERR;
+		goto exit;
+	}
+
+	inherit->block = (struct cil_block *)block_datum;
+
+	rc = cil_check_recursive_blockinherit(current);
+	if (rc != SEPOL_OK) {
+			goto exit;
+	}
+
+	if (inherit->block->bi_nodes == NULL) {
+		cil_list_init(&inherit->block->bi_nodes, CIL_NODE);
+	}
+	cil_list_append(inherit->block->bi_nodes, CIL_NODE, current);
+
+	if (*(args->inheritance_check) == CIL_FALSE) {
+		*(args->inheritance_check) = cil_possible_degenerate_inheritance(node);
 	}
 
 	return SEPOL_OK;
+
+exit:
+	return rc;
 }
 
 int cil_resolve_blockinherit_copy(struct cil_tree_node *current, void *extra_args)
@@ -2475,11 +2458,6 @@ int cil_resolve_blockinherit_copy(struct cil_tree_node *current, void *extra_arg
 
 	db = args->db;
 
-	rc = cil_check_for_degenerate_inheritance(current);
-	if (rc != SEPOL_OK) {
-		goto exit;
-	}
-
 	// Make sure this is the original block and not a merged block from a blockinherit
 	if (current != block->datum.nodes->head->data) {
 		rc = SEPOL_OK;
@@ -3579,6 +3557,88 @@ exit:
 	return rc;
 }
 
+/*
+ * Degenerate inheritance leads to exponential growth of the policy
+ * It can take many forms, but here is one example.
+ * ...
+ * (blockinherit ba)
+ * (block b0
+ *   (block b1
+ *     (block b2
+ *       (block b3
+ *         ...
+ *       )
+ *       (blockinherit b3)
+ *     )
+ *     (blockinherit b2)
+ *   )
+ *   (blockinherit b1)
+ * )
+ * (blockinherit b0)
+ * ...
+ * This leads to 2^4 copies of the content of block b3, 2^3 copies of the
+ * contents of block b2, etc.
+ */
+static unsigned cil_count_actual(struct cil_tree_node *node)
+{
+	unsigned count = 0;
+
+	if (node->flavor == CIL_BLOCKINHERIT) {
+		count += 1;
+	}
+
+	for (node = node->cl_head; node; node = node->next) {
+		count += cil_count_actual(node);
+	}
+
+	return count;
+}
+
+static unsigned cil_count_potential(struct cil_tree_node *node, unsigned max)
+{
+	unsigned count = 0;
+
+	if (node->flavor == CIL_BLOCKINHERIT) {
+		struct cil_blockinherit *bi = node->data;
+		count += 1;
+		if (bi->block) {
+			count += cil_count_potential(NODE(bi->block), max);
+			if (count > max) {
+				return count;
+			}
+		}
+	}
+
+	for (node = node->cl_head; node; node = node->next) {
+		count += cil_count_potential(node, max);
+		if (count > max) {
+			return count;
+		}
+	}
+
+	return count;
+}
+
+static int cil_check_for_degenerate_inheritance(struct cil_tree_node *node)
+{
+	uint64_t num_actual, num_potential, max;
+
+	num_actual = cil_count_actual(node);
+
+	max = num_actual * CIL_DEGENERATE_INHERITANCE_GROWTH;
+	if (max < CIL_DEGENERATE_INHERITANCE_MINIMUM) {
+		max = CIL_DEGENERATE_INHERITANCE_MINIMUM;
+	}
+
+	num_potential = cil_count_potential(node, max);
+
+	if (num_potential > max) {
+		return SEPOL_ERR;
+	}
+
+	return SEPOL_OK;
+}
+
 int __cil_resolve_ast_node(struct cil_tree_node *node, void *extra_args)
 {
 	int rc = SEPOL_OK;
@@ -4054,6 +4114,7 @@ int cil_resolve_ast(struct cil_db *db, struct cil_tree_node *current)
 	struct cil_args_resolve extra_args;
 	enum cil_pass pass = CIL_PASS_TIF;
 	uint32_t changed = 0;
+	int inheritance_check = 0;
 
 	if (db == NULL || current == NULL) {
 		return rc;
@@ -4072,6 +4133,7 @@ int cil_resolve_ast(struct cil_db *db, struct cil_tree_node *current)
 	extra_args.catorder_lists = NULL;
 	extra_args.sensitivityorder_lists = NULL;
 	extra_args.in_list = NULL;
+	extra_args.inheritance_check = &inheritance_check;
 
 	cil_list_init(&extra_args.disabled_optionals, CIL_NODE);
 	cil_list_init(&extra_args.sidorder_lists, CIL_LIST_ITEM);
@@ -4096,6 +4158,15 @@ int cil_resolve_ast(struct cil_db *db, struct cil_tree_node *current)
 			cil_list_destroy(&extra_args.in_list, CIL_FALSE);
 		}
 
+		if (pass == CIL_PASS_BLKIN_LINK) {
+			rc = cil_check_for_degenerate_inheritance(current);
+			if (rc != SEPOL_OK) {
+				cil_log(CIL_ERR, "Degenerate inheritance detected\n");
+				rc = SEPOL_ERR;
+				goto exit;
+			}
+		}
+
 		if (pass == CIL_PASS_MISC1) {
 			db->sidorder = __cil_ordered_lists_merge_all(&extra_args.sidorder_lists, NULL);
 			if (db->sidorder == NULL) {
-- 
2.26.3

Re: [PATCH 5/5] libsepol/cil: Improve degenerate inheritance check

[Nicolas Iooss]

On Mon, Jun 14, 2021 at 5:05 PM James Carter <jwcart2@gmail.com> wrote:
>
> The commit 74d00a8decebf940d95064ff60042dcb2cbcc2c0 (libsepol/cil:
> Detect degenerate inheritance and exit with an error) detects the
> use of inheritance (mostly by the secilc-fuzzer and not in any real
> policies) that results in the exponential growth of the policy through
> the copying of blocks that takes place with inheritance in CIL.
> Unfortunately, the check takes place during the pass when all the
> blocks are being copied, so it is possible to consume all of a system's
> memory before an error is produced.
>
> The new check happens in two parts. First, a check is made while the
> block inheritance is being linked to the block it will inherit. In
> this check, all of the parent nodes of the inheritance rule up to the
> root node are checked and if enough of these blocks are being inherited
> (>= CIL_DEGENERATE_INHERITANCE_DEPTH), then a flag is set for a more
> in-depth check after the pass. This in-depth check will determine the
> number of potential inheritances that will occur when resolving the
> all of the inheritance rules. If this value is greater than
> CIL_DEGENERATE_INHERITANCE_GROWTH * the original number of inheritance
> rules and greater than CIL_DEGENERATE_INHERITANCE_MINIMUM (which is
> set to 0x1 << CIL_DEGENERATE_INHERITANCE_DEPTH), then degenerate
> inheritance is determined to have occurred and an error result will
> be returned.
>
> Since the potential number of inheritances can quickly be an extremely
> large number, the count of potential inheritances is aborted as soon
> as the threshold for degenerate inheritance has been exceeded.
>
> Normal policies should rarely, if ever, have the in-depth check occur.
>
> Signed-off-by: James Carter <jwcart2@gmail.com>
> ---
>  libsepol/cil/src/cil_internal.h    |   5 +-
>  libsepol/cil/src/cil_resolve_ast.c | 229 +++++++++++++++++++----------
>  2 files changed, 153 insertions(+), 81 deletions(-)
>
> diff --git a/libsepol/cil/src/cil_internal.h b/libsepol/cil/src/cil_internal.h
> index a77c9520..b8610976 100644
> --- a/libsepol/cil/src/cil_internal.h
> +++ b/libsepol/cil/src/cil_internal.h
> @@ -48,8 +48,9 @@
>
>  #define CIL_MAX_NAME_LENGTH 2048
>
> -#define CIL_DEGENERATE_INHERITANCE_DEPTH 12
> -#define CIL_DEGENERATE_INHERITANCE_BREADTH (0x1 << CIL_DEGENERATE_INHERITANCE_DEPTH)
> +#define CIL_DEGENERATE_INHERITANCE_DEPTH 10UL
> +#define CIL_DEGENERATE_INHERITANCE_MINIMUM (0x01 << CIL_DEGENERATE_INHERITANCE_DEPTH)
> +#define CIL_DEGENERATE_INHERITANCE_GROWTH 10UL
>
>  enum cil_pass {
>         CIL_PASS_INIT = 0,
> diff --git a/libsepol/cil/src/cil_resolve_ast.c b/libsepol/cil/src/cil_resolve_ast.c
> index 77ffe0ff..baf6fc0d 100644
> --- a/libsepol/cil/src/cil_resolve_ast.c
> +++ b/libsepol/cil/src/cil_resolve_ast.c
> @@ -62,6 +62,7 @@ struct cil_args_resolve {
>         struct cil_list *catorder_lists;
>         struct cil_list *sensitivityorder_lists;
>         struct cil_list *in_list;
> +       int *inheritance_check;
>  };
>
>  static struct cil_name * __cil_insert_name(struct cil_db *db, hashtab_key_t key, struct cil_tree_node *ast_node)
> @@ -2306,40 +2307,7 @@ exit:
>         return rc;
>  }
>
> -int cil_resolve_blockinherit_link(struct cil_tree_node *current, void *extra_args)
> -{
> -       struct cil_blockinherit *inherit = current->data;
> -       struct cil_symtab_datum *block_datum = NULL;
> -       struct cil_tree_node *node = NULL;
> -       int rc = SEPOL_ERR;
> -
> -       rc = cil_resolve_name(current, inherit->block_str, CIL_SYM_BLOCKS, extra_args, &block_datum);
> -       if (rc != SEPOL_OK) {
> -               goto exit;
> -       }
> -
> -       node = NODE(block_datum);
> -
> -       if (node->flavor != CIL_BLOCK) {
> -               cil_log(CIL_ERR, "%s is not a block\n", cil_node_to_string(node));
> -               rc = SEPOL_ERR;
> -               goto exit;
> -       }
> -
> -       inherit->block = (struct cil_block *)block_datum;
> -
> -       if (inherit->block->bi_nodes == NULL) {
> -               cil_list_init(&inherit->block->bi_nodes, CIL_NODE);
> -       }
> -       cil_list_append(inherit->block->bi_nodes, CIL_NODE, current);
> -
> -       return SEPOL_OK;
> -
> -exit:
> -       return rc;
> -}
> -
> -void cil_print_recursive_blockinherit(struct cil_tree_node *bi_node, struct cil_tree_node *terminating_node)
> +static void cil_print_recursive_blockinherit(struct cil_tree_node *bi_node, struct cil_tree_node *terminating_node)
>  {
>         struct cil_list *trace = NULL;
>         struct cil_list_item *item = NULL;
> @@ -2377,7 +2345,7 @@ void cil_print_recursive_blockinherit(struct cil_tree_node *bi_node, struct cil_
>         cil_list_destroy(&trace, CIL_FALSE);
>  }
>
> -int cil_check_recursive_blockinherit(struct cil_tree_node *bi_node)
> +static int cil_check_recursive_blockinherit(struct cil_tree_node *bi_node)
>  {
>         struct cil_tree_node *curr = NULL;
>         struct cil_blockinherit *bi = NULL;
> @@ -2410,53 +2378,68 @@ exit:
>         return rc;
>  }
>
> -/*
> - * Detect degenerate inheritance of the form:
> - * ...
> - * (blockinherit ba)
> - * (block ba
> - *    (block b1
> - *      (blockinherit bb)
> - *    )
> - *    (block bb
> - *      (block b2
> - *        (blockinherit bc)
> - *      )
> - *      (block bc
> - *      ...
> - */
> -static int cil_check_for_degenerate_inheritance(struct cil_tree_node *current)
> +static int cil_possible_degenerate_inheritance(struct cil_tree_node *node)
>  {
> -       struct cil_block *block = current->data;
> -       struct cil_tree_node *node;
> -       struct cil_list_item *item;
> -       unsigned depth;
> -       unsigned breadth = 0;
> -
> -       cil_list_for_each(item, block->bi_nodes) {
> -               breadth++;
> -       }
> +       unsigned depth = 1;
>
> -       if (breadth >= CIL_DEGENERATE_INHERITANCE_BREADTH) {
> -               node = current->parent;
> -               depth = 0;
> -               while (node && node->flavor != CIL_ROOT) {
> -                       if (node->flavor == CIL_BLOCK) {
> -                               block = node->data;
> -                               if (block->bi_nodes != NULL) {
> -                                       depth++;
> -                               }
> +       node = node->parent;
> +       while (node && node->flavor != CIL_ROOT) {
> +               if (node->flavor == CIL_BLOCK) {
> +                       if (((struct cil_block *)(node->data))->bi_nodes != NULL) {
> +                               depth++;
>                         }
> -                       node = node->parent;
>                 }
> +               node = node->parent;
> +       }
>
> -               if (depth >= CIL_DEGENERATE_INHERITANCE_DEPTH) {
> -                       cil_tree_log(current, CIL_ERR, "Degenerate inheritance detected (depth=%u, breadth=%u)", depth, breadth);
> -                       return SEPOL_ERR;
> -               }
> +       if (depth >= CIL_DEGENERATE_INHERITANCE_DEPTH) {
> +               return CIL_TRUE;
> +       }

When I first read the code, I wondered whether this "if" condition
would better be in the while loop, in order to break early when depth
exceeds the threshold. Then I thought that the code was actually
right, because the condition is expected to be unlikely. Maybe you
could add a comment /* This condition is unlikely to happen so put it
after the loop */ right before if (depth >=
CIL_DEGENERATE_INHERITANCE_DEPTH)?

By the way in the patch I saw how "inheritance_check" is set, but I
did not find where it is actually checked. Could you point me to the
functions/lines which actually use its value?

Cheers,
Nicolas

Re: [PATCH 5/5] libsepol/cil: Improve degenerate inheritance check

[James Carter]

On Sat, Jun 19, 2021 at 10:03 AM Nicolas Iooss <nicolas.iooss@m4x.org> wrote:
>
> On Mon, Jun 14, 2021 at 5:05 PM James Carter <jwcart2@gmail.com> wrote:
> >
> > The commit 74d00a8decebf940d95064ff60042dcb2cbcc2c0 (libsepol/cil:
> > Detect degenerate inheritance and exit with an error) detects the
> > use of inheritance (mostly by the secilc-fuzzer and not in any real
> > policies) that results in the exponential growth of the policy through
> > the copying of blocks that takes place with inheritance in CIL.
> > Unfortunately, the check takes place during the pass when all the
> > blocks are being copied, so it is possible to consume all of a system's
> > memory before an error is produced.
> >
> > The new check happens in two parts. First, a check is made while the
> > block inheritance is being linked to the block it will inherit. In
> > this check, all of the parent nodes of the inheritance rule up to the
> > root node are checked and if enough of these blocks are being inherited
> > (>= CIL_DEGENERATE_INHERITANCE_DEPTH), then a flag is set for a more
> > in-depth check after the pass. This in-depth check will determine the
> > number of potential inheritances that will occur when resolving the
> > all of the inheritance rules. If this value is greater than
> > CIL_DEGENERATE_INHERITANCE_GROWTH * the original number of inheritance
> > rules and greater than CIL_DEGENERATE_INHERITANCE_MINIMUM (which is
> > set to 0x1 << CIL_DEGENERATE_INHERITANCE_DEPTH), then degenerate
> > inheritance is determined to have occurred and an error result will
> > be returned.
> >
> > Since the potential number of inheritances can quickly be an extremely
> > large number, the count of potential inheritances is aborted as soon
> > as the threshold for degenerate inheritance has been exceeded.
> >
> > Normal policies should rarely, if ever, have the in-depth check occur.
> >
> > Signed-off-by: James Carter <jwcart2@gmail.com>
> > ---
> >  libsepol/cil/src/cil_internal.h    |   5 +-
> >  libsepol/cil/src/cil_resolve_ast.c | 229 +++++++++++++++++++----------
> >  2 files changed, 153 insertions(+), 81 deletions(-)
> >
> > diff --git a/libsepol/cil/src/cil_internal.h b/libsepol/cil/src/cil_internal.h
> > index a77c9520..b8610976 100644
> > --- a/libsepol/cil/src/cil_internal.h
> > +++ b/libsepol/cil/src/cil_internal.h
> > @@ -48,8 +48,9 @@
> >
> >  #define CIL_MAX_NAME_LENGTH 2048
> >
> > -#define CIL_DEGENERATE_INHERITANCE_DEPTH 12
> > -#define CIL_DEGENERATE_INHERITANCE_BREADTH (0x1 << CIL_DEGENERATE_INHERITANCE_DEPTH)
> > +#define CIL_DEGENERATE_INHERITANCE_DEPTH 10UL
> > +#define CIL_DEGENERATE_INHERITANCE_MINIMUM (0x01 << CIL_DEGENERATE_INHERITANCE_DEPTH)
> > +#define CIL_DEGENERATE_INHERITANCE_GROWTH 10UL
> >
> >  enum cil_pass {
> >         CIL_PASS_INIT = 0,
> > diff --git a/libsepol/cil/src/cil_resolve_ast.c b/libsepol/cil/src/cil_resolve_ast.c
> > index 77ffe0ff..baf6fc0d 100644
> > --- a/libsepol/cil/src/cil_resolve_ast.c
> > +++ b/libsepol/cil/src/cil_resolve_ast.c
> > @@ -62,6 +62,7 @@ struct cil_args_resolve {
> >         struct cil_list *catorder_lists;
> >         struct cil_list *sensitivityorder_lists;
> >         struct cil_list *in_list;
> > +       int *inheritance_check;
> >  };
> >
> >  static struct cil_name * __cil_insert_name(struct cil_db *db, hashtab_key_t key, struct cil_tree_node *ast_node)
> > @@ -2306,40 +2307,7 @@ exit:
> >         return rc;
> >  }
> >
> > -int cil_resolve_blockinherit_link(struct cil_tree_node *current, void *extra_args)
> > -{
> > -       struct cil_blockinherit *inherit = current->data;
> > -       struct cil_symtab_datum *block_datum = NULL;
> > -       struct cil_tree_node *node = NULL;
> > -       int rc = SEPOL_ERR;
> > -
> > -       rc = cil_resolve_name(current, inherit->block_str, CIL_SYM_BLOCKS, extra_args, &block_datum);
> > -       if (rc != SEPOL_OK) {
> > -               goto exit;
> > -       }
> > -
> > -       node = NODE(block_datum);
> > -
> > -       if (node->flavor != CIL_BLOCK) {
> > -               cil_log(CIL_ERR, "%s is not a block\n", cil_node_to_string(node));
> > -               rc = SEPOL_ERR;
> > -               goto exit;
> > -       }
> > -
> > -       inherit->block = (struct cil_block *)block_datum;
> > -
> > -       if (inherit->block->bi_nodes == NULL) {
> > -               cil_list_init(&inherit->block->bi_nodes, CIL_NODE);
> > -       }
> > -       cil_list_append(inherit->block->bi_nodes, CIL_NODE, current);
> > -
> > -       return SEPOL_OK;
> > -
> > -exit:
> > -       return rc;
> > -}
> > -
> > -void cil_print_recursive_blockinherit(struct cil_tree_node *bi_node, struct cil_tree_node *terminating_node)
> > +static void cil_print_recursive_blockinherit(struct cil_tree_node *bi_node, struct cil_tree_node *terminating_node)
> >  {
> >         struct cil_list *trace = NULL;
> >         struct cil_list_item *item = NULL;
> > @@ -2377,7 +2345,7 @@ void cil_print_recursive_blockinherit(struct cil_tree_node *bi_node, struct cil_
> >         cil_list_destroy(&trace, CIL_FALSE);
> >  }
> >
> > -int cil_check_recursive_blockinherit(struct cil_tree_node *bi_node)
> > +static int cil_check_recursive_blockinherit(struct cil_tree_node *bi_node)
> >  {
> >         struct cil_tree_node *curr = NULL;
> >         struct cil_blockinherit *bi = NULL;
> > @@ -2410,53 +2378,68 @@ exit:
> >         return rc;
> >  }
> >
> > -/*
> > - * Detect degenerate inheritance of the form:
> > - * ...
> > - * (blockinherit ba)
> > - * (block ba
> > - *    (block b1
> > - *      (blockinherit bb)
> > - *    )
> > - *    (block bb
> > - *      (block b2
> > - *        (blockinherit bc)
> > - *      )
> > - *      (block bc
> > - *      ...
> > - */
> > -static int cil_check_for_degenerate_inheritance(struct cil_tree_node *current)
> > +static int cil_possible_degenerate_inheritance(struct cil_tree_node *node)
> >  {
> > -       struct cil_block *block = current->data;
> > -       struct cil_tree_node *node;
> > -       struct cil_list_item *item;
> > -       unsigned depth;
> > -       unsigned breadth = 0;
> > -
> > -       cil_list_for_each(item, block->bi_nodes) {
> > -               breadth++;
> > -       }
> > +       unsigned depth = 1;
> >
> > -       if (breadth >= CIL_DEGENERATE_INHERITANCE_BREADTH) {
> > -               node = current->parent;
> > -               depth = 0;
> > -               while (node && node->flavor != CIL_ROOT) {
> > -                       if (node->flavor == CIL_BLOCK) {
> > -                               block = node->data;
> > -                               if (block->bi_nodes != NULL) {
> > -                                       depth++;
> > -                               }
> > +       node = node->parent;
> > +       while (node && node->flavor != CIL_ROOT) {
> > +               if (node->flavor == CIL_BLOCK) {
> > +                       if (((struct cil_block *)(node->data))->bi_nodes != NULL) {
> > +                               depth++;
> >                         }
> > -                       node = node->parent;
> >                 }
> > +               node = node->parent;
> > +       }
> >
> > -               if (depth >= CIL_DEGENERATE_INHERITANCE_DEPTH) {
> > -                       cil_tree_log(current, CIL_ERR, "Degenerate inheritance detected (depth=%u, breadth=%u)", depth, breadth);
> > -                       return SEPOL_ERR;
> > -               }
> > +       if (depth >= CIL_DEGENERATE_INHERITANCE_DEPTH) {
> > +               return CIL_TRUE;
> > +       }
>
> When I first read the code, I wondered whether this "if" condition
> would better be in the while loop, in order to break early when depth
> exceeds the threshold. Then I thought that the code was actually
> right, because the condition is expected to be unlikely. Maybe you
> could add a comment /* This condition is unlikely to happen so put it
> after the loop */ right before if (depth >=
> CIL_DEGENERATE_INHERITANCE_DEPTH)?
>

It is unlikely to trigger, but it seems like it will be clearer to
just put it in the loop. I expect the depth to be 0 most of the time,
so this is not performance critical.

> By the way in the patch I saw how "inheritance_check" is set, but I
> did not find where it is actually checked. Could you point me to the
> functions/lines which actually use its value?
>

I removed the check at one point when I was testing and I didn't put it back in.
The line "if (pass == CIL_PASS_BLKIN_LINK) {" should be "if (pass ==
CIL_PASS_BLKIN_LINK && inheritance_check == CIL_TRUE) {"

I will send out another version.

Thanks,
Jim


> Cheers,
> Nicolas
>