I don’t see anything in the blog post referring to compilation time - only runtime. 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. > 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/B116A61A-200E-4A4E-87E9-8A9AE628B9C1%40ix.netcom.com.
