Home research People General Info Seminars Resources Intranet
Time - Thursday, October 27, 2016, 4:00 pm
Location - 302 HRBB

Maximal Causality Reduction for TSO and PSO

Shiyou Huang
Department of Computer Science and Engineering
Texas A&M University


Verifying concurrent programs is challenging due to the exponentially large thread interleaving space. The problem is exacerbated by relaxed memory models such as Total Store Order (TSO) and Partial Store Order (PSO) which further explode the interleaving space by reordering instructions. A recent advance, Maximal Causality Reduction (MCR), has shown great promise to improve verification effectiveness by maximally reducing redundant explorations. However, the original MCR only works for the Sequential Consistency (SC) memory model, but not for TSO and PSO. In this paper, we develop novel extensions to MCR by solving two key problems under TSO and PSO: 1) generating interleavings that can reach new states by encoding the operational semantics of TSO and PSO with first-order logical constraints and solving them with SMT solvers, and 2) enforcing TSO and PSO interleavings by developing novel replay algorithms that allow executions out of the program order. We show that our approach successfully enables MCR to effectively explore TSO and PSO interleavings. We have compared our approach with a recent Dynamic Partial Order Reduction (DPOR) algorithm for TSO and PSO and a SAT-based stateless model checking approach. Our results show that our approach is much more effective than the other approaches for both state-space exploration and bug finding – on average it explores 5-10X fewer executions and finds many bugs that the other tools cannot find.


Shiyou Huang is a Ph.D. candidate supervised by Dr. Jeff Huang in the ASER group of Parasol Lab, Texas A&M University. His research interests include program verification, debugging, symbolic execution, model checking and static analysis. He has already published several papers at top conferences, e.g., OOPSLA, USENIX ATC and ECOOP. He received his B.S. in Computer Science from Huazhong University of Science and Technology in May 2015.