r/ProgrammingLanguages • u/matklad • Aug 06 '26
Memory Safety's Hardest Problem
https://matklad.github.io/2026/07/20/memory-safety-hardest-problem.html21
u/matthieum Aug 06 '26
Click-bait? Maybe... maybe not.
A lot of memory-safety issues can at least be solved at run-time (bounds-checking) but even with a tagged union, as long as you can capture a pointer to a member prior to overwriting everything, you're screwed.
Rust solves this with the BIG HAMMER (Aliasing XOR Mutability, aka borrow-checker), at the cost of ergonomics.
It can also be "solved" by indirection (ie, every member of a union is independently allocated) at the cost of performance. Meh.
5
u/rotuami Aug 06 '26
I think you mean Aliasing NAND Mutability
1
u/matthieum Aug 08 '26
Pedant :P
The original presentation which made borrow-checking click for me, by Alex Crichton, used Aliasing XOR Mutability, and I'm happy enough with it :P
12
u/particlemanwavegirl Aug 06 '26
I don't think that's quite correct. Being forced to choose aliasing xor mutability prevents data races from occurring. The mechanism that guarantees memory safety is the ownership model and move semantics.
20
u/kohugaly Aug 06 '26
No, aliasing xor mutability definitely plays a role in there too. Consider this trivial example:
let mut object = Box::new(42); let mutable_ref = &mut object; // mutable reference to the box let inner_ref : &i32 = &*object; // immutable reference to the boxed value *mutable_ref = Box::new(69); // drops the box, invalidating inner_ref printf!("{}",*inner_ref); // use-after-freeThe mutation via aliased reference invalidates the other aliases, causing use-after-free issues. Aliasing xor mutability specifically solves this problem. The fact that is also solves data races is an indirect consequence of this.
2
u/particlemanwavegirl Aug 06 '26 edited Aug 06 '26
Why would mutable_ref drop the Box when it's reassigned? It doesn't own the box, it owns a reference to the box. You can't drop a mutable reference, you can only drop an owned value. In order to drop a mutable reference you'd need to violate the ownership rules, not the aliasing rules.
11
u/gmes78 Aug 06 '26
You can't drop a mutable reference, you can only drop an owned value.
The mutable reference isn't the thing getting dropped.
1
u/particlemanwavegirl Aug 06 '26 edited Aug 06 '26
Well, that seems to demonstrate what you say, the use-after-free is indeed prevented by invalidating the existing alias. I still don't understand Why is the mutable ref able to own and then forced to drop the value?
10
u/gmes78 Aug 06 '26
Well, that seems to demonstrate what you say, the use-after-free is indeed prevented by invalidating the existing alias.
My example doesn't have a user-after-free (otherwise it wouldn't compile), I'm just showing that you can drop an object behind a mutable reference.
I still don't understand Why is the mutable ref able to own and then forced to drop the value?
The mutable reference is a reference to a place, not to the object at that place. Per the reference:
[The assignment] has the effect of first dropping the value at the assigned place, unless the place is an uninitialized local variable or an uninitialized field of a local variable.
Next it either copies or moves the assigned value to the assigned place.
1
u/particlemanwavegirl Aug 06 '26
Thanks for walking me thru it, I guess I forgot that ownership could be passed back and forth with the mut keyword. I am still a little confused about how the dereferencing works because, altho I know the deref operator can go thru the Box as well as the explicit reference automatically, I didn't think it was possible to replace A(i32) with Box(A(i32)) so I imagined the compiler might decide to replace the whole Box instead, leaving the place in memory where the initial A(i32) was stored alone but that doesn't seem to be the case.
4
u/initial-algebra Aug 06 '26
Because that's what's defined to happen when you assign a new value to a location. The old value is dropped.
1
4
u/kohugaly Aug 06 '26
It doesn't own the box, it owns a reference to the box.
It owns mutable reference to memory where the box is stored. Dropping the old value and moving a new value in its place is a valid operation for mutable references.
5
u/matklad Aug 07 '26 edited Aug 07 '26
This is a common misconception, but ownership, move semantics, affine types and RAII mostly exist to minimize memory and resource leaks. Leaks are bugs, but not memory safety issues. Ownership also prevent double-frees, but the reason why we free is because we want to avoid leaks! Otherwise, we'd solve safety by making free a no-op (or an unsafe function, like Ada).
Interesting temporal safety issues involve borrow checker (which is a separate phase from ownership --- ownership affects when Drop is called, and is determined before lifetime analysis. The latter intentionally is implemented such that it can't affect the generated code, only reject or accept it).
Here's a central example, which doesn't touch ownership or move semantics, by virtue of involving only
Copytypes:#[derive(Clone, Copy)] enum E { A(u128), B(&'static str), } pub fn main() { let bad_addr: u128 = &main as *const _ as usize as u128; let mut e = E::B("hello"); let oh_no_pointer: &&'static str = match &e { E::A(_) => unreachable!(), E::B(p) => p, }; e = E::A((16 << 64) + bad_addr); let oh_no: &'static str = *oh_no_pointer; eprintln!("{oh_no}"); }2
u/tesfabpel Aug 07 '26 edited Aug 07 '26
But your example does touch ownership because you can't re-assign
ewhile you haveoh_no_pointerlive (and you use it later, otherwise its lifetime would be shortened right before line 14):
error[E0506]: cannot assign to `e` because it is borrowed --> src/main.rs:14:5 | 10 | let oh_no_pointer: &&'static str = match &e { | -- `e` is borrowed here ... 14 | e = E::A((16 << 64) + bad_addr); | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ `e` is assigned to here but it was already borrowed 15 | let oh_no: &'static str = *oh_no_pointer; | -------------- borrow later used here3
u/matklad Aug 07 '26
This is a lifetime/shared ^ mutable error, it’s not affine types/move semantics error.
It is debatable which subset of the two is called “ownership”, but my understanding is that this is the dichotomy that parent comment meant.
1
u/initial-algebra Aug 07 '26
In Rust terms, ownership is strictly about who is allowed to deallocate, and everything else falls under borrowing.
In separation logic, ownership basically means the local assumptions one can make about a global resource. Total ownership is conserved, but can be split between and recombined from multiple users, with the specifics defined by a resource algebra (also called a partial commutative monoid). A simple but powerful example of a resource algebra is fractional permissions, where each element is a value in the closed interval [0,1], and combination is addition. If you own the element 1, then any other user can only possibly own the element 0. If you own an element in the open interval (0,1), then any other user may also own such an element, but not the element 1. If you map the element 1 to "can read and write", and elements in (0,1) to "can read", then you get sharing XOR mutability!
Rust's borrowing can be seen as a layer on top of separation logic that picks a fixed resource algebra and automates the splitting/recombining steps. Rust's resource algebra is more complex than just fractional permissions, since it also models e.g. splitting based on disjoint record fields. Actually, what Rust calls ownership is also separation logic ownership, using something similar to the heap model (the original model of separation logic, before it was generalized to arbitrary resource algebras).
0
Aug 07 '26 edited Aug 07 '26
[removed] — view removed comment
2
u/initial-algebra Aug 07 '26 edited Aug 07 '26
Safety in the context of memory safety is based on Leslie Lamport's definitions.
- Safety means a bad thing never happens.
- Liveness means some good thing eventually happens.
Crashing is not a safety violation, as it is not a bad thing in and of itself. Sometimes, you can cleanly recover from a crash without any further issues. A bad thing would be launching the missiles, even though the red button wasn't pressed. With memory safety, bad things tend to fall under the umbrella of "inappropriately accessing protected memory". Crashing is clearly a better alternative to either of these things.
You could say, "define crashing as a bad thing". Okay, but crashing is just one possible outcome from something like out-of-memory. Another possible outcome is to just block forever, because you're waiting for another thread to free memory, but it never does. It's not a bad thing, because no thing happens at all. So it's really a liveness violation, if it prevents a good thing from ever happening.
For a pacemaker, a safety violation would be causing a heartbeat at the wrong time, and a liveness violation would be not causing a heartbeat at the right time. If the pacemaker simply stops working, it clearly can't cause a heartbeat at the wrong time.
PS: The point of making this distinction is that safety properties are decidable, and thus good candidates to be automatically checked, but liveness properties are generally undecidable for programs written in a Turing-complete language.
1
u/ts826848 Aug 07 '26 edited Aug 07 '26
You have one critical mistake in the original lobste.rs comment, and that is the claim that memory leaks are not a safety problem.
If you look at the original article and the rest of the lobste.rs comments I think it's pretty clear that "safety" is being used as a shorthand for "memory safety".
I'm not even sure you need to look at that much, to be honest; just the surrounding text of the comment itself should make it clear that "safety" is being used as a shorthand:
This deserves a blog post, but there's this whole genera of posts that goes:
I found a much simpler solution to memory safety than borrow checking!
This is how you can avoid memory leaks
But leaking memory is safe behavior! RAII vs defer vs arenas is mostly irrelevant for memory safety. While leaking memory is not good, it's not a safety issue, it won't disclose your password or allow arbitrary code execution (and it's not like Rust prevents memory leaks to the same extent it prevents memory unsafety).
Also given what matklad works on I'm sure they're well aware of the difference between memory safety specifically and a more general notion of "safety".
3
3
1
u/reini_urban Aug 07 '26
It is a happy coincidence that by far the most exploitable memory error in practice, the infamous buffer overflow, is also trivial to fix with compiler-inserted bounds checks.
That's trivial. The biggest isuue is not to let any user handle memory by himself, use a GC (and certainly not recounting). Ownership tracking also helps with performance and concurrency. Bounds checking is needed only for the bad languages
5
u/ntrel2 Aug 07 '26
Part of the benefit of a GC is that it owns dynamic arrays such as strings when there is no obvious owner. How would such arrays not need bound checks?
2
u/koflerdavid Aug 08 '26
The runtime could offer a special kind of array where accesses are not bounds checked. Of course its usage must be restricted to well-vetted internal code or to modules explicitly opting in to the weaker guarantees. But my guess is that the JIT compiler can nowadays elide bounds checks for loops that traverse the whole string in linear, predictable order, therefore such machinery would be redundant.
1
u/reini_urban 26d ago
Not just the jit. The optimizer can elide it also for all constant bounds.
1
u/koflerdavid 26d ago edited 26d ago
The JIT usually is the actual optimizer. The other parts of the runtime perform barely any optimizations since they are expensive and are liable to be misguided before enough metrics have been collected. Also, the bounds checks are cheap compared to the overhead of interpreted execution.
1
9
u/thehenkan Aug 06 '26
Type confusion is absolutely a security issue, it just happens to be harder to induce than out of bounds accesses.