Extracting Atomicity Graph And Detecting General Atomicity Violation

Introducing concurrent mechanism into programming work becomesmore and more popular due to its high efficiency. A study on Dacapobenchmarks shows that nearly2/3of the software contains concurrentbehavior. However, because of the complexity of parallel behaviors andthe indeterminism of the thread interleaving, understanding andmaintaining multi-threaded programs turns into a burden weighing heavilyupon the developers. One big problem is how to get atomicity propertiesand detect violations over them. As such atomicity rules most time arerelated with programs' semantics, and hide deeply in the programs, it isreally hard to identify them from the code.In this paper, we present EAGraph, a technique to automatically extractatomicity properties from the programs and detect various kinds ofconcurrency bugs in form of graph structure. We take advantage offrequent sub-graph mining techniques to fulfill this work. And our worktargets at inferring atomicity which is made up of both low level read-writeoperations as well as high-level functional operations on multiple variableswith rich structure information. As an experiment on ten largemulti-threaded software systems shows, EAGraph manages to findhundreds of atomicity properties with high efficiency and accuracy(with anaverage false positive of28%), meanwhile, it has detected six realconcurrency bugs based on the extracted atomicity properties.