Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

fix(cordyceps): fix use-after-free in List iterators #203

Merged
merged 4 commits into from
Jun 7, 2022

Conversation

hawkw
Copy link
Owner

@hawkw hawkw commented Jun 6, 2022

The cordyceps::List Iter and Cursor types currently have incorrect
Item types that can result in a UAF if used incorrectly. These
iterators return T::Handle as their Item types...but a Handle
owns an element, and dropping the handle can drop the element. If, for
example, the element is Box, then dropping the Handle will
deallocate the memory that the entry lives in. Similarly, dropping an
Arc entry would perform an invalid reference count decrement.

If an iterator over a list is created twice, and the list contains a
handle type such as Box<T>, then the second iterator will cause a
double free. More worryingly, accessing any entries from the list will
cause a use-after-free.

We missed this issue since

  1. there weren't any tests for the iterators, and
  2. all the tests currently use &'a Entry as the handle type, so
    dropping an entry doesn't free memory.

This branch fixes the use-after-free by changing the Iter and Cursor
types to return references to the element, rather than Handles. We
will add an additional Drain iterator that actually removes elements
from the list and returns the Handle type, in a follow-up PR.

I've added a test which fails against the current main branch.

BREAKING CHANGE:

This changes the type signature of the list::Iter and list::Cursor
types.

@hawkw hawkw requested a review from jamesmunns June 6, 2022 19:55
@hawkw hawkw changed the title fix(cordyceps): fix use-after-free in List iterators fix(cordyceps): fix use-after-free in List iterators Jun 6, 2022
@hawkw hawkw enabled auto-merge (squash) June 6, 2022 19:55
hawkw added a commit that referenced this pull request Jun 7, 2022
Signed-off-by: Eliza Weisman <eliza@buoyant.io>
hawkw added a commit that referenced this pull request Jun 7, 2022
Signed-off-by: Eliza Weisman <eliza@buoyant.io>
hawkw added a commit that referenced this pull request Jun 7, 2022
The `cordyceps::List` `Iter` and `Cursor` types currently have incorrect
`Item` types that can result in a UAF if used incorrectly. These
iterators return `T::Handle` as their `Item` types...but a `Handle`
*owns* an element, and dropping the handle can drop the element. If, for
example, the element is `Box`, then dropping the `Handle` will
deallocate the memory that the entry lives in. Similarly, dropping an
`Arc` entry would perform an invalid reference count decrement.

If an iterator over a list is created twice, and the list contains a
handle type such as `Box<T>`, then the second iterator will cause a
double free. More worryingly, accessing any entries from the list will
cause a use-after-free.

We missed this issue since

1. there weren't any tests for the iterators, and
2. all the tests currently use `&'a Entry` as the handle type, so
   dropping an entry doesn't free memory.

This branch fixes the use-after-free by changing the `Iter` and `Cursor`
types to return *references* to the element, rather than `Handle`s. We
will add an additional `Drain` iterator that actually removes elements
from the list and returns the `Handle` type, in a follow-up PR.

I've added a test which fails against the current `main` branch.

BREAKING CHANGE:

This changes the type signature of the `list::Iter` and `list::Cursor`
types.
hawkw added a commit that referenced this pull request Jun 7, 2022
When a linked list's `Handle` type owns the allocation for the item in
the list, it is necessary to drain all entries from the list and drop
them when the `List` instance is dropped. Otherwise, the entries may be
leaked.

This fixes a leak reported by Miri.

Fixes #165

BREAKING CHANGE:

The `List::new` constructor now requires a `T: Linked<list::Links<T>>`
bound.
@hawkw hawkw disabled auto-merge June 7, 2022 00:14
hawkw added 4 commits June 6, 2022 17:14
Signed-off-by: Eliza Weisman <eliza@buoyant.io>
Signed-off-by: Eliza Weisman <eliza@buoyant.io>
The `cordyceps::List` `Iter` and `Cursor` types currently have incorrect
`Item` types that can result in a UAF if used incorrectly. These
iterators return `T::Handle` as their `Item` types...but a `Handle`
*owns* an element, and dropping the handle can drop the element. If, for
example, the element is `Box`, then dropping the `Handle` will
deallocate the memory that the entry lives in. Similarly, dropping an
`Arc` entry would perform an invalid reference count decrement.

If an iterator over a list is created twice, and the list contains a
handle type such as `Box<T>`, then the second iterator will cause a
double free. More worryingly, accessing any entries from the list will
cause a use-after-free.

We missed this issue since

1. there weren't any tests for the iterators, and
2. all the tests currently use `&'a Entry` as the handle type, so
   dropping an entry doesn't free memory.

This branch fixes the use-after-free by changing the `Iter` and `Cursor`
types to return *references* to the element, rather than `Handle`s. We
will add an additional `Drain` iterator that actually removes elements
from the list and returns the `Handle` type, in a follow-up PR.

I've added a test which fails against the current `main` branch.

BREAKING CHANGE:

This changes the type signature of the `list::Iter` and `list::Cursor`
types.
When a linked list's `Handle` type owns the allocation for the item in
the list, it is necessary to drain all entries from the list and drop
them when the `List` instance is dropped. Otherwise, the entries may be
leaked.

This fixes a leak reported by Miri.

Fixes #165

BREAKING CHANGE:

The `List::new` constructor now requires a `T: Linked<list::Links<T>>`
bound.
@hawkw hawkw enabled auto-merge (rebase) June 7, 2022 00:14
@hawkw hawkw merged commit ea7412a into main Jun 7, 2022
@hawkw hawkw deleted the eliza/linked-list-iters branch June 7, 2022 00:25
hawkw added a commit that referenced this pull request Jun 7, 2022
Signed-off-by: Eliza Weisman <eliza@buoyant.io>
hawkw added a commit that referenced this pull request Jun 7, 2022
Signed-off-by: Eliza Weisman <eliza@buoyant.io>
hawkw added a commit that referenced this pull request Jun 7, 2022
The `cordyceps::List` `Iter` and `Cursor` types currently have incorrect
`Item` types that can result in a UAF if used incorrectly. These
iterators return `T::Handle` as their `Item` types...but a `Handle`
*owns* an element, and dropping the handle can drop the element. If, for
example, the element is `Box`, then dropping the `Handle` will
deallocate the memory that the entry lives in. Similarly, dropping an
`Arc` entry would perform an invalid reference count decrement.

If an iterator over a list is created twice, and the list contains a
handle type such as `Box<T>`, then the second iterator will cause a
double free. More worryingly, accessing any entries from the list will
cause a use-after-free.

We missed this issue since

1. there weren't any tests for the iterators, and
2. all the tests currently use `&'a Entry` as the handle type, so
   dropping an entry doesn't free memory.

This branch fixes the use-after-free by changing the `Iter` and `Cursor`
types to return *references* to the element, rather than `Handle`s. We
will add an additional `Drain` iterator that actually removes elements
from the list and returns the `Handle` type, in a follow-up PR.

I've added a test which fails against the current `main` branch.

BREAKING CHANGE:

This changes the type signature of the `list::Iter` and `list::Cursor`
types.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

Successfully merging this pull request may close these issues.

None yet

1 participant