Symbolic verification of message passing interface programs

• Main Authors: YU, Hengbiao, CHEN, Zhenbang, FU, Xianjin, WANG, Ji, SU, Zhendong, SUN, Jun, HUANG, Chun, DONG, Wei
• Format: text
• Language: English
• Published: Institutional Knowledge at Singapore Management University 2020
• Subjects: Information Security
• Online Access: https://ink.library.smu.edu.sg/sis_research/4633; https://ink.library.smu.edu.sg/context/sis_research/article/5636/viewcontent/Symbolic_verification_of_Message_Passing_Interface_Programs_av.pdf
• Institution: Singapore Management University

Message passing is the standard paradigm of programming in high-performance computing. However, verifying Message Passing Interface (MPI) programs is challenging, due to the complex program features (such as non-determinism and non-blocking operations). In this work, we present MPI symbolic verifier (MPI-SV), the first symbolic execution based tool for automatically verifying MPI programs with non-blocking operations. MPI-SV combines symbolic execution and model checking in a synergistic way to tackle the challenges in MPI program verification. The synergy improves the scalability and enlarges the scope of verifiable properties. We have implemented MPI-SV and evaluated it with 111 real-world MPI verification tasks. The pure symbolic execution-based technique successfully verifies 57 out of the 111 tasks (51%) within one hour, while in comparison, MPI-SV verifies 99 tasks (89%). On average, compared with pure symbolic execution, MPI-SV achieves 8x speedups on verifying the satisfaction of the critical property and 5x speedups on finding violations.