News for hackers. Stuff that matters.
Re:TRE: A Regex Engine with Approximate Matching by gitgud on Tuesday November 06, 2018 @08:53AM (#18390934)
Interesting, would help with [1] ReDOS attacks? It would seem that fuzzy matching could put a upper limit on execution time right?

[1] https://en.m.wikipedia.org/wiki/ReDoS

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...