7

我目前正在用 Java 做一个过程间分析项目，我正在研究使用 IFDS 求解器来计算程序的控制流图。我发现很难遵循描述 IFDS 框架和图形可达性所涉及的数学。我在几个地方读到它不可能使用这个求解器来计算程序的点到集，因为“指针分析被认为是一个非分布问题”。[1] 其他消息来源说，这通常专门针对“强更新”，据我所知，这是现场写入语句。

我想我基本上可以遵循求解器如何计算边缘并计算出数据流事实。但我不太明白这是什么意思：f(A ∪ B) = f(A) ∪ f(B) 实际上是指分配函数的定义，因此说指向分析意味着什么处理非分配函数。

链接源 [1] 给出了一个特定于字段写入语句的示例：

A a = new A();
A b = a;
A c = new C();
b.f = c;

它声称，为了推理对 bf 的分配，还必须考虑基 b 的所有别名。我可以按照这个。但我不明白的是，这个动作的特性是什么，使它无法分配。

[2] 中的一个类似（我认为）示例：

x = y.n

在语句之前有指向边 y-->obj1 和 obj1.n-->obj2 （其中 obj1 和 2 是堆对象）。他们声称

如果我们独立考虑每个输入边，则不可能正确推断出边 x-->obj2 应该在语句之后生成。该语句的流函数是点到图整体的函数，不能分解为每条边的独立函数，然后合并得到正确的结果。

我想我几乎明白，至少第一个例子在说什么，但我没有理解分配函数的概念，这阻碍了我了解全貌。任何人都可以在不使用我难以理解的集合论的情况下，在指针分析的实际基础上解释什么是分布函数或非分布函数吗？

[1] http://karimali.ca/resources/pubs/conf/ecoop/SpaethNAB16.pdf

[2] http://dl.acm.org/citation.cfm?doid=2487568.2487569（付费专区，抱歉）

4

1 回答 1

9

流函数的分布性定义为：f(a Π b) = f(a) Π f(b)，其中 Π 是合并函数。在 IFDS 中，Π 被定义为集合并集 ∪。这意味着无论您是否在流函数之前或之后应用合并函数，最终都会得到相同的结果。

在传统的数据流分析中，您会检查 CFG 的语句并传播数据流事实集。因此，使用流函数 f，对于每个语句，您计算 f(in, stmt) = out，输入和输出要保留的信息集（例如：对于 in-set {(a, allocA), ( b, allocA)} - 表示对象 a 和 b 的分配位置是 allocA，并且语句“bf = new X();” - 我们将其命名为 allocX，您可能会得到外集 {(a, allocA), (b, allocA), (af, allocX), (bf, allocX)} 因为 a 和 b 是别名）。

IFDS 将 in-set 分解为单独的数据流事实。因此，对于每个事实，不是对整个 in-set 运行一次流函数，而是在 in-set 的每个元素上运行它：∀ d ∈ in, f(d, stmt) = out_d。然后框架将所有 out_d 合并到最终的 out-set 中。这里的问题是，对于每个流函数，您无权访问整个 in-set，这意味着对于我们上面介绍的示例，在语句上运行流函数 f((a, allocA)) 将产生第一个外集 {(a, allocA)}，f((b, allocA)) 将产生第二个外集 {(b, allocA)}，而 f(0) 将产生第三个外集 {( 0), (bf, allocX)}。因此，合并结果后的全局起点将是 {(a, allocA), (b, allocA), (bf, allocX)}。我们错过了 {(af, allocX)} 这个事实，因为在运行流函数 f(0) 时，我们只知道 in-fact 是 0 并且语句是“bf = new X();”。因为我们不知道 a 和 b 指的是分配站点 allocA，我们不知道它们是别名，因此我们无法知道 af 在语句之后也应该指向 allocX。

IFDS 基于分布性假设运行：在运行流函数后合并外集应该产生与在运行流函数之前合并内集相同的结果。换句话说，如果您需要组合来自 in-set 上多个元素的信息以在您的 out-set 中创建某个数据流事实，那么您不是分布式的，并且不应该在 IFDS 中表达您的问题（除非您这样做处理这些组合案例的东西，就像你提到的论文的作者 [1] 所做的那样）。

于 2018-04-19T10:15:20.090 回答