Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

memory_buffer_alloc.c corner cases and fixes #639

Closed
guidovranken opened this issue Oct 5, 2016 · 3 comments
Closed

memory_buffer_alloc.c corner cases and fixes #639

guidovranken opened this issue Oct 5, 2016 · 3 comments
Labels

Comments

@guidovranken
Copy link
Contributor

This is memory_buffer_alloc.c (simplified, with all ifdefs removed) and some corner cases I identified and proposed fixes for them. This can be readily compiled and run (contains main). I think the code + comments speak for themselves.

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

/* Implementation that should never be optimized out by the compiler */
static void mbedtls_zeroize( void *v, size_t n ) {
    volatile unsigned char *p = v; while( n-- ) *p++ = 0;
}

#define mbedtls_exit   exit

#define MAGIC1       0xFF00AA55
#define MAGIC2       0xEE119966
#define MAX_BT 20

#define MBEDTLS_MEMORY_ALIGN_MULTIPLE       4 /**< Align on multiples of this value */
#define MBEDTLS_MEMORY_VERIFY_ALLOC        (1 << 0)
#define MBEDTLS_MEMORY_VERIFY_FREE         (1 << 1)

typedef struct _memory_header memory_header;
struct _memory_header
{
    size_t          magic1;
    size_t          size;
    size_t          alloc;
    memory_header   *prev;
    memory_header   *next;
    memory_header   *prev_free;
    memory_header   *next_free;
    size_t          magic2;
};

typedef struct
{
    unsigned char   *buf;
    size_t          len;
    memory_header   *first;
    memory_header   *first_free;
    int             verify;
}
buffer_alloc_ctx;

static buffer_alloc_ctx heap;

static int verify_header( memory_header *hdr )
{
    if( hdr->magic1 != MAGIC1 )
    {
        return( 1 );
    }

    if( hdr->magic2 != MAGIC2 )
    {
        return( 1 );
    }

    if( hdr->alloc > 1 )
    {
        return( 1 );
    }

    if( hdr->prev != NULL && hdr->prev == hdr->next )
    {
        return( 1 );
    }

    if( hdr->prev_free != NULL && hdr->prev_free == hdr->next_free )
    {
        return( 1 );
    }

    return( 0 );
}

static int verify_chain()
{
    memory_header *prv = heap.first, *cur = heap.first->next;

    if( verify_header( heap.first ) != 0 )
    {
        return( 1 );
    }

    if( heap.first->prev != NULL )
    {
        return( 1 );
    }

    while( cur != NULL )
    {
        if( verify_header( cur ) != 0 )
        {
            return( 1 );
        }

        if( cur->prev != prv )
        {
            return( 1 );
        }

        prv = cur;
        cur = cur->next;
    }

    return( 0 );
}

static void *buffer_alloc_calloc( size_t n, size_t size )
{
    memory_header *new, *cur = heap.first_free;
    unsigned char *p;
    void *ret;
    size_t original_len, len;

    if( heap.buf == NULL || heap.first == NULL )
        return( NULL );

    original_len = len = n * size;

#ifdef FIX
    /* man calloc:
     *
     *  The calloc() function allocates memory for an array of nmemb elements of size bytes each and returns a pointer to the allocated memory. 
     *  The memory is set to zero.  If nmemb or size is 0, then calloc() returns either NULL, or a unique pointer value that  can  later  be  
     *  successfully  passed  to free().
     *
     *  In other words, mbed TLS cannot rely on the libc calloc to return a valid pointer for calls which amount to nmemb*size = 0, so this
     *  calloc replacement doesn't have to either.
     *
     *  An argument for returning a small buffer for nmemb*size = 0 despite not having an obligation to do so is that this creates a "safety net" for
     *  code that (unjustly) depends on this.
     *
     *  An argument for returning NULL in this event is that zero-allocations won't consume unnecessary resources (buffer bytes)
     *
     *  But even if code depends on a small allocation for zero-allocations, it will either exit (due to allocation failure) or do a null pointer
     *  dereference which is generally understood to be harmless in normal client operations.
     *
     *  So I'm in favor of returning NULL here.
    */
    if( n == 0 || size == 0 || len / n != size )
        return( NULL );
#else
    if( n != 0 && len / n != size )
        return( NULL );
#endif

#ifdef FIX
    /* This fixes bug_1 */
    if ( len > (size_t)-4 )
    {
        return( NULL );
    }
#endif

    if( len % MBEDTLS_MEMORY_ALIGN_MULTIPLE )
    {
        len -= len % MBEDTLS_MEMORY_ALIGN_MULTIPLE;
        len += MBEDTLS_MEMORY_ALIGN_MULTIPLE;
    }

    // Find block that fits
    //
    while( cur != NULL )
    {
        if( cur->size >= len )
            break;

        cur = cur->next_free;
    }

    if( cur == NULL )
        return( NULL );

    if( cur->alloc != 0 )
    {
        mbedtls_exit( 1 );
    }

    // Found location, split block if > memory_header + 4 room left
    //
    if( cur->size - len < sizeof(memory_header) +
                          MBEDTLS_MEMORY_ALIGN_MULTIPLE )
    {
        cur->alloc = 1;

        // Remove from free_list
        //
        if( cur->prev_free != NULL )
            cur->prev_free->next_free = cur->next_free;
        else
            heap.first_free = cur->next_free;

        if( cur->next_free != NULL )
            cur->next_free->prev_free = cur->prev_free;

        cur->prev_free = NULL;
        cur->next_free = NULL;

        if( ( heap.verify & MBEDTLS_MEMORY_VERIFY_ALLOC ) && verify_chain() != 0 )
            mbedtls_exit( 1 );

        ret = (unsigned char *) cur + sizeof( memory_header );
        memset( ret, 0, original_len );

        return( ret );
    }

    p = ( (unsigned char *) cur ) + sizeof(memory_header) + len;
    new = (memory_header *) p;

    new->size = cur->size - len - sizeof(memory_header);
    new->alloc = 0;
    new->prev = cur;
    new->next = cur->next;
    new->magic1 = MAGIC1;
    new->magic2 = MAGIC2;

    if( new->next != NULL )
        new->next->prev = new;

    // Replace cur with new in free_list
    //
    new->prev_free = cur->prev_free;
    new->next_free = cur->next_free;
    if( new->prev_free != NULL )
        new->prev_free->next_free = new;
    else
        heap.first_free = new;

    if( new->next_free != NULL )
        new->next_free->prev_free = new;

    cur->alloc = 1;
    cur->size = len;
    cur->next = new;
    cur->prev_free = NULL;
    cur->next_free = NULL;

    if( ( heap.verify & MBEDTLS_MEMORY_VERIFY_ALLOC ) && verify_chain() != 0 )
        mbedtls_exit( 1 );

    ret = (unsigned char *) cur + sizeof( memory_header );
    memset( ret, 0, original_len );

    return( ret );
}

static void buffer_alloc_free( void *ptr )
{
    memory_header *hdr, *old = NULL;
    unsigned char *p = (unsigned char *) ptr;

    if( ptr == NULL || heap.buf == NULL || heap.first == NULL )
        return;

#ifdef FIX
    /* I believe that (void*)(heap.buf + heap.len) is the first OOB byte. */
    if( p < heap.buf || p >= heap.buf + heap.len )
#else
    if( p < heap.buf || p > heap.buf + heap.len )
#endif
    {
        mbedtls_exit( 1 );
    }

    p -= sizeof(memory_header);
    hdr = (memory_header *) p;

    if( verify_header( hdr ) != 0 )
        mbedtls_exit( 1 );

    if( hdr->alloc != 1 )
    {
        mbedtls_exit( 1 );
    }

    hdr->alloc = 0;

    // Regroup with block before
    //
    if( hdr->prev != NULL && hdr->prev->alloc == 0 )
    {
        hdr->prev->size += sizeof(memory_header) + hdr->size;
        hdr->prev->next = hdr->next;
        old = hdr;
        hdr = hdr->prev;

        if( hdr->next != NULL )
            hdr->next->prev = hdr;

        memset( old, 0, sizeof(memory_header) );
    }

    // Regroup with block after
    //
    if( hdr->next != NULL && hdr->next->alloc == 0 )
    {
        hdr->size += sizeof(memory_header) + hdr->next->size;
        old = hdr->next;
        hdr->next = hdr->next->next;

        if( hdr->prev_free != NULL || hdr->next_free != NULL )
        {
            if( hdr->prev_free != NULL )
                hdr->prev_free->next_free = hdr->next_free;
            else
                heap.first_free = hdr->next_free;

            if( hdr->next_free != NULL )
                hdr->next_free->prev_free = hdr->prev_free;
        }

        hdr->prev_free = old->prev_free;
        hdr->next_free = old->next_free;

        if( hdr->prev_free != NULL )
            hdr->prev_free->next_free = hdr;
        else
            heap.first_free = hdr;

        if( hdr->next_free != NULL )
            hdr->next_free->prev_free = hdr;

        if( hdr->next != NULL )
            hdr->next->prev = hdr;

        memset( old, 0, sizeof(memory_header) );
    }

    // Prepend to free_list if we have not merged
    // (Does not have to stay in same order as prev / next list)
    //
    if( old == NULL )
    {
        hdr->next_free = heap.first_free;
        if( heap.first_free != NULL )
            heap.first_free->prev_free = hdr;
        heap.first_free = hdr;
    }

    if( ( heap.verify & MBEDTLS_MEMORY_VERIFY_FREE ) && verify_chain() != 0 )
        mbedtls_exit( 1 );
}

void mbedtls_memory_buffer_set_verify( int verify )
{
    heap.verify = verify;
}

int mbedtls_memory_buffer_alloc_verify()
{
    return verify_chain();
}

void mbedtls_memory_buffer_alloc_init( unsigned char *buf, size_t len )
{
#ifdef FIX
    /* This fixes bug_2
     * Not only verify that there is enough room for memory header
     * but also for MBEDTLS_MEMORY_ALIGN_MULTIPLE in case 'buf'
     * isn't aligned.
    */
    if ( len < (sizeof(memory_header) + MBEDTLS_MEMORY_ALIGN_MULTIPLE) )
    {
        mbedtls_exit(1);
    }
#endif

    memset( &heap, 0, sizeof(buffer_alloc_ctx) );
    memset( buf, 0, len );

    //mbedtls_platform_set_calloc_free( buffer_alloc_calloc, buffer_alloc_free );

    if( (size_t) buf % MBEDTLS_MEMORY_ALIGN_MULTIPLE )
    {
        /* Adjust len first since buf is used in the computation */
        len -= MBEDTLS_MEMORY_ALIGN_MULTIPLE
             - (size_t) buf % MBEDTLS_MEMORY_ALIGN_MULTIPLE;
        buf += MBEDTLS_MEMORY_ALIGN_MULTIPLE
             - (size_t) buf % MBEDTLS_MEMORY_ALIGN_MULTIPLE;
    }

    heap.buf = buf;
    heap.len = len;

    heap.first = (memory_header *) buf;
    heap.first->size = len - sizeof(memory_header);
    heap.first->magic1 = MAGIC1;
    heap.first->magic2 = MAGIC2;
    heap.first_free = heap.first;
}

void mbedtls_memory_buffer_alloc_free()
{
    mbedtls_zeroize( &heap, sizeof(buffer_alloc_ctx) );
}

void bug_1(void)
{
    /* Memory corruption because sizeof(buf) < sizeof(memory_header) */
    char buf[1];
    mbedtls_memory_buffer_alloc_init(buf, sizeof(buf));
}

void bug_2(void)
{
    /* Underallocation due to this code causing 'size' to overflow:
     * (in buffer_alloc_calloc() )
     *
     * if( len % MBEDTLS_MEMORY_ALIGN_MULTIPLE )
     * {
     *   len -= len % MBEDTLS_MEMORY_ALIGN_MULTIPLE;
     *   len += MBEDTLS_MEMORY_ALIGN_MULTIPLE;
     * }
     *
     * So for a calloc(1, 0xFFFFFFFF) this is:
     *
     * len = 0xFFFFFFFF; // (on 32 bit)
     * if ( 3 )
     * {
     *   len -= 3;
     *   len += 4;
     * }
     *
     * len is now 0
    */
    char buf[100];
    mbedtls_memory_buffer_alloc_init(buf, sizeof(buf));
    buffer_alloc_calloc(1, (size_t)-1);
    /* or */
    buffer_alloc_calloc(1, (size_t)-2);
    /* or */
    buffer_alloc_calloc(1, (size_t)-3);
}

int main(void)
{
    bug_1();
    bug_2();
    return 0;
}
@ciarmcom
Copy link

ARM Internal Ref: IOTSSL-1033

@guidovranken
Copy link
Contributor Author

    if ( len > (size_t)-4 )

should be

    if ( len > (size_t)-MBEDTLS_MEMORY_ALIGN_MULTIPLE )

@gilles-peskine-arm
Copy link
Contributor

Hi Guido,

I believe that this issue has been fixed by the patches introduced by #778, which will be included in the next release, therefore I am closing this issue. Please let us know if there are more problems in memory_buffer_alloc.

Patater pushed a commit that referenced this issue Sep 6, 2019
Merge mbedtls-2.16 into mbedtls-2.16-restricted
iameli pushed a commit to livepeer/mbedtls that referenced this issue Dec 5, 2023

Verified

This commit was created on GitHub.com and signed with GitHub’s verified signature. The key has expired.
update change log
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
Projects
None yet
Development

No branches or pull requests

5 participants