Python, Catastrophic Regular Expressions and the GIL (2013)
benfrederickson.com
benfrederickson.com
Python `re` module now supports possessive quantifiers and atomic grouping (I wrote a blog post here [2]). So, for example, `(a+|\w+)*+:` instead of `(a+|\w+)*:` will avoid such catastrophic behavior.
[1] https://blog.cloudflare.com/details-of-the-cloudflare-outage...
[2] https://learnbyexample.github.io/python-regex-possessive-qua...
https://vtechworks.lib.vt.edu/bitstream/handle/10919/98593/D...
(disclosure: I work for Doyensec)
Some people, when confronted with a problem, think ‘I know, I’ll use regular
expressions.’ Now they have two problems.
The article is short and to the point.
>... there's a bit more to the story than that, as evidenced by Jeffrey Friedl's exhaustive research on the Zawinski quote. Zawinski himself commented on it. Analyzing the full text of Jamie's posts in the original 1997 thread, we find the following:
>Perl's nature encourages the use of regular expressions almost to the exclusion of all other techniques; they are far and away the most "obvious" (at least, to people who don't know any better) way to get from point A to point B.
>The first quote is too glib to be taken seriously. But this, I completely agree with. Here's the point Jamie was trying to make: not that regular expressions are evil, per se, but that overuse of regular expressions is evil.
I like Perl, but that is true. Despite the pretty rich set of built-ins, for example, there's not a top-level string replace function. You have to roll your own with index and substr.
> However, the regular expression module is a C module that doesn’t release the GIL before running.
I would love to know why.
- Releasing/acquiring the GIL isn't cheap. So you'd need to know in advance whether it's worth it or not.
- You need the GIL acquired to instantiate the resulting "match data", captures, etc.... or even better, have re. track its own performance and release the GIL if it forecasts that it statistically-might use a lot more computation... a trivial strawman algorithm: if len(input) > MAX then release GIL first.
a="xxx" b="yyy"
regex = re.compile(r'(^a+)+b')
Perhaps the more general problem was that "The regular expression that was causing the issue here was rather long and convoluted".
A good rule seems to be never have long and convoluted regexs, instead have a pipeline of simple-to-understand regexes that can be independently debugged (I don't know if this could cause performance slowdowns however).
Did you see the even simpler fix in TFA that doesn't break mid-string matches?
Regexps in Tcl use a non-backtracking implementation which handles such cases with minimal slowdown, e.g. the example shown with 16 and 32-character inputs:
(dep) 7 % timerate {regexp (a+)+b aaaaaaaaaaaaaaaa}
0.353737 µs/# 2826961 # 2826961 #/sec 1000.000 net-ms
(dep) 8 % timerate {regexp (a+)+b aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa}
0.412612 µs/# 2423587 # 2423587 #/sec 1000.000 net-msTcl's threading implementation has no GIL, which not only avoids the type of lock-up described here, but also allows performance to scale to use all cores of your machine, see: https://www.hammerdb.com/blog/uncategorized/why-tcl-is-700-f... .
2^n is the number of subsets of the string of a's with no contiguity requirements. Nothing like this number of possible matches should need to be checked. What am I missing?
I tested few other on regex101.com and none of them ran longer than a millisecond or two
>On my laptop it takes about 20ms to do the search above with 16 characters - but by doubling the input string size to 32 characters, it takes over 12 minutes to finish. Exponential running time really does suck.
I checked with 32 characters on regex101, and it says "Match 1 halted after 119986 step(s)" when you click the debug icon (click the message above the regex input box).
> Alternatively you could switch to a regular expression engine that doesn’t exhibit this kind of behaviour. RE2 is an excellent library that uses a finite automata approach to avoid this type of catastrophic backtracking. Using this library on the same 32 character input reduces the running time from 12 minutes to basically instant. The downside being that RE2 doesn’t support all the functionality of the builtin re package.
Perl Compatible Regular Expressions (the flavor used by most engines, including Python's) _require_ this exponential worst-case behavior (using an implementation called backtracking). But the theory behind regex does not require this, and if you eliminate just a couple (infrequently used) features of PCRE, you can have a regex engine that runs in linear time (with respect to the size of the input string). See [2], this is by the authors of RE2. The features which are incompatible with this sort of implementation are:
1. Lookahead assertions. 2. Backreferences to matched groups.
If you don't know what these are, or you rarely ever use them, then you really have no business using this kind of regex engine. (And if you are using them, then I'd argue you're shoving a bit too much logic into a regex, but that's beside the point). Nonetheless, every popular programming language (except Go[1]) has included an exponential backtracking regex implementation in their standard library, and exposed the entire industry to this stupidity, all for a few backreferences and lookahead assertions.
What's especially crazy is this: it's easy for a regex engine to detect the use of these constructs, because it has to parse the regex anyway! So it's feasible for the engine to optimistically try to use an efficient implementation, and only fall back to using a backtracking implementation when you're actually using these features. This is what the Python re2 module[3] does, it uses RE2 by default and supports falling back to the backtracking implementation if necessary.
Instead, we're stuck reading the same postmortem every few years describing how "catastrophic backtracking" ruined another company/person's day, when the problem has been solved for decades, and language/library creators have just failed to include that solution.
[1]: Rob Pike invented, or at least popularized, the algorithm used by RE2. He was also involved in the creation of Go, as was Russ Cox[2]. [2]: https://swtch.com/~rsc/regexp/ [3]: https://pypi.org/project/re2/
... and Rust. Although Rust doesn't have a regex library in std, the official regex crate (I am its author) descends from RE2[1].
> So it's feasible for the engine to optimistically try to use an efficient implementation
Feasible, sure. But not easy or simple. If Python's re2 module uses RE2 by default and Python's regex engine when necessary, then it's very likely that the match offsets it reports are not coherent. RE2 aims to be mostly consistent with things like PCRE, but there are cases where it isn't.
The problem is, building a production grade FSM regex engine or a production grade backtracking regex engine are both huge engineering projects. And there are few, if any, people that know how to do both. They both have their own little specialties and there isn't a ton of crossover among implementors of regex engines.
It's one of those ideas that sounds so stupidly obvious in practice, but when you actually sit down to engineer the thing, it's quite a bit harder than you might imagine.
> (And if you are using them, then I'd argue you're shoving a bit too much logic into a regex, but that's beside the point).
This kind of ignores the fact that regexes are often the interface to something else. If you have a full blown programming language at your fingertips, it's usually not hard to work around the absence of look-around or backreferences by, say, using a second regex or something. But when all you have available to you is, say, a blacklist and you get to provide the regexes to that blacklist, then a more expressive regex syntax becomes a lot more useful. See for example people already running into problems with Discord's new feature: https://github.com/rust-lang/regex/issues/127#issuecomment-1...
Of course, as I noted, it would be very inappropriate for Discord to permit non-regular regexes here. It's borderline already by permitting any regexes at all, because even FSMs have their pathological cases, albeit, not exponential. But if it's a tool you run on your local system? Sure, look-arounds become much more useful.
To be clear, I am pro-FSM and agree with you that they should really be the default regex engine everywhere. But instead, reality is indeed inverted, with backtracking being the default (almost) everywhere. But I wanted to pipe up about a few points that I think you might have not quite captured precisely.
> ... and Rust. Although Rust doesn't have a regex library in std, the official regex crate (I am its author) descends from RE2[1].
... and Tcl (see my earlier post). You might argue that Tcl is not popular but it still has a significant following.
>> (And if you are using them, then I'd argue you're shoving a bit too much logic into a regex, but that's beside the point).
> This kind of ignores the fact that regexes are often the interface to something else.
I will definitely admit to using the occasional assertion or backreference in grep or sed from time to time, so you make a good point about local tools too. I suppose I was thinking more in terms of programming APIs when I said this, and so keeping the standard library FSM-based would still apply here. I'd imagine that special-purpose text munging tools which care that much, will likely have their own engines anyway.
Thanks also for your work on the regex crate. I'm still dipping my toes into Rust but I'm glad to know there's an FSM-based default regex library!