Segfault when an integer table key overflows

[Eric Liu (BLOOMBERG/ 731 LEX)]

Hello,

I ran across a segmentation fault when fuzzing the latest version of the Lua interpreter.

After test case reduction, our bug triggering input looks very similar to the input that triggered bug #3 in Lua version (5.3.4):

> local t = {}

> for i = 1, 2147483648 do

> t[i] = 1

> end

> print(#t)

The above program causes a stack-buffer-overflow in Lua-5.3.4, but is fixed after testing version 5.3.5. However, it seems a new bug was introduced as the above test case crashes Lua with the following stack dump (obtained by adding the “-fsanitize=address -g3” flags to the makefile):

AddressSanitizer:DEADLYSIGNAL

=================================================================

==64760==ERROR: AddressSanitizer: SEGV on unknown address 0x560af5174080 (pc 0x55fef5131282 bp 0x6170000000f0 sp 0x7ffd9880e0a0 T0)

==64760==The signal is caused by a WRITE memory access.

#0 0x55fef5131282 in luaH_finishset /home/eliu/lua/ltable.c:1103

#1 0x55fef5137059 in luaV_finishset /home/eliu/lua/lvm.c:337

#2 0x55fef513d517 in luaV_execute /home/eliu/lua/lvm.c:1320

#3 0x55fef5108c2a in ccall /home/eliu/lua/ldo.c:637

#4 0x55fef5108c2a in luaD_callnoyield /home/eliu/lua/ldo.c:655

#5 0x55fef5105547 in luaD_rawrunprotected /home/eliu/lua/ldo.c:144

#6 0x55fef5109b18 in luaD_pcall /home/eliu/lua/ldo.c:958

#7 0x55fef50fd7b4 in lua_pcallk /home/eliu/lua/lapi.c:1090

#8 0x55fef50f3266 in docall /home/eliu/lua/lua.c:160

#9 0x55fef50f4425 in handle_script /home/eliu/lua/lua.c:264

#10 0x55fef50f4425 in pmain /home/eliu/lua/lua.c:657

#11 0x55fef5107f30 in precallC /home/eliu/lua/ldo.c:529

#12 0x55fef5107f30 in luaD_precall /home/eliu/lua/ldo.c:595

#13 0x55fef5108bee in ccall /home/eliu/lua/ldo.c:635

#14 0x55fef5108bee in luaD_callnoyield /home/eliu/lua/ldo.c:655

#15 0x55fef5105547 in luaD_rawrunprotected /home/eliu/lua/ldo.c:144

#16 0x55fef5109b18 in luaD_pcall /home/eliu/lua/ldo.c:958

#17 0x55fef50fd7b4 in lua_pcallk /home/eliu/lua/lapi.c:1090

#18 0x55fef50f240a in main /home/eliu/lua/lua.c:685

#19 0x7fb7d7829d8f in __libc_start_call_main ../sysdeps/nptl/libc_start_call_main.h:58

#20 0x7fb7d7829e3f in __libc_start_main_impl ../csu/libc-start.c:392

#21 0x55fef50f2ae4 in _start (/home/eliu/lua/lua+0x18ae4)

The root cause of the bug appears to be an issue in the OP_SETTABLE instruction flow. When incrementally filling a table with integer keys (regardless of value), reaching a key value greater than C’s INT_MAX (i.e. 2^31 = 2147483648) causes an invalid write memory access into the table in luaH_finishset (ltable.c:1103). We have narrowed down the following:

1. lvm.c:1312: When we reach a key value of 2147483648, we use the luaV_fastseti(...) macro to fast track integers. This macro sets the value of hres.
2. ltable.h:61: Execution continues until the code for macro luaH_fastseti(...) is triggered. In this macro, the key value 2147483648 is cast to an lua_Unsigned. Then 2147483648 is cast into a signed integer. Since 2147483648 > INT_MAX, the value returned by this cast is -2147483647. It then takes the negation of -2147483647 which is 2147483647 and stores this value in hres.
3. lvm.c:1320: luaV_finishset is called with the table, key, value, and hres of 2147483647.
4. ltable.c:1103: In luaH_finishset, since hres > 0, it attempts to retrieve a regular node with the large hres value as an index. The node retrieved is far beyond the bounds of the &(t)->node array.
5. lobject.h:120: This macro tries to assign a value to the retrieved regular node, but this triggers a segmentation fault

A correct execution of this table flow would return an hres value less than 0 since the cast in step 2 would not result in a negative value if the key is less than INT_MAX but greater than 0. This would change step 4 since we would trigger array entry set table logic instead of regular node set table logic.

A potential patch is converting all instances of hres from type int to lua_Integer:

diff --cc makefile

index 38e21f1f,d9952d0e..00000000

--- a/makefile

+++ b/makefile

diff --git a/lapi.c b/lapi.c

index 2b14c15e..8b8ea3b1 100644

--- a/lapi.c

+++ b/lapi.c

@@ -851,7 +851,7 @@ LUA_API int lua_getiuservalue (lua_State *L, int idx, int n) {

** t[k] = value at the top of the stack (where 'k' is a string)

*/

static void auxsetstr (lua_State *L, const TValue *t, const char *k) {

- int hres;

+ lua_Integer hres;

TString *str = luaS_new(L, k);

api_checkpop(L, 1);

luaV_fastset(t, str, s2v(L->top.p - 1), hres, luaH_psetstr);

@@ -879,7 +879,7 @@ LUA_API void lua_setglobal (lua_State *L, const char *name) {

LUA_API void lua_settable (lua_State *L, int idx) {

TValue *t;

- int hres;

+ lua_Integer hres;

lua_lock(L);

api_checkpop(L, 2);

t = index2value(L, idx);

@@ -902,7 +902,7 @@ LUA_API void lua_setfield (lua_State *L, int idx, const char *k) {

LUA_API void lua_seti (lua_State *L, int idx, lua_Integer n) {

TValue *t;

- int hres;

+ lua_Integer hres;

lua_lock(L);

api_checkpop(L, 1);

t = index2value(L, idx);

diff --git a/ltable.c b/ltable.c

index e969adef..259615d7 100644

--- a/ltable.c

+++ b/ltable.c

@@ -1094,7 +1094,7 @@ int luaH_pset (Table *t, const TValue *key, TValue *val) {

void luaH_finishset (lua_State *L, Table *t, const TValue *key,

- TValue *value, int hres) {

+ TValue *value, lua_Integer hres) {

lua_assert(hres != HOK);

if (hres == HNOTFOUND) {

luaH_newkey(L, t, key, value);

@@ -1114,7 +1114,7 @@ void luaH_finishset (lua_State *L, Table *t, const TValue *key,

** barrier and invalidate the TM cache.

*/

void luaH_set (lua_State *L, Table *t, const TValue *key, TValue *value) {

- int hres = luaH_pset(t, key, value);

+ lua_Integer hres = luaH_pset(t, key, value);

if (hres != HOK)

luaH_finishset(L, t, key, value, hres);

}

diff --git a/ltable.h b/ltable.h

index 6db197ba..10cf0ed0 100644

--- a/ltable.h

+++ b/ltable.h

@@ -58,7 +58,7 @@

{ Table *h = t; lua_Unsigned u = l_castS2U(k); \

if ((u - 1u < h->alimit)) { \

lu_byte *tag = getArrTag(h,(u)-1u); \

- if (tagisempty(*tag)) hres = ~cast_int(u); \

+ if (tagisempty(*tag)) hres = ~l_castU2S(u); \

else { fval2arr(h, u, tag, val); hres = HOK; }} \

else { hres = luaH_psetint(h, u, val); }}

@@ -152,7 +152,7 @@ LUAI_FUNC void luaH_set (lua_State *L, Table *t, const TValue *key,

TValue *value);

LUAI_FUNC void luaH_finishset (lua_State *L, Table *t, const TValue *key,

- TValue *value, int hres);

+ TValue *value, lua_Integer hres);

LUAI_FUNC Table *luaH_new (lua_State *L);

LUAI_FUNC void luaH_resize (lua_State *L, Table *t, unsigned nasize,

unsigned nhsize);

diff --git a/lvm.c b/lvm.c

index 37023afb..43716e1c 100644

--- a/lvm.c

+++ b/lvm.c

@@ -326,7 +326,7 @@ int luaV_finishget (lua_State *L, const TValue *t, TValue *key, StkId val,

** Finish a table assignment 't[key] = val'.

*/

void luaV_finishset (lua_State *L, const TValue *t, TValue *key,

- TValue *val, int hres) {

+ TValue *val, lua_Integer hres) {

int loop; /* counter to avoid infinite loops */

for (loop = 0; loop < MAXTAGLOOP; loop++) {

const TValue *tm; /* '__newindex' metamethod */

@@ -1291,7 +1291,7 @@ void luaV_execute (lua_State *L, CallInfo *ci) {

vmbreak;

}

vmcase(OP_SETTABUP) {

- int hres;

+ lua_Integer hres;

TValue *upval = cl->upvals[GETARG_A(i)]->v.p;

TValue *rb = KB(i);

TValue *rc = RKC(i);

@@ -1305,7 +1305,7 @@ void luaV_execute (lua_State *L, CallInfo *ci) {

}

vmcase(OP_SETTABLE) {

StkId ra = RA(i);

- int hres;

+ lua_Integer hres;

TValue *rb = vRB(i); /* key (table is in 'ra') */

TValue *rc = RKC(i); /* value */

if (ttisinteger(rb)) { /* fast track for integers? */

@@ -1322,7 +1322,7 @@ void luaV_execute (lua_State *L, CallInfo *ci) {

}

vmcase(OP_SETI) {

StkId ra = RA(i);

- int hres;

+ lua_Integer hres;

int b = GETARG_B(i);

TValue *rc = RKC(i);

luaV_fastseti(s2v(ra), b, rc, hres);

@@ -1337,7 +1337,7 @@ void luaV_execute (lua_State *L, CallInfo *ci) {

}

vmcase(OP_SETFIELD) {

StkId ra = RA(i);

- int hres;

+ lua_Integer hres;

TValue *rb = KB(i);

TValue *rc = RKC(i);

TString *key = tsvalue(rb); /* key must be a short string */

diff --git a/lvm.h b/lvm.h

index a11db83c..f45d4eb8 100644

--- a/lvm.h

+++ b/lvm.h

@@ -123,7 +123,7 @@ LUAI_FUNC int luaV_flttointeger (lua_Number n, lua_Integer *p, F2Imod mode);

LUAI_FUNC int luaV_finishget (lua_State *L, const TValue *t, TValue *key,

StkId val, int tag);

LUAI_FUNC void luaV_finishset (lua_State *L, const TValue *t, TValue *key,

- TValue *val, int aux);

+ TValue *val, lua_Integer aux);

LUAI_FUNC void luaV_finishOp (lua_State *L);

LUAI_FUNC void luaV_execute (lua_State *L, CallInfo *ci);

LUAI_FUNC void luaV_concat (lua_State *L, int total);

Can someone in the lua team look into this?

Thank you,

Eric

[Roberto Ierusalimschy]

> I ran across a segmentation fault when fuzzing the latest version of the Lua interpreter.

What do you mean by "the latest version"? 5.4.6? 5.4.7?

-- Roberto

[Eric Liu (BLOOMBERG/ 731 LEX)]

Sorry for the ambiguity; the bug report is based on commit 0897c0a4289ef3a8d45761266124613f364bef60 (Apr 8), so 5.4.6 I believe? I just tested it on the newest commit (bdc85357aa41a9610498232c2cffe7aa191e5cf6) and the segfault remains.

-Eric

--
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 lua-l+un...@googlegroups.com.
To view this discussion on the web visit
https://groups.google.com/d/msgid/lua-l/20240605212611.GB284870%40arraial.inf.pu
c-rio.br.

[Sainan]

FWIW, I am not able to reproduce on 64-bit builds on my system with 64 GB of RAM; it prints 2147483648 after about 40 seconds, as expected.

32-bit builds run out of memory very quickly.

[Roberto Ierusalimschy]

> Sorry for the ambiguity; the bug report is based on commit 0897c0a4289ef3a8d45761266124613f364bef60 (Apr 8), so 5.4.6 I believe? I just tested it on the newest commit (bdc85357aa41a9610498232c2cffe7aa191e5cf6) and the segfault remains.

This is in the master branch, which is work for 5.5. Versions 5.4 (branch
v5.4 in the git) do not have that code.

-- Roberto

[Roberto Ierusalimschy]

> I ran across a segmentation fault when fuzzing the latest version of the Lua interpreter.
>

> [...]
>
> 2)ltable.h:61: Execution continues until the code for macro luaH_fastseti(...) is triggered. In this macro, the key value 2147483648 is cast to an lua_Unsigned. Then 2147483648 is cast into a signed integer. Since 2147483648 > INT_MAX, the value returned by this cast is -2147483647. It then takes the negation of -2147483647 which is 2147483647 and stores this value in hres.

Many thanks for the feedback. Indeed, hres should use C indices, not
Lua indices.

-- Roberto