💻软件分析—期末笔记

status
Published
type
Post
date
May 13, 2026
slug
sa-final
summary
本文为课程的期末复习笔记，包括程序的表示、三种数据流分析，以及指针分析。
tags
软件分析
category
期末复习
icon
password
🗒️
这是南京大学 软件分析 的期末复习笔记，总结了笔者认为期末可能会涉及的内容。详细版笔记强烈建议参考 助教笔记，内容十分全面。

第一部分：程序的表示

概述

Soundness 和 Completeness
  • 完全性（Soundness）：只要是真的，都可以由 S 给出
  • 正确性（Completeness）：S 给出的都是真的
      • notion image
sound 的静态分析居多，即宁误报不漏报。
  • Sound 静态分析：over approximate (false positive)
  • Complete 静态分析：under approximate (false negative)
静态分析就是：抽象和过近似
  • 对程序的具体值和抽象值建立映射，此函数为状态函数（State function）
  • 针对抽象值进行运算（解析）（Evaluate）的函数为转移函数（Transfer function）

程序的中间表示

三地址码（Three-address code, TAC）：一种 IR，每条指令最多有三个地址
控制流图（Control Flow Graph, CFG）：由 Basic Block 组成，BB 指的是只能从首指令进入，从尾指令流出的最长指令序列
  • 入口语句包括：
    • 程序第一条语句
    • 跳转的目标语句
    • 条件跳转的下一条语句
  • BB：

第二部分：数据流分析及其应用

Reaching-Definitions

过近似、正向分析
  • 过近似：到达定值用于优化无用赋值，必须有 100% 的把握保证一个定义不会被用到，才能优化
数据抽象：程序中所有的定义 ，使用位向量表示
Meet Operator:
Node Transfer:
  • : B 中的赋值
  • : 不在 B 中、左值出现在 B 赋值中的赋值
初始化：
  • OUT[Entry]：
  • OUT[其余]：
结束条件：OUT 不变

Live-Variables-Analysis

过近似、逆向分析
  • 过近似：活跃变量分析用于寄存器分配
数据抽象：程序中所有的变量 ，使用位向量表示
Meet Operator:
Node Transfer:
初始化：
  • IN[Exit]:
  • IN[其余]:
一个比较 tricky 的地方：基本块（有多条语句）的 def 和 use 是什么？
  • def[B]: 在 B 中被赋值的变量
  • use[B]: 在 B 中第一次被赋值前就被使用
结束条件：IN 不变

Available-Expressions-Analysis

欠近似、正向分析
  • 欠近似：防止优化不能被优化的表达式
x op y 可用：
  • 从程序入口到程序点 p 的所有路径必须经过求值 x op y
  • 在最后一次求值之后，没有 x 或 y 的重定义
易错例子：
notion image
c=e^16 * x 这句中，表达式 e^16 * x 是可用的
数据抽象：程序中所有的表达式
Meet Operator:
Node Transfer:
初始化：
  • OUT[Entry]:
  • OUT[其他]:

总结

ㅤ
定义可达性分析
活跃变量分析
可用表达式分析
定义域
定义集的幂集
变量集的幂集
表达式集的幂集
方向
正向分析
逆向分析
正向分析
估计
过近似
过近似
欠近似
边界
初始化
状态转移
交汇

数据流分析的基础

数据流分析→数学表示
  • 抽象：CFG 中的每个节点数据流值组成一个 元组
  • 迭代：每次迭代相当于一个函数 作用在 元组上产生一个新的 元组
  • 终止：连续两次迭代结果完全相同
定义：
  • 偏序集：集合 + 二元关系（自反、传递、反对称）
  • bound
    • 最小上界（LUB）：
    • 最大下界（GLB）：
    • Join：, Meet：
  • 定理：一个偏序集如果存在 LUB 和 GLB，则是唯一的
  • 格：任意两元素的 join 和 meet 都存在
  • 全格：所有子集都有最小上界和最大下界
  • 定理：有限格都是全格
数据流分析的迭代算法的时间复杂度为 ，其中 为 CFG 的结点个数， 为定义域格的高度

过程间分析

Java 中的方法调用：
  • 静态调用：静态方法
  • 特殊调用：构造函数，私有实例方法，基类实例方法
  • 虚调用：其他的实例方法（运行时才可以确定）
方法的 Dispatch：
  • Dispatch(c,m)：c 是接受对象的类型，m 是方法签名
  • 过程：从接受对象所在的类开始，按照从子类向到基类的顺序查找，直到找到一个方法名和描述符都相同的非抽象方法为止
类层级结构分析（Class Hierarchy Analysis，CHA）
调用点的 Resolve：
  • Resolve(cs)：返回调用点 cs 可能调用的所有方法
  • 过程：设 c 为调用点接受对象的声明类型，m 为调用点处的函数签名。对 c 的所有子类（直接、间接子类）c’，将 Dispatch(c’,m) 加入返回值集合
易错点：是将 c 所有子类 Dispatch 的方法加入，如：
cha-eg
对于 B b = ...，
有 A.foo() 的原因是 Dispatch(B, foo()) 返回 A.foo()
CHA 的特点：
  • 优点：快
    • 只考虑了调用点处接收对象的声明类型及其继承结构
    • 忽略数据流和控制流信息
  • 缺点：不精确
    • 很容易引入虚假的目标方法
通过 CHA 构建调用图（Call Graph Construction）的方法：
  1. 从入口方法开始（通常为main方法）
  1. 对于每个可达的方法 m，通过 CHA 解析 m 中的每个调用点 cs 的目标方法，即 Resolve(cs)
  1. 重复上述过程，直到没有发现新的方法为止
ICFG：过程间控制流图
icfg-eg
  • call edge: 传参
  • return edge: 传返回值
  • call-to-return edge: 传 local 数据流
过程间数据流分析 = 节点转移 + 边转移
Edge Transfer（以过程间常量传播为例）：
  • Normal Edge: 恒等函数
  • Call-Return Edge: kill 左值变量，其余不变
  • Call Edge: 传参
  • Return Edge: 传返回值

第三部分：指针分析及其应用

指针分析： May analysis，分析程序中的一个指针可能会指向哪些内存区域
别名分析：
  • 两个指针互为别名：两个指针指向同一块内存区域（对象）
  • 指针分析回答的是一个指针可能会指向哪些对象，别名分析回答的是两个指针是否会指向同一个对象
堆抽象：
  • Allocation Site Abstraction: 将一个分配点（new 语句）分配的所有对象，抽象成为一个对象
call 时不添加 作为 PFG 的边: 因为 可以更精确地被处理（仅在 时才将 加入到 中）

上下文敏感（C.S.）

上下文敏感的堆
  • 为什么需要 CS Heap：如果没有 CS Heap，不同上下文调用方法时，被调用方法的内部产生的对象仍然被混在一起，精度提升不明显
  • 在上下文不敏感分析中，CS Heap 不会对精度有提升作用！！
在方法调用时，会使用 为目标方法选择一个上下文，不同的上下文策略仅是 不同（解耦），其余框架相同

上下文敏感的几种变体

  1. 调用点敏感（Call-Site Sensitivity）
      • Intuition：既然上下文是调用产生的，那么就将调用点作为上下文（记得从哪里来）
      • 实际中为 -Limiting Context Abstraction，方法上下文和堆上下文可能会使用不同的
  1. 对象敏感（Object Sensitivity）
      • Intuition：既然数据是由对象携带的，那就将每次调用的接受对象（receiver object）作为上下文（记得我是谁）
      • 也可以限制上下文的尺寸
  1. 类型敏感（Type Sensitivity）
      • 表示 在哪个类被创建（container）
      • 在相同的 下类型敏感的精确性 对象敏感，因为类型敏感是对象敏感的抽象
对比：在 OO 语言的实践过程中，有如下结论：
  • 精度：Object > Type > Call-Site
  • 效率：Type > Call-Site > Object

污点分析

Sources：污点源方法的集合（会返回污点数据的方法调用）
Sinks：带有敏感参数的水槽方法的集合（元组， 表示方法 的第 个参数是 sink）
信息流安全（Information Flow Security） 是指通过追踪信息是如何在程序中流动的方式，来确保程序安全地处理了它所获得的信息。
机密性（Confidentiality） 指的是阻止机密的信息泄漏
  • 信息只能从低机密的数据流向高机密
  • 读保护
完整性（Integrity） 指的是阻止不信任的信息污染受信任的关键信息
  • 不允许信息从不信任流向信任
  • 注入攻击破坏了完整性
显示流：信息可以通过直接拷贝的方式进行流动
隐式流：信息可以通过影响控制流的方式向外传递
信道：计算 系统中指示信息的机制
指示信息的机制的本意并不是信息传递，这样的信道称为隐蔽信道：隐式流、终止信道、时间信道、异常
 
Loading...

© Qiyue Zhang 2026