From 2cc9d436e80632157b99e18d413a62b2d44d321a Mon Sep 17 00:00:00 2001 From: Ron Yorston Date: Tue, 22 Aug 2023 09:38:03 +0100 Subject: tsort: avoid use-after-free 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 Signed-off-by: Denys Vlasenko --- coreutils/tsort.c | 20 +++++++++++++++++--- 1 file changed, 17 insertions(+), 3 deletions(-) diff --git a/coreutils/tsort.c b/coreutils/tsort.c index a451ed2ff..e1ee6bcd7 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); } -- cgit v1.2.3