Skip to content (access key 's')
Logo of Technion
Logo of CS Department
Logo of CS4People

The Taub Faculty of Computer Science Events and Talks

Modular Verification of Concurrent Programs via Sequential Model Checking
event speaker icon
Dan Rasin (M.Sc. Thesis Seminar)
event date icon
Wednesday, 24.05.2017, 11:00
event location icon
Taub 601
event speaker icon
Advisor: Prof. Orna Grumberg and Dr. Sharon Shoham
Verification of concurrent programs is known to be extremely difficult. On top of the challenges inherent in verifying sequential programs, it adds the need to consider a high (typically unbounded) number of thread interleavings. In this work, we utilize the plethora of work on verification of sequential programs for the purpose of verifying concurrent programs. We introduce a technique which reduces the verification of a concurrent program to a series of verification tasks of sequential programs, without explicitly encoding all the possible interleavings. Our approach is modular in the sense that each sequential verification task roughly corresponds to the verification of a single thread, with some additional information about the environment in which it operates. Information regarding the environment is gathered during the run of the algorithm, by need. A unique aspect of our approach is that it exploits a hierarchical structure of the program in which one of the threads, considered main, is being verified as a sequential program. Its verification process initiates queries to its environment (which may contain multiple threads). Those queries are answered by sequential verification, if the environment consists of a single thread, or, otherwise, by applying the same hierarchical algorithm on the environment. Our technique is fully automatic, and allows us to use any off-the-shelf sequential model-checker. We implemented our technique in a tool called CoMuS and evaluated it against existing tools for concurrent verification.