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.
