5 ms·

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 algebr

by wyager 5y ago

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.

tester756 5y ago
>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
- wyager 5y ago
  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.
  - tester756 5y ago
    well, but from security standpoint it should be fine?
roca 5y ago
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.
- andrewmd5 5y ago
  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.
  - roca 5y ago
    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".
    - andrewmd5 5y ago
      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.
      - roca 5y ago
        > 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".

by wyager 5y ago

tester756 5y ago

>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

wyager 5y ago
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.
- tester756 5y ago
  well, but from security standpoint it should be fine?

roca 5y ago

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.

andrewmd5 5y ago
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.
- roca 5y ago
  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".
  - andrewmd5 5y ago
    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.
    - roca 5y ago
      > 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".