6

I am trying to understand the difference between static analysis and dynamic analysis for the purpose of program flow execution, for detection of security vulnerabilities.

It is fairly clear that dynamic analysis's primary weakness is that it cannot explore all possible states that a program can get into, because it relies on actually running the program with a particular set of inputs.

However, static analysis seems to reason about all possible program states, so I cannot envision a scenario where static analysis might fail, even though I am sure that such a scenario does exist. Most of the references I have looked at seem to vaguely say that the "abstract state analysis" is not as precise as what dynamic analysis can provide, but that is too fluffy for me.

Can anyone provide a simple explanation with concrete examples of where static analysis fails and dynamic analysis would be needed?

merlin2011
  • 71,677
  • 44
  • 195
  • 329
  • What is your definition of "fails?" As in "sometimes gives the wrong answer," or "cannot possibly get the right answer?" – templatetypedef Jun 08 '14 at 00:24
  • For static analysis to catch everything, it would need to solve the halting problem. – user2357112 Jun 08 '14 at 00:25
  • @templatetypedef, "Cannot get the right answer with higher probability than by randomly guessing" – merlin2011 Jun 08 '14 at 00:25
  • @user2357112, I can always write a program that will flag every line of code as vulnerable, and it would then "catch everything". It would also catch innocent things. – merlin2011 Jun 08 '14 at 00:26
  • 1
    Okay, let me provide a more formal specification of "catch everything". Suppose you want to take in code and compute whether the relationship between the code's input and output has a certain undesirable (insecure) property. [Rice's theorem](http://en.wikipedia.org/wiki/Rice's_theorem) says there is no algorithm that will do that. – user2357112 Jun 08 '14 at 00:30

1 Answers1

1

Static analysis cannot ever be complete for all programs given a Turing complete input format (this includes almost all programming languages) as one cannot in general determine whether a piece of code is ever executed or not: you cannot determine whether the code prior to it halts — i.e., finishes executing (if it goes into an infinite loop, then any "problem" beyond it is bogus as it is unreachable) — a problem known as the halting problem.

However, it is, in principle, possible to find all possible problems if you also permit the analysis to output "problems" that don't actually exist. This is what virtually all static analysis tools do — large amounts of engineering effort is spent on minimizing the number of false problems they report.

Furthermore, it is worthwhile to note that some state exploration systems essentially do execute the program for every state (typically stopping a new exploration if the state has become equivalent) — however, many programs have impractically large input state spaces (consider any program taking textual input!) making them practically impossible to fully explore all states.

gsnedders
  • 5,532
  • 2
  • 30
  • 41
  • If you can augment this answer with a concrete example (in any language, or even pseudocode), it would address my question much more thoroughly and directly. – merlin2011 Jun 08 '14 at 00:29
  • I have read quite a bit of descriptions similar to this, but nothing *concrete*. – merlin2011 Jun 08 '14 at 00:30
  • @merlin2011 http://stackoverflow.com/a/1111200/478176 includes the closest thing you'll get to a practical example of the halting problem; is it clear to you that if the halting problem is unsolvable that you cannot reason about any further bit of the program? – gsnedders Jun 08 '14 at 00:40
  • Yes, it is clear. Are you implying that the inability to determine whether a piece of code is ever executed or not is the only limitation of static analysis? – merlin2011 Jun 08 '14 at 00:48
  • @merlin2011 It and other challenges that are essentially equivalent are the main challenges; they aren't the *only* limitation. – gsnedders Jun 08 '14 at 02:36