"How to prevent catastrophic regex? "redux

http://lua-users.org/lists/lua-l/2020-06/msg00083.html and the following thread discuss the ability for Lua patterns to chew up lots of CPU but never presented a solution.  Here's a possible solution.

The idea is to add a counter that is decremented at each point the existing code tests ms->matchdepth; if the counter hits zero an error is raised, which can be caught with pcall. (If the counter starts at zero, no limit is imposed.)

The code is available at https://github.com/nhkeni/lua/tree/keni-pattern and is based off current code from https://github.com/lua/lua .  The makefile in this repo is set for MacOS and there is a pattern_limit_demo.lua file using the pattern from the previous thread; the entire set of changes can be turned on and off with the PATTERN_LIMIT define in luaconf.h.

Questions:
- Does anyone have a pattern that this code cannot limit? (Did I miss any cases that can loop significantly?)
- What's the time penalty for this concept?  On a M2 MacBook Pro, adding the code _reduces_ the run time by about 15%.  I'll guess that cache line alignment is improved by adding one variable to MatchState, but I can't prove it.  Regardless, it makes it hard to reason about the cost.

Insights/comments/questions welcome.

Thanks!

-- 
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 [email protected].
To view this discussion visit https://groups.google.com/d/msgid/lua-l/705D848F-A251-4ECE-A231-4F34861D61B9%40his.com.