Detecting, Exposing, and Classifying Sequential Consistency Violations Conference Paper uri icon


  • © 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)

published proceedings

  • 2016 IEEE 27th International Symposium on Software Reliability Engineering (ISSRE)

author list (cited authors)

  • Islam, M. M., & Muzahid, A

citation count

  • 3

complete list of authors

  • Islam, Mohammad Majharul||Muzahid, Abdullah

publication date

  • October 2016