<aside> 💡 Key Points

• What are the differences between static analysis and (dynamic) testing?
• Understand soundness, completeness, false negatives, and false positives.
• Why soundness is usually required by static analysis?
• How to understand abstraction and over-approximation? </aside>

1. Rice’s Theorem

“Any non-trivial property of the behavior of programs in a r.e. language is undecidable.”

• r.e. (recursively enumerable) = recognizable by a Turing-machine
• A property is trivial if either it is not satisfied by any r.e. language, or if it is satisfied by all r.e. languages; otherwise it is non-trivial.
  • non-trivial properties $\approx$ interesting properties $\approx$ the properties related with run-time behaviors of programs

Perfect or Sound or Complete static analysis is impossible.

Useful static analysis is possible, includes:

• Compromise soundness (false negatives)
• Compromise completeness (false positives)

Mostly compromising completeness: Sound but not fully-precise static analysis

Necsssity of Soundness

Soundness is critical to a collection of important (static-analysis) applications such as compiler optimization and program verification.

Static Analysis: ensure (or get close to) soundness, while making good trade-offs between analysis precision and analysis speed.

2. Abstraction + Over-approximation

Two Words to Conclude Static Analysis

Abstraction

Determine the sign (+, -, or 0) of all the variables of a given program.

Over-approximation: Transfer Functions