Symbolic Model Checking of Software

Model checking is a popular formal verification technique for both software and hardware. The verification of concurrent software predominantly employs explicit-state model checkers, such as SPIN, that use partial-order reduction as a main technique to deal with large state spaces efficiently. In the hardware domain, the introduction of symbolic model checking has been considered a breakthrough, allowing the verification of systems clearly out-of-reach of any explicit-state model checker. This paper introduces ImProviso, a new algorithm for model checking of software that efficiently combines the advantages of partial-order reduction with symbolic exploration. IMPROVISO uses implicit BDD representations for both the state space and the transition relation together with a new implicit in-stack proviso for efficient partial-order reduction. The new approach is inspired by the Twophase partial-order reduction algorithm for explicit-state model checking. Initial experimental results show that the proposed algorithm improves the existing symbolic model checking approach and can be used to tackle problems that are not tractable using explicit-state methods.