Use after free in Michael-Scott queue?

[ghost]

Queues that suffer from the problem:

• MsQueue
• SegQueue
• channel::unbounded() (see Potential subtle unsafe memory reclaim #237, thanks to @Pslydhh)
• Queue in crossbeam-epoch

---

Consider the following scenario in MsQueue...

Suppose the current epoch is E. The queue is empty, meaning head and tail are pointing to the sentinel node (let's call it node0).
In other words, head = node0, tail = node0, node0.next = null.

The following happens next...

Thread T1 gets pinned in epoch E and pushes a new value into the queue by allocating a new node node1 and then it does node0.next.cas(null, node1). The next operation it needs to do is tail.cas(node0, node1), but the thread gets yielded first so tail is still node0.

The queue is now: head = node0, tail = node0, node0.next = node1, node1.next = null.

Thread T2 gets pinned in epoch E and pops a value from the queue with head.cas(node0, node0.next). The CAS succeeds and head becomes node1. Then we call defer_destroy(node0), which means node0 becomes garbage marked with epoch E. The thread then exits.

The queue is now: head = node1, tail = node0, node0.next = node1, node1.next = null.

The global epoch gets advanced to E+1.

Thread T3 gets pinned in epoch E+1 and attempts to push a new value into the queue. It allocates a new node called node2, loads the tail pointer and gets node0. Then, it would attempt to do node0.next.cas(null, node2), but first it yields...

Thread T1 resumes, sets tail to node1, and exits.

The queue is now: head = node1, tail = node1, node1.next = null.

The global epoch is advanced to E+2. Garbage from epoch E is collected and so node0 gets deallocated.

Thread T3 resumes and attempts to continue with node0.next.cas(null, node2), but node0 has been destroyed. This is use-after-free!

---

To solve this problem, I propose we just relax the invariant used by defer.

Currently, the invariant is: We may use defer to destroy an object only if it will become inaccessible when all active guards get dropped.

I propose we change it to: We may use defer to destroy an object only if it will become inaccessible when all active guards and future guards overlapping with them get dropped.

In other words, instead of saying "call defer if the object is inaccessible" we'd say "call defer if it is inaccessible or if it will become inaccessible before all active guards get dropped".

The PR fixing this would simply change the global_epoch - garbage_epoch >= 2 invariant to global_epoch - garbage_epoch >= 3.

cc @Pslydhh @jeehoonkang

[Pslydhh]

It seems like based on the invariant:

If a thread accesses an unlinked object, it accesses it at most once.
So in the next epoch, it can't.

This looks right to me, now we no need to modify the source code to avoid such errors.

[blitzerr]

@stjepang If its okay, I would like to work on this

[jeehoonkang]

I think this issue is related to #221, especially "Using small epoch numbers" in #221 (comment) . This can also solve the problem of epoch wraparound. I'll write down more details soon.

[blitzerr]

Thanks a lot @jeehoonkang. It will be much appreciated as I am new to rust and to crossbeam. I am very interested in concurrency and crossbeam. Thanks again.

[jeehoonkang]

@stjepang Thank you for reporting this. It seems much deeper than I first expected... I'd like to spend a little bit more thinking on this issue...

[blitzerr]

Any updates @jeehoonkang ? Anything I can start looking at ?

…

On Thu, Aug 8, 2019, 22:03 Jeehoon Kang ***@***.***> wrote: @stjepang <https://github.com/stjepang> Thank you for reporting this. It seems much deeper than I first expected... I'd like to spend a little bit more thinking on this issue... — You are receiving this because you commented. Reply to this email directly, view it on GitHub <#238?email_source=notifications&email_token=AG3EF4LODVPKUVNQQ75CMGTQDT3DXA5CNFSM4GGWVPYKYY3PNVWWK3TUL52HS4DFVREXG43VMVBW63LNMVXHJKTDN5WW2ZLOORPWSZGOD35THHI#issuecomment-519779229>, or mute the thread <https://github.com/notifications/unsubscribe-auth/AG3EF4O3RWARAYKS5QKV54LQDT3DXANCNFSM4GGWVPYA> .

[blitzerr]

ping @jeehoonkang @stjepang any mentoring notes on the issue ?

[tomtomjhj]

Hi @blitzerr. I discussed this problem with @jeehoonkang and here is the summary.

TL;DR;

• It's enough to tag the block with the local epoch in which it was defer_destroy'd. Using the global epoch is fine too, but it's an overkill.
• If the garbage is tagged with E, it can be free'd in E+3.
• We've already implemented above changes as a part of our recent project, along with many other things. We are planning to merge some of them into crossbeam upstream. The paper summarizes hazard pointer and EBR (with E+3 reclamation scheme as described above) and proposes a new scheme that integrates HP and EBR.

Details

• I'll use some figures and notations from our paper.
• It's basically a re-statement of the example @stjepang gave.

Requirement for retirement (defer_destroy) under "free when current_epoch - garbage_local_epoch >= 3 scheme"

If a block b is retired in epoch E, then b should be unreachable in epoch >= E+2. That is, b should be unlinked from the shared memory (all references to b are removed) before the global epoch advances to E+2.

According to the figure 5 in the paper, use-after-free cannot occur if this condition is met. In fact, this requirement is just a direct description of the figure.

Note that Requirement 2.1 from the paper implies this requirement. Requirement 2.1 can be used for proving safety of some algorithm under EBR. However, Requirement 2.1 doesn't apply to MSQueue as you can see in the example by stjepang. (Queue::pop_internal fails to completely unlink the head from the shared memory if self.head and self.tail coincide.) So we have to show that the more general requirement presented above holds for MSQueue.

MSQueue satisfies the requirement

The only interesting situation is the setting where defer_destroy is called on head (snapshot of self.head in pop) when self.head and self.tail coincide, because this is the only case that doesn't satisfy Requirement 2.1.
Since it seems that the example stjepang gave is the only possible case, I'll use the notations from it.

Claim: All references to node0 in shared memory are removed before the global epoch advances to E+2.

• In order for the global epoch to advance to E+2, T1 should quit epoch E.
• In order for T1 to quit E, T1 should finish executing let _ = self.tail.compare_and_set(onto, new, Release, guard); in push_internal. The result doesn't matter since both cases imply that self.tail no longer points to node0.

Remark

• I'm sorry for the late reply.
• I think there might be a general way to characterize an algorithm that is compatible with EBR with "free when current_epoch - garbage_local_epoch >= n" scheme.
• Please let us know if you have any questions or opinions about this issue and our paper!

[blitzerr]

Thanks a lot @tomtomjhj for the link to the paper. I will read it and get back to you if I have questions, which I am sure I will have many :)

[tomtomjhj]

@stjepang We actually found out that free at E+3 is still buggy because of a similar scenario in which the thread 2 first pins at E and sleeps until the thread 1 pins at E+1 and gets yielded just before the pushing CAS as in your scenario. So in this scenario the actual sequence of modifications of the queue by thread 1 and 2 is identical but the epoch in which the "real unlinking" happens at E+1 instead of E. In this case, a thread that pins at E+2 may access the retired node0 via tail. So even if deallocation of node0 is deferred to E+3, there is no happens-before relation between this access and deallocation.

The real problem is that the implementation doesn't faithfully follow the original MSQueue algorithm. The original pop function advances tail pointer in cases like this scenario so that defer_destroy is called only for nodes that are actually unlinked. This is what other implementations do, e.g. libcds.
Another approach is to advance the tail pointer if the head CAS succeeds.

[twmb]

To be clear, it sounds like the four queues mentioned in the open of this issue are all effectively potentially unsafe. If that is true, I think it's worth it to disclose this information in the documentation for these queues. My understanding was that SegQueue was safe for production, but I'm not so sure now that I know there is a potential use after free issue with it.

[cynecx]

Afaict, crossbeam-channel and crossbeam-queue aren't affected by this because they don't depend on crossbeam-epoch anymore, no?

[twmb]

@cynecx thanks for pointing that out, I think that's true. It doesn't look like anything in this repo is dependent on crossbeam_epoch anymore! It may be worth it to change the title of this issue.

[cynecx]

@twmb Well, actually there is, it's crossbeam-deque ;).

[Shnatsel]

Use-after-free could be an exploitable security vulnerability. Please make a semver-compatible release with a fix and file a security advisory so that dependent crates would know to upgrade to a fixed version.