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.
