Static Analysis 01-Introduction

Static Analysis 01-Introduction

HC_Plantern 201 2022-09-22

本文参考:

重点

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

为什么我们需要静态分析

image-20220310205025687

  • 程序可靠性

    空指针引用、内存泄漏…

  • 程序安全性

    信息泄漏、注入攻击…

  • 编译优化

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

  • 理解程序

    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

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

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