静态分析导论 - Introduction

在软件工程中，静态分析是一种重要的程序分析方法，通过在不运行程序的情况下对其源代码或中间表示进行检查和推理，以获取有关程序行为和性质的信息。本文将介绍静态分析的基本概念以及与之相关的一些重要主题。

概述

程序的生命周期中的许多关键步骤都涉及到对程序的分析，以便更好地理解、维护和优化代码。静态分析是其中之一，它通过在编译或开发阶段对程序进行检查，提供了一种在运行时难以获得的洞察力。

静态分析通常包括以下步骤：

1. 词法分析（Lexical Analysis）：将源代码转换为令牌流。
2. 语法分析（Syntax Analysis）：将令牌流转换为抽象语法树（AST）。
3. 语义分析（Semantic Analysis）：对AST进行类型检查和语义检查，生成带有语义信息的修饰AST。
4. 翻译（Translation）：将修饰AST翻译为中间表示（IR）。
5. 静态分析（Static Analysis）：对IR进行分析，进行诸如代码优化等操作。

[source] -> scanner(lexcial analysis) -> [tokens] -> parser(syntax analysis) -> [ast] -> type checker(semantic analysis) ->[decorated ast] -> translator -> [IR] -> static analysis, e.g code optimization -> code generator -> [machine code]

重要概念

AST vs IR

• AST（抽象语法树）：表示源代码的语法结构，是语法分析的输出。
• IR（中间表示）：在编译器中用于在高级源代码和目标机器代码之间进行转换的数据结构。

3AC（3-Address Code）

3AC是一种中间表示，每条语句最多包含一个操作符。它包括多种类型的语句，如赋值、条件跳转等。
右边最多一个operator( t1=a+b, t2=t1+3.)

• 典型语句类型：
  • x = y bop z;
  • x = uop y;
  • x = y;
  • goto L;
  • if x goto L;
  • if x rop y goto L
• a typed 3AC: soot - jimple
  • for
  • do while
  • method call

SSA（静态单赋值）

SSA是一种中间表示的形式，其中每个变量只被赋值（定义）一次。这有助于某些优化和分析，如条件常量传播和全局值编号。

为什么使用SSA？

• 部分精度的流不直接合并到单一变量名中，有助于流不敏感分析获得部分精度。
• 显式的定义和使用关系（define-and-use对），使得一些优化更高效（如conditional constant propagation, global value numbering）。

为什么不使用SSA？

• 引入了大量变量和phi函数。
• 在生成机器码时可能引入性能问题，因为需要进行复制操作。

控制流图（CFG）与基本块

控制流图是程序中基本块之间控制流的图形表示。节点通常是单独的3AC，或者是基本块（Basic Block）

基本块是一种最基本的控制流单元，它是一个连续的3AC序列，只有一个入口和一个出口。

从A到B有一条边，当且仅当：

• 有一个条件或无条件跳转从A的结束到B的开始（符合的出边）
• B在指令原始序列中紧跟着A，且A的最后不是无条件跳转（不符合的出边）

Basic Block

最长的三地址指令序列满足：只有开始能进入，中间不存在入口；只有结尾能退出，中间不存在出口

两类分析

may analysis:
outputs information that may be true(over-approximation)

must analysisL
outputs information that must be true(under-approximation)

over-approximation & under-approximation are both for safety of analysis

初步了解了静态分析的基本流程、重要概念以及涉及的一些关键主题。在软件工程中，静态分析是提高代码质量、发现潜在问题和进行优化的强大工具。