Heap buffer overflow in stack function

Question

So i created a program that makes a stack and all of its operations, using a structure called stack.

Structure:

typedef struct {
        int *v;     /* contents of the stack */
        int cap;    /* capacity of v, i.e. how many elements can fit in v */
        int sz;     /* number of elements currently stored in v */
    } stack;

The program works fine but when i use fsantize it says that there is a buffer overflow on the heap in the Push function and i dont understand why because ive reallocated the bytes that i needed and freed the ones that i didnt need.

Program:

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

typedef struct {
        int *v;     /* contents of the stack */
        int cap;    /* capacity of v, i.e. how many elements can fit in v */
        int sz;     /* number of elements currently stored in v */
    } stack;

void init(stack * s)
{
    s->v = (int*) calloc(4,sizeof(int));
    s->cap = 4;
    s->sz = -1;
}

int is_empty(stack * s)
{
    if (s->sz == -1)
        return 1;
    else
        return 0;
}

void push(stack * s, int e)
{
    if (s->sz+1 <= s->cap)
    {
        s->sz++;
        s->v[s->sz] = e;
    }
    else
    {
        int *nv;
        s->cap++;
        s->sz++;
        nv = (int*) realloc(s->v, sizeof(int)*s->cap);
        free(s->v);
        s->v = nv;
        s->v[s->sz] = e;
    }
}

int pop(stack * s)
{
    if (is_empty(s) == 0)
    {
        int top = s->v[s->sz];
        s->sz--;
        return top;
    }
    else
    {
        printf("Impossible the stack isn't empty\n");
        return 0;
    }

}

void destroy(stack * s)
{
    //frees the stack bytes that were allocated
    free(s->v);
    free(s);
}

int main()
{
    int i;
    stack *pilha = (stack*) malloc(sizeof(stack));
    init(pilha);
    if (is_empty(pilha) == 1)
        printf("The stack is empty\n");
    pop(pilha);
    for (i = 0; i<=4;i++)
        push(pilha,i);
    push(pilha,5);
    printf("The top is:%d\n",pilha->v[pilha->sz]);
    if (is_empty(pilha) == 0)
        printf("The stack isn't empty\n");
    destroy(pilha);
    return 0;
}

Marco Bonelli · Accepted Answer · 2020-05-05T21:37:40.757

This line:

if (s->sz+1 <= s->cap)

contains a logical error: if s->sz+1 == s->cap you need more space. For example, if s->cap is 4 you only have space for 4 elements (indexes from 0 to 3), but in the case of s->sz == 3 you enter the if and the result is:

s->sz++;         // 4
s->v[s->sz] = e; // s->v[4] overflow!

The right way to check would be if (s->sz+1 < s->cap), or even incrementing the value first:

s->sz++;

if (s->sz < s->cap) {
    // ...

This:

nv = (int*) realloc(s->v, sizeof(int)*s->cap);
free(s->v);
s->v = nv;

Is also wrong. First, you are assuming that realloc() allocates new memory and that you need to free() the old buffer: you don't, realloc() does that for you if needed. Secondly, you are assuming that realloc() does not fail (as you are doing anywhere else in your code, malloc(), calloc(), etc). Third, you are casting the return value (again as you are doing anywhere else in your code), which you shouldn't (see Do I cast the result of malloc?).

What you should do instead is:

nv = realloc(s->v, sizeof(int)*s->cap);
if (nv == NULL) {
    // Handle error, abort execution.
}

s->v = nv;

The check if (nv == NULL) should be done after every single call of malloc(), realloc() or calloc().

I did what u told me i think and retyped push to this ```void push(stack * s, int e) { s->sz++; if (s->sz < s->cap) { s->v[s->sz] = e; } else { int *nv; s->cap++; s->sz++; nv = realloc(s->v, sizeof(int)*s->cap); if (nv == NULL) {} s->v = nv; s->v[s->sz] = e; } }``` and it still giving a buffer overflow so if u could write the modified version i would appreciate it a lot because im still not understanding what my error is — Martim Correia, May 05 '20 at 22:27
@MartimCorreia you are incrementing `s->sz` two times in the second case, remove `s->sz++` from inside the `else`. — Marco Bonelli, May 05 '20 at 22:32
yeah i just did that and i only understood what u meant while i was trying to sleep, thanks man — Martim Correia, May 06 '20 at 10:08

Vlad from Moscow · Answer 2 · 2020-05-05T22:16:31.887

The function push is invalid.

This condition in the if statement

if (s->sz+1 <= s->cap)

can be a reason of undefined behavior. Let's assume for simplicity that s->cap is equal to 1. So you may push only one element without resizing the dynamically allocated array. So after pushing a new value s->sz will be equal to 0. And you may not push one more a new value without resizing the array. However the condition in the if statement will evaluate to true and you will write to memory outside the allocated array.

Also this code snippet

    nv = (int*) realloc(s->v, sizeof(int)*s->cap);
    free(s->v);

is invalid. In the case when the call of realloc was successful the memory pointed to by s->v was freed (or rreused). So the call of free again will invoke undefined behavior. That is whether there will be an attempt to free the already reallocated memory or the new allocated memory will be freed.

The function push can be defined for example the following way

int push( stack *s, int e )
{
    int success = 0;

    if ( ( success = s->sz+1 < s->cap ) )
    {
        s->v[++s->sz] = e;
    }
    else
    {
        int *nv = realloc( s->v, sizeof( int ) * ( s->cap + 1 ) );
        success = nv != NULL;

        if ( success )
        {
            s->v = nv;
            ++s->cap;
            s->v[++s->sz] = e;
        }
    }

    return success;
}

But in any case it would be better to set the initial value to the data member sz to 0. In this case the data member would reflect the current size of the stack.

The return value of the function pop is ambiguous. The returned value 0 can be a valid value stored in the stack. Also the function shall shall not issue any message. It is the caller of the function that will decide whether to issue a message if any or not.

Also there is no need to allocate the object itself of the type stack dynamically. It can have the automatic storage duration and be a local variable.

And it is much better when the function that initialize the stack also has a second parameter that allows to specify the capacity of the created stack instead of using the magic number 4.

Below there is a demonstrative program that shows how the stack and its functions can be defined.

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

typedef struct 
{
    int *v;     /* contents of the stack */
    size_t cap;    /* capacity of v, i.e. how many elements can fit in v */
    size_t sz;     /* number of elements currently stored in v */
} stack;

int init( stack * s, size_t capacity )
{
    s->sz  = 0;
    s->cap = 0;

    s->v = calloc( capacity, sizeof( int ) );

    int success = s->v != NULL; 

    if ( success )
    {
        s->cap = capacity;;
    }       

    return success;
}

int is_empty( const stack *s )
{
    return s->sz == 0;
}

int push( stack *s, int e )
{
    int success = 0;

    if ( ( success = s->sz < s->cap ) )
    {
        s->v[s->sz++] = e;
    }
    else
    {
        int *nv = realloc( s->v, sizeof( int ) * ( s->cap + 1 ) );
        success = nv != NULL;

        if ( success )
        {
            s->v = nv;
            ++s->cap;
            s->v[s->sz++] = e;
        }
    }

    return success;
}

int pop( stack *s, int *value )
{
    int success = !is_empty( s );

    if ( success )
    {
        *value = s->v[--s->sz];
    }

    return success;
}

void destroy( stack *s )
{
    free( s->v );
    s->v = NULL;
    s->cap = 0;
    s->sz = 0;
}

int main( void )
{
    stack pilha;
    init( &pilha, 4 );

    if ( is_empty( &pilha ) )
    {
        printf( "The stack is empty\n" );
    }        

    const int N = 5;

    for ( int i = 0; i < 5; i++ )
    {
        push( &pilha, i );
    }

    push( &pilha, N );

    while ( ! is_empty( &pilha ) )
    {
        int value;
        pop( &pilha, &value );
        printf( "the current top value is %d\n", value );
    }

    destroy( &pilha );

    if ( is_empty( &pilha ) )
    {
        printf("The stack isn't empty\n");
    }

    return 0;
}

The program output is

The stack is empty
the current top value is 5
the current top value is 4
the current top value is 3
the current top value is 2
the current top value is 1
the current top value is 0
The stack isn't empty

It isn't really the condition in the `if` statement that invokes undefined behavior. — Marco Bonelli, May 05 '20 at 21:36
@MarcoBonelli The wrong condition is the reason of the invoked undefined behavior. — Vlad from Moscow, May 05 '20 at 21:39

Heap buffer overflow in stack function

2 Answers2