6 ms·

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'

by chubot 10y ago

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://github.com/andychu/bwk https://swtch.com/~rsc/regexp/regexp1.html 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 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)

abecedarius 10y ago
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_simplest.py https://github.com/darius/sketchbook/blob/master/regex/nfa_s...
mamcx 10y ago
Sadly not much Thompson's libraries are implemented. I have tried to find one for F# but are just toy projects.
- chubot 10y ago
  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).
  - cyphar 10y ago
    I'd look at GNU sed if you wanted a very featureful substitution engine that IIRC is also linear time.
    - chubot 10y ago
      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.
  - mamcx 10y ago
    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-expressions-in-f.html 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...
xigency 10y ago
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?
- jandrese 10y ago
  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.
  - deleted 10y ago
    [deleted]
  - cyphar 10y ago
    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.
    - chubot 10y ago
      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...
      - 10y ago
throwanem 10y ago
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.")
- chubot 10y ago
  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/ 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.
nickpsecurity 10y ago
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/ https://leepike.github.io/Copilot/
- paulddraper 10y ago
  You can only safely abort a "task" if the task has specifically be designed that way, or if the task is a process.
  - zaphar 10y ago
    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.
    - nickpsecurity 10y ago
      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.
    - paulddraper 10y ago
      Everything processes user input. Whether a numeric user id or some text.

by chubot 10y ago

abecedarius 10y ago

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_simplest.py https://github.com/darius/sketchbook/blob/master/regex/nfa_s...

mamcx 10y ago

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

chubot 10y ago
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).
- cyphar 10y ago
  I'd look at GNU sed if you wanted a very featureful substitution engine that IIRC is also linear time.
  - chubot 10y ago
    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.
- mamcx 10y ago
  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-expressions-in-f.html 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...

xigency 10y ago

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?

jandrese 10y ago
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.
- deleted 10y ago
  [deleted]
- cyphar 10y ago
  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.
  - chubot 10y ago
    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...
    - 10y ago

throwanem 10y ago

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.")

chubot 10y ago
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/ 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.

nickpsecurity 10y ago

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/ https://leepike.github.io/Copilot/

paulddraper 10y ago
You can only safely abort a "task" if the task has specifically be designed that way, or if the task is a process.
- zaphar 10y ago
  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.
  - nickpsecurity 10y ago
    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.
  - paulddraper 10y ago
    Everything processes user input. Whether a numeric user id or some text.