If you actually read OPs second E-Mail, they did and they didn't find it very clear. With that in mind, your message isn't very nice. (Also, not to be repetitive or anything: ~80% of the messages in this thread aren't actually concerned with what the complexity class *is*, but whether it matters)
On Tue, Jun 9, 2020 at 5:12 PM 'Thomas Bushnell, BSG' via golang-nuts < golang-nuts@googlegroups.com> wrote: > I'm surprised none of you have taken all this time to just go read the > code, where it is clearly linear. > > On Mon, Jun 8, 2020 at 9:12 PM Robert Engels <reng...@ix.netcom.com> > wrote: > >> 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 >>>> <https://groups.google.com/d/msgid/golang-nuts/CABx2%3DD9sKeHnqUAqB61y5Ts-U_f%2BctVAuS4BC0ae8phhhcp1iw%40mail.gmail.com?utm_medium=email&utm_source=footer> >>>> . >>>> >>> -- >>> 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 >>> <https://groups.google.com/d/msgid/golang-nuts/CAEkBMfGnRrAt%3Dx3buNcfoOc9xGqVj_tfMEviU%3D7Amjw01e%3Df_w%40mail.gmail.com?utm_medium=email&utm_source=footer> >>> . >>> >> >> >> -- >> >> *Michael T. jonesmichael.jo...@gmail.com <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 >> <https://groups.google.com/d/msgid/golang-nuts/CALoEmQwXi99-PCpfrwzgfBkk5H6-u82ROYeNG9%2B-0yeNirDx-g%40mail.gmail.com?utm_medium=email&utm_source=footer> >> . >> >> -- >> 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 >> <https://groups.google.com/d/msgid/golang-nuts/1580060C-120D-429C-9108-FE43D9992F6D%40ix.netcom.com?utm_medium=email&utm_source=footer> >> . >> > -- > 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/CA%2BYjuxuSgcy_GeiCJJDCYbbxK%2BpbssQAvG15wp2ssrvRirAj0w%40mail.gmail.com > <https://groups.google.com/d/msgid/golang-nuts/CA%2BYjuxuSgcy_GeiCJJDCYbbxK%2BpbssQAvG15wp2ssrvRirAj0w%40mail.gmail.com?utm_medium=email&utm_source=footer> > . > -- 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/CAEkBMfEfG2ORsbxceyZau2DpoiODJPiPzXXQjVoyxKSchrO_4Q%40mail.gmail.com.
