Detecting, Exposing, and Classifying Sequential Consistency Violations
Conference Paper
Overview
Research
Identity
Additional Document Info
Other
View All
Overview
abstract
2016 IEEE. Sequential Consistency (SC) is the most intuitivememory model for parallel programs. However, modern architectures aggressively reorder and overlap memory accesses, causing SC violations. An SC violation is virtually always abug. Most prior schemes either search the entire state spaceof a program, or use a constraint solver to find SC violations. A promising recent scheme uses active testing technique butfails to be effective for SC violations involving larger numberof threads and variables, and larger codebases. We proposeOrion, the first active testing technique that can detect, expose, and classify any arbitrary SC violations in any program. Orionworks in two phases. In the first phase, it finds potentialSC violation cycles by focusing on racing accesses. In thesecond phase, it exposes each SC violation cycle by enforcingthe exact scheduling order. We present a detailed design ofOrion in the paper. We tested different concurrent algorithms, bug kernels, SPLASH2, PARSEC applications, and an opensource program, Apache. We experimented with TSO and PSOmemory models. We detected and exposed 60 SC violationsof which 15 violations involve more than two processorsand variables. Orion exposes SC violations quickly and withhigh probability. Compared to a state-of-the-art active testingtechnique, it has a much better SC violation detection ability.
name of conference
2016 IEEE 27th International Symposium on Software Reliability Engineering (ISSRE)
