Making symbolic execution promising by learning aggressive state-pruning strategy

We present Homi, a new technique to enhance symbolic execution by maintaining only a small number of promising states. In practice, symbolic execution typically maintains as many states as possible in a fear of losing important states. In this paper, however, we show that only a tiny subset of the states plays a significant role in increasing code coverage or reaching bug points. Based on this observation, Homi aims to minimize the total number of states while keeping promising states during symbolic execution. We identify promising states by a learning algorithm that continuously updates the probabilistic pruning strategy based on data accumulated during the testing process. Experimental results show that Homi greatly increases code coverage and the ability to find bugs of KLEE on open-source C programs.

• Software and its engineering → Software testing and debugging.