南大软分课程笔记｜08 指针分析

前言

上节课中，我们主要学习了调用图构建、过程间控制流图和过程间数据流分析。其中，调用图是基于CHA构建的，而CHA本身存在精度欠佳的问题。因此，本节我们开始学习指针分析（pointer analysis）技术。相比CHA，它能得出更为精确的结果，因为它依赖实际的对象指向关系。

若无特别说明，本节课中我们提到的“指针”并不是C等程序设计语言中的指针类型，而是变量（variable）或域（field）等，指针分析就是分析这些指针与它们所表示的内存对象之间的指向关系。

指针分析简介

指针分析是一种非常重要的静态分析技术，用来计算给定指针指向的内存位置。对于OOP语言来说（以Java为例），我们主要关注一个指针（变量或域）能够指向哪些内存对象。另外，指针分析是一种may-analysis。

指针分析至今仍然是PL中的一个活跃研究领域。如果做文献考古的话，我们可以追溯到1980年POPL会议上的一篇论文。

下面是一个指针分析的简单的例子：

别名分析（alias analysis）与指针分析有紧密关联，但是实际上两者是不同的概念。前者想要回答的问题是，两个指针能否指向同一对象？后者想要回答的问题是，一个指针可能指向的对象有哪些？我们也很容易发现，别名信息实际上可以从指针分析的结果中得出。

指针分析有非常多的应用，如基础信息提取（调用图、别名等），编译器优化，Bug检测（空指针等）和安全分析等。我之前阅读的很多安全领域的论文都用到了指针分析，而这也是我学习程序分析的缘由。

指针分析的关键因素

指针分析是一个复杂系统，许多因素都会影响到分析的准确性和效率。谭添老师将这些因素、涉及的问题和学界已有的研究路线用表格做了归纳，十分清晰明了：

本课程在这些因素上的选择如上表中红色标注所示。下面我们分别来研究一下这些关键因素。

Heap Abstraction

“堆抽象”很好理解，就是研究如何对堆内存进行建模。程序运行起来后，从时间上看，堆上对象的数量可能是不定的。例如，某个for循环中可能会包含对象创建操作。

因此，为了确保分析能够终止，在静态分析中，我们会将动态分配的具体对象当作有限抽象对象（finite abstract objects）。例如，将所有在同一语句处创建的对象当作一个来处理，即使该语句可能位于一个for循环中：

ACM CSUR 2016的一篇论文用一幅图总结了不同的堆抽象建模方式：

其中，allocation-site是最常用的堆抽象方式。简单来说，就是将具体对象根据它们的分配点（allocation sites）进行抽象。例如，对于下面的代码片段来说，第二行a = new A();是一处allocation-site，我们就将所有在这一行创建的对象抽象为$o_{2}$。

for (i = 0; i < 3; i++) {
	a = new A();
}

Context Sensitivity

上下文敏感性则关注的是如何对函数调用上下文进行建模，分为两种情况：上下文敏感分析和上下文不敏感分析。前者将区分针对同一方法的不同调用上下文，为每一次针对该方法的调用都分析一次它的上下文；后者则将所有针对同一方法的调用上下文合并处理，每个方法只分析一次。

下图中，左侧就是上下文敏感分析，右侧是上下文不敏感分析：

很明显，前者更为精确，后者则可能不那么精确。

Flow Sensitivity

接下来是流敏感性。类似的，它也分为流敏感分析和流不敏感分析。前者会关注程序中语句的执行顺序，在每个程序点处维护一个指针指向关系映射；后者则会忽略控制流顺序，将程序视作无序的语句集合，为整个程序维护一个指针指向关系映射。

根据上述定义可以发现，我们之前做过的数据流分析都属于流敏感分析。

下图中，左侧和下方的蓝色块是不同程序点处的指针分析结果，属于流敏感分析；右侧的橘红色块则是流不敏感分析，因为它是整个代码段的指针分析结果，并不区分程序点。显而易见，后者可能存在误报，如橘红色块中的s实际上并不会指向"y"：

然而，本课程将选用流不敏感的分析方法。流敏感分析通常用于分析C/C++等代码。

Analysis Scope

最后一个关键因素是分析范围：整个程序或需求驱动。前者为整个程序中的所有指针计算指向信息；后者则只计算那些影响到特定区域（sites of interest，这个词组在我之前读过的很多安全论文中都出现过）的指针的指向信息。

我们关心的程序语句

现代程序设计语言中有许多不同的语句类型。本课中，我们只关心那些影响到指针分析的语句。在Java中，常见的指针有四种类型：本地变量（如变量x）、静态域（如c.f，有时也叫全局变量）、实例域（如x.f）和数组元素（如array[i]）。

对于数组元素来说，我们在做指针分析时会忽略它的索引，直接将数组元素当作数组对象的单一域arr，如array.arr。

在Java中，影响指针的语句可以归纳如下（更复杂的语句将被转换为三地址码）：

• New，如x = new T()
• Assign，如x = y
• Store，如x.f = y
• Load，如y = x.f
• Call，如r = x.k(a, ...)

对于Call语句来说，它又可以分为static call、special call和virtual call。我们在上一节说过，virtual call的情况最复杂，因此我们主要关注virtual call。

总结与思考

相对来说，这一节内容较少，是指针分析的简单的概念性介绍。

从这些知识中，我已经能够感受到指针分析在安全领域大有可为。继续学习吧！