Skip to content

Zip may call __iterator_get_unchecked twice with the same index #82291

Closed
@SkiFire13

Description

@SkiFire13
Contributor

Here __iterator_get_unchecked is called for potential side effects until self.index == self.a.size(), ignoring however that it could have already been called in next_back with those indexes.

} else if A::may_have_side_effect() && self.index < self.a.size() {
let i = self.index;
self.index += 1;
// match the base implementation's potential side effects
// SAFETY: we just checked that `i` < `self.a.len()`
unsafe {
self.a.__iterator_get_unchecked(i);
}
None

Playground link that demonstrates how this can be exploited to get two mutable references to the same data and cause an use-after-free bug.

Activity

added
I-unsoundIssue: A soundness hole (worst kind of bug), see: https://en.wikipedia.org/wiki/Soundness
T-libsRelevant to the library team, which will review and decide on the PR/issue.
on Feb 19, 2021
added
I-prioritizeIssue: Indicates that prioritization has been requested for this issue.
on Feb 19, 2021
hameerabbasi

hameerabbasi commented on Feb 19, 2021

@hameerabbasi
Contributor

Assigning P-critical as part of the WG-prioritization discussion on Zulip.

added and removed
I-prioritizeIssue: Indicates that prioritization has been requested for this issue.
on Feb 19, 2021
the8472

the8472 commented on Feb 19, 2021

@the8472
Member

The gift that keeps on giving 🤣

Maybe it is time to get rid of TrustedRandomAccess as it exists today and replace it with a slightly safer (but still unsafe) variant? One that imposes the additional requirement on the caller that it must bring the iterator back into a safe state after it is done iterating.

The upside would be eliminating a lot of code in ZipImpl and enabling the same optimization for vec::IntoIter<T> where T: Drop and similar sources.
While the downside would be that external iteration (i.e. for loops and manual calls to next()) would cease to benefit from TrustedRandomAccess optimizations and only internal iteration methods (including for_each) would continue to do so.

SkiFire13

SkiFire13 commented on Feb 19, 2021

@SkiFire13
ContributorAuthor

I don't know, I feel like that would just make more complex to upheld the invariants. IMO a good improvement over the current __iterator_get_unchecked would be separating forward and backward iteration, this way it becomes easier to keep track of the state and I think would also make it possible to implement them for vec::IntoIter<T> where T: Drop

the8472

the8472 commented on Feb 19, 2021

@the8472
Member

I don't see how separating the forward and backward state would help with a drop implementation. The issue is that the source (IntoIter) currently does not have access to that state, instead the consumer drives the iteration by direct access through __iterator_get_unchecked and never informs the source about it.

SkiFire13

SkiFire13 commented on Feb 19, 2021

@SkiFire13
ContributorAuthor

It would help because it allows the source iterator to keep track of its state by updating it when the method is called. Anyway, looks like someone already tried this approach back in 2016 and it resulted in worse optimizations, but maybe LLVM got better in the meantime, or maybe that implementation could have been better.

Anyway I don't think this is the right place to discuss this, a topic on zulip would probably be better.

added a commit that references this issue on Mar 6, 2021

Rollup merge of rust-lang#82292 - SkiFire13:fix-issue-82291, r=m-ou-se

fbdc900

10 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

    C-bugCategory: This is a bug.I-unsoundIssue: A soundness hole (worst kind of bug), see: https://en.wikipedia.org/wiki/SoundnessP-criticalCritical priorityT-libsRelevant to the library team, which will review and decide on the PR/issue.

    Type

    No type

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

      Participants

      @the8472@hameerabbasi@SkiFire13@jackh726@rustbot

      Issue actions

        Zip may call __iterator_get_unchecked twice with the same index · Issue #82291 · rust-lang/rust