Postconditioned Symbolic Execution
Authors:
- Qiuping YiQYQiuping Yi
- Zijiang YangZYZijiang Yang
- Shengjian GuoSGShengjian Guo
- Chao WangCWChao Wang
- Jian LiuJLJian Liu
- Chen ZhaoCZChen Zhao
- 1 April 2015
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 21594848,p. 1-10
Abstract
Symbolic execution is emerging as a powerful technique for generating test inputs systematically to achieve exhaustive path coverage of a bounded depth. However, its practical use is often limited by path explosion because the number of paths of a program can be exponential in the number of branch conditions encountered during the execution. To mitigate the path explosion problem, we propose a new redundancy removal method called postconditioned symbolic execution. At each branching location, in addition to determine whether a particular branch is feasible as in traditional symbolic execution, our approach checks whether the branch is subsumed by previous explorations. This is enabled by summarizing previously explored paths by weakest precondition computations. Postconditioned symbolic execution can identify path suffixes shared by multiple runs and eliminate them during test generation when they are redundant. Pruning away such redundant paths can lead to a potentially exponential reduction in the number of explored paths. We have implemented our method in the symbolic execution engine KLEE and conducted experiments on a large set programs from the GNU Coreutils suite. Our results confirm that redundancy due to common path suffix is both abundant and widespread in real- world applications.Keywords
This publication has 22 references indexed in Scilit:
- Green2012
- Efficient state merging in symbolic execution2012
- A Complete Method for Symmetry Reduction in Safety VerificationLecture Notes in Computer Science, 2012
- Cloud9ACM SIGOPS Operating Systems Review, 2010
- Lazy Annotation for Program Testing and Verification2010
- A survey of new trends in symbolic execution for software testing and analysisInternational Journal on Software Tools for Technology Transfer, 2009
- An Interpolation Method for CLP Traversal2009
- Compositional dynamic test generation2007
- CUTE and jCUTE: Concolic Unit Testing and Explicit Path Model-Checking Tools2006
- CUTE2005