Solving the Path Explosion Problem in Symbolic Execution Looking at the Symbolic Execution limitations, there are some good solutions to the "Environment interactions" problems. However, the solutions to the path explosion problem are less than ideal.


  Solutions to the path explosion problem generally use either heuristics for path-finding to increase code coverage,[2] reduce execution time by parallelizing independent paths,[3] or by merging similar paths.[4]


The parallelizing is just adding more power to the situation which doesn't really solve it. The first and third suggestions I am not to familiar with. The first sounds like it has similar problems to testing, in that they are just opting into certain paths based on heuristics, which also doesn't seem to solve it. I am wondering if the solutions to the path explosion problem could be explained here a little bit, either the solutions listed above or anything else. Specifically I am interested in the heuristics one, and what kind of things can be done here.
The heuristic approach to solving the path explosion problem picks the next branch to explore based on some function. A simple heuristic function, yet pretty effective, would be to assign the score of a branch based on how many times it has been seen before, and then pick the one with the lowest score. This ensures that branches which haven't been seen yet are explored first instead of getting stuck in a path explosion, whose branches would have been seen many times.