I wander if rust (or any other memory safe system language in the future) could have avoided this exploit. If not, what could we do to avoid such exploits?
One method of forbidding the entire category of bugs is "bounds checks on integer arithmetic". Rust implements this in debug mode, but not by default in release mode, because it comes at a performance cost. To make this sort of solution ubiquitous you really want better hardware support to make bounds checking cheap.
Realistically I think it is unlikely you would have written the same exploit in rust even with integer overflow wrapping by default, because in idiomatic rust you end up using types with lengths attached to them, and memcpy methods that check that you didn't fuck up the lengths before copying. You absolutely could end up writing it in rust though (using unsafe code, but at some level unsafe code is inevitable for this sort of work), and you could if you really wanted to implement a similar set of safer buffer types in C that would provide a similar degree of prevention (though it would be more cumbersome to use than in rust).
> To make this sort of solution ubiquitous you really want better hardware support to make bounds checking cheap.
It's funny because it's trivial to implement underflow/overflow reporting in an ALU, but somehow that kind of event doesn't get reported to the offending program, at least at the naive C level.
My potentially incorrect understanding is that at the hardware level overflows basically always set flags indicating underflow/overflow, but
- Checking those flags and branching depending on extra instructions and comes at a performance cost, and that this could be instructions that trap on overflow instead of setting a flag. This can be solved, but needs instruction set level support.
- Requiring overflows are correctly handled at all comes at a performance cost at the optimization level (you can't turn (x + x - x) into a no-op), this is fundamental, but probably an acceptable cost if you solved the other issue.
C's arithmetic operators on unsigned operations also require the implementation doesn't return some sort of error on overflows, but for signed errors it would be a valid thing to do (since the behavior is undefined by the spec), and you could use compiler supplied functions instead of the primitives for erroring on the unsigned operations as well (or a non-standards-compliant compiler flag).
Rust kept the option open in how they defined arithmetic. Currently it wraps in release mode, but it's explicitly backwards compatible to change that to a panic (rust's version of exceptions).
I think this bug would not have been exploitable in rust. Rust would not catch the integer underflow, but the exploit was only possible because of memcpy.
You can line for line rewrite the code with unsafe rust and get the same exploit with a bad memcpy[1]. But this code would never have used unsafe rust.
The method that was exploited was "append user supplied strings to the end of a string". This can easily be written in safe rust, a thousand different ways. Here is one way it could have been written.
You can't have this bug in WUFFS. The WUFFS compiler will point out that it can't see any reason to believe the expression won't overflow, and any possibility of overflow is illegal in WUFFS, so your program is invalid and won't compile. So you need to write code which can't overflow.
Of course WUFFS is deliberately constrained to a simple world and thus utterly unsuitable for writing an operating system kernel. However, the principles do apply, the authors of this code didn't want overflow to be possible, they just didn't have a way to express that to their compiler.
In Rust it is at least easier to express that you don't want overflow:
let x = size.checked_add(len).unwrap().checked_add(2).unwrap();
if (x > PAGE_SIZE) { ...
The above code will panic (regardless of build parameters) if adding size + len + 2 overflows. If you don't want a panic, you can write some unwrap_or_else() code to pick some preferred value when overflow occurs, or you can handle the None result (which is what checked_add gives you for overflow) explicitly.
However, perhaps it should be possible to express at compile time that you want an expression which can't overflow at runtime, as in WUFFS.
This got nothing to do with the memory but to the fact how CPU works with the integers. This means that (low-level) programming language fundamentally cannot solve this problem but only alleviate it either by:
1. Changing the semantics of integer arithmetic (e.g. saturate on overflow)
2. Keeping the semantics but babysit the computation during runtime so that the overflow/underflow can never happen (expensive)
First, unsigned integer underflow and overflow is _not_ UB. It is very well defined operation (wrap-around arithmetic) and the bug in question is not the result of undefined behavior and rust or whatever other bs I keep hearing around would have not solved it. It's the fundamental artifact of how CPUs work.
Secondly, CPUs have been "alerting" through their carry and overflow bits in registers since forever so this isn't some exclusive feature that only rust compiler writers were smart enough to take advantage of. The same code can be and is written where it matters in C and C++ code too.
It's not only the question if such extra checks are expensive (which they are given that integer arithmetic is such a fundamental operation and your favorite language disables it in release builds for the sakes of, I guess, nothing?) but it is also a question of all known _semantics_ of unsigned
integer arithmetic. That's simply the way they work and I see no near future where the CPU hardware engineers would change that (they will not).
> First, unsigned integer underflow and overflow is _not_ UB. It is very well defined operation (wrap-around arithmetic) and the bug in question is not the result of undefined behavior
Shockingly true. Per the C Standard, "6.2.5 Types" paragraph 9:
A computation involving unsigned operands can never overflow, because a result that cannot be represented by the resulting unsigned integer type is reduced modulo the number that is one greater than the largest value that can be represented by the resulting type.
What you actually want is to enable some kind automatic trapping behavior when a section of code is entered so that you can say “this set of math operations shouldn’t overflow”. That’s cheaper than what overflow bits get you although entering/exiting such a mode may be equally or more expensive.
The existence of the overflow bits and that overflow continues to remain a common security flaw indicates that there’s a disconnect between the mental model users have when writing this kind of arithmetic (ie they don’t think about it generally and C integer promotion rules don’t do any favors) and how CPU designers imagine you write code.
> you can say “this set of math operations shouldn’t overflow”
This is the same as putting an "if" statement to check for sizes (before or after the operation); the thing that other languages automatically do for you at runtime (with its performance implications).
> The existence of the overflow bits and that overflow continues to remain a common security flaw
What do you propose for a new CPU architecture/instruction set/register types?
How would you implement it? Signed registers?
> how CPU designers imagine you write code.
Write a program in assembler. You'll be checking carry/overflow bits in no-time.
> CPUs have been "alerting" through their carry and overflow bits in registers since forever so this isn't some exclusive feature that only rust compiler writers were smart enough to take advantage of.
Another way of putting it: C/C++ have been handling overflow badly since forever despite hardware support, but now Rust and other more security aware systems languages are free to take advantage of it.
I hope Rust will take the opportunity sooner or later, as the semantics seem to allow it.
You could imagine a version of the arithmetic instructions that traps on overflow. Or maybe a prefix for the normal instruction. Then it can be basically free in the happy path.
Realistically I think it is unlikely you would have written the same exploit in rust even with integer overflow wrapping by default, because in idiomatic rust you end up using types with lengths attached to them, and memcpy methods that check that you didn't fuck up the lengths before copying. You absolutely could end up writing it in rust though (using unsafe code, but at some level unsafe code is inevitable for this sort of work), and you could if you really wanted to implement a similar set of safer buffer types in C that would provide a similar degree of prevention (though it would be more cumbersome to use than in rust).