状态流图（State Flow Graph）¶

污点分析是漏洞检测中常用的分析技术，其执行依赖于程序语义分析的结果。在语义分析阶段，系统已经计算出了符号、内存对象抽象及其之间的指向与依赖关系。污点跟踪在传播与路径查询过程中需要直接使用这些语义结果，因此有必要将其组织为统一的结构化表示。基于此，引入状态流图SFG（State Flow Graph），用于表达与数据传播相关的语义关系。

状态流图不引入新的语义推导规则，其作用是对已有语义分析结果进行统一建模。这些结果包括指令级的定义与使用关系、数据流分析得到的可达性信息，以及指针分析产生的符号状态。状态流图作为中间表示，为污点传播与路径查询提供直接的图结构支持。

1 状态流图的构成¶

状态流图由节点和边组成，用于描述符号、内存状态与指令之间的关系。

状态流图包含以下几类节点：

符号节点（Symbol）：表示程序中的变量、函数参数、返回值等符号实体；
状态节点（State）：表示符号在语义分析阶段对应的内存对象抽象；
指令节点（Stmt）：表示具体的程序指令，用于标识数据产生和使用的位置。

状态流图中的边用于刻画节点之间的语义关系，主要包括：

引用边：表示某条指令使用了某个符号或状态；
定义边：表示某条指令对符号或状态进行了定义或更新；
符号状态关联边：表示符号与其在语义分析阶段对应的状态集合之间的关联关系；
符号流边：表示符号之间由于赋值、参数传递或返回值形成的数据依赖关系；
状态复制边：表示在语义分析过程中，由状态复制策略产生的新旧状态之间的关联关系。

2 示例¶

考虑如下示例程序：

def main():
    a = A()
    b = a.g
    foo(a)
    sink(b.f)

def foo(z):
    x = z.g
    w = source()
    x.f = w

main()

在该程序中，a与z在函数调用过程中形成别名关系。字段g的访问导致多个符号指向同一状态，而在foo中对x.f的赋值会影响main中对b.f的读取。

在语义分析阶段，LIAN已计算出符号之间的指向关系及其对应的内存对象抽象。状态流图在此基础上，将这些结果组织为图结构，用以表达：

a与z之间的符号依赖关系；
a.g、z.g、b与x所对应状态之间的共享关系；
source()产生的数据如何经由状态更新传播至sink(b.f)。

根据上述程序构建的状态流图如下所示：

在该状态流图中，可以从source()对应的状态节点出发，沿符号流边、状态复制边以及指令相关边，得到一条到达sink 调用点的数据传播路径。该图结构允许从源节点出发，通过图遍历直接枚举可能的数据传播路径，用于支持污点传播分析与路径回溯。