Re:TRE: A Regex Engine with Approximate Matching
by onlydnaq on Tuesday November 06, 2018 @10:24AM
(#18391791)
I believe the correct way to protect against ReDOS is to use one of the many regular expression implementations that do not have exponential worst cases.
Nowadays there are good DFA or Tree based matching algorithms that are O(mn) where m is the length of the regular expression and n is the length of the input.
Re:TRE: A Regex Engine with Approximate Matching
by jey on Tuesday November 06, 2018 @11:08AM
(#18392201)
No, seems like it would result in a much bigger state machine that includes states and transitions for all those non-exact matches.
https://en.wikipedia.org/wiki/Finite-state_machine#Acceptors...
[1] https://en.m.wikipedia.org/wiki/ReDoS