Regex: badly needs fuzzing

https://svn.boost.org/trac/boost/ticket/12818

by infogulch • 9 years ago

193 166 9 years ago

svn.boost.org

pcwalton9• 9 years ago

Another counterexample to the idea that modern C++ written by experts is free of memory safety issues.

If the solution doesnt make it any easier to avoid memory issues (just forces you to avoid them,) its not an attractive solution

gcp3• 9 years ago

Given that we're talking about bugs, I don't think this is a valid argument. Being forced to avoid bugs is good, yes? Even if it's not necessarily less hard to make them in the first place (which is arguable, too!).

I mean, I spend most of my time coding searching for bugs, not avoiding them.

pcwalton9• 9 years ago

I disagree? It's better to not have memory safety problems than to have them!

amalag3• 9 years ago

Avoiding bugs is a pretty effective way to not have bugs.

_delirium• 9 years ago

Not that I necessarily think it'd avoid the problem even then, but I wouldn't call this modern C++ exactly. For one thing, it's (c) 2002, so written in C++98. And for another, it looks very uh, C-ish (not that uncommon in the C++98 era). In the bad sense of lots of error-prone pointer-based string manipulation, stuff like this:

    if(STR_COMP(s1, p) >= 0)
    {
       do{ ++p; }while(*p);
       ++p;
       if(STR_COMP(s1, p) <= 0)
          return set_->isnot ? next : ++next;
    }

sidlls3• 9 years ago

Well, yes if the strawman "all modern C++ written by experts is free from memory safety issues" is what you're countering. I find that to be gratuitous and petty, and not a good representation of Rust, however.

10293101• 9 years ago

The position "modern C++ is safe and all C programmers are idiots" is repeated quite often here on HN.

To be fair, it is always the same small group of people who do that.

pcwalton9• 9 years ago

Well, yes if the strawman "all modern C++ written by experts is free from memory safety issues" is what you're countering.

Well, I have seen exactly that sentiment. But, more importantly, this isn't exactly an obscure memory safety issue. It's a huge collection of flaws that showed up the instant Dmitry Vyukov threw a fuzzer at it. It's not just "all expertly-written C++ is free of memory safety issues" that this is a counterexample to: it's also a counterexample to "most C++ written by experts doesn't have memory safety issues that matter in practice".

I find that to be gratuitous and petty, and not a good representation of Rust, however.

I haven't brought up Rust here. You can eliminate the memory safety issues by writing in Go, or Java, or C#, etc. etc.

andrepd• 9 years ago

It's not modern, it's C++98.

stinos• 9 years ago

Do you have more of these examples?

anon1385• 9 years ago

http://www.cvedetails.com/vulnerability-list/vendor_id-452/p...

ambrop7• 9 years ago

If it has memory safety issues then it's not written by experts :)

dbaupp6• 9 years ago

So there's no such thing as a C++ expert? That statement is dangerously close to a No True Scotsman: IME even people who seem to fit any reasonable definition of expert (committee members, compiler developers) still make memory-safety mistakes.

ska• 9 years ago

Ignoring the straw man, can you explain how c++98 code provides a counterexample for anything in modern c++?

mackal• 9 years ago

This isn't modern c++, but whatever.

randyrand3• 9 years ago

No, but not everything needs to be memory safe. That's what the kernel is there for. You can typically just restart the program.

The classic program safety vs programmer time tradeoff.

AaronFriel• 9 years ago

If your program isn't memory safe, it's very often the case that someone can make your program run their program, at which point the kernel doesn't know that your program didn't intend to modify itself.

W^X/NX bits and other technologies don't totally obviate the issue, as ROP gadgets can be used to defeat it. And so on, there's a whole domain of computer science dedicated to that arms race and no evidence that it's stopping any time soon.

On the other hand, a Rust program without unsafe should simply never execute code outside of its defined control flow, it's not possible to hijack any control flow on the stack or heap, and so a running program under arbitrary user input can only ever explore execution paths that exist in the absence of memory unsafety. No ROP gadgets or heap/stack smashing, no overflows leading to overwriting a function definition in memory, no overwriting the parameters of a function to cause impossible branches to be taken, and so on.

pcwalton9• 9 years ago

No, but not everything needs to be memory safe. That's what the kernel is there for.

The kernel doesn't automatically defend against RCE.

jasode• 9 years ago

Maybe you're right that it's wrong to think that modern C++17 (unique_ptr, shared_ptr) written by experts is free of memory safety issues.

But in this specific case, it looks like old code from 2002[1]. No modern techniques such as std:unique_ptr. Just 1970s C style raw pointer manipulation. I suppose the contemporaneous compiler used by John Maddock would have been C++98?!?

[1] one example of a source file mentioned by the bug report: http://www.boost.org/doc/libs/1_63_0/boost/regex/v4/perl_mat...

dnljms• 9 years ago

The main windows compiler would have been Visual C++ 6, which was released before standardization, and had notable differences from C++98. It was also buggy for non-trivial templates. Visual C++ 2002 wasn't much better.

acconsta• 9 years ago

modern C++

This library is old enough to drive...

gok• 9 years ago

I don't fundamentally disagree with you (any C++ bigger than a screenful of code probably has memory safety issues) but contrary to its reputation, I've find Boost to be of really poor code quality.

tonyedgecombe• 9 years ago

I've find Boost to be of really poor code quality

Which is telling because it's raison d'etre is quality and it was written by some pretty smart people.

flukus• 9 years ago

modern C++ written by experts is free of memory safety issues

Which simply isn't good enough, it takes 10+ years to become expert level at anything, so what are people supposed to do to get to that level?

nix0n2• 9 years ago

Google's cache of this bug (loads quite slowly for some reason):

https://webcache.googleusercontent.com/search?q=cache:mVrrFL...

amalag3• 9 years ago

Text only link: http://webcache.googleusercontent.com/search?q=cache:https:/...

zao• 9 years ago

The trac instance (and legacy SVN server) isn't really designed for slashdot (well, HN) effect traffic, runs on some jiggly piece of rust at some uni somewhere.

nix0n2• 9 years ago

I was commenting on the loadtime of the cached page (amalag found the solution).

CJefferson• 9 years ago

Any rust lovers out there: Could I ask you do a benchmark comparison and a fuzz comparison. I'd be genuinely interested in the result and if (as you might hope) the Rust::regex is as fast as boost:regex, and never crashes, that would persuade at least me to finally learn some Rust!

gcp3• 9 years ago

The Rust regex library is written by the same guy who wrote ripgrep. I'd be surprised if it didn't run circles around boost::regex.

stuckagain4• 9 years ago

If you were interested in performance you probably would not have been using boost::regex to begin with. RE2 is often an order of magnitude faster. You might choose boost if you require backtracking, but that's crazy anyway due to exponential time.

0xFFC• 9 years ago

What is backtracking?

flogic• 9 years ago

In my experience, the exponential time thing isn't really a big deal. I've used Perl regular expressions on a very regular basis for about 16 years now. Exponential time has been an issue only once. Obviously if I were accepting regular expressions from random people, I'd use RE2. But for my day to day purposes, it's pretty much a complete non issue.

slavik81• 9 years ago

Is there a quick and easy way to check if a particular regex could take exponential time?

zintinio52• 9 years ago

From my understanding the main benefit of RE2 is not speed, but linearly scaling execution time with respect to the input size, along with bounded memory usage. For certain inputs, it may outperform other engines, but the converse may also be true. As with any feature that may be abused, backtracking may also be useful: for example, you may need to write a script to munge text. Since you're not exposing it to arbitrary user input, it's a reasonable feature.

gpm• 9 years ago

You can look at a well known (but not very complete) benchmark comparison here [0], rust wins, the fastest boost program is c++ g++ #3 and takes 8.5 times as long, the fastest c++ implementation (using re2) takes twice as long.

I don't know of a fuzz comparison, but there has been fuzzing done on the rust library without finding anything bad, e.g. see this issue [1].

[0] http://benchmarksgame.alioth.debian.org/u64q/performance.php...

[1] https://github.com/rust-lang/regex/issues/203

justinmk• 9 years ago

benchmark comparison here [0], rust wins, the fastest boost program is c++ g++ #3 and takes 8.5 times as long

With PHP at #2? Doesn't seem credible, or the thing being tested isn't meaningfully language-dependent.

wbond• 9 years ago

Considering the C implementation using PCRE is 4.1x Rust, whereas PHP (implemented in C, also using PCRE) is 1.2x Rust, that makes me think that this benchmark is… unhelpful at best.

The fastest C implementation uses TCL’s simplified regexes. However, http://lh3lh3.users.sourceforge.net/reb.shtml indicates that they found generally oniguruma and re2 trounce TCL.

Some other comparisons of regex engine performance is at http://sljit.sourceforge.net/regex_perf.html. Unfortunately neither of these are new enough to include Rust.

One of the big pieces that can easily be glossed over, especially during performance comparisons, is unicode handling.

kibwen3• 9 years ago

Issue 203 indicates that the fuzzing was done, but doesn't link to the issues that were uncovered by fuzzing. The PR at https://github.com/rust-lang/regex/pull/262 does: one infinite loop, four panics, and one instance of the NFA reporting the wrong position of a match.

thomasahle• 9 years ago

Regex seems to be one of the big strengths of Rust, performance wise: https://benchmarksgame.alioth.debian.org/u64q/performance.ph... (C++ g++ #4 uses Boost)

dikaiosune• 9 years ago

It does look like the afl.rs project (afl for rust code) has been run on regex:

https://github.com/frewsxcv/afl.rs#trophy-case

Which resulted in just one issue? I'm not sure how long they fuzzed or what the methodology was, but this was the panic they found (still not a memory safety issue, more akin to an unchecked exception in Java than a crash in C++):

https://github.com/rust-lang/regex/issues/84

Since that issue is from the same time as Rust's 1.0 release, I suspect that either it hasn't been run again recently or that things are pretty stable in the regex crate w.r.t. fuzzing.

mastax• 9 years ago

Also more recently: https://github.com/rust-lang/regex/pull/262

PudgePacket• 9 years ago

It's not related to fuzzing but this article is definitely an interesting one that involved a lot of regex in rust http://blog.burntsushi.net/ripgrep/.

burntsushi5• 9 years ago

As others have mentioned, Rust's regex library has been fuzz tested. Most of the bugs have been fixed. There are a couple outstanding that I hope to get to soon. None of them have been unsafe memory bugs. :-)

Benchmarking is a bit mirkier. The benchmark game has already been linked, but the regex-dna benchmark can't really be used to judge the overall performance of regex engines. It's not that the regex-dna benchmark is bad on its own, but rather, it's not enough. You need more coverage. For example, regex engines with aggressive literal optimizations will do very well on regex-dna.

Rust's regex library does have a benchmark harness that compares it to many other popular regex engines: PCRE1 w/ JIT, PCRE2 w/ JIT, RE2, Tcl's engine and Oniguruma. In general, Rust's regex engine is competitive with PCRE{1,2} and RE2, but does quite a bit better than both Tcl and Oniguruma. I haven't added Boost to this harness, but in theory it would be relatively easy. You can see how I did it for RE2[1].

Unfortunately, the set of benchmarks in the harness---while probably better than any other benchmark I've seen---has two major problems with it:

1. It is biased. I wrote most of the benchmarks and I'm not terribly familiar with the types of optimizations performed by sophisticated backtracking engines. Moreover, many of the benchmarks were added to measure optimizations I added to Rust's regex engine, so there will naturally be more benchmarks where Rust does well.

2. The benchmarks themselves lack analysis. Microbenchmarks are too hard to interpret using numbers alone. Someone needs to do the work to explain the results. I've always intended to do this, but it is a gargantuan task.

I've just updated the repo to contain the benchmark results as of today[2]. The most interesting comparison is PCRE2, which is quite fast.[3] Most of the interesting benchmarks are defined in sherlock.rs[4], which also contains some Rust specific notes.

Another source of benchmarks is my blog post on ripgrep[5]. This isn't really a benchmark for regex engines, but rather, a benchmark for line oriented search tools. Nevertheless, it is a collection of data points.

[1] https://github.com/rust-lang/regex/blob/master/bench/src/ffi...

[2] https://github.com/rust-lang/regex/tree/master/bench/log/05

[3] https://github.com/rust-lang/regex/blob/master/bench/log/05/...

[4] https://github.com/rust-lang/regex/blob/master/bench/src/she...

[5] http://blog.burntsushi.net/ripgrep/

revelation2• 9 years ago

They seem to be fuzzing the regex, not just the input it is applied to. This may or may not change the results, but if you're allowing users to input arbitrary regex patterns you have a whole lot of other problems.

gcp3• 9 years ago

Huh? It would be perfectly valid to have it power the regex part of the scripting engine in a browser, for example. If that would then lead to memory safety errors, you just got yourself a 0-day.

Regex engines used in browsers are both fast and hardened against these attacks.

Houshalter• 9 years ago

Finding vulnerabilities in existing regexes would be significantly more dangerous/interesting though. Like say if an exploit was found that could be triggered with a carefully crafted input to an email validator. Half of the servers on the web would be vulnerable! See e.g. https://en.wikipedia.org/wiki/ReDoS

If you have to be able to run an arbitrary regex on the victim's machine, that makes it much more limited. You shouldn't be letting users access regex any more than you should let them execute arbitrary code. Sure browsers do both of those things. But only through monumental effort that shouldn't be expected everywhere else.

AgentME• 9 years ago

I've seen plenty of places that you may want to accept an arbitrary regex from the user. An app could allow the user to set up a filter for messages or usernames by putting in a regex. Or an interpreter for a sandboxed language could provide regex support.

revelation2• 9 years ago

All manner of problems in the programmers mind become trivial if only we allow users to input essentially code to express exactly what they want. Of course this is basically never a good solution.

The issue with allowing arbitrary regex patterns is DoS through exponential blowup. But if you allow running code anyway you might not very much care for that.

kuschku• 9 years ago

Or the ignore rule in an IRC client. The input pattern of a log filter. Etc.

Someone12343• 9 years ago

if you're allowing users to input arbitrary regex patterns you have a whole lot of other problems.

Why? I am legitimately asking, you say that like it is meant to be obvious or common knowledge. But many regular expression engines are self contained entities that can crash but cannot expose information or poison other parts of the program.

A DoS-like attack might be an argument against unfettered user inputed regular expressions. But that off the top of my head is the only BIG risk. Particularly in secure-by-design languages like Java, C#, and Rust.

Twirrim• 9 years ago

It would be easy to create a regex that consumes a lot of CPU power. It's very difficult to vet a regex in an automated fashion.

ZoFreX2• 9 years ago

Allowing users to enter regular expressions is definitely something that should only be entered into with caution. It is effectively code in a programming language that will be run, after all.

For example, it means their input needs parsing - and parsing is very hard to get right and frequently results in exploitable bugs. There are also potential problems where regexps could take a very long time to execute, which could be a denial of service issue.

jimrandomh• 9 years ago

Practical upshot: do not feed untrusted regexes into boost::regex.

jvoorhis• 9 years ago

Or any untrusted user input for that matter?

Groxx2• 9 years ago

Untrusted regexes to anything, where possible. There are fairly well-known ways to use those to run a DoS: https://en.wikipedia.org/wiki/ReDoS

stuckagain4• 9 years ago

I take it you don't use a web browser?

kibwen3• 9 years ago

Note that it is possible to design regex engines that deliberately avoid these pitfalls (e.g. RE2, which was originally written for Google Code Search, as well as Go's regex engine (written by the RE2 author) and Rust's regex engine). The downside is that these engines are forced to disallow certain exploitable features, such as backtracking.

foota• 9 years ago

This is your reminder to treat a regex with similar scrutiny as eval.

darfs• 9 years ago

Am i the only one, who get slowly angry about that "Use $language but Not this One"-comments? I don't see much value in such comments, srsly.

Why don't accept the fact someone decided to write $it, and move on with usefull comments? Enough hn this today.

davb• 9 years ago

Yes, I had a similar thought.

The top two comment chains right now are (to paraphrase) "See, modern C++ isn't free of memory issues" and "Maybe we should rewrite it in Rust and compare".

burntsushi5• 9 years ago

"Maybe we should rewrite it in Rust and compare"

That already happened, almost three years ago.

It's an interesting comparison point. The OP contains memory corruption bugs in C++'s standard regex library. If Rust claims to prevent these kinds of bugs, does it actually hold up to scrutiny? One way of testing that is throwing a fuzzer against a regex library written in Rust.

Retra• 9 years ago

What comment would you think is useful, and why not make that one instead?

donovanm• 9 years ago

Hmm makes me wonder what the result of running this fuzzing test on other regex libraries would be.

moosingin3space2• 9 years ago

Rust's regex crate has fuzzing running against it, and that has lead to a lot of useful small fixes: https://github.com/rust-lang/regex/pull/262

hannob• 9 years ago

pcre has been fuzzed by quite a few people a while ago, I remember also having reported a couple of issues. When I tested re2 nothing showed up. oniguruma also had quite a few issues, I tested it with libfuzzer lately. But everything should be fixed now.

saywatnow• 9 years ago

Badly needs static analysis. coverity is free for open source projects, will find many of the same issues, and produces reports that directly identify the buggy code, rather than the crash which might come thousands of instructions later in a completely different layer, requiring extensive reverse engineering to identify the source. And then when you've fixed one, the other test cases all need to be re-tested because they might have come from the same root cause, despite crashing in different locations.

Particularly when the hit rate is very high, fuzzing is a stupidly inefficient way to find bugs.

daurnimator• 9 years ago

I've found coverity to be very hard to set up with a normal developer workflow on github. ==> I think I've given up on it 3 times.

Do you have any guidance around getting it to work?

MaulingMonkey• 9 years ago

Needs both.

rather than the crash which might [...]

Assert like mad. Break out your debug allocators, your asan, your checked iterators. Fuzzing can be as bad as you say, but it can also give you extremely easy to diagnose repro cases - and catch an incredibly wide range of issues for incredibly little work, in my experience.

Static analysis generally won't tell you "Hey, if I almost-but-not-quite exhaust your address space allocating to successfully parsing this file, I can get your next closed-source API call to segfault!" - useful for tracking down each and every possible allocation related to networking deserialization so you can configure sane quotas (such as "array size probably shouldn't be larger than bytes sent, bail out safely instead of trying to allocate that")

With most sane setups that come to mind, no false positives either.

And then when you've fixed one, the other test cases all need to be re-tested because they might have come from the same root cause, despite crashing in different locations.

Your tooling should do this automatically for you. If it doesn't, get better tooling. AFL. SDL MiniFuzz. Whatever floats your boat.

Particularly when the hit rate is very high, fuzzing is a stupidly inefficient way to find bugs.

I've had it be stupidly efficient in terms of programmer time once setup. Occasionally leaving my computer on overnight? Worth.

luckystartup• 9 years ago

Is it true that most of these bugs wouldn't be possible in Rust? I think Rust might have solved:

heap-buffer-overflows, stack overflow, use of uninitialized data, SIGSEGV, undefined shift, invalid enum value, memory leaks

I don't think Rust can protect you from infinite loops. And of course, actual logic bugs where the output is incorrect (including "assert failures").

amalag3• 9 years ago

I don't think Rust can protect you from infinite loops.

That is the Turing Halting Problem!

Regex: badly needs fuzzing

Related Stories