Re: Interesting interaction between debug hooks, the garbage collector, and "open" VM instructions

[Peter Cawley <lua@...>]

There are two issues here, which I think need clarifying:
1) Having "important" values above L->top after an instruction which sets L->top
2) Segfault from a call where func is above L->top (leading to
negative nargs, etc.)

Starting with (1), there are two choices: either it is valid to have
important values above L->top, or it is invalid. To reiterate the
earlier statement, the default code generator never has important
values above L->top. Is can be useful to have important values above
L->top, as it allows for things like implementing select('#', ...)
with correct handling of trailing nils as a Lua function rather than a
C function, which is (as far as I know) impossible otherwise (see
http://codepad.org/fKjjQT4b for my implementation of this). In itself,
having important values above L->top cannot cause a segfault, however,
debug hooks which fire when L->top < ci->top will mess things up.

If you think it is valid to have important values above L->top, then
the debug hook code needs to be tweaked. I think this would be fairly
trivial; in luaD_callhook, after saving L->top, if L->top is less than
ci->top, then set L->top to ci->top.
Is you think it is invalid to have important values above L->top, then
code which does it is considered garbage-input and thus any output
(except a segfault) is valid, as garbage in -> garbage out.

Moving onto point (2), when loading a binary chunk, the validator
checks that any instruction which produces a variable number of
results (hereby refered to as an open instruction) is followed by an
instruction which consumes a variable number of results (hereby a
closed instruction). To clarify, open instructions can be calls,
tailcalls and varargs. Closed instructions can be calls, tailcalls,
returns and setlists. The validator checks that an open instruction is
immediately followed by a closed instruction, but it does not check
that they match up in terms of where they put/expect arguments. It is
this failure to check which causes L->top to be below func. To correct
this, you thus need to improve checkopenop / luaG_checkopenop to test
if L->top could be below func (or equivalent for return and setlist)
after executing.

On Sun, Feb 8, 2009 at 2:46 PM, Mike Pall <mikelu-0902@mike.de> wrote:
> Patrick Donnelly wrote:
>> This is caused by the top of the stack being reduced below the top
>> slot for the running function. The string and table will both be
>> collected (during the hook) by the GC before the SETLIST operation is
>> executed. What follows is a patch which corrects the problem.
>
> As Peter explained this cannot happen with bytecode generated by
> the Lua parser. Patching the interpreter is only a band-aid (the
> patch is flawed, too). It's necessary to fix the bytecode verifier
> to prevent injection of malicious bytecode.
>
> On short inspection this turns out to be a non-trivial problem.
> The bytecode doesn't contain enough information to easily
> determine the maximum used stack slot at all points in the
> bytecode stream. The debug info helps a bit (lifetimes of locals),
> but this is not always available and incomplete (lifetimes of
> temporaries are missing).
>
> E.g. take the following two functions:
>
> local function foo(...)
>  local a,b,c,d = {},{},{},{}
>  return ...
> end
>
> local function bar(...)
>  local a,b = {},{}
>  do local c,d = {},{} end
>  return ...
> end
>
> And the resulting bytecode:
>
> foo()
>  1  NEWTABLE   1 0 0
>  2  NEWTABLE   2 0 0
>  3  NEWTABLE   3 0 0
>  4  NEWTABLE   4 0 0
>  5  VARARG     5 0
>  6  RETURN     5 0
>
> bar()
>  1  NEWTABLE   1 0 0
>  2  NEWTABLE   2 0 0
>  3  NEWTABLE   3 0 0
>  4  NEWTABLE   4 0 0
>  5  VARARG     3 0
>  6  RETURN     3 0
>
> It's tempting to try to determine the maximum used stack slot by
> searching backwards from the VARARG opcode. This is 4 for foo(),
> so the VARARG starting at slot 5 is ok. But the VARARG starting at
> slot 3 in bar() would be rejected even though the bytecode is
> valid. One needs a full data-flow analysis to discover that none
> of the potentially overwritten slots are used later on. Oh well ...
>
> --Mike
>