What is the subset of problems that static analysis cannot capture?

Question

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?

Answer 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.