Hack Monty - Postmortem

#Vulnerability step 1: the flawed unsafe code

Being an implementation of Python, Monty has to create Python objects which hold references to each other in a graph structure. Graph data structures are a challenging fit for Rust's borrow checker, because (under a direct application of Rust's Sharing XOR Mutability) editing data in one portion of the graph requires exclusive access to the whole graph. This would imply for example that the Monty interpreter cannot perform basic Python operations like list.extend(iterable) because the interpreter could not be writing to list while also reading from iterable.

There are ways to work around this without reaching for unsafe. Rust provides built-in types such as RefCell and Mutex which enable so-called "interior mutability", i.e. fine-grained mutability on individual elements of the graph without needing to take exclusive access to the whole graph. We evaluated these options, but they come with downsides of code complexity and runtime cost. For Monty we had the insight that we could use certain assumptions about Python objects, such that they don't change type once created, and the fact that Monty is a single-threaded implementation, to build our own way to enforce sharing XOR mutability at the individual element level on the graph.

This custom approach required unsafe code internally, and we took best practices to engineer the unsafe code, including testing the code with Rust's Miri interpreter and documenting all the safety invariants at the unsafe code points. Unfortunately, the documented safety invariants failed to account for the possibility that a flawed implementation of Monty's GC could violate those invariants. Due to the nature of unsafe code, once the invariants are broken, Rust's safety guarantees are void and it only becomes a matter of time before an exploit is found.

In this case, researchers were able to use the GC to exploit list.sort(key=<some function>) - an appropriately crafted key function could cause the GC to remove the list object undergoing sorting and replace it with an attacker controlled object, such as a bytes object with custom content. This is a use after free - a classic way for hackers to cause programs to execute attacker controlled code.

It's worth noting that without the unsafe code, this flaw in the GC would likely have led Monty to panic when the list object was replaced with another type. A panic typically leads to a noisy but deterministic shutdown, which at worst can lead to denial of service attacks rather than remote code execution.

#Vulnerability step 2: weaknesses in Monty's GC

Like CPython, Monty primarily uses reference counting to keep track of Python objects and decide when they are no longer in use and can be safely cleaned up.

Reference counting is insufficient because objects can create cycles, for example the following Python code creates a cycle of two lists containing each other:

a = []
b = [a]
a.append(b)

Such cycles will never have their reference counts naturally drop to 0, so a second strategy is needed to detect these cycles and clean them up. The GC implementation in Monty is categorised as a tracing GC, which means that starting from a known set of "root" objects the GC identifies all objects which can be reached from those roots, with the conclusion that any object not reachable must be in a dangling cycle and so targetable for removal.

We learned from Hack Monty that Monty's tracing GC had several deficiencies, including:

• objects were missing from the root set, and
• objects had incorrect traversal logic.

These kinds of deficiencies meant that Monty's GC would not be able to reach all objects which it should have. Those objects were therefore incorrectly treated as being in dangling cycles and freed while still in use.

In the vulnerability exploited in Hack Monty where list.sort was attacked, this was because the list object undergoing sorting was missing from the set of roots and so could be incorrectly freed by the GC in this way.

Again, it's worth noting that without the flawed unsafe code above, this GC flaw still would have led to highly observable bugs in Monty such as panics or incorrect execution of the input Python code, but they would almost certainly not have led to remote code execution.

#Closing the gap

Once the vulnerability was understood, we were able to immediately close the gap by patching the GC to include all objects currently dependent on the unsafe code's soundness in the root set. This restores the invariants needed by the unsafe code,

With this fix in place, and having conducted a thorough re-audit of the small number of unsafe blocks within Monty, we have confidence that there are no further memory safety issues within Monty.

This of course doesn't mean that we are complacent; we would be surprised if Monty is bug-free, we simply expect these to be minor logical bugs rather than vulnerabilities. For example, we know the current GC design doesn't prevent missing roots by construction, and we're exploring how we solve that, ideally before Hack Monty 2.