Program Analysis and Specialization for the C Programming Language Chapter 4

节选其中一部分

通过一种与标准语义相关的非标准类型推断系统来定义该分析。从该定义中，推导出基于约束的公式表达，并开发了一种高效的推断算法。非标准类型推断的使用在定义和实现之间实现了清晰的分离，并且提供了比文献先前报告的简单得多的分析方法。

这一章展示了一种过程间的基于约束的程序分析方法。通常来说，函数的上下文敏感分析通过拷贝约束来实现。这指数级增加了约束数量，并降低了解决的速度。我们提出了一种求解指针类型向量约束的方法。通过这种方式，只有一部分额外约束产生比过程内的情况。

Introduction

当两个对象的左值一致时，称这些对象互为别名。别名分析的目的是近似分析运行时的别名集合。本章我们展示一个相关但有些不同的指针分析对于C语言程序。对于每一个指针变量，它计算指针可能指向的抽象地址集合。

在具有指针和 / 或引用调用参数的语言中，别名分析是大多数其他数据流分析的核心部分。例如，对表达式*p = 13进行活跃变量分析时，如果没有指针信息，就必须基于最坏情况假设：p可能引用所有（可见的）对象，因此这些对象随后都必须被标记为 “活跃”。显然，这会导致活跃变量分析几乎失去作用。另一方面，如果已知可能的别名仅为 ${<*p, x> , <*p, y>}$ ，则只需将x和y标记为 “活跃”。

一些实验证据表明：Landi 的别名分析报告显示，在一个 3000 行的程序中，特定程序点的别名数量超过 200 万个 [Landi，1992a]。

指向分析（Points-to analysis)

对于每个指针类型的对象，我们在程序执行时决定一个安全的近似计算对指针也许指向的地址集合，对于所有可能的输入。一个特别的例子是函数指针。分析的结果是指针也许会调用的函数集合。

一个指向关系可以被分为static或是dynamic依赖于其的创建，例如创建一个数组等。在对程序进行单次遍历的过程中，可以收集到准确的静态指向信息。指向关系创建在程序执行叫做动态的，例如取地址等。更普遍来说，值设置（value setting）函数可能创建一个动态的指向关系

基于集合的指针分析

在这一章中我们研究一种值不敏感的基于集合的指向分析方法，通过解决约束来实现。一个基于集合的分析一个规则说明和一个推理算法组成。

说明描述了指针近似计算的安全性。我们展示一系列推理规则，如此一个指针抽象映射满足规则只有当这个映射是安全的。这给出了该问题与算法无关的特征描述。

随后我们展示一个基于约束特性的详细说明，并且给一个解决约束的算法。这个基于约束的算法工作于两个阶段：（1）一个约束系统产生捕捉指针和抽象地址间的依赖。（2）接下来，通过迭代求解过程找到约束的解决方案。

基于约束分析和经典的数据流分析相似，但有一个更强的语义基础。我们将借鉴迭代数据流分析技术来求解具有有限解的约束系统。

本章总览

4.2 节讨论值流分析可实现的不同精度维度：过程内与过程间分析，以及流敏感与流不敏感分析。

4.3 节探讨 C 语言指针分析的若干方面。

4.4 节为 C 语言定义一种粘性、流不敏感的指针分析，并阐明 “安全性” 概念。

4.5 节给出该问题的基于约束的特征描述，并证明其正确性。

4.6 节将分析扩展为上下文敏感的过程间分析。粘性分析会合并对函数的所有调用，导致精度损失。我们提出一种基于静态调用图的、上下文敏感的基于约束分析技术。

4.7 节介绍一种约束求解算法。

4.8 节讨论算法层面的问题，重点关注效率。

4.9 节通过现有实现的基准测试，说明该分析方法的实用性。

流敏感分析比流不敏感分析更精确。在4.10 节中，我们研究基于约束的 C 语言程序点指针分析，说明为何多级指针使这类分析变得困难。

最后，4.11 节介绍相关工作，4.12 节提出未来工作方向并总结全文。

指针分析：精确性与效率

值流分析的精度大致可以通过两个特性来描述：流敏感性，以及它是过程间分析还是过程内分析。提高精确度通常会降低效率并且使用更多存储空间。在本节中，我们将讨论各种精度程度及其与 C 程序的相关性。

流不敏感和流敏感分析

一个数据流分析考虑了控制流就叫做流敏感。否则叫流不敏感。两者最大的区别是对于if语句的处理。

int x,y,*p;
if(test) p=&x;else p=&y;
// foo(p);
// bar(p);

流敏感分析分别记录下p被赋值为x地址和y地址的分析。在这个分支后，信息合并，并且p被映射到x和y两者。两个分支区别十分重要如果包含函数调用。

流不敏感分析总结这个指针的使用，并且认为p也许会指向x和y在两个分支。在这种情况下，虚假的指向信息会被传播到两个分支上。

流不敏感分析和流敏感分析的概念与程序点特定分析和摘要分析的概念密切相关。一种为每个变量维护适用于函数所有程序点（对于全局变量则适用于整个程序）的摘要的分析，称为摘要分析。流敏感分析必须不可避免的是程序点特定分析。

流敏感和不敏感分析是一个在精确度和效率之间的妥协：一个流敏感分析是更精确的，但是用了更多空间并且更慢。

我们关注流不敏感指针分析考虑到下面几个原因：

经验而谈，C程序由许多小函数组成。通过总结所有程序点而引入的额外近似似乎并不太重要。
程序点特定分析必须使用一个不可接收数量的存储。在分析大型程序时，这种务实的观点很重要。
我们的分析应用不涉及程序点特定信息，例如绑定时间分析是程序点不敏感的。因此，流敏感指针分析不会在绑定时间分离的基础上进一步改进（除非存在虚假信息的传播 —— 但我们认为这种情况可以忽略不计）。

Poor man’s program-point analysis

通过一个简单的转换，恢复程序点特定分析的精确度是可能的，在没有收集每个程序点的确切信息时。

一个赋值语句 $e_1 = e_2$ ，当 $e_1$ 是一个变量， $e_2$ 与指针变量独立，被称为初始化赋值。这个idea是重命名指针变量当它们被初始化。

过程内和过程间分析

过程内程序分析关注函数体内部的数据流，并且对函数调用做出最坏情况假设。在这章中我们使用”过程内“以一种更严格的意义：函数分析是上下文无关的。过程间分析在考虑调用上下文的情况下推断信息。过程内分析也称为单变体分析或粘性分析，而过程间分析也称为多变体分析。

过程间分析通过避免调用之间的相互干扰来提高过程内分析的精度。注意图34描述了例子4.6程序过程间调用图。目标是第一个调用返回的值不会错误地传播到第二个调用，反之亦然。信息必须仅通过有效或可实现的程序路径传播。当过程间的退出路径与进入路径相对应时，控制路径是可实现的。

使用程序间信息

程序间分析主要关注函数间值流信息传播。另一个方面是使用推断的信息，例如为了优化，或是驱动其他的分析。经典的过程间分析会为每个函数生成一个摘要，即合并所有调用。显然，这会降低可能的优化数量。

例子4.7：假设我们对一个包含调用bar(0)和bar(1)的程序应用过程间常量传播分析。经典分析会将这两个调用合并，此后将参数归类为 “非常量”，从而排除了如if语句在编译时执行的可能性。

一种激进的方法是要么将函数内联到调用方中，要么根据函数的使用情况对其进行复制。后者也被称为过程克隆。

我们开发了一种灵活的方法，其中每个函数都标注有上下文特定信息和摘要。如果需要，函数可以在后续阶段进行克隆。我们将在第 6 章再次讨论这个问题，并推迟就是否克隆函数做出决定。

我们假设程序的静态调用图是可用的。回想一下，静态调用图近似表示函数的调用关系，并根据调用上下文为函数分配一个变体编号。例如，如果一个函数在 n 个上下文中被调用，该函数就有 n 个变体。尽管函数不会根据上下文进行文本复制，但假设函数的参数和局部变量存在 n 个变体是有用的。我们用 vi 表示对应第 i 个变体的变量。

也许还是必须

指针抽象的确定性可以用“可能（may）”或“必须（must）”来描述。可能指向分析（may point-to analysis）为每个指针计算其在运行时可能指向的一组抽象位置；必须指向分析（must point-to analysis）则为每个指针计算其必须指向的一组抽象位置。

“可能”和“必须”分析也称为存在性分析（existential analysis）和全称分析（universal analysis）。在前一种情况下，必须存在至少一条路径使指向关系有效；在后一种情况下，指向关系必须在所有路径上均有效。

本章只关注可能指向分析。

C指针分析

定义4.1：假设p是一个指针。如果一个指针抽象映射p到Unknown， $p\rightarrow Unknown$ ，当p会指向运行时所有可以获取对象。

约束4.1：（1）不存在指针类型的全局变量可能被其他单元修改。（2）假设函数对于所分析的翻译单元是静态的。

描述函数 strdup() 返回一个指针指向 “Unknown” 对象。

安全指针抽象

一个指针抽象是一个映射，将抽象程序对象（变量）映射到到抽象地址集合。如果对于每个指针类型的对象，其在运行时可能包含的具体地址集合都能被抽象位置集合安全地描述，那么这种抽象就是安全的。举个例子，如果指针p包含x的地址和g的地址，那么抽象 $p\rightarrow\{x,g\}$ 是安全的。

本节将定义抽象地址并对安全做出严谨的概念定义。我们提出了一种可用于检查抽象安全性的规范。该规范奠定了发展约束指针分析的基础。

抽象位置

一个指针是一个包含特定常量NULL或地址的变量。由于强制类型转换，一个指针可以指向任何地址。一个对象时一个逻辑上相关的地址，例如四个字节代表一个整数值。自从指针可以指向函数，我们也将函数视为对象。

一个对象可以被分配到程序栈上（局部变量），在一个给定的位置（字符串和全局变量），在代码空间（函数），或者是在堆上（运行时分配的对象）。我们只关注通过 “alloc ()” 调用在运行时分配的对象。假设所有的调用都被独立标记。 $alloc^{l}()$ 的标记 $l$ 被用来表示在 $alloc^{l}()$ 调用点分配的（匿名）对象。标记 $l$ 也许会被认为作为一个相关类型的指针。

定义4.2：抽象位置集合 ALoc 按如下方式归纳定义：

如果v是全局变量的名字： $v\in ALoc$
如果 v 是某个具有 n 个变体的函数的参数： $v^{i} \in ALoc , i=1,...,n$
如果v是一个有n个变体的函数中的局部变量， $v^{i} \in ALoc$
如果v是一个字符串常量： $s \in ALoc.$
如果f是一个有n个变体的函数的名字： $f^i \in ALoc$
如果f是一个有n个变体的函数的名字： $f^i_{0} \in ALoc$
如果l是一个在有n个变体的函数中的分配标签： $l^i \in ALoc.$
如果l是一个在有n变体函数中的地址操作符： $l^i \in ALoc.$
如果 $o \in ALoc$ 标记一个类型为array的对象： $o \in ALoc$
如果S是一个联合体或结构体的类型名： $S \in ALoc.$
如果 $S \in ALoc$ 并且S是结构体或是联合体： $S.i \in ALoc\ for\ all\ fields\ i\ of\ S$
$Unknown \in ALoc$

名称被假定为独特的。

很明显，对于所有程序集合ALoc都是有限的。这个分析将指针映射到ALoc集合中的元素。元素Unknown标记一个任意（不知道）地址。这意味着该分析进行了如下抽象。

函数调用根据程序静态调用图进行折叠。这意味着有n个变体的函数f，只考虑n个参数和局部变量的实例。例如，由于堆递归函数施加的1限制，递归函数调用链中参数的所有实例都被视为相同。与函数f关联的位置f0表示一个抽象返回位置，即f传递其结果值的唯一位置。

数组被视为聚合体，即所有元素被合并处理。结构体对象中的相同名字的字段被合并，例如给一个定义：

1
2
3

struct S{
    int x;
}s,t;

字段s.x和t.x都被折叠。

独特的抽象地址Unknown代表了一个任意，不知道的地址，可以是合法的也可以是不合法的。

即使抽象地址的定义实际上是针对特定程序的，但我们将继续独立于程序使用ALoc这一表示。更进一步，我们假定对象的类型被一个抽象地址代表是可用的。举个例子，我们写“如果s属于ALoc是结构体的类型”，表示“如果一个对象S属于ALoc所表示的对象是结构体类型”。最终，我们隐含地假定一个从函数设计器到参数的绑定。如果f是一个函数标识符，我们写 $f:x_i$ 对于一个f的参数 $x_i$ 。

指针抽象

一个指针抽象 $S : ALoc \rightarrow ALoc$ 是一个从抽象地址到抽象地址集合的映射

第一个条件要求基本类型的对象被摘要为Unknown。这个想法是值可以被强制类型转换为指针，因此是Unknown。第二个条件明确要求结构体对象的抽象值是一个空的集合。请注意，一个结构体对象由其类型唯一标识。第四个条件要求一个数组变量指向器内容。最终unknown地址的内容为unknown。

定义对于 $s \in ALoc \backslash \{Unknown\}:\{s\}\subseteq \{Unknown\}$ 。然后，两个指针抽象按集合包含关系排序。一个程序有一个最小的指针抽象。给定一个程序，我们想要最小的安全指针抽象。（s是ALoc中的一个元素，但不等于Unknown）（单集合元素s是Unknown的子集）

安全指针抽象

直觉上来看，一个指针的抽象对于一个程序是安全的对于所有的输入，每个对象一个指针可能指向的在运行时被这个抽象捕获。

让一个抽象函数 $\alpha : Loc\rightarrow ALoc$ 被一种明显的方式定义。举个例子，如果 $l_x$ 是函数f调用中对应第i个变体的参数x的位置，那么 $\alpha(l_x)=x^i$ 。从初始程序点 $p_0$ 的一个执行路径和一个初始程序存储 $S_0$ 被表示为

$<p_0,S_0>\rightarrow...\rightarrow<p_n,S_n>$

假设p是一个程序， $S_0$ 是一个初始存储（从程序输入映射到目标函数参数）。让 $p_n$ 是一个程序点，让 $L_n$ 是所有可见变量的位置。一个指针抽象S相对于程序点p是安全的，当且仅当

指针分析说明

ctype是用于验证变量声明的类型是否符合指针抽象的安全规则，确保变量的抽象类型与其声明类型一致。

ptype用于描述指针类型的抽象规则，特别是针对结构体、联合体、数组等复杂类型的指针。

petype专门用于处理extern声明的外部变量，强制其指针抽象为Unknown，以应对多模块程序中外部变量无法静态确定指向的问题。

声明相关推理规则

当声明基础类型变量（如整数、浮点数）时，其指针抽象必须被近似为 “未知”（Unknown）。
当声明指针变量（如int* p）并初始化时，其抽象结果必须包含所指向的对象。
对于extern声明的外部变量，其指针抽象必须强制设为 “未知”。
结构体或联合体变量本身不直接作为指针目标，其字段的指针抽象需通过后续表达式规则处理。
数组变量的指针抽象映射为其聚合类型（例如数组名a映射为a[]），表示指向数组的内容。

表达式相关推理规则

解引用操作规则（*p）：若指针p的抽象结果包含对象o，则解引用*p的抽象结果为o所指向的对象集合。
地址获取操作规则（&x）：对变量x取地址时，生成唯一标签（如l）表示该地址，且标签的抽象结果必须包含x。
类型转换规则（Casts）：
- 安全转换：结构体指针转换为其首成员指针时，抽象结果为该成员的位置（例如结构体S的首成员为x，则S*指针转换为int*时，抽象结果为S.x）。
- 不安全转换：指针与整数之间的转换、不明确的结构体转换等，抽象结果为 “未知”。
函数调用规则：
- 直接调用：实参的抽象结果必须包含在形参的抽象结果中，函数返回值存入抽象的返回位置（如f_0）。
- 间接调用（函数指针）：需考虑指针可能指向的所有函数，将所有可能的函数返回位置纳入抽象结果。

语句相关推理规则

赋值语句规则（p = q）：左值p的抽象结果必须包含右值q的抽象结果，即p的可能指向包含q的所有可能指向。
返回语句规则（return e） ：函数的抽象返回位置（如f_0）必须包含返回表达式e的抽象结果，确保返回值的指针指向被正确捕获。
指针算术与运算符规则：
- 指针减法等操作的结果抽象为 “未知”（如p - q的结果为整数，无法确定指针指向）。
- 单指针偏移（如p - 1）假设指针仍在数组范围内，保守地保留原指针的抽象结果。