PQueue heap-overflow - Githubissues

I've detected a heap-overflow bug in the following snipped of code:

enum cc_stat cc_pqueue_push(CC_PQueue *pq, void *element)
{
    size_t i = pq->size; // size_t is unsigned
    ... 
    while (i != 0 && pq->cmp(child, parent) > 0) {
        void *tmp = pq->buffer[i];
        pq->buffer[i] = pq->buffer[CC_PARENT(i)];
        pq->buffer[CC_PARENT(i)] = tmp;

        i      = CC_PARENT(i);
        child  = pq->buffer[i];
        parent = pq->buffer[CC_PARENT(i)]; // <-- here (i - 1) / 2 will overflow because i is unsigned
    }
    return CC_OK;
}

The problem occurs in the last iteration of the while loop, when computing the new value of the variable parent, which would be in the index (0-1)/2 in pq->buffer. However, since i is declared to be of type size_t (unsigned int), the evaluation of (0-1)/2 will trigger an integer overflow, and subsequently lead to a heap overflow. Even though this bug is harmless, it results in unspecified behaviour, potentially causing portability problems. A possible fix would be to add an explicit check for 0 to the macro of CC_PARENT. Replacing the current statement for:

#define CC_PARENT(i) ((i > 0) ? (i-1)/2 : 0)

I used a the following test case to trigger the bug:

static int comp2(const void *a, const void *b)
{
    return *((int *)a) - *((int *)b);
}

static CC_PQueue *p1;

int main()
{
    int e = 1001, f = 1000;
    int *ptr;

    cc_pqueue_new(&p1, comp2);

    cc_pqueue_push(p1, (void *) &f);
    cc_pqueue_push(p1, (void *) &e);

    cc_pqueue_destroy(p1);
}

I compiled it with AddressSanitizer (-fsanitize=address), for both 32-bit and 64-bit targets (-m32 and -m64), which reported the following:

=================================================================
==94691==ERROR: AddressSanitizer: heap-buffer-overflow on address 0xf4f00b4c at pc 0x56621445 bp 0xffc62908 sp 0xffc628f8
READ of size 4 at 0xf4f00b4c thread T0
    #0 0x56621444 in cc_pqueue_push /home/filipe/documents/uni/thesis/Collections-C/src/cc_pqueue.c:245
    #1 0x56621ec5 in main /home/filipe/documents/uni/thesis/Collections-C/src/cc_pqueue.c:352
    #2 0xf77b3a0c in __libc_start_main (/usr/lib32/libc.so.6+0x1ea0c)
    #3 0x56620124 in _start (/home/filipe/documents/uni/thesis/Collections-C/src/a.out+0x1124)

0xf4f00b4c is located 4 bytes to the left of 32-byte region [0xf4f00b50,0xf4f00b70)
allocated by thread T0 here:
    #0 0xf7a465c5 in __interceptor_malloc /build/gcc/src/gcc/libsanitizer/asan/asan_malloc_linux.cpp:145
    #1 0x56620708 in cc_pqueue_new_conf /home/filipe/documents/uni/thesis/Collections-C/src/cc_pqueue.c:122
    #2 0x566204a0 in cc_pqueue_new /home/filipe/documents/uni/thesis/Collections-C/src/cc_pqueue.c:81
    #3 0x56621e71 in main /home/filipe/documents/uni/thesis/Collections-C/src/cc_pqueue.c:347
    #4 0xf77b3a0c in __libc_start_main (/usr/lib32/libc.so.6+0x1ea0c)

SUMMARY: AddressSanitizer: heap-buffer-overflow /home/filipe/documents/uni/thesis/Collections-C/src/cc_pqueue.c:245 in cc_pqueue_push
Shadow bytes around the buggy address:
  0x3e9e0110: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x3e9e0120: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x3e9e0130: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x3e9e0140: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x3e9e0150: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
=>0x3e9e0160: fa fa fa fa fa fa fa fa fa[fa]00 00 00 00 fa fa
  0x3e9e0170: 00 00 00 00 fa fa fa fa fa fa fa fa fa fa fa fa
  0x3e9e0180: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x3e9e0190: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x3e9e01a0: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x3e9e01b0: 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
  Shadow gap:              cc
==94691==ABORTING

srdja / Collections-C

PQueue heap-overflow #147