课程网站，课程视频，讨论，作业。

课程网站，在线评测，课程视频，silverbullettt。

知难而进，贵在坚持。省察体悟，贵于改过。

Course Introduction

概念

程序设计语言（Programming Languages，PL），静态程序分析（Static Program Analysis），莱斯定理（Rice’s Theorem），可靠性（Soundness）和完备性（Completeness）。

莱斯定理说明，不存在完美的静态分析，满足 Sound（Overapproximate）和 Complete（Underapproximate）。Sound 允许误报（false positives），但不允许漏报（false negatives），Complete 相反。

静态分析可以使用两个词概括：Abstraction + Safe-approximation（Transfer functions，Control flows）。首先对数据做抽象，然后对数据流做近似。近似涉及到 Transfer functions 如何设计和 Control flows 如何合并。Safe-approximation 的含义取决于使用场景，在大多数场景 Sound 就是 Safe-approximation，而小部分场景 Complete 才是。

问题

Q：关于静态分析，思考 What、Why、How？

Q：如何使用一句话概括静态分析？什么是有用的静态分析？

A：在确保 Safe-approximation 的前提下，在精度（precision）和速度（speed）之间权衡。

参考

Intermediate Representation

概念

编译器（Compiler），中间表示（Intermediate Representation，IR），三地址码（Three-Address Code，3AC），控制流图（Control Flow Graph，CFG），基本块（Basic Block，BB）。

问题

Q：如何基于 3AC 构建 BB？如何基于 BB 构建 CFG？

参考

Data Flow Analysis - Applications

概念

数据流分析的种类：may analysis（over-approximation），must analysis（under-approximation）。

数据流分析的应用：Reaching Definitions Analysis，Live Variables Analysis，Available Expressions Analysis。

问题

Q：为什么 Reaching Definitions Analysis 的算法最终会停止？

A：所有的 OUT 对应的 Bit Vector，它包含的 1 的数量都是单调递增的，最后必定会到达一个上界。

Q：为什么 Live Variables Analysis 使用 Backward Analysis，而不是 Forward Analysis？（算法设计更方便）

参考

Data Flow Analysis - Foundations

概念

不动点（Fixed point），偏序集（Partially ordered set），上确界和下确界（LUB and GLB，Join and meet），格（Lattice），不动点定理（Knaster–Tarski theorem），抽象解释（Abstract interpretation）。

Data Flow Analysis	Domain	Direction	May/Must
Constant Propagation Analysis	Set of pairs (variable, value)	Forwards	Must

问题

Q：什么是 Meet-Over-All-Paths Solution（MOP）？MOP 和 Iterative Algorithm 的精度有什么关系？

Q：为什么 Constant Propagation Analysis 的 Transfer function 是不可分配的（Non-distributivity）？

Q：如何理解可能存在多个不动点，以及 Iterative Algorithm 求到的是最小/最大不动点？为什么在 Constant Propagation Analysis 中，MOP 的精度大于 Iterative Algorithm 的精度？MOP 是否满足不动点定理？

A：对于函数 \(F\) 而言，可能有多个 \(x\) 使得 \(F(x)=x\)，所以可能存在多个不动点。由于 Iterative Algorithm 满足不动点定理，对于特定的函数 \(F\)，如果存在多个不动点，我们求到的必然是最小/最大不动点。MOP 和 Iterative Algorithm 的函数 \(F\) 不同，所以 MOP 的精度可以更大，不会违背不动点定理。MOP 应该是满足不动点定理的，因为 Transfer function 和 Join/Meet function 相比 Iterative Algorithm 没有变化，只是它们组成的函数 \(F\) 有变化。

参考

Interprocedural Analysis

问题

Q：什么是 CHA？如何基于 CHA 构建 Call Graph？

Q：如何实现 Interprocedural Constant Propagation Analysis？

参考

Pointer Analysis

问题

Q：Pointer Analysis 和 Alias Analysis 的区别？

A：Pointer Analysis 回答一个指针能指向哪些对象，Alias Analysis 回答两个指针是否能指向同一个对象。

Q：各个 Factor 的方案该如何选择，精度和速度的权衡？

A：课程选择 Allocation-site，Context-sensitive，Flow-insensitive，Whole-program。

参考

Pointer Analysis - Foundations

问题

Q：什么是 Pointer Flow Graph（PFG）？如何构建 PFG？

Q：为什么构建 PFG 和在 PFG 上传播指向信息，两个过程相互依赖？以及构建 PFG 和构建 Call Graph 相互依赖？

A：首先需要有 PFG，才能在 PFG 上传播指向信息。而 PFG 节点获得指向信息之后，可能会在 PFG 中添加边。主要原因是 PFG 使用抽象对象的字段 \(o_{i}.f\) 来表示实例字段 \(x.f\)，其中 \(o_{i}\in pt(x)\)，它是动态变化的。为什么不直接使用 \(x.f\) 作为节点，在最开始将所有边建好？个人理解，如果 \(x\) 和 \(y\) 的指向信息存在交集，当更新 \(x.f\) 时需要部分更新 \(y.f\)，这样很难使用图上的算法来实现 Pointer Analysis，所以需要做更细粒度的划分。构建 PFG 和构建 Call Graph 相互依赖，也是取决于 Call Rule 的设计，从而在构建 Call Graph 的过程中会在 PFG 中添加边。

参考

Pointer Analysis - Context Sensitivity

问题

Q：为什么 Instance fields 不需要限定上下文？

A：明确限定上下文的作用是什么，区分对同一个方法的多次调用，也就是区分多次调用中的变量和对象。而对于 Instance fileds 不需要区分什么，它从属于某个对象，该对象已经被上下文限定。

参考

Static Analysis for Security

参考

实验作业

如何减少和检查代码的错误？

① 编写代码前：可以先使用注释梳理逻辑，确定算法步骤。重要！如果遗漏某种情况，之后找错会花费更多时间。遇到不清楚的地方要及时（使用 TODO）标出来，不要想当然。② 编写代码时：不要过早优化。在必要的地方添加断言。当找不到想要的 API 时可以查看继承关系，目标 API 可能在子类中。每完成一个功能，就编写相应的测试用例，尽早发现问题。③ 代码出错时：首先检查逻辑是否有误/遗漏，以及边界条件的处理是否有误/遗漏。然后检查 API 是否存在误用，例如对 API 的功能理解有误，或者误用其他类的相同名称的 API。最后检查文档表述是否存在歧义，或者不清楚的地方，从而在实现细节的理解上存在偏差。④ 找不到错时：如果可以的话，找到正确代码，然后对拍测试。休息一下，或许之后能找到。真的找不到，重写一遍，或许能够发现遗漏的地方。真的真的找不到，寄。

Java 的 ArrayDeque 不能存储 null，而 LinkedList 可以。Deque 的文档有说明：

While Deque implementations are not strictly required to prohibit the insertion of null elements, they are strongly encouraged to do so. Users of any Deque implementations that do allow null elements are strongly encouraged not to take advantage of the ability to insert nulls. This is so because null is used as a special return value by various methods to indicate that the deque is empty.

存储技术

随机访问存储器

随机访问存储器（Random-Access Memory，RAM）分为两类：静态的和动态的。静态 RAM（SRAM）比动态 RAM（DRAM）更快，但也更贵。SRAM 通常用来作为高速缓存存储器，DRAM 通常用来作为主存以及图形系统的帧缓冲区。

静态 RAM

SRAM 将每个位存储在一个双稳态的（bistable）存储器单元里。每个单元是用一个六晶体管电路来实现的。这个电路有这样一个属性，它可以无限期地保持在两个不同的电压配置（configuration）或状态（state）之一。由于 SRAM 存储器单元的双稳态特性，只要有电，它就会永远地保持它的值。即使有干扰（例如电子噪音）来扰乱电压，当干扰消除时，电路就会恢复到稳定值。

动态 RAM

DRAM 将每个位存储为对一个电容的充电。这个电容非常小，通常只有大约 \(30\times 10^{-15}\) 法拉（femtofarad）。DRAM 存储器单元对干扰非常敏感，当电容的电压被扰乱之后，它永远都不会恢复。内存系统必须周期性地通过读出，然后重写来刷新内存每一位。有些系统也使用纠错码，其中计算机的字会被多编码几位（例如 64 位的字可能用 72 位来编码），这样一来，电路可以发现并纠正一个字中任何单个的错误位。

非易失性存储器

如果断电，DRAM 和 SRAM 会丢失它们的信息，从这个意义上说，它们是易失的（volatile）。另一方面，非易失性存储器（nonvolatile memory）即使是在关电后，仍然保存着它们的信息。现在有很多种非易失性存储器。由于历史原因，虽然 ROM 中有的类型既可以读也可以写，但是它们整体上都被称为只读存储器（Read-Only Memory，ROM）。ROM 是以它们能够被重编程（写）的次数和对它们进行重编程所用的机制来区分的。

存储在 ROM 设备中的程序通常被称为固件（firmware）。当一个计算机系统通电以后，它会运行存储在 ROM 中的固件。一些系统在固件中提供了少量基本的输入和输出函数，例如 PC 的 BIOS（基本输入/输出系统）例程。复杂的设备，像图形卡和磁盘驱动控制器，也依赖固件翻译来自 CPU 的 I/O（输入/输出）请求。

总线事务

数据流通过称为总线（bus）的共享电子电路在处理器和 DRAM 主存之间来来回回。每次 CPU 和主存之间的数据传送都是通过一系列步骤来完成的，这些步骤称为总线事务（bus transaction）。读事务（read transaction）从主存传送数据到 CPU。写事务（write transaction）从 CPU 传送数据到主存。

总线是一组并行的导线，能携带地址、数据和控制信号。取决于总线的设计，数据和地址信号可以共享同一组导线，也可以使用不同的。同时，两个以上的设备也能共享同一总线。控制线携带的信号会同步事务，并标识出当前正在被执行的事务的类型。例如，当前事务是到主存还是到诸如磁盘控制器这样的其他 I/O 设备，事务是读还是写，总线上的信息是地址还是数据项。

图 6-6 展示了一个示例计算机系统的配置。主要部件是 CPU 芯片、我们将称为 I/O 桥接器（I/O bridge）的芯片组（其中包括内存控制器），以及组成主存的 DRAM 内存模块。这些部件由一对总线连接起来，其中一条总线是系统总线（system bus），它连接 CPU 和 I/O 桥接器，另一条总线是内存总线（memory bus），它连接 I/O 桥接器和主存。I/O 桥接器将系统总线的电子信号翻译成内存总线的电子信号。I/O 桥也将系统总线和内存总线连接到 I/O 总线，像磁盘和图形卡这样的 I/O 设备共享 I/O 总线。

磁盘存储

磁盘构造

磁盘是由盘片（platter）构成的。每个盘片有两面或者称为表面（surface），表面覆盖着磁性记录材料。盘片中央有一个可以旋转的主轴（spindle），它使得盘片以固定的旋转速率（rotational rate）旋转，通常是 5400 ~ 15000 转每分钟（Revolution Per Minute，RPM）。磁盘通常包含一个或多个这样的盘片，并封装在一个密封的容器内。

图 6-9a 展示了一个典型的磁盘表面的结构。每个表面是由一组称为磁道（track）的同心圆组成的。每个磁道被划分为一组扇区（sector）。每个扇区包含相等数量的数据位（通常是 512 字节），这些数据编码在扇区上的磁性材料中。扇区之间由一些间隙（gap）分隔开，这些间隙中不存储数据位。间隙存储用来标识扇区的格式化位。

磁盘是由一个或多个叠放在一起的盘片组成的，它们被封装在一个密封的包装里，如图 6-9b 所示。整个装置通常被称为磁盘驱动器（disk drive），我们通常简称为磁盘（disk）。有时，我们会称磁盘为旋转磁盘（rotating disk），以使之区别于基于闪存的固态硬盘（SSD），SSD 是没有移动部分的。

磁盘制造商通常用术语柱面（cylinder）来描述多个盘片驱动器的构造，这里，柱面是所有盘片表面上到主轴中心的距离相等的磁道的集合。例如，如果一个驱动器有三个盘片和六个面，每个表面上的磁道的编号都是一致的，那么柱面 k 就是 6 个磁道 k 的集合。

磁盘操作

磁盘用读/写头（read/write head）来读写存储在磁性表面的位，而读写头连接到一个传动臂（actuator arm）一端，如图 6-10a 所示。通过沿着半径轴前后移动这个传动臂，驱动器可以将读/写头定位在盘面上的任何磁道上。这样的机械运动称为寻道（seek）。一旦读/写头定位到了期望的磁道上，那么当磁道上的每个位通过它的下面时，读/写头可以感知到这个位的值（读该位），也可以修改这个位的值（写该位）。有多个盘片的磁盘针对每个盘面都有一个独立的读/写头，如图 6-10b 所示。读/写头垂直排列，一致行动。在任何时刻，所有的读/写头都位于同一个柱面上。

磁盘以扇区大小的块来读写数据。对扇区的访问时间（access time）有三个主要的部分：寻道时间（seek time）、旋转时间（rotational latency）和传送时间（transfer time）。

逻辑磁盘块

正如我们看到的那样，现代磁盘构造复杂，有多个盘面，这些盘面上有不同的记录区。为了对操作系统隐藏这样的复杂性，现代磁盘将它们的构造呈现为一个简单的视图，一个 B 个扇区大小的逻辑块的序列。磁盘封装中有一个小的硬件/固件设备，称为磁盘控制器，维护着逻辑块号和实际（物理）磁盘扇区之间的映射关系。当操作系统想要执行一个 I/O 操作时，例如读一个磁盘扇区的数据到主存，操作系统会发送一个命令到磁盘控制器，让它读某个逻辑块号。控制器上的固件执行一个快速表查找，将一个逻辑块号翻译成一个（盘面，磁道，扇区）的三元组，这个三元组唯一地标识了对应的物理扇区。控制器上的硬件会解释这个三元组，将读/写头移动到适当的柱面，等待扇区移动到读/写头下，将读/写头感知到的位放到控制器上的一个小缓冲区中，然后将它们复制到主存中。

局部性原理

局部性通常有两种不同的形式：时间局部性（temporal locality）和空间局部性（spatial locality）。在一个具有良好时间局部性的程序中，被引用过一次的内存位置很可能在不远的将来再被多次引用。在一个具有良好空间局部性的程序中，如果一个内存位置被引用了一次，那么程序很可能在不远的将来引用附近的一个内存位置。

存储器层次结构

存储器层次结构的中心思想是，对于每个 k，位于 k 层的更快更小的存储设备作为位于 k + 1 层的更大更慢的存储设备的缓存。换句话说，层次结构中的每一层都缓存来自较低一层的数据对象。数据总是以块大小为传送单元（transfer unit）在第 k 层和第 k + 1 层之间来回复制的。虽然在层次结构中任何一对相邻的层次之间块大小是固定的，但是其他的层次对之间可以有不同的块大小。

高速缓存存储器

早期计算机系统的存储器层次结构只有三层：CPU 寄存器、DRAM 主存储器和磁盘存储。不过，由于 CPU 和主存之间逐渐增大的差距，系统设计者被迫在 CPU 寄存器文件和主存之间插入 SRAM 高速缓存存储器。

缓存不命中的种类：强制性不命中/冷不命中、冲突不命中和容量不命中。

高速缓存的种类：直接映射高速缓存、组相联高速缓存和全相联高速缓存。

写的策略：直写 + 非写分配、后写 + 写分配。

组织结构

考虑一个计算机系统，其中每个存储器地址有 \(m\) 位，形成 \(M=2^{m}\) 个不同的地址。如图 6-25a 所示，这样一个机器的高速缓存被组织成一个有 \(S=2^{s}\) 个高速缓存组（cache set）的数组。每个组包含 \(E\) 个高速缓存行（cache line）。每个行是由一个 \(B=2^{b}\) 字节的数据块（block）组成的，一个有效位（valid bit）指明这个行是否包含有意义的信息，还有 \(t=m-(b+s)\) 个标记位（tag bit）（是当前块的内存地址的位的一个子集），它们唯一地标识存储在这个高速缓存行中的块。