4 ms·
Perhaps to protect against ReDoS the client should use an extended finite automata (1). https://www.arl.wustl.edu/~pcrowley/a25-becchi.pdf https://www.arl.wus
by manthideaal 7y ago
Perhaps to protect against ReDoS the client should use an extended finite automata (1).
https://www.arl.wustl.edu/~pcrowley/a25-becchi.pdf https://www.arl.wustl.edu/~pcrowley/a25-becchi.pdf
(1) Extending Finite Automata to Efficiently Match Perl-Compatible Regular Expressions.
- burntsushi 7y agoNope. That still supports backreferences, and resolving backreferences is an NP-complete problem.[1] And I don't see anything in that paper that addresses that. Note that there may be some versions of the problem that maybe aren't NP-complete[2], but again, not addressed by that paper. Besides, that paper was published 12 years ago. Where is the productionized version of it? Or are you suggesting the the OP go spend a few years writing a regex eninge? :-) Doesn't seem like a particularly practical suggestion. [1] - https://perl.plover.com/NPC/NPC-3SAT.html https://perl.plover.com/NPC/NPC-3SAT.html [2] - https://branchfree.org/2019/04/04/question-is-matching-fixed-regexes-with-back-references-in-p/ https://branchfree.org/2019/04/04/question-is-matching-fixed...
- manthideaal 7y agoIn the paper there are some bounds about the number of states in the automata as a function of the length of the input. So one could limit the length of the input when using back references to bound the complexity of the algorithm. They have used their algorithm for snort (network intrusion detection) using asic. The author could contact the authors of the paper and ask for (or pay for) an implementation. By the way, good work ripgrep and rust.