A Survey of Satisfiability Modulo Theory <s> Symbolic Execution <s> This paper describes the symbolic execution of programs. Instead of supplying the normal inputs to a program (e.g. numbers) one supplies symbols representing arbitrary values. The execution proceeds as in a normal execution except that values may be symbolic formulas over the input symbols. The difficult, yet interesting issues arise during the symbolic execution of conditional branch type statements. A particular system called EFFIGY which provides symbolic execution for program testing and debugging is also described. It interpretively executes programs written in a simple PL/I style programming language. It includes many standard debugging features, the ability to manage and to prove things about symbolic expressions, a simple program testing manager, and a program verifier. A brief discussion of the relationship between symbolic execution and program proving is also included. <s> BIB001 </s> A Survey of Satisfiability Modulo Theory <s> Symbolic Execution <s> SAGE has had a remarkable impact at Microsoft. <s> BIB002
In symbolic program execution BIB001 , a program is executed as though operating on symbolic inputs. Along a straight path in the program, the semantics of the instructions and tests encountered accumulate as a path condition, expressing the relationship between the final values and the inputs. In case a branching instruction is encountered, the analyzer tests whether either branch may be taken by checking for a solution to the conjunction of the path condition and the guard associated with the branch: branches for which a solution is known not to exist are not retained for the rest of the analysis. The analysis thus explores a tree of possible executions, which in general does not cover all possible executions of the program: this is acceptable in bug-finding applications. Pure symbolic execution may prove infeasible due to the large number of paths to explore. This is especially true if the program involves loads and writes to memory, due to the aliasing conditions to test ("does this read correspond to this write?"). Because of this, often what is done is a mixture of concrete and symbolic execution, dubbed concolic: sometimes a non-symbolic value is picked (e.g. memory allocation addresses) for simpler execution. In whitebox fuzzing, concolic execution is applied from symbolic values coming from external inputs (files, network communications) so as to reach security hazards BIB002 .