本文主要是介绍【静态分析】软件分析课程实验A4-类层次结构分析与过程间常量传播,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
官网:作业 4:类层次结构分析与过程间常量传播 | Tai-e
参考:https://www.cnblogs.com/gonghr/p/17984124
-----------------------------------------------------------------------
1 作业导览
- 为 Java 实现一个类层次结构分析(Class Hierarchy Analysis,CHA)。
- 实现过程间常量传播。
- 实现过程间数据流传播的 worklist 求解器。
在本次实验作业中,你将在 Tai-e 的基础之上为 Java 实现一个基于类层次结构(下面简称为 CHA)的调用图(call graph)构造器。接着为了展现它的用处,你需要依靠你实现的调用图实现一个过程间常量传播分析。此外,为了使得你的过程间常量传播能够正常运行,你还需要实现一个 worklist 求解器来支持过程间数据流分析(虽然在软件分析课程中,我们并没有教过你实现过程间分析的具体方法,但是不必担心,通过本次作业,你会掌握相关的知识和实现方法)。
本次作业的分析范围和第二次作业是一致的,也就是说你仍然只需要考虑针对 int
类型变量的常量传播,只不过在本次作业中,你需要更准确地处理方法调用。如果你的实现是正确的,那么在实验的最后你就可以发现:与保守处理方法调用的过程内常量传播相比,过程间常量传播可以达到更好的精度。
idea打开实验作业仓库的 A4/tai-e/,并按
【静态分析】软件分析课程实验-前置准备-CSDN博客进行配置。
2 实现类层次结构分析(CHA)
在本次作业中,你需要处理 Java 语言的四种方法调用:invokestatic
、invokespecial
、invokeinterface
和 invokevirtual
(详情见【静态分析】静态分析笔记05 - 过程间分析-CSDN博客)。当然,Java 中的一些新特性会让方法调用的情形更复杂:比如 Java 8 开始允许接口定义非抽象方法(default methods
);还有从 Java 11 开始,invokeinterface
和 invoke-virtual
可以调用 private 方法了。这都会使我们构建调用图的过程变得更复杂。而简单起见,你并不需要在本次作业中处理这些改动。
2.1 Tai-e 中你需要了解的类
本次作业中,有一些类包含了很多 API。为了减轻你的压力,我们将会介绍一些你可能会用到的相关的类和 API。我们将以自顶到下的方式来介绍这些类,也就是说,我们会首先介绍构建调用图的关键类(DefaultCallGraph),紧接着介绍与它相关的其他类。
-
pascal.taie.analysis.graph.callgraph.DefaultCallGraph
该类代表了程序的调用图。它提供了多样的 API(继承自类
AbstractCallGraph
)来获取到调用图的信息。另外,它还提供了一些修改调用图的 API,你可以借此来建立调用图。Stream<Invoke> callSitesIn(JMethod)
:返回给定方法JMethod
中的所有call sites
。boolean contains(JMethod)
: 返回当前调用图是否含有给定的方法,即给定方法JMethod
在当前调用图中是否可达。boolean addReachableMethod(JMethod)
: 向当前调用图中添加方法JMethod
并将方法标记成可达的。boolean addEdge(Edge<Invoke,JMethod>)
: 向当前调用图中添加一条调用边。
-
pascal.taie.analysis.graph.callgraph.CallKind
该枚举类型表示调用图中边的种类,包括
INTERFACE
、VIRTUAL
、SPECIAL
和STATIC
,它对应第 7 讲中介绍过的 Java 的四种调用类型(call kind)。 -
pascal.taie.analysis.graph.callgraph.Edge<Invoke,JMethod>
该类表示调用图中的边。每一条边从调用点(call site,Tai-e 中为
Invoke
类型)出发,指向被调用方法(callee method,类型为JMethod
)。在创建一条边的时候,你需要向构造方法提供调用类型、调用点和被调用方法的信息。 -
pascal.taie.ir.stmt.Invoke
(subclass ofStmt
)该类表示程序中的方法调用(举个例子:
x = o.m(a1,a2,…)
)以及调用图中的调用点。它提供了一些 API 来获取调用点的各种信息。明确一点:你需要使用getMethodRef()
来获取目标方法的签名信息。 -
pascal.taie.ir.proginfo.MethodRef
Tai-e 中的目标方法引用,如调用点的目标方法。它包含了调用点所调用的目标方法的签名信息。
JClass getDeclaringClass()
:返回该方法签名的声明类,即声明该方法的类。(也就是class type);Subsignature getSubsignature()
:返回被调用方法的子签名(subsignature
)。稍后我们回来介绍子签名类——Subsignature
。
对
MethodRef
,在本次作业中你只需要使用上面提到的两个 API。 -
pascal.taie.language.classes.JMethod
该类表示 Tai-e 中的 Java 方法。每个
JMethod
的实例关联着一个方法并包含该方法的各种信息。boolean isAbstract()
: 如果该JMethod
是一个没有方法体的抽象方法,则返回true
,否则返回false
;
-
pascal.taie.language.classes.JClass
该类表示 Tai-e 中的 Java 类。每个
JClass
的实例关联着一个类并包含该类的各种信息。JClass getSuperClass()
: 返回该类的父类。如果这个类在类层次结构的顶端(没有父类),比如java.lang.Object
,则返回null
。JMethod getDeclaredMethod(Subsignature)
: 根据子签名返回该类中声明的对应方法。如果该类中没有该子签名对应的方法,则返回null
。boolean isInterface()
: 返回该类是否是一个接口。
-
pascal.taie.language.classes.Subsignature
该类表示 Tai-e 中的子签名。一个方法的子签名只包含它的方法名和方法签名的描述符。举个例子,下面方法 foo 的子签名是:“
T foo(P,Q,R)
” ,而它的完整签名是:“<C: T foo(P,Q,R)>
”。class C {T foo(P p, Q q, R r) { … } }
pascal.taie.language.classes.ClassHierarchy
该类提供了类层次结构的相关信息。
Collection<JClass> getDirectSubclassesOf(JClass)
: 对于给定类,返回直接继承该类的子类。Collection<JClass> getDirectSubinterfacesOf(JClass)
: 对于一个给定接口,返回直接继承该接口的子接口。Collection<JClass> getDirectImplementorsOf(JClass)
: 对于一个给定接口,返回直接实现了该接口的类。
举个例子,在下面的 class hierarchy 中,I, II, III 是接口,其他均为类:
-
那么
getDirectSubclassesOf(A) = [B]
getDirectSubinterfacesOf(I) = [II, III]
getDirectImplementorsOf(II) = [E]
-
pascal.taie.analysis.graph.callgraph.CHABuilder
这个类通过 CHA 来建立调用图。目前该类是不完整的,你将会在第 2.2 节的讲解和帮助下完成它。
2.2 你的任务 [重点!]
你的第一个任务是完成 CHABuilder
类。你需要完成以下三个 API:
-
JMethod dispatch(JClass,Subsignature)
该方法实现了
Dispatch方法,
根据方法调用者的类和方法签名寻找目标方法。 -
特别地,如果找不到满足要求的方法,返回
null
。 -
比较显然,是个递归算法。
递归的终止条件有两个,一个是如果一直找不到相应方法,不断递归到父类,最后递归到
Object
在向上递归就是null
,Object
没有父类,此时返回空,说明找不到相应方法;另一个是如果当前类的方法中有能匹配方法签名的方法,并且该方法不是抽象方法,说明找到相应方法,返回该方法。其他情况向当前类的父类递归。
-
Set<JMethod> resolve(Invoke)
该方法实现了
Resolve
方法, 通过类的继承关系确定一个调用点的所有可能的目标方法。
-
提示:
你可以使用
CallGraphs.getCallKind(Invoke)
来获得调用点的调用类型。
-
CallGraph<Invoke, JMethod> buildCallGraph(JMethod)
该方法实现了
BuildCallGraph
算法, 代码中DefaultCallGraph
既是个调用图CG
,也能记录哪些方法访问过,即RM。
我们提供了上述 3 个 API 的代码框架。你的任务是填写所有标有注释 “TODO – finish me
” 的部分。
/** Tai-e: A Static Analysis Framework for Java** Copyright (C) 2022 Tian Tan <tiantan@nju.edu.cn>* Copyright (C) 2022 Yue Li <yueli@nju.edu.cn>** This file is part of Tai-e.** Tai-e is free software: you can redistribute it and/or modify* it under the terms of the GNU Lesser General Public License* as published by the Free Software Foundation, either version 3* of the License, or (at your option) any later version.** Tai-e is distributed in the hope that it will be useful,but WITHOUT* ANY WARRANTY; without even the implied warranty of MERCHANTABILITY* or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General* Public License for more details.** You should have received a copy of the GNU Lesser General Public* License along with Tai-e. If not, see <https://www.gnu.org/licenses/>.*/package pascal.taie.analysis.graph.callgraph;import pascal.taie.World;
import pascal.taie.ir.proginfo.MethodRef;
import pascal.taie.ir.stmt.Invoke;
import pascal.taie.language.classes.ClassHierarchy;
import pascal.taie.language.classes.JClass;
import pascal.taie.language.classes.JMethod;
import pascal.taie.language.classes.Subsignature;import java.util.ArrayDeque;
import java.util.Queue;
import java.util.Set;import java.util.*;
import java.util.stream.Stream;/*** Implementation of the CHA algorithm.*/
class CHABuilder implements CGBuilder<Invoke, JMethod> {private ClassHierarchy hierarchy;@Overridepublic CallGraph<Invoke, JMethod> build() {hierarchy = World.get().getClassHierarchy();return buildCallGraph(World.get().getMainMethod());}private CallGraph<Invoke, JMethod> buildCallGraph(JMethod entry) {DefaultCallGraph callGraph = new DefaultCallGraph();callGraph.addEntryMethod(entry);// TODO - finish meArrayDeque<JMethod> worklist = new ArrayDeque<>();worklist.addLast(entry);while (!worklist.isEmpty()) {JMethod m = worklist.pollFirst();if (!callGraph.contains(m)) {callGraph.addReachableMethod(m);Stream<Invoke> invokeStream = callGraph.callSitesIn(m);invokeStream.forEach(cs -> {for (JMethod targetMethod : resolve(cs)) {if (targetMethod != null) {callGraph.addEdge(new Edge<>(CallGraphs.getCallKind(cs), cs, targetMethod));worklist.addLast(targetMethod);}}});}}return callGraph;}/*** Resolves call targets (callees) of a call site via CHA.*/private Set<JMethod> resolve(Invoke callSite) {// TODO - finish meSet<JMethod> T = new HashSet<JMethod>(); // 调用点的所有可能的目标方法集合MethodRef m = callSite.getMethodRef();Subsignature subsignature = m.getSubsignature(); // 函数签名JClass declaringClass = m.getDeclaringClass(); // 调用点声明类型// CallKind - INTERFACE、VIRTUAL、SPECIAL、STATICCallKind callKind = CallGraphs.getCallKind(callSite); // 函数调用类型switch (callKind) {case STATIC -> { // T = {该调用点声明类型的方法}T.add(declaringClass.getDeclaredMethod(subsignature));break;}case SPECIAL -> { // dispatch递归查找父类T.add(dispatch(declaringClass, subsignature));break;}case VIRTUAL, INTERFACE -> { // 根据声明类型,对该类和该类的所有子类dispatchArrayDeque<JClass> subclasses = new ArrayDeque<>();HashSet<JClass> set = new HashSet<>();subclasses.addLast(declaringClass);set.add(declaringClass);while (!subclasses.isEmpty()) {JClass subclass = subclasses.pollFirst();T.add(dispatch(subclass, subsignature));for (JClass jClass : (hierarchy.getDirectSubclassesOf(subclass))) {if (!set.contains(jClass)) {set.add(jClass);subclasses.addLast(jClass);}}for (JClass jClass : (hierarchy.getDirectSubinterfacesOf(subclass))) {if (!set.contains(jClass)) {set.add(jClass);subclasses.addLast(jClass);}}for (JClass jClass : (hierarchy.getDirectImplementorsOf(subclass))) {if (!set.contains(jClass)) {set.add(jClass);subclasses.addLast(jClass);}}}break;}}return T;}/*** Looks up the target method based on given class and method subsignature.** @return the dispatched target method, or null if no satisfying method* can be found.*/private JMethod dispatch(JClass jclass, Subsignature subsignature) {// TODO - finish meif (jclass == null) {return null;}if (jclass.getDeclaredMethod(subsignature) != null && !jclass.getDeclaredMethod(subsignature).isAbstract()) {return jclass.getDeclaredMethod(subsignature);}return dispatch(jclass.getSuperClass(), subsignature);}
}
3 实现过程间常量传播
3.1 Edge Transfer
过程间常量传播和过程内常量传播很像。它们的主要区别是:过程间常量传播使用了 edge transfer,因此能够更准确地处理方法调用和返回所产生的过程间数据流。
举一个前向分析的例子,在传统的过程内数据流分析中,如果我们想计算一个节点的IN fact,我们可以直接meet该节点的全部前驱的OUT fact:
然而,在过程间数据流分析中,为了计算一个节点的 IN fact,我们需要先对该节点的前驱的 OUT fact 应用 edge transfer,然后把得到结果 meet 进该节点的 IN fact。
举个例子,这是第 7 讲中出现过的一个 ICFG:
为了计算第 4 条语句的 IN fact,也就是方法 addOne()
的 entry 节点的 IN fact,我们需要对 2→4 这条边应用 edge transfer,这样使得第 2 条语句的 OUT fact(a=6)转换为 x=6,并最终 meet 结果 x=6 到第四条语句的 IN fact中。
我们定义了 transferEdge(edge, fact)
函数来实现 edge transfer。它以 ICFG 中的一条边(对应参数 edge)和边的源节点的 OUT fact(对应参数fact)为输入,并输出经transfer计算之后的结果fact。据此,我们把计算IN fact的转换函数调整为:
我们曾在第 7 讲中提到过,在过程间常量传播中,transfer edge 需要处理的边被分为以下四种:
- Normal edge: 这种边一般是与过程间调用无关的边,edge transfer 函数不需要对此进行特殊的处理。这种边上的 fact 经 transfer edge 之后不会有任何改变。换句话说,此时 edge transfer 是一个恒等函数,即 transferEdge(edge, fact) = fact。
- Call-to-return edge: 对于方法调用
x = m(…)
,edge transfer 函数会把等号左侧的变量(在这个例子里也就是x
)和它的值从 fact 中 kill 掉。而对于等号左侧没有变量的调用,比如m(…)
,edge transfer 函数的处理方式与对待 normal edge 的一致:不修改 fact,edge transfer 是一个恒等函数。 - Call edge: 对于这种边,edge transfer 函数会将实参(argument)在调用点中的值传递给被调用函数的形参(parameter)。具体来说,edge transfer 首先从调用点的 OUT fact 中获取实参的值,然后返回一个新的 fact,这个 fact 把形参映射到它对应的实参的值。举个例子,在图 1 里,transferEdge(2→4, {a=6}) = {x=6}。此时,edge transfer 函数的返回值应该仅包含被调用函数的形参的值(比如图 1 里,
addOne()
的x
)。 - Return edge: edge transfer 函数将被调用方法的返回值传递给调用点等号左侧的变量。具体来说,它从被调用方法的 exit 节点的 OUT fact 中获取返回值(可能有多个,你需要思考一下该怎么处理),然后返回一个将调用点等号左侧的变量映射到返回值的 fact。举个例子,在图1中,transferEdge(6→3, {x=6,y=7}) = {b=7}。此时,edge transfer 函数返回的结果应该仅包含调用点等号左侧变量的值(例如图1在第三条语句处的b)。如果该调用点等号左侧没有变量,那么 edge transfer 函数仅会返回一个空 fact。
在接下来的章节,我们将会向你介绍更多关于如何在 Tai-e 中实现上述这些 edge transfer 函数的信息。
3.2 Tai-e 中你需要了解的类
-
pascal.taie.analysis.graph.icfg.ICFGEdge
该类是一个抽象类,它表示了 ICFG 中的边。而它有四个子类,分别关联着上一节中提到的四种 ICFG 边:
Normal Edge
、CallToReturnEdge
、CallEdge
、ReturnEdge
:pascal.taie.analysis.graph.icfg.NormalEdge
pascal.taie.analysis.graph.icfg.CallToReturnEdge
pascal.taie.analysis.graph.icfg.CallEdge
pascal.taie.analysis.graph.icfg.ReturnEdge
这些类都非常简单易懂并且有详尽的注释,请好好阅读源码来认识它们吧。
-
pascal.taie.analysis.dataflow.inter.InterDataflowAnalysis
这是一个过程间数据流分析的接口。它总共有 6 个API。它的前 5 个 API 都与过程内数据流分析
DataflowAnalysis
的相同,所以如果需要,你可以翻看此前的作业手册再次认识它们。而它的最后一个 API 就是transferEdge()
,也就是我们在第 3.1 节中介绍的 edge transfer 函数。这 6 个 API将被过程间数据流分析的求解器调用,而你的任务就是利用这些 API 实现这个求解器。 -
pascal.taie.analysis.dataflow.inter.AbstractInterDataflowAnalysis
该抽象类实现了
InterDataflowAnalysis
,并为InterDataflowAnalysis
的实现提供了一些基本的功能。说得明白一点,它把 ICFG 中不同的点和边分派给对应 transfer 方法。这样一来,我们的分析的实现就可以分别处理各类的点和边。 -
pascal.taie.analysis.dataflow.inter.InterConstantPropagation
该类继承自
AbstractInterDataflowAnalysis
,并且定义了过程间常量传播。但是它还是不完整的。你需要根据第 3.3 节的描述完成它。 -
pascal.taie.ir.exp.InvokeExp
该类表示程序中的方法调用表达式。它包含了被调用的方法引用和传入的各个参数。具体的细节和如何使用,需要你阅读源码和相关注释来了解。
3.3 你的任务 [重点!]
你的第二个任务是完成 InterConstantPropagation
的这些 API:
boolean transferCallNode(Stmt,CPFact,CPFact)
boolean transferNonCallNode(Stmt,CPFact,CPFact)
CPFact transferNormalEdge(NormalEdge,CPFact)
CPFact transferCallToReturnEdge(CallToReturnEdge,CPFact)
CPFact transferCallEdge(LocalEdge,CPFact)
CPFact transferReturnEdge(LocalEdge,CPFact)
InterConstantPropagation
类包含了一个 ConstantPropagation
类的字段:cp
,这使得你可以利用过程内常量传播实现的逻辑。但是ConstantPropagation.java
目前还和以前一样没有实现完全,所以,为了防止你的过程间常量分析罢工,你首先需要补全 ConstantPropagation.java
。你可以从你此前已经完成的作业中复制代码,并粘贴到本次作业中。
提示:
- 你在实现
transfer*Edge()
方法的时候,不应该修改第二个参数,也就是该边的源节点的 OUT fact。- 我们在第二次作业中介绍过,你可以从 IR 类中获取方法的参数,且可以使用 API
JMethod.getIR()
来获取一个方法的 IR。
/** Tai-e: A Static Analysis Framework for Java** Copyright (C) 2022 Tian Tan <tiantan@nju.edu.cn>* Copyright (C) 2022 Yue Li <yueli@nju.edu.cn>** This file is part of Tai-e.** Tai-e is free software: you can redistribute it and/or modify* it under the terms of the GNU Lesser General Public License* as published by the Free Software Foundation, either version 3* of the License, or (at your option) any later version.** Tai-e is distributed in the hope that it will be useful,but WITHOUT* ANY WARRANTY; without even the implied warranty of MERCHANTABILITY* or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General* Public License for more details.** You should have received a copy of the GNU Lesser General Public* License along with Tai-e. If not, see <https://www.gnu.org/licenses/>.*/package pascal.taie.analysis.dataflow.inter;import pascal.taie.analysis.dataflow.analysis.constprop.CPFact;
import pascal.taie.analysis.dataflow.analysis.constprop.ConstantPropagation;
import pascal.taie.analysis.graph.cfg.CFG;
import pascal.taie.analysis.graph.cfg.CFGBuilder;
import pascal.taie.analysis.graph.icfg.CallEdge;
import pascal.taie.analysis.graph.icfg.CallToReturnEdge;
import pascal.taie.analysis.graph.icfg.NormalEdge;
import pascal.taie.analysis.graph.icfg.ReturnEdge;
import pascal.taie.config.AnalysisConfig;
import pascal.taie.ir.IR;
import pascal.taie.ir.exp.InvokeExp;
import pascal.taie.ir.exp.Var;
import pascal.taie.ir.stmt.Invoke;
import pascal.taie.ir.stmt.Stmt;
import pascal.taie.language.classes.JMethod;import pascal.taie.ir.exp.LValue;
import pascal.taie.analysis.dataflow.analysis.constprop.Value;/*** Implementation of interprocedural constant propagation for int values.*/
public class InterConstantPropagation extendsAbstractInterDataflowAnalysis<JMethod, Stmt, CPFact> {public static final String ID = "inter-constprop";private final ConstantPropagation cp;public InterConstantPropagation(AnalysisConfig config) {super(config);cp = new ConstantPropagation(new AnalysisConfig(ConstantPropagation.ID));}@Overridepublic boolean isForward() {return cp.isForward();}@Overridepublic CPFact newBoundaryFact(Stmt boundary) {IR ir = icfg.getContainingMethodOf(boundary).getIR();return cp.newBoundaryFact(ir.getResult(CFGBuilder.ID));}@Overridepublic CPFact newInitialFact() {return cp.newInitialFact();}@Overridepublic void meetInto(CPFact fact, CPFact target) {cp.meetInto(fact, target);}@Overrideprotected boolean transferCallNode(Stmt stmt, CPFact in, CPFact out) {// TODO - finish mereturn out.copyFrom(in);}@Overrideprotected boolean transferNonCallNode(Stmt stmt, CPFact in, CPFact out) {// TODO - finish mereturn cp.transferNode(stmt, in, out);}@Overrideprotected CPFact transferNormalEdge(NormalEdge<Stmt> edge, CPFact out) {// TODO - finish mereturn out;}@Overrideprotected CPFact transferCallToReturnEdge(CallToReturnEdge<Stmt> edge, CPFact out) {// TODO - finish meCPFact copy = out.copy();if (edge.getSource().getDef().isPresent()) { // 检查edge.getSource()中是否有变量被定义LValue lValue = edge.getSource().getDef().get();if (lValue instanceof Var lVar) {copy.remove(lVar);}}return copy;}@Overrideprotected CPFact transferCallEdge(CallEdge<Stmt> edge, CPFact callSiteOut) {// TODO - finish meCPFact newCPFact = newInitialFact();JMethod callee = edge.getCallee(); // 被调用方法Stmt source = edge.getSource();if (source instanceof Invoke invoke) { // 检查source是否是一个方法调用InvokeExp invokeExp = invoke.getRValue();for (int i = 0; i < invokeExp.getArgCount(); i++) {Var actual = invokeExp.getArg(i); // 获取实参变量Value value = callSiteOut.get(actual); // 获取实参值Var formal = callee.getIR().getParam(i); // 获取形参变量newCPFact.update(formal, value);}}return newCPFact;}@Overrideprotected CPFact transferReturnEdge(ReturnEdge<Stmt> edge, CPFact returnOut) {// TODO - finish meCPFact newCPFact = newInitialFact();Stmt callSite = edge.getCallSite();if (callSite.getDef().isPresent()) {Value value = Value.getUndef(); // 累积从方法返回的所有可能值for (Var returnVar : edge.getReturnVars()) { // 遍历所有返回变量value = cp.meetValue(value, returnOut.get(returnVar));}LValue lValue = callSite.getDef().get();if (lValue instanceof Var lVar) {newCPFact.update(lVar, value);}}return newCPFact;}
}
4 实现过程间 Worklist 求解器
4.1 算法
过程间 worklist
求解器所使用的算法和你在第二次作业中实现的过程内worklist
求解器的算法大体上是一样的。它们仅有两处不同:
- 在第 3.1 节介绍过,在计算一个节点的 IN fact 时,过程间求解器需要对传入的 edge 和前驱们的 OUT facts 应用 edge transfer 函数(transferEdge)。
- 在初始化的过程中,过程间求解器需要初始化程序中所有的 IN/OUT fact,也就是 ICFG 的全部节点。但你仅需要对 ICFG 的 entry 方法(比如 main 方法)的 entry 节点设置 boundary fact。这意味着其他方法的 entry 节点和非 entry 节点的初始 fact 是一样的。
4.2 Tai-e 中你需要了解的类
-
pascal.taie.analysis.dataflow.fact.DataflowResult
你已经在此前的作业中见过这个类了。在本次作业中,你将会使用一个
DataflowResult
对象来管理 ICFG 中所有节点的 fact。通过使用该类中的 API,你可以获取或设置 ICFG 中各个节点的 IN/OUT fact。 -
pascal.taie.analysis.graph.icfg.ICFG
该类代表的是程序的过程间控制流图。与 CFG 相似,它也是可迭代的(iterable),所以你可以利用 for 循环来迭代 ICFG 的所有节点:
ICFG icfg = ...;
for (Node node : icfg) {...
}
-
关于 ICFG 的更多信息,请阅读源码和有关注释。
-
pascal.taie.analysis.dataflow.inter.InterSolver
该类是过程间数据流分析的求解器。它目前是不完整的,需要你根据第 4.3 节的说明来完成它。
4.3 你的任务 [重点!]
终于,这是你最后的任务了——完成 InterSolver
的两个 API:
void initialize()
void doSolve()
同样,你只需要实现前向分析的求解器,因为过程间常量分析就是前向的。你需要在 initialize()
中初始化 ICFG 节点的 IN/OUT fact,还需要在 doSolve()
中实现 worklist 算法的主要部分。
提示:
我们已经为待求解的分析、程序的 ICFG 和管理 fact 的
DataflowResult
创建了对象,并且把它们分别存在了InterSolver
类的analysis
、icfg
和result
字段里。这样,你可以很轻易地访问和操作这些对象。
/** Tai-e: A Static Analysis Framework for Java** Copyright (C) 2022 Tian Tan <tiantan@nju.edu.cn>* Copyright (C) 2022 Yue Li <yueli@nju.edu.cn>** This file is part of Tai-e.** Tai-e is free software: you can redistribute it and/or modify* it under the terms of the GNU Lesser General Public License* as published by the Free Software Foundation, either version 3* of the License, or (at your option) any later version.** Tai-e is distributed in the hope that it will be useful,but WITHOUT* ANY WARRANTY; without even the implied warranty of MERCHANTABILITY* or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General* Public License for more details.** You should have received a copy of the GNU Lesser General Public* License along with Tai-e. If not, see <https://www.gnu.org/licenses/>.*/package pascal.taie.analysis.dataflow.inter;import pascal.taie.analysis.dataflow.fact.DataflowResult;
import pascal.taie.analysis.graph.icfg.ICFG;
import pascal.taie.util.collection.SetQueue;import java.util.Queue;
import java.util.Set;
import java.util.stream.Collectors;import pascal.taie.analysis.graph.icfg.*;
import java.util.*;/*** Solver for inter-procedural data-flow analysis.* The workload of inter-procedural analysis is heavy, thus we always* adopt work-list algorithm for efficiency.*/
class InterSolver<Method, Node, Fact> {private final InterDataflowAnalysis<Node, Fact> analysis;private final ICFG<Method, Node> icfg;private DataflowResult<Node, Fact> result;private Queue<Node> workList;InterSolver(InterDataflowAnalysis<Node, Fact> analysis,ICFG<Method, Node> icfg) {this.analysis = analysis;this.icfg = icfg;}DataflowResult<Node, Fact> solve() {result = new DataflowResult<>();initialize();doSolve();return result;}private void initialize() {// TODO - finish mefor (Node node : icfg) {result.setInFact(node, analysis.newInitialFact());result.setOutFact(node, analysis.newInitialFact());}icfg.entryMethods().forEach(method -> {Node entryOf = icfg.getEntryOf(method);result.setOutFact(entryOf, analysis.newBoundaryFact(entryOf));result.setInFact(entryOf, analysis.newBoundaryFact(entryOf));});}private void doSolve() {// TODO - finish meworkList = new ArrayDeque<>();for (Node node : icfg) {workList.add(node);}while (!workList.isEmpty()) {Node node = workList.poll();for (ICFGEdge<Node> nodeICFGEdge : icfg.getInEdgesOf(node)) { // 对于当前节点的每一条入边// fact - analysis.transferEdge(nodeICFGEdge, result.getOutFact(nodeICFGEdge.getSource()))// target - result.getInFact(node)analysis.meetInto(analysis.transferEdge(nodeICFGEdge, result.getOutFact(nodeICFGEdge.getSource())), result.getInFact(node));}boolean f = analysis.transferNode(node, result.getInFact(node), result.getOutFact(node));if (f) {workList.addAll(icfg.getSuccsOf(node));}}}
}
5 运行与测试
你可以用 Tai-e 框架(教学版)配置指南 中介绍的方法来运行分析算法。本次作业中,Tai-e 首先运行 CHA 来创建程序的调用图,然后根据调用图构建 ICFG,最后在 ICFG 上运行过程间常量传播分析。为了方便调试,Tai-e 会将 CHA 和过程间常量分析的结果都输出到控制台。
#reachable methods: 0
----------Reachable methods:----------
#call graph edges: 0
----------Call graph edges:----------
----------------------------------------
--------------------<Example: void <init>()> (inter-constprop)--------------------
[0@L1] invokespecial %this.<java.lang.Object: void <init>()>(); null
[1@L1] return; null
--------------------<Example: void main(java.lang.String[])> (inter-constprop)--------------------
[0@L5] a = 6; null
[1@L6] temp$1 = invokestatic <Example: int addOne(int)>(a); null
[2@L6] b = temp$1; null
[3@L7] %intconst0 = 3; null
[4@L7] c = b - %intconst0; null
[5@L8] temp$3 = invokestatic <Example: int ten()>(); null
[6@L8] b = temp$3; null
[7@L9] c = a * b; null
[8@L9] return; null
--------------------<Example: int addOne(int)> (inter-constprop)--------------------
[0@L13] %intconst0 = 1; null
[1@L13] y = x + %intconst0; null
[2@L14] return y; null
--------------------<Example: int ten()> (inter-constprop)--------------------
[0@L17] temp$0 = 10; null
[1@L18] return temp$0; null
上面的例子已经在第 7 讲中介绍过。因为当前你还没有实现作业要求完成分析,所以此时该分析的调用图为空(没有任何的可达方法)并且 OUT fact 均为 null
。
而当你完成了这些分析之后,输出应当形如:
#reachable methods: 3
----------Reachable methods:----------
<Example: int addOne(int)>
<Example: int ten()>
<Example: void main(java.lang.String[])>
#call graph edges: 2
----------Call graph edges:----------
<Example: void main(java.lang.String[])>[1@L6] temp$1 = invokestatic <Example: int addOne(int)>(a); -> [<Example: int addOne(int)>]
<Example: void main(java.lang.String[])>[5@L8] temp$3 = invokestatic <Example: int ten()>(); -> [<Example: int ten()>]
----------------------------------------
--------------------<Example: void main(java.lang.String[])> (inter-constprop)--------------------
[0@L5] a = 6; {a=6}
[1@L6] temp$1 = invokestatic <Example: int addOne(int)>(a); {a=6}
[2@L6] b = temp$1; {a=6, b=7, temp$1=7}
[3@L7] %intconst0 = 3; {%intconst0=3, a=6, b=7, temp$1=7}
[4@L7] c = b - %intconst0; {%intconst0=3, a=6, b=7, c=4, temp$1=7}
[5@L8] temp$3 = invokestatic <Example: int ten()>(); {%intconst0=3, a=6, b=7, c=4, temp$1=7}
[6@L8] b = temp$3; {%intconst0=3, a=6, b=10, c=4, temp$1=7, temp$3=10}
[7@L9] c = a * b; {%intconst0=3, a=6, b=10, c=60, temp$1=7, temp$3=10}
[8@L9] return; {%intconst0=3, a=6, b=10, c=60, temp$1=7, temp$3=10}
--------------------<Example: int addOne(int)> (inter-constprop)--------------------
[0@L13] %intconst0 = 1; {%intconst0=1, x=6}
[1@L13] y = x + %intconst0; {%intconst0=1, x=6, y=7}
[2@L14] return y; {%intconst0=1, x=6, y=7}
--------------------<Example: int ten()> (inter-constprop)--------------------
[0@L17] temp$0 = 10; {temp$0=10}
[1@L18] return temp$0; {temp$0=10}
另外,Tai-e 会将它所分析程序的 ICFG 输出到目录 output/
下。ICFG 被保存为可以使用 Graphviz 可视化的 .dot
格式。
使用 dot -Tpng xxx.dot -O 命令即可将.dot 文件转换为 png 来查看
注意,每个 ICFG 都是基于一个调用图构建的,所以一旦你修改了 CHABuilder
,那么即使分析同一个程序,Tai-e 也可能会输出不同的 ICFG。
我们已经提供了 pascal.taie.analysis.graph.callgraph.cha.CHATest
和 pascal.taie.analysis.dataflow.analysis.constprop.InterCPTest
作为 CHA 和过程间常量传播的测试驱动类。如 Tai-e 框架(教学版)配置指南 所介绍,你可以使用它们来测试你代码的正确性。
在本次作业中,你实现的分析是过程间分析。过程间分析会从入口方法来分析整个程序,也就是 main
方法。所以,请确保被分析的类有一个 main
方法:public static void main(String[])
。
设置入口方法文件:Tai-e-assignments-main\A4\tai-e\src\main\java\pascal\taie\analysis\graph\callgraph\CHABuilder.java
这篇关于【静态分析】软件分析课程实验A4-类层次结构分析与过程间常量传播的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!