Symbolic execution Contents Example Limitations Tools History See also References External links Navigation menubibliography10.1007/978-3-540-78800-3_28Directed Symbolic Execution10.1145/1831708.183173210.1.1.348.82310.1145/2254064.2254088"KLEE: Unassisted and Automatic Generation of High-coverage Tests for Complex Systems Programs""MultiOtter: Multiprocess Symbolic Execution"10.1145/2110356.21103580734-207110.1145/2591062.2594450Symbolic Execution for finding bugsSymbolic Execution and Software Testing presentation at NASA AmesSymbolic Execution for Software Testing in Practice – Preliminary Assessment

Abstract interpretationComputer science


computer scienceabstract interpretationsymbolic simulationSymbolic computationconstraint solverDynamic program analysisbibliography




In computer science, symbolic execution (also symbolic evaluation) is a means of analyzing a program to determine what inputs cause each part of a program to execute. An interpreter follows the program, assuming symbolic values for inputs rather than obtaining actual inputs as normal execution of the program would, a case of abstract interpretation. It thus arrives at expressions in terms of those symbols for expressions and variables in the program, and constraints in terms of those symbols for the possible outcomes of each conditional branch.


The field of symbolic simulation applies the same concept to hardware. Symbolic computation applies the concept to the analysis of mathematical expressions.




Contents





  • 1 Example


  • 2 Limitations

    • 2.1 Path explosion


    • 2.2 Program-dependent efficiency


    • 2.3 Environment interactions



  • 3 Tools


  • 4 History


  • 5 See also


  • 6 References


  • 7 External links




Example


Consider the program below, which reads in a value and fails if the input is 6.


 1 int f() 
2 ...
3 y = read();
4 z = y * 2;
5 if (z == 12)
6 fail();
7 else
8 printf("OK");
9
10

During a normal execution ("concrete" execution), the program would read a concrete input value (e.g., 5) and assign it to y. Execution would then proceed with the multiplication and the conditional branch, which would evaluate to false and print OK.


During symbolic execution, the program reads a symbolic value (e.g., λ) and assigns it to y. The program would then proceed with the multiplication and assign λ * 2 to z. When reaching the if statement, it would evaluate λ * 2 == 12. At this point of the program, λ could take any value, and symbolic execution can therefore proceed along both branches, by "forking" two paths. Each path gets assigned a copy of the program state at the branch instruction as well as a path constraint. In this example, the path constraint is λ * 2 == 12 for the then branch and λ * 2 != 12 for the else branch. Both paths can be symbolically executed independently. When paths terminate (e.g., as a result of executing fail() or simply exiting), symbolic execution computes a concrete value for λ by solving the accumulated path constraints on each path. These concrete values can be thought of as concrete test cases that can, e.g., help developers reproduce bugs. In this example, the constraint solver would determine that in order to reach the fail() statement, λ would need to equal 6.



Limitations



Path explosion


Symbolically executing all feasible program paths does not scale to large programs. The number of feasible paths in a program grows exponentially with an increase in program size and can even be infinite in the case of programs with unbounded loop iterations.[1] 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]



Program-dependent efficiency


Symbolic execution is used to reason about a program path-by-path which is an advantage over reasoning about a program input-by-input as other testing paradigms use (e.g. Dynamic program analysis). However, if few inputs take the same path through the program, there is little savings over testing each of the inputs separately.



Environment interactions



Programs interact with their environment by performing system calls, receiving signals, etc. Consistency problems may arise when execution reaches components that are not under control of the symbolic execution tool (e.g., kernel or libraries). Consider the following example:


 1 int main()
2
3 FILE *fp = fopen("doc.txt");
4 ...
5 if (condition)
6 fputs("some data", fp);
7 else
8 fputs("some other data", fp);
9
10 ...
11 data = fgets(..., fp);
12

This program opens a file and, based on some condition, writes different kind of data to the file. It then later reads back the written data. In theory, symbolic execution would fork two paths at line 5 and each path from there on would have its own copy of the file. The statement at line 11 would therefore return data that is consistent with the value of "condition" at line 5. In practice, file operations are implemented as system calls in the kernel, and are outside the control of the symbolic execution tool. The main approaches to address this challenge are:


Executing calls to the environment directly. The advantage of this approach is that it is simple to implement. The disadvantage is that the side effects of such calls will clobber all states managed by the symbolic execution engine. In the example above, the instruction at line 11 would return "some datasome other data" or "some other datasomedata" depending on the sequential ordering of the states.


Modeling the environment. In this case, the engine instruments the system calls with a model that simulates their effects and that keeps all the side effects in per-state storage. The advantage is that one would get correct results when symbolically executing programs that interact with the environment. The disadvantage is that one needs to implement and maintain many potentially complex models of system calls. Tools such as KLEE,[5] Cloud9, and Otter[6] take this approach by implementing models for file system operations, sockets, IPC, etc.


Forking the entire system state. Symbolic execution tools based on virtual machines solve the environment problem by forking the entire VM state. For example, in S2E[7] each state is an independent VM snapshot that can be executed separately. This approach alleviates the need for writing and maintaining complex models and allows virtually any program binary to be executed symbolically. However, it has higher memory usage overheads (VM snapshots may be large).



Tools






































































































Tool
It can analyze Arch/Lang
url
Can anybody use it/ Open source/ Downloadable
angr
libVEX based (supporting x86, x86-64, ARM, AARCH64, MIPS, MIPS64, PPC, and PPC64)

http://angr.io/
yes
BE-PUM
x86

https://github.com/NMHai/BE-PUM
yes
FuzzBALL
VineIL / Native

http://bitblaze.cs.berkeley.edu/fuzzball.html
yes
Jalangi2

JavaScript

https://github.com/Samsung/jalangi2
yes
janala2
Java

https://github.com/ksen007/janala2
yes
JBSE
Java

https://github.com/pietrobraione/jbse
yes
jCUTE
Java

https://github.com/osl/jcute
yes
JPF
Java

http://babelfish.arc.nasa.gov/trac/jpf
yes
KeY
Java

http://www.key-project.org/
yes
Kite
LLVM

http://www.cs.ubc.ca/labs/isd/Projects/Kite/
yes
KLEE
LLVM

https://klee.github.io/
yes
Manticore
x86-64, ARMv7, Ethereum Virtual Machine (EVM) / Native

https://github.com/trailofbits/manticore/
yes
Mayhem
Binary

http://forallsecure.com
no
Mythril-Classic

Ethereum Virtual Machine (EVM) / Native

https://github.com/ConsenSys/mythril-classic
yes
Otter
C

https://bitbucket.org/khooyp/otter/overview
yes
Pathgrind[8]Native 32-bit Valgrind-based

https://github.com/codelion/pathgrind
yes
Pex

.NET Framework

http://research.microsoft.com/en-us/projects/pex/
no
pysymemu
x86-64 / Native

https://github.com/feliam/pysymemu/
yes
Rubyx

Ruby

http://www.cs.umd.edu/~avik/papers/ssarorwa.pdf
no
S2E
x86, x86-64, ARM / User and kernel-mode binaries

http://s2e.systems/
yes
SymDroid

Dalvik bytecode

http://www.cs.umd.edu/~jfoster/papers/symdroid.pdf
no
SymJS

JavaScript

http://www.cs.utah.edu/~ligd/publications/SymJS-FSE14.pdf
no
Triton
x86 and x86-64

http://triton.quarkslab.com
yes
ExpoSE
JavaScript

https://github.com/ExpoSEJS/ExpoSE
yes


History


The concept of symbolic execution was introduced academically with descriptions of: the Select system,[9]
the EFFIGY system,[10]
the DISSECT system,[11]
and Clarke's system.[12]
See a bibliography of more technical papers published on symbolic execution.



See also



  • Abstract interpretation

  • Symbolic simulation

  • Symbolic computation

  • Concolic testing

  • Control flow graph

  • Dynamic recompilation


References



  1. ^ Anand, Saswat; Patrice Godefroid; Nikolai Tillmann (2008). Demand-Driven Compositional Symbolic Execution. Tools and Algorithms for the Construction and Analysis of Systems, Lecture Notes in Computer Science. Lecture Notes in Computer Science. 4963. pp. 367–381. doi:10.1007/978-3-540-78800-3_28. ISBN 978-3-540-78799-0..mw-parser-output cite.citationfont-style:inherit.mw-parser-output .citation qquotes:"""""""'""'".mw-parser-output .citation .cs1-lock-free abackground:url("//upload.wikimedia.org/wikipedia/commons/thumb/6/65/Lock-green.svg/9px-Lock-green.svg.png")no-repeat;background-position:right .1em center.mw-parser-output .citation .cs1-lock-limited a,.mw-parser-output .citation .cs1-lock-registration abackground:url("//upload.wikimedia.org/wikipedia/commons/thumb/d/d6/Lock-gray-alt-2.svg/9px-Lock-gray-alt-2.svg.png")no-repeat;background-position:right .1em center.mw-parser-output .citation .cs1-lock-subscription abackground:url("//upload.wikimedia.org/wikipedia/commons/thumb/a/aa/Lock-red-alt-2.svg/9px-Lock-red-alt-2.svg.png")no-repeat;background-position:right .1em center.mw-parser-output .cs1-subscription,.mw-parser-output .cs1-registrationcolor:#555.mw-parser-output .cs1-subscription span,.mw-parser-output .cs1-registration spanborder-bottom:1px dotted;cursor:help.mw-parser-output .cs1-ws-icon abackground:url("//upload.wikimedia.org/wikipedia/commons/thumb/4/4c/Wikisource-logo.svg/12px-Wikisource-logo.svg.png")no-repeat;background-position:right .1em center.mw-parser-output code.cs1-codecolor:inherit;background:inherit;border:inherit;padding:inherit.mw-parser-output .cs1-hidden-errordisplay:none;font-size:100%.mw-parser-output .cs1-visible-errorfont-size:100%.mw-parser-output .cs1-maintdisplay:none;color:#33aa33;margin-left:0.3em.mw-parser-output .cs1-subscription,.mw-parser-output .cs1-registration,.mw-parser-output .cs1-formatfont-size:95%.mw-parser-output .cs1-kern-left,.mw-parser-output .cs1-kern-wl-leftpadding-left:0.2em.mw-parser-output .cs1-kern-right,.mw-parser-output .cs1-kern-wl-rightpadding-right:0.2em


  2. ^ Ma, Kin-Keng; Khoo Yit Phang; Jeffrey S. Foster; Michael Hicks (2011). Directed Symbolic Execution. Proceedings of the 18th International Conference on Statis Analysis. pp. 95–111. ISBN 9783642237010. Retrieved 2013-04-03.


  3. ^ Staats, Matt; Corina Pasareanu (2010). Parallel symbolic execution for structural test generation. Proceedings of the 19th International Symposium on Software Testing and Analysis. pp. 183–194. doi:10.1145/1831708.1831732. ISBN 9781605588230.


  4. ^ Kuznetsov, Volodymyr; Kinder, Johannes; Bucur, Stefan; Candea, George (2012-01-01). Efficient State Merging in Symbolic Execution. Proceedings of the 33rd ACM SIGPLAN Conference on Programming Language Design and Implementation. PLDI '12. New York, NY, USA: ACM. pp. 193–204. CiteSeerX 10.1.1.348.823. doi:10.1145/2254064.2254088. ISBN 978-1-4503-1205-9.


  5. ^ Cadar, Cristian; Dunbar, Daniel; Engler, Dawson (2008-01-01). "KLEE: Unassisted and Automatic Generation of High-coverage Tests for Complex Systems Programs". Proceedings of the 8th USENIX Conference on Operating Systems Design and Implementation. OSDI'08: 209–224.


  6. ^ Turpie, Jonathan; Reisner, Elnatan; Foster, Jeffrey; Hicks, Michael. "MultiOtter: Multiprocess Symbolic Execution" (PDF).


  7. ^ Chipounov, Vitaly; Kuznetsov, Volodymyr; Candea, George (2012-02-01). "The S2E Platform: Design, Implementation, and Applications". ACM Trans. Comput. Syst. 30 (1): 2:1–2:49. doi:10.1145/2110356.2110358. ISSN 0734-2071.


  8. ^ Sharma, Asankhaya (2014). Exploiting Undefined Behaviors for Efficient Symbolic Execution. Icse 2014. pp. 727–729. doi:10.1145/2591062.2594450. ISBN 9781450327688.


  9. ^ Robert S. Boyer and Bernard Elspas and Karl N. Levitt SELECT--a formal system for testing and debugging programs by symbolic execution, Proceedings of the International Conference on Reliable Software, 1975,page 234--245, Los Angeles, California


  10. ^ James C. King,Symbolic execution and program testing, Communications of the ACM, volume 19, number 7, 1976, 385--394


  11. ^ William E. Howden, Experiments with a symbolic evaluation system, Proceedings, National Computer Conference, 1976.


  12. ^ Lori A. Clarke, A program testing system, ACM 76: Proceedings of the Annual Conference, 1976, pages 488-491, Houston, Texas, United States



External links


  • Symbolic Execution for finding bugs

  • Symbolic Execution and Software Testing presentation at NASA Ames

  • Symbolic Execution for Software Testing in Practice – Preliminary Assessment


Abstract interpretation, Computer scienceUncategorized

Popular posts from this blog

Frič See also Navigation menuinternal link

Identify plant with long narrow paired leaves and reddish stems Planned maintenance scheduled April 17/18, 2019 at 00:00UTC (8:00pm US/Eastern) Announcing the arrival of Valued Associate #679: Cesar Manara Unicorn Meta Zoo #1: Why another podcast?What is this plant with long sharp leaves? Is it a weed?What is this 3ft high, stalky plant, with mid sized narrow leaves?What is this young shrub with opposite ovate, crenate leaves and reddish stems?What is this plant with large broad serrated leaves?Identify this upright branching weed with long leaves and reddish stemsPlease help me identify this bulbous plant with long, broad leaves and white flowersWhat is this small annual with narrow gray/green leaves and rust colored daisy-type flowers?What is this chilli plant?Does anyone know what type of chilli plant this is?Help identify this plant

fontconfig warning: “/etc/fonts/fonts.conf”, line 100: unknown “element blank” The 2019 Stack Overflow Developer Survey Results Are In“tar: unrecognized option --warning” during 'apt-get install'How to fix Fontconfig errorHow do I figure out which font file is chosen for a system generic font alias?Why are some apt-get-installed fonts being ignored by fc-list, xfontsel, etc?Reload settings in /etc/fonts/conf.dTaking 30 seconds longer to boot after upgrade from jessie to stretchHow to match multiple font names with a single <match> element?Adding a custom font to fontconfigRemoving fonts from fontconfig <match> resultsBroken fonts after upgrading Firefox ESR to latest Firefox