Automatic verification of multi-threaded programs by inference of rely-guarantee specifications

• Main Authors: LE, Xuan-Bach, SANAN, David, SUN, Jun, LIN, Shang-Wei
• Format: text
• Language: English
• Published: Institutional Knowledge at Singapore Management University 2020
• Subjects: CEGAR; Concurrency; Rely-Guarantee; Theory and Algorithms
• Online Access: https://ink.library.smu.edu.sg/sis_research/5939; https://ink.library.smu.edu.sg/context/sis_research/article/6942/viewcontent/Auto_verification_MTP_2020.pdf
• Institution: Singapore Management University

Rely-Guarantee is a comprehensive technique that supports compositional reasoning for concurrent programs. However, specifications of the Rely condition - environment interference, and Guarantee condition - local transformation of thread state - are challenging to establish. Thus the construction of these conditions becomes bottleneck in automating the technique. To tackle the above problem, we propose a verification framework that, based on Rely-Guarantee principles, constructs the correctness proof of concurrent program through inferring suitable Rely -Guarantee conditions automatically. Our framework first constructs a Hoare-style sequential proof for each thread and then applies abstraction refinement to elevate these proofs into concurrent ones with appropriate Rely-Guarantee relations. Experiment results demonstrate that our approach is efficient in proving the correctness of concurrent programs.