4 ms·

I remember the day I learned that Python's "re" module uses backtracking for non-extended regexes. My tests covered lots of corner cases in the regex logic, but

I remember the day I learned that Python's "re" module uses backtracking for non-extended regexes. My tests covered lots of corner cases in the regex logic, but were too short for me to notice the performance penalty. Luckily I only caused a partial outage in production. I actually got to talk to Raymond Hettinger (Python core team) about why re uses a potentially exponential-time algorithm for regexes when there is a famous linear-time algorithm, and (I suspect) most programmers would assume linear complexity. As it turns out, there was an attempt to re-write re to fix this, but the re-write never managed to present exactly the same (extremely large) API as the existing module. He advised me that "the standard library is where code goes to die."

deadowl 10y ago
I looked at that module a while back. The goto statements make it very difficult to analyze. It seems to integrate well with the signals module, which could be used to interrupt a large class of ReDoS attempts, but determining whether all potential regexps could be interrupted using signals, with the goto statements, is a difficult task.
mark-r 10y ago
I vaguely remember a replacement for Python's re module, but I can't remember the name, and Googling for it is an exercise in frustration. Edit: it's "regex" - https://pypi.python.org/pypi/regex https://pypi.python.org/pypi/regex. I have no idea if it behaves better with backtracking, a cursory glance at the documentation doesn't indicate any changes in that area.
- d0mine 10y ago
  regex module shows the same behavior as re module in this case: $ python -mtimeit -s "s=' '*20000; import regex as re" "re.search(r'\s+$', s)" # ends with spaces is fast 10000 loops, best of 3: 201 usec per loop $ python -mtimeit -s "s=' '*20000+'non-space'; import regex as re" "re.search(r'\s+$', s)" # ends with a non-space is slow 10 loops, best of 3: 3.39 sec per loop
cyphar 10y ago
I started writing a replacement in Python that doesn't use backtracking. https://github.com/cyphar/redone https://github.com/cyphar/redone
- devinj 10y ago
  I finished (but never optimized it): https://bitbucket.org/devin.jeanpierre/re0 https://bitbucket.org/devin.jeanpierre/re0

deadowl 10y ago

I looked at that module a while back. The goto statements make it very difficult to analyze. It seems to integrate well with the signals module, which could be used to interrupt a large class of ReDoS attempts, but determining whether all potential regexps could be interrupted using signals, with the goto statements, is a difficult task.

mark-r 10y ago

I vaguely remember a replacement for Python's re module, but I can't remember the name, and Googling for it is an exercise in frustration. Edit: it's "regex" - https://pypi.python.org/pypi/regex https://pypi.python.org/pypi/regex. I have no idea if it behaves better with backtracking, a cursory glance at the documentation doesn't indicate any changes in that area.

d0mine 10y ago
regex module shows the same behavior as re module in this case: $ python -mtimeit -s "s=' '*20000; import regex as re" "re.search(r'\s+$', s)" # ends with spaces is fast 10000 loops, best of 3: 201 usec per loop $ python -mtimeit -s "s=' '*20000+'non-space'; import regex as re" "re.search(r'\s+$', s)" # ends with a non-space is slow 10 loops, best of 3: 3.39 sec per loop

cyphar 10y ago

I started writing a replacement in Python that doesn't use backtracking. https://github.com/cyphar/redone https://github.com/cyphar/redone

devinj 10y ago
I finished (but never optimized it): https://bitbucket.org/devin.jeanpierre/re0 https://bitbucket.org/devin.jeanpierre/re0