Skip to content

Functions, closures, and HRTB-trait-objects can implement traits such that validity of associated types is never checked. #84533

@steffahn

Description

@steffahn
Member

edit: while this issue has been mostly fixed by #115538, the underlying issue still exists for higher ranked function pointers. It feels highly likely that it can still be exploited, even if the exploit will now be even more involved.


Make sure to also read through the next few comments of mine, where I present some other, significantly different examples of related problems (that’s where HRTBs become relevant, and closures, fn-pointers and trait objects play a role). I also explain the T-lang tag there with a question on changing the meaning of HRTBs that include associated types. Possibly it’s even a sensible thing to split this issue up into two issues.

So if I write a function such as

fn foo<'b, 'a>() -> PhantomData<&'b &'a ()> {
    PhantomData
}

then foo’s return type is only valid if 'a: 'b. When we call the function this is enforced a the call site, e.g.

fn caller<'b, 'a>() {
    foo::<'b, 'a>();
}

doesn’t work, with

error[E0491]: in type `&'b &'a ()`, reference has a longer lifetime than the data it references
 --> src/lib.rs:8:5
  |
8 |     foo::<'b, 'a>();
  |     ^^^^^^^^^^^^^^^
  |
note: the pointer is valid for the lifetime `'b` as defined on the function body at 7:11
 --> src/lib.rs:7:11
  |
7 | fn caller<'b, 'a>() {
  |           ^^
note: but the referenced data is only valid for the lifetime `'a` as defined on the function body at 7:15
 --> src/lib.rs:7:15
  |
7 | fn caller<'b, 'a>() {
  |               ^^

error: aborting due to previous error

(playground)

However, if we just instantiate the lifetime parameters, there’s apparently no check being performed at all, i.e.

fn caller<'b, 'a>() {
    foo::<'b, 'a>;
}

compiles just fine. (playground).

This seems questionable, the type of foo::<'b, 'a> implements FnOnce with Output = PhantomData<&'b &'a ()>, and it is in fact possible to use this output type to circumvent the borrow checker:

use std::marker::PhantomData;

fn foo<'b, 'a>() -> PhantomData<&'b &'a ()> {
    PhantomData
}

fn extend_lifetime<'a, 'b, T: ?Sized>(x: &'a T) -> &'b T {
    let f = foo::<'b, 'a>;
    f.baz(x)
}

trait Foo<'a, 'b, T: ?Sized> {
    fn baz(self, s: &'a T) -> &'b T;
}
impl<'a, 'b, R, F, T: ?Sized> Foo<'a, 'b, T> for F
where
    F: Fn() -> R,
    R: ProofForConversion<'a, 'b, T>,
{
    fn baz(self, s: &'a T) -> &'b T {
        self().convert(s)
    }
}

trait ProofForConversion<'a, 'b, T: ?Sized> {
    fn convert(self, s: &'a T) -> &'b T;
}
impl<'a, 'b, T: ?Sized> ProofForConversion<'a, 'b, T> for PhantomData<&'b &'a ()> {
    fn convert(self, s: &'a T) -> &'b T {
        s
    }
}

fn main() {
    let d;
    {
        let x = "Hello World".to_string();
        d = extend_lifetime(&x);
    }
    println!("{}", d);
}
�ZV&�V�

(playground)

@rustbot modify labels: A-lifetimes, A-typesystem, T-compiler
and someone please add “I-unsound 💥”.

Activity

added
A-lifetimesArea: Lifetimes / regions
T-compilerRelevant to the compiler team, which will review and decide on the PR/issue.
on Apr 24, 2021
added
I-unsoundIssue: A soundness hole (worst kind of bug), see: https://en.wikipedia.org/wiki/Soundness
on Apr 24, 2021
added
I-prioritizeIssue: Indicates that prioritization has been requested for this issue.
on Apr 24, 2021
SkiFire13

SkiFire13 commented on Apr 25, 2021

@SkiFire13
Contributor

Possible duplicate of #25860?

steffahn

steffahn commented on Apr 25, 2021

@steffahn
MemberAuthor

I wouldn't think it's a duplicate but I guess it's related, at least in the sense that there are changes to Rust that could solve both issues at once. This bug results in unsoundness even if the invalidly typed function is never called. (It is called in my example, but I think it can be refactored so that it doesn't get called. I will try to create some example code later today. Edit: Here’s a playground.) The point in this case is that the type of foo::<'b, 'a> implements Fn traits with an Output type whose validity hasn't been checked.

I guess it's similar in spirit to #82633 in this sense. Possible resolutions are either to forbid instantiating foo::<'b, 'a> with these lifetime parameters entirely or to at least make sure that the (anonymous function-)type of that instantiation doesn't implement any Fn traits. I guess I'll add @rustbot modify labels to +A-traits.

steffahn

steffahn commented on Apr 25, 2021

@steffahn
MemberAuthor

Edit: This example does, unlike the issue I described above, involve HRTBs. You might qualify everything in this and the following 3 comments of mine as a seperate / new issue. I don’t like creating too many similar “I-unsound 💥” issues though, and the main problem is similar in that there’s a type that implements a trait with an illegal associated type. (Illegal in the sense that implied bounds are violated, in particular the type is &'b &'a () or PhantomData<&'b &'a ()> in a setting where 'a: 'b might not actually hold true.) I have since renamed this topic so that it fits all the examples.

Here’s another problem involving illegal Fn implementations. Makes me think that it might be a good idea after all to have some function-types or function-pointer-types that don’t implement certain Fn-traits. This might also be relevant to the discussion of #82633, where the current proposed resolution is to disallow fn-pointers with !Sized return types, whereas an alternative approach could be to just have them not implement Fn-traits. Edit: On second thought, the situation described below is significantly different from #82633, so Iʼm not sure of the relevance of this issue for the discussion in #82633 anymore.

Onto the problem. Take trait bounds such as for<'b, 'a> Fn(&'b(), &'a()) -> PhantomData<&'b &'a ()>. The corresponding function-pointer type for<'b, 'a> fn(&'b(), &'a()) -> PhantomData<&'b &'a ()> implements this trait bound.

use std::marker::PhantomData;

fn fun<'b, 'a>(_: &'b (), _: &'a ()) -> PhantomData<&'b &'a ()> {
    PhantomData
}

fn use_fun() {
    blah(fun);
    blubb(fun);
}

fn use_closure() {
    blah(|_, _| PhantomData);
    blubb(|_, _| PhantomData);
}

fn blah(f: for<'b, 'a> fn(&'b (), &'a ()) -> PhantomData<&'b &'a ()>) {
    blubb(f);
}

fn blubb(f: impl for<'b, 'a> Fn(&'b (), &'a ()) -> PhantomData<&'b &'a ()>) {}

However, if you try to re-create an Fn-trait-style trait and try to implement it accordingly, this fails, and with good reason:

trait MyFn<Arg1, Arg2> {
    type Output;
    fn call(&self, a1: Arg1, a2: Arg2) -> Self::Output;
}

struct Fun;
impl<'b, 'a> MyFn<&'b (), &'a ()> for Fun {
    type Output = PhantomData<&'b &'a ()>;
    fn call(&self, a1: &'b (), a2: &'a ()) -> PhantomData<&'b &'a ()> {
        PhantomData
    }
}
error[E0491]: in type `&'b &'a ()`, reference has a longer lifetime than the data it references
   --> src/main.rs:51:5
    |
 51 |     type Output = PhantomData<&'b &'a ()>;
    |     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    |
 note: the pointer is valid for the lifetime `'b` as defined on the impl at 50:6
   --> src/main.rs:50:6
    |
 50 | impl<'b, 'a> MyFn<&'b (), &'a ()> for Fun {
    |      ^^
 note: but the referenced data is only valid for the lifetime `'a` as defined on the impl at 50:10
   --> src/main.rs:50:10
    |
 50 | impl<'b, 'a> MyFn<&'b (), &'a ()> for Fun {
    |          ^^

In other words, the Fn-implementation of these functions / function-pointers / closures is unsound. I’ll try to create a direct exploitation of this unsoundness later today.

steffahn

steffahn commented on Apr 25, 2021

@steffahn
MemberAuthor

I’ll try to create a direct exploitation of this unsoundness later today.

use std::marker::PhantomData;

fn unsoundness_demonstration<'b, 'a, F, T>(f: F, x: &'a T) -> &'b T
where
    for<'b_, 'a_> F: Fn(&'b_ (), &'a_ ()) -> PhantomData<&'b_ &'a_ ()>,
{
    conversion::<'b, 'a, _, _>(f, x)
}

fn conversion<'b, 'a, F, T>(f: F, x: &'a T) -> &'b T
where
    F: HelperTrait<'b, 'a>,
{
    f.convert(x)
}

trait HelperTrait<'b, 'a> {
    fn convert<T>(self, x: &'a T) -> &'b T;
}
impl<'b, 'a, F, R> HelperTrait<'b, 'a> for F
where
    F: Fn(&'b (), &'a ()) -> PhantomData<R>,
    PhantomData<R>: Proof<'b, 'a>,
{
    fn convert<T>(self, x: &'a T) -> &'b T {
        PhantomData.convert(x)
    }
}

trait Proof<'b, 'a> {
    fn convert<T>(self, x: &'a T) -> &'b T;
}

impl<'b, 'a> Proof<'b, 'a> for PhantomData<&'b &'a ()> {
    fn convert<T>(self, x: &'a T) -> &'b T {
        x
    }
}

fn fun<'b, 'a>(_: &'b (), _: &'a ()) -> PhantomData<&'b &'a ()> {
    PhantomData
}

fn extend_lifetime<'a, 'b, T>(x: &'a T) -> &'b T {
    unsoundness_demonstration(fun, x)
}

fn main() {
    let d;
    {
        let x = "Hello World".to_string();
        d = extend_lifetime(&x);
    }
    println!("{}", d);
}
�����U�

(playground)

steffahn

steffahn commented on Apr 25, 2021

@steffahn
MemberAuthor

By the way, next to function types and function pointer types and closure types, you also have dyn for<'b, 'a> Fn(&'b (), &'a ()) -> PhantomData<&'b &'a ()> as a type that implements for<'b, 'a> Fn(&'b (), &'a ()) -> PhantomData<&'b &'a ()>.

Here’s an exploitation of that trait object type:
use std::marker::PhantomData;

fn unsoundness_demonstration<'b, 'a, F, T>(x: &'a T) -> &'b T
where
    for<'b_, 'a_> F: Fn(&'b_ (), &'a_ ()) -> PhantomData<&'b_ &'a_ ()>,
{
    conversion::<'b, 'a, F, _>(x)
}

fn conversion<'b, 'a, F, T>(x: &'a T) -> &'b T
where
    F: HelperTrait<'b, 'a>,
{
    F::convert(x)
}

trait HelperTrait<'b, 'a> {
    fn convert<T>(x: &'a T) -> &'b T;
}
impl<'b, 'a, F, R> HelperTrait<'b, 'a> for F
where
    F: Fn(&'b (), &'a ()) -> PhantomData<R>,
    PhantomData<R>: Proof<'b, 'a>,
{
    fn convert<T>(x: &'a T) -> &'b T {
        PhantomData.convert(x)
    }
}

trait Proof<'b, 'a> {
    fn convert<T>(self, x: &'a T) -> &'b T;
}

impl<'b, 'a> Proof<'b, 'a> for PhantomData<&'b &'a ()> {
    fn convert<T>(self, x: &'a T) -> &'b T {
        x
    }
}

fn extend_lifetime<'a, 'b, T>(x: &'a T) -> &'b T {
    unsoundness_demonstration::<
        Box<dyn for<'b_, 'a_> Fn(&'b_ (), &'a_ ()) -> PhantomData<&'b_ &'a_ ()>>,
        _,
    >(x)
}

fn main() {
    let d;
    {
        let x = "Hello World".to_string();
        d = extend_lifetime(&x);
    }
    println!("{}", d);
}

To reiterate, having any type implement for<'b, 'a> Fn(&'b (), &'a ()) -> PhantomData<&'b &'a ()> is currently unsound.


We could talk about making a trait bound for<'b, 'a> Fn(&'b (), &'a ()) -> PhantomData<&'b &'a ()> mean something different, i.e. it could be made to only quantify over those 'b and 'a such that PhantomData<&'b &'a ()>, too, is a valid type, i.e. such that 'a: 'b holds.

However, after such a change, we would need to make sure that

F: for<'b, 'a> Fn<(&'b (), &'a ()), Output = PhantomData<&'b &'a ()>>

cannot imply

F: for<'b, 'a> Fn<(&'b (), &'a ())>

anymore. And accordingly, trait inference would need to be changed so that e.g. the F: for<'b, 'a> Fn<(&'b (), &'a ()), Output = PhantomData<&'b &'a ()>> doesn’t imply F: HelperTrait<'b1, 'a1> anymore, unless 'a1: 'b1. (HelperTrait having a blanket implementation like e.g. in one of my code examples above.)


I’d guess that answering the question of how to best solve this issue (especially the question of changing the meaning of HRTBs with associated types) might touch on T-lang responsibility. I’m not entirely sure if that’s the correct procedure while there’s an outstanding I-prioritize for T-compiler, but I’ll just add the label – @rustbot modify labels: +T-lang, +A-dst. The additional A-dst is for the trait object example.

added
A-DSTsArea: Dynamically-sized types (DSTs)
T-langRelevant to the language team
on Apr 25, 2021
changed the title [-]It’s possible to have the validity of a function return type never checked.[/-] [+]Functions / closures / trait objects can implement traits such that validity of associated types is never checked.[/+] on Apr 25, 2021

55 remaining items

Loading
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    A-DSTsArea: Dynamically-sized types (DSTs)A-associated-itemsArea: Associated items (types, constants & functions)A-closuresArea: Closures (`|…| { … }`)A-dyn-traitArea: trait objects, vtable layoutA-higher-rankedArea: Higher-ranked things (e.g., lifetimes, types, trait bounds aka HRTBs)A-lifetimesArea: Lifetimes / regionsA-trait-systemArea: Trait systemA-type-systemArea: Type systemC-bugCategory: This is a bug.I-unsoundIssue: A soundness hole (worst kind of bug), see: https://en.wikipedia.org/wiki/SoundnessP-mediumMedium priorityS-bug-has-testStatus: This bug is tracked inside the repo by a `known-bug` test.T-compilerRelevant to the compiler team, which will review and decide on the PR/issue.T-typesRelevant to the types team, which will review and decide on the PR/issue.

    Type

    No type

    Projects

    Status

    new solver everywhere

    Milestone

    No milestone

    Relationships

    None yet

      Development

      Participants

      @pnkfelix@oli-obk@Aaron1011@steffahn@SkiFire13

      Issue actions

        Functions, closures, and HRTB-trait-objects can implement traits such that validity of associated types is never checked. · Issue #84533 · rust-lang/rust