A soundness issue

[steffahn]

use std::cell::RefCell;

use ouroboros::self_referencing;

struct Bar<'a>(RefCell<(Option<&'a Bar<'a>>, String)>);

#[self_referencing]
struct Foo {
    owner: (),
    #[borrows(owner)]
    #[not_covariant]
    bar: Bar<'this>,
    #[borrows(bar)]
    #[not_covariant]
    baz: &'this Bar<'this>,
}

impl Drop for Bar<'_> {
    fn drop(&mut self) {
        let r1 = self.0.get_mut();
        let string_ref_1 = &mut r1.1;
        let mut r2 = r1.0.unwrap().0.borrow_mut();
        let string_ref_2 = &mut r2.1;

        let s = &string_ref_1[..];
        string_ref_2.clear();
        string_ref_2.shrink_to_fit();
        println!("{}", s); // prints garbage :-), use-after free
    }
}

fn main() {
    Foo::new(
        (),
        |_| Bar(RefCell::new((None, "Hello World!".to_owned()))),
        |bar| {
            bar.0.borrow_mut().0 = Some(bar);
            bar
        },
    );
}

Don’t expect a deeper explanation from me before tomorrow 😃

[someguynamedjosh]

Cells have been the bane of my existence :P If I understand, this causes UB by creating a self-referencing struct that is not labeled as self-referencing. Rust thinks `'a` must be some external lifetime when really it's referring to itself. Problem being that the lifetime of the `bar` argument needs to be `'this` so that we can use it to build a self-referencing object, but then that allows setting its internal reference to itself. I'll take a crack at reducing this to a smaller example.

…

On Tue, Oct 5, 2021 at 1:51 PM Frank Steffahn ***@***.***> wrote: use std::cell::RefCell; use ouroboros::self_referencing; struct Bar<'a>(RefCell<(Option<&'a Bar<'a>>, String)>); #[self_referencing] struct Foo { owner: (), #[borrows(owner)] #[not_covariant] bar: Bar<'this>, #[borrows(bar)] #[not_covariant] baz: &'this Bar<'this>, } impl Drop for Bar<'_> { fn drop(&mut self) { let r1 = self.0.get_mut(); let string_ref_1 = &mut r1.1; let mut r2 = r1.0.unwrap().0.borrow_mut(); let string_ref_2 = &mut r2.1; let s = &string_ref_1[..]; string_ref_2.clear(); string_ref_2.shrink_to_fit(); println!("{}", s); // prints garbage :-), use-after free } } fn main() { Foo::new( (), |_| Bar(RefCell::new((None, "Hello World!".to_owned()))), |bar| { bar.0.borrow_mut().0 = Some(bar); bar }, ); } Don’t expect a deeper explanation from me before tomorrow 😃 — You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub <#41>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AOL2YRJXMGXK3UJO3MD3QPLUFNQL7ANCNFSM5FMTTSPQ> . Triage notifications on the go with GitHub Mobile for iOS <https://apps.apple.com/app/apple-store/id1477376905?ct=notification-email&mt=8&pt=524675> or Android <https://play.google.com/store/apps/details?id=com.github.android&referrer=utm_campaign%3Dnotification-email%26utm_medium%3Demail%26utm_source%3Dgithub>.

[steffahn]

The best analogy I can come up with is that the problem is related what ordinarily in Rust is handled by the drop check.

The problem is that ouroboros-structs like the one in the example provide in their constructor a reference &'this Bar<'this>, which claims to be a shared borrow of the Bar<'this> for its entire lifetime. But this is only okay if Bar is either covariant, or doesn’t implement Drop.

Some demonstration

use std::ptr;

struct CovariantNoDrop<'a>(*const &'a ());
struct CovariantWithDrop<'a>(*const &'a ());

struct InvariantNoDrop<'a>(*mut &'a ());
struct InvariantWithDrop<'a>(*mut &'a ());

impl Drop for CovariantWithDrop<'_> {
    fn drop(&mut self) {}
}

impl Drop for InvariantWithDrop<'_> {
    fn drop(&mut self) {}
}

fn test1() {
    fn expects_same_lifetime<'a>(_: &'a CovariantNoDrop<'a>) {}

    let x = CovariantNoDrop(ptr::null());
    expects_same_lifetime(&x); // works fine
}

fn test2() {
    fn expects_same_lifetime<'a>(_: &'a CovariantWithDrop<'a>) {}

    let x = CovariantWithDrop(ptr::null());
    expects_same_lifetime(&x); // works fine
}

fn test3() {
    fn expects_same_lifetime<'a>(_: &'a InvariantNoDrop<'a>) {}

    let x = InvariantNoDrop(ptr::null_mut());
    expects_same_lifetime(&x); // works fine
}

fn test4() {
    fn expects_same_lifetime<'a>(_: &'a InvariantWithDrop<'a>) {}

    let x = InvariantWithDrop(ptr::null_mut());
    expects_same_lifetime(&x); // error: x does not live long enough!
}

(playground)

Note that for mutable borrows, covariance doesn’t help either

use std::ptr;

struct CovariantNoDrop<'a>(*const &'a ());
struct CovariantWithDrop<'a>(*const &'a ());

struct InvariantNoDrop<'a>(*mut &'a ());
struct InvariantWithDrop<'a>(*mut &'a ());

impl Drop for CovariantWithDrop<'_> {
    fn drop(&mut self) {}
}

impl Drop for InvariantWithDrop<'_> {
    fn drop(&mut self) {}
}

fn test1() {
    fn expects_same_lifetime<'a>(_: &'a mut CovariantNoDrop<'a>) {}

    let mut x = CovariantNoDrop(ptr::null());
    expects_same_lifetime(&mut x); // works fine
}

fn test2() {
    fn expects_same_lifetime<'a>(_: &'a mut CovariantWithDrop<'a>) {}

    let mut x = CovariantWithDrop(ptr::null());
    expects_same_lifetime(&mut x); // error: x does not live long enough!
}

fn test3() {
    fn expects_same_lifetime<'a>(_: &'a mut InvariantNoDrop<'a>) {}

    let mut x = InvariantNoDrop(ptr::null_mut());
    expects_same_lifetime(&mut x); // works fine
}

fn test4() {
    fn expects_same_lifetime<'a>(_: &'a mut InvariantWithDrop<'a>) {}

    let mut x = InvariantWithDrop(ptr::null_mut());
    expects_same_lifetime(&mut x); // error: x does not live long enough!
}

(playground)

[someguynamedjosh]

Could this be leveraged by inserting some hidden code like this:

fn hypothetical_bar<'a>() -> Bar<'a> { unimplemented!() }
fn check_bar_lifetime<'a>(_: &'a Bar<'a>) { }
fn checks() {
    check_bar_lifetime(&hypothetical_bar());
}

[steffahn]

One potential fix I can think of would be:

Rule out immutably borrowing non-covariant types that implement Drop or mutably borrowing types that implement Drop by generating a test case like

fn test(f: for<'this> fn(&'this ()) -> InvariantWithDrop<'this>) {
    fn expect_same_lifetime<'this>(_: &'this InvariantWithDrop<'this>) {}
    let foo = f(&());
    expect_same_lifetime(&foo);
}

whenever a borrowing field is borrowed by another field as in

struct Foo {
    ...
    #[borrows(...)]
    foo: InvariantWithDrop<'this>,
    ...
    #[borrows(foo)]
    different_field: ...
    ...
}

and a similar test involving &'this mut InvariantWithDrop<'this> if foo was borrowed mutably by another field.

---

A different fix would be to look for some way to have multiple different 'this lifetimes. So the constructor of

#[self_referencing]
struct Foo {
    owner: (),
    #[borrows(owner)]
    #[not_covariant]
    bar: Bar<'this_owner>,
    #[borrows(bar)]
    #[not_covariant]
    baz: &'this_bar Bar<'this_owner>,
}

(syntax for declaring the struct TBD)
would then have a constructor for baz of type impl for<'this_owner, 'this_baz> FnOnce(&'this_bar Bar<'this_owner>) -> &'this_bar Bar<'this_owner>.

The constructors as well as the with_… functions would need to be updated accordingly.

---

It also seems reasonable to give the user the choice of whether they want a single homogeneous 'this lifetime with the additional restrictions to the types involved, or multiple distinct 'this lifetimes

[steffahn]

Could this be leveraged by inserting some hidden code like this

Yes, I think so. We kind-of posted at the same time :-)

Of course this is to some degree a breaking change. Note that this interoperates nicely with types such as Vec that implement Drop yet opt into #[may_dangle] to allow for things like &'a Vec<Foo<'a>>.

[someguynamedjosh]

Thanks for the input, this is really helpful. I'll take some time to develop my understanding of the problem. I think the hidden code approach would be a good first step, then possibly add granular lifetimes later to allow getting around some of the restrictions.

[steffahn]

I don’t know what your level of understanding w.r.t. dropck is – quick explanation – the basic idea is that when you have a &'a Foo<'a> and Foo implements Drop, then the call to drop(&mut self) creates a &mut Foo<'a> after the end of the lifetime of the &'a Foo<'a>. But that’s problematic, there’s really no time where this mutable reference can safely exist.

Rust’s drop check still allows this when Foo doesn’t implement Drop; it’s even allowed when it has fields that implement drop, as long as those fields don’t use that lifetime 'a: The main problem with a &mut Foo<'a> after a &'a Foo<'a> is that the Foo<'a> may contain references &'a SomeType and you must not dereference such references. As long as the compiler knows that dropping the Foo<'a> cannot touch any of such references, there’s no soundness issue. That’s why fields’ types implementing drop are fine as long as the fields don’t contain any references using the lifetime 'a. And Vec<T> promises that e.g. dropping a Vec<&'a T> won’t touch the references, by using the #[may_dangle] flag.

W.r.t. covariance, why you can create a &'a Foo<'a> if Foo is covariant: You can first create a Foo<'b> where 'b: 'a. Then take a reference &'a Foo<'b> to it and then coerce that reference to &'a Foo<'a>. At the end of the day, the destructor is called on the original Foo<'b> after that reference is gone.

I haven’t 100% thought through the question of whether allowing immutable borrows like this for covariant types is okay in the context of ouroboros. In case it turns out that it isn’t sound, the generated test code would always need to involve &'this mut InvariantWithDrop<'this>, even for an immutable borrow of a field.

[steffahn]

I haven’t 100% thought through the question of whether allowing immutable borrows like this for covariant types is okay in the context of ouroboros.

Maybe the best approach is to just let borrowck evaluate the whole situation itself, by writing – for a struct Foo – a function that takes the arguments of Foo::new as argument, uses it to initialize (without any unsafe code) a local variable for each field (in reverse drop-order), and finally creates a BorrowedFields struct for all of the (not mutably borrowed) fields.

E.g. for DocumentationExample

pub struct DocumentationExample {
    int_data: i32,
    float_data: f32,
    #[borrows(int_data)]
    int_reference: &'this i32,
    #[borrows(mut float_data)]
    float_reference: &'this mut f32,
}

something like

fn test_dropck(
    int_data: i32,
    float_data: f32,
    int_reference_builder: impl for<'this> FnOnce(&'this i32) -> &'this i32,
    float_reference_builder: impl for<'this> FnOnce(&'this mut f32) -> &'this mut f32
) {
    let int_data = int_data;
    let mut float_data = float_data;
    let int_reference = int_reference_builder(&int_data);
    let float_reference = float_reference_builder(&mut float_data);
    BorrowedFields {
        int_data: &int_data,
        int_reference: &int_reference,
        float_reference: &float_reference,
    };
}

[steffahn]

Well, so now you generate something like

    fn check_if_okay_according_to_borrow_checker(
        owner: (),
        bar_builder: impl for<'this> ::core::ops::FnOnce(&'this ()) -> Bar<'this>,
        baz_builder: impl for<'this> ::core::ops::FnOnce(&'this Bar<'this>) -> &'this Bar<'this>,
    ) {
        let mut owner = ::ouroboros::macro_help::aliasable_boxed(owner);
        let bar = bar_builder(&owner);
        let mut bar = ::ouroboros::macro_help::aliasable_boxed(bar);
        let baz = baz_builder(&bar);
        BorrowedFields {
            owner: &owner,
            bar: &bar,
            baz: &baz,
        };
    }

The usage of aliasable_boxed goes beyond what I suggested, and it’s not necessary IMO, furthermore even problematic:

Because of the aliasable boxes being introduced, now the struct

struct Bar<'a>(RefCell<(Option<&'a Bar<'a>>, String)>);

#[self_referencing]
struct Foo {
    owner: (),
    #[borrows(owner)]
    #[not_covariant]
    bar: Bar<'this>,
    #[borrows(bar)]
    #[not_covariant]
    baz: &'this Bar<'this>,
}

is rejected even when Bar does not implement Drop. This is because AliasableBox implements Dro and (unlike e.g. Box or Vec) it doesn’t (and cannot because that feature’s unstable) use #[may_dangle] attributes to tell dropck that it’s not a problem to drop e.g. an AliasableBox<&'a Foo> even after the lifetime of that contained reference has already ended.

It’s perhaps a separate question whether the approach that AliasableBox currently seems to take to implement Drop actually soundly works for may_dangle-style situations, but even if it doesn’t, IMO rather the implementation of AliasableBox should change instead of adding annoying additional restrictions to ouroboros.

[steffahn]

Here’s another example of a struct that doesn’t work in 0.13 as it stands

#[self_referencing]
struct Foo {
    o: (),
    #[borrows(mut o)]
    r: &'this mut (),
    #[borrows(mut r)]
    #[not_covariant]
    rr: &'this mut &'this mut (),
}

(Another issue with this struct is that it’s misinferring the variance of rr if not explicitly specified. If the field is a type &'this mut T, and T also contains further use of the lifetime 'this, then it’s always going to be invariant.)

[steffahn]

I’m doing some code review of the latest commits here now 😅 😉

Why did you add the (redundant) second set of : 'static bounds here? ;-P

https://github.com/joshua-maros/ouroboros/blob/7de4cf5398722e534cd12d2df27779b56d62fff7/examples/src/ok_tests.rs#L57-L61

[steffahn]

</codereview> Couldn’t find any other problems in those two commits so far. Well, except that the naming of the whole thing only talks about borrow checking, while the test (mostly) targets drop checking (dropck is AFAIK not really “part of” borrow checking). But I don’t really care about the naming of the check_if_okay_according_to_borrow_checker and even less about internal naming for the proc-macro implementation.

[steffahn]

Oh, now I get the TemplateMess change. It doesn’t compile anymore on 0.13. I suppose there’s a bug that you forgot to put the struct’s where clause on the generated check_if_okay_according_to_borrow_checker :-)

[someguynamedjosh]

@steffahn I've pushed some updates. lmk what you think:

• Include where clause on check (somehow I managed to miss the other pair of 'statics when changing the code :P)
• Require variance annotation for mutable references
• Use regular boxes for fields that are only immutably borrowed

[steffahn]

I'll take a look tomorrow.

[steffahn]

https://github.com/joshua-maros/ouroboros/blob/83f7b9f368609bcf62d9be12eaeeb65bb6cb4f2a/examples/src/lib.rs#L33-L34

These kinds of annotations seem wrong; the type &'this mut f32 should be covariant w.r.t. the lifetime 'this.

• Require variance annotation for mutable references

I think this isn’t necessary. The rules for a &'this mut … field are actually really simple:

• if it’s &'this mut TYPE and TYPE does not include any further mention of the lifetime 'this, then it’s always covariant,
• if it’s &'this mut TYPE and TYPE does include some further mention of the lifetime 'this, then it’s always not covariant.

If these rules are implemented, then there should never be a need for variance annotations on mutable references.

Interestingly, the same can not be said about shared references. Only

• if it’s &'this TYPE and TYPE does not include any further mention of the lifetime 'this, then it’s always covariant,

is true for them, but we have

• if it’s &'this TYPE and TYPE does include some further mention of the lifetime 'this, then it could be either covariant or not covariant (depending on the variance of the type TYPE)

I’ll have to take a deeper look at the logic around covariance detection to figure out how best to change it. I think the main change that would need to happen is that the detection should feature a three-valued logic, returning whether

• type is known to be covariant
• type is know not to be covariant
• it’s unknown whether the type is covariant or not

instead of the current two-valued logic, returning whether the type is know to be covariant or unknown.

---

Usage of Box seems incorrect even for immutably borrowed things. AFAIR, the soundness problem is that ownership of a struct containing a Box<T> implies that the pointer from the box is unique to its target. Since as a user of a struct like

#[self_referencing]
struct Foo {
    owner: u8,
    #[borrows(owner)]
    dependent: &'this u8
}

you can own a Foo, hence implying that the owner: Box<u8> is unique even though it’s aliased by the dependent reference.

Note that I’m not 100% certain about these things, but I personally would prefer the conservative approach to keep the AliasableBox around everywhere.

---

Note – if that wasn't clear – that in my comment above

The usage of aliasable_boxed goes beyond what I suggested […]

I’m exclusively referring to the usage of AliasableBox in the generated check_if_okay_according_to_borrow_checker function. I’m saying:

• use AliasableBox in the actual implementation of self-referencing structs,
• but don’t use any box/aliasable-box in the check_if_okay_according_to_borrow_checker check, because using AliasableBox would introduce unnecessary restrictions that are only a thing because #[may_dangle] annotations are unstable, hence AliasableBox doesn’t use them, even though – logically – it should.

---

Reviewing code like this is a bit suboptimal. If you want to follow my suggestion not to use Box fields, perhaps you could completely revert 83f7b9f (since that commit seems to be mostly the Box change), and then add just the fix for the where clauses as a separate commit, which should probably be just fine without further review. Then future commits that you’d like me to review (addressing the usage of AliasableBox in check_if_okay_according_to_borrow_checker; the variance detection; and/or other related things) could be put into a pull request first (i.e. you do them in a new branch and then go through a GitHub PR in order to merge or rebase-merge them into master); code in PRs is easier to review; also the PR helps avoiding the weirdness of doing review in this closed issue thread.

Alternatively, I can also try to create a PR myself, if you want :-)

[someguynamedjosh]

Thanks again for your continued input. I've reverted the Box changes and opened two PRs:
#44
#45