Compact Symbolic Execution (technical report)
This is an incremental improvement for software verification and testing, addressing scalability issues in symbolic execution.
The authors tackled the problem of infinite or large symbolic execution trees by introducing compact symbolic execution, which uses templates to fold paths from loops and recursive calls into single vertices, reducing tree size without information loss and enabling finite trees for some programs where classic trees are infinite.
We present a generalisation of King's symbolic execution technique called compact symbolic execution. It is based on a concept of templates: a template is a declarative parametric description of such a program part, generating paths in symbolic execution tree with regularities in program states along them. Typical sources of these paths are program loops and recursive calls. Using the templates we fold the corresponding paths into single vertices and therefore considerably reduce size of the tree without loss of any information. There are even programs for which compact symbolic execution trees are finite even though the classic symbolic execution trees are infinite.