The OP was about MustCompile, so I think it's clear they are not using patterns passed in by external requests.
On Mon, Jun 8, 2020 at 9:39 AM Robert Engels <reng...@ix.netcom.com> wrote: > I will claim it also doesn’t matter because you need external bounding > anyway. Take a simple recursive directory listing. It is linear time > bounded. Perform it on the top level on a sufficiently large directory and > it might run for days consuming TBs of memory - easily becoming a DOS > attack point. So regardless of the complexity you need other constraints > anyway. Build those in at the request handling level to avoid DOS and UX > issues. > > On Jun 8, 2020, at 8:27 AM, 'Axel Wagner' via golang-nuts < > golang-nuts@googlegroups.com> wrote: > > > > > On Mon, Jun 8, 2020 at 3:19 PM Robert Engels <reng...@ix.netcom.com> > wrote: > >> I don’t see anything in the blog post referring to compilation time - >> only runtime. >> > > Sure. It's more a general point about you saying algorithmic complexity > doesn't matter. > > >> That being said I couldn’t review the graphs on my phone. >> >> Even still, to prevent DOS you can bound the compilation time as easily >> as the runtime. If the lib doesn’t support it a simple fork to add an emit >> with cancel out stage is all that is required. >> > > Or, you know, make sure that it just has a guaranteed linear complexity. > Then you don't even need "an emit with a cancel out stage". > > FTR, the whole issue here is a) someone asked about the algorithmic > complexity of a stdlib function and b) people told them off saying the > question isn't relevant. It is. You might not care (you should, IMO. But if > you don't, that's on you). But it's definitely a relevant question to ask. > > >> >> On Jun 8, 2020, at 8:04 AM, 'Axel Wagner' via golang-nuts < >> golang-nuts@googlegroups.com> wrote: >> >> >> On Mon, Jun 8, 2020 at 2:53 PM Robert Engels <reng...@ix.netcom.com> >> wrote: >> >>> Attempting to prevent DOS attacks through algorithm efficiency never >>> works >>> >> >> Uhm, no, it totally does. Code Search is a real-world example of it >> working at least once. >> >> >>> you have to have resource throttling. >>> >> >> Well, yes. But reigning in algorithmic complexity makes that far easier >> and . If the cost of a query is proportional to its length, you can just >> limit the length of queries to some gratuitous upper bound of reasonable. >> But if it's quadratic or even exponential, that no longer works; if the >> cost can be doubled just by adding a character to the query, you have to >> restrict query length to a restrictive *lower* bound on reasonable - which >> is inherently user-unfriendly. >> >> Really, I'd argue that algorithmic efficiency is the *only* real >> effective measure against a cost DoS. >> >> I’m guessing the IO cost of pulling the text in this case has a better >>> chance of creating a DOS than the regex compile. >>> >> >> You might guess that, but you'd be wrong. Again, just look at the graph >> on top of this blog post <https://swtch.com/~rsc/regexp/regexp1.html>. >> You get *minutes* of match-times for queries and corpus of a couple hundred >> characters. >> >> Regexp-based code search couldn't exist without carefully designing >> around algorithmic complexity. >> >> >>> >>> On Jun 8, 2020, at 7:40 AM, 'Axel Wagner' via golang-nuts < >>> golang-nuts@googlegroups.com> wrote: >>> >>> >>> Hi Amnon, >>> >>> if you read the blog posts I linked above, you'll find examples of where >>> we care very much. RE2 was developed for enabling regular expression search >>> in a large source code corpus. In that scenario, the attacker controls both >>> the regular expression and (to a degree) the text to be searched. If they >>> could craft expression/text pairs that are costly to compile and/or match, >>> then this could enable a denial of service attack. >>> >>> So, guaranteeing linear compile- *and* match-times is actually pretty >>> relevant for some real-world use-cases. >>> >>> Best, >>> >>> Axel >>> >>> On Mon, Jun 8, 2020 at 10:16 AM Amnon Baron Cohen <amno...@gmail.com> >>> wrote: >>> >>>> Should we care? >>>> >>>> Regular expressions are generally small. >>>> So the asymptotic complexity is not particularly important. >>>> >>>> But regular expressions are often used to search large amounts of input. >>>> >>>> regexp gives us fast, guaranteed linear search times. >>>> But we pay for this with slower compilation times. >>>> >>>> In my opinion, this is a good tradeoff. >>>> >>>> >>>> >>>> On Wednesday, 3 June 2020 18:07:12 UTC+1, Ray Pereda wrote: >>>>> >>>>> I believe that the complexity of regexp.MustCompile() >>>>> <https://golang.org/pkg/regexp/#MustCompile> is linear based on this >>>>> comment in the regexp package overview. >>>>> <https://golang.org/pkg/regexp/#pkg-overview> >>>>> >>>>> "The regexp implementation provided by this package is guaranteed to >>>>> run in time linear in the size of the input" >>>>> >>>>> >>>>> What is the complexity of regexp.MustCompile() >>>>> <https://golang.org/pkg/regexp/#MustCompile>? Is it linear in the >>>>> length of the regular expression? >>>>> >>>>> -ray >>>>> >>>>> >>>>> >>>>> -- >>>> 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/162b28e7-bd81-47d4-afb7-7fe9f8a15b8do%40googlegroups.com >>>> <https://groups.google.com/d/msgid/golang-nuts/162b28e7-bd81-47d4-afb7-7fe9f8a15b8do%40googlegroups.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/CAEkBMfGXknH1ZQK7%3DYWay_ruVitjubh3CgWk5hxrTcNLdry%3D_g%40mail.gmail.com >>> <https://groups.google.com/d/msgid/golang-nuts/CAEkBMfGXknH1ZQK7%3DYWay_ruVitjubh3CgWk5hxrTcNLdry%3D_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/CAEkBMfGBDB%2BE%3DiVUDdD0_6oa-mXQYPVnjv%2BCpGGGJYaODP8NYA%40mail.gmail.com >> <https://groups.google.com/d/msgid/golang-nuts/CAEkBMfGBDB%2BE%3DiVUDdD0_6oa-mXQYPVnjv%2BCpGGGJYaODP8NYA%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/CAEkBMfEaOy0%2BUVnCFQCyoVJvAiEEtgLFGn--_XwDAngKD8RmDg%40mail.gmail.com > <https://groups.google.com/d/msgid/golang-nuts/CAEkBMfEaOy0%2BUVnCFQCyoVJvAiEEtgLFGn--_XwDAngKD8RmDg%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/C20ABA56-0DE5-4E9E-9D4A-4F8F35D0700F%40ix.netcom.com > <https://groups.google.com/d/msgid/golang-nuts/C20ABA56-0DE5-4E9E-9D4A-4F8F35D0700F%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%2BYjuxs%2B%3DQ2g5WnCvpRqsOBEoHpX1oOmk8dZ6oPbE1pquMeLKg%40mail.gmail.com.
