Page 220 - 《软件学报》2026年第7期

毛祥煜 等: 面向 Web 应用漏洞检测的多数据流静态分析方法 2905

分析方法决定. 举例而言, 对于 IFDS 分析框架 [32] , 有 τ(E,V) ∼ O(ED ), 其中 D 代表数据流值域集合大小, 传统污
3
V
2
2
点分析场景下满足 D = 2 ; 对基于有限格 (lattice) 的数据流不动点迭代分析算法 [33] , 则有 τ(E,V) ∼ O(Eh ) ∼ O(EV ),
h 为格的高度. 如第 3.3 节中所述, MultiFlow 采用基于抽象语法树遍历的分析策略, 忽略循环、递归等代码
其中
结构中的控制流回边, 将代码控制流处理为有向无环图结构, 在分析复杂度上可实现 τ(E,V) ∼ O(E +V). 前述实验
结果表明, 在 Web 应用安全领域中使用该分析策略, 可在不损失过多检测精确度的条件下显著提高分析效率, 适
用于工业级大规模应用场景.
● 敏感操作检测阶段. 对所有污染节点执行污点汇模式匹配判断是否为敏感操作, 匹配次数上界为 S sink V t .
当规则规模相对固定时, V t ≪ V, 由此得到传统污点分析复杂度上界表示为:
S source 和 S sink 可视为常数, 且
O(S source V +τ(E,V)+S sink V t ) = O(V +τ(E,V)) (9)
对于 MultiFlow, 代入得到其传统污点分析模式的时间复杂度上界为 O(E +V).
5.2.2 多段数据流分析
对于多段数据流分析算法, 其主要的额外分析开销来源于针对共享数据存储/读取操作的迭代分析过程. 而迭
代过程遵循增量分析思想, 不会重复分析先前已有结果, 故最终可在有限程序内实现收敛.
设算法迭代总轮次数为 n, 漏洞规则中配置的共享数据存储模式数量为 S store , 以下详细推导其时间复杂度.
在第 i 轮迭代中, 使用的污点源模式数量为 s i , 识别到污染可达的共享数据存储操作数量为 . 考虑到共享数
w i
w i−1 ≪ V t ; 每个轮次中的共享数据存储操作将被映射至共享数据读取模式, 并
据存储操作在程序中的实际分布, 有
在去重后作为下一迭代轮次的污点源, 因此有:



s 1 = S source

(10)

 s i ⩽ w i−1 , 1 < i ⩽ n

由此可以得到污点源匹配总次数上界满足:

 
n−1
n ∑ ∑
 
   
s i V ⩽  S source + w iV ≪ (S source +nV t )V (11)

 
i=1 i=1
对于污点传播追踪, 单个迭代轮次的时间开销仍为 τ(E,V). 此外, 在每个轮次迭代中, 将逐一验证该轮次的污
n ∑
染语句集合 V t i 是否为敏感操作或符合共享数据存储模式, 由 V t = V t i , 可知总匹配次数满足:

i=1
n ∑
(12)
< n(S sink +S store )V t
(S sink +S store )V t i
i=1
综合上述结果, 可得到 MultiFlow 多段数据流分析的时间复杂度表示:

O((S source +nV t )V +nτ(E,V)+n(S sink +S store )V t ) = O(V t ·V +nE) (13)
即算法开销与迭代轮次数 n 直接相关. 在实际分析中, n 通常为较小值, 即多段数据流分析算法可在常数轮次内实
现快速收敛.
5.2.3 多标签数据流分析
对于多标签数据流分析算法, 其额外分析开销来源于将单一类型污点扩展到多类型污点后的污染变量集合维
护, 以及增强的传播条件与漏洞条件谓词分析步骤.
k, 其各个阶段时间复杂度推导过程如下.
设多标签数据流分析漏洞规则中配置的污染标签数量为
● 污点源匹配阶段. 由公式 (1) 可知 |S source | ⩽ kS source , 同第 5.2.1 节的分析, 得多标签污点源匹配次数上界为
kS source V ; 在实际分析场景中, 绝大多数污点源模式仅关联单个污染标签, 即 |S source | ∼ S source .
● 污点传播追踪阶段. 该阶段中, 若考虑对每条语句与不同污染标签均进行组合的极端情况, 则等价于为每个
污染标签独立执行一次污点传播追踪, 总开销为 kτ(E,V); 实际分析场景中, 除跨类型污染传播谓词外, 不同污染标
签均执行独立传播, 且程序中的多数污染语句或变量仅关联单个污染标签, 可认为污染传播步骤的分析开销仍为
τ(E,V).