HARDMEMTESTS: apparent stale stack pointer written to L->top by checkGC (heap OOB read in traversethread)

Hello,

I would like to report a problem I ran into while testing the current 
master (7579fc9d7ed90240487251dfb69168f8e64e9294) built with 
-DHARDMEMTESTS: AddressSanitizer reports a heap out-of-bounds read in 
traversethread. From my reading of the code, it looks as if checkGC(L, ra + 
1) wrote a stale stack pointer to L->top after the GC step moved the stack, 
but I may well be missing something about the intended invariants here, so 
I would appreciate your view. I found it while fuzzing with an 
OSS-Fuzz-style harness, but it also reproduces with the plain interpreter.

Reproduction

Save as repro.lua:
local function f(n)
    if n <= 0 then return 0 end 
    return f(n - 1) + 0 
end 
f(100) 
local function g() return 1 end

*Build and run:*
git clone https://github.com/lua/lua && cd lua
make CC=clang \
MYCFLAGS="-std=c99 -O1 -g -DLUA_USE_LINUX -DHARDMEMTESTS -fsanitize=address 
-fno-omit-frame-pointer" \
MYLDFLAGS="-fsanitize=address" 
./lua repro.lua


*Result:*

==7071==ERROR: AddressSanitizer: heap-buffer-overflow on address 
0x518000000ff8 at pc 0x598b2bf1a477 bp 0x7ffc26980780 sp 0x7ffc26980778
READ of size 1 at 0x518000000ff8 thread T0
    #0 0x598b2bf1a476  (lua+0x143476) (BuildId: 
cf47c548dcdedf37f5c5990c60b2f6da369f4d68)
        => propagatemark lgc.c:705
    #1 0x598b2bf1646e  (lua+0x13f46e) (BuildId: 
cf47c548dcdedf37f5c5990c60b2f6da369f4d68)
        => atomic lgc.c:745
    #2 0x598b2bf130b7  (lua+0x13c0b7) (BuildId: 
cf47c548dcdedf37f5c5990c60b2f6da369f4d68)
        => entergen lgc.c:1431
    #3 0x598b2bf158bb  (lua+0x13e8bb) (BuildId: 
cf47c548dcdedf37f5c5990c60b2f6da369f4d68)
        => fullgen lgc.c:1460
    #4 0x598b2bf4a369  (lua+0x173369) (BuildId: 
cf47c548dcdedf37f5c5990c60b2f6da369f4d68)
        => luaV_execute lvm.c:1939
    #5 0x598b2bf09edd  (lua+0x132edd) (BuildId: 
cf47c548dcdedf37f5c5990c60b2f6da369f4d68)
        => luaD_callnoyield ldo.c:768
    #6 0x598b2bf05b55  (lua+0x12eb55) (BuildId: 
cf47c548dcdedf37f5c5990c60b2f6da369f4d68)
        => luaD_rawrunprotected ldo.c:166
    #7 0x598b2bf0b355  (lua+0x134355) (BuildId: 
cf47c548dcdedf37f5c5990c60b2f6da369f4d68)
        => luaD_pcall ldo.c:1090
    #8 0x598b2befb9a8  (lua+0x1249a8) (BuildId: 
cf47c548dcdedf37f5c5990c60b2f6da369f4d68)
        => lua_pcallk lapi.c:1097
    #9 0x598b2bef02ca  (lua+0x1192ca) (BuildId: 
cf47c548dcdedf37f5c5990c60b2f6da369f4d68)
        => docall lua.c:168
    #10 0x598b2beef59b  (lua+0x11859b) (BuildId: 
cf47c548dcdedf37f5c5990c60b2f6da369f4d68)
        => pmain lua.c:272
    #11 0x598b2bf097b7  (lua+0x1327b7) (BuildId: 
cf47c548dcdedf37f5c5990c60b2f6da369f4d68)
        => luaD_precall ldo.c:657
    #12 0x598b2bf09eaf  (lua+0x132eaf) (BuildId: 
cf47c548dcdedf37f5c5990c60b2f6da369f4d68)
        => luaD_callnoyield ldo.c:766
    #13 0x598b2bf05b55  (lua+0x12eb55) (BuildId: 
cf47c548dcdedf37f5c5990c60b2f6da369f4d68)
        => luaD_rawrunprotected ldo.c:166
    #14 0x598b2bf0b355  (lua+0x134355) (BuildId: 
cf47c548dcdedf37f5c5990c60b2f6da369f4d68)
        => luaD_pcall ldo.c:1090
    #15 0x598b2befb9a8  (lua+0x1249a8) (BuildId: 
cf47c548dcdedf37f5c5990c60b2f6da369f4d68)
        => lua_pcallk lapi.c:1097
    #16 0x598b2beeea5d  (lua+0x117a5d) (BuildId: 
cf47c548dcdedf37f5c5990c60b2f6da369f4d68)
        => main lua.c:788
    #17 0x7dfe5e02a1c9  (/lib/x86_64-linux-gnu/libc.so.6+0x2a1c9) (BuildId: 
328820b908de8ea1ef79afa8995e302e819163d7)
    #18 0x7dfe5e02a28a  (/lib/x86_64-linux-gnu/libc.so.6+0x2a28a) (BuildId: 
328820b908de8ea1ef79afa8995e302e819163d7)
    #19 0x598b2be15604  (lua+0x3e604) (BuildId: 
cf47c548dcdedf37f5c5990c60b2f6da369f4d68)
        => _start ??:?

0x518000000ff8 is located 8 bytes after 880-byte region 
[0x518000000c80,0x518000000ff0)
allocated by thread T0 here:
    #0 0x598b2beb0870  (lua+0xd9870) (BuildId: 
cf47c548dcdedf37f5c5990c60b2f6da369f4d68)
        => ___interceptor_realloc ??:?
    #1 0x598b2bf1beee  (lua+0x144eee) (BuildId: 
cf47c548dcdedf37f5c5990c60b2f6da369f4d68)
        => luaM_realloc_ lmem.c:180
    #2 0x598b2bf062de  (lua+0x12f2de) (BuildId: 
cf47c548dcdedf37f5c5990c60b2f6da369f4d68)
        => luaD_reallocstack ldo.c:339
    #3 0x598b2bf069ee  (lua+0x12f9ee) (BuildId: 
cf47c548dcdedf37f5c5990c60b2f6da369f4d68)
        => luaD_shrinkstack ldo.c:426
    #4 0x598b2bf19764  (lua+0x142764) (BuildId: 
cf47c548dcdedf37f5c5990c60b2f6da369f4d68)
        => propagatemark lgc.c:710
    #5 0x598b2bf166f7  (lua+0x13f6f7) (BuildId: 
cf47c548dcdedf37f5c5990c60b2f6da369f4d68)
        => atomic lgc.c:745
    #6 0x598b2bf14978  (lua+0x13d978) (BuildId: 
cf47c548dcdedf37f5c5990c60b2f6da369f4d68)
        => luaC_step lgc.c:1348
    #7 0x598b2bf4a2c8  (lua+0x1732c8) (BuildId: 
cf47c548dcdedf37f5c5990c60b2f6da369f4d68)
        => luaV_execute lvm.c:1939
    #8 0x598b2bf09edd  (lua+0x132edd) (BuildId: 
cf47c548dcdedf37f5c5990c60b2f6da369f4d68)
        => luaD_callnoyield ldo.c:768
    #9 0x598b2bf05b55  (lua+0x12eb55) (BuildId: 
cf47c548dcdedf37f5c5990c60b2f6da369f4d68)
        => luaD_rawrunprotected ldo.c:166
    #10 0x598b2bf0b355  (lua+0x134355) (BuildId: 
cf47c548dcdedf37f5c5990c60b2f6da369f4d68)
        => luaD_pcall ldo.c:1090
    #11 0x598b2befb9a8  (lua+0x1249a8) (BuildId: 
cf47c548dcdedf37f5c5990c60b2f6da369f4d68)
        => lua_pcallk lapi.c:1097
    #12 0x598b2bef02ca  (lua+0x1192ca) (BuildId: 
cf47c548dcdedf37f5c5990c60b2f6da369f4d68)
        => docall lua.c:168
    #13 0x598b2beef59b  (lua+0x11859b) (BuildId: 
cf47c548dcdedf37f5c5990c60b2f6da369f4d68)
        => pmain lua.c:272
    #14 0x598b2bf097b7  (lua+0x1327b7) (BuildId: 
cf47c548dcdedf37f5c5990c60b2f6da369f4d68)
        => luaD_precall ldo.c:657
    #15 0x598b2bf09eaf  (lua+0x132eaf) (BuildId: 
cf47c548dcdedf37f5c5990c60b2f6da369f4d68)
        => luaD_callnoyield ldo.c:766
    #16 0x598b2bf05b55  (lua+0x12eb55) (BuildId: 
cf47c548dcdedf37f5c5990c60b2f6da369f4d68)
        => luaD_rawrunprotected ldo.c:166
    #17 0x598b2bf0b355  (lua+0x134355) (BuildId: 
cf47c548dcdedf37f5c5990c60b2f6da369f4d68)
        => luaD_pcall ldo.c:1090
    #18 0x598b2befb9a8  (lua+0x1249a8) (BuildId: 
cf47c548dcdedf37f5c5990c60b2f6da369f4d68)
        => lua_pcallk lapi.c:1097
    #19 0x598b2beeea5d  (lua+0x117a5d) (BuildId: 
cf47c548dcdedf37f5c5990c60b2f6da369f4d68)
        => main lua.c:788
    #20 0x7dfe5e02a1c9  (/lib/x86_64-linux-gnu/libc.so.6+0x2a1c9) (BuildId: 
328820b908de8ea1ef79afa8995e302e819163d7)
    #21 0x7dfe5e02a28a  (/lib/x86_64-linux-gnu/libc.so.6+0x2a28a) (BuildId: 
328820b908de8ea1ef79afa8995e302e819163d7)
    #22 0x598b2be15604  (lua+0x3e604) (BuildId: 
cf47c548dcdedf37f5c5990c60b2f6da369f4d68)
        => _start ??:?

SUMMARY: AddressSanitizer: heap-buffer-overflow (lua+0x143476) (BuildId: 
cf47c548dcdedf37f5c5990c60b2f6da369f4d68) 
        => propagatemark lgc.c:705
Shadow bytes around the buggy address:
  0x518000000d00: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x518000000d80: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x518000000e00: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x518000000e80: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x518000000f00: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
=>0x518000000f80: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 fa[fa]
  0x518000001000: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x518000001080: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x518000001100: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x518000001180: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x518000001200: 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
==7071==ABORTING

That is, the collection that over-reads the stack happens in the luaC_fullgc forced 
by HARDMEMTESTS, and it reads from a stack that was just shrunk/reallocated 
by the luaC_step of the very same checkGC.

Explanation

OP_CLOSURE (lvm.c:1935) and OP_NEWTABLE (lvm.c:1423) both end with checkGC(L, 
ra + 1), which expands to luaC_condGC(L, (savepc(ci), L->top.p = ra+1), 
updatetrap(ci)).

With HARDMEMTESTS on, luaC_condGC evaluates pre twice (lgc.h:229-235): once 
before luaC_step (when the debt is due) and once again before the forced 
luaC_fullgc (condchangemem).

In the repro, f(100) leaves the stack much larger than necessary (stacksize 
> 3*inuse). At the OP_CLOSURE for g:

   1. first pre: L->top.p = ra + 1 (valid); luaC_step runs, its atomic 
   phase calls traversethread -> luaD_shrinkstack, which reallocates the 
   stack. correctstack remaps L->top correctly and sets ci->u.l.trap = 1, 
   but the C registers base/ra of the running luaV_execute stay stale until 
   the next vmfetch;
   2. second pre (from condchangemem): re-evaluates L->top.p = ra + 1 with 
   the stale ra, overwriting the correctly remapped value with a dangling 
   pointer (I confirmed this write with a gdb watchpoint: L->top goes from 
   the remapped, in-bounds address to an address in the freed old stack, PC at 
   lvm.c:1939);
   3. luaC_fullgc then marks [th->stack, th->top) out of bounds 
   (lgc.c:704-705).

Without HARDMEMTESTS, condchangemem compiles to nothing, pre runs only once 
(before the step, with a valid ra), and the trap/vmfetch mechanism repairs 
base before it is used again — so normal builds cannot reach this. It is 
also rare with HARDMEMTESTS: the step of that particular checkGC must 
actually shrink the stack, i.e. the stack must be oversized relative to 
inuse at that point. Besides deep recursion, a call with many arguments 
also works; this variant needs no recursion at all (crashes at OP_NEWTABLE, 
lvm.c:1431):
local function sink(...) return 0 end 
local t = {} 
for i = 1, 20000 do t[i] = i end 
sink(table.unpack(t)) 
local x = {}

Note that OP_CONCAT's checkGC(L, L->top.p) (lvm.c:1637) is not affected, 
because re-reading L->top.p after the remap is safe.

-- 
You received this message because you are subscribed to the Google Groups "lua-l" group.
To unsubscribe from this group and stop receiving emails from it, send an email to [email protected].
To view this discussion visit https://groups.google.com/d/msgid/lua-l/ec502a73-1dc1-4912-8ba1-959d467d0dcbn%40googlegroups.com.