静态程序分析

2025/3/4

字数统计: 2.6k字 | 阅读时长: 10分 | 总文章阅读量：次

前言

大作业所迫，8周时间试图产出一个静态分析工具，正好我也试试能不能写一个当毕设（

参考：

https://fushuling.com/index.php/2025/01/08/%e9%9d%99%e6%80%81%e5%88%86%e6%9e%90%e5%85%a5%e9%97%a8/

https://www.bilibili.com/video/BV1b7411K7P4/

基本概念

静态分析（Static Analysis）：在运行一个程序 P 之前，通过静态分析 P 来推测其行为，并且确定是否满足一些特定的性质

我们需要关心的是：

是否存在私有信息泄露（Private Information Leak）
是否有空指针的解引用（Null Pointer Dereference）操作
类型转换（Type Cast）操作是否安全
两个变量能否指向同一个内存地址
是否存在无法满足的断言（assert）语句
是否存在控制流无法到达的代码（Dead Code）

静态分析的评定标准

Sound：即全面的或者完备的，简单来说，满足 Sound 即允许错报不允许漏报
Truth：真实的，顾名思义，就是一个程序真正存在的漏洞，是最理想的分析结果
Complete：完整的，简单来说，满足 Complete 即允许漏报但不允许错报

那么很明显，同时满足 Sound 和 Complete 是几乎不可能的，Truth 是 Sound 的子集，Complete 又是 Truth 的子集，Sound 属于一种 Overapproximate，即过拟合，而 Complete 属于一种 Underapproximate，即弱拟合

在真实的程序分析中，显然我们要先做到 Sound，在此基础上向 Truth 上靠拢，宁可误报不能漏报

抽象

将具体域的值映射到抽象域中

例如按符号（+，-，0）给变量值做划分，大于0就划分为+，小于0就划分为-

而不确定的值划分为 unknown ，错误的值划分为 undefined

近似

定义计算抽象值的转换规则

控制流

所有 control flows 的汇聚点，都要执行合并（merge）：抽象做近似

中间表示（IR）

编译器与静态分析器

编译流程：

Scanner：扫描源代码，进行词法分析（Lexical Analysis），词法分析会用到正则表达式（Regular Expression），词法分析后的结果为一个标记（Token）串。

以自然语言为例：You dkasnd&^$Roewn godd，由于不能构成单词，所以不能通过 Scanner
Parser： 遍历标记串，进行语法分析（Syntax Analysis），这里的语法分析分析的是上下文无关的语法（Context Free Grammer），解析器的内部应该是实现了一个有限状态机，用于识别和分析每个语法块格式的正确性，语法分析的结果为一棵抽象语法树（Abstract Syntax Tree，AST）。

以自然语言为例：Like your hair I，词法正确但是语法不正确，不能通过 Parser
Type Checker：会遍历抽象语法树，进行语义分析（Semantic Analysis），不过编译器的语意分析是简单的，主要是分析属性语法（Attribute Grammer），比如说变量类型，并适当调整一下语法树。语义分析的结果我们称之为装饰过的抽象语法树（Decorated AST）。

以自然语言为例：Apples eat you，词法、语法正确，但是语义上不正确，不能通过 Type Checker
Translator： 会将抽象语法树翻译成中间表示（Intermediate Representation, IR），IR 的出现解耦了编译器的机器相关（Machine Dependent）部分和机器无关（Machine Independent）部分，上述几个层次在不同架构的机器上面是可以几乎不加改动地复用的。
Code Generator：会将 IR 转化成物理 CPU 能够直接执行的比特序列，也就是机器代码

可以把 IR 之前的部分类比为前端， IR 后面的部分类比为后端

AST & IR

对于这个代码：

do i = i + 1; while (a[i] < v);

AST 和 IR 的结果分别是：

AST：之前接触过 https://c1oudfl0w0.github.io/blog/2024/02/10/AST%E6%B3%A8%E5%85%A5/#%E8%AF%8D%E6%B3%95%E5%88%86%E6%9E%90

解析出来的语法树用json表示为：

{
  "type": "Program",
  "start": 0,
  "end": 31,
  "body": [
    {
      "type": "DoWhileStatement",	// do-while结构
      "start": 0,
      "end": 31,
      "body": {	// body
        "type": "ExpressionStatement",
        "start": 3,
        "end": 13,
        "expression": {
          "type": "AssignmentExpression",
          "start": 3,
          "end": 12,
          "operator": "=",
          "left": {
            "type": "Identifier",
            "start": 3,
            "end": 4,
            "name": "i"
          },
          "right": {
            "type": "BinaryExpression",
            "start": 7,
            "end": 12,
            "left": {
              "type": "Identifier",
              "start": 7,
              "end": 8,
              "name": "i"
            },
            "operator": "+",	// 右子树根节点
            "right": {
              "type": "Literal",
              "start": 11,
              "end": 12,
              "value": 1,
              "raw": "1"
            }
          }
        }
      },
      "test": {
        "type": "BinaryExpression",
        "start": 21,
        "end": 29,
        "left": {
          "type": "MemberExpression",
          "start": 21,
          "end": 25,
          "object": {
            "type": "Identifier",
            "start": 21,
            "end": 22,
            "name": "a"
          },
          "property": {
            "type": "Identifier",
            "start": 23,
            "end": 24,
            "name": "i"
          },
          "computed": true,
          "optional": false
        },
        "operator": "<",	// 右子树根节点
        "right": {
          "type": "Identifier",
          "start": 28,
          "end": 29,
          "name": "v"
        }
      }
    }
  ],
  "sourceType": "module"
}

IR：三地址码

i = i + 1
临时变量 t1 = a[i]
if t1 < v goto 1，即回到第一步重复执行

可以看出来，抽象语法树（AST）是源代码结构的一种抽象表示，以树状的形式表现编程语言的语法结构，相对而言层次较高，和语法结构更接近，并且依赖于具体的语言类，缺少和程序控制流相关的信息

而 IR 与机器代码接近，通常与具体的语言无关，简单通用，包含程序的控制流信息，也是我们做静态分析的基础

三地址码（3 Address Code，3AC）

通常使用 3AC 形式的 IR

所谓的三地址码是指：每个三地址码指令，都可以被分解为四个元组（运算符，运算对象1，运算对象2，结果）

因为每个陈述都包含了三个变量，所以它被称为三地址码。

例子：

a+b+3

转化成三地址码：这里是结果运算符对象1 运算符对象2

t1 = a + b
t2 = t1 + 3

其中a, b是原始变量，3是常数，t1和t2是编译过程中生成的临时变量

系统中常见的三地址码指令：

x = y bop z //bop：二元运算，二进制算术或逻辑运算
x = uop y //uop：一元运算（减号、否定、强制转换）
x = y
goto L //L： 表示程序位置的标签  goto L就是一种无条件跳转
if x goto L // if ... 满足条件后再xxx属于一种条件跳转
if x rop y goto L //rop：关系运算符（>、<、==、>=、<=等）

真实案例：https://github.com/soot-oss/soot

观察一下这个 java 方法调用的 3AC，部分涉及到 JVM 的设计

基本块 Basic Blocks（BB）

具体定义是：一个基本块中只能有一个入口和一个出口

入口就是其中的第—个语句，出口就是其中的最后一个语句。对一个基本块来说，执行时只从其入口进入，从其出口退出

在具体程序中，我们划分 BasicBlock 的方式就是找到不同的 leader，即不同 BasicBlock 的入口点，通过不同的入口点划分不同的 BasicBlock

划分 leader 的原则：

程序的第一条语句：即整个程序最初的入口
转移语句的目标语句：比如一个 goto 语句跳转到了第三句代码，那么这个第三句代码必然是 leader
紧跟在条件转移语句后面的语句：比如第三句代码是一个 goto 语句，那么第四句代码必然是 leader

3AC 的例子：

(1)x = input
(2)y = x
(3)z = x * y
(4)if z < x goto (7)
(5)p = x / y
(6)q = p + y
(7)a = q
(8)b = x + a
(9)c = 2a - b
(10)if p == q goto (12)
(11)goto(3)
(12)return

按照第一条原则，程序的第一条语句必须是 leader，我们可以得到 leader：(1)

按照第二条原则，转移语句的目标语句必须是 leader，我们可以得到 leader：(3) (7) (12)

按照第三条原则，紧跟在条件转移语句后面的语句必然是 leader，我们可以得到 leader：(5) (11) (12)

对三个集合进行合并，整个程序的 leader 便是：(1) (3) (5) (7) (11) (12)

通过不同的 leader 划分不同的 BasicBlock，我们可以划分出该程序的 BasicBlock 分别为：

{(1) (2)}
{(3) (4)}
{(5) (6)}
{(7) (8) (9) (10)}
{(11)}
{(12)}

控制流图 Control Flow Graphs（CFG）

有了 BasicBlock 作为工具，我们就可以很清晰的画出程序的 Control Flow Graph，即控制流图

类似于 IDA 的 Flow chart

CFG 控制流程图，是一个过程或程序的抽象表现，是用在编译器中的一个抽象数据结构，由编译器在内部维护，代表了一个程序执行过程中会遍历到的所有路径

它用图的形式表示一个过程内所有基本块执行的可能流向, 也能反映一个过程的实时执行过程

CFG 能反映出一个过程的许多信息，包括但不限于：

是哪一个过程;
一个过程的入口（第一个基本块）和出口（最后一个基本块）；
一个基本块的所有可能的下一个基本块（所有的出口）；
一个基本块的所有可能的上一个基本块（所有的入口）；
一个基本块所对应的语句表

CFG 的节点是 BasicBlock，只有两种情况下从块A到块B存在边：

从A的末尾到B的开头有一个有条件或无条件的跳转
B立即按照原始指令顺序跟随A且A不会以无条件跳转结束

因此这种A以无条件跳转结尾的情况下，A与B之间不存在边

若A不以跳转结尾，那么二者间存在边

在日常的分析中，我们会经常把跳转到指令标签替换为跳转到基本块，这样就简化了我们分析的难度

对于前面给出来的 3AC 代码块而言，CFG 如下

安全问题

信息流安全

访问控制 vs 信息流安全

访问控制（Access Control）：是一种保护敏感数据的标准方法，主要用于检查程序是否有权访问某些信息，关注如何访问信息

信息流安全（Information Flow Security）：是一种端到端的方法，跟踪信息如何流经程序，以确保程序安全地处理信息，关注信息如何传播

信息流

如果变量 x 中的信息被转移到变量 y 中

目录

LOADING