Efficient verification of program fragments:Eager POR

Software verification of concurrent programs is hampered by an exponentially growing state space due to non-deterministic process scheduling. Partial order reduction (POR)-based verification has proven to be a powerful technique to handle large state spaces. In this paper, we propose a novel dynamic POR algorithm, called Eager POR (epor), that requires considerably less overhead during state space exploration than existing algorithms. epor is based on a formal characterization of program fragments for which exploration can be scheduled in advance and dependency checks can be avoided. We show the correctness of this characterization and evaluate the performance of epor in comparison to existing state-of-the-art dynamic POR algorithms. Our evaluation shows substantial improvement in the runtime performance by up to 91%. © Springer International Publishing AG 2016