P2: 从下而上语义分析（Bottom-up Semantic Analysis）¶

在本阶段，Lian程序分析框架进行细粒度、从下而上（bottom-up）的语义分析，包括数据流分析和指向关系分析。该阶段的核心目标是，在不依赖类型信息的前提下，精确刻画程序中数据流与指向关系，为后续的跨函数分析、污点跟踪与安全建模提供高质量的语义基础。

本阶段由core/prelim_semantics模块完成，由PreliminaryAnalysis.run()驱动，所需要的输入包括GIR语句和上一阶段“基础结构性分析”得到的结果。

1 主要思路¶

1-1 总体流程¶

本阶段采用从下而上的语义分析策略，其基本流程分为两步：1）以函数为基本分析单元，对每个函数独立进行语义分析，计算其语义摘要（summary）；2）沿函数调用关系逐步向上合成，将被调用函数（callee）的语义摘要引入调用者函数（caller）的语义分析中。

该策略的核心思想在于优先刻画局部、可复用的函数语义，再逐步向上构建完整的行为理解。这种设计有以下几个重要考量：

首先，所有函数都会被分析，包括潜在的“死代码”函数。在传统程序分析中，常通过调用图剪枝排除不会被调用的函数，但这一策略在现实系统中并不总是可靠。由于高阶函数、动态属性访问、反射机制以及第三方库调用的广泛存在，静态分析在判断“函数是否可达”时往往存在偏差。一旦误判并忽略某些函数，将对后续分析的完整性与可扩展性造成不可逆影响。因此，Lian在本阶段不依赖调用可达性作为语义前提，而是对所有可解析函数构建保守的局部语义摘要。这些摘要是否在最终程序语义中生效，由后续分析阶段决定。

其次，将函数视为独立分析单元，有助于抽象出与调用位置无关的语义信息。

[01] f(int a) {
[02]    int b = a;
[03]    return b;
[04] }

该函数表达的语义是“返回其输入参数”，这一结论与其调用位置无关，具备高度复用价值。

当然，这一假设并非总是成立。当函数引用外部环境（如this、全局变量、隐式对象或间接调用目标）时，其语义将不可避免地依赖于具体调用上下文。例如：

f(A a) {
    a.speak();
}

在这种情况下，a.speak()的实际行为取决于a的运行时指向对象。

本阶段的目标并非完全解决此类问题，而是尽可能提取可稳定复用的函数语义。剩余依赖调用上下文的语义，将在后续“从上而下”的分析阶段进一步处理。

1-2 gen/kill算法¶

gen/kill算法已在过去大量数据流分析中充分体现其有效性，其对无类型语言分析来说是同样适用的。因此，Lian系统沿用gen/kill算法进行数据流分析。不仅局限于此，Lian还将gen/kill算法应用到了指向集合的分析中，取得了非常好的效果。

Gen/Kill算法是经典数据流分析中的核心机制，已在大量程序分析系统中验证了其有效性。该算法并不依赖强类型假设，因此同样适用于动态语言和弱类型语言场景。在Lian中，Gen/Kill算法不仅用于符号级数据流分析，还被扩展应用于指向关系（points-to set）的演化分析。通过在不同层次上采用Gen/Kill思路，Lian能够在保持分析可控性的同时，获得较高的精度。

1-3 SSA分析策略的取舍¶

静态单赋值形式（SSA）在编译优化和依赖分析中具有重要价值，能够高效刻画变量级的数据依赖关系。然而，在Lian的目标场景中，SSA并非万能，其局限性主要体现在以下方面：

首先，SSA 难以自然支持字段敏感分析。例如：

[01] x.f = 1;
[02] x.f = 2;
[03] c = x.f;

对于第三句[03]来说，x的f字段的依赖关系难以应用SSA结果进行分析和理解。类似问题在数组元素访问、动态属性访问中尤为突出。

其次，从表达能力上看，SSA在很多场景下与经典数据流分析是等价的。因此，在二者只能择其一的情况下，Lian更倾向于以数据流分析作为核心语义建模机制，并在此基础上融合指向关系分析。

1-4 指向关系分析¶

指向关系分析（Points-to Analysis）是解决动态语言复杂行为的关键技术，对属性访问、间接调用等场景尤为重要，例如

对于属性访问z = x[y]，如果能够知道x和y的指向集，可以推断出x的具体数据类型（可能是数组、对象），以及y的类型（可能是int和string）和取值，从而计算z的指向集；
对于间接调用z = x(y)，如果能够知道x的指向集，则可以按需（on-the-fly）分析潜在的被调用函数，推断参数个数、参数指向集以及返回值语义；这一机制同样适用于对象方法调用z = x.f(y)。

若缺乏指针分析支持，对于静态语言尚可借助编译器类型信息近似推断调用目标，但在动态语言中，被调用函数往往在运行时才能确定，传统类型驱动的方法难以奏效。因此，不依赖于类型系统的指针分析在此类场景中至关重要。

1-5 指针分析和污点分析之间的关系¶

在Lian中，指针分析不仅用于解决别名与调用分派问题，其结果还被直接复用于污点跟踪分析。指针分析的结果是变量到内存对象抽象的映射，而这些内存对象抽象同样可以作为污点传播的载体。

以赋值语句为例，如x = y，x的指向集为y的指向集。当y被打上污点了后，y的指向集内部的内存对象也可以被打上污点标记。当这条语句被分析后，x的指向集也会被更新，x的指向集的指向对象也会被打上污点标记。推而广之，对于其他语句，如x.f = y，类似机制同样适用。

因此，在Lian的设计中，指针分析是语义分析阶段的核心能力，也是高精度污点分析得以实现的基础。

1-6 指针分析的精度目标¶

指针分析是Lian程序分析框架的焦点，其具体精度目标包括：

上下文敏感：对于本阶段的分析来说，其采用摘要summary的方式达成上下文敏感分析；对于下一阶段从上而下分析来说，则采用1-CallSite精度。
流敏感：通过可达性定义分析识别语句执行顺序对指向关系的影响；
字段敏感：显式建模对象属性与数组元素的依赖关系。

2 语义分析Preliminary Analysis¶

2-1 基本定义¶

符号（Symbol）：程序中所有的标识符，如变量、函数、类、属性、数组元素等。
内存对象抽象（Abstract Memory Object）：符号在运行时可能对应的内存实体抽象，包含地址、语句ID、类型、值、字段与数组元素等信息；
状态（State）：符号到内存对象抽象集合的映射关系（symbol → {memory objects}）。
可达定义（reaching Definition）：在当前语句位置仍然有效的符号定义及其对应的内存对象抽象。

2-2 函数摘要（Method Summary）¶

函数摘要（Method Summary）用于描述函数在输入与输出两个维度上的语义行为：

输入：函数对外界环境的依赖，包括函数的参数、外部变量引用等；
输出：函数对外部环境产生的影响，包括函数的返回值、外部变量修改等。

在本阶段，函数的所有输入被统一抽象为anything。其中，anything表示当前抽象域上的上界元素（abstract top），用于在信息不足时维持语义分析的保守性，而非引入额外假设。通过函数内语义分析，逐步计算其输出行为。当callee的摘要被应用于caller时，只需将摘要中的anything替换为caller语境下的真实内存对象抽象即可。

为支持摘要计算，引入函数帧（Method Frame），用于记录函数分析过程中涉及的输入、状态与中间结果。

2-3 分析流程¶

语义分析以函数为基本单元，按以下顺序逐步展开： - 不存在任何函数调用语句的函数（methods with no callee） - 包含直接函数调用语句的函数（methods with direct callee）：这里的直接调用是指，可以直接通过函数名变量ID直接定位到被调用的函数； - 包含间接函数调用语句的函数（methods with indirect callee）：这里的间接调用是指，无法通过函数名变量ID确定被调用的函数。

对每个函数，初始化函数帧，并对其控制流图中的每一条语句进行分析。整体流程如下：

输入：函数GIR语句、基础结构性分析结果
输出：函数摘要summary

Worklist = [first stmt of method CFG]
while Worklist ≠ ∅:
    // 获取一条语句
    stmt = Worklist.pop()

    // 分析这条语句中可用的symbol def
    reaching_symbol_defs = analyze_reaching_symbols(stmt)

    // 分析这条语句的指向关系
    compute_stmt_states(stmt, reaching_symbol_defs)

    // 上述语句分析是不是改变了符号定义（例如函数调用），进行更新
    update_reaching_defs(stmt)

    // 检查这条语句是不是在symbol层面或者在state方面发生了变化
    if is_changed(symbol, states) or first_round:
        Worklist = Worklist ∪ succ(stmt)

2-4 符号层面的可达性定义分析¶

analyze_reaching_symbols()在符号层面实现经典的Gen/Kill算法，用于计算每条语句处可达的符号定义。其详细原理可参考数据流分析章节中关于定义可达性分析的说明。

update_reaching_defs()用于处理指针分析带来的隐式影响，典型场景包括函数调用。当被调用函数引用或修改外部符号时，需要相应更新当前语句的符号使用与定义集合。

2-5 指向关系分析¶

compute_stmt_states()函数计算了每一条语句对指向关系的变化。

流敏感分析¶

[01] x.f = 1;  
[02] x.f = 2; 
[03] c = x.f

以上述代码为例，[01]语句中x的内存对象抽象为{fields: {f: 1}}；[02]语句中x的内存对象抽象变化为{fields: {f: 2}}；[03]语句中x的指向集为{fields: {f: 2}}。如果是流不敏感的分析，那么[03]语句中x的指向集为{fields: {f: {1, 2}}}，增加了误报。如果流敏感分析，能够得到正确结果。

为此，Lian在内存对象抽象层面引入基于可达定义的状态选择机制，确保每次字段读取都能关联到最新有效的状态定义。在[03]是得到被使用的符号是x及其字段f，需要计算当前x的最新状态，找到其最新的状态定义是在[02]，因此x的指向集为{fields: {f: 2}}。

状态复制和强更新¶

在上述例子中，在缺乏精确别名判定的前提下，直接采用强更新容易在分支和合流场景中引入不一致，尤其是在处理分支的时候。由于本阶段未引入SSA形式，为避免强更新在分支场景下带来的不一致性，Lian采用状态复制策略，即创建一个副本，将副本的状态中修改，而源状态保持不变。该状态复制机制并非对SSA的替代，而是工作在内存对象抽象层面，用于表达字段与别名相关的语义演化，这是SSA在变量层面难以直接刻画的。

由此而引发了一个如何区别源状态和副本状态的问题，这通过内存对象抽象层面的可达性分析决定的。

状态计算¶

针对一条指令的指向关系分析具体流程如下：

输入：待被分析的GIR指令stmt、基础结构性分析结果、符号层可达定义
输出：指令相关指向关系

// 根据这条语句中可用的符号定义，收集对应的所有的状态
symbol_states = collect_newest_states(reaching_symbol_defs)

// 检查是否有符号没有对应的状态，如果有进行填充
complete_in_states(symbol_states)

// 准备好所有的输入符号及其内存状态后，计算指令的state变化
// 具体对于每条指令的state的变化，由`core/stmt_states.py`完成
run_stmt_state_analysis()

// 计算完成后，检查有哪些新的状态生成了，如果有新状态生成，需要更新状态层的可达性定义
adjust_computation_results()

函数摘要应用¶

在callee函数摘要生成以后，会被应用到caller函数中。这种应用的过程使用core/stmt_states.py中的call_stmt实现的：

收集所有被用到的符号，并收集这些可达符号的最新状态；
摘要作为模版来使用，将最新状态替换模版中的anything，实现函数摘要实例化；
将实例化后的摘要作为新的状态，更新caller函数语义。