Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Regex: badly needs fuzzing

svn.boost.org

Post reply on HN
Print view View original

61–70 of 180 posts

Re: Regex: badly needs fuzzing

#61

Post by wbond »

gpm wrote: post #19
CJefferson wrote: post #7

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!

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

Re: Regex: badly needs fuzzing

#62

Post by eridius »

ue_ wrote: post #56
stuckagain wrote: post #51

Earlier quoted context omitted.

There are features of some regular expressions for which the only known solution is backtracking. If you want those features then you "require backtracking".

Out of interest, what are some of these? I have a hard time believing that the implementors of the Perl regex engine chose to write it that way for no reason while the Thompson NFA figures are thrown about. I knew there must havevbeen something this 'implementation detail' was good for.

I believe backreferences require backtracking.

Re: Regex: badly needs fuzzing

#63

Post by marvy »

mlmlmasd wrote: post #43
amalag wrote: post #12

Earlier quoted context omitted.

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

Avoiding bugs is the default in software development in any language, no? If you have pointer DSL that can lead to various bugs, replacing it with a more complex pointer DSL is not a good way to avoid bugs. And I don't think C++ 'smart pointers' and other crap are very simple (relative to C pointers) or much less error-prone. That's just my opinion though.

Avoiding bugs is what you try to do by default in any language, yes. But success is not guaranteed :)

I agree that in general, if you have a pointer DSL that can lead to bugs, replacing to with a more complex one just makes things worse, assuming all else stays the same.

But! Maybe the extra complexity buys you something. For instance, maybe the complexity allows the compiler to prove that certain classes of bugs are impossible. Now we have a tradeoff. Let's say we want to get a correct program as fast as possible. Then you can quickly write a buggy program in the simple DSL, but you will need to spend some time debugging it. Or you can spend a long time wrestling with the complicated one, but you don't need to debug pointer issues anymore (you still have to fix other bugs of course.)

Then the question is: do you save more time in debugging than you pay in "fighting" a complex language. And the answer is always the same: maybe! Maybe you make less pointer bugs in C than most people, and maybe you're more allergic to smart pointers than most people, so for you it's pointless. Certainly pointer bugs are not very rare in the world though. Worse, they're not always noticed right away.

Re: Regex: badly needs fuzzing

#65

Post by eridius »

sidlls wrote: post #53
10293101 wrote: post #42

Earlier quoted context omitted.

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.

Not sure what that has to do with anything. The parent is a very vocal Rust proponent and made a ridiculous comment which has been called out by myself and several others. It hasn't anything to do with any "small group of people" talking smack about C programmers. Although that's unfortunate, too.

I don't think it's ridiculous. It seems like almost every discussion about Rust vs C++ here has a few people saying that you don't need Rust's guarantees about memory safety if you're writing modern C++. And that oft-repeated comment is what pcwalton is referencing.

Re: Regex: badly needs fuzzing

#66

Post by geofft »

carussell wrote: post #40
0xFFC wrote: post #20

Earlier quoted context omitted.

What is backtracking?

Looks like there's (a lot of) confusion in these comments about the difference between backtracking and backreferences . The `\2` in Phritzy's snippet is a backreference. Backtracking is an implementation strategy for writing a regular expression engine. I don't know why anyone choosing an engine would "require backtracking". It's an implementation detail, not a feature. (Although the fact that Thompson NFAs avoid ex…

From the RE2 wiki:

"As a matter of principle, RE2 does not support constructs for which only backtracking solutions are known to exist. Thus, backreferences and look-around assertions are not supported."

From your link:

One common regular expression extension that does provide additional power is called backreferences. A backreference like \1 or \2 matches the string matched by a previous parenthesized expression, and only that string: (cat|dog)\1 matches catcat and dogdog but not catdog nor dogcat. As far as the theoretical term is concerned, regular expressions with backreferences are not regular expressions. The power that backreferences add comes at great cost: in the worst case, the best known implementations require exponential search algorithms, like the one Perl uses. Perl (and the other languages) could not now remove backreference support, of course, but they could employ much faster algorithms when presented with regular expressions that don't have backreferences, like the ones considered above. This article is about those faster algorithms.

If your regex has backreferences, or look-ahead/look-behind assertions, or similar things, then your regex engine must support a backtracking strategy.

If you do not need backreferences or similar things, then your regex engine may still choose to use backtracking, but does not need to.

RE2 is a regex engine that prioritizes never using backtracking as an implementation detail, and therefore does not support backreferences as a matter of external API.

RE2 is not able to evaluate Phritzy's regex.

Re: Regex: badly needs fuzzing

#67

Post by Twirrim »

Someone1234 wrote: post #37
revelation wrote: post #11

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.

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

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.

Re: Regex: badly needs fuzzing

#68

Post by blub »

10293101 wrote: post #42
sidlls wrote: post #21

Earlier quoted context omitted.

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.

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.

Safety may seem like a binary property, but it's really not.

Modern C++ is not as safe as Rust, but it is much safer than C, and significantly safer than doing manual memory management and raw pointer manipulation in C++. The interesting question is if that's enough for a particular project.

In general, I would argue that it is, because security is but one of the non-functional properties of software and the types of bugs that Rust prevents compared to modern C++ are but one category of security-relevant bugs. The advantages that modern C++ can bring over Rust would compensate on average for its safety gap.

C on the other hand is simply a losing proposition safety-wise. Whatever I do, the type system won't do much if anything to help me prevent or catch bugs.

Re: Regex: badly needs fuzzing

#69

Post by [deleted] »

barkingcat wrote: post #60
justinmk wrote: post #47

Earlier quoted context omitted.

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

PHP pcre is implemented in c https://github.com/php/php-src/blob/master/ext/pcre/php_pcre...

[deleted]

Re: Regex: badly needs fuzzing

#70

Post by kmike84 »

flogic wrote: post #25
stuckagain wrote: post #10

Earlier quoted context omitted.

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.

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.

re2 is not only about exponential time: matching of regexes like a|b|c is O(N) in backtracking engines and O(1) in DFA-based engines like re2. It can make a big difference in practice for generated regexes - e.g. if you want to check if an URL has one of the thousand substrings in it (think adblock-like use cases). With backtracking regex or with a loop it'd be O(N) regarding the number of options, but with DFA it is O(1) regarding the number of options. I've seen 1000x speedups for similar use cases with re2 vs re from Python stdlib.
Post reply on HN