软件测试：实践者方法最新章节_孙志安著

5.6　流敏感指针分析

指针分析能够用于空指针引用、内存泄漏、内存释放后重用等缺陷分析，是重要的静态代码分析方法之一。流敏感（Flow-Sensitive）、流不敏感（Flow-Insensitive）、上下文敏感（Context-Sensitive）、上下文不敏感（Context-Insensitive）以及流敏感+上下文敏感组合、流敏感+上下文不敏感组合分析算法是常用的指针分析方法。这里仅讨论基于流敏感的指针分析方法，其他分析方法读者可参考相关文献。

流敏感是指基于程序语句执行顺序，如数据流分析的指针别名（Pointer Alias）分析过程中，一个流不敏感指针别名分析可能得到“变量 x 和 y 可能指向同一位置”，流敏感指针别名分析得到的结论则类似于“在执行第20条指令后，变量 x 和 y 可能指向同一位置”。一个流不敏感指针别名分析不考虑控制流，且认为所发现的别名在程序所有位置均成立。

5.6.1　流敏感分析背景

程序控制流图上的每个节点 k 维护两个指向图：表示进入节点 k 的指针信息，表示从节点 k 流出的指针信息。每个节点都有一个传递函数将传递到。传递函数的一个特点就是采用两个集合和分别表示节点 k 产生的指针信息和删除的指针信息，此两个集合的内容依赖于节点 k 关联程序语句的语义，随着新指针信息的积累，在分析过程中，其内容发生变化。对于所有节点 k ，指针分析迭代计算如下函数，直至收敛

（5-5）

（5-6）

对于一条语句 k ，如果关联语句是 x = y ，则表示 x 指向的所有信息被杀（kill）掉，即被新的关系替代。对于一条语句 k ，如果关联的语句是* x = y ，则情况将变得比较复杂。如果 x 被定义为仅仅指向一个单一的对象 z ，那么。因此，虽然添加了新的信息，但保守地保留了所有现有指向关系。在如下情况下，一个指针可能指向多个具体的内存地址：

（1）指针的指针集包含多个具体的内存地址。

（2）指针是一个heap变量。

（3）递归函数中的局部变量，在栈上运行时将产生多个对象实例。

堆模型是指针分析的基础，它将概念上无限大小的堆抽象为一组有限的内存位置。基本做法是将每个静态内存分配位置视为一个不同的抽象内存位置，并在程序执行过程中映射到多个具体内存位置。

5.6.2　静态单赋值问题

对于静态单赋值（Static Single Assignment，SSA），每个变量在程序中只定义一次，原始程序中具有多个定义的变量被拆分为单独的实例，每个实例对应于一个定义。在控制流图中的汇聚点处，使用函数组合同一变量的不同实例，生成对该变量新实例的赋值。SSA形式显式地表示定义−使用（def-use）信息，并允许数据流信息直接从变量定义流到相应使用的地方，是执行稀疏分析的理想形式。

向SSA形式的转换是通过指针使用实现的，且指针只能通过指针分析发现，因为间接def的存在，使得这种转换异常复杂。由于得到的指针信息是保守的，实际上，每个间接的def和use都是一个可能的def或use。我们使用 X 和 μ 函数表示这些可能的def和use，在原始程序表示的每一个间接STORE,如* x = y 中，对于每一个可能被STORE定义的变量 v ，用一个函数 v = X ( v ) 进行注释。类似地，对于每一个可能被LOAD如访问的变量 v ，则用一个函数注释。当转换为SSA形式时，每个 X 函数被视为给定变量的定义和使用，每个函数则被视为对给定变量的使用。

为了有效避免处理间接STORE和LOAD的复杂性，GCC、LLVM等编译器使用SSA的一个变体，称为不完全SSA形式。变量可分为两类：一类是包含从不被指针引用的顶级变量（Top-Level Variables，TLV），其定义和使用可以通过检查予以简单确定，无须指针信息，这些变量可以使用任何构造SSA形式的算法转换为SSA；另一类是包含那些可以被指针引用的变量（Address-Taken Variables，ATV），为避免上述复杂情况，这些变量不以SSA形式放置。

5.6.3　LLVM的内部表示

在LLVM中，TLV保存在概念上无限的虚拟寄存器中，这些寄存器以SSA形式维护。ATV以非SSA形式保存在内存中而非寄存器中，使用ALLOC和COPY指令修改TLV。ATV通过LOAD和STORE指令访问，这两条指令将TLV作为参数。ATV在内部表示IR从未被语法引用，而是使用LOAD和STORE指令来间接引用。LLVM指令使用三地址格式，因此每条指令最多有一个指针解引用级别，通过引入临时变量，具有多个间接级别的源状态被简化为一个指针解引用级别。图5-32给出了一个C代码片段及其对应的不完全SSA形式示例。

图5-32中，变量 w 、 x 、 y 、是TLV，已转换为SSA形式；变量 a 、 a 、 c 、 d 是ATV，因为它们存储在内存中，仅通过LODA和STORE指令访问。因为ATV为非SSA形式，它们可以分别被定义多次，就像变量 c 、 d 一样。由于无法直接命名ATV，LLVM将对它保持不变，即每个ATV至少有一个仅引用该变量的虚拟寄存器。

图5-32　一个C代码片段及其对应的不完全SSA形式示例

5.6.4　稀疏流敏感指针分析

稀疏流敏感指针分析（Sparse Flow-Sensitive Pointer Analysis，SFS）的主要数据结构是def-use图，它包含程序语句的一个节点以及表示def-use链的边，如果在节点中定义变量并在节点中使用，则存在从到的有向边。TLV的def-use边，可以通过程序检查确定。ATV的边则需要通过辅助分析进行计算。第一步是使用辅助分析结果，将ATV转换为SSA形式，既然STORE和LOAD已经使用了和函数进行注释，则采用任何标准的SSA算法，都可以将程序转化为SSA形式。图5-33给出了一个示例程序片段及采用辅助分析计算的指针信息。

图5-33　一个示例程序片段及采用辅助分析计算的指针信息

图5-34给出了用和函数注释并翻译成SSA的相同程序片段，注释来自于辅助分析计算的指针信息。例如，对于控制流图节点，为p的指针集合中每个变量（a）添加一个函数，。对于控制流图节点，为v的指针集合中每个变量（e和f）添加一个函数。其他节点都可以通过类似方式进行注释。一旦对所有节点都进行了注释，就可以使用任何标准SSA算法导出其SSA形式。

图5-34　用和函数注释并翻译成SSA的相同程序片段

相对于分析计算更加精确的流敏感信息，辅助分析计算def-use信息则偏于保守。因此，对于一个增加了注释的STORE指令，必须解决如下3个方面的问题：

（1）在流敏感结果中，可能并不指向。在这种情况下，是的副本，且不会并入的任何信息。

（2）在流敏感结果中，可能仅指向。在这种情况下，对的指针集进行强更新，是的副本，且不包含的任何信息。

（3）可能指向及流敏感结果中的其他变量。在这种情况下，对的指针集进行弱更新，包含来自和 y 的指向信息。

通过计算得到的SSA信息，能够构建def-use图。但要创建def-use图，必须从每个间接定义，即STORE到可能使用这个间接定义变量的每个语句之间，增加一条边。为每个用函数注释的STORE，创建一个从该STORE到每个使用作为参数的 X 、、函数的语句之间，定义一条def-use边，用ATV变量的名称标记与ATV相对应的每条def-use边，当传播指针信息时，分析只沿着标有变量名称的边传播变量的信息即可。图5-35展示了由图 5-34转换而成的def-use图。

图5-35　由图5-34转换而成的def-use图

5.6.5　访问等效性

在实际应用中，可能需要大量def-use边，而且每个LOAD和STORE都可以访问数以千计的变量，基于解引用变量的指针集来设置大小，每个变量都可以在程序中的数十或数百个位置进行访问。在大型基准测试中，可能会创建数以亿计的def-use边，以至于无法实现可扩展分析。为此，引入访问等效（Access Equivalence，AE）的概念，以便以紧凑的方式表示相同的信息。也就是无论何时，用LOAD或STORE指令访问一个变量时，两个ATV变量和访问等效。即对于所有变量，使得在LOAD或STORE中被解引用，，这种对等概念与Hardekopf和Lin所描述的位置对等概念相似，其不同点为：通过位置对等，检查程序中的所有指针，以确定两个变量是否相等，而访问等效性只关注在LOAD或STORE中解所使用的指针。两个变量的访问等效是一种非位置等效。访问等效的优点是SSA算法将为所有访问等效变量计算相同的def-use链。根据定义，任何定义一个变量的STORE也必须定义所有访问等效变量。类似地，当使用一个变量时，必须使用所有访问等效变量的LOAD。

使用辅助分析确定访问等效性，必须识别由同一组LOAD和STORE访问的变量。设AE是从ATV到指令集的映射，对于每个LOAD或STORE指令I，以及对于I访问的每个变量，包括I。一旦处理完所有指令，如果，那么任意两个变量和是访问等价的。一旦ATV被划分为访问等价类，def-use图的边就会使用分区而不是变量名重新标记。对于图5-33，访问等效项为：、、、。图5-36展示了与图5-35相同的def-use图，其不同之处在于同一分区中访问等效变量的边折叠成了一条边。

图5-36　基于访问等效性分析的def-use图

5.6.6　算法

将所有内容放在一起，稀疏流敏感指针分析算法从计算def-use图的一系列预处理开始。

（1）通过辅助分析计算程序保守的def-use信息，通过辅助分析结果计算程序的过程间控制流程图（Interprocedural Control-Flow Graph，ICFG），包括对其潜在目标间接调用的解决方案。然后，所有函数调用被转换为一组COPY指令，用以表示参数分配。类似地，函数返回亦被转换为COPY指令。

（2）计算所有TLV确切的SSA信息。这个步骤所计算的函数被转换成COPY语句。例如，将转换为，将地址获取变量划分为访问等价类。

（3）对于每个分区 P ，使用辅助分析结果标记每个STORE，该STORE可以使用函数修改 P 中的变量，用函数标记每个可能访问 P 中变量的LOAD。

（4）使用多种可用方法中的任一方法计算分区的SSA形式创建函数。

（5）通过为每个指针相关的指令和步骤（4）创建的每个函数，创建一个节点，构造def-use图。然后，对于每个ALLOC、COPY和LOAD节点，将来自的未标记的边添加到使用由定义TLV的每个其他节点；对于具有定义分区变量的函数的每个STORE节点，将来自的边添加到使用的每个节点，并由分区 P 标记；对于定义分区变量的每个节点，为每个使用的节点创建一个未标记的边。