4 ms·

Or just stop using terrible regular expression engines with superlinear runtime? E.g. Rust's regex crate has linear runtime is thus not susceptible to "ReDoS".

by devit 4y ago

turminal 4y ago
That would be great, but given that people generally expect backreferences to work in their regexes, that's not really an option.
tptacek 4y ago
The article mentions this. If you're using a regex engine that isn't susceptible, people will still report ReDoS vulnerabilities against your project.
- burntsushi 4y ago
  I missed this on my first read through. So I went back and tried to find what you're referencing, and this is all I could find: > This is even before any of the really cheap shots, like observing that the entire bug class is based on unreliable premises: that there are no timeouts or resource limits anywhere else in the system (almost always false, particularly in web development), and that the regular expression engine itself is susceptible to pathological runtime behavior (plenty aren’t). Is this what you were thinking of? Or am I still missing something? I'd be curious to see ReDoS reports against programs using regex engines that provide a linear time guarantee.
  - woodruffw 4y ago
    > Is this what you were thinking of? Or am I still missing something? You're not missing anything: I meant to write more about this, but I forgot and snuck that little paragraph at the last minute in instead. I think I could have worded this better -- the observation was meant to be that (1) the regular expression's superlinear behavior is not part of the public interface of languages like Python, and (2) lots of these "vulnerabilities" show up in code ends up in a task queue somewhere, meaning that it's subject to timeouts and other resource constraints that ReDoS reporters don't bother to check for. For (1), what I mean is that Python (or an implementation of Python) could switch to a non-backtracking engine for the subset of compatible regular expressions, and nothing about Python's interface would change.
    - burntsushi 4y ago
      I agree with (2). (1) is in theory right, but it's very rare to see it done. The only one I'm aware of actually doing a "switch between linear time and unbounded backtracking" is Tcl, and I'm not familiar enough with it to know if it actually gives any guarantees. The difficulty in (1) is rooted in: 1) implementation complexity, 2) performance and 3) match semantics. (1)+(2) are related, and indeed, if you want your linear time engine to compete with your backtracker engine, you're going to need to do a fair bit of work. (3) is also quite tricky. Cox's RE2 paves the path for how to get linear time engines to mostly agree with backtrackers, but there may be some corner cases where there is some disagreement. So for something like Python, (3) may be quite difficult to overcome. Popping up a level, I'm not sure how relevant all of this is to your overall point. As the author of Rust's regex crate, I actually generally agree with your post, insomuch as catastrophic backtracking is handled as a security vulnerability. I'm mostly just picking at nits and elaborating here.
      - woodruffw 4y ago
        Yeah, agreed -- (1) isn't exactly commonplace. That point was originally meant to fit into an extended section of the post on reporting format imprecision, i.e. our current inability to express anything more precise than "this dependency is exploitable, you need to upgrade it" with existing vulnerability formats and feeds. Not being able to automatically filter by implementation variance or context-sensitivity fall under that. But I then trimmed that section so this point is mostly irrelevant to the larger post, as you said!
        burntsushi 4y ago
        > our current inability to express anything more precise than "this dependency is exploitable, you need to upgrade it" Oof, yes. I know this pain.

Or just stop using terrible regular expression engines with superlinear runtime? E.g. Rust's regex crate has linear runtime is thus not susceptible to "ReDoS".

by devit 4y ago

Or just stop using terrible regular expression engines with superlinear runtime? E.g. Rust's regex crate has linear runtime is thus not susceptible to "ReDoS".

turminal 4y ago

That would be great, but given that people generally expect backreferences to work in their regexes, that's not really an option.

tptacek 4y ago

The article mentions this. If you're using a regex engine that isn't susceptible, people will still report ReDoS vulnerabilities against your project.

burntsushi 4y ago
I missed this on my first read through. So I went back and tried to find what you're referencing, and this is all I could find: > This is even before any of the really cheap shots, like observing that the entire bug class is based on unreliable premises: that there are no timeouts or resource limits anywhere else in the system (almost always false, particularly in web development), and that the regular expression engine itself is susceptible to pathological runtime behavior (plenty aren’t). Is this what you were thinking of? Or am I still missing something? I'd be curious to see ReDoS reports against programs using regex engines that provide a linear time guarantee.
- woodruffw 4y ago
  > Is this what you were thinking of? Or am I still missing something? You're not missing anything: I meant to write more about this, but I forgot and snuck that little paragraph at the last minute in instead. I think I could have worded this better -- the observation was meant to be that (1) the regular expression's superlinear behavior is not part of the public interface of languages like Python, and (2) lots of these "vulnerabilities" show up in code ends up in a task queue somewhere, meaning that it's subject to timeouts and other resource constraints that ReDoS reporters don't bother to check for. For (1), what I mean is that Python (or an implementation of Python) could switch to a non-backtracking engine for the subset of compatible regular expressions, and nothing about Python's interface would change.
  - burntsushi 4y ago
    I agree with (2). (1) is in theory right, but it's very rare to see it done. The only one I'm aware of actually doing a "switch between linear time and unbounded backtracking" is Tcl, and I'm not familiar enough with it to know if it actually gives any guarantees. The difficulty in (1) is rooted in: 1) implementation complexity, 2) performance and 3) match semantics. (1)+(2) are related, and indeed, if you want your linear time engine to compete with your backtracker engine, you're going to need to do a fair bit of work. (3) is also quite tricky. Cox's RE2 paves the path for how to get linear time engines to mostly agree with backtrackers, but there may be some corner cases where there is some disagreement. So for something like Python, (3) may be quite difficult to overcome. Popping up a level, I'm not sure how relevant all of this is to your overall point. As the author of Rust's regex crate, I actually generally agree with your post, insomuch as catastrophic backtracking is handled as a security vulnerability. I'm mostly just picking at nits and elaborating here.
    - woodruffw 4y ago
      Yeah, agreed -- (1) isn't exactly commonplace. That point was originally meant to fit into an extended section of the post on reporting format imprecision, i.e. our current inability to express anything more precise than "this dependency is exploitable, you need to upgrade it" with existing vulnerability formats and feeds. Not being able to automatically filter by implementation variance or context-sensitivity fall under that. But I then trimmed that section so this point is mostly irrelevant to the larger post, as you said!
      - burntsushi 4y ago
        > our current inability to express anything more precise than "this dependency is exploitable, you need to upgrade it" Oof, yes. I know this pain.