On Mon, Jun 14, 2021 at 5:05 PM James Carter <jwcart2@xxxxxxxxx> 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@xxxxxxxxx>
> ---
> 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
