Hmm makes me wonder what the result of running this fuzzing test on other regex libraries would be.
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
Regex: badly needs fuzzing
101–110 of 180 posts
Re: Regex: badly needs fuzzing
#102Earlier 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.
> 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 i…
> Well, I have seen exactly that sentiment.
Then surely you can provide a reference to it.
> it's also a counterexample to "most C++ written by experts doesn't have memory safety issues that matter in practice".
This is "most C++ written by experts"? At least you're willing to back off your initial ridiculous assertion somewhat. This one isn't much better though.
> I haven't brought up Rust here.
Oh come on, you can't be serious given your advocacy for Rust.
Re: Regex: badly needs fuzzing
#103Earlier quoted context omitted.
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, an…
> 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 regexes that use backreferences, or look-ahead/look-behind assertions, or similar things, then your regex engine must support a backtracking strategy, or you need to rewrite all the regexes you care about to not use any of these."
Is it possible to automate that morphism, i.e., is it possible to build a wrapper around RE2 that converts (in suitably bounded time) a regex using backreferences to RE2 if the language described is in fact regular, and prints an error otherwise?
Re: Regex: badly needs fuzzing
#104Earlier quoted context omitted.
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.
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…
[deleted]
Re: Regex: badly needs fuzzing
#105Earlier quoted context omitted.
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, an…
> 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…
[deleted]
Re: Regex: badly needs fuzzing
#106Earlier 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…
> One of the big pieces that can easily be glossed over, especially during performance comparisons, is unicode handling.
Patterns in Rust's regex library are Unicode-aware by default: https://doc.rust-lang.org/regex/regex/index.html#unicode
Re: Regex: badly needs fuzzing
#107Earlier quoted context omitted.
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.
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…
Memory-safety bugs can lead to RCEs, which are considered unacceptable risks to most in computer science. Additionally, as Rust shows, memory-safety bugs can be checked by a computer, which can consistently apply those checks, making it an excellent bang-for-buck to use Rust or a comparable memory-safety checker. That's what pcwalton is saying.
Re: Regex: badly needs fuzzing
#108Earlier 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.
> 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 i…
Well, I have seen exactly that sentiment.
I've seen it too but as a bunch of other people pointed out, the C++ in this library is not the C++ that sort of sentiment is about. This seems like the criticism you should be responding to.
Re: Regex: badly needs fuzzing
#109Any 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…
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.
Re: Regex: badly needs fuzzing
#110Earlier quoted context omitted.
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.
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…
> lecturing everyone "No, you really want to have 0 risk, you fools"
On HN, please don't use quotation marks that make it look like you're quoting someone when you're not. It may seem a minor point, but we've found that it's important for clarity and respect.
Also, "lecturing everyone" is borderline name-calling, which the site guidelines ask you not to do: https://news.ycombinator.com/newsguidelines.html.