SymPaths: Symbolic Execution Meets Partial Order Reduction
Peer reviewed, Journal article
MetadataShow full item record
Original versionde Boer, F. S., Bonsangue, M., Johnsen, E. B., Pun, V. K. I., Tapia Tarifa, S. L., & Tveito, L. (2020). Sympaths: Symbolic execution meets partial order reduction. In W. Ahrendt, B. Beckert, R. Bubel, R. Hähnle, & M. Ulbrich (Eds.), Deductive software verification: Future perspectives (pp. 313-338). 10.1007/978-3-030-64354-6_13
Symbolic execution is an important technique for software analysis, which enables systematic model exploration by following all possible execution paths for a given program. For multithreaded shared variable programs, this technique leads to a state space explosion. Partial order reduction is a technique which allows equivalent execution paths to be recognized, reducing the state space explosion problem. This paper provides formal justifications for these techniques in a multithreaded setting by proving the correctness and completeness of symbolic execution for multithreaded shared variable programs, with and without the use of partial order reduction. We then show how these formal justifications carry over to prove the soundness and relative completeness of a proof system for such multithreaded shared variable programs in dynamic logic, such that partial order reduction can be used to simplify the proof construction by mitigating the state space explosion.
This is an author's accepted manuscript version (postprint) of an article published by Springer in Lecture Notes in Computer Science on 4 December 2020. The final authenticated version is available online at https://doi.org/10.1007/978-3-030-64354-6_13