Compressed heap pointers with offsets reminds me a lot of the early segmented memory regions offered by x86. The segmentation registers baked the offsets directly into the architecture.
Grsecurity leveraged x86 segmentation for a number of powerful mitigations like UDEREF, which was a precursor to SMAP, using (iirc) the segmentation registers to isolate kernel/ user memory. SMAP is a sort of specialized instruction for this enforcement but Grsecurity used the generalized approach to build numerous mitigations. I suppose segmentation was considered too complex to burn registers on? Not sure why they were removed.
Even if you’re not up to replacing pointers entirely, you should start considering them as handles: They should only be dereferenceable together with the engine base pointer, never without it.
This is, basically, what UDEREF did and it was a decade-ahead (or more?) mitigation from Grsecurity using this concept.
The language that dominates the future of software development may not be Rust, Rust’s borrow checker is after all currently not even strong enough to encode the features needed to do use-after-free checking of handles to garbage collected data without some manual work, but it will be a language with a borrow checker that will win the sweepstakes. The benefits of a borrow checker are simply too great, and the downsides are only a matter of finding the right way to frame your assumptions for it to check.
It seems like a bit of a turtles situation. At some point you need to implement this “offset” logic. I suppose a memory tagging system could do it at the hardware level like with grsecurity, but I don’t see why Rust wouldn’t be suitable to implement something like compressed pointers/ offsets.
I … have trouble believing the author of this really understands GC. The whole point of GC is that “ownership” of memory is moot.
External pointers to GC objects are not plain old pointers, not unless you’re using a conservative collector that scans native stacks. Generally they are always some sort of handle that has to be dereferenced through special GC code. Because (a) the objects they point to can move, and (b) the GC has to keep track of these handles because they are roots that keep objects alive.
So the problem of dangling raw pointers to a disposed GC heap is not real, not unless you’re using a conservative collector, which no JS runtime I know of does.
They seem to understand GC just fine, they even describe pointer semantics and how a GC works, as well as V8’s pointer compression. I think it’s perhaps their use of “ownership” that’s a bit contentious but they give their own definition so I think it’s fine (I think their definition is actually accurate?). They also appear to be a developer of a garbage collected language runtime, Nova. Perhaps I’m missing something myself.
So the problem of dangling raw pointers to a disposed GC heap is not real, not unless you’re using a conservative collector, which no JS runtime I know of does.
If the GC “owns” the memory and the GC is unaware of a reference, which seems both possible and trivial to express in cases like FFI from a GC language, then you run into the issues described. Another case is the implementation of a system like V8, which implements a GC that may have external references (or improperly managed/ generated references) into the memory allocated by javascript being executed (and is the focus of much of the article). This seems consistent and reasonable, and would motivate something like the specific compressed pointers in V8?
I wonder if I’m missing something because I don’t know much about GCs, but this all seems like it makes sense?
If the GC “owns” the memory and the GC is unaware of a reference, which seems both possible and trivial to express in cases like FFI from a GC language, then you run into the issues described.
But that never happens; if it does, it’s a bug. The GC has to know about every external reference to its objects, because those objects anre by definition live annd cannot be freed; they are “roots” that it traces live objects from.
A conservative collector scans thread stacks looking for anything that might be a pointer to an object. Other collectors, like V8, use special handle types that wrap pointers.
In this post, I’ll analyse CVE-2021-37975 (reported by an anonymous researcher), which is a logic bug in the implementation of the garbage collector (GC) in v8 (the JavaScript interpreter of Chrome). This bug allows reachable JavaScript objects to be collected by the garbage collector, which then leads to a use-after-free (UAF) vulnerability for arbitrary objects in v8. In this post, I’ll go through the root cause analysis and exploit development for the bug.
An optimization in EarlyOptimizationPhase that elides ChangeTaggedToInt32 -> ChangeInt31ToTaggedSigned caused a HeapNumber to be stored to an object in a field with a TaggedSigned representation. A check before EarlyOptimizationPhase in SimplifiedLoweringPhase makes the correct assumption that write barriers can be elided when storing anything to a field in an object with the TaggedSigned representation. This leads to a use-after-free if the HeapNumber being mistakenly stored to the object lives in NewSpace, and the object being stored to lives in OldSpace.
Not every object is managed by the V8 GC, and there are also bugs in that GC, it seems.
Also, at least in Ruby, I know it’s very easy to create invalid references via FFI.
My reading of the article does not support your assumption that it’s all about the presence of bugs. It’s more like “we’ve given out a raw pointer into GC and now people could deref it after the heap is disposed.”
And the big conclusion:
A handle cannot be dereferenced on its own, all usage of it to access real memory requires access to the engine’s base pointer: The engine owns the memory. A handle cannot be dereferenced on its own, if the engine shuts down then the handle becomes a useless integer, fit only for performing integer overflow tricks with.
No, actually, what happens is the handle gets dereferenced against some garbage address (where the base pointer used to be located), and now you’re at best reading a random memory location and getting garbage or crashing, and at worst writing to some random memory location and corrupting the process’s state.
Hm, well perhaps the author would have to weigh in then. Given the reference to the V8 isolated heaps, which are definitely about preventing exploitation of GC bugs, and the bits about segmented heaps, and the reference to Halvar’s talk, it does strike me as being about the sorts of issues I described.
and now you’re at best reading a random memory location and getting garbage or crashing, and at worst writing to some random memory location and corrupting the process’s state.
Assuming the offset is secret, that seems like quite a win, but I would have to reference the paper on these heaps that the V8 team put out to know, and I don’t have time this morning :\ but “random in a 64bit space” is pretty good, there’s a huge chance you access something that just instantly crashes the system.
The author definitely has more experience with GCs than I do, and perhaps it’s only for this article’s sake that they focus so much on pointers themselves, but.. I feel this is a bit misguided.
A garbage collector (ref counting included) operates semantically on handles. In the ref counting case that handle will as an internal detail increment/decrement a counter. In the tracing case it may have write or read-barriers, but the point is that these are objects that have their own semantics by which they can be accessed. It’s an entirely separate implementation detail if they are represented as an integer corresponding to a memory address/region or something else. There are languages that can express express these semantics natively (I believe RAII is a core primitive here), but we have seen user-level APIs for ref counting (e.g. glib), and runtimes may choose to simply handle it themselves e.g. by generating the correct code via a JIT compiler.
Of course a runtime’s assumptions can be violated, but as the author even points out, the JVM for example hands out handles for FFI purposes, so not sure how much of a problem this actually is. As for the concrete design, I don’t have enough experience to provide feedback - I do like the aspect that code can be monomorphic, but given that tracing GCs have to trace the heap, I feel the runtime checks for that phase would be a negative tradeoff.
Also, to continue with their analogy, if you reach for native code, you effectively call a burgler to your block. Even if you only hand them a key and don’t tell them which house is yours and have an alarm system so you have to know the password, they might just break the window in.
It has even been shown that the two approaches are equivalent fixed point algorithms; the first gives the greatest and the latter the least fixed point
Compressed heap pointers with offsets reminds me a lot of the early segmented memory regions offered by x86. The segmentation registers baked the offsets directly into the architecture.
Grsecurity leveraged x86 segmentation for a number of powerful mitigations like UDEREF, which was a precursor to SMAP, using (iirc) the segmentation registers to isolate kernel/ user memory. SMAP is a sort of specialized instruction for this enforcement but Grsecurity used the generalized approach to build numerous mitigations. I suppose segmentation was considered too complex to burn registers on? Not sure why they were removed.
This is, basically, what UDEREF did and it was a decade-ahead (or more?) mitigation from Grsecurity using this concept.
It seems like a bit of a turtles situation. At some point you need to implement this “offset” logic. I suppose a memory tagging system could do it at the hardware level like with grsecurity, but I don’t see why Rust wouldn’t be suitable to implement something like compressed pointers/ offsets.
I … have trouble believing the author of this really understands GC. The whole point of GC is that “ownership” of memory is moot.
External pointers to GC objects are not plain old pointers, not unless you’re using a conservative collector that scans native stacks. Generally they are always some sort of handle that has to be dereferenced through special GC code. Because (a) the objects they point to can move, and (b) the GC has to keep track of these handles because they are roots that keep objects alive.
So the problem of dangling raw pointers to a disposed GC heap is not real, not unless you’re using a conservative collector, which no JS runtime I know of does.
They seem to understand GC just fine, they even describe pointer semantics and how a GC works, as well as V8’s pointer compression. I think it’s perhaps their use of “ownership” that’s a bit contentious but they give their own definition so I think it’s fine (I think their definition is actually accurate?). They also appear to be a developer of a garbage collected language runtime, Nova. Perhaps I’m missing something myself.
If the GC “owns” the memory and the GC is unaware of a reference, which seems both possible and trivial to express in cases like FFI from a GC language, then you run into the issues described. Another case is the implementation of a system like V8, which implements a GC that may have external references (or improperly managed/ generated references) into the memory allocated by javascript being executed (and is the focus of much of the article). This seems consistent and reasonable, and would motivate something like the specific compressed pointers in V8?
I wonder if I’m missing something because I don’t know much about GCs, but this all seems like it makes sense?
But that never happens; if it does, it’s a bug. The GC has to know about every external reference to its objects, because those objects anre by definition live annd cannot be freed; they are “roots” that it traces live objects from.
A conservative collector scans thread stacks looking for anything that might be a pointer to an object. Other collectors, like V8, use special handle types that wrap pointers.
The compressed pointers/ isolated heaps are assuming the presence of bugs.
For example, https://github.blog/security/vulnerability-research/chrome-in-the-wild-bug-analysis-cve-2021-37975/
Here’s one where the JIT gets involved, which seems to be a common problem lately: https://googleprojectzero.github.io/0days-in-the-wild//0day-RCAs/2021/CVE-2021-4102.html
Not every object is managed by the V8 GC, and there are also bugs in that GC, it seems.
Also, at least in Ruby, I know it’s very easy to create invalid references via FFI.
My reading of the article does not support your assumption that it’s all about the presence of bugs. It’s more like “we’ve given out a raw pointer into GC and now people could deref it after the heap is disposed.”
And the big conclusion:
No, actually, what happens is the handle gets dereferenced against some garbage address (where the base pointer used to be located), and now you’re at best reading a random memory location and getting garbage or crashing, and at worst writing to some random memory location and corrupting the process’s state.
Hm, well perhaps the author would have to weigh in then. Given the reference to the V8 isolated heaps, which are definitely about preventing exploitation of GC bugs, and the bits about segmented heaps, and the reference to Halvar’s talk, it does strike me as being about the sorts of issues I described.
Assuming the offset is secret, that seems like quite a win, but I would have to reference the paper on these heaps that the V8 team put out to know, and I don’t have time this morning :\ but “random in a 64bit space” is pretty good, there’s a huge chance you access something that just instantly crashes the system.
The author definitely has more experience with GCs than I do, and perhaps it’s only for this article’s sake that they focus so much on pointers themselves, but.. I feel this is a bit misguided.
A garbage collector (ref counting included) operates semantically on handles. In the ref counting case that handle will as an internal detail increment/decrement a counter. In the tracing case it may have write or read-barriers, but the point is that these are objects that have their own semantics by which they can be accessed. It’s an entirely separate implementation detail if they are represented as an integer corresponding to a memory address/region or something else. There are languages that can express express these semantics natively (I believe RAII is a core primitive here), but we have seen user-level APIs for ref counting (e.g. glib), and runtimes may choose to simply handle it themselves e.g. by generating the correct code via a JIT compiler.
Of course a runtime’s assumptions can be violated, but as the author even points out, the JVM for example hands out handles for FFI purposes, so not sure how much of a problem this actually is. As for the concrete design, I don’t have enough experience to provide feedback - I do like the aspect that code can be monomorphic, but given that tracing GCs have to trace the heap, I feel the runtime checks for that phase would be a negative tradeoff.
Also, to continue with their analogy, if you reach for native code, you effectively call a burgler to your block. Even if you only hand them a key and don’t tell them which house is yours and have an alarm system so you have to know the password, they might just break the window in.
Somebody has a reference for this?
Perhaps they are referencing this paper? https://www.cs.cornell.edu/courses/cs6120/2019fa/blog/unified-theory-gc/
Edit: same title, wrong link: https://courses.cs.washington.edu/courses/cse590p/05au/p50-bacon.pdf