Backward Symbolic Execution with Loop Folding

Warning

This publication doesn't include Faculty of Economics and Administration. It includes Faculty of Informatics. Official publication website can be found on muni.cz.
Authors

CHALUPA Marek STREJČEK Jan

Year of publication 2021
Type Article in Proceedings
Conference Static Analysis - 28th International Symposium, SAS 2021, Chicago, IL, USA, October 17-19, 2021, Proceedings
MU Faculty or unit

Faculty of Informatics

Citation
Web https://link.springer.com/chapter/10.1007%2F978-3-030-88806-0_3
Doi http://dx.doi.org/10.1007/978-3-030-88806-0_3
Keywords symbolic execution;k-induction;backward symbolic execution;inductive invariants;invariants
Description Symbolic execution is an established program analysis tech- nique that aims to search all possible execution paths of the given pro- gram. Due to the so-called path explosion problem, symbolic execution is usually unable to analyze all execution paths and thus it is not convenient for program verification as a standalone method. This paper focuses on backward symbolic execution (BSE), which searches program paths backwards from the error location whose reachability should be proven or refuted. We show that this technique is equivalent to performing k-induction on control-flow paths. While standard BSE simply unwinds all program loops, we present an extension called loop folding that aims to derive loop invariants during BSE that are sufficient to prove the unreachability of the error location. The resulting technique is called backward symbolic execution with loop folding (BSELF). Our experiments show that BSELF performs better than BSE and other tools based on k-induction when non-trivial benchmarks are considered. Moreover, a sequential combination of symbolic execution and BSELF achieved very competitive results compared to state-of-the-art verification tools.
Related projects:

You are running an old browser version. We recommend updating your browser to its latest version.