Arbitary Lifetime Transmutation via Rust Unsoundness

Do you believe that one can write a function in safe Rust which can arbitrarily change the lifetime of a reference? For clarity, try to implement the following function without using unsafe:

fn transmute_lifetime<'a, 'b>(x: &'a u64) -> &'b u64 { todo!() }

Such intention seems to violate the fundamental principle of Rust’s lifetime system, which is to prevent dangling references and data. However, it is possible to write such a function in safe Rust, and it is not even that hard:

trait Trait {
    type Output;
}

impl<T: ?Sized> Trait for T {
    type Output = &'static u64;
}

fn foo<'a, T: ?Sized>(x: <T as Trait>::Output) -> &'a u64 { x }

fn transmute_lifetime<'a, 'b>(x: &'a u64) -> &'b u64 {
    foo::<dyn Trait<Output=&'a u64>>(x)
}

WOAH! There’s a lot of magic going on here. This is from my recent discovery of a Github issue Coherence can be bypassed by an indirect impl for a trait object, which is a quite enjoyable reading down the rabbit hole.

Let’s break down the code step by step.

The Trait trait

trait Trait {
    type Output;
}

impl<T: ?Sized> Trait for T {
    type Output = &'static u64;
}

The first part defines a trait Trait with an associated type Output. As a reminder, let’s recap on the concept of associated types:

1. An associated type is a type that is associated with a trait, and must be specified by the trait implementor.
2. The associated type of a trait is unique for each implementor, i.e., a type T cannot implement Trait<Output=O1> and Trait<Output=O2> at the same time, which is different from the generic type parameters.
3. Given the uniqueness mentioned above, one can access the associated type of a trait by using the syntax <T as Trait>::Output, which resolves to a concrete type.

What’s interesting is that we have Trait implemented for all types T: ?Sized, in which the associated type Output is set to &'static u64. This implies for any type T, including those dynamically sized, is now a subtype of Trait, and <T as Trait>::Output should resolve to &'static u64.

Hence, we have the validity of the foo function.

fn foo<'a, T: ?Sized>(x: <T as Trait>::Output) -> &'a u64 { x }

Since <T as Trait>::Output should always be &'static u64, variable x of that type can be safely cast to &'a u64 without any lifetime issues.

So far so good, until we enter the territory of dyn ... types, aka the trait objects.

The Trait Objects

Trait objects is a way to abstract over types that implement a trait, denoted as dyn Trait which is a special type in Rust and enables dynamic dispatch at runtime. We may consider an implicit implementation is generated for every trait object type as:

impl Trait for dyn Trait { ... }

Specially, if a trait Trait contains associated types, a bare dyn Trait is not allowed. Instead we need to specify the associated types explicitly, e.g., dyn Trait<Output=...>. Similar to above, an imaginary implementation is generated for this case as:

impl<O> Trait for dyn Trait<Output=O> { type Output = O; }

Now let’s think about a question: Does trait object type belong to “any type”?

This matters since if it does, our aforementioned impl<T: ?Sized> Trait for T should also apply to dyn Trait types, which means the following implementation also exists:

impl<O> Trait for dyn Trait<Output=O> { type Output = &'static u64; }

which contradicts the previous one! Unfortunately, Rust does not prevent this from happening, and the compiler will not complain about it. By exploiting this, we can write the legendary transmute_lifetime function.

fn transmute_lifetime<'a, 'b>(x: &'a u64) -> &'b u64 {
    foo::<dyn Trait<Output=&'a u64>>(x)
}

The snippet is legitimized as explained by @nikomatsakis in the Github issue:

Now the problem is that different parts of the compiler could select different impls, resulting in distinct values for Output. In @Centril’s example (#57893 (comment)), there is a helper function foo which only knows that it has some T: ?Sized, so it uses the user’s impl to resolve Output. […]

On the other hand, the transmute_lifetime function invokes foo with the type dyn Object<Output=&'a u64>. […] This winds up resolving using the “auto-generated” impl, and hence Output is normalized to &'a u64.

This problem remains unsolved since 2019 and is considered a soundness hole in Rust’s type system. The Rust team has been aware of this issue for a long time, but it is not easy to fix.

Author: hsfzxjy.
Link: .
License: CC BY-NC-ND 4.0.
All rights reserved by the author.
Commercial use of this post in any form is NOT permitted.
Non-commercial use of this post should be attributed with this block of text.