Rust allows impl Fn(T<'a>) -> T<'b> to be : 'static, which is unsound

[danielhenrymantilla]

This is similar to #84366, but I don't know if I would say it's exactly the same. For instance, the exploit involves no associated types (no Output of FnOnce at all), just the mere approach of:

1. type F<'a, 'b> = impl Fn(T<'a>) -> T<'b> : 'static;
2. dyn Any-erase it.
3. downcast to a different F<'c, 'd> (e.g., 'a = 'b = 'c, and 'd = 'whatever_you_want).

Mainly, the -> T<'b> return could always become an &mut Option<T<'b>> out parameter (so as to have a -> () returning closure), so the return type of the closure not being : 'static is not really the issue; it's really about the closure being allowed to be : 'static despite any part of the closure API being non-'static.

In fact, before 1.66.0, we did have impl 'static + Fn(&'a ()) being 'a-infected (and thus non : 'static). While a very surprising property, it seems to be a more sound one that what we currently have.

The simplest possible exploit, with no unsafe(-but-sound) helper API (replaced by an implicit bound trick) requires:

• T<'lt> to be covariant;
• type_alias_impl_trait.

I'll start with that snippet nonetheless to get people familiarized with the context:

#![forbid(unsafe_code)] // No `unsafe!`
#![feature(type_alias_impl_trait)]

use core::any::Any;

/// Anything covariant will do, for this demo.
type T<'lt> = &'lt str;

type F<'a, 'b> = impl 'static + Fn(T<'a>) -> T<'b>;

fn helper<'a, 'b>(_: [&'b &'a (); 0]) -> F<'a, 'b> {
    |x: T<'a>| -> T<'b> { x } // this should *not* be `: 'static`
}

fn exploit<'a, 'b>(a: T<'a>) -> T<'b> {
    let f: F<'a, 'a> = helper([]);
    let any = Box::new(f) as Box<dyn Any>;

    let f: F<'a, 'static> = *any.downcast().unwrap_or_else(|_| unreachable!());

    f(a)
}

fn main() {
    let r: T<'static> = {
        let local = String::from("...");
        exploit(&local)
    };
    // Since `r` now dangles, we can easily make the use-after-free
    // point to newly allocated memory!
    let _unrelated = String::from("UAF");
    dbg!(r); // may print `UAF`! Run with `miri` to see the UB.
}

• Playground

---

Now, to avoid blaming implicit bounds and/or type_alias_impl_trait, here is a snippet not using either (which thus works independently of variance or lack thereof).

It does require unsafe to offer a sound API (it's the "witness types" / "witness lifetimes" pattern, wherein you can be dealing with a generic API with two potentially distinct generic parameters, but you have an instance of EqWitness<T, U> or EqWitness<'a, 'b>, with such instances only being constructible for <T, T> or <'a, 'a>.

/// Note: this is sound (modulo the `impl 'static`):
/// it's the "type witness" pattern (here, lifetime witness).
mod some_lib {
    use super::T; // e.g., `type T<'a> = Cell<&'a str>;`

    /// Invariant in `'a` and `'b` for soundness.
    pub struct LtEq<'a, 'b>(::core::marker::PhantomData<*mut Self>);

    impl<'a, 'b> LtEq<'a, 'b> {
        /// Invariant: these are the only actual instances of `LtEq` code may witness.
        pub fn new() -> LtEq<'a, 'a> {
            LtEq(<_>::default())
        }
    
        pub fn eq(&self) -> impl 'static + Fn(T<'a>) -> T<'b> {
            // this `impl Fn(T<'a>) -> T<'b>` is sound;
            let f = |a| unsafe { ::core::mem::transmute::<T<'a>, T<'b>>(a) };
            // what is *not* sound, is it being allowed to be `: 'static`
            f
        }
    }
}

With this tool/library at our disposal, we can then exploit it:

use core::{any::Any, cell::Cell};
use some_lib::LtEq;

/// Feel free to choose whatever you want, here.
type T<'lt> = Cell<&'lt str>;

/// I've explicitly lifetime annotated everything to make it clearer.
fn exploit<'a, 'b>(a: T<'a>) -> T<'b> {
    let f = LtEq::<'a, 'a>::new().eq();
    let any = Box::new(f) as Box<dyn Any>; // this should not compile: `T<'a> -> T<'a>` ought not to be `'static`

    let new_f = None.map(LtEq::<'a, 'b>::eq);

    fn downcast_a_to_type_of_new_f<F: 'static>(
        any: Box<dyn Any>,
        _: Option<F>,
    ) -> F {
        *any.downcast().unwrap_or_else(|_| unreachable!())
    }

    let f = downcast_a_to_type_of_new_f(any, new_f);

    f(a)
}

fn main() {
    let r: T<'static> = {
        let local = String::from("…");
        let a: T<'_> = Cell::new(&local[..]);
        exploit(a)
    };
    // Since `r` now dangles, we can easily make the use-after-free
    // point to newly allocated memory!
    let _unrelated = String::from("UAF");
    dbg!(r.get()); // may print `UAF`! Run with `miri` to see the UB.
}

• Playground

---

This happens since 1.66.0.

@rustbot modify labels: +I-unsound +regression-from-stable-to-stable

[BoxyUwU]

I definitely think this is a dupe of #84366 you're constraining a hidden type to be a closure that thinks its 'static but shouldn't be because a lifetime has to be early bound and part of self.

[compiler-errors]

Regression:

found 10 bors merge commits in the specified range
commit[0] 2022-09-24UTC: Auto merge of #98483 - dvtkrlbs:bootstrap-dist, r=jyn514
commit[1] 2022-09-24UTC: Auto merge of #102040 - TaKO8Ki:separate-definitions-and-hir-owners, r=cjgillot
commit[2] 2022-09-25UTC: Auto merge of #102169 - scottmcm:constify-some-conditions, r=thomcc
commit[3] 2022-09-25UTC: Auto merge of #98457 - japaric:gh98378, r=m-ou-se
commit[4] 2022-09-25UTC: Auto merge of #99609 - workingjubilee:lossy-unix-strerror, r=thomcc
commit[5] 2022-09-25UTC: Auto merge of #102254 - matthiaskrgr:rollup-gitu6li, r=matthiaskrgr
commit[6] 2022-09-25UTC: Auto merge of #100865 - compiler-errors:parent-substs-still, r=cjgillot
commit[7] 2022-09-25UTC: Auto merge of #102265 - fee1-dead-contrib:rollup-a7fccbg, r=fee1-dead
commit[8] 2022-09-25UTC: Auto merge of #102266 - Mark-Simulacrum:fix-custom-rustc, r=jyn514
commit[9] 2022-09-25UTC: Auto merge of #95474 - oli-obk:tait_ub, r=jackh726

[compiler-errors]

This probably regressed in #95474, cc @oli-obk

[apiraino]

WG-prioritization assigning priority (Zulip discussion).

@rustbot label -I-prioritize +P-high

[nikomatsakis]

We dove into this in the @rust-lang/types meetup and uncovered a few interesting observations.

Most importantly, we believe this is a dup of #25860. The reason why is not super obvious. The key point is that for this type...

type F<'a, 'b> = impl 'static + Fn(T<'a>) -> T<'b>;

...the hidden type is a closure that (implicitly) relies on 'a: 'b:

fn helper<'a, 'b>(_: [&'b &'a (); 0]) -> F<'a, 'b> {
    // Why does this compile? Because of an implied bound
    // `where `'a: 'b` (which could well have been explicit);
    // that relationship is required to make the hidden type
    // well-formed.
    |x: T<'a>| -> T<'b> { x } // this should *not* be `: 'static`
}

We ordinarily require that the hidden type is WF under the where-clauses on the type alias (example). But in this case, because of the bugs in how we handle implied bounds, these where-clauses are "implied" and are not present in the predicates list for the closure. If we make them explicit, by adding where 'a: 'b, then the code fails to compile, claiming that the hidden type is not well-formed. If we add where 'a: 'b onto the type alias, then we get an error on the dyn-cast.

As a side note, we dug into the "dyn-transmute" mechanism here, which is an important interaction I was not aware of. The key point seems to be that if you have "semantic 'static bounds", meaning that T<'a, 'b>: 'static if it has no reachable references (even though T<'a, 'b> may still have free regions), then typeid+dyn allows you to change 'a and 'b arbitrarily. This is unsound here because the closure's body required a relationship between those lifetimes that was being lost. In general, I would like to adopt semantic 'static bounds (and e.g. #116040 is an instance of that), so this is concerning -- however, it may be that semantic 'static bounds are still sound so long as we don't lose the where-clauses like this. I'm going to leave a separate comment on that PR though to call more attention to this interaction.

[workingjubilee]

@nikomatsakis What about the second example that doesn't use type F<'a, 'b> = impl 'static + Fn(T<'a>) -> T<'b>?

[nikomatsakis]

@workingjubilee Hmm, which example is that? I'm having trouble finding it :)

[lcnr]

This one

/// Note: this is sound! It's the "type witness" pattern (here, lt witness).
mod some_lib {
    use super::T;

    /// Invariant in `'a` and `'b` for soundness.
    pub struct LtEq<'a, 'b>(::core::marker::PhantomData<*mut Self>);
    
    impl<'a, 'b> LtEq<'a, 'b> {
        pub fn new() -> LtEq<'a, 'a> {
            LtEq(<_>::default())
        }
    
        pub fn eq(&self) -> impl 'static + Fn(T<'a>) -> T<'b> {
            |a| unsafe { ::core::mem::transmute::<T<'a>, T<'b>>(a) }
        }
    }
}

use core::{any::Any, cell::Cell};
use some_lib::LtEq;

/// Feel free to choose whatever you want, here.
type T<'lt> = Cell<&'lt str>;

fn exploit<'a, 'b>(a: T<'a>) -> T<'b> {
    let f = LtEq::<'a, 'a>::new().eq();
    let any = Box::new(f) as Box<dyn Any>;

    let new_f = None.map(LtEq::<'a, 'b>::eq);

    fn downcast_a_to_type_of_new_f<F: 'static>(
        any: Box<dyn Any>,
        _: Option<F>,
    ) -> F {
        *any.downcast().unwrap_or_else(|_| unreachable!())
    }

    let f = downcast_a_to_type_of_new_f(any, new_f);

    f(a)
}

fn main() {
    let r: T<'static> = {
        let local = String::from("…");
        let a: T<'_> = Cell::new(&local[..]);
        exploit(a)
    };
    dbg!(r.get());
}