Dfi：一个面向大规模代码库的过程间价值流分析框架

解决痛点

由于内存和运行时需求较高，目前的价值流计算方法无法扩展到大型代码库。

价值流分析

价值流分析是数据流分析的一个子集，它有助于静态地分析变量和内存块等程序结构之间的依赖关系。它支持许多关键的程序分析技术，这些技术被广泛用于编译器优化和寻找安全漏洞：指向分析、空指针分析和污点分析。为了有效地操作，这类技术通常需要精确的价值流信息，这些信息具有上下文和流敏感以及过程间性。” <span class="citation" data-citation="%7B%22citationItems%22%3A%5B%7B%22uris%22%3A%5B%22http%3A%2F%2Fzotero.org%2Fusers%2F8438660%2Fitems%2FMZGEWCFE%22%5D%2C%22locator%22%3A%221%22%7D%5D%2C%22properties%22%3A%7B%7D%7D" ztype="zcitation">(<span class="citation-item"><a href="zotero://select/library/items/MZGEWCFE">Hsu 等, 2022, p. 1</a></span>)</span>

创新点

• 开发一种新的图结构，采用LLVM IR扩展，多了两个操作，简化指针混淆的建模
• 由上个方式产生的用于价值流分析的def-use链的轻量级和精确的稀疏表示，包含顶层变量和获取地址的变量
• 一个通过图可达性求解价值流的算法，该算法的规模几乎与处理的顶点数量成线性关系，需要的内存显著减少，而且显著快于以前的解决方案
• 基于LLVM IR，可扩展到包含数十万行代码的大型现实项目

DFI 设计与实现

DFI主要包括两个主要组成部分：

• 主分析引擎
• 客户端分析

首先，分析引擎基于客户端提供的价值流映射信息计算得到运行过程内的DFT间隔；

其次，过程内的价值流被传递到它们的调用者以支持过程间查询；

最后，客户端分析将受到流和上下文敏感的价值流结果，以解决其领域特定的作用

预处理：修改了两个操作

dfi.store：将更新的存储量用不同的标记存储，使得可以用跟踪标量值相同的方法跟踪强更新的内存依赖dfi.call：为捕获输出参数传输的价值流，DFI将llvm.call替换为dfi.call

程序内（运行过程内）分析：

价值流分析可以归结为一个图可达性问题，其中每个顶点都是程序点上的数据流事实，通过判断两个顶点的可达性来解决价值流分析问题。

核心思想：对于一个给定的价值流分析问题，如果程序中的每一个相关操作都被注释为DFT区间，那么可以通过比较任意两个操作在几乎恒定时间内的区间来判断它们之间的可达性。
为了演示这个概念，图3给出了一个MLIR函数，其中的值用DFT区间进行了标注。例如，值% p和% 1的区间分别为⟨0，5和⟨1，4。这些区间标注在由SSA定义-引用图衍生的生成树上，由从单个SSA值定义到其用途的边组成。假设对图3进行污点分析，% p为污点值。为了判断返回值% 3是否被污染，只需检查其区间⟨2，3 “是否被% p⟨0，5 “所包含。在这种情况下，由于⟨0，5⋅⊇⟨2，3⋅根据我们在2.3节的定义，返回值是污点。事实上，% 1和% 3都是污点，因为它们的区间都在⟨0，5 “的子树内。另一方面，间隔为⟨7，8的% 0不被污染，因为它位于以⟨6，9为根的不同DFT子树中。”
为了计算图3所示的树和相关区间，客户端分析自定义了2.3节中介绍的遍历机制。首先，对于每个函数，客户端分析选择一组根顶点开始遍历。注意，每个函数中的遍历时间戳总是从零开始。其次，对于函数中的每个顶点，通过客户端分析提供一个局部转移函数来指示离开的顶点进行下一次访问。在图3污点分析的背景下，客户端分析选择% a和% p作为遍历根。对于局部传递函数，每类运算的规则如图4所示。以dfi . store规则为例，其中仅当存储值% v被污染时，结果指针% q才被污染。它有效地停止了从% p到% q的DFT遍历，但允许从% v到% q的路径。” <span class="citation" data-citation="%7B%22citationItems%22%3A%5B%7B%22uris%22%3A%5B%22http%3A%2F%2Fzotero.org%2Fusers%2F8438660%2Fitems%2FMZGEWCFE%22%5D%2C%22locator%22%3A%225%22%7D%5D%2C%22properties%22%3A%7B%7D%7D" ztype="zcitation">(<span class="citation-item"><a href="zotero://select/library/items/MZGEWCFE">Hsu 等, 2022, p. 5</a></span>)</span>

DEF-USE的非树边

非树边的存在抑制了图的可达性在一般SSA的DEF-USE图上的应用，因此，减少非树边是一件很必要的事情。

采用反转图：可以有效避免多参数情况下的函数产生的非树边问题。

增广DFT区间图的可达性：在遇到非树边时复制区间，以此可以使用两个区间之间相似的包含关系确定它们的可达性

• 区间集Π:
  其中每个元素之间至少有一个时间戳，满足：

• 区间包含关系，若区间中任意子区间（可以是一个元素）对另一区间存在包含关系，则该区间集包含另一区间：

• 区间合并：两个区间可以通过∪操作合并。在可达性算法中，每个DEF-USE图的顶点v和一个区间集相关联。vi可以达到vj需满足两个区间集存在包含关系，即：

• 例子

  交集运算符<span style="background-color: #ff666680">（成立前提？）</span>

  交集运算符指定价值流如何从不同的程序路径进行组合，例如在控制流合并点。在我们的算法中，我们使用区间集合merge∪作为我们的相遇算子。根据我们之前对∪的定义，合并后的区间集总是对传入的区间集的一个安全近似，从而保证了可靠性。” <span class="citation" data-citation="%7B%22citationItems%22%3A%5B%7B%22uris%22%3A%5B%22http%3A%2F%2Fzotero.org%2Fusers%2F8438660%2Fitems%2FMZGEWCFE%22%5D%2C%22locator%22%3A%226%22%7D%5D%2C%22properties%22%3A%7B%7D%7D" ztype="zcitation">(<span class="citation-item"><a href="zotero://select/library/items/MZGEWCFE">Hsu 等, 2022, p. 6</a></span>)</span>

  程序间过程分析

  通过构建一个函数价值流摘要来总结每个函数的价值流。这个价值流摘要被传递到所有它的调用点。由于新引入的被调用方会改变调用方函数内部的价值流，因此该过程将重复执行，直到达到一个固定点。

  函数价值流摘要由函数参数和输出结果之间的一组可达关系组成。摘要描述了参数和结果之间的映射，该映射通过参数和结果索引来表示。

• 结果索引等于dfi.call操作的结果列表中对应的索引。

• 调用时，原始返回值（若有的话）的索引为0，后面跟着指针参数类型的结果

  我们记I ( p )为参数p的参数指标。此外，O ( p )被定义为p的结果指标，如果p是PT_f的一部分，PT_f是f包含所有指针参数的函数参数的子集。函数f的价值流汇总记为Sf = S^R_f∪S^P_f。集合S^R_f和S^P_f分别表示从函数参数到返回值和输出参数的映射。Rf和Pf是f返回值和参数的集合，S^R_f被定义为：

  SPf捕获应用于函数f中的指针参数的潜在价值流。它包含指针参数和DFI.call上相应输出结果之间的映射由于指针参数的结果再被调用方中难以定位，因此DFI使用了指针参数和反向根之间的可达性作为近似结果处理。对于任意两个指针参数p0和p1，用和

  对SPf进行初始化。如果p0和p1都可达逆根┏，那么就可以把和

  这两个可达条件添加到SPf中，令Tf是f的逆根集合，SPf就被定义为：

• 两个例子

• 列表3：由于存在包含关系因此a，c可达r，SRf == Sf，为：

• 列表4：k’和r’分别对应k和r在一个调用点的结果。由于k和r都可达t1，因此SRf：

  价值流摘要值的传播：将被调者函数的价值流摘要传播到调用者，以便将上下文敏感的价值流信息添加到调用者函数

  得到这些摘要值Sf后，需要将Sf传播到所有调用f的节点。在更高层次（？）上，Sf提供了每个调用f节点所缺的本地价值流映射。通过这些信息可以在调用者函数中添加新的价值流以提高精度。传播包括两步：

• 第一步：对于Sf中每个vs -> vd，在每个调用函数中执行另一轮的反向DFT遍历。不过不采用客户端分析的假根，而是采用vs的实际参数作为反向根。

• 第二步：使用第一步的结果在每个调用点上以相反的方向传播

• 一个例子：

  • 第一步：从第八行调用f。在这里使用%s0和%b（实际参数的%v %p）作为反向根进行反向DFT遍历
  • 第二步：将第一步得到的%s0和%b的区间集在增广DFT中过渡性地合并到其父节点和祖先节点（如%s3）的区间集合中，直到达到原来的反向根

采用的算法是使用一个基于工作表的算法，递归地改变总结传播给其调用者，直到达到一个固定点：
在算法1中，GetV FSummary ( f )返回函数f的Sf；PropagateSummary( Sf , c)在调用函数c中执行前面介绍的带有被调用者值-流摘要Sf的两阶段传播。 <span class="citation" data-citation="%7B%22citationItems%22%3A%5B%7B%22uris%22%3A%5B%22http%3A%2F%2Fzotero.org%2Fusers%2F8438660%2Fitems%2FMZGEWCFE%22%5D%2C%22locator%22%3A%227%22%7D%5D%2C%22properties%22%3A%7B%7D%7D" ztype="zcitation">(<span class="citation-item"><a href="zotero://select/library/items/MZGEWCFE">Hsu 等, 2022, p. 7</a></span>)</span>

可达功能的摘要：将传播过程扩展到一个可达函数的摘要。

通过区间集Π vb⊇Π va确定两个值va和vb在同一函数中的可达性，可以计算具有流量和上下文敏感性的程序间的价值流。在这一部分中，将这种能力推广到任意函数中的va和vb。
一个可达函数摘要Ψ ( ε )提供了一个从端点ε到可通行端点集合的映射。端点εⁱ_f表示函数f的第i个参数。

• 一个例子：

• ε

  ⁰

  _f

  的摘要值为：

对于函数所有的所有参数，Ψ被反复传播到它的所有调用者，并与它们的摘要值合并，直到达到一个固定值，即所有可达函数的摘要值都不发生变化为止。

对于某个可达函数摘要，可以执行一个两阶段的过程来回答不同函数中的va->vb是否是可达的：

1. 计算集合 检查对于任意的索引j是否包含函数g的端点ε

   ^j

   _g

   。

2. 只有当前端点ε

   ^j

   _g

   可以达到vb时，va才能达到vb，即：

评估

回答两个问题：

• 在大型代码库上的扩展效果如何，如其他的价值流分析工具相比？

• DFI中回答图的可达性的效率与每个顶点关联的区间集的大小强相关。在所有顶点上间隔集的大小分布如何？

  

所有实验在10分钟内完成，使用的物理内存不超过4.5 GB。