Hacker News Reader

Comment by wyager | Hacker News Reader

Because people implement parsers in languages that don’t allow direct expression of grammars (e.g. C). To safely implement parsers you must choose either algebraic datatypes or continuation passing, and a lot of programmers choose neither. CPS is annoying in most languages. ADTs are the obvious choice but somehow in 2021 most people are using languages that don’t have them. If you write a parser in Haskell, for example, you’d have to mess up pretty badly and write totally non-idiomatic code to write a parser that crashes at all, let alone crashes in a way that compromises memory safety.

View on HN

You can just use a handwritten parser in any memory-safe language.

However, I suspect parsers for big objects like images tend to have more vulnerabilities because developers try to avoid copying data, for performance reasons. Many memory-safe languages have their own performance issues, or make it hard to avoid copying bulk data, so those languages aren't a great fit.

This makes Rust a particularly good choice for writing parsers: Rust is pretty strong at supporting complex data sharing patterns while remaining memory-safe.

If your goal is validation (i.e. this is a JPG/PNG) and stripping of EXIF data it is entirely possible to write your own parser in a managed and safe language in less than 500 lines of code without sacrificing any performance.

Don’t load them into memory, parse them as a stream byte-by-byte in accordance with the standard for the codec, check every offset before seeking, and reject images that don’t conform to the standard.

And of course, a ton of fuzzing to accompany it.

The overhead of the stream abstraction is typically a lot greater than the cost of accessing a byte array.

Also, maybe I'm wrong, but when I read "image parsing" I think that actually means "image decoding".

The overhead of stream abstractions is negligible if your goal is security when processing arbitrary input files provided from a zero-trust environment.

In environments where you’re prioritizing performance I’d still argue streams are likely your best bet when the size of the file to be parsed is not a constant. You wouldn’t want to load 50 large files into ram on a server environment let alone a phone.

If your input buffer is a bunch of tiny 10 KB files and you trust them? Sure, load them into memory and access their indices on the stack. Make sure you reuse the buffer to avoid unnecessary allocations.

If you want parallel processing with zero-allocations then streams with an array pool for their backing buffer are the best bet.

Not loading arbitrary files into memory will always be safer than doing so.

As for decoding - I believe the functions for validating if an array of bytes is an image should be far removed from the decoding and presentation of those bytes to the frame buffer. You don’t need to decode a JPG to validate that a file is a JPG. It either conforms to the standard or it doesn’t; the pixel data is irrelevant.

> if your goal is security

The goal is never just security.

E.g. for a Web browser like Firefox the priority has to be to be as fast or faster than the competition, THEN be secure. That's just the reality of what users care about. If the goal was just security we'd all have been using HotJava for the last 24 years.

The goal for Rust was performance plus safety. That's pretty hard to pull off.

> You wouldn’t want to load 50 large files into ram on a server environment let alone a phone.

mmap() works pretty well here.

> As for decoding - I believe the functions for validating if an array of bytes is an image should be far removed from the decoding and presentation of those bytes to the frame buffer. You don’t need to decode a JPG to validate that a file is a JPG. It either conforms to the standard or it doesn’t; the pixel data is irrelevant.

Yeah but in a browser for example you never want to just "validate" an image file, you want to decode it, and separating validation from decoding is just asking for trouble. That is the meaning of "parse, don't validate".

> You can just use a handwritten parser in any memory-safe language.

It’s still probably going to be wrong for a complex grammar, even if it’s not going to literally crash. Bratus et al did a survey of PDF parsers a few years ago and iirc all the popular ones were wrong in ways that don’t necessarily correspond to memory errors (like infinite looping).

> This makes Rust a particularly good choice for writing parsers

In particular, Rust has ADTs, which is the main feature I advocate for this.

Even infinite looping is much better failure mode than "villains seize control of your device".

>ADTs are the obvious choice but somehow in 2021 most people are using languages that don’t have them.

Isn't inheritance to create hierarchy enough? why?

       Node 
   SubNode1    SubNode2
 SubNode1.1      SubNode2.1

Using inheritance in this way is a hack to emulate some of the functionality of ADTs. Grammars are perhaps one of the most poignant examples where the various constructors in your type might have no behaviors in common, so adherence to a shared interface is nothing but a vague indication that these types are somehow related. Sealed classes let you recover a little bit more of the functionality.

well, but from security standpoint it should be fine?

Reply on news.ycombinator.com