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

51–60 of 180 posts

Re: Regex: badly needs fuzzing

#51

Post by stuckagain »

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…

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

Re: Regex: badly needs fuzzing

#52

Post by randyrand »

pcwalton wrote: post #2

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

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.

Re: Regex: badly needs fuzzing

#53

Post by sidlls »

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.

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.

Re: Regex: badly needs fuzzing

#54

Post by mastax »

dikaiosune wrote: post #28
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!

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…

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

Re: Regex: badly needs fuzzing

#55

Post by dbaupp »

ambrop7 wrote: post #44
pcwalton wrote: post #2

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

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

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.

Re: Regex: badly needs fuzzing

#56

Post by ue_ »

stuckagain wrote: post #51
carussell wrote: post #40

Earlier quoted context omitted.

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…

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.

Re: Regex: badly needs fuzzing

#57

Post by [deleted] »

justinmk wrote: post #47
gpm wrote: 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…

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

[deleted]

Re: Regex: badly needs fuzzing

#58

Post by [deleted] »

justinmk wrote: post #47
gpm wrote: 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…

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

[deleted]

Re: Regex: badly needs fuzzing

#59

Post by AaronFriel »

randyrand wrote: post #52
pcwalton wrote: post #2

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

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.

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.

Re: Regex: badly needs fuzzing

#60

Post by barkingcat »

justinmk wrote: post #47
gpm wrote: 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…

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

Post reply on HN