On Mon, Jun 8, 2020 at 3:38 PM 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. > Depends on what we're talking about as the "input" here. It is certainly not linearly bound by the name of the directory, as you pointed out. So the input would have to be the FS then. > 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. > I disagree. Because for this to be the case, the attacker would then have to be able to provide a sufficiently large FS as an input. Of course you shouldn't design a system where someone can run directory listings against an arbitrarily large FS with an arbitrarily short query. But the reason is *precisely* that in that scenario, a directory listing is *not* bounded by the input-size. That's the core of the argument here: If your algorithm is linear or sublinear in the input-size, then any attacker wanting to consume resources, must spent a proportional amount of their own resources. > > 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/CAEkBMfHfXYOPXYjFB%2BP5w-sN7VF%2BWLS-dkiZAriF5a4nnVTPRA%40mail.gmail.com.
