Catastrophic backtracking in string.match and friends

[vgskye]

Bug Description

the lua built-in functions string.match and string.find take in patterns, which are matched using a backtracking matcher. a backtracking matcher can take exponential time to complete, effectively freezing the game even with very low instruction counts.

Reproduction Steps

1. lower your own avatar's trust level
2. /figura run string.find("this will run for at least three eternities", ".*.*.*.*.*.*.*.*.*.*z.*")
3. observe that the game freezes

Log File

N/A

[TheBunnyMan123]

Step 1: make a while true loop
Observe that the game freezes :trol:

fr though making patterns faster if possible would be cool

[UnlikePaladin]

this isn't really a bug but things just being slow

[vgskye]

Step 1: make a while true loop Observe that the game freezes :trol:

Due to instruction counting, such a construct will not freeze the game with low trust levels. as string pattern matching happens inside luaj itself, it is not counted against the instruction limit despite having the ability to take an arbitrarily long amount of time.

[PoolloverNathan]

I don't see a reasonable way to fix this without reimplementing string.match, unless we just add a 2ⁿ punishment for having n + or * characters in the pattern from the sandbox script.