SYMBION: Interleaving Symbolic with Concrete Execution

Symbolic execution is a powerful technique for exploring programs and generating inputs that drive them into specific states. However, symbolic execution is also known to suffer from severe limitations, which prevent its application to real-world software. For example, symbolically executing programs requires modeling their interactions with the surrounding environment (e.g., libraries, operating systems). Unfortunately, models are usually created manually, introducing considerable approximations of the programs behaviors and significant imprecision in the analysis. In addition, as the complexity of the system under analysis grows, additional models are needed, making this process unsustainable. For these reasons, in this paper we propose a novel technique that allows interleaving symbolic execution with concrete execution, focusing the symbolic exploration only on interesting portions of code. We call this approach interleaved symbolic execution. The key idea of our approach is to re-use the concrete environment to run the input program, and then synchronize the results of the environment interactions with the symbolic execution engine. As a consequence, our approach does not make any assumption about such interactions, and it is agnostic with respect to the concrete environment. We implement a prototype for this technique, SYMBION, and we demonstrate its effectiveness by analyzing real-world malware, showing that it allows us to effectively skip complex portions of code that do not need to be analyzed symbolically.