Tha*_*ain 7 java pointers static-analysis analysis taint
我目前正在用 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（付费专区，抱歉）
小智 9
流函数的分布定义为： f(a ? b) = f(a) ? f(b)，与 ? 是合并功能。在 IFDS 中， ? 被定义为集合联合 ?。这意味着无论您是在 flow 函数之前还是之后应用合并函数，最终都会得到相同的结果。
在传统的数据流分析中，您浏览 CFG 的语句并传播数据流事实集。因此，使用流函数 f，对于每个语句，您计算 f(in, stmt) = out，输入和输出要保留的信息集（例如：对于输入集 {(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) 时，我们只知道事实上是 0 并且语句是“bf = new X();”。因为我们不知道 a 和 b 指的是分配站点 allocA，我们不知道它们是别名，因此我们不知道 af 也应该在语句之后指向 allocX。
IFDS 在分配性假设上运行：在运行流函数之后合并输出应该产生与在运行流函数之前合并输入集相同的结果。换句话说，如果您需要将来自多个元素的信息组合在集合中以在您的集合中创建某个数据流事实，那么您不是分布式的，并且不应在 IFDS 中表达您的问题（除非您这样做一些东西来处理这些组合案例，就像你提到的论文的作者 [1] 所做的那样）。