Trace-based symbolic analysis for atomicity violations

C Wang, R Limaye, M Ganai, A Gupta - … on Tools and Algorithms for the …, 2010 - Springer
International Conference on Tools and Algorithms for the Construction and …, 2010Springer
We propose a symbolic algorithm to accurately predict atomicity violations by analyzing a
concrete execution trace of a concurrent program. We use both the execution trace and the
program source code to construct a symbolic predictive model, which captures a large set of
alternative interleavings of the events of the given trace. We use precise symbolic reasoning
with a satisfiability modulo theory (SMT) solver to check the feasible interleavings for
atomicity violations. Our algorithm differs from the existing methods in that all reported …
Abstract
We propose a symbolic algorithm to accurately predict atomicity violations by analyzing a concrete execution trace of a concurrent program. We use both the execution trace and the program source code to construct a symbolic predictive model, which captures a large set of alternative interleavings of the events of the given trace. We use precise symbolic reasoning with a satisfiability modulo theory (SMT) solver to check the feasible interleavings for atomicity violations. Our algorithm differs from the existing methods in that all reported atomicity violations can appear in the actual program execution; and at the same time the feasible interleavings analyzed by our model are significantly more than other predictive models that guarantee the absence of false alarms.
Springer