The OP specifically asked about compilation - in fact it’s in the title. You stated the compilation complexity is a DoS attack vector. I argued that it is not. That is all.
> On Jun 8, 2020, at 6:39 PM, Michael Jones <michael.jo...@gmail.com> wrote: > > > Ray, only the discussion is exponential. > >> On Mon, Jun 8, 2020 at 4:23 PM 'Axel Wagner' via golang-nuts >> <golang-nuts@googlegroups.com> wrote: >>> On Tue, Jun 9, 2020 at 12:48 AM Kurtis Rader <kra...@skepticism.us> wrote: >> >>> You're talking past each other. Robert is talking about limiting the length >>> of the regex, not the string(s) evaluated by the regex. >> >> So am I. Note that e.g. a Code Search based on PCRE would break, even if you >> limit *both* (or rather, any limit causing it to not break would result in a >> completely useless piece of software). >> >>> It should be possible to compile any regex of a reasonable length in a >>> matter of microseconds. Regardless of whether the application of the regex >>> to a given input is near linear (as in the case of the Go RE >>> implementation) or exponential (as in the case of PCRE). >> >> This might be, where we talk past each other. I am using application as an >> example for concrete numbers on how quickly exponential growth can devolve. >> Of course, compilation of a regexp is fast - I am aware of that. As it turns >> out, so is application of a regexp, if you use RE2 (or Go's regexp package). >> >> What I take issue with are the statements that a) the question about the >> complexity of compiling a regexp is irrelevant, because b) limiting the >> algorithmic complexity of a function to counteract resource exhaustion >> attacks "never works". RE2 is an excellent example to show that it does >> work; it is carefully designed for linear complexity of the combined >> compilation+matching of a regular expression. >> >> I'm not saying compiling a regular expression is an exponential operation. >> I'm saying *if it was*, you could never reasonably build something like Code >> Search. And we can use the fact that *application* indeed is (in most >> engines) exponential in the combined input length of expression+search text >> as a good basis to make that case. >> >> Of course we don't even need this fantasy world to make the case - after >> all, saying "you can't build Code Search on PCRE, but you can on RE2" is >> just as effective to prove the effectiveness of lowering algorithmic >> complexity. It's just that OP's question was about compilation, so to talk >> about why OP's question *is* relevant, we need to talk about what would >> happen if the answer *wasn't* "it's linear". >> >> (I also genuinely don't understand the instinct to tell someone "why would >> you care?" instead of telling them the answer, FWIW. Especially in a case >> like this, where the answer is pretty simple) >> >>> I'm pretty sure Robert is not arguing that the scaling problems of the >>> regex implementation used by Perl, and too many others, can be mitigated >>> simply by limiting the size of the string to be matched by the regex. If >>> compiling a regex of reasonable length takes a non-negligible amount of >>> time something is wrong. >>> >>>> On Mon, Jun 8, 2020 at 3:22 PM Wojciech S. Czarnecki <o...@fairbe.org> >>>> wrote: >>>> Dnia 2020-06-08, o godz. 16:22:24 >>>> Robert Engels <reng...@ix.netcom.com> napisał(a): >>>> >>>> > it is trivial to limit the input size to something a user could input. >>>> >>>> With exponential complexity simple regex /(x+x+)+y/ blows up at input of >>>> 20 to 30 x-es. >>>> See: https://www.regular-expressions.info/catastrophic.html >>>> >>>> [Cut long explanations... Axel just posted most of what I was writing >>>> regarding trade-offs). >>>> >>>> Hope this helps, >>>> >>>> -- >>>> Wojciech S. Czarnecki >>>> << ^oo^ >> OHIR-RIPE >>>> >>>> -- >>>> You received this message because you are subscribed to the Google Groups >>>> "golang-nuts" group. >>>> To unsubscribe from this group and stop receiving emails from it, send an >>>> email to golang-nuts+unsubscr...@googlegroups.com. >>>> To view this discussion on the web visit >>>> https://groups.google.com/d/msgid/golang-nuts/20200609002207.0a161adf%40xmint. >>> >>> >>> -- >>> Kurtis Rader >>> Caretaker of the exceptional canines Junior and Hank >>> -- >>> You received this message because you are subscribed to the Google Groups >>> "golang-nuts" group. >>> To unsubscribe from this group and stop receiving emails from it, send an >>> email to golang-nuts+unsubscr...@googlegroups.com. >>> To view this discussion on the web visit >>> https://groups.google.com/d/msgid/golang-nuts/CABx2%3DD9sKeHnqUAqB61y5Ts-U_f%2BctVAuS4BC0ae8phhhcp1iw%40mail.gmail.com. >> >> -- >> You received this message because you are subscribed to the Google Groups >> "golang-nuts" group. >> To unsubscribe from this group and stop receiving emails from it, send an >> email to golang-nuts+unsubscr...@googlegroups.com. >> To view this discussion on the web visit >> https://groups.google.com/d/msgid/golang-nuts/CAEkBMfGnRrAt%3Dx3buNcfoOc9xGqVj_tfMEviU%3D7Amjw01e%3Df_w%40mail.gmail.com. > > > -- > Michael T. Jones > michael.jo...@gmail.com > -- > You received this message because you are subscribed to the Google Groups > "golang-nuts" group. > To unsubscribe from this group and stop receiving emails from it, send an > email to golang-nuts+unsubscr...@googlegroups.com. > To view this discussion on the web visit > https://groups.google.com/d/msgid/golang-nuts/CALoEmQwXi99-PCpfrwzgfBkk5H6-u82ROYeNG9%2B-0yeNirDx-g%40mail.gmail.com. -- You received this message because you are subscribed to the Google Groups "golang-nuts" group. To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscr...@googlegroups.com. To view this discussion on the web visit https://groups.google.com/d/msgid/golang-nuts/1580060C-120D-429C-9108-FE43D9992F6D%40ix.netcom.com.
