Making symbolic execution promising by learning aggressive state-pruning strategy

Abstract

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.

BibTeX

@inproceedings{Cha-Oh:FSE20,
  author    = {Sooyoung Cha and
               Hakjoo Oh},
  title     = {Making symbolic execution promising by learning aggressive state-pruning strategy},
  booktitle = {{ESEC/SIGSOFT} {FSE}},
  pages     = {147--158},
  publisher = {{ACM}},
  year      = {2020},
}

Making symbolic execution promising by learning aggressive state-pruning strategy

Abstract

Related papers