[PATCH] libsepol/cil: fix heap-use-after-free when using optional blockinherit

[PATCH] libsepol/cil: fix heap-use-after-free when using optional blockinherit

[Nicolas Iooss]

When secilc compiles the following policy:

    (block b1
        (optional o1
            (blockinherit b1)
            (blockinherit x)
        )
    )

it disables the optional block at pass 3 (CIL_PASS_BLKIN_LINK) because
the block "x" does not exist. __cil_resolve_ast_last_child_helper()
calls cil_tree_children_destroy() on the optional block, which destroys
the two blockinherit statements. But the (blockinherit b1) node was
referenced inside (block b1) node, in its block->bi_nodes list.
Therefore, when this list is used at pass 4 (CIL_PASS_BLKIN_COPY), it
contains a node which was freed: this triggers a use-after-free issue

Fix this issue by removing blockinherit nodes from their lists of nodes
block->bi_nodes when they are being destroyed. As
cil_destroy_blockinherit() does not have a reference to the node
containing the blockinherit data, implement this new logic in
cil_tree_node_destroy().

This issue was found while investigating a testcase from an OSS-Fuzz
issue which seems unrelated (a Null-dereference READ in
cil_symtab_get_datum, https://bugs.chromium.org/p/oss-fuzz/issues/detail?id=29861).

Signed-off-by: Nicolas Iooss <nicolas.iooss@m4x.org>
---
 libsepol/cil/src/cil_tree.c | 9 +++++++++
 1 file changed, 9 insertions(+)

diff --git a/libsepol/cil/src/cil_tree.c b/libsepol/cil/src/cil_tree.c
index 886412d1b974..72c4892de707 100644
--- a/libsepol/cil/src/cil_tree.c
+++ b/libsepol/cil/src/cil_tree.c
@@ -223,11 +223,20 @@ void cil_tree_node_init(struct cil_tree_node **node)
 void cil_tree_node_destroy(struct cil_tree_node **node)
 {
 	struct cil_symtab_datum *datum;
+	struct cil_blockinherit *inherit;
 
 	if (node == NULL || *node == NULL) {
 		return;
 	}
 
+	if ((*node)->flavor == CIL_BLOCKINHERIT) {
+		inherit = (*node)->data;
+		if (inherit->block != NULL && inherit->block->bi_nodes != NULL) {
+			// Unlink the blockinherit from the block
+			cil_list_remove(inherit->block->bi_nodes, CIL_NODE, *node, CIL_FALSE);
+		}
+	}
+
 	if ((*node)->flavor >= CIL_MIN_DECLARATIVE) {
 		datum = (*node)->data;
 		cil_symtab_datum_remove_node(datum, *node);
-- 
2.30.0

Re: [PATCH] libsepol/cil: fix heap-use-after-free when using optional blockinherit

[James Carter]

On Sun, Jan 31, 2021 at 6:14 PM Nicolas Iooss <nicolas.iooss@m4x.org> wrote:
>
> When secilc compiles the following policy:
>
>     (block b1
>         (optional o1
>             (blockinherit b1)
>             (blockinherit x)
>         )
>     )
>
> it disables the optional block at pass 3 (CIL_PASS_BLKIN_LINK) because
> the block "x" does not exist. __cil_resolve_ast_last_child_helper()
> calls cil_tree_children_destroy() on the optional block, which destroys
> the two blockinherit statements. But the (blockinherit b1) node was
> referenced inside (block b1) node, in its block->bi_nodes list.
> Therefore, when this list is used at pass 4 (CIL_PASS_BLKIN_COPY), it
> contains a node which was freed: this triggers a use-after-free issue
>
> Fix this issue by removing blockinherit nodes from their lists of nodes
> block->bi_nodes when they are being destroyed. As
> cil_destroy_blockinherit() does not have a reference to the node
> containing the blockinherit data, implement this new logic in
> cil_tree_node_destroy().
>
> This issue was found while investigating a testcase from an OSS-Fuzz
> issue which seems unrelated (a Null-dereference READ in
> cil_symtab_get_datum, https://bugs.chromium.org/p/oss-fuzz/issues/detail?id=29861).
>
> Signed-off-by: Nicolas Iooss <nicolas.iooss@m4x.org>

The patch is good, but I prefer the work to be done in
cil_destroy_blockinherit(), so I just sent out a patch based on this
one to do that.

Jim

> ---
>  libsepol/cil/src/cil_tree.c | 9 +++++++++
>  1 file changed, 9 insertions(+)
>
> diff --git a/libsepol/cil/src/cil_tree.c b/libsepol/cil/src/cil_tree.c
> index 886412d1b974..72c4892de707 100644
> --- a/libsepol/cil/src/cil_tree.c
> +++ b/libsepol/cil/src/cil_tree.c
> @@ -223,11 +223,20 @@ void cil_tree_node_init(struct cil_tree_node **node)
>  void cil_tree_node_destroy(struct cil_tree_node **node)
>  {
>         struct cil_symtab_datum *datum;
> +       struct cil_blockinherit *inherit;
>
>         if (node == NULL || *node == NULL) {
>                 return;
>         }
>
> +       if ((*node)->flavor == CIL_BLOCKINHERIT) {
> +               inherit = (*node)->data;
> +               if (inherit->block != NULL && inherit->block->bi_nodes != NULL) {
> +                       // Unlink the blockinherit from the block
> +                       cil_list_remove(inherit->block->bi_nodes, CIL_NODE, *node, CIL_FALSE);
> +               }
> +       }
> +
>         if ((*node)->flavor >= CIL_MIN_DECLARATIVE) {
>                 datum = (*node)->data;
>                 cil_symtab_datum_remove_node(datum, *node);
> --
> 2.30.0
>

Re: [PATCH] libsepol/cil: Fix heap-use-after-free when using optional blockinherit

[Nicolas Iooss]

On Tue, Feb 2, 2021 at 10:15 PM James Carter <jwcart2@gmail.com> wrote:
>
> On Mon, Feb 1, 2021 at 5:08 PM Nicolas Iooss <nicolas.iooss@m4x.org> wrote:
> >
> > On Mon, Feb 1, 2021 at 3:24 PM James Carter <jwcart2@gmail.com> wrote:
> > >
> > > This is based on a patch by Nicolas Iooss. He writes:
> > >     When secilc compiles the following policy:
> > >
> > >         (block b1
> > >             (optional o1
> > >                 (blockinherit b1)
> > >                 (blockinherit x)
> > >             )
> > >         )
> > >
> > >     it disables the optional block at pass 3 (CIL_PASS_BLKIN_LINK)
> > >     because the block "x" does not exist.
> > >     __cil_resolve_ast_last_child_helper() calls
> > >     cil_tree_children_destroy() on the optional block, which destroys
> > >     the two blockinherit statements. But the (blockinherit b1) node
> > >     was referenced inside (block b1) node, in its block->bi_nodes list.
> > >     Therefore, when this list is used at pass 4 (CIL_PASS_BLKIN_COPY),
> > >     it contains a node which was freed: this triggers a use-after-free
> > >     issue
> > >
> > >     Fix this issue by removing blockinherit nodes from their lists of
> > >     nodes block->bi_nodes when they are being destroyed. As
> > >     cil_destroy_blockinherit() does not have a reference to the node
> > >     containing the blockinherit data, implement this new logic in
> > >     cil_tree_node_destroy().
> > >
> > >     This issue was found while investigating a testcase from an OSS-Fuzz
> > >     issue which seems unrelated (a Null-dereference READ in
> > >     cil_symtab_get_datum,
> > >     https://bugs.chromium.org/p/oss-fuzz/issues/detail?id=29861).
> > >
> > > Reported-by: Nicolas Iooss <nicolas.iooss@m4x.org>
> > > Signed-off-by: James Carter <jwcart2@gmail.com>
> > > ---
> > >  libsepol/cil/src/cil_build_ast.c | 17 +++++++++++++++++
> > >  1 file changed, 17 insertions(+)
> > >
> > > diff --git a/libsepol/cil/src/cil_build_ast.c b/libsepol/cil/src/cil_build_ast.c
> > > index 02481558..3d8367fe 100644
> > > --- a/libsepol/cil/src/cil_build_ast.c
> > > +++ b/libsepol/cil/src/cil_build_ast.c
> > > @@ -283,6 +283,23 @@ void cil_destroy_blockinherit(struct cil_blockinherit *inherit)
> > >                 return;
> > >         }
> > >
> > > +       if (inherit->block != NULL && inherit->block->bi_nodes != NULL) {
> > > +               struct cil_tree_node *node;
> > > +               struct cil_list_item *item;
> > > +               int found = CIL_FALSE;
> > > +
> > > +               cil_list_for_each(item, inherit->block->bi_nodes) {
> > > +                       node = item->data;
> > > +                       if (node->data == inherit) {
> > > +                               found = CIL_TRUE;
> > > +                               break;
> > > +                       }
> > > +               }
> > > +               if (found == CIL_TRUE) {
> > > +                       cil_list_remove(inherit->block->bi_nodes, CIL_NODE, node, CIL_FALSE);
> > > +               }
> > > +       }
> > > +
> > >         free(inherit);
> > >  }
> >
> > Hello,
> > The code seems to be too complex for two reasons.
> >
> > First, doing "if (node->data == inherit) found = CIL_TRUE;" then "if
> > (found == CIL_TRUE){...}" seems too verbose. The code could be
> > simplified to something such as:
> >
> > if (inherit->block != NULL && inherit->block->bi_nodes != NULL) {
> >   struct cil_list_item *item;
> >
> >   /* Find the in bi_nodes the item which contains the inherit object */
> >   cil_list_for_each(item, inherit->block->bi_nodes) {
> >     struct cil_tree_node *node = item->data;
> >     if (node->data == inherit) {
> >       cil_list_remove(inherit->block->bi_nodes, CIL_NODE, node, CIL_FALSE);
> >       break;
> >     }
> >   }
> > }
> >
>
> I sent a revised patch.
>
> > Second, doing so makes the code browse the inherit->block->bi_nodes
> > list twice (in cil_list_for_each and cil_list_remove). This seems to
> > be easily optimisable by unlinking item when if (node->data ==
> > inherit), but unfortunately there is no helper function for this
> > (because cil_list_item_destroy() does not unlink the item). What do
> > you think of adding a new helper function
> > cil_list_item_unlink_and_destroy(list, item, destroy_data) which would
> > provide a feature between cil_list_remove() and
> > cil_list_item_destroy()?
> >
> I don't know how you can get around walking the list twice. The first
> time through you need to find the node that is going to be removed by
> matching the node's data and the second time through the node is
> removed by matching the list item's data. Not all lists are lists of
> nodes, so the list functions can't search the data of something in the
> list. There are probably a lot of lists of nodes, so perhaps there
> could be a special function that searches the data of a list of nodes
> for a match, but I am not too worried about efficiency here.

I was thinking of something such as (in cil_destroy_blockinherit):

struct cil_list_item *previous = NULL;
cil_list_for_each(item, inherit->block->bi_nodes) {
  node = item->data;
  if (node->data == inherit) {
    if (previous == NULL) {
       inherit->block->bi_nodes->head = item->next;
    } else {
      previous->next = item->next;
    }
    if (item->next == NULL) {
      inherit->block->bi_nodes->tail = previous;
    }
    cil_list_item_destroy(&item, CIL_FALSE);
    break;
  }
  previous = item;
}

This code walks inherit->block->bi_nodes only once, but it would be
less maintainable because it relies on cil_list's implementation
details. So I was thinking of introducing a new helper function which
would implement the logic around "unlinking" in cil_list by using the
found "item".

> I don't understand what you are proposing with
> cil_list_item_unlink_and_destroy().

Nevermind. Thinking more about this, this could make the code more
complex. I will test and review your v2 patch. Thanks!

Nicolas

Re: [PATCH] libsepol/cil: Fix heap-use-after-free when using optional blockinherit

[James Carter]

On Mon, Feb 1, 2021 at 5:08 PM Nicolas Iooss <nicolas.iooss@m4x.org> wrote:
>
> On Mon, Feb 1, 2021 at 3:24 PM James Carter <jwcart2@gmail.com> wrote:
> >
> > This is based on a patch by Nicolas Iooss. He writes:
> >     When secilc compiles the following policy:
> >
> >         (block b1
> >             (optional o1
> >                 (blockinherit b1)
> >                 (blockinherit x)
> >             )
> >         )
> >
> >     it disables the optional block at pass 3 (CIL_PASS_BLKIN_LINK)
> >     because the block "x" does not exist.
> >     __cil_resolve_ast_last_child_helper() calls
> >     cil_tree_children_destroy() on the optional block, which destroys
> >     the two blockinherit statements. But the (blockinherit b1) node
> >     was referenced inside (block b1) node, in its block->bi_nodes list.
> >     Therefore, when this list is used at pass 4 (CIL_PASS_BLKIN_COPY),
> >     it contains a node which was freed: this triggers a use-after-free
> >     issue
> >
> >     Fix this issue by removing blockinherit nodes from their lists of
> >     nodes block->bi_nodes when they are being destroyed. As
> >     cil_destroy_blockinherit() does not have a reference to the node
> >     containing the blockinherit data, implement this new logic in
> >     cil_tree_node_destroy().
> >
> >     This issue was found while investigating a testcase from an OSS-Fuzz
> >     issue which seems unrelated (a Null-dereference READ in
> >     cil_symtab_get_datum,
> >     https://bugs.chromium.org/p/oss-fuzz/issues/detail?id=29861).
> >
> > Reported-by: Nicolas Iooss <nicolas.iooss@m4x.org>
> > Signed-off-by: James Carter <jwcart2@gmail.com>
> > ---
> >  libsepol/cil/src/cil_build_ast.c | 17 +++++++++++++++++
> >  1 file changed, 17 insertions(+)
> >
> > diff --git a/libsepol/cil/src/cil_build_ast.c b/libsepol/cil/src/cil_build_ast.c
> > index 02481558..3d8367fe 100644
> > --- a/libsepol/cil/src/cil_build_ast.c
> > +++ b/libsepol/cil/src/cil_build_ast.c
> > @@ -283,6 +283,23 @@ void cil_destroy_blockinherit(struct cil_blockinherit *inherit)
> >                 return;
> >         }
> >
> > +       if (inherit->block != NULL && inherit->block->bi_nodes != NULL) {
> > +               struct cil_tree_node *node;
> > +               struct cil_list_item *item;
> > +               int found = CIL_FALSE;
> > +
> > +               cil_list_for_each(item, inherit->block->bi_nodes) {
> > +                       node = item->data;
> > +                       if (node->data == inherit) {
> > +                               found = CIL_TRUE;
> > +                               break;
> > +                       }
> > +               }
> > +               if (found == CIL_TRUE) {
> > +                       cil_list_remove(inherit->block->bi_nodes, CIL_NODE, node, CIL_FALSE);
> > +               }
> > +       }
> > +
> >         free(inherit);
> >  }
>
> Hello,
> The code seems to be too complex for two reasons.
>
> First, doing "if (node->data == inherit) found = CIL_TRUE;" then "if
> (found == CIL_TRUE){...}" seems too verbose. The code could be
> simplified to something such as:
>
> if (inherit->block != NULL && inherit->block->bi_nodes != NULL) {
>   struct cil_list_item *item;
>
>   /* Find the in bi_nodes the item which contains the inherit object */
>   cil_list_for_each(item, inherit->block->bi_nodes) {
>     struct cil_tree_node *node = item->data;
>     if (node->data == inherit) {
>       cil_list_remove(inherit->block->bi_nodes, CIL_NODE, node, CIL_FALSE);
>       break;
>     }
>   }
> }
>

I sent a revised patch.

> Second, doing so makes the code browse the inherit->block->bi_nodes
> list twice (in cil_list_for_each and cil_list_remove). This seems to
> be easily optimisable by unlinking item when if (node->data ==
> inherit), but unfortunately there is no helper function for this
> (because cil_list_item_destroy() does not unlink the item). What do
> you think of adding a new helper function
> cil_list_item_unlink_and_destroy(list, item, destroy_data) which would
> provide a feature between cil_list_remove() and
> cil_list_item_destroy()?
>
I don't know how you can get around walking the list twice. The first
time through you need to find the node that is going to be removed by
matching the node's data and the second time through the node is
removed by matching the list item's data. Not all lists are lists of
nodes, so the list functions can't search the data of something in the
list. There are probably a lot of lists of nodes, so perhaps there
could be a special function that searches the data of a list of nodes
for a match, but I am not too worried about efficiency here.

I don't understand what you are proposing with
cil_list_item_unlink_and_destroy().

Thanks for the comments,
Jim


> By the way, while testing more the patch I sent, I found out that this
> introduces a use-after-free issue if inherit->block was freed. I
> encountered this issue with a simple CIL policy: "(block
> b2a)(blockinherit b2a)". I will send a patch for this, which performs
> the opposite operation in cil_destroy_block().
>
> Thanks,
> Nicolas
>

Re: [PATCH] libsepol/cil: Fix heap-use-after-free when using optional blockinherit

[Nicolas Iooss]

On Mon, Feb 1, 2021 at 3:24 PM James Carter <jwcart2@gmail.com> wrote:
>
> This is based on a patch by Nicolas Iooss. He writes:
>     When secilc compiles the following policy:
>
>         (block b1
>             (optional o1
>                 (blockinherit b1)
>                 (blockinherit x)
>             )
>         )
>
>     it disables the optional block at pass 3 (CIL_PASS_BLKIN_LINK)
>     because the block "x" does not exist.
>     __cil_resolve_ast_last_child_helper() calls
>     cil_tree_children_destroy() on the optional block, which destroys
>     the two blockinherit statements. But the (blockinherit b1) node
>     was referenced inside (block b1) node, in its block->bi_nodes list.
>     Therefore, when this list is used at pass 4 (CIL_PASS_BLKIN_COPY),
>     it contains a node which was freed: this triggers a use-after-free
>     issue
>
>     Fix this issue by removing blockinherit nodes from their lists of
>     nodes block->bi_nodes when they are being destroyed. As
>     cil_destroy_blockinherit() does not have a reference to the node
>     containing the blockinherit data, implement this new logic in
>     cil_tree_node_destroy().
>
>     This issue was found while investigating a testcase from an OSS-Fuzz
>     issue which seems unrelated (a Null-dereference READ in
>     cil_symtab_get_datum,
>     https://bugs.chromium.org/p/oss-fuzz/issues/detail?id=29861).
>
> Reported-by: Nicolas Iooss <nicolas.iooss@m4x.org>
> Signed-off-by: James Carter <jwcart2@gmail.com>
> ---
>  libsepol/cil/src/cil_build_ast.c | 17 +++++++++++++++++
>  1 file changed, 17 insertions(+)
>
> diff --git a/libsepol/cil/src/cil_build_ast.c b/libsepol/cil/src/cil_build_ast.c
> index 02481558..3d8367fe 100644
> --- a/libsepol/cil/src/cil_build_ast.c
> +++ b/libsepol/cil/src/cil_build_ast.c
> @@ -283,6 +283,23 @@ void cil_destroy_blockinherit(struct cil_blockinherit *inherit)
>                 return;
>         }
>
> +       if (inherit->block != NULL && inherit->block->bi_nodes != NULL) {
> +               struct cil_tree_node *node;
> +               struct cil_list_item *item;
> +               int found = CIL_FALSE;
> +
> +               cil_list_for_each(item, inherit->block->bi_nodes) {
> +                       node = item->data;
> +                       if (node->data == inherit) {
> +                               found = CIL_TRUE;
> +                               break;
> +                       }
> +               }
> +               if (found == CIL_TRUE) {
> +                       cil_list_remove(inherit->block->bi_nodes, CIL_NODE, node, CIL_FALSE);
> +               }
> +       }
> +
>         free(inherit);
>  }

Hello,
The code seems to be too complex for two reasons.

First, doing "if (node->data == inherit) found = CIL_TRUE;" then "if
(found == CIL_TRUE){...}" seems too verbose. The code could be
simplified to something such as:

if (inherit->block != NULL && inherit->block->bi_nodes != NULL) {
  struct cil_list_item *item;

  /* Find the in bi_nodes the item which contains the inherit object */
  cil_list_for_each(item, inherit->block->bi_nodes) {
    struct cil_tree_node *node = item->data;
    if (node->data == inherit) {
      cil_list_remove(inherit->block->bi_nodes, CIL_NODE, node, CIL_FALSE);
      break;
    }
  }
}

Second, doing so makes the code browse the inherit->block->bi_nodes
list twice (in cil_list_for_each and cil_list_remove). This seems to
be easily optimisable by unlinking item when if (node->data ==
inherit), but unfortunately there is no helper function for this
(because cil_list_item_destroy() does not unlink the item). What do
you think of adding a new helper function
cil_list_item_unlink_and_destroy(list, item, destroy_data) which would
provide a feature between cil_list_remove() and
cil_list_item_destroy()?

By the way, while testing more the patch I sent, I found out that this
introduces a use-after-free issue if inherit->block was freed. I
encountered this issue with a simple CIL policy: "(block
b2a)(blockinherit b2a)". I will send a patch for this, which performs
the opposite operation in cil_destroy_block().

Thanks,
Nicolas

[PATCH] libsepol/cil: Fix heap-use-after-free when using optional blockinherit

[James Carter]

This is based on a patch by Nicolas Iooss. He writes:
    When secilc compiles the following policy:

        (block b1
            (optional o1
                (blockinherit b1)
                (blockinherit x)
            )
        )

    it disables the optional block at pass 3 (CIL_PASS_BLKIN_LINK)
    because the block "x" does not exist.
    __cil_resolve_ast_last_child_helper() calls
    cil_tree_children_destroy() on the optional block, which destroys
    the two blockinherit statements. But the (blockinherit b1) node
    was referenced inside (block b1) node, in its block->bi_nodes list.
    Therefore, when this list is used at pass 4 (CIL_PASS_BLKIN_COPY),
    it contains a node which was freed: this triggers a use-after-free
    issue

    Fix this issue by removing blockinherit nodes from their lists of
    nodes block->bi_nodes when they are being destroyed. As
    cil_destroy_blockinherit() does not have a reference to the node
    containing the blockinherit data, implement this new logic in
    cil_tree_node_destroy().

    This issue was found while investigating a testcase from an OSS-Fuzz
    issue which seems unrelated (a Null-dereference READ in
    cil_symtab_get_datum,
    https://bugs.chromium.org/p/oss-fuzz/issues/detail?id=29861).

Reported-by: Nicolas Iooss <nicolas.iooss@m4x.org>
Signed-off-by: James Carter <jwcart2@gmail.com>
---
 libsepol/cil/src/cil_build_ast.c | 17 +++++++++++++++++
 1 file changed, 17 insertions(+)

diff --git a/libsepol/cil/src/cil_build_ast.c b/libsepol/cil/src/cil_build_ast.c
index 02481558..3d8367fe 100644
--- a/libsepol/cil/src/cil_build_ast.c
+++ b/libsepol/cil/src/cil_build_ast.c
@@ -283,6 +283,23 @@ void cil_destroy_blockinherit(struct cil_blockinherit *inherit)
 		return;
 	}
 
+	if (inherit->block != NULL && inherit->block->bi_nodes != NULL) {
+		struct cil_tree_node *node;
+		struct cil_list_item *item;
+		int found = CIL_FALSE;
+
+		cil_list_for_each(item, inherit->block->bi_nodes) {
+			node = item->data;
+			if (node->data == inherit) {
+				found = CIL_TRUE;
+				break;
+			}
+		}
+		if (found == CIL_TRUE) {
+			cil_list_remove(inherit->block->bi_nodes, CIL_NODE, node, CIL_FALSE);
+		}
+	}
+
 	free(inherit);
 }
 
-- 
2.26.2