程序分析基础 Fundamentals of Program Analysis¶

作者: 杨广亮
更新日期: 2026-01-04
版权声明: 本文档遵循 CC BY-NC-SA 4.0 协议

程序分析是理解程序的语法和行为的重要方法，是自动化代码安全漏洞的重要基础。它包含了几个重要步骤

    源代码                Source code
->  抽象语法树AST          Abstract Syntax Tree
->  作用域层级关系         Scope Hierarchy
->  类型分析和检查         Type Analysis
->  中间语言IR            Intermediate Representation
->  控制流CFG             Control Flow Graph
->  静态单一赋值SSA        Static Single Assignment
->  数据流DFG             Data Flow Graph
->  指针分析              Pointer Analysis
->  污点分析              Taint Analysis

这些步骤并不是线性流水线，而是一组语义建模工具，不同程序分析框架会选择、调整、组合这些步骤。

本章将详细介绍数据流之前的步骤，其他几个步骤将在后续章节中详细介绍。

1. 词法单元 Token¶

在分析的第一阶段，输入是字符串形式的源代码，经过词法分析器（Lexical Analyzer）的扫描（Scan）后，输出为词法单元或记号（Token）的序列。也就是说字符串流被分割成一个个token。Token主要包括两部分，一部分是分割出的内容，也叫词位（Lexeme），一部分是该内容的类别，因此一个Token可以表示为：(Lexeme, Type)。

以下列C源代码为例：

[01] int x = 1;
[02]
[03] int f(int y) {
[04]     int z;
[05]     if (y > 0) {
[06]         z = x + y;
[07]     } else {
[08]         z = x - y;
[09]     }
[10]     return z;
[11] }

当上述代码开始被lexer进行扫描时，它不会关心语义信息，例如if是控制流关键词，z会被多次赋值。相反，它只关心语法信息，如if是关键词，z/x/y全部只是标识符（identifier，缩写为IDENT）。当空白和换行符被忽略后，最终得到以下Token序列：

[01] int     , KEYWORD_INT
[02] x       , IDENTIFIER
[03] =       , ASSIGN
[04] 1       , INT_LITERAL
[05] ;       , SEMICOLON

[06] int     , KEYWORD_INT
[07] f       , IDENTIFIER
[08] (       , LPAREN
[09] int     , KEYWORD_INT
[10] y       , IDENTIFIER
[11] )       , RPAREN
[12] {       , LBRACE

[13] int     , KEYWORD_INT
[14] z       , IDENTIFIER
[15] ;       , SEMICOLON

[16] if      , KEYWORD_IF
[17] (       , LPAREN
[18] y       , IDENTIFIER
[19] >       , GREATER_THAN
[20] 0       , INT_LITERAL
[21] )       , RPAREN
[22] {       , LBRACE

[23] z       , IDENTIFIER
[24] =       , ASSIGN
[25] x       , IDENTIFIER
[26] +       , PLUS
[27] y       , IDENTIFIER
[28] ;       , SEMICOLON
[29] }       , RBRACE

[30] else    , KEYWORD_ELSE
[31] {       , LBRACE
[32] z       , IDENTIFIER
[33] =       , ASSIGN
[34] x       , IDENTIFIER
[35] -       , MINUS
[36] y       , IDENTIFIER
[37] ;       , SEMICOLON
[38] }       , RBRACE

[39] return  , KEYWORD_RETURN
[40] z       , IDENTIFIER
[41] ;       , SEMICOLON

[42] }       , RBRACE

2. 抽象语法树 AST (Abstract Syntax Tree)¶

抽象语法树（AST）是程序源代码的抽象表示，是程序语义分析的基础。它是一种树形结构，它是由一系列的节点组成的，这些节点表示源代码中的各种元素，如变量、函数、运算符、表达式等等。

以Token序列为输入，解析器Parser会应用语法规则来生成语法解析树（Parse Tree）。语法规则由人为描述的，通常使用BNF（Backus-Naur Form，巴科斯-诺尔范式）来表示。以下语法规则例子表示了对if分支结构语法的描述，其中以双引号包裹的内容表示的固有的关键字或者语法元素。该规则描述了一个if-else结构，其中Cond表示条件表达式，Then表示then块，Else表示else块，Block表示块，Stmt表示语句。

IfStmt ::= "if" "(" Cond ")" Then "else" Else
Cond ::= BoolExpr
Then ::= Block
Else ::= Block
Block ::= "{" Stmt* "}"

通过按照该规则对Token流进行自上而下的解析，将Token流转换为语法解析树。不过，语法解析树非常繁琐，再通过去繁就简后，最终得到抽象语法树（AST）。上述C源代码的抽象语法树如下：

Global
├── VarDecl
│   ├── Type: int
│   ├── Name: x
│   └── Init
│       └── IntegerLiteral(1)
│
└── FunctionDecl
    ├── ReturnType: int
    ├── Name: f
    ├── Params
    │   └── ParamDecl
    │       ├── Type: int
    │       └── Name: y
    └── Body: CompoundStmt
        ├── VarDecl
        │   ├── Type: int
        │   └── Name: z
        │
        ├── IfStmt
        │   ├── Cond
        │   │   └── BinaryExpr (>)
        │   │       ├── Identifier(y)
        │   │       └── IntegerLiteral(0)
        │   │
        │   ├── Then
        │   │   └── CompoundStmt
        │   │       └── ExprStmt
        │   │           └── AssignExpr (=)
        │   │               ├── Identifier(z)
        │   │               └── BinaryExpr (+)
        │   │                   ├── Identifier(x)
        │   │                   └── Identifier(y)
        │   │
        │   └── Else
        │       └── CompoundStmt
        │           └── ExprStmt
        │               └── AssignExpr (=)
        │                   ├── Identifier(z)
        │                   └── BinaryExpr (-)
        │                       ├── Identifier(x)
        │                       └── Identifier(y)
        │
        └── ReturnStmt
            └── Identifier(z)

3. 作用域 Scope¶

作用域（Scope）是程序语义分析的基本单位，作用域描述了变量和函数的访问范围。作用域可以理解为变量和函数的命名空间，作用域内定义的变量和函数可以在作用域内被访问，而作用域外定义的变量和函数则不能被访问。实际应用中，作用域由作用域嵌套构成，作用域嵌套关系由作用域的声明顺序决定。

对于一个作用域的刻画，它不仅需要描述其内嵌作用域和外层作用域，还需要完整记录本作用域内定义的（或者所拥有的）变量和函数，以方便查找。

还是以之前的C源代码为例，它的作用域层级关系（Scope Hierarchy）如下：

GlobalScope
├── x : int
├── f : function(int) -> int
│
└── FunctionScope(f)
    ├── y : int
    │
    └── BlockScope (function body)
        ├── z : int
        ├── BlockScope (then)
        └── BlockScope (else)

以源代码中第8行z = x - y为例，可以通过查找Scope Hierarchy找到x和y的定义。它属于BlockScope (else)，它查询该作用域是否有x和y的变量定义，发现没有，则继续查询其外层作用域，即BlockScope (function body)。还是发现没有，则继续查询其外层作用域，即FunctionScope(f)，这时候它找到了y，那么[08]行处使用的y的定义的地方就找到了。再继续向上找x，查验GlobalScope，最终发现x变量定义。

为了方便查找往往还会将所有的符号进行统一编号，编码的方式有多种，可以从0开始顺序递增，也可以以行号为编码，只需要确保编号唯一即可。假设我们以行号为编码，那么作用域层级关系如下：

GlobalScope： ID-00
├── x : ID-01, int
├── f : ID-02, function(int) -> int
│
└── FunctionScope(f): ID-02
    ├── y : ID-03, int
    │
    └── BlockScope (function body): ID-04
        ├── z : ID-05, int
        ├── BlockScope (then): ID-06
        └── BlockScope (else): ID-07

编码是一种常用且关键的标识和区分变量的方式，编码在程序分析中发挥极其重要的作用。例如，[08]行z = x - y可以通过作用域编号找到z、x、y的变量的编码ID，分别为ID-05、ID-01、ID-03。而同理而言，[06]行的z = x + y的变量编码ID也分别为ID-05、ID-01、ID-03。因此，可以得到结论[06]和[08]都使用了两个变量ID-01（x）和ID-03（y），同时也都修改了变量ID-05（z）。

4. 类型检查¶

在Scope Hierarchy基础上对所有的变量进行编号，就可以对类型进行静态检查，甚至推断。这里面的关键在于需要根据语言语法和语义的设计对每一种指令进行建模，即指定每一条指令所对应的类型转换和检查规则。

以[08]行z = x - y代码为例，x和y的编码ID分别为ID-01和ID-03，他们编码对应的类型信息（分别被GlobalScope：ID-00和FunctionScope:ID-02记录）都是int。而z的编码ID为ID-05，它被BlockScope:ID-04所记录，它的类型信息也为int。那么[08]行z = x - y的静态检查规则就变为了int = int - int，这对于C语言来说是正确的。

类型信息对于程序分析的正确性发挥有重要的作用。例如，有一个函数调用指令f(1)。如果能够定位到f的编码是ID-02，那么就可以快速理解该函数调用行为，该指令准备要调用定义在FunctionScope:ID-02位置的函数f，并传入参数1。

5. 控制流图 CFG（Control Flow Graph）¶

控制流图CFG（Control Flow Graph）是一个图状结构，用于描述一个函数在运行时的执行路径，以及函数内部各个路径所对应的控制结构。CFG的边表示程序在执行过程中可能发生的控制转移关系，节点是一条指令或者一个基本块BB（Basic Block）。BB是多个指令组成的组合，除最后一条指令外，BB内部不包含控制转移指令。

回顾示例C源代码函数f的源代码：

[03] int f(int y) {
[04]     int z;
[05]     if (y > 0) {
[06]         z = x + y;
[07]     } else {
[08]         z = x - y;
[09]     }
[10]     return z;
[11] }

f函数的CFG图如下所示，每个节点为单一指令，用行号来表示，而每条边将不同指令连接起来，表示调用关系。

6. 中间表示 IR（Intermediate Representation）¶

示例中的代码非常简单，易于理解，也有利于程序分析。但是，实际程序中的指令则非常复杂，例如w=f(1)+f(2)，这条指令即包含了函数调用、加法运算、赋值运算。对该语句进行静态分析，非常难以刻画它的控制流，也难以进行更加复杂的分析。

因此，为了描述更复杂的程序，需要将程序进行抽象，将复杂指令进行拆分，将多个指令组合成更简单的指令，这种简单的、抽象的指令被称为中间表示IR（Intermediate Representation），或者中间语言（Intermediate Language）。在IR基础上进行程序分析，就变得非常容易了。

比较经典的IR格式是三地址表示法（three-address code），即一条指令只涉及三个变量，如x = y + z。以w=f(1)+f(2)代码为例，其IR生成结果为：

%v0 = f(1)
%v1 = f(2)
w = %v0 + %v1

IR的生成过程，是以AST为输入，从AST的根节点开始，从上而下，递归地访问AST的节点，生成IR。

7. 静态单一赋值 SSA（Static Single Assignment）¶

静态单赋值（SSA）将变量分配为单赋值变量，即每个变量只允许被赋值一次。这样的好处是，当对程序进行分析时，能够通过名称作为唯一标识变量进行查找，快速定位变量最新的赋值位置。

例如，在示例C源代码中，对于[10] return z指令来说，它引用z，那如何快速得知z的最新赋值位置（或者说在第10行之前最近修改z的指令）是个问题。SSA能够帮助快速解决这个问题，生成的函数f函数的SSA格式如下：

x0 = 1
y0 = param y

if (y0 > 0) {
    z1 = x0 + y0
} else {
    z2 = x0 - y0
}

z3 = phi(z1, z2)
return z3

其中，phi是汇总点和合并点，将多个变量（z1和z2）汇总为一个变量（z3）。

SSA生成的算法非常成熟，可以参考两篇工作：

Efficiently Computing Static Single Assignment Form and the Control Dependence Graph, 1991 这篇工作是SSA形式的奠基性研究，引入了支配关系（Dominator）与支配边界DF（Dominance Frontier），并给出了系统化的phi函数插入与变量重命名算法，是当前教材与传统编译器中最常用的 SSA 构造方法。
Simple and Efficient Construction of Static Single Assignment Form, 2013 该工作提出了一种不依赖显式DF计算的SSA构造算法，phi函数按需插入，非常适合从AST直接生成SSA形式的IR。

在某些框架中，SSA扮演了非常重要和核心的角色，由于可以直接从AST生成SSA，因此IR这一步骤就可以跳过了。同时从后续数据流的角度来说，SSA和数据流是等价的，有了SSA，数据流图（Data Flow Graph）就非常容易生成。同理地，反过来也是一样的，如果做了IR和数据流，那么SSA也不是必要的了。这更多地是一个实现策略问题，而不是一个技术问题。

8. 其他¶

8.1 类层级关系 Class Hierarchy¶

针对面向对象语言，类的继承是非常重要的编程方式和行为逻辑。类层级关系（Class Hierarchy）可以高效地描述对象间的继承关系，可以帮助定位对象间的属性访问关系。

以下列Java代码为例：

class Animal {
    void speak() {
        System.out.println("animal");
    }
}

class Dog extends Animal {
    @Override
    void speak() {
        System.out.println("dog");
    }
}

class Cat extends Animal {
    @Override
    void speak() {
        System.out.println("cat");
    }
}

class Other extends Animal {}

类层级关系可以描述为：

Animal
 ├── Dog
 ├── Cat
 └── Other

类层级关系可以帮助解决函数调用解析问题。例如

[01] Animal a = new Other();
[02] a.speak();

对于第二行代码a.speak()，由于a是Other类的对象，因此调用的是Other类的speak()方法，但是Other类没有speak()方法，因此会调用Other的父类Animal的speak()方法，即打印"animal"。

由此也引申出了一个指针问题，即变量指向的对象，变量和对象之间存在指向关系。例如

void makeSound(Animal a) {
    a.speak();
}

在该代码中，变量a可以是Dog、Cat、Other或者Animal对象。在运行时，当执行a.speak()时，需要针对a的具体类型来动态判断具体调用哪个speak函数。在程序分析中，主要有两种方法：

一种方法是，直接通过类型信息，结合类层级关系，将调用目标解析为一个可能函数集合（即Animal.speak、Dog.speak和Cat.speak）；
另一种方法是，分析函数makeSound调用者，定位到参数a对应的具体类型是什么，从而确定调用目标。

前一种为类层级关系分析，后一种为指针分析。我们将在后续的章节中介绍指针分析。

8.2 函数调用图 CG（Call Graph）¶

函数调用图CG（Call Graph）描述了程序中的函数之间调用关系。CG对于多种分析场景中都起到很重要的作用。首先，通过CG，能够快速扫描敏感函数；其次，通过在CG上定位任意两个函数，追查这两个函数之间的调用链（call chain），来确定是否存在调用路径。这些是对代码进行安全分析重要的方法。

CG的生成过程，主要在于对函数调用指令的解析，可以按照函数调用的格式分别进行解析：

如果是method()格式，而method是一个函数名，那么可以直接在CG添加一条边，即（当前函数，method函数）。
如果是receiver.method()格式，常见的方法是引用类层级关系或者通过类型，定位receiver.method的函数原型，那么也可以在CG中添加一条边，即（当前函数，receiver.method函数原型）。特别的是，super.method()、this.method()、self.method()等，需要应用类层级来定位。
此外，还有些隐式的函数调用，例如初始化函数、运算符加载函数等，需要特殊处理。

当然，现实情况会更加复杂，尤其是在高阶函数（Higher-order function）存在的情况下，那么就往往需要应用更加高级的分析方法（例如指针分析）来构建更加完整的CG。

高阶函数

高阶函数是指至少满足下列一个条件的函数：

接受一个或多个函数作为输入（参数）；
返回一个函数作为输出（返回值）；
把函数当做变量使用，例如赋值等。

除了高阶函数外，还有几个常见的函数类型：

lambda函数：它是一个匿名函数，函数体是一个表达式，也是这个函数的返回值，格式为<lambda 参数: 表达式>，例如下面代码中，x 的右值是一个lambda函数。
```
x = lambda a : a + 10
print(x(5))
```
闭包（closure）：它是一个嵌套nested函数，该函数引用了外部函数的变量，该函数可被外部函数返回，例如下面代码中inner函数。
```
def outer():
    def inner():
        return 1
    return inner
```

8.3 跨函数控制流图 ICFG（Interprocedural Control Flow Graph）¶

控制流图CFG仅仅是描述函数内的指令之间的控制执行关系，并没有反应跨函数级别的控制关系。为了弥补这一缺陷，跨函数控制流图ICFG（Interprocedural Control Flow Graph）结合调用图CG和每个函数的CFG，形成一个全局、完整的控制流图。

在传统框架中，跨函数控制流图ICFG是很多复杂分析的基础，例如数据流、指针分析等，发挥了非常大的作用。