Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
, symbolic execution (also symbolic evaluation) refers to the analysis of programs by tracking symbolic rather than actual values, a case of abstract interpretation
Abstract interpretation
In computer science, abstract interpretation is a theory of sound approximation of the semantics of computer programs, based on monotonic functions over ordered sets, especially lattices. It can be viewed as a partial execution of a computer program which gains information about its semantics In...
In computer science, a simulation is a computation of the execution of some appropriately modelled state-transition system. Typically this process models the complete state of the system at individual points in a discrete linear time frame, computing each state sequentially from its predecessor...
Symbolic computation or algebraic computation, relates to the use of machines, such as computers, to manipulate mathematical equations and expressions in symbolic form, as opposed to manipulating the approximations of specific numerical quantities represented by those symbols...
applies the concept to the analysis of mathematical expressions.
Symbolic execution is used to reason about all the inputs that take the same path through a program.
Example
Consider the program below, which reads in a value and fails if the input is 6. If this program is symbolically executed, a special symbolic variable (as distinct from the program's variables) is associated with the values returned from the read function. These symbolic variables, and expressions of them are tracked in a special symbolic state. The symbolic variable, which we call s, is assigned to y in the symbolic state, later when y is multiplied by two, y is updated to contain the expression 2 * s.
At any control transfer instructions, such as the y
12
, a Path Constraint is updated to track which branch was taken. In this example assuming the condition is true, the Path Constraint is updated, from being empty, to contain: 2 * s 12.
y = read
y = 2 * y
if (y
12)
fails
print("OK")
By negating some of the conditions in the Path Constraint, and by using a constraint solver to obtain satisfying assignments to the modified Path Constraint it is possible to generate inputs that explore new parts of the program.
Testing
Symbolic execution is useful for software testing because it can analyse if and when errors in the code may occur. It can be used to predict what code statements do to specified inputs and outputs. It is also important for considering path traversal.
Limitations
Symbolic execution is used to reason about a program path-by-path. This may be superior to reasoning about a program, like Dynamic program analysis
Dynamic program analysis
Dynamic program analysis is the analysis of computer software that is performed by executing programs built from that software system on a real or virtual processor. For dynamic program analysis to be effective, the target program must be executed with sufficient test inputs to produce interesting...
does, input-by-input. But if few inputs take the same path through the program, there is no saving over testing each of the inputs separately.
Addressing the path explosion of symbolic execution is a research problem
.
History
The concept of symbolic execution was introduced academically with descriptions of: the Select system
,
the EFFIGY system
,
the DISSECT system
,
and Clarke's system
.
See a bibliography of more technical papers published on symbolic execution.
In computer science, abstract interpretation is a theory of sound approximation of the semantics of computer programs, based on monotonic functions over ordered sets, especially lattices. It can be viewed as a partial execution of a computer program which gains information about its semantics In...
In computer science, a simulation is a computation of the execution of some appropriately modelled state-transition system. Typically this process models the complete state of the system at individual points in a discrete linear time frame, computing each state sequentially from its predecessor...
Symbolic computation or algebraic computation, relates to the use of machines, such as computers, to manipulate mathematical equations and expressions in symbolic form, as opposed to manipulating the approximations of specific numerical quantities represented by those symbols...
Concolic testing is a hybrid software verification technique that interleaves concrete execution with symbolic execution, a classical technique that treats program variables as symbolic variables...
The source of this article is wikipedia, the free encyclopedia. The text of this article is licensed under the GFDL.
