Regex: badly needs fuzzing

I should have specified more clearly

by:

> That's what the kernel is there for.

I meant, you should still be able to easily restart your program and continue using it. It wont crash your computer.

RCE is only a problem for computers that are connected to the internet and/or take user provided input.

> 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 unacceptable to pcwalton and the Rust community.

I'm not a member of the security community, but I have never seen anyone in that community disagree with my claim that C and C++ are unsuitable for writing secure software at scale (at least without a robust sandbox or restrictive subsets). I have seen the claim that sandboxes are sufficient to mitigate memory safety problems, but even in that case the comparison becomes "C and C++ with a correctly maintained, leak-proof sandbox" vs. "a memory-safe language", not "C and C++" vs. "a memory-safe language".

> This is Poe's law territory

Heh, I think that's possibly the only virtue to sarcasm: it confuses the pedants. I use friendly smileys or the word "heh" when I'm trying to be jovial, and I'm willing to give that poster the benefit of the doubt. :-)

> a lot of your own comments sound very similar to the parent

Which comments?

> there are other emoticons more commonly used to indicate sarcasm/joke

I think any common standard about something like this probably only applies to a narrow clique.

Needs both.

> rather than the crash which might [...]

Assert like mad. Break out your debug allocators, your asan, your checked iterators. Fuzzing can be as bad as you say, but it can also give you extremely easy to diagnose repro cases - and catch an incredibly wide range of issues for incredibly little work, in my experience.

Static analysis generally won't tell you "Hey, if I almost-but-not-quite exhaust your address space allocating to successfully parsing this file, I can get your next closed-source API call to segfault!" - useful for tracking down each and every possible allocation related to networking deserialization so you can configure sane quotas (such as "array size probably shouldn't be larger than bytes sent, bail out safely instead of trying to allocate that")

With most sane setups that come to mind, no false positives either.

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

Your tooling should do this automatically for you. If it doesn't, get better tooling. AFL. SDL MiniFuzz. Whatever floats your boat.

> Particularly when the hit rate is very high, fuzzing is a stupidly inefficient way to find bugs.

I've had it be stupidly efficient in terms of programmer time once setup. Occasionally leaving my computer on overnight? Worth.

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 effectively zero-with assertions. It's not sexy, and the rest is easy to sketch out from there as a conceptual matter. What's more interesting are the Ragel-specific details.

Before we tackled backreferences we had a problem with repetitions causing unacceptable state blow up with unioned DFAs, repetitions, semantic conditions, and especially with their interactions. This was the biggest barrier for most of the final 10%. To help solve that the contractor added an NFA construct to Ragel, along with the magic needed for the generated Ragel state machines to switch from DFA to NFA modes mid-expression. The NFA construct expands on the notion of embedded host-language code in transition actions and semantic conditions, which allows embedding inline C code to track and control the matching behavior of each subexpression, as well as to handle bookkeeping, including state stack management.

Most simple captures can be accomplished using Ragel's regular action features. But IIRC even captures that could be done from a DFA machine would sometimes blow up state too much so I think the captures necessary for backreferences are always done in NFA mode. Similarly, the code is quick to fallback to NFA mode for expressions without backreferences as it simplified grouping some of the complex expressions into secondary unions, which allowed compiling their prefixes as a DFA; as opposed to immediately falling back to prefilters and a linear match of each expression that couldn't be added to the primary or secondary unions.

Matching of backreferences is implemented similar to lookarounds. Lookarounds, at least in my early code, are implemented using semantic conditions. In my later code I think lookbehinds still had to be a fixed size, but it looks like (bugs notwithstanding) backreferences could be variable sized. The Ragel match is anchored on the empty string at the relevant position using the NFA construct, auxiliary code handles matching against the capture, and on a match the `p' index variables is updated to skip over the length of the match. The NFA construct saves and restores `p' as it trials each subexpression. Of course this approach doesn't work well in streaming mode. Similar to Ragel scanners I think theoretically the host application could arrange for windowing, but I don't know if everything is in place to make that feasible. In our case we didn't need the streaming.

And at least in my code, anything with backreferences automatically gets a prefilter and is only run conditionally in a second phase. Presumably that's so we don't need to do captures for stuff that will never match, whether or not it involves an NFA. I'm sure that's how it's still implemented.

Regarding streaming, I totally forgot about Hyperscan's streaming mode. Streaming isn't something that (IME) can be readily bolted on after the fact, so it's a testament to it's careful design and forethought.

But in C, especially in a complex networking application doing asynchronous I/O, callbacks are so extremely costly--they break code locality and compound the normal headaches with ownership and lifetime. Managing that complexity is of utmost importance in a language like C. Using Hyperscan in streaming mode, especially in combination with DPDK... I imagine the project failure rate is really high. I know of at least one skillful team that bombed precisely as I predicted because of the excessive complexity and the resulting inability to stabilize the product. The callback/push/interrupt model is too difficult in C. In languages with lambdas, Hyperscan's streaming mode has no handicap. But especially in C, Ragel's idiosyncratic host-language interface, with it's embedded action handling and minimal state, is just so incredibly important for reducing complexity and for sticking as closely as possible to a pull model for data consumption without sacrificing performance. If developers spend most of their time working on and fixing the I/O code and related interface boundaries (as is typical), there's much less time for implementing the functional features that matter. I don't doubt people have built a ton of amazing things with DPDK and Hyperscan's streaming mode, but the number of teams that can do that _correctly_ are few and far between. Honestly, I wouldn't want a solution like that protecting my data unless I knew the team had the requisite skill.

On second thought... I should reel that criticism in a little bit. ;) For just matching and cataloging "hits", rather than performing complex operations on them, it's much less of a problem. The costs will be a function of how much work is done on the other side of the callback. But it's just so much more difficult to balance efficiency and complexity, and to constrain complexity in general. I've been writing asynchronous I/O services since before libevent and I've just become constitutionally averse to callbacks. I've never used libevent's buffering API because before it even debuted I had internalized how poorly suitable that sort of interface is in terms of interface composition. Callbacks are necessary--e.g. at the interface boundary of the event loop--but I try so hard to avoid them when possible, including switching to languages other than C when possible. It's just a huge consideration for me, perhaps unreasonably. :)

Also, I understand that Hyperscan's callback interface is largely dictated by other considerations, like the perfectly sensible choice for a runtime library interface. In streaming mode a generic queuing and retrieval interface would be awkward and suboptimal for most cases, and there's no good substitute for pushing that implementation detail to the application. DPDK, OTOH, wasn't forced to adopt an asynchronous interrupt model, it was just the easiest.

[1] I don't like to mention names of people not participating in a thread, even though in this case I'm sure you're familiar and he probably would appreciate the plug. You may have conversed with him at some point because your SIMD work is awesome, Hyperscan in general is amazing, and when it was finally open sourced we had to take a really hard look at adopting it or, alternatively, whether we should pursue SIMD optimizations on our own. And IIRC at some point he may have chatted with someone on the Hyperscan team.