The string package has regular expression matching, and they can be used to leverage https://www.regular-expressions.info/catastrophic.html. Check the following example, which takes 25 seconds to run.
start = os.time()
print('running...')
s = string.gsub('aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa', 'a*a*a*a*a*a*a*b', 'X')
print('ran in ', os.difftime(os.time(), start), ' second(s)')
I'd like to find a way to prevent from such "attack" on a system that would execute user provided lua scripts. The system uses a custom allocator that limits the memory that can be allocated, and a hook that calls lua_error at next instruction executed if script evaluation takes too long.
Unfortunately, none of those help, because the above code doesn't need a lot of memory allocated to run, and the debug hook sees the whole gsub call as one instructions.
So the only solution I see is to not expose string.gsub() to users, or to run in a sandbox that can be terminated violently after some time. Has the Lua community figured out a better solution? Have I missed something in our hooks should be used, or potential native Lua ways of "bounding" execution?
