clox: buffer overflow on the stack

[ceronman]

I've found a program that can overflow the stack array in clox. Attached as overflow.txt (sorry for the .txt extension, GitHub doesn't allow to attach .lox files)

Now, if you run this program, the buffer overflow happens unnoticed (at least on my machine) because the stack lives in the C stack, so no segfault. But it's there, and it might cause some super weird bugs. To verify it, you can edit the push() function in vm.c to something like this:

void push(Value value) {
  if (vm.stackTop > &vm.stack[STACK_MAX]) {
    runtimeError("Booom!");
  }
  *vm.stackTop = value;
  vm.stackTop++;
}

After investigating a bit, I noticed that the stack size is then defined as

#define STACK_MAX (FRAMES_MAX * UINT8_COUNT)

It seems that clox tries to prevent overflows by limiting the number of local variables to 255 (UINT8_COUNT - 1). In most cases this works, because clox will throw a Stack Overflow runtime error before actually overflowing the stack array. However, a stack frame can actually have more elements on the stack. First, the actual closure object is stored as the first element on the stack, additionally you can also push an operand for an arithmetic expression as shown in the example attached. This leave us with a frame with 257 elements on the stack. And this is why the buffer is overflown.

A simple fix would be to adjust STACK_MAX to be something like this:

#define STACK_MAX (FRAMES_MAX * (UINT8_COUNT + 1))

However, this might not be enough. There might be other ways of putting more elements on the stack, this and super come to my mind.

[munificent]

There might be other ways of putting more elements on the stack

Yeah, you can overflow from having temporaries on the stack too. Something like:

fun foo() {
  1 + 2 + 3 + 4 + 5 + 6 + 7 + foo();
}

Would probably do it as well. There's an aside that says:

It is still possible to overflow the stack if enough function calls use enough temporaries in addition to locals. A robust implementation would guard against this, but I’m trying to keep things simple.

It's not ideal, but calculating the max stack height of a function body during compilation is kind of a boring chore so I cut it out of the book.

[ceronman]

Hi @munificent!

I'm sorry I forgot about the side note. I just wanted to mention that using code like that example won't actually be a problem, because only two temporaries would be in the stack at a time.

What I mean is that for code like: 1 + 2 + 3 + 4 + 5 + 6 + 7

The stack during execution would look like:

[1]
[1][2]
[3]
[3][3]
[6]
[6][4]
[10]
[10][5]
[15]
[15][6]
[21]
[21][7]
[28]

Or perhaps I'm missing one case when you can fill the stack with temporaries?

If not then I think increasing the size of the stack for the extra possible cases might be good enough to prevent the overflow.

[munificent]

I just wanted to mention that using code like that example won't actually be a problem, because only two temporaries would be in the stack at a time.

Ah, you're right of course. Maybe something more like:

fun foo() {
  1 + (2 + (3 + (4 + (5 + (6 + (7 + foo()))))));
}

It's always possible to contrive some kind of expression that uses an arbitrary number of temporaries.

[nocturn9x]

Maybe we could prevent the overflow altogether by using an ArrayList instead of a fixed size stack, that's what I do in my implementation. That's surely slower, but doesn't limit the number of temporaries

[munificent]

Maybe we could prevent the overflow altogether by using an ArrayList instead of a fixed size stack

This is in clox where we don't have easy access to a growably array. We could use our own ValueList and grow it as needed, yes, but that has a fairly significant performance cost if you check for overflow on every single stack push.

The way most interpreters handle this is instead statically calculate the maximum number of stack slots each function needs. Then, only at function calls, you check to ensure the stack is big enough. But implementing that in the book is a lot of kind of boring bookkeeping code, so I omitted it.