[prev in list] [next in list] [prev in thread] [next in thread] 

List:       busybox
Subject:    Re: [PATCH] tsort: avoid use-after-free
From:       Denys Vlasenko <vda.linux () googlemail ! com>
Date:       2023-08-31 7:48:14
Message-ID: CAK1hOcO3BZ=38C-B57pTrdkpuFwcPRRtdaJp+TG6_hsn0f4nUQ () mail ! gmail ! com
[Download RAW message or body]

Applied, thank you.

On Tue, Aug 22, 2023 at 10:38 AM Ron Yorston <rmy@pobox.com> wrote:
>
> When the input data contained a cycle it was possible for tsort to
> attempt to access freed nodes.  This sometimes resulted in the
> test case 'echo a b b a | tsort' crashing.
>
> Don't free nodes when they're removed from the graph.
>
> function                                             old     new   delta
> tsort_main                                           621     596     -25
> ------------------------------------------------------------------------------
> (add/remove: 0/0 grow/shrink: 0/1 up/down: 0/-25)             Total: -25 bytes
>
> Signed-off-by: Ron Yorston <rmy@pobox.com>
> ---
>  coreutils/tsort.c | 20 +++++++++++++++++---
>  1 file changed, 17 insertions(+), 3 deletions(-)
>
> diff --git a/coreutils/tsort.c b/coreutils/tsort.c
> index a451ed2ff..3e7aa48f4 100644
> --- a/coreutils/tsort.c
> +++ b/coreutils/tsort.c
> @@ -101,6 +101,10 @@ int tsort_main(int argc UNUSED_PARAM, char **argv)
>         ssize_t len;
>         struct node *a;
>         int cycles;
> +       unsigned i;
> +#if ENABLE_FEATURE_CLEAN_UP
> +       unsigned max_len;
> +#endif
>
>         INIT_G();
>
> @@ -152,9 +156,11 @@ int tsort_main(int argc UNUSED_PARAM, char **argv)
>          *   - if any nodes are left, they form cycles.
>          */
>         cycles = 0;
> +#if ENABLE_FEATURE_CLEAN_UP
> +       max_len = G.nodes_len;
> +#endif
>         while (G.nodes_len) {
>                 struct node *n;
> -               unsigned i;
>
>                 /* Search for first node with no incoming edges */
>                 for (i = 0; i < G.nodes_len; i++) {
> @@ -173,16 +179,24 @@ int tsort_main(int argc UNUSED_PARAM, char **argv)
>                 /* Remove the node (need no longer maintain sort) */
>                 n = G.nodes[i];
>                 G.nodes[i] = G.nodes[--G.nodes_len];
> +#if ENABLE_FEATURE_CLEAN_UP
> +               /* Keep reference to removed node so it can be freed */
> +               G.nodes[G.nodes_len] = n;
> +#endif
>
>                 /* And remove its outgoing edges */
>                 for (i = 0; i < n->out_count; i++)
>                         n->out[i]->in_count--;
> -               free(n->out);
>
>                 puts(n->name);
> -               free(n);
> +       }
> +#if ENABLE_FEATURE_CLEAN_UP
> +       for (i = 0; i < max_len; i++)
> +               free(G.nodes[i].out);
> +               free(G.nodes[i]);
>         }
>         free(G.nodes);
> +#endif
>
>         fflush_stdout_and_exit(cycles ? 1 : 0);
>  }
> --
> 2.41.0
>
> _______________________________________________
> busybox mailing list
> busybox@busybox.net
> http://lists.busybox.net/mailman/listinfo/busybox
_______________________________________________
busybox mailing list
busybox@busybox.net
http://lists.busybox.net/mailman/listinfo/busybox

[prev in list] [next in list] [prev in thread] [next in thread]