Here is a simpler reproducer: https://play.golang.org/p/82UBmyfyqV- <https://play.golang.org/p/82UBmyfyqV->
(Running it on the playground isn’t much use because of the playground’s fake time, though.) It just repeats the string “D||” (with two vertical bars) to make the regex. The runtime is roughly quadratic in the number of repetitions. Andy > On Jun 11, 2020, at 12:55 PM, Andy Balholm <andybalh...@gmail.com> wrote: > > Obviously any reasonable input validation or length limit would disallow it. > > The time requirement is only quadratic, not exponential, so it takes > ridiculously long inputs to cause a problem. > > Andy > >> On Jun 11, 2020, at 12:26 PM, Robert Engels <reng...@ix.netcom.com >> <mailto:reng...@ix.netcom.com>> wrote: >> >> Why would you ever allow that regex? >> >>> On Jun 11, 2020, at 11:01 AM, Andy Balholm <andybalh...@gmail.com >>> <mailto:andybalh...@gmail.com>> wrote: >>> >>> It’s apparently quadratic in some cases. Yesterday fuzzing on >>> github.com/andybalholm/cascadia <http://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+unsubscr...@googlegroups.com >>> <mailto:golang-nuts+unsubscr...@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 >>> >>> <https://groups.google.com/d/msgid/golang-nuts/885CBC71-3268-4BEA-983E-A67B824AC654%40gmail.com?utm_medium=email&utm_source=footer>. >>> <regex.txt> >>> >>> >>>> On Jun 9, 2020, at 8:42 AM, 'Thomas Bushnell, BSG' via golang-nuts >>>> <golang-nuts@googlegroups.com <mailto:golang-nuts@googlegroups.com>> wrote: >>>> >>>> On Tue, Jun 9, 2020 at 11:23 AM Axel Wagner <axel.wagner...@googlemail.com >>>> <mailto:axel.wagner...@googlemail.com>> wrote: >>>> 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) >>>> >>>> The OP stopped participating in this exciting thread a long time ago. I >>>> went and read through the code, and it seems pretty clear to me that it's >>>> linear. >>>> >>>> -- >>>> 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 >>>> <mailto:golang-nuts+unsubscr...@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 >>>> >>>> <https://groups.google.com/d/msgid/golang-nuts/CA%2BYjuxvQgnTKMM4FF4%3D4pspM-2nBJScNfCNinDv-2cNA09N%3DaQ%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 >>> <mailto:golang-nuts+unsubscr...@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 >>> >>> <https://groups.google.com/d/msgid/golang-nuts/885CBC71-3268-4BEA-983E-A67B824AC654%40gmail.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/DECADAAC-2F98-463C-9202-132D6D0F93F6%40gmail.com.
