"The regexp implementation provided by this package is guaranteed to run in time linear in the size of the input"
--
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...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/golang-nuts/f51125e7-f66e-45e8-af3a-381f96071d9a%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...@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.
On Jun 8, 2020, at 7:40 AM, 'Axel Wagner' via golang-nuts <golan...@googlegroups.com> wrote:
To view this discussion on the web visit https://groups.google.com/d/msgid/golang-nuts/CAEkBMfGXknH1ZQK7%3DYWay_ruVitjubh3CgWk5hxrTcNLdry%3D_g%40mail.gmail.com.
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 8:04 AM, 'Axel Wagner' via golang-nuts <golan...@googlegroups.com> wrote:
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.
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:27 AM, 'Axel Wagner' via golang-nuts <golan...@googlegroups.com> wrote:
To view this discussion on the web visit https://groups.google.com/d/msgid/golang-nuts/CAEkBMfEaOy0%2BUVnCFQCyoVJvAiEEtgLFGn--_XwDAngKD8RmDg%40mail.gmail.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.
The OP was about MustCompile, so I think it's clear they are not using patterns passed in by external requests.
On Mon, Jun 8, 2020 at 5:41 PM Thomas Bushnell, BSG <tbus...@google.com> wrote:The OP was about MustCompile, so I think it's clear they are not using patterns passed in by external requests.I don't think that's clear at all. How do you assume patterns from external sources can be matched, if not by compiling them?
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 11:07 AM, Axel Wagner <axel.wa...@googlemail.com> wrote:
On Jun 8, 2020, at 2:27 PM, Axel Wagner <axel.wa...@googlemail.com> wrote:
--
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...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/golang-nuts/20200609002207.0a161adf%40xmint.
You're talking past each other. Robert is talking about limiting the length of the regex, not the string(s) evaluated by the regex.
It should be possible to compile any regex of a reasonable length in a matter of microseconds. Regardless of whether the application of the regex to a given input is near linear (as in the case of the Go RE implementation) or exponential (as in the case of PCRE).
I'm pretty sure Robert is not arguing that the scaling problems of the regex implementation used by Perl, and too many others, can be mitigated simply by limiting the size of the string to be matched by the regex. If compiling a regex of reasonable length takes a non-negligible amount of time something is wrong.On Mon, Jun 8, 2020 at 3:22 PM Wojciech S. Czarnecki <oh...@fairbe.org> wrote:Dnia 2020-06-08, o godz. 16:22:24
Robert Engels <ren...@ix.netcom.com> napisał(a):
> it is trivial to limit the input size to something a user could input.
With exponential complexity simple regex /(x+x+)+y/ blows up at input of 20 to 30 x-es.
See: https://www.regular-expressions.info/catastrophic.html
[Cut long explanations... Axel just posted most of what I was writing regarding trade-offs).
Hope this helps,
--
Wojciech S. Czarnecki
<< ^oo^ >> OHIR-RIPE
--
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...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/golang-nuts/20200609002207.0a161adf%40xmint.
----Kurtis RaderCaretaker of the exceptional canines Junior and Hank
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...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/golang-nuts/CABx2%3DD9sKeHnqUAqB61y5Ts-U_f%2BctVAuS4BC0ae8phhhcp1iw%40mail.gmail.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/golang-nuts/CAEkBMfGnRrAt%3Dx3buNcfoOc9xGqVj_tfMEviU%3D7Amjw01e%3Df_w%40mail.gmail.com.
On Jun 8, 2020, at 6:39 PM, Michael Jones <michae...@gmail.com> wrote:
To view this discussion on the web visit https://groups.google.com/d/msgid/golang-nuts/CALoEmQwXi99-PCpfrwzgfBkk5H6-u82ROYeNG9%2B-0yeNirDx-g%40mail.gmail.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/golang-nuts/1580060C-120D-429C-9108-FE43D9992F6D%40ix.netcom.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/golang-nuts/CA%2BYjuxuSgcy_GeiCJJDCYbbxK%2BpbssQAvG15wp2ssrvRirAj0w%40mail.gmail.com.
If you actually read OPs second E-Mail, they did and they didn't find it very clear. With that in mind, your message isn't very nice.(Also, not to be repetitive or anything: ~80% of the messages in this thread aren't actually concerned with what the complexity class *is*, but whether it matters)
On Jun 11, 2020, at 11:01 AM, Andy Balholm <andyb...@gmail.com> wrote:
It’s apparently quadratic in some cases. Yesterday fuzzing on github.com/andybalholm/cascadia found an input that triggered a timeout. The time was being spent compiling a 180-KB regex (which I’m attaching to this message). If I concatenate two copies of this file, the combined regex takes at least four times as long to compile.
I plan to investigate further, and see if I can find a way to reproduce the issue that doesn’t look like it was generated by a fuzzer.Andy
--
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...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/golang-nuts/885CBC71-3268-4BEA-983E-A67B824AC654%40gmail.com.
<regex.txt>
--
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...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/golang-nuts/CA%2BYjuxvQgnTKMM4FF4%3D4pspM-2nBJScNfCNinDv-2cNA09N%3DaQ%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...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/golang-nuts/885CBC71-3268-4BEA-983E-A67B824AC654%40gmail.com.
You received this message because you are subscribed to a topic in the Google Groups "golang-nuts" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/golang-nuts/8M-qVbRKIWA/unsubscribe.
To unsubscribe from this group and all its topics, send an email to golang-nuts...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/golang-nuts/DECADAAC-2F98-463C-9202-132D6D0F93F6%40gmail.com.
The Graph is clearly not linear. Another way to see this is to print out the ratio of time taken and i. If the cost is linear, you'd expect that ratio to be constant. When I run this code https://play.golang.org/p/v1JVQkOXnEH on my machine I get...
--
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...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/golang-nuts/CABx2%3DD-ciPs%3DRa9GAO9SqXqFM_AFRV6TR6h3n3g-_DSpnzu%3DBg%40mail.gmail.com.
You received this message because you are subscribed to a topic in the Google Groups "golang-nuts" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/golang-nuts/8M-qVbRKIWA/unsubscribe.
To unsubscribe from this group and all its topics, send an email to golang-nuts...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/golang-nuts/C52F7F0C-1DCA-44B6-ACE8-2F96066D62CD%40gmail.com.