前言 之前学习过tai-e的污点分析功能,不是很好用,现在学习一下基础的指针分析功能,看看能不能自己搞污点分析模块。
要搞这里的练习,最好先读一下网站上的课件文档,了解一下它的程序分析设计思路。
环境搭建 搭建IDEA+Java17的代码环境,然后打开Tai-e课程作业 ,去tai-e作业仓库 下载待分析的Java项目,再使用IDEA打开A1任务。
在Setting中搜索Gradle,将Build and run using和Run tests using这两栏内容改为IDEA,再继续构建测试项目。
下载gradle-7.4-bin.zip时遇到了问题connect timeout,打算更换国内镜像的时候又可以正常下载了,那就不管了,解决方法参考gradle8.0或者其他版本下载太慢或者time out超时(完美解决方法) 和gradle:Connection timed out 问题解决 。
A1 A1名为活跃变量分析和迭代求解器,用于判断一个变量v的值在程序执行路径中是否会被使用。
作业测试机制分析 按照作文文档所说,项目入口点为Assignment类里面调用的Main.main函数:
1 Usage: - cp <CLASS_PATH> - m <CLASS_NAME>
可以在程序运行参数里填入待分析类路径和待分析类名。
但看了后面的作业内容,发现作业的运行和结果校验用的不是这个Assignment类,而是JUnit测试框架,找到项目里的测试类LiveVarTest:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 public class LiveVarTest { void testLV (String inputClass) { Tests.test(inputClass, "src/test/resources/dataflow/livevar" , LiveVariableAnalysis.ID, "strongly:false" ); } @Test public void testAssign () { testLV("Assign" ); } @Test public void testBranch () { testLV("Branch" ); } @Test public void testBranchLoop () { testLV("BranchLoop" ); } @Test public void Array () { testLV("Array" ); } @Test public void Fibonacci () { testLV("Fibonacci" ); } @Test public void Reference () { testLV("Reference" ); } }
6个Test标注的测试方法对应的就是src/test/resources/dataflow/livevar目录下面的6个测试用的待分析类以及期望的分析结果,JUnit会对比得到的输出结果和期望的分析结果,并打印结果不一致的地方。
比如待分析文件Array.java:
1 2 3 4 5 6 7 8 9 10 11 class Array { int sum (int arr[]) { int result = 0 ; for (int i = 0 ; i < arr.length; i++) { result += arr[i]; } return result; } }
它的期望分析结果就是Array-livevar-expected.txt:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 -------------------- <Array: void <init>()> (livevar) -------------------- [0 @L1 ] invokespecial %this. <java.lang.Object: void <init>()>() [1 @L1 ] return -------------------- <Array: int sum(int[])> (livevar) -------------------- [0 @L4 ] result = 0 [1 @L5 ] i = 0 [2 @L5 ] nop [3 @L5 ] temp$0 = arr.length [4 @L5 ] if (i < temp$0 ) goto 6 [5 @L5 ] goto 13 [6 @L5 ] nop [7 @L6 ] temp$4 = arr[i] [8 @L6 ] result = result + temp$4 [9 @L6 ] nop [10 @L5 ] %intconst0 = 1 [11 @L5 ] i = i + %intconst0 [12 @L5 ] goto 2 [13 @L5 ] nop [14 @L8 ] return result
每一个测试方法都会走到testLV函数,再进入Tests.test方法,可以看到其中也调用了Main.main方法进行tai-e指针分析,因此直接在IDEA中运行LiveVarTest类就可以开始测试,得到全错的检查结果:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 java.lang.AssertionError: Mismatches of analysis "livevar": <Array : void <init>()> [0 @L1] invokespecial %this.<java.lang.Object : void <init>()>(); expected: [], given: null <Array : void <init>()> [1 @L1] return ; expected: [], given: null <Array : int sum(int [])> [0 @L4] result = 0 ; expected: [arr, result], given: null <Array : int sum(int [])> [1 @L5] i = 0 ; expected: [arr, i, result], given: null <Array : int sum(int [])> [2 @L5] nop; expected: [arr, i, result], given: null <Array : int sum(int [])> [3 @L5] temp $0 = arr.length; expected: [arr, i, result, temp $0 ], given: null <Array : int sum(int [])> [4 @L5] if (i < temp $0 ) goto 6 ; expected: [arr, i, result], given: null <Array : int sum(int [])> [5 @L5] goto 13 ; expected: [result], given: null <Array : int sum(int [])> [6 @L5] nop; expected: [arr, i, result], given: null <Array : int sum(int [])> [7 @L6] temp $4 = arr[i]; expected: [arr, i, result, temp $4 ], given: null <Array : int sum(int [])> [8 @L6] result = result + temp $4 ; expected: [arr, i, result], given: null <Array : int sum(int [])> [9 @L6] nop; expected: [arr, i, result], given: null <Array : int sum(int [])> [10 @L5] %intconst0 = 1 ; expected: [%intconst0, arr, i, result], given: null <Array : int sum(int [])> [11 @L5] i = i + %intconst0; expected: [arr, i, result], given: null <Array : int sum(int [])> [12 @L5] goto 2 ; expected: [arr, i, result], given: null <Array : int sum(int [])> [13 @L5] nop; expected: [result], given: null <Array : int sum(int [])> [14 @L8] return result; expected: [], given: null
作业分析 我们要做的就是根据项目中已有的接口或者抽象类,实现自己的分析的方法,补全空缺LiveVariableAnalysis类的代码完成分析:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 public class LiveVariableAnalysis extends AbstractDataflowAnalysis <Stmt, SetFact<Var>> { public static final String ID = "livevar" ; public LiveVariableAnalysis (AnalysisConfig config) { super (config); } @Override public boolean isForward () { return false ; } @Override public SetFact<Var> newBoundaryFact (CFG<Stmt> cfg) { return null ; } @Override public SetFact<Var> newInitialFact () { return null ; } @Override public void meetInto (SetFact<Var> fact, SetFact<Var> target) { } @Override public boolean transferNode (Stmt stmt, SetFact<Var> in, SetFact<Var> out) { return false ; } }
可以看到,其中四个方法都是空的,需要我们将其逻辑补充完全来完成代码分析,我们可以在父接口DataflowAnalysis中找到补充代码的参考。
首先是newBoundaryFact方法,该方法的注释为:
初始化边界向量,对于活跃变量分析的后向分析方式,简单来说就是在程序的exit点将所有变量设定为不活跃,或者说将活跃变量设定为一个空集合。
然后是newInitialFact方法,该方法的注释为:
初始化CFG图中每个节点的向量,对于活跃变量分析的后向分析方式,简单来说就是将所有变量设定为不活跃,或者说将活跃变量设定为一个空集合。
meetInto方法,该方法的注释为:
用于处理CFG图中由循环导致的环、由条件跳转等语句导致的多边指向同点的情况,将多个节点的活跃变量集合进行合并。而根据参考文章,在Taie中for、while、switch这些隐含了控制流跳转的语句类型,都被转换为了If语句。
transferNode方法,该方法的注释为:
用于处理遍历CFG图节点时,每个节点的活跃变量变化情况,并返回一个布尔代表该节点的活跃变量集合相比上次迭代是否发生了变化,当所有节点的活跃变量集合相比上次迭代都无变化时就代表得到了一个最小不动点,程序分析得到了一个精确度较高的结果。
此外代填充的还有Solver类中的一个方法initializeBackward和IterativeSolver类中的一个方法doSolveBackward,通过调试可以发现前面Analysis类中的四个方法并不会被调用,因此我们还需要在这两个方法中使用Analysis类。
具体调用顺序为solve->initialize->initializeBackward,然后再solve->doSolve->doSolveBackward,因此这两个方法的功能分别为:initializeBackward方法负责调用newBoundaryFact和newInitialFact初始化节点的进、出活跃变量集合,doSolveBackward方法负责调用meetInto和transferNode修改每个节点的活跃变量集合。
代码补全 首先先阅读源码,看看要用到的几个类如CFG、DataflowResult有什么方法可用。
DataflowResult 类的描述为:
1 An object which manages the data-flow facts associated with nodes .
一个管理着所有节点数据流动的类,里面有两个Map,存储着每个CFG节点对应的出、入活跃变量集合:
1 2 3 private final Map<Node, Fact> inFacts = new LinkedHashMap <>();private final Map<Node, Fact> outFacts = new LinkedHashMap <>();
还有某个节点的这两种活跃变量集合对应的getter和setter。
CFG 接口的描述为:
1 Representation of a control-flow graph of a method.
代表一个源代码方法的控制流图,父接口为Graph,主要用于获取节点相关的信息,如出入口节点、各节点的前驱后继和与之相连的边等等。
可以通过CFG接口遍历整个CFG。
Stmt 代表代码块/代码行/代码片段,有两个重要方法:
1 2 3 4 5 6 7 8 9 10 Optional<LValue> getDef () ; List<RValue> getUses () ;
简单调试打印一下可以看到,Assign的源码为:
1 2 3 4 5 6 7 8 9 class Assign { int assign (int a, int b, int c) { int d = a + b; b = d; c = a; return b; } }
这两个方法获取到的数据主要为:
1 2 3 4 [+] pascal.taie .ir .stmt .Binary : Optional[d] , [a, b, a + b] [+] pascal.taie .ir .stmt .Copy : Optional[b] , [d] [+] pascal.taie .ir .stmt .Copy : Optional[c] , [a] [+] pascal.taie .ir .stmt .Return : Optional.empty , [b]
简单来说就是一个获取等号左边的表达式(如果存在),一个获取等号右边(或者return等语句的返回值)的表达式。
说是表达式,但看结果一般都会返回一个Var,其他语句比如invoke等后面看到了再学习。
newBoundaryFact/newInitialFact 两个方法都是相同处理方式,各个节点的出入活跃变量结合都初始化为空就行:
1 2 3 4 5 6 7 8 9 @Override public SetFact<Var> newBoundaryFact (CFG<Stmt> cfg) { return new SetFact <>(); }@Override public SetFact<Var> newInitialFact () { return new SetFact <>(); }
meetInto 当程序分析在各个节点间跳转时,可能存在多条边指向同一个节点的情况,所以要用该方法将多个活跃变量集合并在一起取并集:
可以用SetFact类的union方法,里面会再调用Set的addAll方法:
1 2 3 4 @Override public void meetInto (SetFact<Var> fact, SetFact<Var> target) { target.union(fact); }
transferNode 该方法用于遍历节点中的代码块,同时根据出/入数据集合和代码内容得到入/出数据集合。
对于活跃变量分析的后向分析方式而言,要做的就是对每一个节点,根据其出口活跃变量集合和代码内容,得到一个入口活跃变量集合,最后判断迭代是否到达了不动点:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 @Override public boolean transferNode (Stmt stmt, SetFact<Var> in, SetFact<Var> out) { SetFact<Var> newIn = new SetFact <>(); newIn.union(out); if (stmt.getDef().isPresent()) { LValue def = stmt.getDef().get(); if (def instanceof Var) { newIn.remove((Var)def); } } for (RValue use: stmt.getUses()) { if (use instanceof Var) { newIn.add((Var)use); } } if (!in.equals(newIn)) { in.set(newIn); return true ; } return false ; }
initializeBackward 调用newBoundaryFact和newInitialFact方法来初始化每个节点的活跃变量集合:
1 2 3 4 5 6 7 8 9 10 11 protected void initializeBackward (CFG<Node> cfg, DataflowResult<Node, Fact> result) { for (Node node: cfg.getNodes()) { if (cfg.isExit(node)) { result.setInFact(node, analysis.newBoundaryFact(cfg)); result.setOutFact(node, analysis.newBoundaryFact(cfg)); }else { result.setInFact(node, analysis.newInitialFact()); result.setOutFact(node, analysis.newInitialFact()); } } }
doSolveBackward 调用meetInto和transferNode方法来处理每个节点的活跃变量变化:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 @Override protected void doSolveBackward (CFG<Node> cfg, DataflowResult<Node, Fact> result) { boolean fixed = false ; while (!fixed) { fixed = true ; for (Node node: cfg.getNodes()) { for (Node succ: cfg.getSuccsOf(node)) { analysis.meetInto(result.getInFact(succ), result.getOutFact(node)); } if (analysis.transferNode(node, result.getInFact(node), result.getOutFact(node))) { fixed = false ; } } } }
方法名为后向分析,出入集合的处理方式确实是后向,但实际节点到下一节点的处理顺序其实是前向分析,原因有二。
其一是StmtCFG类的getNodes方法使用了自定义的comparator创建了一个正向的TreeSet,反序搞起来比较麻烦。
其二是无论从哪个块开始,最终总会达到同一结果并终止,因为所有节点的初始出入集相同,从入口到出口的顺序相同,且每个节点都有固定的remove和add,每条路径上无论是前向还是后向,所经过的所有节点上的remove和add也是一样的。
流程分析 以Assign这个test为例,打印一下迭代过程中,每个节点产生的出入活跃变量集合。
首先是第一次,两个括号里的分别是入和出活跃变量集合:
1 2 3 4 [+] Line 4 : d = a + b [a, b] [] [+] Line 5 : b = d[d] [] [+] Line 6 : c = a [a] [] [+] Line 7 : return b [b] []
第二次:
1 2 3 4 [+] Line 4 : d = a + b [a, b] [d] [+] Line 5 : b = d[a, d] [a] [+] Line 6 : c = a [a, b] [b] [+] Line 7 : return b [b] []
第三次:
1 2 3 4 [+] Line 4 : d = a + b [a, b] [a, d] [+] Line 5 : b = d[a, d] [a, b] [+] Line 6 : c = a [a, b] [b] [+] Line 7 : return b [b] []
Tai-e课程作业
软件分析课程实验-A1-活跃变量分析和迭代求解器
Taie-食用指南(一)
南京大学 静态软件分析(static program analyzes)– Data Flow Analysis:Foundation 学习笔记
南大软分实验笔记|A1 存活变量分析与迭代求解器