堆栈函数中的堆缓冲区溢出

Question

所以我创建了一个程序，它使用称为堆栈的结构来生成堆栈及其所有操作。

结构：

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;

程序运行良好，但是当我使用 fsantize 时，它说 Push 函数中的堆上存在缓冲区溢出，我不明白为什么，因为我重新分配了我需要的字节并释放了这些字节我不需要。

计划：

#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;
}

Answer 1

函数push无效。

if语句中的这个条件

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

可能是未定义行为的原因。为简单起见，我们假设 s->cap 等于 1。因此，您可以只压入一个元素而无需调整动态分配的数组的大小。因此在推送新值后 s->sz 将等于 0。并且您可能不会在不调整数组大小的情况下再推一个新值。但是，if 语句中的条件将计算为真，您将写入分配数组之外的内存。

还有这段代码

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

无效。在调用 realloc 成功的情况下，s->v 指向的内存被释放（或重新使用）。因此再次调用 free 将调用未定义的行为。也就是说，是否会尝试释放已经重新分配的内存，或者是否会释放新分配的内存。

函数push可以这样定义，例如

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;
}

但无论如何，最好将数据成员sz的初始值设置为0。在这种情况下，数据成员将反映堆栈的当前大小。

函数 pop 的 return 值不明确。 returned 值 0 可以是存储在堆栈中的有效值。此外，该功能不得发出任何消息。函数的调用者将决定是否发出消息（如果有）。

也不需要动态分配stack类型的对象本身。可以有自动存储时间，可以是局部变量。

当初始化堆栈的函数还有第二个参数允许指定创建堆栈的容量而不是使用幻数 4.

时会好得多

下面有一个演示程序，展示了如何定义堆栈及其函数。

#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 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

Answer 2

这一行：

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

包含逻辑错误：如果 s->sz+1 == s->cap 您需要更多 space。例如，如果 s->cap 是 4，则 4 元素（从 0 到 3 的索引）只有 space，但在这种情况下s->sz == 3 你输入 if 结果是：

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

正确的检查方法是 if (s->sz+1 < s->cap)，或者甚至先增加值：

s->sz++;

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

这个：

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

也是错误的。首先，您假设 realloc() 分配了新内存并且您需要 free() 旧缓冲区：您不需要，如果需要，realloc() 会为您完成。其次，您假设 realloc() 不会失败（就像您在代码中的其他任何地方所做的那样，malloc()、calloc() 等）。第三，您正在强制转换 return 值（再次在代码中的其他任何地方执行），您不应该这样做（请参阅 Do I cast the result of malloc?）。

你应该做的是：

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

s->v = nv;

检查 if (nv == NULL) 应该在每次调用 malloc()、realloc() 或 calloc() 后进行。

堆栈函数中的堆缓冲区溢出

Heap buffer overflow in stack function

c

struct

stack

dynamic-memory-allocation

function-definition