Overflow bug in search functions

classic Classic list List threaded Threaded
2 messages Options
Reply | Threaded
Open this post in threaded view
|

Overflow bug in search functions

Dmitry

I checked a new version 5.3.5 of Lua and found overflow bug in four functions.
The older versions of Lua also contain this error.

Affected functions.
lauxlib.c
   int countlevels (lua_State *L)

ltable.c
   int unbound_search (Table *t, unsigned int j) 
   int luaH_getn (Table *t);

ltabllib.c
   void auxsort (lua_State *L, TabA *ta, int l, int u)

The bug is very common. This equation leads overflow.
m = (h + l) / 2;

The equation should be rewritten as:
m = l + (h - l) / 2;

https://stackoverflow.com/questions/6735259/calculating-mid-in-binary-search

Reply | Threaded
Open this post in threaded view
|

Re: Overflow bug in search functions

Pierre Chapuis
As far as I know, this bug is known in older versions of Lua, and fixed in 5.3.4 and later versions by using unsigned integers for the pivot in `unbound_search` and `luaH_getn` [1].

As you can see there is an explicit overflow check in `unbound_search` before computing the pivot. For `auxsort`, the same check is performed in `sort` before calling it.

For `countlevels`, it doesn't  exist anymore (replaced by `lastlevel` in 5.3.2) and I don't think this can possibly overflow in general since indices are bounded by the size of the stack, which is much less than `INT_MAX / 2`. *Maybe* it is possible to make it overflow in theory by changing `LUAI_MAXSTACK` in `luaconf.h` though?


-- 
Pierre Chapuis


On Mon, Jul 16, 2018, at 07:45, Dmitry wrote:

I checked a new version 5.3.5 of Lua and found overflow bug in four functions.
The older versions of Lua also contain this error.

Affected functions.
lauxlib.c
   int countlevels (lua_State *L)

ltable.c
   int unbound_search (Table *t, unsigned int j) 
   int luaH_getn (Table *t);

ltabllib.c
   void auxsort (lua_State *L, TabA *ta, int l, int u)

The bug is very common. This equation leads overflow.
m = (h + l) / 2;

The equation should be rewritten as:
m = l + (h - l) / 2;