Attempting to prevent DOS attacks through algorithm efficiency never works - you have to have resource throttling.
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. > 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/08669F7D-3D67-4A84-BA5B-395556550E0A%40ix.netcom.com.
