Parallel SMT Solving and Concurrent Symbolic Execution

Abstract

Satisfiability Modulo Theories (SMT) solving is a fundamental tool in numerous areas of computer science, where problems are expressed as logical formulas whose satisfiability has to be decided. State-of-the-art solvers can handle many real-world problems efficiently, however, SMT solving is an NP-hard problem, and the strong reliance on the solvers typically makes them the dominating performance hot spot of the systems utilizing them. Symbolic execution is a software analysis method used for automated high-coverage test generation, among others. It relies heavily on SMT solving and spends substantial amount of its run time, commonly more than 90%, in solver activities. In this paper, we investigate how symbolic execution can benefit from the use of general-purpose, parallel SMT solving. We present design, prototypical implementation, and evaluation of a linearly scalable SMT solver cluster and an extension of the KLEE symbolic execution engine, offering concurrent execution and asynchronous constraint solving. We show that, depending on the characteristics of the program being analyzed, KLEE's performance is improved by up to 7.6x with the help of our approach.