Marathon: Detecting Atomic Set Serializability Violations With Conflict Graphs

Title
Marathon: Detecting Atomic Set Serializability Violations With Conflict Graphs
Authors
Venue
RV 2011, 42%=22/?

Recent research has proposed several analyses to mitigate the fact that finding concurrency bugs in multi-threaded software is notoriously hard. This work proposes a new analysis based on a correctness criterion called "atomic-set serializability", which incorporates both race conditions and traditional atomicity/serializability. We present a novel analysis based on conflict cycle detection that is guaranteed to find all violations in the intercepted execution trace. A set of heuristics automatically determines all annotations required for atomic-set serializability. We implemented the analysis and evaluated it on a suite consisting of real programs and benchmarks. The evaluation demonstrates the usefulness of our heuristics by finding a number of known (as well as new) violations with competitive overhead and a very low false positive rate.

[doi]
@inproceedings{DBLP:conf/rv/SumnerHD11,
  author    = {William N. Sumner and
               Christian Hammer and
               Julian Dolby},
  title     = {Marathon: Detecting Atomic-Set Serializability Violations
               with Conflict Graphs},
  booktitle = {RV},
  year      = {2011},
  pages     = {161-176},
  ee        = {http://dx.doi.org/10.1007/978-3-642-29860-8_13},
  crossref  = {DBLP:conf/rv/2011},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}