文章总结： 文章介绍了静态程序分析中的数据流分析技术，包括证明转换函数单调性的方法、格的高度概念、May和Must分析的区别、常量传播分析以及Worklist算法优化。文章最后提供了基于Tai-e框架的LiveVariableAnalysis的完整代码实现，包括三个关键类的详细代码，展示了如何在实际框架中实现数据流分析算法。 综合评分： 85 文章分类： 代码审计,安全工具,技术标准,二进制安全,其他
静态程序分析之数据流分析(Foundations + LiveVar Analysis Code)续
TeddyBe4r
看雪学苑
2025年10月22日 20:57 上海
从Bottom出发达到的一定是最小不动点，从Top出发到达的一定是最大不动点。
Prove Function is Monotonic(证明转换函数单调性)
对于Transfer Function的单调性，我们需要回到之前的章节
以这个为例子，在课程中笔者认为该例子过于晦涩难懂，仅仅因为 genB固定 KillB固定就证明该函数是单调的。但实际上我们可以通过一个不严谨的思想来理解这个Transfer Function是单调的，我们考虑将该函数类比为 普通的一次函数。
y = const1 + x - const2
其中
y = OUT[B]
const1 = genb
x = IN[B]
const2 = killB
通过如上的类似仿射变换的思想可以帮助我们理解Transfer Funcion的单调性。
合理严格的证明如下
这里的证明思路还是阐述一下方便理解。
1.首先我们根据lub 的定义可以得出y <= y V z因为y V z是 y的lub
2.根据传递性 因为x <= y且y <= y V z所以x <= y V z
3.然后我们又一次根据 lub的定义x V z是x的lub 而y V z是 x的ub
4.根据lub的定义 lub 必定小于等于 ub
5.所以我们能够得出x V z <= y V z
经过如上的证明我们能够将数据分析的问题转化到格上，且能够通过获取lfp和gfp 得到Best Fixed Point，也能够证明这些问题是一定有解的。
现在我们需要讨论什么时候我们能够抵达不动点。为了解决这个问题我们需要引入格的高度这个概念。
Height of Lattice（格的高度）
#
格的高度就是从 Top 到 Buttom最长的一条路径就是 格的高度
最坏的迭代次数就是格高度 * 节点个数该次数是悲观上界 辅佐以下图理解，不过我们需要申明几个前提
1.每次走一步
2.每次只有一个节点变化
CFG节点 B1: OUT[B1] = ∅ → {a} → {a,b} → {a,b,c}
↑ 格中的某个元素
CFG节点 B2: OUT[B2] = ∅ → {c} → {b,c} → {a,b,c}
↑ 格中的某个元素
CFG节点 B3: OUT[B3] = ∅ → {b} → {a,b} → {a,b,c}
↑ 格中的某个元素
May And Must Analysis, a Lattice view(从格视角理解May 和 Must 分析)
#
我们可以考虑把一个PL的 抽象的Lattice 的 Product Lattice看成一个新的Lattice
#
May Analysis
#
对于May 我们通常是从 Bottom 出发从一个unsafe result到 safe result的过程
结合这张图我们用 Reach Def 举例子
在Reaching Definitions问题中，我们在Entry块给所有变量一个undefined定义。在格中：
◆Bottom (⊥): 空集，表示没有信息，这是分析的起点（信息最不完整）
◆Top (⊤): 全集，表示所有定值（包括所有undefined）都可能到达，这是最保守的过近似（最不精确）
◆迭代过程: 从Bottom出发，单调地向上增长，逐步添加可达的定值
◆不动点: 最终收敛到最小不动点，这是最精确的安全解
◆语义: 如果某点的undefined定义可达，说明变量可能未初始化（不安全）；如果不可达，说明变量已被定义（安全）
这里我们做一个类比理解
想象你问：”明天会下雨吗？”
| | | | | — | — | — | | 回答 | 对应 | 评价 | | “不知道”（啥都没说） | ⊥ (Bottom) | ❌ 不靠谱（可能错过重要信息） | | “有30%概率下雨” | 不动点 | ✅ 靠谱且有用 | | “明天可能下雨，可能晴天，可能下雪，可能刮风，可能地震，可能外星人入侵…” | ⊤ (Top) | ✅ 靠谱（肯定不会错）❌ 但完全没用 |
Must Analysis
Available Expressions分析是Must分析，目标是找出在某个程序点肯定被计算过且还有效的表达式（用于优化，如公共子表达式消除）。
格的结构
◆Top (⊤): 所有可能表达式的全集
◆Bottom (⊥): 空集 ∅（没有表达式available）
◆偏序关系: 集合包含 ⊇（注意方向相反！）
◆合并操作: 交集 ∩
Top (⊤) = 所有表达式的全集
◆含义：假设所有表达式都available
◆这是Unsafe的（过度乐观，可能错误）
◆如果用这个结果做优化可能出错
Bottom (⊥) = ∅ (空集)
◆含义：没有表达式available
◆这是Safe的（最保守，绝对不会出错）
◆但最没用（无法做任何优化）
我们给出该图进行回顾总结
Definitions问题
| | | | | — | — | — | | 视角 | 问题 | 分析类型 | | May | “哪些定值可能到达？” | May Reaching Defs | | Must | “哪些定值一定到达？” | Must Reaching Defs |
Expressions问题
| | | | | — | — | — | | 视角 | 问题 | 分析类型 | | May | “哪些表达式可能被计算过？” | May Available Expr | | Must | “哪些表达式一定被计算过？” | Must Available Expr |
#
How Precise is Our Solution？
◆Meet Over-All-Paths Solution(MOP)
MOP和常见的迭代算法的结果区别
一个是 利用了控制流的Merge一个是用最后的节点的路径去做Merge
Mop 和 迭代算法精度的区别
当算法具有可分配性的时候可以视作 MOP和 Ours的精确度相等。对于Gen/Kill 问题都是具有可分配性的
Constant Propagetion（常量传播）
Data Abstruct And Transfer Function
undefine在L里是top，其他常量≤undef，若undef的一个函数输出是常量，则这个常量可能小于其他常量的函数的输出结果，导致gen(undef)≤gen(c) 不满足单调性
Worklist Algorithm(Iterator 的优化算法)
以下就是Worklist
对于Worklist算法其实就是对 迭代算法的一种优化，只操作有变化的集合。
接下来我给出基于Tai-E框架的对Live Var Analysis 的 代码。
/* LiveVariableAnalysis.java */
/*
* Tai-e: A Static Analysis Framework for Java
*
* Copyright (C) 2022 Tian Tan <[email protected]>
* Copyright (C) 2022 Yue Li <[email protected]>
*
* This file is part of Tai-e.
*
* Tai-e is free software: you can redistribute it and/or modify
* it under the terms of the GNU Lesser General Public License
* as published by the Free Software Foundation, either version 3
* of the License, or (at your option) any later version.
*
* Tai-e is distributed in the hope that it will be useful,but WITHOUT
* ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
* or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General
* Public License for more details.
*
* You should have received a copy of the GNU Lesser General Public
* License along with Tai-e. If not, see <https://www.gnu.org/licenses/>.
*/
package pascal.taie.analysis.dataflow.analysis;
import pascal.taie.analysis.dataflow.fact.SetFact;
import pascal.taie.analysis.graph.cfg.CFG;
import pascal.taie.config.AnalysisConfig;
import pascal.taie.ir.exp.RValue;
import pascal.taie.ir.exp.Var;
import pascal.taie.ir.stmt.Stmt;
/**
* Implementation of classic live variable analysis.
*/
public class LiveVariableAnalysis extends
AbstractDataflowAnalysis<Stmt, SetFact<Var>> {
public static final String ID = "livevar";
public LiveVariableAnalysis(AnalysisConfig config) {
super(config);
}
@Override
public boolean isForward() {
return false;
}
@Override
public SetFact<Var> newBoundaryFact(CFG<Stmt> cfg) {
// TODO - finish me
System.out.println("[*] bottom init");
return new SetFact<>();
}
@Override
public SetFact<Var> newInitialFact() {
// TODO - finish me
// System.out.println("[*] assume all pl without live var");
return new SetFact<>();
}
@Override
public void meetInto(SetFact<Var> fact, SetFact<Var> target) {
// TODO - finish me
// System.out.println("[*] meet");
target.union(fact);
}
@Override
public boolean transferNode(Stmt stmt, SetFact<Var> in, SetFact<Var> out) {
// TODO - finish me
// 保存 in 的旧值，用于比较是否发生变化
SetFact<Var> oldIn = in.copy();
// 1. 先将 OUT[s] 复制到 IN[s]
in.set(out);
// 2. 处理定义（def）：移除被定义的变量
// 获取语句中被定义的变量（赋值语句的左侧）
stmt.getDef().ifPresent(lValue -> {
if (lValue instanceof Var) {
// 从 IN 中移除被定义的变量
in.remove((Var) lValue);
}
});
// 3. 处理使用（use）：添加被使用的变量
// 获取语句中使用的所有变量（赋值语句的右侧）
for (RValue rValue : stmt.getUses()) {
if (rValue instanceof Var) {
// 将使用的变量添加到 IN 中
in.add((Var) rValue);
}
}
// 4. 检查 IN 是否发生变化
// 如果改变了，迭代求解器需要继续迭代
return !in.equals(oldIn);
}
}
/* IterativeSolver.java */
/*
* Tai-e: A Static Analysis Framework for Java
*
* Copyright (C) 2022 Tian Tan <[email protected]>
* Copyright (C) 2022 Yue Li <[email protected]>
*
* This file is part of Tai-e.
*
* Tai-e is free software: you can redistribute it and/or modify
* it under the terms of the GNU Lesser General Public License
* as published by the Free Software Foundation, either version 3
* of the License, or (at your option) any later version.
*
* Tai-e is distributed in the hope that it will be useful,but WITHOUT
* ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
* or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General
* Public License for more details.
*
* You should have received a copy of the GNU Lesser General Public
* License along with Tai-e. If not, see <https://www.gnu.org/licenses/>.
*/
package pascal.taie.analysis.dataflow.solver;
import pascal.taie.analysis.dataflow.analysis.DataflowAnalysis;
import pascal.taie.analysis.dataflow.fact.DataflowResult;
import pascal.taie.analysis.graph.cfg.CFG;
class IterativeSolver<Node, Fact> extends Solver<Node, Fact> {
public IterativeSolver(DataflowAnalysis<Node, Fact> analysis) {
super(analysis);
}
@Override
protected void doSolveForward(CFG<Node> cfg, DataflowResult<Node, Fact> result) {
throw new UnsupportedOperationException();
}
@Override
protected void doSolveBackward(CFG<Node> cfg, DataflowResult<Node, Fact> result) {
// TODO - finish me
// 注意：不要在这里调用 initializeBackward
// 初始化已经在 Solver.solve() -> initialize() 中完成了
boolean changed = true; // 标记是否有变化
// 不动点迭代：重复直到没有变化
while (changed) {
changed = false; // 假设本轮没有变化
// 遍历 CFG 中的所有节点（除了 EXIT）
// 对于后向分析，我们从 EXIT 开始向前传播
for (Node node : cfg) {
// 跳过 EXIT 节点（它的 OUT 是边界条件，不会改变）
if (node == cfg.getExit()) {
continue;
}
// ========== Step 1: Meet 操作 ==========
// OUT[B] = ⋃ IN[S] (对所有后继 S)
// 对于活跃变量分析：OUT[B] = IN[S1] ∪ IN[S2] ∪ ...
// 获取当前节点的所有后继
// 后继的 IN 会汇聚到当前节点的 OUT
for (Node succ : cfg.getSuccsOf(node)) {
// 调用 meetInto 将后继的 IN 合并到当前节点的 OUT
// meetInto(fact, target): 将 fact 合并到 target
analysis.meetInto(
result.getInFact(succ), // 后继的 IN fact
result.getOutFact(node) // 当前节点的 OUT fact（会被修改）
);
}
// ========== Step 2: Transfer 函数 ==========
// IN[B] = transfer(B, OUT[B])
// 对于活跃变量分析：IN[B] = use[B] ∪ (OUT[B] - def[B])
// transferNode 会：
// 1. 根据 OUT[B] 计算新的 IN[B]
// 2. 如果 IN[B] 发生改变，返回 true
if (analysis.transferNode(
node, // 当前节点
result.getInFact(node), // IN fact（会被修改）
result.getOutFact(node) // OUT fact（只读）
)) {
// 如果 IN 发生了变化，需要继续迭代
changed = true;
}
}
}
}
}
/* Solver.java */
/*
* Tai-e: A Static Analysis Framework for Java
*
* Copyright (C) 2022 Tian Tan <[email protected]>
* Copyright (C) 2022 Yue Li <[email protected]>
*
* This file is part of Tai-e.
*
* Tai-e is free software: you can redistribute it and/or modify
* it under the terms of the GNU Lesser General Public License
* as published by the Free Software Foundation, either version 3
* of the License, or (at your option) any later version.
*
* Tai-e is distributed in the hope that it will be useful,but WITHOUT
* ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
* or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General
* Public License for more details.
*
* You should have received a copy of the GNU Lesser General Public
* License along with Tai-e. If not, see <https://www.gnu.org/licenses/>.
*/
package pascal.taie.analysis.dataflow.solver;
import pascal.taie.analysis.dataflow.analysis.DataflowAnalysis;
import pascal.taie.analysis.dataflow.fact.DataflowResult;
import pascal.taie.analysis.graph.cfg.CFG;
/**
* Base class for data-flow analysis solver, which provides common
* functionalities for different solver implementations.
*
* @param <Node> type of CFG nodes
* @param <Fact> type of data-flow facts
*/
public abstract class Solver<Node, Fact> {
protected final DataflowAnalysis<Node, Fact> analysis;
protected Solver(DataflowAnalysis<Node, Fact> analysis) {
this.analysis = analysis;
}
/**
* Static factory method to create a new solver for given analysis.
*/
public static <Node, Fact> Solver<Node, Fact> makeSolver(
DataflowAnalysis<Node, Fact> analysis) {
return new IterativeSolver<>(analysis);
}
/**
* Starts this solver on the given CFG.
*
* @param cfg control-flow graph where the analysis is performed on
* @return the analysis result
*/
public DataflowResult<Node, Fact> solve(CFG<Node> cfg) {
DataflowResult<Node, Fact> result = initialize(cfg);
doSolve(cfg, result);
return result;
}
/**
* Creates and initializes a new data-flow result for given CFG.
*
* @return the initialized data-flow result
*/
private DataflowResult<Node, Fact> initialize(CFG<Node> cfg) {
DataflowResult<Node, Fact> result = new DataflowResult<>();
if (analysis.isForward()) {
initializeForward(cfg, result);
} else {
initializeBackward(cfg, result);
}
return result;
}
protected void initializeForward(CFG<Node> cfg, DataflowResult<Node, Fact> result) {
throw new UnsupportedOperationException();
}
protected void initializeBackward(CFG<Node> cfg, DataflowResult<Node, Fact> result) {
// TODO - finish me
// 1. 为 EXIT 节点设置边界条件
// EXIT 是后向分析的起点（边界）
result.setOutFact(cfg.getExit(), analysis.newBoundaryFact(cfg));
// 2. 为 CFG 中的所有节点设置初始 fact
for (Node node : cfg) {
// 初始化所有节点的 IN fact（防止 null）
result.setInFact(node, analysis.newInitialFact());
// 初始化非 EXIT 节点的 OUT fact
if (node != cfg.getExit()) {
result.setOutFact(node, analysis.newInitialFact());
}
}
}
/**
* Solves the data-flow problem for given CFG.
*/
private void doSolve(CFG<Node> cfg, DataflowResult<Node, Fact> result) {
if (analysis.isForward()) {
doSolveForward(cfg, result);
} else {
doSolveBackward(cfg, result);
}
}
protected abstract void doSolveForward(CFG<Node> cfg, DataflowResult<Node, Fact> result);
protected abstract void doSolveBackward(CFG<Node> cfg, DataflowResult<Node, Fact> result);
}
看雪ID：TeddyBe4r
https://bbs.kanxue.com/user-home-983513.htm
*本文为看雪论坛精华文章，由 TeddyBe4r 原创，转载请注明来自看雪社区
倒计时！看雪·第九届安全开发者峰会（SDC2025）
往期推荐
无”痕”加载驱动模块之傀儡驱动 (上)
为 CobaltStrike 增加 SMTP Beacon
隐蔽通讯常见种类介绍
buuctf-re之CTF分析
物理读写/无附加读写实验
球分享
球点赞
球在看
点击阅读原文查看更多
版权声明
本站仅做备份收录，仅供研究与教学参考之用。
读者将信息用于其他用途的，全部法律及连带责任由读者自行承担，本站不承担任何责任。
评论