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.
