4 ms·

Open-loop fuzz testing catches only the most shallow of bugs. It is like genetic optimization with no fitness function. Why are people still using parsers for

Open-loop fuzz testing catches only the most shallow of bugs. It is like genetic optimization with no fitness function. Why are people still using parsers for untrusted input in C? That is the real flaw here, not how the fuzzing was done.

ralphb 4y ago
I'm confused and very far from an expert here. What is wrong with parsers, and what is the alternative?
- jcims 4y ago
  A specific class of parsers >parsers for untrusted input in C
  - thaumasiotes 4y ago
    That didn't answer anything. If you want to do anything with your input, you have to run it through a parser. Doesn't matter if it's untrusted or not. Your only options are ignoring the input, echoing it somewhere, or parsing it.
    - Diggsey 4y ago
      They're saying don't write such a parser in C. Use something else (memory safe language, parser generator, whatever).
      - lazide 4y ago
        And then do what with it? Throw it away? If it hands it to a C program, that C program needs to parse (in some form!) those values! How is a C program expected to ever do anything if it can’t safely handle input?
        tsimionescu 4y ago
        Untrusted input -> memory-safe parser -> trusted input -> C program. Probably not that important for `ls`, probably worth it for OpenSSL.
        lazide 4y ago
        The challenge of course is the links to the ‘memory safe parser’, or how it gets from the untrusted input to it mediated by C, correct?
    - nicoburns 4y ago
      Right, but you do have the option of writing that parser in a language other than C. And given how often severe security issues are caused by such parsers written in C, one probably ought to choose a different language, or at least use C functions and string types that store a length rather than relying on null termination.
      - thaumasiotes 4y ago
        >>>>> Why are people still using parsers for untrusted input in C? No matter what the parser itself is written in, if you're writing in C you'll be using the parser in C.
        nicoburns 4y ago
        1. Well don’t write in C then if your program is security critical or going to be exposed over a network. Sure, there are some targets that require C, but that’s not the case for the vast majority of platforms running OpenSSL. 2. That’s still less of a problem as the C will then be handling trusted data validated by the safe langauge.
        jstimpfle 4y ago
        If you make argument 2) could you explain how writing a parser is more security critical than any other code that has a (direct or indirect) interaction with the network? At least recursive descent parsers are close to trivial. I usually start by writing a "next_byte" function and then "next_token". You'll have to look very hard to find any pointer code there. It's close to impossible to get this wrong and I don't see how the fact that it's a parser would make it any more dangerous.
        thaumasiotes 4y ago
        > It's close to impossible to get this wrong and I don't see how the fact that it's a parser would make it any more dangerous. I can answer that one. The parser is more dangerous because a parser, essentially by definition, takes untrusted input. Nothing the parser does is any more dangerous than the rest of the code; it's all about the parser's position in the data flow.
  - lazide 4y ago
    Pretty much all input is untrusted unless it originated (exclusively!) from something with more permissions that is trustworthy. The kernel is written in C. So that pretty much means all parsers written in C and every other language should consider all input untrustworthy, no?
    - Gigachad 4y ago
      Linux is probably the most carefully constructed C codebase in existence and still falls in to C pitfalls semi regularly. Every other project has no hope of safely using C. It's looking more and more like Linux should be carefully rewritten in Rust. It's a monstrous task but I can see it happening over the next decade.
      - Shared404 4y ago
        I agree with the spirit of your comment. > Linux is probably the most carefully constructed C codebase in existence and still falls in to C pitfalls semi regularly. My guess is that it would actually be OpenBSD, but I'm not sure either way.
er4hn 4y ago
The problem here was that the coverage of the fuzz testing was not being examined. Using parsers for untrusted input in C is a legacy of when this was written. Requiring the parsing portion (or any version of OpenSSL) to be rewritten in Rust or whatever new language is a massive change given the length of time the OpenSSL project has been around.
- duped 4y ago
  It's not that big of a change, in the grand scheme of things. But it's also not the only thing you can do. The memory safe subset of C++ is also an option. Shipping a CVE in critical infrastructure because of a trivial memory safety bug is borderline negligence in 2022. This is why people get upset over new code being written in C. The cost of writing new portions of the software with memory safety in mind dwarfs the cost of writing in C because it's more convenient for the build tooling. The bigger question is why hasn't OpenSSL bitten the bullet and adopted some memory safety guarantees in their tooling, given the knowledge of the sources of these bugs and prevalent literature and tools in avoiding them!
  - coder543 4y ago
    > The memory safe subset of C++ is also an option. This does not actually exist, as far as I'm aware. There are certain things people propose doing in C++ that eliminate a small number of issues, but I haven't seen anyone clearly define and propose a subset of C++ that is reasonably described as memory safe. Even if such a subset existed, you would still need some way to statically enforce that people only use that. Even just writing the parsers in Lua should be a safer choice than writing it in C, but I think now is as good of a time as any to start writing critical code paths in Rust. If the Linux kernel is beginning to allow Rust for kernel modules, then it is high time that OpenSSL looked more seriously at Rust too As others have pointed out, parser generators could be a useful intermediate option for some of this.
    - duped 4y ago
      You can write memory safe C++ easier than memory safe C. The problem of statically verifying it the C++ is actually memory safe because of the numerous ways to write unsafe code in C++ is a different goalpost. My point is that there isn't a compelling reason to write new code in C for something where safety is critical.
mkeedlinger 4y ago
What alternatives are there to parsers? Genuine question from the ignorant.
- chowells 4y ago
  There are no alternatives to parsers. There are alternatives to "in C".
not2b 4y ago
But modern fuzzers aren't open-loop, they are coverage directed, adjusting their inputs to increase coverage. As the article points out, this works best if leaf functions are fuzzed; difficult to reach corners still might not be found.
kazinator 4y ago
You can easily write a robust parser in C. Just don't write a clump of code that interleaves pointer manipulation for scanning the input, writing the output and doing the parsing per se. * Have a stream-like abstraction for getting or peeking at the next symbol (and pushing back, if necessary). Make it impervious to abuse; under no circumstances will it access memory beyond the end of a string or whatever. * Have some safe primitives for producing whatever output the parser produces. * Work only with the primitives, and check all the cases of their return values.
deleted 4y ago
[deleted]
halpmeh 4y ago
Because there isn't a good way of distributing pre-compiled cross-platform C libraries. So if you want to use a parsing library written in Rust, for example, you'd need to add Rust to your toolchain, which is a pain. One solution to this problem would be to write an LLVM backend that outputs C. Maybe such a thing already exists.

ralphb 4y ago

I'm confused and very far from an expert here. What is wrong with parsers, and what is the alternative?

jcims 4y ago
A specific class of parsers >parsers for untrusted input in C
- thaumasiotes 4y ago
  That didn't answer anything. If you want to do anything with your input, you have to run it through a parser. Doesn't matter if it's untrusted or not. Your only options are ignoring the input, echoing it somewhere, or parsing it.
  - Diggsey 4y ago
    They're saying don't write such a parser in C. Use something else (memory safe language, parser generator, whatever).
    - lazide 4y ago
      And then do what with it? Throw it away? If it hands it to a C program, that C program needs to parse (in some form!) those values! How is a C program expected to ever do anything if it can’t safely handle input?
      - tsimionescu 4y ago
        Untrusted input -> memory-safe parser -> trusted input -> C program. Probably not that important for `ls`, probably worth it for OpenSSL.
        lazide 4y ago
        The challenge of course is the links to the ‘memory safe parser’, or how it gets from the untrusted input to it mediated by C, correct?
  - nicoburns 4y ago
    Right, but you do have the option of writing that parser in a language other than C. And given how often severe security issues are caused by such parsers written in C, one probably ought to choose a different language, or at least use C functions and string types that store a length rather than relying on null termination.
    - thaumasiotes 4y ago
      >>>>> Why are people still using parsers for untrusted input in C? No matter what the parser itself is written in, if you're writing in C you'll be using the parser in C.
      - nicoburns 4y ago
        1. Well don’t write in C then if your program is security critical or going to be exposed over a network. Sure, there are some targets that require C, but that’s not the case for the vast majority of platforms running OpenSSL. 2. That’s still less of a problem as the C will then be handling trusted data validated by the safe langauge.
        jstimpfle 4y ago
        If you make argument 2) could you explain how writing a parser is more security critical than any other code that has a (direct or indirect) interaction with the network? At least recursive descent parsers are close to trivial. I usually start by writing a "next_byte" function and then "next_token". You'll have to look very hard to find any pointer code there. It's close to impossible to get this wrong and I don't see how the fact that it's a parser would make it any more dangerous.
        thaumasiotes 4y ago
        > It's close to impossible to get this wrong and I don't see how the fact that it's a parser would make it any more dangerous. I can answer that one. The parser is more dangerous because a parser, essentially by definition, takes untrusted input. Nothing the parser does is any more dangerous than the rest of the code; it's all about the parser's position in the data flow.
- lazide 4y ago
  Pretty much all input is untrusted unless it originated (exclusively!) from something with more permissions that is trustworthy. The kernel is written in C. So that pretty much means all parsers written in C and every other language should consider all input untrustworthy, no?
  - Gigachad 4y ago
    Linux is probably the most carefully constructed C codebase in existence and still falls in to C pitfalls semi regularly. Every other project has no hope of safely using C. It's looking more and more like Linux should be carefully rewritten in Rust. It's a monstrous task but I can see it happening over the next decade.
    - Shared404 4y ago
      I agree with the spirit of your comment. > Linux is probably the most carefully constructed C codebase in existence and still falls in to C pitfalls semi regularly. My guess is that it would actually be OpenBSD, but I'm not sure either way.

er4hn 4y ago

The problem here was that the coverage of the fuzz testing was not being examined. Using parsers for untrusted input in C is a legacy of when this was written. Requiring the parsing portion (or any version of OpenSSL) to be rewritten in Rust or whatever new language is a massive change given the length of time the OpenSSL project has been around.

duped 4y ago
It's not that big of a change, in the grand scheme of things. But it's also not the only thing you can do. The memory safe subset of C++ is also an option. Shipping a CVE in critical infrastructure because of a trivial memory safety bug is borderline negligence in 2022. This is why people get upset over new code being written in C. The cost of writing new portions of the software with memory safety in mind dwarfs the cost of writing in C because it's more convenient for the build tooling. The bigger question is why hasn't OpenSSL bitten the bullet and adopted some memory safety guarantees in their tooling, given the knowledge of the sources of these bugs and prevalent literature and tools in avoiding them!
- coder543 4y ago
  > The memory safe subset of C++ is also an option. This does not actually exist, as far as I'm aware. There are certain things people propose doing in C++ that eliminate a small number of issues, but I haven't seen anyone clearly define and propose a subset of C++ that is reasonably described as memory safe. Even if such a subset existed, you would still need some way to statically enforce that people only use that. Even just writing the parsers in Lua should be a safer choice than writing it in C, but I think now is as good of a time as any to start writing critical code paths in Rust. If the Linux kernel is beginning to allow Rust for kernel modules, then it is high time that OpenSSL looked more seriously at Rust too As others have pointed out, parser generators could be a useful intermediate option for some of this.
  - duped 4y ago
    You can write memory safe C++ easier than memory safe C. The problem of statically verifying it the C++ is actually memory safe because of the numerous ways to write unsafe code in C++ is a different goalpost. My point is that there isn't a compelling reason to write new code in C for something where safety is critical.

mkeedlinger 4y ago

What alternatives are there to parsers? Genuine question from the ignorant.

chowells 4y ago
There are no alternatives to parsers. There are alternatives to "in C".

not2b 4y ago

But modern fuzzers aren't open-loop, they are coverage directed, adjusting their inputs to increase coverage. As the article points out, this works best if leaf functions are fuzzed; difficult to reach corners still might not be found.

kazinator 4y ago

You can easily write a robust parser in C. Just don't write a clump of code that interleaves pointer manipulation for scanning the input, writing the output and doing the parsing per se. * Have a stream-like abstraction for getting or peeking at the next symbol (and pushing back, if necessary). Make it impervious to abuse; under no circumstances will it access memory beyond the end of a string or whatever. * Have some safe primitives for producing whatever output the parser produces. * Work only with the primitives, and check all the cases of their return values.

deleted 4y ago

[deleted]

halpmeh 4y ago

Because there isn't a good way of distributing pre-compiled cross-platform C libraries. So if you want to use a parsing library written in Rust, for example, you'd need to add Rust to your toolchain, which is a pain. One solution to this problem would be to write an LLVM backend that outputs C. Maybe such a thing already exists.