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

161–170 of 180 posts

Re: Regex: badly needs fuzzing

#161

Post by glangdale »

wahern wrote: post #149
glangdale wrote: post #139

Earlier quoted context omitted.

(Hyperscan team lead here) Interesting. I should point out that Hyperscan is not abandonware; it is still maintained by Intel. Streaming is not unique to Ragel. You're not wrong about libpcre compatibility. We have very tight syntactic compatibility with libpcre (that is, we won't misidentify an unsupported construct and supply some erroneous semantics) but we make no secret of our inability to handle general lookaro…

As I alluded to earlier, the 100% (possibly +/- edge cases) solution was finished primarily by a contractor.[1] So the following only reflects the state of things while my Lua parser, analyzer, and transformation code was still in use. Also, my grasp of this stuff is nowhere near as strong as your's or the contractor's. I'm a pretender ;) Backreferences are implemented with prefilters, NFA machines, and what are effe…

Thanks for the kind words about Hyperscan. If you'd like to talk more, please get in contact (via the list, via our support alias, or our emails if you have them already).

I'm curious about the design issues w.r.t callbacks. We certainly haven't had complaints from most of our users about this, but maybe there would have been better models. Note that callbacks are partly a design pattern for our convenience - we need those big, complex stack frames for many of our engines. It's nice to throw a match out of the middle of a big unrolled loop and know that we can come back to the middle of the loop - not into the tedious 'preconditioning and warmup' part of the loop.

An alternate design is to fill a buffer of matches, but that has its own issues, especially with timeliness. Some users want to stop matching quickly after the first match - a problem if we go off and scan another megabyte to get the second through Nth matches.

In any case, we're always interested to hear about cases where we aren't the best solution, as this is always the most productive type of feedback to get. "Your library is great and you guys are really smart" is gratifying, but it doesn't lend itself well to continuous improvement.

Re: Regex: badly needs fuzzing

#162

Post by mrkgnao »

burntsushi wrote: post #116
WildUtah wrote: post #93

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…

How do you escape an asterisk on HN? Other than

  (a*)*c
which seems to work.

Re: Regex: badly needs fuzzing

#163

Post by dnljms »

jasode wrote: post #72
pcwalton wrote: post #2

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

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

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.

Re: Regex: badly needs fuzzing

#164

Post by quicknir »

blub wrote: post #68
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.

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…

The thing is, and Rust advocates seem to consistently plug their ears when they hear it, is that most software written specifically in C++ is very highly specialized stuff with a small specific client set, where security is just not an issue.

According to the poll that JetBrains did when it started working on CLion, about half of C++ usage is in financial software. I will tell you first hand that in most applications in financial software, C++ servers will be talking to other internal servers, exchanges, reputable data distributors, etc. The idea that memory = security risk is just not a connection that people around here generally make.

I also know some game developers and my strong sense is that games are similar. Video games may talk to a specialized multiplayer server, an update server, and that's mostly it.

I could continue, but you get the idea. For most C++ developers I've ever encountered, memory issue == bug, != security risk.

Browsers, which operate on maximally complex data (a Turing complete programming, JS) and are by nature exposed to the entire world, including malicious users who want to harm other browser users, are simply not the typical domain for C++. I think there's every chance that Rust is a good fit for writing browsers, but outside of that things are much less clear (at least, at the moment).

Re: Regex: badly needs fuzzing

#165

Post by Etzos »

blub wrote: post #159
pcwalton wrote: post #143

Earlier quoted context omitted.

> How can you say these are considered unacceptable risks to most, when people write so much code in C and C++? This argument was very compelling in, for example, 1997. But, nowadays, most code is written in memory safe languages. Choosing to write your next Unix daemon in Go or your next Windows app in C# is not exactly an uncommon choice in 2017. > And that's what I'm trying to communicate: they're only unacceptabl…

There exist entire industries built on C and C++ today. The security community may think that they're unsuitable, but they're not the ones building the software and making the decisions. e.g: Mozilla exists because of C and C++. Take that away and Mozilla ceases to exist. I don't know how to explain this more clearly: you are trying to enter an established market and "sell" a product based on its safety capabilities.…

> But your problem is that the market doesn't think it has a big safety problem, they think they can manage it.

Is that not what his original comment was addressing though? There are a number of people who feel there is no safety problem, but examples like this are good indications otherwise. Boost is a very fundamental (as in low-level, not as is essential) library in many cases and having memory safety problem at such a level should be concerning.

Re: Regex: badly needs fuzzing

#166

Post by luckystartup »

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

Re: Regex: badly needs fuzzing

#167

Post by amalag »

luckystartup wrote: post #166

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

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

That is the Turing Halting Problem!

Re: Regex: badly needs fuzzing

#168

Post by blub »

pcwalton wrote: post #114
sidlls wrote: post #102

Earlier quoted context omitted.

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

> This is "most C++ written by experts"? Boost is peer-reviewed and receives more scrutiny than most C++ in the wild. Its peer review is its major selling point, in fact. > Oh come on, you can't be serious given your advocacy for Rust. I think it's possible for me to be able to express opinions in favor of memory safe programming languages in general (which is what I'm doing here) while also having worked on one. If…

Boost.regex was peer reviewed in 2001, the same year XP was released and three years before Firefox was released. Modern C++.

Let's talk about the state of security back then if you want and compare.

The disappointing thing in this is that they haven't done a security review and put a plan in place for handling security. Par for the course in the world of software development, sadly.

Re: Regex: badly needs fuzzing

#169

Post by blub »

Etzos wrote: post #165
blub wrote: post #159

Earlier quoted context omitted.

There exist entire industries built on C and C++ today. The security community may think that they're unsuitable, but they're not the ones building the software and making the decisions. e.g: Mozilla exists because of C and C++. Take that away and Mozilla ceases to exist. I don't know how to explain this more clearly: you are trying to enter an established market and "sell" a product based on its safety capabilities.…

> But your problem is that the market doesn't think it has a big safety problem, they think they can manage it. Is that not what his original comment was addressing though? There are a number of people who feel there is no safety problem, but examples like this are good indications otherwise. Boost is a very fundamental (as in low-level, not as is essential) library in many cases and having memory safety problem at s…

That's not what's happening, this is an old(er) discussion.

pcwalton is asserting in general that modern C++ is not memory-safe, with the goal of promoting Rust and discouraging C++ usage.

Now that assertion is true, but it's not really useful, because programming language choices are not done only on the basis of a language being completely memory-safe. It's also misleading to emphasize only this one aspect (while ignoring others) and to such an extent (complete vs. good-enough safety).

It is concerning that this regex library has security issues. People should review their usage of it. But the original comment is something between offtopic and being inflammatory for the sake of it.

"There are a number of people who feel there is no safety problem"

The thing to remember here is: no safety problem... big enough that one should abandon C++ for Rust instead of working on tooling and idioms to improve it. That's what pcwalton would like.

Re: Regex: badly needs fuzzing

#170

Post by msbarnett »

randyrand wrote: post #140
AaronFriel wrote: post #59

Earlier quoted context omitted.

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…

Not every program is intended to be connected to the internet or have user provided input. I agree, for many programs memory safety matters. But there are a large chunk of programs where it doesnt matter/is not worth the effort.

> Not every program is intended to be connected to the internet or have user provided input.

While true, I think the vast majority of programs do do one of these two things (and increasingly, both), whereas the majority of programmers seem to think that what they work on "isn't a security issue".

It's this disconnect that is giving us the Internet of Crap. Your phone apps, your fridge, your video games, your text editor -- every program I interact with every day -- it's all a security issue

Post reply on HN