Add an opt-in timeout parameter to re to mitigate catastrophic backtracking

Ideas
21

To be clear, in order for this to be a relevant threat, there needs to be:

  1. A Python app running somewhere on your computer
  2. Accessible to an attacker
  3. Who can send you a regular expression and possibly text to search
  4. AND you have to be using the default re module, not one of the alternatives (some of which are hardened, and if they’re not, this proposal won’t help them).

This is NOT an attack that can be performed against a locally-running app like a text editor, since the only person the attacker can hurt is themselves.

So, how many web apps or other remotely-accessible apps do you have where untrusted people can provide regular expressions to execute on your server?

22

Another possibility would be a subset of the re language that is actually regular, and can therefore be matched using a DFA in linear time.

1 Like
23

Tim Peters is always open to discussion. I’m not him (unluckily :rofl:) but I doubt he changed his mind.

I’m not a C expert, but the regex implementation seems very simple:

If I decrypted the code, the check is done only every 8192 iterations.

I think it’s not difficult to test: just provide a pathological regex and a pathological string, and a very low timeout. But maybe my assumption is wrong, since it seems there’s no tests for timeout in regex.

Anyway, the OP was right: a counter of the number of iterations exists in re. And not only that! It exists also a function that makes the regex fails after n counts. It’s intended for debugging only and the counter and the function are available only if you compile CPython in debug mode:

Curiously, I developed many years ago an app where unstructured data were parsed, and the customer wanted regexes. I tried to not use backtracking, but it was simply impossible, because the number of different formats of data was too high.

It’s not a flag, but it’ possible with regex. It implements some obscure PCRE verbs:

Also many other modules in the stdlib. Or Python. There’s a lot of other programming languages.

It’s not a matter something exists in a third party package. It’s a matter if it makes sense to add it to the stdlib or not. Possessive quantifiers were added to the language even if regex supported them before they landed in Python.

sourcegraph, for example.

24

Yeah, in theory, but it would be a minilanguage that’s just as cryptic as a regex, looks a lot like a regex, but is weirdly incompatible. I think it’d cause a lot of confusion. Hence the alternatives, which would clearly differentiate themselves.

25

So… one. And… is it a major problem for sourcegraph to fetch something from PyPI rather than using the stdlib module? Special cases aren’t special enough to break the rules.

26

It was meant as an opt-out option as I wrote in my first post (3rd from top).

I wrote that there as well. Of course, I was hoping that there is a chance. The break could be not so significant. Solving an regexp for 10+ seconds is IMO not a feature to appreciate and preserve.

Anyway, I do understand that there must be very good reason for changing something as the RE module and this one probably is a reason, but not good enough.

2 Likes
27

While I suspect that a “sufficiently high” limit would not be considered a major breaking change to the majority of the community, I have less hope that people would actually agree on how high the limit should be.

1 Like
28

Or what an acceptable impact on performance is.

29

That said, I am curious about how often people actually write regex with the expectation that they may run for an extended amount of time.

I faintly recall once writing an expression that would, worst-case, run for longer than ten seconds to filter out bad samples from a text dataset, but that was while being well-aware that this might not be the best solution for my problem and valuing my sanity over the time consumed for the job.
If an opt-out timeout been implemented into re at that point and I wasn’t aware of its existence, I probably would have been surprised to see the job interrupted after a good-night’s sleep but not too annoyed about it.

30

To reduce impact, one should anyway have a depreciation period in which long running regexps would just issue a warning and suggest users to increase/deactivate the timeout.

1 Like
31

I think regex without backreferences is regex. And can be implemented to avoid catastrophic backtracking.

RE2 and the default regex crate on Rust support regex, but don’t support backreferences.

Regular Expression Matching Can Be Simple And Fast describes backreferences as “One common regular expression extension”

I’ve not been able to find a source that looks particularly authorative, but there’s a lot of people on the internet who say that “regular expressions with backreferences are not regular expressions”

I don’t expect Python to drop support for backtracking from the regex module, because I understand that would break a lot of people’s code.
But I think it would have been a correct choice way back when regex was first added, and it’s something we should certainly consider for Python4 (if that ever happens).

1 Like
32

I don’t think anyone’s talking about back references here; it’s back tracking that is the costly feature. Backreferences are certainly handy, but they’re not essential and they’re also unlikely to cause catastrophes.

Not sure how this follows?

The problems with backtracking come from simple qualifiers that can compound on each other. A regular expression can tell you whether the length of a string is a prime number (if it matches, it’s not prime) simply by testing whether you can consider that string to be a combination of blocks of equal length. In order to be sure that it can’t be, the regex engine has to first figure out if it can be 2-character blocks, then 3-character, then 4-character, etc. (Or it might work greedily and start from the other end - same difference.) That’s where the catastrophic backtracking comes in. Backreferences can certainly make this a lot easier to trigger, but they aren’t the fundamental problem. Here’s an example that has no backreferences in it:

>>> r = re.compile("^#(_|[0-9]+)+#$")
>>> r.match("#123_234_345#")
<re.Match object; span=(0, 13), match='#123_234_345#'>
>>> r.match("#123_234_345q")
>>>

Looks fine. We allow individual underscores or blocks of digits.[1] It matches a number bracketed by number signs. Seems fine, you could imagine having a regex like this to locate invoice numbers or something.

>>> t = time.monotonic(); r.match("#1231234123412341234123412341234q"); print(t\
ime.monotonic() - t)
69.34401441225782
>>>

Yyyyyyeah. That’s a problem. And no backreferences in sight - just two plus signs and some alternation.

This won’t be a Python 4 change. Either it would be implemented in an entirely backward compatible way, or it would be a replacement module (which is its own form of backward compatibility, in that you can continue to use the original module unchanged). It’s not worth breaking everyone’s code for this.

Regular expressions are code. If you are accepting them from potentially hostile actors, you should NOT trust them. There are other modules better suited to this role.

  1. Please ignore the fact that this trivial example isn’t ACTUALLY enforcing that there’s no underscores here. ↩︎

1 Like
33

“This crate provides routines for searching strings for matches of a regular expression (aka “regex”). The regex syntax supported by this crate is similar to other regex engines, but it lacks several features that are not known how to implement efficiently.” (source: regex - Rust)

My understanding is that all algorithms that robustly avoid catastropic backtracing do not support backreferences. Because there is no way to implement backreferences without opening yourself up to catastropic backtracking.
And when you’re already open to catastropic backtracking, people don’t care that much about avoiding catastropic backtracking for regex without backreferences either, which seems quite rational.

The commandline tool ripgrep demonstrates this.
with the appropriate file in my folder I get the following output:

~/tmp$ cat tmp
#111111111111111111111111111111q
#111111111111111111111
~/tmp$ rg '#(_|[0-9]+)+$' --engine=pcre2
rg: tmp: PCRE2: error matching: match limit exceeded
~/tmp$ rg '#(_|[0-9]+)+$'
tmp
2:#111111111111111111111

the default engine does not allow backreferences, and it completes this pattern fine, almost instantly. The pcre2 enginge, which adds support for backreferences, experiences catastrophic backtracking.

I think it would be better to require people to depend on an external package when they want extra features, such as backreferences, rather than to protect themselves from bad behaviour.

there is no backwards-compatible way to fix catastropic backtracking, because you have to remove backreferences, which is a breaking change.
(Hence, Python4, not Python3.17)

34

You could use a non-backtracking implementation for regexes without backreferences, falling back to the existing implementation when backreferences are present. I’m not convinced it’s worth it, but it’s possible.

But the real solution is:

Catastrophic backtracking is no more of an issue than eval is. Don’t pass untrusted user input to something that evaluates it without checking and sanitising the input.

3 Likes
35

Not related to the core discussion, but there is parse which does the reverse of format.

Of course it converts the format string syntax to regex, internally. But these regexes can be tested against malicious input, which should make the library more secure in situations where users provide patterns.