4

What is the difference between implementation of static analysis and symbolic execution?

Improve this question

2 Answers 2

Reset to default
8

I really like this slide by Julian Cohen's Contemporary Automatic Program Analysis talk. In a nutshell, people like to divide program analysis into two broad categories of static and dynamic analysis. But there is really a broad spectrum of program analysis techniques that range from static to dynamic and manual to fully automatic. Symbolic execution is an interesting technique that falls somewhere in between static and dynamic analysis and is generally applied as a fully automatic approach.

Dimensions of Program Analysis

Improve this answer
Sign up to request clarification or add additional context in comments.

3 Comments

thanks. Do you know what kind of errors static analysis (e.g. compiler) can detect and symbolic execution can not detect?
It's hard to say (especially in a comment). Static analysis deals with issues of path feasibility, whereas dynamic analysis tends to deal with path coverage. Symbolic analysis is sort of in between and deals with state space explosion by logically forking the analysis at branches and solving for a set of satisfiable constraints. Most implementations I've seen spend lots of processing time in SAT/SMT solvers. This is also hard to answer because many implementations are a blend of techniques. Static analysis can be fully automatic for instance.
I create new question about that in this link: stackoverflow.com/questions/38540082/…
5

Static analysis is any off-line computation that inspects code and produces opinions about the code quality. You can apply this to source code, to virtual machine code for Java/C#/... virtual machine instruction sets, and even to binary object code. There is no "one" static analysis (although classic compiler control and dataflow often figure prominently as foundation machinery for SA); the term collectively applies to all types of mechanisms that might be used offline.

Symbolic execution is a specific kind of off-line computation that computes some approximation of what the program actually does by constructing formulas representing the program state at various points. It is called "symbolic" because the approximation is usually some kind of formula involving program variables and constraints on their values.

Static analysis may use symbolic execution and inspect the resulting formula. Or it may use some other technique (regular expressions, classic compiler flow analyses, ...) or some combination. But static analysis does not have to use symbolic execution.

Symbolic execution may be used just to show an expected symbolic result of a computation. That isn't static analysis by the above definition because there isn't any opinion formed about how good that result is. Or, the formula may be subjected to analysis, at which point it becomes part of a static analysis. As a practical matter, one may use other program analysis techniques to support symbolic execution ("this formula for variable is propagated to which reads of variable x?" is a question usually answered well by flow analysis).

You may insist that static analysis is any offline computation over your source code, at which point symbolic execution is just a special case. I don't find this definition helpful, because it doesn't discriminate between use cases well enough.

Improve this answer

12 Comments

thanks. In general way which implementation is less time-consuming?
"which is less time consuming?" This isn't about effort to implement. You choose a technology/architecture to achieve a purpose, from among the set of choices you have. But without a specific statement of purpose, you have no way to rank which of these is more sensible. If you have no specific purpose and want to do the least amount of work, you simply do nothing.
Now, you may have a specific task in mind. What you will discover is that no matter which of these technologies you'd like to use, they all take significant time to build from scratch. If you want to accomplish your purpose, what you should do is acquire the technologies you need in a way that integrates neatly, so you can focus on tuning them to solve your specific problem. My experience is that you mostly can't find these together, and so I set out to solve that problem. See semdesigns.com/Products/DMS/LifeAfterParsing.html
I said that because my time is limited. When I read articles about static analysis for example modeling-languages.com/… link and compare it with what you said in stackoverflow.com/questions/39490607/… I found several similarities for example both of them use Abstract syntax tree. This isn't clear for me what is exactly difference between them from the aspect of implementation and technologies used (not goal).
Your best bet is to use the understanding and experience that other people in the community have painfully acquired. Abstract syntax trees are sort of a good idea, but doing it the way most folks do adds complexity beleive it or not, you want abstract syntax trees derived from concrete ones if you don't want the "abstract" part to create more work. See stackoverflow.com/a/1916687/120163. But the trees are the easy part by far; Life After Parsing tells you what you need in practice, if you want to honor the fact that your time is limited. Otherwise you reinvent it all, badly.
|

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.