Re: Deterministic hashing for lua tables

[HyperHacker <hyperhacker@...>]

On Mon, Jan 30, 2012 at 18:24, Isaac Dupree <contact@idupree.com> wrote:
> Hi Holly,
>
> I've been contemplating a fully deterministic Lua.  Your post[1] on
> lua-users was the closest thing I found, so I'm asking what progress you've
> made.
>
> I'm probably going to be hacking on Lua's code anyway, and I'd be happy to
> do what I can to implement this.
>
> My use-case: I'm writing a game/simulation where two networked players can
> execute the same user-written script, such as an AI for someone's robot.  I
> desire to guarantee that the two players' simulation states will not go out
> of sync.  Even if they write stupid/malicious scripts.
>
> I wish the determinism to apply even across serialization/deserialization
> (e.g. Pluto[2]), so that the game can be saved/loaded at any time, new
> players can be added to a networked game, etc.
>
> (To protect from stupid/malicious scripts I'll also have to implement
> processor-time and memory usage limits for Lua, and make sure that they're
> deterministic from the simulation's point of view.  I think the limits will
> be per-robot.  Each robot could have its own lua_state to make the
> accounting easier.  Perhaps a count of bytecodes executed, and some
> reasonable count of reachable data, is the way to go.  And I'll do something
> about worst-case hash-table performance.)
>
> [1] http://lua-users.org/lists/lua-l/2011-12/msg00441.html
> [2] http://lua-users.org/wiki/PlutoLibrary
>

Counting bytecode won't protect you against nonsense like:
print(string.match(("x"):rep(1000000000), ("."):rep(1000000000)))

The only reliable way to prevent a script hogging CPU is to limit its CPU time.

Similarly, if you want to protect against memory hogging using Lua's
allocator, then you have to ensure scripts can't allocate a ton of
junk outside of the allocator. e.g. C++ library wrappers commonly
create a new object and store only a pointer to it in a userdata,
since C++ doesn't provide a way to create an object in a pre-allocated
block. If your API lets scripts allocate a 1MB object, but only asks
for 4 bytes from Lua for a pointer to it, that gives them a way to
exceed your memory limit by a factor of 262,144.

I haven't studied sandboxing myself but I believe most properly
secured implementations spawn a new Lua process for each script, using
the OS-provided facilities to limit its resource usage (and access to
filesystem, etc). That might be difficult to pull off in a game,
especially if you have networking involved, where latency becomes an
even bigger issue than it already is.

-- 
Sent from my toaster.