Static Analysis 01 Introduction

重点

• 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?

为什么我们需要静态分析

• 程序可靠性

  空指针引用、内存泄漏…

• 程序安全性

  信息泄漏、注入攻击…

• 编译优化

  死代码消除、代码移动(比如在循环里定义不会改变的值，可以把初始化放在循环外面)

• 理解程序

  idea自动提示、分析结构…

什么是静态分析

• Static analysis analyzes a program P to reason about its behaviors and determines whether it satisfies some properties before running P.

Rice’s Theorm

• non-trivial properties 简单理解为: 和运行时行为有关的特性
• Rice’s Theorm 告诉我们程序分析不存在 exact answer.
• 但是可以有两种选择: Compromise soundness or Compeomise completeness

Sound & Complete

• 妥协 soundness -> 漏报 False Negatives 
• 妥协 completeness -> 误报 False Positives 

注意这里「妥协」是指无法满足而倾向于另一种

为什么通常选择 Soundness

• 准则：宁可误报不能漏报，妥协 completeness，保证soundness.
• 确保 soundness 的基础上，在精度和速度上作出权衡。

Abstraction

Over-approximation

Transfer Function

• In static analysis, transfer functions define how to evaluate different program statements on abstract values.
• Transfer functions are defined according to “analysis problem” and the “semantics"of different program statements.

Control Flows