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.
