static and dynamic code analysis
Asked Answered
I

2

7

I found several questions about this topic, and all of them with lot of references, but still I don't have a clear idea about that, because most of the references speak about concrete tools and not about the concept in general of the analysis. Thus I have some questions:

About Static analysis: 1. I would like to have a reference, or a summary of which techniques are successful and have more relevance nowadays. 2. What really can they do about discovering bugs, can we make a summary or it is depending of the tool?

About symbolic execution: 1. Where could be enclose symbolic execution? I guess depending of the approach, I would like to know if they are dynamic analysis, or mix of static and dynamic analysis if it is possible to determine.

I found problems to differentiated the two different techniques in the tools, even I think I know the theoretical difference.

I'm actually working with C Thanks in advance

Isomorphism answered 14/10, 2012 at 17:21 Comment(1)
Is there something missing in the answer below? If yes, tell me. If no, please mark it as solution. Zane.Nilgai
N
8

I'm trying to give a short answer:

Static analysis looks at the syntactical structure of code and draws conclusions about the program behavior. These conclusions must not always be correct.

A typical example of static analysis is data flow analysis, where you compute sets like used, read, write for every statement. This will help to find e.g. uninitialized values.

You can also analyze the code regarding code-patterns. This way, these tools can be used to check if you are complying to a specific coding standard. A prominent coding standard example is MISRA. This coding standard is used for safety critical systems and avoids problematic constructs in C. This way you can already say a lot about the robustness of your applications against memory leaks, dangling pointers, etc.

Dynamic analysis is not looking at the syntax only, but takes state information into account. In symbolic execution, you are adding assumptions about the possible values of all variables to the statements.

The most expensive and powerful method of dynamic analysis is model checking, where you really look at all possible execution states of the system. You can think of a model checked system as a system that is tested with 100% coverage - but there are of course a lot of practical problems that prevent real systems to be checked that way.

These methods are very powerful, and you can gain a lot from the static code analysis tools especially when combined with a good coding standard.

A feature my software team found really impressive is e.g. that it will tell you in C++ when a class with virtual methods does not have a virtual destructor. Easy to check in fact, but really helpful.

The commercial tools are very expensive, but worth the money, once you learned how to use them. A typical problem in the beginning is that you will get a lot of false alarms, and don't know where to look for the real problem.

Note that nowadays g++ has some of this stuff already built-in, and that you can use something like pclint which is free.

Sorry - this is already getting quite long...hope it's interesting.

Nilgai answered 14/10, 2012 at 17:42 Comment(4)
I'm developing a commercial static analyzer. IMHO, symbolic execution and model checking are also static analysis. And a dynamic analysis part of this answer actually explains semantic analysis.Fula
@ihji: Running a program symbolically is like running it in parallel for several test data sets. Checking a predicate on a model is in fact executing it for a set of test data in parallel. It is true, you will find both techniques listed under "static" in testing literature. Still, both techniques do not only look at the control flow graph, but they execute the system - as said, they take state information into account that is not available from the control flow graph.Nilgai
I think we defined a different meaning of "execution". I used the word execution for "executing a compiled binary file". Maybe your definition was closer to "semantically analyze" or "estimating semantics" or "interpreting the program on the analyzer".Fula
@ihji: I don't want to be mean, just would like to challenge you: is running a Java application "executing a compiled binary" or is it "symbolic execution" (with a singleton for each possible value)?Nilgai
F
4

The term "static analysis" means that the analysis does not actually run a code. On the other hand, "dynamic analysis" runs a code and also requires some kinds of real test inputs. That is the definition. Nothing more.

Static analysis employs various formal methods such as abstract interpretation, model checking, and symbolic execution. In general, abstract interpretation or model checking is suitable for software verification. Symbolic execution is more appropriate for the purpose of bug finding.

Symbolic execution is categorized into static analysis. However, there is a hybrid method called concolic execution which uses both symbolic execution and dynamic testing.

Added for Zane's comment:

Maybe my explanation was little confusing.

The difference between software verification and bug finding is whether the analysis is sound or not. For example, when we say the buffer overrun analyzer is sound, it means that the analyzer must report all possible buffer overruns. If the analyzer reports nothing, it proves the absence of buffer overruns in the target program. Because model checking is the method that guarantees soundness, it is mostly used for software verification.

On the other hands, symbolic execution which is actively used by today's most commercial static analyzers does not guarantee soundness since sound analysis inherently issues lots, lots of false positives. For the purpose of bug finding, it is more important to reduce false positives even if some true positives are also lost.

In summary,

  • soundness: there are no false negatives

  • completeness: there are no false positives

  • software verification: soundness is more important than completeness

  • bug finding: completeness is more important than soundness

Fula answered 12/3, 2015 at 6:9 Comment(2)
What do you mean: model checking is suitable for software verification, while symbolic execution is more appropriate for bug finding? Model checking has been used for finding bugs, see e.g. Formal modeling and analysis of an audio/video protocol: an industrial case study using UPPAAL.Nilgai
@Nilgai I edited the article because it's too long to comment here :-)Fula

© 2022 - 2024 — McMap. All rights reserved.