实验作业 8

作业 8：污点分析

南京大学《软件分析》课程

作业出品：谭添、李樾

1 作业导览

为 Java 实现污点分析。

欢迎大家开启我们课程的最后一次作业！ヾ(o◕∀◕)ﾉ

在这次作业中，你需要基于第 6 次作业实现的上下文敏感的指针分析来为 Java 实现污点分析（taint analysis）。为了让你的污点分析不仅仅是个玩具，我们会在这次作业中教你一个叫做污点传播（taint transfer）的技术，这样你实现的污点分析就能够应用到生产实践中检测安全漏洞了。此外，我们也提供了可配置的污点分析框架，帮助你方便地设置污点分析中所需要的诸如 sources、sinks 等数据。

和第 7 次作业一样，这次作业是开放式的。换句话说，你需要依靠自己的智慧理清污点分析该如何与指针分析交互，然后设计污点分析算法并实现它。因此，本次作业的答案也是不唯一的。不过不用担心，我们会给你适当的提示。

在阅读接下来的内容前，请先按照 Tai-e 框架（教学版）配置指南将作业 8 对应的 Tai-e 项目（位于实验作业仓库的 A8/tai-e/ ）配置好。

2 实现污点分析

2.1 分析范围

在这一小节中，我们来定义一下你在这次作业中所需要实现的污点分析。和第 13 讲介绍的污点分析一样，我们会把一些特定的方法（通常是产生数据的 API）视作 taint sources，调用这些方法的语句会返回污点数据；为了和指针分析中的对象对应，这些污点数据也被叫做污点对象（taint objects）。我们也把一些特定方法的某些参数视作 taint sinks。此外，为了达到更高的精度，你需要实现一个上下文敏感的污点分析。作为参考，我们已经帮你写好了处理 sources 和 sinks 的规则（修改自第 13 讲课件的第 76 页给出的规则）：

类型	语句	规则（在上下文 $c$ 下）
Call (source)	`l: r = x.k(a1,...,an)`	$c : l \to c^{t} : m \in C G$ $⟨ m, u ⟩ \in$ $S o u r c e s$ $[] : t_{l}^{u} \in p t (c : r)$
Call (sink)	`l: r = x.k(a1,...,an)`	$c : l \to c^{t} : m \in C G$ $⟨ m, i ⟩ \in$ $S i n k s$ $[] : t_{j}^{u} \in p t (c : a i)$ $⟨ j, l, i ⟩ \in$ $T a i n t F l o w s$

这里， $S o u r c e s$ 是二元组 $⟨ m, u ⟩$ 的集合，其中 $m$ 表示一个被视作 source 的方法的签名，而 $u$ 是该方法返回的污点对象的类型。我们用 $t_{l}^{u}$ 来表示一个污点对象，其中 $u$ 是这个对象的类型， $l$ 表示创建这个对象的调用点（call site）。简单起见，你只需要使用空上下文作为污点对象的堆上下文（heap context）。

污点传播. 污点分析和指针分析看起来很相似，因为他们本质上都在跟踪程序中数据的流动——指针分析跟踪的是抽象的对象，污点分析跟踪的是污点对象。但是他们又有些微妙的不同：污点分析中的污点是一个更加抽象的概念——它与数据的内容相关联（参考这篇论文open in new window），因此它可以在不同的对象之间传播。我们把这样的现象叫做污点传播（taint transfer）。下面我们通过一个例子来展示这个概念：

String taint = getSecret(); // source
StringBuilder sb = new StringBuilder();
sb.append("abc");
sb.append(taint); // taint is transferred to sb
sb.append("xyz");
String s = sb.toString(); // taint is transferred to s
leak(s); // sink

假设我们把 getSecret() 和 leak() 分别视作 source 和 sink，那么在这个例子中，第 1 行的代码首先通过方法调用获得了一份字符串类型的秘密数据（即污点对象）并把它保存在了变量 taint 中。然后，这份秘密数据会经过两次污点传播流入到第 7 行的 sink 中：

第 4 行的方法调用 append() 把 taint 中包含的内容添加到了 sb 的末尾，于是 sb 指向的 StringBuilder 对象中也包含了秘密数据，故而该对象也应该被视作污点对象。换句话说，第 4 行的 append() 方法把污点从变量 taint 指向的对象传播到了变量 sb 指向的对象中。
第 6 行的方法调用 toString() 把 StringBuilder 对象转化成了包含相同内容的 String 对象，因此这个 String 也包含了秘密数据。换句话说，toString() 把污点从变量 sb 指向的对象中传播到了变量 s 指向的对象中。

然而，课上讲解的污点分析算法由于无从知道程序中 API 的含义，例如它不知道上面例子中的 append() 和 toString() 方法可以在不同的对象之间传播内容（特别是敏感数据），因而它不会像我们先前所描述的那样顺利地传播污点。结果就是，很多安全漏洞都会被遗漏。又因为上述模式在现实中的代码中很常见，所以我们需要对这些方法进行额外处理。

我们的解决方法是告诉污点分析哪些方法会引发污点传播以及它们是如何传播污点的。在这次作业中，当一个引发污点传播的方法 foo 被调用时，有以下三种污点传播的模式：

Base-to-result：如果 receiver object（由 base 指向）被污染了，那么该方法调用的返回值也会被污染。StringBuilder.toString() 是这样一类方法。
Arg-to-base：如果某个特定的参数被污染了，那么 receiver object（由 base 指向）也会被污染。StringBuilder.append(String) 是这样一类方法。
Arg-to-result：如果某个特定的参数被污染了，那么该方法调用的返回值也会被污染。String.concat(String) 是这样一类方法。

注意，因为静态方法没有 base 变量，所以他们不会引起 base-to-result 和 arg-to-base 的污点传播。此外，一些方法可能会引起多种污点传播，例如 String.concat(String) 不仅会引发 arg-to-result 的传播，也会引发 base-to-result 的传播。这是因为，它的返回值中同时包含了参数和 receiver object 的内容。

处理污点传播. 本质上，污点传播指的是某个方法调用会在调用点把污点从一些变量传播到另外一些变量中。在这样的传播过程中，我们把污点的来源称为 from 变量，把目标称为 to 变量。例如，对于一个 base-to-result 的污点传播，from 变量指的是调用点中的 base 变量，to 变量指的是调用点中接收返回值的变量。

为了处理污点传播，我们为污点分析定义一种新的输入，叫做 $T a i n t T r a n f e r s$ 。它是由四元组 $⟨ m, f r o m, t o, u ⟩$ 所构成的集合，其中 $m$ 表示会引发污点传播的方法，而污点会从 $f r o m$ 所表示的变量中传播到 $t o$ 所表示的变量中。 $u$ 表示传播后的污点（由 $t o$ 指向）的类型。具体来说,

$m$ 是引发污点传播的方法的签名；
$f r o m$ 要么是一个从 0 开始的整数索引，用来表示调用点中的实参，要么是字符串“base”，表示 base 变量。
$t o$ 是字符串“base”，表示 base 变量，要么是字符串“result”，表示调用点中接收返回值的变量；
$u$ 是传播后污点对象的类型。我们之所以需要这个信息，是因为污点传播有可能改变污点对象的类型。例如，StringBuilder.toString() 就会把污点从一个 StringBuilder 类型的对象上传播到一个 String 类型的对象上。所以，我们需要用 $u$ 来告诉分析算法传播后污点对象是什么类型。当污点对象类型在传播前后不一样时，这就很有用了。

基于 $T a i n t T r a n s f e r s$ ，我们下面给出应对三种污点传播模式的污点分析规则：

类型	语句	规则（在上下文 $c$ 下）
Call (base-to-result)	`l: r = x.k(a1,...,an)`	$c : l \to c^{t} : m \in C G$ $⟨ m, “base”, “result”, u ⟩ \in$ $T a i n t T r a n s f e r s$ $[] : t_{j}^{u^{'}} \in p t (c : x)$ $[] : t_{j}^{u} \in p t (c : r)$
Call (arg-to-base)	`l: r = x.k(a1,...,an)`	$c : l \to c^{t} : m \in C G$ $⟨ m, i, “base”, u ⟩ \in$ $T a i n t T r a n s f e r s$ $[] : t_{j}^{u^{'}} \in p t (c : a i)$ $[] : t_{j}^{u} \in p t (c : x)$
Call (arg-to-result)	`l: r = x.k(a1,...,an)`	$c : l \to c^{t} : m \in C G$ $⟨ m, i, “result”, u ⟩ \in$ $T a i n t T r a n s f e r s$ $[] : t_{j}^{u^{'}} \in p t (c : a i)$ $[] : t_{j}^{u} \in p t (c : r)$

配置污点分析. 为了让污点分析用起来灵活，我们设计了可配置的污点分析框架。该框架支持你使用 YAMLopen in new window 格式来配置 sources、sinks和污点传播。作业包中路径为 src/test/resources/pta/taint/taint-config.yml 的文件可以作为参考样例。

配置文件由一条条数据构成。表示 source 的数据格式是：

{ method: <METHOD_SIGNATURE>, type: <TYPE_NAME> }

其中

<METHOD_SIGNATURE> 是 source 方法的签名；
<TYPE_NAME> 是调用该方法返回的污点对象的类型名称。

在指针分析中，每个对象都有类型，污点对象也不外乎如是。所以，我们需要在配置文件中指明污点对象的类型，这样污点分析在处理 source 方法调用的时候才能创建出类型正确的污点对象。

表示 sink 的数据格式是：

{ method: <METHOD_SIGNATURE>, index: <INDEX> }

其中

<METHOD_SIGNATURE> 是 sink 方法的签名；
<INDEX> 是指向方法参数的索引，一般是包含敏感信息的参数（通常也只有参数才会被设置为sinks）。它从0开始计数。

表示污点传播的数据格式是：

{ method: <METHOD_SIGNATURE>, from: <INDEX>, to: <INDEX>, type: <TYPE_NAME> }

这里的四个元素刚好对应了前面定义的 $T a i n t T r a n s f e r s$ 中的四元组。

2.2 Tai-e 中你需要了解的类

作业 6 已经介绍过了上下文敏感的指针分析所用到的类。下面我们再介绍一下和污点分析相关的类：

pascal.taie.analysis.pta.plugin.taint.Source
这个 record 类表示 sources。
pascal.taie.analysis.pta.plugin.taint.Sink
这个 record 类表示 sinks。
pascal.taie.analysis.pta.plugin.taint.TaintTransfer
这个 record 类表示污点传播。在这个类中，我们用整数来表示污点传播被对应方法引发时的 from 变量和 to 变量。具体来说，一个大于等于 0 的整数 i 表示调用点上被调用方法的第 i 个参数；-1 表示 base 变量；-2 表示接收结果的变量。
pascal.taie.analysis.pta.plugin.taint.TaintConfig
这个类表示污点分析的配置信息。它提供了解析配置文件以及获取 sources、sinks 和污点传播信息的 API。
pascal.taie.analysis.pta.plugin.taint.TaintManager
这个类被用来管理污点分析中的污点对象。
pascal.taie.analysis.pta.plugin.taint.TaintFlow
这个 record 类表示分析算法检测到的 taint flows（由 source 的调用点和 sink 的调用点组成），也就是污点分析算法的结果。
pascal.taie.analysis.pta.plugin.taint.TaintAnalysiss
这个类实现了污点分析。它目前是不完整的，因此你需要按照第 2.3 节的要求补全它。（注意，类名 TaintAnalysiss 最后之所以多了一个s，是因为 TaintAnalysis 类已经在 Tai-e 中被用于实现非作业版的污点分析了 😕）

2.3 你的任务 [重点!]

在这次作业中，你需要补全下面列出的两个类中的方法：

pascal.taie.analysis.pta.cs.Solver:

void addReachable(CSMethod)
void addPFGEdge(Pointer,Pointer)
void analyze()
PointsToSet propagate(Pointer,PointsToSet)
void processCall(CSVar,CSObj)

pascal.taie.analysis.pta.plugin.taint.TaintAnalysiss:

Set<TaintFlow> collectTaintFlows()：返回一个集合，其中包含污点分析检测到的所有 taint flows。提示：你可以在这个方法中实现处理 sink 的规则（在第 2.1 节给出过）。

Solver 中要实现的 5 个方法和作业 6 中的一样，只不过你现在需要再添加一些代码来支持污点分析。但是要注意，不要直接用作业 6 中的 Solver.java 来替换本次作业中的同名文件，因为这次作业中的 Solver.java 中还包含了一些和污点分析相关的框架代码。

在这次作业中，你可能会需要分析指针集的结果来帮助你开发和调试污点分析。但是附有上下文信息的指针集很可能会让你看得头疼，所以我们这次把 CISelector（上下文不敏感）指定为默认的上下文策略。希望这能让你调试得轻松一点。不过，当你实现完 TaintAnalysiss 和 Solver 以后，你也可以试试其它上下文选择策略（在第 3 节会介绍）来观察污点分析的精度在不同上下文下的变化。

在 TaintAnalysiss 类中，除了 collectTaintFlows()，你也需要实现处理 sources 和污点传播的逻辑。再次声明一下，这次作业是开放式的，所以你需要自己想办法实现污点分析，比如考虑设计什么样的数据结构和辅助方法加入到 TaintAnalysiss 中。

提示：

在 TaintAnalysiss 的构造函数中，我们已经给出了解析配置文件的代码，并把解析的结果保存在了 config 字段中，你可以直接使用它。此外，我们也初始化了 TaintManager 对象并将其保存在了 manager 字段中，你可以通过它来管理污点对象。如果你的实现还需要做一些初始化工作，你也可以在构造函数中添加你的代码。
在这次作业中，指针分析和污点分析互相依赖，所以 Solver 和 TaintAnalysiss 各自保存了指向对方的引用，即 Solver 中的 taintAnalysis 字段和 TaintAnalysiss 中的 solver 字段。你需要想清楚如何利用这两个引用字段实现两个分析之间的交互。如果有需要的话，你也可以向这两个类中添加自己需要的字段和方法。

3 运行与测试

你可以按照 Tai-e 框架（教学版）配置指南的说明来运行分析算法。在这次作业中，Tai-e 会对被分析的程序运行上下文敏感的指针分析和污点分析，然后输出各类指针的指针集以及检测到的 taint flows：

Points-to sets of all variables

Points-to sets of all static fields

Points-to sets of all instance fields

Points-to sets of all array indexes

Detected 0 taint flow(s):

由于你还没有完成作业代码，所以指针集目前都还是空的，并且也不存在任何 taint flows。当你完成作业后，输出可能会长得像这样（省略了指针集的结果）：

Detected 4 taint flow(s):

TaintFlow{<SimpleTaint: void main(java.lang.String[])>[0@L4] temp$0 = invokestatic <SourceSink: java.lang.String source()>(); -> <SimpleTaint: void main(java.lang.String[])>[2@L5] invokestatic <SourceSink: void sink(java.lang.String)>(s1);/0}

TaintFlow{<SimpleTaint: void main(java.lang.String[])>[0@L4] temp$0 = invokestatic <SourceSink: java.lang.String source()>(); -> <SimpleTaint: void main(java.lang.String[])>[16@L11] invokestatic <SourceSink: void sink(java.lang.String,int)>(s3, %intconst0);/0}

TaintFlow{<SimpleTaint: void main(java.lang.String[])>[3@L7] temp$1 = invokestatic <SourceSink: java.lang.String source()>(); -> <SimpleTaint: void main(java.lang.String[])>[5@L8] invokestatic <SourceSink: void sink(java.lang.String)>(s2);/0}

TaintFlow{<SimpleTaint: void main(java.lang.String[])>[3@L7] temp$1 = invokestatic <SourceSink: java.lang.String source()>(); -> <SimpleTaint: void main(java.lang.String[])>[16@L11] invokestatic <SourceSink: void sink(java.lang.String,int)>(s3, %intconst0);/0}

除此之外，Tai-e 还会把被分析程序的 IR 输出到 output/ 目录下。IR 都保存在了 .tir 格式的文件中，用一般编辑器都可以打开。

我们的测试驱动程序在 pascal.taie.analysis.pta.TaintTest 类中。你可以用这个类来测试你的实现，具体参考 Tai-e 框架（教学版）配置指南。注意，在这次作业中，我们只会取你输出的 taint flows 和标准输出比较。换句话说，其它分析结果诸如指针集都会被忽略。有些测试需要上下文敏感的指针分析，因此记得把作业 6 中实现的 context selectors 复制到这次作业中，否则你可能会有测试用例无法通过。

我们鼓励大家用不同的上下文策略（比如 context insensitivity 和 2-object sensitivity）来分析测试用例（如 TaintInList.java），然后观察指针分析的精度是如何影响污点分析的精度的。

4 通用准则

在这次作业中，你只需要保证实现的正确性。不必过早考虑效率。
禁止把你的作业包发给其他人参考。
禁止抄袭。自己的工作必须由自己完成。

5 作业提交

你应当提交一个 zip 文件，其中包含你实现好的以下类：

TaintAnalysiss.java
Solver.java

6 评分

你可以参照实验作业评测系统使用指南来使用我们的作业评测系统对你完成的作业进行评分。

你的分数将取决于你实现的正确性：我们会用你提交的实现来分析 src/test/resources/ 目录下的测试用例和另外一些未公开的测试用例，然后将得到的结果与标准实现的分析结果进行比较，从而进行评分。

祝君好运!

# 实验作业 8

作业 8：污点分析

# 1 作业导览

# 2 实现污点分析

# 2.1 分析范围

# 2.2 Tai-e 中你需要了解的类

# 2.3 你的任务 [重点!]

# 3 运行与测试

# 4 通用准则

# 5 作业提交

# 6 评分

实验作业 8

1 作业导览

2 实现污点分析

2.1 分析范围

2.2 Tai-e 中你需要了解的类

2.3 你的任务 [重点!]

3 运行与测试

4 通用准则

5 作业提交

6 评分