LÖVE

Xgoff wrote:the pattern matcher a potential DoS target

That's an interesting thought. Do you happen to know any example of a pattern that can be used that way? I could find/think of none.

kikito wrote:

Xgoff wrote:the pattern matcher a potential DoS target

That's an interesting thought. Do you happen to know any example of a pattern that can be used that way? I could find/think of none.

you can quite easily invoke catastrophic backtracking

for example the code: ("a"):rep(100):match(patt)

where patt might be:
* a+a+b: too low to measure
* a+a+a+b: 0.08 seconds
* a+a+a+a+b: 1.3 seconds
* a+a+a+a+a+b: 20.3 seconds
etc...

and this is only matching 100 characters!

it might be possible to wrap those functions to use a pattern simplifier (eg to reduce something like `x+x+x+` to just `xxx+`) and run it over pattern strings in order to avoid this, but i don't know if this is feasible in general, or if optimizations like that are always valid (such as if they involve captures)

for fun, the "equivalent" patterns to those above (aa+b, aaa+b, aaaa+b, aaaaa+b) all complete instantly

Well, a simple alternative would be to not expose string.match in the first place (set it to nil before executing the protected code, and restore it on exit). I'm already doing that for string.rep. Thanks for the feedback!

kikito wrote:Well, a simple alternative would be to not expose string.match in the first place (set it to nil before executing the protected code, and restore it on exit). I'm already doing that for string.rep. Thanks for the feedback!

sure, but then you'll have to deal with people who need patterns for something

i guess an alternative could be to reimplement the pattern functions in pure lua so that they could be monitored by hooks, but...