Hacker News Reader

Comment by chubot | Hacker News Reader

Ha! The same bug happened internally at my company. In that case it was a regex matching a URL taking so much CPU as to cause a DOS of a proxy server. I won't be surprised if it's happened to someone here too.

This is very timely, because minutes ago, I made a link to Russ Cox's articles in my Kernighan awk repo:

https://github.com/andychu/bwk

https://swtch.com/~rsc/regexp/regexp1.html

If you are not familiar with this issue, basically Perl popularized bad computer science... "regexes" are not regular languages.

They say that this particular case triggered quadratic behavior, not exponential, but the point is that there is a linear time algorithm to do this.

The file b.c in the awk repo implements the linear time algorithm:

https://github.com/andychu/bwk/blob/master/b.c

(and rsc's site has some nice sample code too, as well as caveats with regard to capturing and so forth)

View on HN

The key quote here is:

"Regular expressions are one of computer science's shining examples of how using good theory leads to good programs ..."

"Today, regular expressions have also become a shining example of how ignoring good theory leads to bad programs. The regular expression implementations used by today's popular tools are significantly slower than the ones used in many of those thirty-year-old Unix tools."

The alarming thing is that regex are supposed to be compiled before use, and the class of expressions that need quadratic or exponential time is distinct from the class that needs linear time. Why don't these popular, widely-used regex implementations perform any optimizations?

It's a little unfair to complain that they're slower than 30 year old regex engines when the old regex engines were so feature limited that they were nearly useless.

They're only missing one feature: back references. This feature is not needed for the majority of regular expressions, so the 30 year old engines are actually remarkably useful and don't have these pathologies. And actually it was the introduction of back references (in Perl) that causes you to have to implement backtracking regular expression engines.

In addition to back references, Perl also has forward and back assertions, IF/ELSE, and recursion IIRC. I'm not sure if anyone actually USES those features, but they are there.

Python adopted back references as well as forward and back assertions, but not the other stuff.

Perl really turned regular expressions into something else entirely...

Yes, I forgot about assertions. I've never _really_ used them, but I remember they were useful once or twice when wrangling with a particularly ugly format problem.

FWIW, the conversion from NFA (non-deterministic, i.e. backtracking) to DFA (deterministic, linear time) can take exponential space. So there's another avenue for DDOS; it's a lot harder to exploit, though, because it requires the attacker to control the input (i.e. regular expression) to the NFA->DFA transformation, rather than merely provide a string that takes a long time for an NFA to recognize.

I'm actually not aware of any popular DFA based engines that suffer from this vulnerability. grep and RE2, for example, build the DFA lazily and cap the size of the DFA such that matching is still linear time even if generating the full DFA would take exponential space. (This is because at most one DFA state is generated for each byte in the input, so technically, you only ever need space for one or two states. In practice, you give a little more room to avoid constantly recomputing states, but it's still bounded.)

Random side note... Recognized your name, we use your TOML go package in a bunch of our tools. Thanks and keep up the great work!

There is a misunderstanding here -- NFA simulation is NOT backtracking. A NFA can be simulated in time LINEAR to the input length (holding the regex length as a constant). A DFA state corresponds to a set of NFA states. It is an additional optimization to convert NFA to DFA, but it just prevents doing repeated calculation -- it doesn't affect the computational complexity. Cox's articles address this and are quite lucid.

The problem is that the friedl O'Reilly book uses the terms NFA and DFA in a completely wrong and boneheaded way. I was confused by that book for awhile.

Only if you want to model it with every combination of states from the nfa getting one from the dfa. If you don't mind describing the current state as a list of potential states from the nfa, the conversion is linear space.

Usually there's no need to convert NFA to DFA. NFA can be simulated directly, i.e. by using bit vector instead of integer for state accounting. Also, no backtracking is necessary to simulate an NFA.

So you have the classic NFA and DFA engines, and these more modern NSH (non-deterministic space heater) engines.

At least they keep you warm. Sometimes.

How can it not be a feature that you can heat more space the more spaces you feed it?

> How can it not be a feature that you can heat more space the more spaces you feed it?

You just made my day. Thank you.

Unfortunately, there is a hint as to how this has happened:

"This strategy is no longer practical: users have come to rely on backreferences for at least occasional use, and backreferences are part of the POSIX standard for regular expressions."

What better excuse is there for a poor implementation than standards compliance? In many ways, using regex with backtracking by default is like programming in Lisp without tail-call optimizations. If the POSIX standard is going to require backreferences, then it should also require a non-backtracking implementation for regular expressions without backreferences, just like the Scheme specification requires implementations to support tail-call optimization.

The comparison is valid because they both can create a quadratic runtime from a linear time algorithm.

Yes, I recall that he talks about the multi-engine approach with respect to both PCRE and RE2 somewhere in these articles:

https://swtch.com/~rsc/regexp/

Sorry I don't have the exact reference handy. Apparently the author of PCRE tried to implement an NFA/DFA engine for some regexes as well. And I think RE2 might also have different strategies for different regexes as well, but I forget the details (it might be related to capturing).

> If the POSIX standard is going to require backreferences, then it should also require a non-backtracking implementation for regular expressions without backreferences

At least in some regexp engines, this is possible. There is a concept of possessive (as opposed to reluctant, or as it's often called, "non-greedy") quantifiers. Given the string "abb", consider the following regexes:

/[ab]+b/ -- matches "abb"

/[ab]+?b/ -- matches "ab"

/[ab]++b/ -- DOES NOT MATCH!! (Because there is no back-tracking.)

More info: http://www.regular-expressions.info/possessive.html

One regexp engine which implements this (see section 4): https://raw.githubusercontent.com/k-takata/Onigmo/master/doc... -- this is the engine used by modern Ruby versions.

The name regular expression seems meant to evoke regular languages, whose significance is that they can be recognized in a very straightforward way (by finite state automata) without pathological gotcha cases like this.

Perhaps we ought to call them irregular expressions - this kind of behavior is the literal antithesis of what regular means in automata/parsing theory.

The first non-boilerplate-header line in b.c:

    /* lasciate ogne speranza, voi ch'intrate. */

Well, that's encouraging...

("Abandon all hope, you who enter here.")

Admittedly I haven't stepped through all the code, but it's 958 lines and doesn't look horrible. It somewhat resembles the example C programs here:

https://swtch.com/~rsc/regexp/

In particular there don't seem to be crazy optimizations and non-portable stuff like you see in other production regex implementations and in interpreters. It's pure ANSI C.

The functions are all short -- no 1000 line monsters like I've seen in a lot of old C code lately.

The rsc example code is actually a great example of using pointers in C. People rightly avoid lots of raw pointers for application code, but for this use case, they yield compact and elegant code.

There's a simple trick the real-time and high-assurance communities use to catch stuff like this: enforce a hard limit for time each task takes to complete. Some you might give leeway to prevent DDOS'ing your users. Many (most?) things have a sane, hard limit that can apply along with a log entry or notification to ops. Keeps one user or task from DDOSing whole system or forces it to fail fast + noticeably.

Note a lot of developers use this trick anymore but it's quite powerful. Should get more consideration. Not to mention the real solution of choosing tools or algorithms with predictable, reliable behavior. Those definitely exist for the task they're performing as other commenters noted.

EDIT to add modern example from high-assurance field that shows how awesome it can be (esp see Github link):

https://leepike.github.io/Copilot/

You can only safely abort a "task" if the task has specifically be designed that way, or if the task is a process.

Which is of course part of his point. Anything that processes arbitrary user input should be designed in a way that is abortable in some way. As this particular case shows even the attempts to sanitize input can be vectors for a DOS against them.

It's why you use isolation techniques outside that code as the fall-back. Simplest forms I saw involved while loops counting downward and threads that got interrupted to assess things.

Everything processes user input. Whether a numeric user id or some text.

That's going a bit far. User input is usually handled by a small percentage of modules. Those should guard against malicious or faulty input where possible.

That's not even the issue here, though. The issue is tgat the input is processed via an algorithm thst is easy to hang and/or format that's hard to parse. On top of that, no isolation or monitor to catch the fault. Each of these can be done differently... are in many programs... to avoid or better mitigate such risks. Developers often dont.

For the specific example, this is how I dealt with a situation in one service I wrote that takes an arbitrary user-controlled regex (for search).

The program was written in python, and as it turns out the GIL prevents a thread from being able to interrupt another thread that's doing a re.match() call - the entire regex engine is in C so the GIL is held for the entire call.

My solution was to use SIGALRM to set a timer before calling, and have the signal handler raise an exception. This causes the regex call to raise that exception, which I then catch and display an appropriate error.

Since those all have a lot more code than is needed to show the basic idea of an NFA-based matcher: https://github.com/darius/sketchbook/blob/master/regex/nfa_s...

Sadly not much Thompson's libraries are implemented. I have tried to find one for F# but are just toy projects.

It doesn't actually take that many lines of code to implement a linear time NFA engine. Most of the code is actually in the regex compiler. That is, there are only a few actual "instructions" or node types in a regex engine (alternation, concatenation, etc.). The rest is just compiling the bizarre syntax to a those nodes/instructions. (And dealing with Unicode if you need that.)

The whole awk implementation is 958 lines, so it can't be that bad. It supports a fairly featureful regex language (though no capturing AFAICT).

I'd look at GNU sed if you wanted a very featureful substitution engine that IIRC is also linear time.

Hm it seems to be a copy of the GNU libc regex engine. And coreutils, grep, and awk also package the same engine in user space! That's really annoying.

But yes it looks like it uses a struct re_dfa_t for matching, and some special flags for backreferences? That seems to indicate that they are using linear time maybe with a fallback? Hm.

I think the general turn of events was that libc supported BRE at first, which was implemented using the DFA algorithm. Then Perl implemented a backtracking engine and Perl syntax for REs, and Python/Ruby/etc. wanted to be compatible with Perl, so they also implemented backtracking as well. Because Perl has other features like forward and back assertions that require backtracking.

And then perhaps libc got EREs with backreferences which they bolted onto the existing infrastructure?

Anyway, thanks for the pointer... I may look into these more in the future.

musl libc also uses the TRE regex engine, which apparently uses the DFA algorithm.

if is that "simple" why then are few? Or is because I don't know where to look at?

Maybe regex are just enough and few bother to have something faster?

I have found some start code at https://t0yv0.blogspot.com/2011/02/home-made-regular-express.... The thing is that I don't know how much else is necessary to have a well made library...

Reply on news.ycombinator.com