[concurrency-interest] Paper-> Exposing Non-Atomic Methods of Concurrent Objects

Kimo Crossman kimo at webnetic.net
Thu Jul 6 09:37:35 EDT 2017


Exposing Non-Atomic Methods of Concurrent Objects
Michael Emmi <https://arxiv.org/find/cs/1/au:+Emmi_M/0/1/0/all/0/1>, Constantin
Enea <https://arxiv.org/find/cs/1/au:+Enea_C/0/1/0/all/0/1>
(Submitted on 28 Jun 2017)
In particular, we identify 10 classes in the
java.util.concurrent package which implement queues, deques, sets, and
key-value maps. For each class we
select a small set of core methods which are believed to behave atomically.
These core methods represent the
most basic operations, e.g., a key-value map’s put, get, remove, and
containsKey methods.

Multithreaded software is typically built with specialized concurrent
objects like atomic integers, queues, and maps. These objects' methods are
designed to behave according to certain consistency criteria like
atomicity, despite being optimized to avoid blocking and exploit
parallelism, e.g., by using atomic machine instructions like compare and
exchange (cmpxchg). Exposing atomicity violations is important since they
generally lead to elusive bugs that are difficult to identify, reproduce,
and ultimately repair.
In this work we expose atomicity violations in concurrent object
implementations from the most widely-used software development kit: The
Java Development Kit (JDK). We witness atomicity violations via simple test
harnesses containing few concurrent method invocations. While stress
testing is effective at exposing violations given catalytic test harnesses
and lightweight means of falsifying atomicity, divining effectual catalysts
can be difficult, and atomicity checks are generally cumbersome. We
overcome these problems by automating test-harness search, and establishing
atomicity via membership in precomputed sets of acceptable return-value
outcomes. Our approach enables testing millions of executions of each
harness each second (per processor core). This scale is important since
atomicity violations are observed in very few executions (tens to hundreds
out of millions) of very few harnesses (one out of hundreds to thousands).
Our implementation is open source and publicly available
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://cs.oswego.edu/pipermail/concurrency-interest/attachments/20170706/c5f11db3/attachment.html>

More information about the Concurrency-interest mailing list