  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.
