github地址

1.介绍

组件	核心目标	Tai-e的关键设计与优势
程序抽象（如IR、类层次）	为程序分析提供统一、清晰、易操作的程序表示	1.采用更简洁、语义明确的中间表示（IR），比 Soot/Wala 的IR更易读写。2.IR 设计贴近分析逻辑，减少template代码，提升算法实现效率。3.类层次和方法签名等元数据结构清晰，便于查询与扩展
基础分析	（如CFG、指针分析） 提供高质量、可复用的基础分析结果	1.控制流图（CFG）与调用图构建准确且接口友好。2.指针分析系统高度模块化、可扩展，支持快速实现新算法（如上下文敏感变体）。3.性能优于主流框架，同时保持结果精度
新分析开发机制	降低开发者实现新分析（如污点、异常、反射分析）的门槛	1.引入插件式分析开发模型，新分析只需实现标准接口。2.内置对与指针分析交互的支持，简化复杂分析（如 taint analysis）的集成。3.提供调试友好的执行流程，便于理解与验证分析逻辑。
多分析协同管理	支持多个分析按需组合、依赖协调与结果共享	1.定义标准化的分析调度与依赖管理机制。2.分析间可通过统一接口传递中间结果（如别名信息、可达性）。3.避免重复计算，提升整体分析效率与可组合性。

1.1.程序抽象

Tai-e相比Soot、Wala的改进总结为下面表格

问题维度	Soot和Wala的处理	Tai-e的改进
语句类型区分	在Soot中所有赋值语句统一为 AssignStmt，不区分 new、binary、load 等类型，需大量 instanceof 检查和强制类型转换，Wala明确区分语句类型（如 SSABinaryOpInstruction）	明确区分语句子类型（如 Binary），避免冗余类型检查
表达式/操作数返回类型	Soot总是返回顶层接口 Value ，使用时需频繁downcast（如转为 Local），Wala使用整数索引（如 int op2）以及间接引用操作数，需查符号表获取实际值，调试困难	1.返回具体类型（如 Local, Constant）。2.直接持有操作数值，无需索引或额外查找。
信息组织方式	Soot变量、类型、名称等信息分散在多个接口中，Wala类型、名称需通过 ir 或 TypeInference 等不同模块获取，API 不统一	统一聚合变量相关信息到单一接口（如通过语句对象直接获取操作数、类型、名称等）

与Soot、Wala相比Tai-e代码更简洁

• 1.无需冗余的类型判断与强制转换。比如处理二元操作时，Tai-e直接使用 Binary 类型，而Soot需先cast再check。

• 2.IR结构贴近分析逻辑，API自解释性强（“self-explainable”）。

• 3.开发效率更高，开发者可直接通过语句/变量对象访问所需信息，无需跨多个接口拼凑数据。

• 4.支持高级分析优化。例如：每个变量 v 在IR中关联其所有相关语句，便于指针分析中快速响应值变化。

// Soot
void processBinary(AssignStmt assign) {
    Value rightOp = assign.getRightOp();
    // "Abstract" statement introduces conditional checks
    if (rightOp instanceof BinopExpr) {
        BinopExpr binopExpr = (BinopExpr) rightOp;
        // "Top" returned type needs casting
        Local lhs = (Local) assign.getLeftOp();
        Value op1 = binopExpr.getOp1();
        Value op2 = binopExpr.getOp2();
        // obtain name of op1
        if (op1 instanceof Local) {
           Local var1 = (Local) op1;
           String name1 = var1.getName();
        }
        // obtain type of op1
        Type type1 = op1.getType();
        // obtain constant value of op2
        if (op2 instanceof Constant) {
            Constant val2 = (Constant) op2;
        }
    }
}

// WALA
void processBinary(SSABinaryOpInstruction binary, IR ir) {
    int lhs = binary.getDef();
    // getUse() returns an int value as index to access the
    // info of the corresponding operand: lines 32, 37-39
    int op1 = binary.getUse(0);
    int op2 = binary.getUse(1);
    // obtain name of op1
    String[] name1 = ir.getLocalNames(binary.iIndex(), op1);
    // obtain type of op1
    TypeInference ti = TypeInference.make(ir, true);
    TypeAbstraction type1 = ti.getType(op1);
    // obtain constant value of op2
    SymbolTable symbolTable = ir.getSymbolTable();
    if (symbolTable.isConstant(op2)) {
        Object val2 = symbolTable.getConstantValue(op2);
    }
}

// Tai-e
void processBinary(Binary binary) {
    Var lhs = binary.getLValue();
    BinaryExp binaryExp = binary.getRValue();
    Var op1 = binaryExp.getOperand1();
    Var op2 = binaryExp.getOperand2();
    // obtain name of op1
    String name1 = op1.getName();
    // obtain type of op1
    Type type1 = op1.getType();
    // obtain constant value of op2
    if (op2.isConst()) {
        Literal val2 = op2.getConstValue();
    }
}

1.2.基础分析

Tai-e主要聚焦在指针分析（Pointer Analysis） 和控制/数据流分析（Control/Data Flow Analysis）两大基础分析。

在指针分析方面

设计维度	经典框架问题	Tai-e的解决方案	优势
1. 指向集表示（Points-to Representation）	Soot/Wala 使用固定大小的位图（bit set），即使只有少量对象也浪费大量内存	采用 “虚拟内存”式稀疏位图（两层页表结构），动态分配存储空间	1.平均节省23%内存（最高 40%）。2.在有限内存下可分析更大程序。
2. 上下文管理（Context Sensitivity）	1.Soot：缺乏高效上下文敏感支持（Spark无上下文，Paddle已废弃）。2.Doop：需为每种上下文长度重写Datalog规则，代码冗余。3.Wala：仅支持callsite-sensitivity，object-sensitivity继承自方法	统一、参数化的上下文管理机制: 1.可独立指定callsite-sensitivity和object-sensitivity的上下文策略（如 3-callsite + 1-object）。2.原生支持选择性上下文敏感（selective context sensitivity）。3.易于实现新算法（如 Zipper、Scaler、Mahjong）	灵活平衡精度与性能

CFG/DF分析方面

分析类型	经典框架局限	Tai-e 的优化	效果
控制流图（CFG）	1.Soot/Wala/Checker：不分类CFG边（如 IF_TRUE、EXCEPTION 等）。2.异常处理粗糙：多数框架未区分显式/隐式异常流。	细粒度边标签：(a).IF_TRUE / IF_FALSE、(2).SWITCH 边带 case 值、(3).EXCEPTION 边带具体异常类型、(4).区分显式 vs 隐式异常流，允许用户按需包含。(5).集成高精度异常分析	1.支持路径敏感、分支相关分析。2.提升CFG完整性与实用性
数据流分析框架	1.Wala：初始化逻辑耦合到求解器，每换初始化策略就要重写求解器。2.Soot/Checker：不直接支持边转移函数（edge transfer functions），需hack实现分支感知分析	1.解耦求解器与分析逻辑：一个通用求解器驱动多种分析。2.原生支持边转移函数：(1).允许沿不同边传播不同dataflow fact、(2).利用分支条件提升分析精度	1.开发者只需关注分析本身。2.更自然地实现条件敏感分析。

1.3.新分析算法实现

静态分析框架应支持开发者方便地实现新的分析（如反射分析、异常分析、污点分析、漏洞检测等），这些分析通常需要与指针分析深度交互。而其它框架存在明显不足：

• 1.Doop（基于Datalog）：虽能优雅表达交互逻辑，但难以处理非集合型格（non-set lattices），且优化困难。

• 2.Soot：缺乏对指针分析交互的原生支持。

• 3.Wala：提供有限交互机制（通过 ContextSelector 和 ContextInterpreter 生成“虚拟 IR”），但存在两大缺陷：(1).无法监听变量指向集的变化（如异常分析中需响应 throw e 的变化）；(2).必须生成大量虚拟代码并重新分析，效率低；不能直接修改调用图或指向集。

Tai-e对此的解决方案是分析插件系统（Analysis Plugin System）。核心思想提供一个简单、统一、事件驱动的接口，让新分析算法能与指针分析求解器（Solver）双向通信。开发者只需实现一个 Plugin 接口中的少数方法，即可构建复杂分析，无需了解指针分析内部实现。关键机制是事件通知机制：

机制类别	核心特性	优势与作用
事件通知机制	1.onNewPointsToSet(Var v, PointsToSet pts)：变量指向集更新时触发。2. onNewCallEdge(CallEdge edge)：新调用边解析出时触发	实现响应式编程模型，让插件能实时感知指针分析进展，无需轮询或侵入核心逻辑
直接干预能力	1.调用Solver API：(1). addPointsTo(var, obj); (2). addCallEdge(callsite, method)。2.辅助API：addStmts(...)（用于模拟 IR）	避免生成冗余虚拟代码，提升效率；支持灵活修改分析状态，增强表达力
极简接口设计	1.仅需实现 Plugin 接口。2.核心方法 ≤ 3 个（如 onNewPointsToSet, onNewCallEdge, onFinish）。3.其余为可选辅助方法	学习成本低，新手也能快速上手；解耦分析逻辑与框架实现
实际应用覆盖	已支持十余类分析：1.基础分析包括：反射、异常。2.安全分析：污点分析。3.语言特性：Lambda、方法引用。4.运行时建模：线程、native 代码。5.工具：分析计时器、约束检查器	验证了系统的通用性、可扩展性与实用性

1.4.多分析管理

管理维度	经典框架（Soot/Wala/SpotBugs）的问题	Tai-e 的解决方案与优势
分析配置与依赖管理	1.Soot：需硬编码注册分析（Transformer），且运行时必须手动指定所有依赖链，易出错。2.Wala：无显式多分析管理机制。3.SpotBugs：依赖配置较静态，缺乏条件逻辑支持	1.通过单一配置文件声明分析及其依赖。2.自动解析依赖关系，确保执行顺序正确。3.支持条件逻辑描述依赖与选项。4.无需命令行参数，降低使用门槛
分析结果存储与访问	1.Soot/Wala：无统一结果管理机制；Soot仅部分分析结果存于 Scene 单例中。2.SpotBugs：需记忆不同API和参数获取各类结果，接口不一致	1.提供统一接口：getResult(id)（id 为配置中的分析名）。2.自动按分析类型（方法/类/程序级）存储结果。3.无需记忆复杂方法或额外参数，提升可用性
整体体验反馈	1.开发者反映Soot中“不清楚有哪些分析可用”，难以共享和复用。2.Wala 需手动拼接多个分析，组合困难	1.Tai-e 内置多种分析，易于组合。2.新开发者能快速理解框架能力，促进社区协作与复用

1.5.效率

作者在Java DaCapo benchmarks上拿Tai-e与Qilin、Doop、Soot进行了对比。指针分析的开销如下。

活跃变量分析的效果如下

2.分析算法

2.1.指针分析

指针分析算法参考Pointer Analysis - Context Sensitivity以及上下文敏感的指针分析。分析规则是上下文敏感的，将CSPointer映射到CSObject集合，其中CSPointer可表示为 $(C\times V)\cup (C\times O\times F)$，而CSObject可表示为 $C\times O$。$C$ 表示context variable集合，$V$ 表示变量集合，$O$ 表示memory object集合，通常一个memory object对应一个allocation site( new 语句)，$F$ 表示字段集合。$o.f$ 表示object $o$ 的 $f$ 字段，$o[\ast ]$ 表示object $o$ 的任意数组偏移（Tai-e采用array- insensitive算法，因此任意偏移值别名）。具体规则如下

语句类型	abstraction	规则	PFG边
New	$x=\text{new}\text{T}()$ (allocate $o$)	$⟨c,o⟩\in \text{pts}(⟨c,x⟩)$	无
Assign	$x=y$	$\text{pts}(⟨c,y⟩)\subseteq \text{pts}(⟨c,x⟩)$	$⟨c,y⟩\to ⟨c,x⟩$
FieldLoad	$x=v.f$	$\text{pts}(⟨c^{{}^{\prime }},o.f⟩)\subseteq \text{pts}(⟨c,x⟩)\mid \forall ⟨c^{{}^{\prime }},o⟩\in \text{pts}(⟨c,v⟩)$	$⟨c^{{}^{\prime }},o.f⟩\to ⟨c,x⟩$
FieldStore	$v.f=y$	$\text{pts}(⟨c,y⟩)\subseteq \text{pts}(⟨c^{{}^{\prime }},o.f⟩)\mid \forall ⟨c^{{}^{\prime }},o⟩\in \text{pts}(⟨c,v⟩)$	$⟨c,y⟩\to ⟨c^{{}^{\prime }},o.f⟩$
ArrayLoad	$x=v[i]$	$\text{pts}(⟨c^{{}^{\prime }},o[\ast ]⟩)\subseteq \text{pts}(⟨c,x⟩)\mid \forall ⟨c^{{}^{\prime }},o⟩\in \text{pts}(⟨c,v⟩)$	$⟨c^{{}^{\prime }},o[\ast ]⟩\to ⟨c,x⟩$
ArrayStore	$v[i]=y$	$\text{pts}(⟨c,y⟩)\subseteq \text{pts}(⟨c^{{}^{\prime }},o[\ast ]⟩)\mid \forall ⟨c^{{}^{\prime }},o⟩\in \text{pts}(⟨c,v⟩)$	$⟨c,y⟩\to ⟨c^{{}^{\prime }},o[\ast ]⟩$
StaticLoad	$x=T.f$	$\text{pts}(T.f)\subseteq \text{pts}(⟨c,x⟩)$	$T.f\to ⟨c,x⟩$
StaticStore	$T.f=y$	$\text{pts}(⟨c,y⟩)\subseteq \text{pts}(T.f)$	$⟨c,y⟩\to T.f$
Call	$l:r=x.k(a_1,\dots ,a_n)$	$1.\text{pts}(⟨c,a_i⟩)\subseteq \text{pts}(⟨c^t,m_{p_i}⟩),2.\text{pts}(⟨c^t,m_{\text{ret}}⟩)\subseteq \text{pts}(⟨c,r⟩),3.\text{pts}(⟨c,x⟩)\in \text{pts}(⟨c^t,m_{\text{this}}⟩\mid \forall ⟨c^{{}^{\prime }},o⟩\in \text{pts}(⟨c,x⟩),m=\text{Dispatch}(o_i,k),c_t=\text{Select}(c,l,⟨c^{{}^{\prime }},o⟩),i\in [1,n]$	$⟨c,x⟩\to ⟨c^t,m_{\text{this}}⟩$, $⟨c,a_i⟩\to ⟨c^t,m_{p_i}⟩$, $⟨c^t,m_{\text{ret}}⟩\to ⟨c,r⟩$
StaticCall	$l:r=T.m(a_1,...,a_n)$	$\text{pts}(⟨c,a_i⟩)\subseteq \text{pts}(⟨c^t,m_{p_i}⟩),\text{pts}(⟨c^t,m_{\text{ret}}⟩)\subseteq \text{pts}(⟨c,r⟩)\mid c^t=\text{Select}(c,l),i\in [1,n]$	$⟨c,a_i⟩\to ⟨c^t,m_{p_i}⟩$, $⟨c^t,m_{\text{ret}}⟩\to ⟨c,r⟩$

和C相比Java是面向对象语言，因此在Java指针分析中，调用图的求解需要用到 $\text{Dispatch}$ 和 $\text{Select}$ 函数：

• $\text{Dispatch}(o_i,k)$ 通常基于对象 $o_i$ 的类型分析 $k$ 具体的调用目标（哪个类的哪个函数）。

• $\text{Select}(c,l,⟨c^{{}^{\prime }},o⟩)$ 基于callsite $l$ 的信息分析callee中其它变量的context variable $c^t$，其中context variable可用 list 表示。对于callsite-sensitivity（call-string、k-CFA），$c^t=[c;l]$（list 拼接操作）；对于object-sensitivity，$c^t=[c^{{}^{\prime }};o]$；对于type-sensitivity，$c^t=[c^{{}^{\prime }};\text{InType}(o)]$，$\text{InType}$ 表示 $o$ 对应的allocation site所在成员函数对应的类，比如下面代码中 $\text{InType}(o)=X$。

class X {
    void m() {
        Y y = new Y(); // allocate o
    }
}

下图对比了3种context-sensitivity策略在分析一些java程序的开销以及精度，其中精度用 may-fail-cast 和call graph求解表示，数字越小精度越高。可以看到callsite-sensitvity精度最低开销最高，性价比很低。所以通常Java分析都采用object-sensitivity，type-sensitivity可以当作object-sensitivity的降级版本，精度变低了但是开销更小。

指向集的计算采用WorkList算法，过程大致如下。

2.2.污点分析

参考Static Analysis for Security以及污点分析，Tai-e的污点分析算法采用的是P/Taint ${}^{[2]}$，也就是和指针分析共享一套分析框架。在指针分析的基础上增加了下面规则，其中都是处理调用 $l:r=x.k(a_1,...,a_n)$，并且根据指针分析结果，有 $⟨c,l⟩\to ⟨c^t,m⟩\in \text{CG}$，也就是在当前调用context $c$ 下语句 $l$ 会调用方法 $m$，并且 $m$ 中变量的context为 $c^t$。这里taint tag会被视为一种特殊的object。

• 由 $m\in \text{Sources}$ 表示 $m$ 的返回值会生成一个新的taint tag。

• $⟨m,i⟩\in \text{Sinks}$ 表示如果函数 $m$ 第 $i$ 个参数指向taint tag那么存在一条taint flow。

• $⟨m,\text{from},\text{to}⟩\in \text{TaintTransfers}$ 包括除了赋值操作以外额外的污点传播规则，表示函数 $m$ 的 $\text{from}$ 参数如果指向taint tag，那么 $\text{to}$ 参数也会指向。$\text{from}$ 可以为base变量也就是 $r=x.k(...)$ 中的 $x$，也可以是某个参数 $a_i$。而 $\text{to}$ 可以是base $x$ 或者result变量 $r$。StringBuilder.append(String) 就属于arg-to-base传播规则。

• 污点分析的结果为taint flow集合 $\text{TaintFlows}$，其中 $⟨l^{{}^{\prime }},l,i⟩\in \text{TaintFlows}$ 表示语句 $l^{{}^{\prime }}$ 生成的taint tag流入了语句 $l$ 的第 $i$ 个参数。

类型	规则
Source	$t_l\in \text{pts}(⟨c,r⟩)\mid m\in \text{Sources}$
Sink	$⟨l^{{}^{\prime }},l,i⟩\in \text{TaintFlows}\mid ⟨m,i⟩\in \text{Sinks},t_{l^{{}^{\prime }}}\in \text{pts}(⟨c,a_i⟩)$
Transfer(base-to-result)	$t_{l^{{}^{\prime }}}\in \text{pts}(⟨c,r⟩)\mid ⟨m,\text{base},\text{result}⟩\in \text{TaintTransfers},t_{l^{{}^{\prime }}}\in \text{pts}(⟨c,x⟩)$
Transfer(arg-to-result)	$t_{l^{{}^{\prime }}}\in \text{pts}(⟨c,r⟩)\mid ⟨m,i,\text{result}⟩\in \text{TaintTransfers},t_{l^{{}^{\prime }}}\in \text{pts}(⟨c,a_i⟩)$
Transfer(arg-to-base)	$t_{l^{{}^{\prime }}}\in \text{pts}(⟨c,x⟩)\mid ⟨m,i,\text{base}⟩\in \text{TaintTransfers},t_{l^{{}^{\prime }}}\in \text{pts}(⟨c,a_i⟩)$

下面代码中有 Sources = { getPassword } \text{Sources} = \{ \text{getPassword} \} Sources={getPassword}，$\text{Sinks}=\{⟨\text{log},0⟩\}$，其中指针/污点分析结束后每个变量的point-to set如下表所示（context-insensitive版本），因此最后分析到 log(s) 时会生成taint flow $⟨2,5,0⟩$ 表示line 2生成的taint tag流向line 5第0个参数。

void main() {
    A x = new A(); // o
    String pw = getPassword();  // t2 - line 2
    A y = x;
    x.f = pw;  
    String s = y.f;
    log(s); // line 5
}

变量	point-to set
$x$	{ o } \{ o \} {o}
$\text{pw}$	{ t 2 } \{ t_2 \} {t2​}
$y$	{ o } \{ o \} {o}
$o.f$	{ t 2 } \{ t_2 \} {t2​}
$s$	{ t 2 } \{ t_2 \} {t2​}

3.代码

Tai-e的IR参考program-abstraction。运行方面参考command-line-options.html，可以通过命令 java -jar tai-e-all.jar -cp foo.jar -cp "my program/dir/" -m baz.Main -java 8 -a "pta=cs:2-type;time-limit:60;" 运行指针分析。这里指针分析的入口在PointerAnalysis::analyze函数中，随后进入PointerAnalysis::runAnalysis分别调用 solver.setPlugin 加载插件以及 solver.solve 进行指针分析。通常进行指针分析的 solver 是DefaultSolver类型。PointerAnalysis::setPlugin中加载了一系列插件，包括

插件名称	功能说明	激活条件
AnalysisTimer	记录各分析阶段的耗时，用于性能监控	始终启用（优先注册以确保计时精确）
EntryPointHandler	识别并处理程序入口点，主要模拟 main 函数的 String[] args 数组	始终启用
ClassInitializer	建模类初始化逻辑（如 <clinit>）	始终启用
ThreadHandler	处理多线程相关语义（如 Thread.start()）	始终启用
NativeModeller	对native方法进行抽象建模（如 System.arraycopy）	始终启用
ExceptionAnalysis	高精度异常流分析，支持显式/隐式异常解析	始终启用
ReferenceHandler	处理软引用、弱引用等 java.lang.ref 相关逻辑	仅当Java版本 < 9 时启用
LambdaAnalysis	支持Java 8+ Lambda 表达式和方法引用的语义建模	仅当Java版本 ≥ 8 时启用
Java9StringConcatHandler	处理Java 9+ 中基于 invokedynamic 的字符串拼接优化	仅当Java版本 ≥ 9 时启用
ReflectionAnalysis	分析反射调用（如 Class.newInstance(), Method.invoke()）	当输入参数 reflection-inference 或 reflection-log 非空时启用
InvokeDynamicAnalysis	建模 invokedynamic 字节码（如用于动态语言或 Lambda）	当输入参数 handle-invokedynamic=true 且支持 MethodHandle 时启用，默认为 false
TaintAnalysis	实现污点分析（敏感数据流检测）	当提供 taint-config 文件或 taint-config-providers 非空时启用
ResultProcessor	后处理分析结果（如格式化、输出）	始终启用（最后注册）
用户自定义插件 （通过 options.plugins 指定）	允许用户通过配置动态加载额外插件	由命令行或配置文件中的 plugins 列表指定

3.1.指针分析

指针分析核心过程是 worklist 算法，这里用 $\text{WL}$ 表示 worklist，对应WorkList类。和文档中定义的算法不同的是，在实际分析过程中要想尽办法减少不必要的重复计算，比如context-sensitive分析过程中，对于context-sensitive method $⟨c^t,m⟩$ 需要context-sensitive分析其中部分语句但是其它 plugin 也可能需要context-insensitve分析。insensitive部分只需要运行1次就够了，所以具体实现过程对核心算法做了一些拆分。

在初始化 main 入口点信息 void main(String[] args) 时有 ⟨ args , { o m } ⟩ ∈ WL \langle \text{args}, \{o_m\} \rangle \in \text{WL} ⟨args,{om​}⟩∈WL, ⟨ o m [ ∗ ] , { o m i } ⟩ ∈ WL \langle o_m[*], \{o_{m_i}\} \rangle \in \text{WL} ⟨om​[∗],{omi​​}⟩∈WL 表示后续更新pts集后 pts ( args ) = { o m } \text{pts}(\text{args}) = \{ o_m \} pts(args)={om​}, pts ( o m [ ∗ ] ) = { o m ∗ } \text{pts}(o_m[*]) = \{ o_{m_*} \} pts(om​[∗])={om∗​​}。定义pointer flow graph为 $\text{PFG}$，Call Graph为 $\text{CG}$，$\text{pts}(⟨c,v⟩)$ 表示变量 $v$ 在context $c$ 下的指向集，指针分析算法会不断更新 $\text{PFG}$、$\text{CG}$ 以及每个变量的 $\text{pts}$ 直到收敛为止。worklist 每个元素为1个Entry，目前定义了两类Entry，CallEdgeEntry和PointerEntry：

• CallEdgeEntry 可以记为 $⟨⟨c,l⟩,⟨c^t,m⟩⟩$ 表示后面处理这个entry时 $⟨c,l⟩\to ⟨c^t,m⟩⟩\in \text{CG}$，$l$ 为callsite对应的语句、$m$ 为callee对应的方法、$c$, $c^t$ 为context variable。

• PointerEntry 可以记为 $⟨⟨c,x⟩,\text{CO}⟩$，$\text{CO}=\{⟨c_1,o_1⟩,...,⟨c_n,o_n⟩\}$ 为context-sensitive object集合，表示后面处理这个entry时有 $\text{CO}\subseteq \text{pts}(⟨c,x⟩)$。当需要添加entry时，Tai-e会过滤 $\text{CO}$ 的entry减少不必要的计算。

worklist 算法核心步骤如下，大致符合前面的算法定义不过实现层面还是有些不同。对于 PointerEntry $⟨⟨c,x⟩,\text{CO}⟩$ 处理步骤如下：

• 1.通过propagate函数会更新 p 的point-to set为 pts 同时分析pts中更新的部分 diff（记为 $\text{DO}$）, 并将 diff 沿着 p 的 copy 边连通的结点加入到 worklist 中，具体规则可描述为 (1).$\text{DO}=\text{CO}-\text{pts}(p),\text{CO}\subseteq \text{pts}(q)$；(2).$⟨q,\text{DO}⟩\in \text{WL}\mid \forall p\to q\in \text{PFG}$。

• 2.通过 processInstanceStore 以及 processCallEdge 等函数会往 $\text{PFG}$ 中添加新的边以及往 $\text{WL}$ 中添加新的entry但不会更新 pts 集。具体分析规则如下表所示，总共处理 FieldLoad、FieldStore、ArrayLoad、ArrayStore、Call 5种情况，其中每个 v 对应1个context-sensitive变量 $⟨c,v⟩$，$c$ 为当前context。处理 Call 时会先添加一个 CallEdgeEntry $⟨⟨c,l⟩,⟨c^t,m⟩$ 表示稍后到 processCallEdge 中进一步处理call relation以及添加 PointerEntry $⟨⟨c^t,m_{\text{this}}⟩,\text{pts}(⟨c,v⟩)⟩$ 表示更新 this 对象的指向集，不过这里似乎没有添加对应的PFG Edge。 $\text{Dispatch}(\text{Type}(o),l)$ 表示根据 $o$ 的类型以及 $l$ 调用的方法引用算出callee $m$，也就是哪个类的哪个成员函数，具体实现参考CallGraphs::resolveCallee函数。对于KObjSelector，$\text{Select}(⟨c,l⟩,⟨c^{{}^{\prime }},o⟩,m)=[c^{{}^{\prime }};o]$（对应 selectContext 函数）。

while (!workList.isEmpty()) {
    WorkList.Entry entry = workList.pollEntry();
    if (entry instanceof WorkList.PointerEntry pEntry) {
          Pointer p = pEntry.pointer();
          PointsToSet pts = pEntry.pointsToSet();
          PointsToSet diff = propagate(p, pts);
          if (!diff.isEmpty() && p instanceof CSVar v) {
              processInstanceStore(v, diff);
              processInstanceLoad(v, diff);
              processArrayStore(v, diff);
              processArrayLoad(v, diff);
              processCall(v, diff);
              plugin.onNewPointsToSet(v, diff);
          }
     } 
     else if (entry instanceof WorkList.CallEdgeEntry eEntry) 
          processCallEdge(eEntry.edge());            
}

在调用分析时 $\text{Dispatch}(\text{Type}(o),l)$ 对应语句是 JMethod callee = CallGraphs.resolveCallee(recvObj.getObject().getType(), callSite);，里面具体的处理逻辑如下，Java中有5种不同的调用指令具体参考下表，可以看到通常动态分配（也就是根据指针分析结果确定调用目标）是针对 InvokeInterface 和 InvokeVirtual ，而对于 InvokeSpecial 是根据callsite $l:r=v.k(...)$ 中 $v.k$ 对应的签名识别分配的类型而不是 $\text{Type}(o)$。最后标准指针分析框架暂时不处理 invokedynamic 也就是 lambda 函数。

@Nullable
public static JMethod resolveCallee(Type type, Invoke callSite) {
    MethodRef methodRef = callSite.getMethodRef();
    if (callSite.isInterface() || callSite.isVirtual()) 
        return World.get().getClassHierarchy().dispatch(type, methodRef);
    else if (callSite.isSpecial()) 
        return World.get().getClassHierarchy().dispatch(methodRef.getDeclaringClass(), methodRef);
    else if (callSite.isStatic()) 
        return methodRef.resolveNullable();
    else 
        throw new AnalysisException("Cannot resolve Invoke: " + callSite);
}

invoke类型	指令格式	适用场景
InvokeVirtual	invokevirtual Var.MethodRef(ArgList)	实例方法（非 private/static/final））
InvokeInterface	invokeinterface Var.MethodRef(ArgList)	接口中声明的方法
InvokeSpecial	invokespecial Var.MethodRef(ArgList)	构造器、私有方法、父类方法（super）
InvokeStatic	invokestatic MethodRef(ArgList)	静态调用
InvokeDynamic	invokedynamic BootstrapMethodRef MethodName MethodType [BootstrapArgList] (ArgList)	lambda 表达式

语句类型	abstraction	处理函数	规则
FieldLoad	$x=v.f$	processInstanceLoad	$⟨c^{{}^{\prime }},o.f⟩\to ⟨c,x⟩\in \text{PFG},⟨⟨c,x⟩,\text{pts}(⟨c^{{}^{\prime }},o.f⟩)⟩\in \text{WL}\mid \forall ⟨c^{{}^{\prime }},o⟩\in \text{DO}$
FieldStore	$v.f=y$	processInstanceStore	$⟨c,y⟩\to ⟨c^{{}^{\prime }},o.f⟩\in \text{PFG},⟨⟨c^{{}^{\prime }},o.f⟩,\text{pts}(⟨c,y⟩)⟩\in \text{WL}\mid \forall ⟨c^{{}^{\prime }},o⟩\in \text{DO}$
ArrayLoad	$x=v[i]$	processArrayLoad	$⟨c^{{}^{\prime }},o[\ast ]⟩\to ⟨c,x⟩\in \text{PFG},⟨⟨c,x⟩,\text{pts}(⟨c^{{}^{\prime }},o[\ast ]⟩)⟩\in \text{WL}\mid \forall ⟨c^{{}^{\prime }},o⟩\in \text{DO}$
ArrayStore	$v[i]=y$	processArrayStore	$⟨c,y⟩\to ⟨c^{{}^{\prime }},o[\ast ]⟩\in \text{PFG},⟨⟨c^{{}^{\prime }},o[\ast ]⟩,\text{pts}(⟨c,y⟩)⟩\in \text{WL}\mid \forall ⟨c^{{}^{\prime }},o⟩\in \text{DO}$
Call	$r=v.k(a_1,...,a_n)$	processCallEdge, processCall	$⟨⟨c,l⟩,⟨c^t,m⟩⟩\in \text{WL},⟨⟨c^t,m_{\text{this}}⟩,\text{pts}(⟨c,v⟩)⟩\in \text{WL}\mid \forall ⟨c^{{}^{\prime }},o⟩\in \text{DO},m=\text{Dispatch}(\text{Type}(o),l),c^t=\text{Select}(⟨c,l⟩,⟨c^{{}^{\prime }},o⟩)$

对 CallEdgeEntry $⟨⟨c,l⟩,⟨c^t,m⟩$ 的处理在processCallEdge函数中，处理规则包括：

• 1.更新Call Graph：$⟨⟨c,l⟩\to ⟨c^t,m⟩\in \text{CG}$。

• 2.通过addCSMethod函数调用StatementProcessor对 $⟨c^t,m⟩$ 中所有的语句进行分析 (也就是上下文为 $c^t$ 时分析一遍 $m$)，里面调用了Visitor的方法，大致规则如下表所示。需要注意：

  • 在处理多层数组时，会为不同层级的数组建立mock object $o_{\ast }$，并将 $o_{\ast }$ 添加进 $o[\ast ]$ 的指向集，每级以此类推。这里Tai-e在初始化时将 args 的信息添加进 worklist 前会调用 addCSMethod 对 $⟨[],\text{main}⟩$ 调用一次开始 main 函数的分析过程。

  • 在调用 addCSMethod 处理 $⟨c^t,m⟩$ 时，如果是第一次遇到 $m$，那其中 processNewMethod(method) 会调用其它 plugin 会对其进行一些context-insensitve分析。不过个人认为在context-sensitive分析过程，这个步骤更多是为了减少计算开销。

• 3.更新参数和返回值之间的value-flow： $⟨c,a_i⟩\to ⟨c^t,m_{p_i}⟩\in \text{PFG}$, $⟨⟨c^t,m_{p_i}⟩,\text{pts}(⟨c,a_i⟩)⟩\in \text{WL}$, $⟨c^t,m_{\text{ret}}⟩\to ⟨c,r⟩\in \text{PFG}$, $⟨⟨c,r⟩,\text{pts}(⟨c^t,m_{\text{ret}}⟩)⟩\in \text{WL}$。这里不会构造PFG edge $⟨c,v⟩\to ⟨c^t,m_{\text{this}}⟩$，推测是考虑到 $⟨c,l⟩\to ⟨c^t,m⟩$ 是基于object $⟨c^{{}^{\prime }},o⟩\in \text{pts}(⟨c,v⟩)$ 算出来的，因此不适合把 $\text{pts}(⟨c,v⟩)$ 的所有元素丢进 $\text{pts}(⟨c^t,m_{\text{this}}⟩)$。

语句类型	abstraction	规则
New	$x=\text{new}T();$, allocate $o$	$⟨⟨c^t,x⟩,\{⟨c^t,o⟩\}⟩\in \text{WL}$
NewMultiArray	$x=\text{new}T[][][];$ allocate $o$	$⟨⟨c^t,x⟩,\{⟨c^t,o⟩\}⟩\in \text{WL},⟨⟨c^t,o[\ast ]⟩,\{⟨c^t,o_{\ast }⟩\}⟩\in \text{WL}$，$⟨⟨c^t,o_{\ast }[\ast ]⟩,\{⟨c^t,o_{\ast \ast }⟩\}⟩\in \text{WL}$，…
Copy, Cast	$x=y$	$⟨c^t,y⟩\to ⟨c^t,x⟩\in \text{PFG},⟨⟨c^t,x⟩,\text{pts}(⟨c^t,x⟩)⟩\in \text{WL}$
AssignLiteral	$x=c$ ($c$ 为 class 类型不是基础类型)	$⟨⟨c^t,x⟩,\{⟨c^t,o_c⟩\}⟩\in \text{WL}$
StaticLoad	$x=T.f$	$T.f\to ⟨c^t,x⟩\in \text{PFG},⟨⟨c^t,x⟩,\text{pts}(T.f)⟩\in \text{WL}$
StaticStore	$T.f=y$	$⟨c^t,y⟩\to T.f\in \text{PFG},⟨T.f,\text{pts}(⟨c^t,y⟩)⟩\in \text{WL}$
StaticCall	$l:r=T.m(a_1,...,a_n)$	$⟨⟨c^t,l⟩,⟨c^{t_{{}^{\prime }}},m⟩⟩\in \text{WL}\mid c^{t_{{}^{\prime }}}=\text{Select}(c^t,l)$

在具体实现方面，Tai-e中object对应的类型包括NewObj、MockObj、ConstantObj、MergedObj。NewObj 表示 new 操作对应allocation site对应的object，MockObj 在处理数组元素等操作时会用到也可以用来表示taint object、ConstantObj 表示常量对应的object。处理 StaticCall 时，对于object-sensitivity以及type-sensitivity，$c^{t_{{}^{\prime }}}=c^t$；对于context-sensitivity，$c^{t_{{}^{\prime }}}=[c^t;l]$。

3.2.Client

Java指针分析论文常用精度评估指标包括 may-fail-cast、polymorphic-callsite、may-alias-pair。这些定义在analysis.pta.client下

3.2.1.May-Fail-Cast

实现类是MayFailCast。核心代码如下，isRelevant 表明只分析cast语句，算法大概意思是safe cast的条件是 $\text{safe}(l),l:p=(T)q\mid \forall o\in \text{pts}(q),\text{isSubType}(T,\text{Type}(o))$，也就是 $q$ 指向集中所有object的type必须是 $T$ 的子类型才能保证safe cast。数字越小精度越高。

@Override
boolean isRelevant(Stmt stmt) {
   return stmt instanceof Cast;
}

@Override
boolean isWanted(Stmt stmt, PointerAnalysisResult result) {
    Cast cast = (Cast) stmt;
    Type castType = cast.getRValue().getCastType();
    Var from = cast.getRValue().getValue();
    for (Obj obj : result.getPointsToSet(from)) {
       if (!World.get().getTypeSystem().isSubtype(castType, obj.getType())) {
            return true;
       }
    }
    return false;
}

3.2.2.Polymorphic-CallSite

实现类是PolymorphicCallSite，也就是收集所有callee多余1个的virtual callsite集合。数字越大精度越高。

@Override
boolean isRelevant(Stmt stmt) {
    return stmt instanceof Invoke invoke && (invoke.isVirtual() || invoke.isInterface());
}

@Override
boolean isWanted(Stmt stmt, PointerAnalysisResult result) {
    Invoke invoke = (Invoke) stmt;
    return result.getCallGraph().getCalleesOf(invoke).size() > 1;
}

3.3.污点分析

污点分析source、sink、transfer规则定义在commonly-used-taint-config目录下，用户可以在此自定义增加污点传播规则。比如 java.io 和 dropwizard 中能生成taint tag的函数包括

  - { kind: call, method: "<java.io.BufferedReader: java.lang.String readLine()>", index: result, type: "java.lang.String" }
  - { kind: call, method: "<java.io.Console: java.lang.String readLine()>", index: result, type: "java.lang.String" }
  - { kind: call, method: "<java.io.Console: java.lang.String readLine(java.lang.String,java.lang.Object[])>", index: result, type: "java.lang.String" }
  - { kind: call, method: "<java.io.DataInputStream: java.lang.String readLine()>", index: result, type: "java.lang.String" }
  - { kind: call, method: "<java.io.DataInputStream: java.lang.String readUTF()>", index: result, type: "java.lang.String" }
  - { kind: call, method: "<java.io.DataInputStream: java.lang.String readUTF(java.io.DataInput)>", index: result, type: "java.lang.String" }
  - { kind: call, method: "<java.io.LineNumberReader: java.lang.String readLine()>", index: result, type: "java.lang.String" }

  - { kind: param, method: "<io.dropwizard.jersey.filter.AllowedMethodsFilter: void doFilter(jakarta.servlet.ServletRequest,jakarta.servlet.ServletResponse,jakarta.servlet.FilterChain)>", index: 0, type: "jakarta.servlet.ServletRequest" }

transfer API示例包括:

  - { method: "<java.lang.String: int codePointBefore(int)>", from: base, to: result }

  - { method: "<java.lang.String: java.lang.String concat(java.lang.String)>", from: 0, to: result }

  - { method: "<java.lang.String: java.lang.String copyValueOf(char[])>", from: 0, to: result }
  - { method: "<java.lang.String: java.lang.String copyValueOf(char[],int,int)>", from: 0, to: result }

  - { method: "<java.lang.String: java.lang.String format(java.util.Locale,java.lang.String,java.lang.Object[])>", from: 1, to: result }
  - { method: "<java.lang.String: java.lang.String format(java.util.Locale,java.lang.String,java.lang.Object[])>", from: "2[*]", to: result }
  - { method: "<java.lang.String: java.lang.String format(java.lang.String,java.lang.Object[])>", from: 0, to: result }
  - { method: "<java.lang.String: java.lang.String format(java.lang.String,java.lang.Object[])>", from: "1[*]", to: result }

  - { method: "<java.lang.String: byte[] getBytes()>", from: base, to: result }
  - { method: "<java.lang.String: byte[] getBytes(java.nio.charset.Charset)>", from: base, to: result }
  - { method: "<java.lang.String: void getBytes(int,int,byte[],int)>", from: base, to: 2 }
  - { method: "<java.lang.String: byte[] getBytes(java.lang.String)>", from: base, to: result }
  - { method: "<java.lang.String: void getChars(int,int,char[],int)>", from: base, to: 2 }

sink API (比如RCE)包括：

  - { method: "<java.lang.Runtime: java.lang.Process exec(java.lang.String)>", index: 0 }
  - { method: "<java.lang.Runtime: java.lang.Process exec(java.lang.String[])>", index: 0 }
  - { method: "<java.lang.Runtime: java.lang.Process exec(java.lang.String,java.lang.String[])>", index: 0 }
  - { method: "<java.lang.Runtime: java.lang.Process exec(java.lang.String,java.lang.String[])>", index: 1 }

处理污点分析的为TaintAnalysis插件，其内部又会分别调用SourceHandler、TransferHandler、SanitizerHandler、SinkHandler分别根据sources信息生成taint tag、处理额外transfer、以及sanitize操作。

(1).SourceHandler

SourceHandler需要根据规约定义的API信息生成taint tag。taint tag生成包括3种方法，(1).通过call语句污染 base/result 变量、(2).某个函数的某个参数直接引入污点、(3).某个类的某个敏感字段访问：

• 1.Call: 在标准污点分析规则基础上，支持定义 base/result 变量数组元素或者某个字段会被tainted。以 $l:r=v.k(...)$ 的 $r$/$r[\ast ]$/$r.f$ 包含taint tag为例，处理规则如下，对应的逻辑写在SourceHandler::processCallSource中。

包含污点的变量	分析规则
$r$	$⟨⟨c,r⟩,\{⟨[],t_l⟩\}⟩\in \text{WL}$
$r[\ast ]$	$⟨⟨c^{{}^{\prime }},o[\ast ]⟩,\{⟨[],t_l⟩\}⟩\in \text{WL}\mid \forall ⟨c^{{}^{\prime }},o⟩\in \text{pts}(⟨c,r⟩)$
$r.f$	$⟨⟨c^{{}^{\prime }},o.f⟩,\{⟨[],t_l⟩\}⟩\in \text{WL}\mid \forall ⟨c^{{}^{\prime }},o⟩\in \text{pts}(⟨c,r⟩)$

• 2.Param: 如果函数 $m$ 的参数 $m_{p_i}$ 可能会引入污点，那么在指针分析过程中通过 addCSMethod 分析 $⟨c^t,m⟩$ 时最后按下面规则生成污点分析，不过这里考虑到开始 $⟨c^t,m_{p_i}⟩$ 的point-to set为空，Tai-e修改了一下逻辑延迟了数组/字段情况下worklist更新。

包含污点的变量	分析规则
$m_{p_i}$	$⟨⟨c^t,m_{p_i}⟩,\{⟨[],t⟩\}⟩\in \text{WL}$
$m_{p_i}[\ast ]$	$⟨⟨c^{{}^{\prime }},o[\ast ]⟩,\{⟨[],t_l⟩\}⟩\in \text{WL}\mid \forall ⟨c^{{}^{\prime }},o⟩\in \text{pts}(⟨c^t,m_{p_i}⟩)$
$m_{p_i}.f$	$⟨⟨c^{{}^{\prime }},o.f⟩,\{⟨[],t_l⟩\}⟩\in \text{WL}\mid \forall ⟨c^{{}^{\prime }},o⟩\in \text{pts}(⟨c^t,m_{p_i}⟩)$

• (3).Field: 如果字段 $f$(某个类型的)被标记为taint source，那么处理 $⟨c^t,m⟩$ 时有 $⟨⟨c^t,x⟩,\{⟨[],t⟩\}⟩\in \text{WL}\mid \forall l:x=v.f\in m$。

(2).TransferHandler

对于每个context $c$ 下的call $l:r=v.k(a_1,...,a_n)$，调用的CS Method $⟨c^t,m⟩$，分别根据给定的transfer rule算出source变量 $\text{from}$ 以及dest变量 $\text{to}$（base, result 或者某个参数）。一个transfer rule可以简化为 $\text{from}\to \text{to}$ 的形式，其中两边都可能为普通变量（Var）、Array ($\text{from}[\ast ]$, $\text{to}[\ast ]$)、Field（$\text{from}.f$, $\text{to}.f$）。具体操作对应TransferHandler::processTransfer。${\text{pts}}_{\text{taint}}$ 表示只获取point-to set中的taint object，$\stackrel{\text{taint}}{⟶}$ 表示这条PFG edge只传播taint object。

from变量类型	to变量类型	规则
Var	Var	$⟨c,\text{from}⟩\stackrel{\text{taint}}{⟶}⟨c,\text{to}⟩\in \text{PFG},⟨⟨c,\text{to}⟩,{\text{pts}}_{\text{taint}}(⟨c,\text{from}⟩)⟩\in \text{WL}$
Var	Array	$⟨c,\text{from}⟩\stackrel{\text{taint}}{⟶}⟨c^{{}^{\prime }},o[\ast ]⟩\in \text{PFG},⟨⟨c^{{}^{\prime }},o[\ast ]⟩,{\text{pts}}_{\text{taint}}(⟨c,\text{from}⟩)⟩\in \text{WL}\mid \forall ⟨c^{{}^{\prime }},o⟩\in \text{pts}(⟨c,\text{to}⟩)$
Var	Field	$⟨c,\text{from}⟩\stackrel{\text{taint}}{⟶}⟨c^{{}^{\prime }},o.f⟩\in \text{PFG},⟨⟨c^{{}^{\prime }},o.f⟩,{\text{pts}}_{\text{taint}}(⟨c,\text{from}⟩)⟩\in \text{WL}\mid \forall ⟨c^{{}^{\prime }},o⟩\in \text{pts}(⟨c,\text{to}⟩)$
Array	Var	$⟨c^{{}^{\prime }},o[\ast ]⟩\stackrel{\text{taint}}{⟶}⟨c,\text{to}⟩\in \text{PFG},⟨⟨c,\text{to}⟩,{\text{pts}}_{\text{taint}}(⟨c^{{}^{\prime }},o[\ast ]⟩)⟩\in \text{WL}\mid \forall ⟨c^{{}^{\prime }},o⟩\in \text{pts}(⟨c,\text{from}⟩)$
Field	Var	$⟨c^{{}^{\prime }},o.f⟩\stackrel{\text{taint}}{⟶}⟨c,\text{to}⟩\in \text{PFG},⟨⟨c,\text{to}⟩,{\text{pts}}_{\text{taint}}(⟨c^{{}^{\prime }},o.f⟩)⟩\in \text{WL}\mid \forall ⟨c^{{}^{\prime }},o⟩\in \text{pts}(⟨c,\text{from}⟩)$

(3).SanitizerHandler

SanitizerHandler 根据sanitizer rule $⟨m,i⟩$（$i$ 为 base 或者参数索引） 处理 $⟨c^t,m⟩$ 时设置 $⟨c^t,m_{p_i}⟩$ 更新point-to set时不会新增任何taint tag类object。具体操作对应taintFilter。

(4).SinkHandler

对于Sink Rule $⟨m,i⟩$，SinkHandler 处理规则为 $⟨l^{{}^{\prime }},l,i⟩\in \text{TaintFlows}\mid \forall l\to m\in \text{CICG},⟨c,a_i⟩\in \text{retriveCtxVar}(a_i),⟨[],t_{l^{{}^{\prime }}}⟩\in {\text{pts}}_{\text{taint}}(⟨c,a_i⟩)$，这里 $\text{CICG}$ 表示conbtext-insensitive call graph，$l:r=v.k(..,a_i,..)$。这里如果参数指定 array 或者 field ，处理方式类似 TransferHandler 和 SourceHandler ，按下面表格替换部分条件。

Sink规则类型	污点匹配条件
VAR	$⟨[],t_{l^{\prime }}⟩\in {\text{pts}}_{\text{taint}}(⟨c,a_i⟩)$
ARRAY	$⟨[],t_{l^{\prime }}⟩\in {\text{pts}}_{\text{taint}}(⟨c^{\prime },o[\ast ]⟩)\mid \forall ⟨c^{\prime },o⟩\in \text{pts}(⟨c,a_i⟩)$
FIELD	$⟨[],t_{l^{\prime }}⟩\in {\text{pts}}_{\text{taint}}(⟨c^{\prime },o.f⟩)\mid \forall ⟨c^{\prime },o⟩\in \text{pts}(⟨c,a_i⟩)$

总结

相比于标准污点分析规则，Tai-e额外考虑到了指定变量可能为 base 变量的array element或者field访问情况，不过从Tai-e默认source、sink、transfer来看这些复杂情况似乎并没有用到，同时Tai-e目前没有内置sanitize规则，需要用户配置。此外，Tai-e中还有1个TaintFlowGraph类不过看起来并没有用到。

3.4.Lambda分析

lambda 表达式是java函数式编程重要特性，java 代码可通过函数式接口接收lambda表达式，比如 Runnable r = () -> System.out.println("OK");。编译成字节码后如下，可以看到生成了一个 invokedynamic 指令，这个 invokedynamic 比起callsite更像是allocate了一个新的lambda object $o_l$ 并且 $o_l\in \text{pts}(r)$，需要调用的代码写在一个新生成的匿名函数 lambda$main$0 中。

r = invokedynamic
      <java.lang.invoke.LambdaMetafactory: CallSite metafactory(...)> 
      "run" 
      ()Ljava/lang/Runnable; 
      [ MethodType "()V", MethodHandle "<Test: void lambda$main$0()>", MethodType "()V"]
      ()

private static void lambda$main$0()
{
    java.io.PrintStream $r0;
    $r0 = <java.lang.System: java.io.PrintStream out>;
    virtualinvoke $r0.<java.io.PrintStream: void println(java.lang.String)>("hello world");
    return;
}

Tai-e IR中 invokedynamic 的格式为 invokedynamic BootstrapMethodRef MethodName MethodType [BootstrapArgList] (ArgList)。通常如果 BootstrapMethodRef 是 java.lang.invoke.LambdaMetafactory 的 metafactory 或者 altMetafactory 那么就是个lambda object。这里 invokedynamic 的 [BootstrapArgList] 中包含了 lambda$main$0 的信息。在实际运行过程中，后面遇到 r.run() 时会通过 invokeinterface r.run 运行生成的匿名函数。需要注意的是 ArgList 是lambda捕获的参数，Tai-e中处理的lambda包括4种情况，下面例子用 javac --release 8 LambdaCaptureTest.java 编译字节码并用 javap -p -v LambdaCaptureTest > LambdaCaptureTestDecompile.java 获得字节码，或者用 java -jar tai-e-all.jar -cp <path/to/class> -m LambdaCaptureTest -java 8 -a ir-dumper 导出Tai-e IR（这里需要在当前目录下存在子目录 java-benchmarks/JREs/...，可以去Tai-e官网下载）。

• InvokeStatic: 两种情况

  • 没捕获 this 的自定义lambda函数生成的是 static 方法。下面例子 lambda1 对应的匿名方法签名为 private static synthetic java.lang.String lambda$testLambdas$0(java.lang.String r1, java.lang.Integer r3)。对应的 invokedynamic 指令为 invokedynamic ... "apply" ... [REF_invokeStatic]:lambda$testLambdas$0, (r0);，捕获列表包括 r0 也就是 input 。表示最终通过 xx.apply 用 REF_invokeStatic 方式调用匿名静态方法 lambda$testLambdas$0,，传入捕获参数 r0。

  • 方法引用静态函数，下面例子中 lambda5 对应的是 invokedynamic ... "apply" ...[REF_invokeStatic]: <Math:abs>]();，通过 xx.apply 调用静态方法 xx.apply。

• InvokeSpecial: 如果捕获了 this 那么生成的匿名方法非 static 并且 this 一定是捕获列表第1位。下面例子 lambda2 对应的匿名方法签名为 private synthetic java.lang.String lambda$testLambdas$1(java.lang.Integer r4)，对应的 invokedynamic 为 invokedynamic ... "apply" ... [REF_invokeSpecial]:lambda$testLambdas$1](%this);，捕获了 this。表示最终用 REF_invokeSpecial 方式通过 xx.apply 调用 this.lambda$testLambdas$1。

• InvokeVirtual：2种情况

  • 捕获了局部变量或者 this：lambda3 对应指令为 invokedynamic ... "get" ... [REF_invokeVirtual]: <String: toUpperCase()>.String ()](r0);。表示最终通过 xx.get() 用 REF_invokeVirtual 方式调用 r0.toUpperCase。这里捕获列表为 [ r0 ]，后序调用方法的 base 也是 r0。

  • 未捕获变量：lambda4 对应的 invokedynamic 为 invokedynamic "apply" [REF_invokeVirtual]: <String:String toUpperCase()>, String (String)]();，最终需要通过 xx.apply(arg) 的方式调用 arg.toUpperCase()。这里捕获列表为空，后续调用方法为第1个实参。

• newInvokeSpecial：引用构造函数，比如 lambda7，功能上和 lambda6 等价但是 lambda6 依旧会生成一个匿名 static 函数来处理。lambda7 对应的指令为 invokedynamic ... "apply" ... [REF_newInvokeSpecial]: void <init>();，等价于执行了 new + String 构造函数。这里 Function<String, String> 指定了输入1个参数类型为 String 的构造函数。

public class LambdaCaptureTest {
    private String instanceField = "instance";

    public void testLambdas(String input, String input2) {
        // Case 1: Lambda 捕获局部变量（不捕获 this）
        String localVar = input;
        this.instanceField = input2;
        Function<Integer, String> lambda1 = x -> localVar + x; // 只捕获 localVar
        // Case 2: Lambda 捕获 this（通过访问实例字段或方法）
        Function<Integer, String> lambda2 = x -> this.instanceField + x; // 捕获 this
        // Case 3
        Supplier<String> lambda3 = input::toUpperCase;
        // Case 4
        Function<String, String> lambda4 = String::toUpperCase;
        // Case 5: 静态方法引用
        Function<Integer, Integer> lambda5 = Math::abs;
        
        Function<String, StringBuilder> lambda6 = s -> new StringBuilder(s);
        Function<String, String> lambda7 = String::new;
    }
}

Java目前有下面几个典型的函数式接口接收lambda object，同时用户自定义接口 UserInterface 如果只有1个接口方法 foo 那么可以通过 UserInterface u = ... 接收和 UserInterface::foo 签名相同的lambda object。

接口	方法签名	典型用途
java.lang.Runnable	void run()	执行无参无返回的任务（如线程、回调）
java.util.function.Supplier<T>	T get()	提供/生成一个值（延迟初始化、默认值）
java.util.function.Consumer<T>	void accept(T t)	消费或处理一个值（如 forEach）
java.util.function.BiConsumer<T, U>	void accept(T t, U u)	处理两个值
java.util.function.Predicate<T>	boolean test(T t)	条件判断、过滤（如 filter）
java.util.function.Function<T, R>	R apply(T t)	类型转换、映射（如 map）
java.util.function.UnaryOperator<T>	T apply(T t)	同类型输入输出的转换
java.util.function.BinaryOperator<T>	T apply(T t1, T t2)	同类型聚合操作（如求和、取最大值）

Tai-e中Lambda分析对应插件LambdaAnalysis，它会识别 invokedynamic 的导引方法是否在处理范围内，具体比较是否是LAMBDA_METAFACTORY或者LAMBDA_ALTMETAFACTORY，也就是 LambdaMetafactory.metafactory 和 LambdaMetafactory.altMetafactory，其它类型的不在lambda分析范围内。lambda的分析规则对应LambdaAnalysis::onNewCSMethod以及LambdaAnalysis::onUnresolvedCall。对于lambda调用，示例中会通过 r.run 调用，在指针分析过程中，DefaultSolver::processCall中对于 Runnable r = () -> System.out.Println("") 有 $⟨c^{{}^{\prime }},o_l⟩\in \text{pts}(⟨c,r⟩)$，而调用 CallGraphs.resolveCallee 分析 $o_l$ 时其类型为 Runnable 但是没找到实现的方法因此 callee == null，此时会分析 $⟨c^{{}^{\prime }},o_l⟩$ 解析 $o_l$ 中启动的方法（也就是 $\text{Func}(o_l)$）确定callee。这里lambda生成的一定是 private 方法因此不需要复杂的动态分配。

JMethod callee = CallGraphs.resolveCallee(recvObj.getObject().getType(), callSite);
if (callee != null) ...
else
    plugin.onUnresolvedCall(recvObj, context, callSite);

对于context $c$ 下的 invokedynamic $l:r=\text{invokedynamic},\text{func}$ 以及后续调用 $l:\text{res}=r.\text{apply}(a_1,...,a_n)$ 简化大致如下表所示（假设当前上下文为 $c$），

语句类型	分析规则	说明
InvokeDynamic	$⟨⟨c,r⟩\{⟨c,o_l⟩\}⟩\in \text{WL}$	$o_l$ 为新生成的lambda object，对应 MockObj，同时里面保存了具体执行的匿名函数 $\text{func}$ 的信息。
InvokeStatic	$⟨⟨c,l⟩,⟨c^t,m⟩\in \text{WL}\mid \forall ⟨c^{{}^{\prime }},o_{l^{{}^{\prime }}}⟩\in \text{pts}(⟨c,r⟩),m=\text{Func}(o_{l^{{}^{\prime }}}),c^t=\text{Select}(⟨c,l⟩)$	$r$ 为lambda receiver，$o_{l^{{}^{\prime }}}$ 为lambda object，$\text{Func}(o_{l^{{}^{\prime }}})$ 为 $o_{l^{{}^{\prime }}}$ 对应的静态函数，比如 lambda$main$0。
InvokeSpecial	$⟨⟨c,l⟩,⟨c^t,m⟩\in \text{WL},⟨⟨c^t,m_{this}⟩,\{⟨c^{{}^{\prime \prime }},o_t⟩\}⟩\in \text{WL}\mid \forall ⟨c^{{}^{\prime }},o_{l^{{}^{\prime }}}⟩\in \text{pts}(⟨c,r⟩),m=\text{Func}(o_{l^{{}^{\prime }}}),\forall ⟨c^{{}^{\prime \prime }},o_t⟩\in \text{pts}(⟨c^{{}^{\prime }},m_{\text{this}}⟩),c^t=\text{Select}(⟨c,l⟩,⟨c^{{}^{\prime \prime }},o_t⟩)$	在lambda表达式捕获 this 的情况下生成的匿名方法是 private 非 static 的，因此调用时需要考虑 base 变量是 this。不过 private 方法不需要考虑动态分配。
InvokeVirtual - 捕获局部变量或 this	$⟨⟨c,l⟩,⟨c^t,m⟩⟩\in \text{WL},⟨⟨c^t,m_{\text{this}}⟩,\{⟨c^{{}^{\prime \prime }},o_{v_c}\}⟩⟩\in \text{WL}\mid \forall ⟨c^{{}^{\prime }},o_{l^{{}^{\prime }}}⟩\in \text{pts}(⟨c,r⟩),\forall ⟨c^{{}^{\prime \prime }},o_{v_c}⟩\in \text{pts}(⟨c^{{}^{\prime }},v_c⟩),m=\text{Dispatch}(\text{Type}(o_{v_c}),l^{{}^{\prime }}),c^t=\text{Select}(⟨c,l⟩,⟨c^{{}^{\prime \prime }},o_{v_c}⟩)$	方法引用且捕获了变量，比如 r = obj.foo，此时callee的 base 变量为 obj，也就是捕获列表第一个参数 $v_c$，捕获变量的context通常和 invokedynamic 处一致。
InvokeVirtual - 未捕获变量	$⟨⟨c,l⟩,⟨c^t,m⟩⟩\in \text{WL}⟨⟨c^t,m_{\text{this}}⟩,\{⟨c^{{}^{\prime \prime }},o_{a_0}\}⟩⟩\in \text{WL}\mid \forall ⟨c^{{}^{\prime }},o_{l^{{}^{\prime }}}⟩\in \text{pts}(⟨c,r⟩),\forall ⟨c^{{}^{\prime \prime }},o_{a_0}⟩\in \text{pts}(⟨c,a_0⟩),m=\text{Dispatch}(\text{Type}(o_{a_0}),l^{{}^{\prime }}),c^t=\text{Select}(⟨c,l⟩,⟨c^{{}^{\prime \prime }},o_{a_0}⟩)$	方法引用且未捕获变量，比如 r = Type::foo，此时callee的 base 变量为第1个实参 $a_0$捕获变量的context通常就是callsite处context $c$。
newInvokeSpecial	$⟨⟨c,\text{res}⟩,\{⟨c,o_m⟩\}⟩\in \text{WL},⟨⟨c,l⟩,⟨c^t,m⟩⟩\in \text{WL},⟨⟨c^t,m_{\text{this}}⟩,\{⟨c,o_m⟩\}⟩\in \text{WL}\mid m=\text{Dispatch}(l^{{}^{\prime }}),c^t=\text{Select}(⟨c,l⟩,⟨c,o⟩)$	该处新allocate了一个heap object同时调用其构造函数 $m$。$\text{Dispatch}(l^{{}^{\prime }})$ 表示根据 invokedynamic 语句 $l^{{}^{\prime }}$ 处的信息解析调用的是哪个类的哪个构造函数。

在指针分析处理 CallEdgeEntry 时，DefaultSolver::processCallEdge 最终通过 plugin.onNewCallEdge(edge); 处理 lambdaCallEdge 而不是在主分析类中进行。对于lambda调用，其输入的实参为 InvokeDynamic.ArgList（捕获参数）+ InvokeVirtual.ArgList（实际参数），两类参数的context变量不同。因此LambdaAnalysis::onNewCallEdge根据这些构建捕获参数和实参到callee参数的PFG Edge。

在处理 PointerEntry $⟨⟨c,v⟩,\text{DO}⟩$ 时，表示lambda函数的 this 对象 ($⟨c,v⟩$) 可能有新的object被添加进指向集，LambdaAnalysis::onNewPointsToSet此时需要根据新添加的对象增加新的 lambdaCallEdge，不过这里应该只影响 $c^t=\text{Select}(c,l,⟨c^{{}^{\prime \prime }},o_t⟩)$，也就是不会增加reachable method只是在更多context下调用匿名函数。

3.5.其它分析

这里简单提一下Tai-e中实现了但是默认没开启的分析插件。

(1).InvokeDynamic分析

invokedynamic 在 lambda 中相当于分配了一个object辅助回调，不过用途不止 lambda ，包括但不限于下面。InvokeDynamicAnalysis主要对 MethodHandle 的API而Java9StringConcatHandler主要分析字符串拼接，不过 MethodHandle 貌似主要在框架库中用到而在用户代码中很少用以及Tai-e目前支持的jdk版本在3-8不涉及Java 9就不深入了。

用途	说明
Lambda 表达式和方法引用	Java 8+编译器将 lambda 编译为 invokedynamic + LambdaMetafactory
字符串拼接（Java 9+）	"a" + b + "c" 被编译为 invokedynamic 调用 StringConcatFactory.makeConcatWithConstants
动态语言调用	JRuby、Nashorn等通过 indy 实现方法查找和调用
手动使用 MethodHandle	开发者直接使用 MethodHandles API 构造动态调用

(2).反射分析

Tai-e通过ReflectionAnalysis插件进行反射分析，实现的算法包括StringConstant分析以及Solar ${}^{[3]}$。在Solar paper中，作者拿了3个桌面应用：javac-1.7.0、jEdit-5.1.0、Eclipse-4.2.2，2个服务中间件 Jetty-9.0.5、Tomcat-7.0.42 以及11个Dacapo benchmark中的程序，分析 java.lang.reflect、java.lang.Class 下191个反射API的使用情况。发现:

• 1.newInstance() 和 invoke() 是绝对主流，前者占有46.3%反射调用，后者32.7%。

• 2.静态成员的反射调用非常普遍，不可忽视。在所有 invoke() 调用点中，平均有37%是在调用静态方法。在所有 get()/set() 调用点中，平均有50%是在访问或修改静态字段。

• 3.仅靠字符串常量和强制转换是远远不够的，需要利用更丰富的上下文信息（即“自推断属性”）。在所有使用字符串参数来指定反射目标的调用点中，平均只有49%使用了字符串常量。这意味着超过一半的情况下，字符串分析会失效。28% 的 newInstance() 调用点没有可以用于推断类型的“过程内后支配强制转换”（intra-procedural post-dominating casts）。

• 4.返回成员数组的方法（如 getMethods()），虽然调用频次不高，但影响深远，忽略它们会导致分析结果在关键应用上严重失准。具体来说，在对两个Eclipse程序的研究中发现：有4个 invoke() 调用点作用于 getMethods() 返回的方法数组上，从而触发了数十个方法的调用。有15个 fld.get() 和 fld.set() 调用点作用于 getDeclaredFields() 返回的字段数组上，从而访问或修改了数百个字段。

不过上面Java程序都属于工具型/框架型/基础设施类程序，严格意义上不算应用型程序（比如Spring App），实际上App业务代码很少用到反射。因此在App分析中反射的分析价值不高，这里暂时不考虑。

参考文献

[1].Tian Tan and Yue Li. 2023. Tai-e: A Developer-Friendly Static Analysis Framework for Java by Harnessing the Good Designs of Classics. In Proceedings of the 32nd ACM SIGSOFT International Symposium on Software Testing and Analysis (ISSTA 2023). Association for Computing Machinery, New York, NY, USA, 1093–1105.

[2].Neville Grech and Yannis Smaragdakis. 2017. P/Taint: unified points-to and taint analysis. Proc. ACM Program. Lang. 1, OOPSLA, Article 102 (October 2017), 28 pages.

[3].Yue Li, Tian Tan, and Jingling Xue. 2019. Understanding and Analyzing Java Reflection. ACM Trans. Softw. Eng. Methodol. 28, 2, Article 7 (April 2019), 50 pages.