realloc() use-after-free address sanitizer issue with recursion

Question

I wrote a small program to in-order traverse a binary tree, I wanted to practice realloc and wrote the following code to dynamically fill an array with the elements of a binary search tree:

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
};
 
void inorder(struct TreeNode *root, int *inorder_arr, int *size) {
    if (root) {
        inorder(root->left, inorder_arr, size);
        inorder_arr[(*size)-1] = root->val;
        (*size)++;
        inorder_arr = (int *)realloc(inorder_arr, (*size) * sizeof(int));
        inorder(root->right, inorder_arr, size);
    }
}

bool findTarget(struct TreeNode *root, int k) {
    if (!root) return false;
    int size =1;
    
    int *inorder_arr = (int *)malloc(sizeof(int));
    inorder(root, inorder_arr, &size);
    return false;
}

int main () {
    // this is for creating a binary search tree which its inorder traversal looks like this : 2,3,4,5,6,7
    struct TreeNode *root = (struct TreeNode *)malloc(sizeof(struct TreeNode));
    root->val = 5;
    root->left = (struct TreeNode *)calloc(1, sizeof(struct TreeNode));
    root->left->val = 3;
    root->right = (struct TreeNode *)calloc(1, sizeof(struct TreeNode));
    root->right->val = 6;
    root->right->right = (struct TreeNode *)calloc(1, sizeof(struct TreeNode));
    root->right->right->val = 7;
    root->left->right = (struct TreeNode *)calloc(1, sizeof(struct TreeNode));
    root->left->right->val = 4;
    root->left->left = (struct TreeNode *)calloc(1, sizeof(struct TreeNode));
    root->left->left->val = 2;
    printf("%d", FindTarget(root, 9));
}

~please neglect the fact that my function FindTarget will always return false, this is not the full purpose of this program, and not the purpose of my question.

also it might be useful to note that my binary search tree looks like this: binary search tree.png

~My program seems to work but I have a big issue when compiling it with address sanitizer using:

gcc -ggdb 2_sum_bst.c -fsanitize=address

when I run my program "a.out" I get the following error:

=================================================================
==13399==ERROR: AddressSanitizer: heap-use-after-free on address 0x602000000014 at pc 0x55c7a8ef5d77 bp 0x7ffebafbf0c0 sp 0x7ffebafbf0b0
WRITE of size 4 at 0x602000000014 thread T0
    #0 0x55c7a8ef5d76 in inorder /home/yarin/my_dev/C_C++_learning/basics/2_sum_bst.c:15
    #1 0x55c7a8ef5cb8 in inorder /home/yarin/my_dev/C_C++_learning/basics/2_sum_bst.c:14
    #2 0x55c7a8ef5ef3 in findTarget /home/yarin/my_dev/C_C++_learning/basics/2_sum_bst.c:28
    #3 0x55c7a8ef628b in main /home/yarin/my_dev/C_C++_learning/basics/2_sum_bst.c:45
    #4 0x7f1186741b96 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x21b96)
    #5 0x55c7a8ef5b79 in _start (/home/yarin/my_dev/C_C++_learning/basics/a.out+0xb79)

0x602000000014 is located 0 bytes to the right of 4-byte region [0x602000000010,0x602000000014)
freed by thread T0 here:
    #0 0x7f1186beff30 in realloc (/usr/lib/x86_64-linux-gnu/libasan.so.4+0xdef30)
    #1 0x55c7a8ef5da6 in inorder /home/yarin/my_dev/C_C++_learning/basics/2_sum_bst.c:17
    #2 0x55c7a8ef5cb8 in inorder /home/yarin/my_dev/C_C++_learning/basics/2_sum_bst.c:14
    #3 0x55c7a8ef5cb8 in inorder /home/yarin/my_dev/C_C++_learning/basics/2_sum_bst.c:14
    #4 0x55c7a8ef5ef3 in findTarget /home/yarin/my_dev/C_C++_learning/basics/2_sum_bst.c:28
    #5 0x55c7a8ef628b in main /home/yarin/my_dev/C_C++_learning/basics/2_sum_bst.c:45
    #6 0x7f1186741b96 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x21b96)

previously allocated by thread T0 here:
    #0 0x7f1186befb40 in __interceptor_malloc (/usr/lib/x86_64-linux-gnu/libasan.so.4+0xdeb40)
    #1 0x55c7a8ef5ecf in findTarget /home/yarin/my_dev/C_C++_learning/basics/2_sum_bst.c:27
    #2 0x55c7a8ef628b in main /home/yarin/my_dev/C_C++_learning/basics/2_sum_bst.c:45
    #3 0x7f1186741b96 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x21b96)

SUMMARY: AddressSanitizer: heap-use-after-free /home/yarin/my_dev/C_C++_learning/basics/2_sum_bst.c:15 in inorder
Shadow bytes around the buggy address:
  0x0c047fff7fb0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x0c047fff7fc0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x0c047fff7fd0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x0c047fff7fe0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x0c047fff7ff0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
=>0x0c047fff8000: fa fa[fd]fa fa fa 00 fa fa fa fa fa fa fa fa fa
  0x0c047fff8010: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0c047fff8020: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0c047fff8030: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0c047fff8040: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0c047fff8050: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
Shadow byte legend (one shadow byte represents 8 application bytes):
  Addressable:           00
  Partially addressable: 01 02 03 04 05 06 07 
  Heap left redzone:       fa
  Freed heap region:       fd
  Stack left redzone:      f1
  Stack mid redzone:       f2
  Stack right redzone:     f3
  Stack after return:      f5
  Stack use after scope:   f8
  Global redzone:          f9
  Global init order:       f6
  Poisoned by user:        f7
  Container overflow:      fc
  Array cookie:            ac
  Intra object redzone:    bb
  ASan internal:           fe
  Left alloca redzone:     ca
  Right alloca redzone:    cb
==13399==ABORTING

~ as we can see I got heap-use-after-free and i got curious and started to debug the program

~ I started to debug the program and realized my mistake, when my function "inorder" is doing its recursive calls when it starts to backtrack the pointer that points to my array at each call in the call stack is unique to that specific call , but I used realloc and realloc frees the memory and allocates new memory and returns the pointer to that pointer in that call and not to all pointers in the call stack, running this issue which is little complicated I thought how could I do a workaround this issue without using a global pointer, I thought about using static pointer but that also did not work..

as of now I can't think how can I possibly work around this issue without using a global pointer, I would like to hear suggestions since I am a beginner to C Programming and want to know the best solution to such case without using a global pointer or without traversing the whole tree getting its size and then using malloc to get enough memory for all the nodes, as you can see my purpose here is to do it as my program Traverses the tree.

thank you in advance for reading and helping!

In the findTarget function, you pass the address of size to the inorder function. You should also pass the address of inorder_arr, so that every level of recursion is using the same pointer. That means the inorder_arr parameter in the declaration of the inorder function needs to be a pointer to a pointer, i.e. int **inorder_arr. — user3386109
Pointer Basic: Passing a pointer as a value parameter to a function any direct assignment to said pointer means nothing to the caller, which still retains the original pointer value. E.g: foo(Type *p) , and within the foo you p = <<soemthing>>; means nothing to the caller; they still have the value originally passed in. That is normally a recipe for a memory leak and subtle bugs. In your case its even worse, as realloc is involved. The caller still has their original pointer but realloc has reclaimed the memory to which it refers. A pointer to pointer is your answer. — WhozCraig

prog-fh prog-fh · Accepted Answer · 2020-08-29T22:02:28

As clearly stated in the comments of the question, the main problem is due to the fact that, in the inorder() function of the posted code, the original counter (size in findTarget()) is actually updated but the original pointer to the beginning of the dynamically allocated storage (inorder_arr in findTarget()) is not.

The code below is intended to reproduce the same problem in a much simpler context (simply append an integer, without any recursion).

The extend_dyn_array_bad() function is similar to the inorder() function because its parameters give it the ability to alter the counter but not the pointer to the beginning of the dynamically allocated storage.

On the other hand, the extend_dyn_array() function receives the pointer parameter by address in the same manner as the counter parameter :

an int, in order to be passed by address to a function that may alter it, needs an int * parameter,
an int *, in order to be passed by address to a function that may alter it, needs an int ** parameter. (we simply add a * to the type as it is in its original context).

Dealing with multiple levels of indirection on a single variable is not really easy to read, that's why I suggest getting rid of this extra level of indirection as soon as possible when entering the function, then perform all the actual work on these local variables, and when it's done alter the original parameters thanks to this extra level of indirection (see the three commented steps in the extend_dyn_array() function.

Note also that the findTarget() function of the question relies on the dynamic allocation of an array which is never released (free()).

/**
  gcc -std=c99 -o prog_c prog_c.c \
      -pedantic -Wall -Wextra -Wconversion \
      -Wwrite-strings -Wold-style-definition -Wvla \
      -g -O0 -UNDEBUG -fsanitize=address,undefined
**/

#include <stdio.h>
#include <stdlib.h>

void
extend_dyn_array_bad(int *values,
                     int *count)
{
  ++(*count);
  values=realloc(values, sizeof(*values)*(size_t)(*count));
  if(values==NULL)
  {
    abort();
  }
  // after realloc, values may point to a different address
  // which is known and usable by this function but that
  // is not know by the v variable in main().
  values[*count-1]=*count; // initialise last element
}

void
extend_dyn_array(int **inout_values,
                 int *inout_count)
{
  //-- load inout-parameters --
  int *values=*inout_values;
  int count=*inout_count;
  //-- perform actual work --
  ++count;
  values=realloc(values, sizeof(*values)*(size_t)count);
  if(values==NULL)
  {
    abort();
  }
  values[count-1]=count; // initialise last element
  //-- store out-parameters --
  *inout_values=values;
  *inout_count=count;
}

int
main(void)
{
  int *v=NULL;
  int n=0;
  for(int i=0; i<10000; ++i)
  {
    extend_dyn_array(&v, &n); // both v and n may be altered
    // extend_dyn_array_bad(v, &n); // only n may be altered
  }
  for(int i=0;   i<5; ++i) { printf("%d ", v[i]); } printf("... ");
  for(int i=n-5; i<n; ++i) { printf("%d ", v[i]); } printf("\n");
  free(v);
  return 0;
}

realloc() use-after-free address sanitizer issue with recursion

1 Answers