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.
Why are people still using parsers for untrusted input in C? That is the real flaw here, not how the fuzzing was done.
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.
The idea of not writing parsers directly was well established by the time OpenSSL started in the late 90s.
Parser generators feel like an academic dream
The main drawback is that it is difficult to get good error messages when a parse fails.
EDIT: An important note to newbs: The Halting Problem is correct. However, a problem which maps to the halting problem can still be solved often enough in practice to make it worthwhile. In fact, entire industries have been born of heuristic solutions to such problems.
Valgrind and fuzzing are useful tools, but there is no general method. Being semi-decidable, with enumerable inputs. This means that fuzzing can be useful both with random walks and constrained random walks. But it doesn't come close to generating 'provably correct code'.
The 'Post correspondence problem' is maybe an easier way to see how this applies at the compiler level.
But tools that help are opportunistic, but that doesn't change the undecidability of generalizations.
While crossing domains, but because it is commonly used, considering the VC dimensionality of the problem also helps, or pure math problems like the Collatz conjecture that generalize to the same halting problem.
Generating 'provably correct code' in the general case is simply not possible without major advances in math. There is room to improve with many paths to do so, just not going down this particular path.
Note that parsing a context free grammar maps to a stack machine. The Halting Problem uses a Turing Machine. I don't think it applies! (But if you do still want to show off your knowledge, please elucidate. I've forgotten about half of the automata theory I covered as an undergrad and in grad school.) For parsing tasks corresponding to computational models which are less complex, like regular expressions, the problem is well under the threshold of "semi-decidable, with enumerable inputs" in your words.
Generating 'provably correct code' in the general case is simply not possible without major advances in math.
Note that I was responding specifically to the problem domain of parsing and compiler compilers, and that most parsing problems involve models of computation which are akin to a stack machine or less powerful.
People generally throwing out The Halting Problem as an objection without carefully considering the particulars/context is one of my chief pet peeves.
C++ templates, Haskel templates, Lisp macros, etc... are all examples of metaprogramming facilities that would be considered TC, and thus subject to Rice's Theorem (To avoid HP).
But last I saw the code that was generated was the problem, not the primitives. As the languages are TC, a parser not being so doesn't remove the issue with this CVE.
Good! So, if what we want the compiler compiler to do is, say, just to produce an output isomorphic to the input, then this also reduces the complexity of what we're asking to do. I think this falls well inside what we could automate with some kind of guarantee of correctness.
A good mental habit for programmers is to constantly ask, "Can the stated problem be reduced in scope, such that we satisfy the goal?"
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!
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.
My point is that there isn't a compelling reason to write new code in C for something where safety is critical.
> What to do with leaks out of temporaries? : p = (s1 + s2).c_str();
> pointer/iterator invalidation leading to dangling pointers
I feel like those are relatively common memory safety pitfalls, not obscure corner cases. The Core Guidelines have been in the works for about 7 years, I think? It's not clear if/when these will ever be addressed if they haven't been addressed by now.
https://isocpp.github.io/CppCoreGuidelines/CppCoreGuidelines...
There are other things mentioned in the list that look suspicious, but they're less clear. So, unless I'm misreading this, then I stand behind my original assertion that there is no safe subset of C++, but the Core Guidelines are certainly better than nothing... assuming they're actually used/enforced in real world applications. Other people are welcome to have their own opinions.
Hence why the ongoing efforts to improve static analysis tooling in regards to mechanical enforcement of C++ Core Guidelines across all major C++ compilers, IDEs and commercial static analysers.
It is perfect? Don't let perfect be the enemy of good.
In any case, anyone that cares about secure code shouldn't be touching any language that is copy-paste compatible with C, unless they can't avoid it.
As for the rest, I was quite clear where I stand on my last sentence.
https://github.com/openssl/openssl/blob/openssl-3.0.6/crypto...
* 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.
One solution to this problem would be to write an LLVM backend that outputs C. Maybe such a thing already exists.
>parsers for untrusted input in C
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?
> 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.
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?
Probably not that important for `ls`, probably worth it for OpenSSL.
No matter what the parser itself is written in, if you're writing in C you'll be using the parser in C.
2. That’s still less of a problem as the C will then be handling trusted data validated by the safe langauge.
Plain pointer access in high-level code (say when parsing a particular syntactic element by hand in a recursive descent parser) is a violation of the principle of separation of concerns IMO.
In any case I still don't see what's special about parsers. Most vulnerabilities I suspect to be in the higher levels, like validating parsed numbers and references, for a trivial example. In general, those are checks that are likely to be implemented much closer at the core of the application.
What I see (especially in libraries like OpenSSL) is the core logic often receives a lot of scrutiny and testing, and thus it is silly mistakes with offsets and bounds checks that make up the majority of bugs.
It’s also worth considering the severity of different kinds of bug. A bug in high level logic might allow an attacker to do something they shouldn’t be able to do, but it doesn’t give them code execution.
The worst bit is, an attacker can often gain code execution through a part of the code that otherwise wouldn’t be security critical (where a logic mistake would be low impact). So writing code in a language that allows for these vulnerabilities greatly increases your attack surface.
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.