Re: Overflow bug in search functions

[Pierre Chapuis <catwell@...>]

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?

[1] https://www.lua.org/bugs.html#5.3.4-3

[2] https://www.lua.org/work/diffu-lua-5.3.1-lua-5.3.2.html

-- 

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;

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