Writing heapify function from scratch, getting a "stack-based buffer overrun"

Question

I am trying to implement the heap sort algorithm for the first time, but I am getting an error with the heapify function.

Unhandled exception at 0x0005369A in heapify.exe: Stack cookie instrumentation code detected a stack-based buffer overrun.

The console does open, and the output is 999 10 5 11 1012398875 2 0 1.

Could someone help me understand what is going wrong here? Thank you.

#include <iostream>

// given the address of element 0 of an array, and a non-zero index k, heapify assumes that the L/R subtrees
// of node k are max heaps. But the subtrees combined with node k do not necesarily form 
// a max heap. heapify interchanges the value at node k with the value of one of its children,
// and then calls itself on the subtree in question 
int heapify(int* n, int k, int sizeOfHeap)
{
    // terminate the function if the input "node" is not actually a node
    if (k > sizeOfHeap)
    {
        return 0;
    }
        int root = *(n + k); // value of kth node
        int leftChild = *(n + 2 * k); // value of left chold
        int rightChild = *(n + 2 * k + 1); // value of right child
        if (root < leftChild)
        {
            // swap value of kth node with value of its left child
            int temp = root;
            *(n + k) = leftChild;
            *(n + 2 * k) = root;

            // call heapify on the left child
            heapify(n, 2 * k, sizeOfHeap);
        }
        else
        {
            // swap value of kth node with value of its right child
            int temp = root;
            *(n + k) = rightChild;
            *(n + 2 * k + 1) = root;

            // call heapify on right child
            heapify(n, 2 * k + 1, sizeOfHeap);
        }
    
}

int main()
{
    // arr is the array we will heapify. 999 is just a placeholder. 
    // The actual (almost) heap occupies indices 1 - 7
    int arr[8] = {999, 3, 10, 11, 5, 2, 0, 1};
    int sizeOfHeap = 8;
    
    heapify(arr, 1, sizeOfHeap);

    // print out arr
    int i;
    for (i = 0; i <= 7; i++)
    {
        std::cout << arr[i] << std::endl;
    }
}

In `*(n + 2 * k)` you are not checking if `2 * k` is larger than `sizeOfHeap`, and possibly accessing the array out of bounds. — NathanOliver, Jul 12 '21 at 19:39
@NathanOliver Thanks, that fixed the error! As humans we know that the element with address `n + 2 * k` might not be in the original array, but to the computer, `n + 2 * k` is just an address with some junk. Why does it throw an error instead of retrieving that junk and running with it? — Ovi, Jul 12 '21 at 19:50
@mattlangford I think its `>`, because in the main function the heap starts at index `1`, not at index `0`. The `999` value is just a placeholder. — Ovi, Jul 12 '21 at 19:51
Accessing an array out of bounds is undefined behavior. You get whatever the compiler decides to give you, sometimes, oftentimes, getting the result you expected, which makes it really dangerous. — NathanOliver, Jul 12 '21 at 19:52
Oh I made a mistake, `sizeOfHeap` should be `7` instead of `8`. — Ovi, Jul 12 '21 at 19:54
If you check one bit of pointer arithmetic to ensure that it is within bounds, you pretty much have to check them all, and this extra testing would slow down the program noticeably. To maintain the speed people expect of C++ programs, typically the only checking performed is the checking the programmer asks for with a function that performs the appropriate checks or writes themselves. With great speed comes great responsibility. — user4581301, Jul 12 '21 at 20:03

badasz · Accepted Answer · 2021-07-13T17:17:23.043

Unhandled exception at 0x0005369A in heapify.exe: Stack cookie instrumentation code detected a stack-based buffer overrun.

The console does open, and the output is 999 10 5 11 1012398875 2 0 1.

Could someone help me understand what is going wrong here? Thank you.

Stack of process (one of real-live uses of stack data structure, FILO queue) is the place in memory for static allocation. Always small and mostly same size for all processes. On stack, still, compiler save local variables i.e. small statically allocated buffers (this happens then the stack pointer is, on Linux, moved to expand the stack size, and compiler evaluate offsets on stack). They (buffers) could not be handled correctly (unsafe lib functions, like strcpy()) so they could be potentially overflowed (overrunned) leading to buffer overflow vulnerability.

Stack cookie AKA stack canary is mitigation technique for writing sequential data on stack while attacker try to exploit vulnerability like stack buffer overflow, but not limited to (if You do stack pivot from heap back to heap but badly overwrite saved instruction pointer... nevermind ;) ). If the overflow is detected then they raise SegFault. Example link with example of exploitation.

This answers Your direct question (understand what is going wrong).

Now, You should debug it and then narrow down the issue. Especially ask the next question, not edit again.

@Ovi, I was not downvoter (I still cant do it) but this is not SO question type. I got downvotes for the same reasons (issue/question not narrowed down). You should try to learn debugging your code, that is thought but only on first few times. — badasz, Jul 12 '21 at 19:58
Thank you for the information. I recently learned how to use the debugger to fix logic errors, but it is time to learn how to fix these these more technical errors as well (do they have a name?). One other question, if I may: How can I know which "stack" this error is referring to? Is this stack in the header file? (I don't have any stack in my explicit code). Or some other stack? — Ovi, Jul 13 '21 at 00:12
@Ovi see the updated answer. In short words it is stack of Your process, not any stack (like any FILO queue, or other data structure which You have in code). They are on stack or heap. — badasz, Jul 13 '21 at 17:18

Writing heapify function from scratch, getting a "stack-based buffer overrun"

1 Answers1