On Mon, Jun 8, 2020 at 5:41 PM Thomas Bushnell, BSG <tbushn...@google.com> wrote:
> The OP was about MustCompile, so I think it's clear they are not using > patterns passed in by external requests. > I don't think that's clear at all. How do you assume patterns from external sources can be matched, if not by compiling them? > > 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/CAEkBMfEVgTL2oaF7m2bQE4UVz61qmFkU7WNJR%2BxfFoGZKyz2Bw%40mail.gmail.com.
