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. 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() is linear based >>>>>>> on this comment in the regexp package 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()? 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. >>>>> >>>>> -- >>>>> 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. >>> >>> -- >>> 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. > > -- > 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. -- 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.
