如何实现VTA算法并结合Soot、Spark为Java程序构建调用图？

一、VTA算法核心实现逻辑 #

VTA（Variable-Type Analysis）是上下文不敏感的基于类型的指针分析算法，精度高于CHA、执行效率高于RTA，核心实现步骤如下：

• 预计算类型层次结构：提前遍历所有待分析类的继承、接口实现关系，生成类型到其子类型集合的映射表Map<RefType, Set<RefType>> subtypeMap
• 定义核心数据结构：
  • 变量到类型集合的映射表Map<Local, Set<RefType>> varTypeMap，存储每个局部变量可能的类型
  • 实例字段到类型集合的映射表Map<SootField, Set<RefType>> fieldTypeMap，存储每个类字段可能的类型
  • 调用点到目标方法集合的映射表Map<InvokeExpr, Set<SootMethod>> callTargetMap，存储每个调用点的所有可行目标方法
• 迭代执行类型传播：
  1. 初始化阶段扫描所有new语句，将新创建的对象类型加入对应接收变量的类型集合
  2. 扫描所有赋值语句x = y，将y的所有类型合并到x的类型集合，若x的类型集合出现新增项，触发所有依赖x的赋值语句的二次传播
  3. 处理字段操作：x = y.f场景下将y类型集合对应类的f字段的所有类型合并到x的类型集合；x.f = y场景下将y的所有类型合并到对应f字段的类型集合
  4. 循环迭代直到所有变量、字段的类型集合不再发生变化
• 计算调用点目标：对每个虚拟调用点x.m(参数)，遍历x的类型集合，查找每个类型中签名匹配的方法，去重后加入该调用点的目标集合。

二、Soot中集成VTA并结合Spark生成调用图 #

Soot的Spark是内置的全程序指针分析框架，支持自定义分析规则扩展，集成步骤如下：

• 第一步：配置Soot基础运行环境

Options.v().set_src_prec(Options.src_prec_class);
// 填入待分析Java程序的class文件所在目录
Options.v().set_process_dir(Arrays.asList("./target/classes"));
Options.v().set_whole_program(true);
Options.v().set_allow_phantom_refs(true);
// 启用Spark指针分析框架
Options.v().set_spark(true);
Scene.v().loadNecessaryClasses();

• 第二步：扩展Spark的PAG（指针赋值图）适配VTA规则
  重写Spark默认的指向关系传播逻辑，将原本的分配位点传播替换为类型集合传播，关闭Spark默认的上下文敏感开关，避免不必要的性能开销。
• 第三步：注册自定义调用图构建器
  实现Soot的CallGraphBuilder接口，基于VTA生成的callTargetMap遍历所有程序调用点，将调用点和目标方法的关联边加入Soot全局CallGraph实例，替换Soot默认的CHA/RTA调用图构建器。
• 第四步：执行分析获取调用图
  触发全程序分析后，通过Scene.v().getCallGraph()即可获取VTA生成的调用图，可按需导出为DOT、文本等格式。

小提示：如果不需要完全自主实现VTA，可直接开启Spark内置的类型指针分析开关Options.v().set_type_based_points_to(true)，其逻辑与VTA基本一致，可直接生成符合VTA规则的调用图，无需从零编写传播逻辑。

内容的提问来源于stack exchange，提问作者user16921896