Live data from Hacker News

Regex: badly needs fuzzing

svn.boost.org

121–130 of 180 posts

Re: Regex: badly needs fuzzing

#121

Earlier quoted context omitted.

All regexes run in O(N) where N is the length of the string matched. But some regex engines accept non-regular expressions. [0] The usual notation for it is an escaped number: \1 or \2 or so on. They're used to refer back to capturing groups earlier in the expression, usually marked by parentheses. Regular expressions don't have backreferences but various enhanced expressions add them. If you use those extensions, yo…

It's worth pointing out that if you're using a regex engine that only uses backtracking, then you can't assume all regular expressions take linear time. For example, running `(a ) c` against `aaaaaaaaaa` takes exponential time in the number of `a` characters even though it is regular. A hybrid regular expression engine could, in theory, recognize that a particular expression is regular and therefore use a finite stat…

But unfortunately, converting a non-deteministic finite automaton (i.e., regexp) to a deterministic finite automaton (i.e., engine that can do matches in linear time) may take exponential time and/or space.

Yet, I should add, flex does that with extraordinary success. Most grammars are not that bad, it seems.

Re: Regex: badly needs fuzzing

#122
post #71

Earlier quoted context omitted.

pcwalton is not framing the problem in a particularly useful way. This is a question of risk management and his argument is basically that one should always reduce the risk of memory management errors to zero. Others say that they can tolerate some risk, as long as it's in acceptable margins, since it's expensive to totally eliminate it. I don't think that lecturing everyone "No, you really want to have 0 risk, you f…

> This is a question of risk management and his argument is basically that one should always reduce the risk of memory management errors to zero. No, that's not my argument. > Others say that they can tolerate some risk, as long as it's in acceptable margins, since it's expensive to totally eliminate it. These flaws are not "in acceptable margins". They were numerous and were found the instant Dmitry Vyukov turned a…

I wasn't talking about a specific example or these particular flaws, but in general, because this is just an instance of your generic argument that modern C++ is unsafe, where "unsafe" means not verifiably memory-safe.

That's correct, but you are framing the problem in an unrealistic way in which Rust wins by default. In reality, this type of memory-safety guarantees will be evaluated against other concerns and those other concerns might be more important.

For you memory-safety errors are unacceptable, that much is clear. For many they are more or less acceptable and insisting that they're unacceptable won't make them change their minds.

Re: Regex: badly needs fuzzing

#123
post #103

Earlier quoted context omitted.

> If your regex has backreferences, or look-ahead/look-behind assertions, or similar things, then your regex engine must support a backtracking strategy. There's a morphism that maps Phritzy's pattern to an equivalent pattern that can be matched with a Thompson NFA. (It's a similar strategy to the one that allows you to take an NFA and turn it into a DFA.) You can perform a sort of "static decomposition" on a subset…

> But saying that backreferences cannot be supported by a pattern matching engine that uses something other than backtracking is like saying that because there is no general algorithm no prove any given program P halts, then no program can be proven to halt. But that's trivially demonstrated to be untrue. ∃ ≠ ∀ Yeah, sorry, I mixed up the sense of the quantifiers a bit. More accurately: "If you are interested in rege…

I did something similar for word boundary zero-width assertions (i.e. \b and \B); that is, rewrite the PCRE by expanding permutations inline. The purpose was to compile as many PCREs as possible to DFAs using Ragel.

Fortunately, Ragel supported a limited form of assertions called semantic conditions, which it implements by expanding the code space of each state and allows you to associate a C boolean expression as a predicate for entering that state. For various reasons the semantic condition needed to be attached to a terminal, not to subexpressions (i.e. groupings and alternations).

Also, expressions like (cat?|dog?)\b needed to be permuted similar to the backreference problem, resulting in something that might look like (ca\b|cat\b|do\b|dog\b). This strategy didn't work for kleene stars (*), but usually a semantic condition could be attached to trailing terminals instead of leading terminals.

The actual code to perform these AST transformations was surprisingly simple. Excluding parsing of PCREs into an annotated AST and generation of the code, less than 200 lines of Lua code, maybe.

The PCREs weren't simple, but most were only moderately complex. For a corpus of about 10,000 PCREs about 1/2 used word boundary assertions. The vast majority of those (possibly even all of them... I can't remember) could be successfully transformed. With nested subexpressions (groups, alternations) the number of permutations rapidly grows, but I don't think our production corpus ever caused a problem in that regard, and only the most insane regular expressions nest subexpressions more than a few deep.

Before we tackled back references and other gnarly PCRE features I think we managed to coax better than 90% of our PCRE corpus to transform into semantically equivalent Ragel-based DFAs. In other words, back references were rare. With 90%+ compiled completely to native machine code and the remainder simplified into prefilters we saw greater than 10x performance improvement (> 1000%) over libpcre in terms of production throughput, not just benchmarks. (Ragel is awesome!) RE2 was usually faster than libpcre, but RE2's performance wasn't even remotely in the same league as the native machine code DFA Ragel produced, so I quickly ditched the idea of using RE2 anywhere in the pipeline.

That last 10% or so took much longer to tackle, and eventually most of my original code was dumped. But getting to about 90% was surprisingly easy. We did eventually get (and continue to maintain) 100% transformation to native machine code, but a small percentage still require backtracking. All-in-all I _think_ we're at 20x to 30x over baseline libpcre; that is, tacking the last 10% put us 2x or 3x atop the 10x. It wasn't a simple case of diminishing returns as the most difficult expressions to transform also tended to be the most costly at runtime, but if we had stopped early on at 90% it still would have been a resounding success.

Regarding RE2, it's important to note once an expression was transformed into a proper regular expression, they could be easily joined into a single union. Setting aside the bytecode vs machine code differences, RE2 just isn't capable of compiling huge unions of expressions (on the order of 100s or 1000s), whereas for Ragel it was a relative breeze. Another team was using re2c (not RE2) for a project, and it turned out that what it literally took re2c DAYS to compile only took SECONDS for Ragel to compile. GCC and clang also became bottlenecks compiling the Ragel generated code. And interestingly they both, coincidentally, exhibited (and still exhibit, AFAIK) quadratic complexity when parsing certain C constructs, such as initializer lists. So that necessitated some workarounds.

Re: Regex: badly needs fuzzing

#124

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!

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/

Re: Regex: badly needs fuzzing

#125
post #103

Earlier quoted context omitted.

> If your regex has backreferences, or look-ahead/look-behind assertions, or similar things, then your regex engine must support a backtracking strategy. There's a morphism that maps Phritzy's pattern to an equivalent pattern that can be matched with a Thompson NFA. (It's a similar strategy to the one that allows you to take an NFA and turn it into a DFA.) You can perform a sort of "static decomposition" on a subset…

> But saying that backreferences cannot be supported by a pattern matching engine that uses something other than backtracking is like saying that because there is no general algorithm no prove any given program P halts, then no program can be proven to halt. But that's trivially demonstrated to be untrue. ∃ ≠ ∀ Yeah, sorry, I mixed up the sense of the quantifiers a bit. More accurately: "If you are interested in rege…

You can run into similar theoretical worst-case problems as what can happen when trying to conversion for arbitrary NFA -> DFA. See beeforpork's comment:

https://news.ycombinator.com/item?id=13603461

You'd want to target a restricted subset containing patterns that use only certain "tractable", er... motifs.[1] It would make for an interesting project. Specifically, how much you have to restrict yourself in your focus while still aiming to produce something that's useful. I'm not going to pretend that I've got an up-to-date perspective that includes all available research in this area. Something like this may have already been done.

1. For lack of a better word. (I'm trying to avoid using the word "pattern" multiple times in the same sentence, where each has a different meaning.)

Re: Regex: badly needs fuzzing

#126
post #61
post #19

Earlier quoted context omitted.

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/p…

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 a…

The regex-dna benchmark biases toward regex engines with aggressive literal optimizations. Namely, there are 21 distinct regexes in the benchmark. Of those 21, only 1 of them actually uses Rust's core regex engine. The rest are compiled down to literal searches. Even in that one case, literal optimizations are used to speed it up.

I'm not familiar with Tcl's engine, but if it also applies aggressive literal optimizations, then that could explain its performance. However, given a more fine-grained analysis of regex-dna[1], that seems unlikely. The C program is large, so perhaps there is more to it than meets the eye.

The perf difference between PHP w/ PCRE and C w/ PCRE has always perplexed me. But there are... so many variables. Maybe PHP enables JIT in PCRE (the C program does not), or perhaps PHP's preg_replace is doing something clever, e.g., by combining all of the replacement regexes into one.[2]

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

Indeed. The regex-dna benchmark does not require any Unicode handling at all. It's a strictly ASCII based benchmark.

If your regex engine uses finite state machines, then one can typically build your encoding into the machines themselves, which results in little or no performance degradation in matching in the common case. (The cases where it matters is if your regex is large, e.g., `\pL{100}` is large indeed.)

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

[2] - https://github.com/rust-lang/regex/blob/master/examples/shoo...

Re: Regex: badly needs fuzzing

#127
post #123
post #103

Earlier quoted context omitted.

> But saying that backreferences cannot be supported by a pattern matching engine that uses something other than backtracking is like saying that because there is no general algorithm no prove any given program P halts, then no program can be proven to halt. But that's trivially demonstrated to be untrue. ∃ ≠ ∀ Yeah, sorry, I mixed up the sense of the quantifiers a bit. More accurately: "If you are interested in rege…

I did something similar for word boundary zero-width assertions (i.e. \b and \B); that is, rewrite the PCRE by expanding permutations inline. The purpose was to compile as many PCREs as possible to DFAs using Ragel. Fortunately, Ragel supported a limited form of assertions called semantic conditions, which it implements by expanding the code space of each state and allows you to associate a C boolean expression as a…

Neat! What was the application? Or was it pure research?

Re: Regex: badly needs fuzzing

#128
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.

Re: Regex: badly needs fuzzing

#129

Earlier quoted context omitted.

It's worth pointing out that if you're using a regex engine that only uses backtracking, then you can't assume all regular expressions take linear time. For example, running `(a ) c` against `aaaaaaaaaa` takes exponential time in the number of `a` characters even though it is regular. A hybrid regular expression engine could, in theory, recognize that a particular expression is regular and therefore use a finite stat…

But unfortunately, converting a non-deteministic finite automaton (i.e., regexp) to a deterministic finite automaton (i.e., engine that can do matches in linear time) may take exponential time and/or space. Yet, I should add, flex does that with extraordinary success. Most grammars are not that bad, it seems.

Executing an NFA on search text takes linear time and space, so what I said is true. ;-) In practice, it is hard to make NFA execution as fast as backtracking engines. (PCRE famously implements an NFA, calls it a DFA, and uses that to declare that the DFA engine is slow, which is incredibly misleading.[1] Thank you, Mr. Friedl. sigh)

Production grade regex engines with a DFA (like GNU grep, RE2 and Rust's) do conversion lazily. By doing it lazily, at most one new DFA state is added for each byte in the input in the worst case, which maintains the linear time bound. Unfortunately, this can result in memory growth proportional to the search text, which is why all such implementations use a fixed-size cache of states that is flushed once it's full. It works well in practice, but can slow down dramatically (to about the speed of an NFA) if the cache of states needs to be flushed frequently. The most common provoker of such behavior is large counted repetitions, e.g., `\pL{100}`.

[1] - http://pcre.org/current/doc/html/pcre2matching.html#SEC4

Re: Regex: badly needs fuzzing

#130

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

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.
Post reply on HN