@article{navas2022occam,
title={OCCAM-v2: Combining Static and Dynamic Analysis for Effective and Efficient Whole-program Specialization: Leveraging scalable pointer analysis, value analysis, and dynamic analysis},
author={Navas, Jorge A and Gehani, Ashish},
journal={Queue},
volume={20},
number={5},
pages={58--85},
year={2022},
publisher={ACM New York, NY, USA}
}
OCCAM-v2：
0 摘要
软件已发展到可以支持多样的功能集。灵活的软件工程实践，如为重用行设计而引入的冗余代码。在更常见的模式中，整个库被链接，然而实际上只需要其中的少数功能。这些额外代码的积累可能会对只需要访问功能子集的应用程序产生负面影响。
嵌入式系统通常只有有限的内存，不必要的代码占用的空间回增加成本并对性能产生不利影响。云计算平台可能会因为臃肿的代码增加内部攻击面，通过 return-oriented programming，jump-oriented programming，和call-oriented programming等机制
随着配置参数的增加，程序的轨迹空间呈指数增长。这使得全面测试成本的增加，这次进了全程序特化的需求，这可以将程序分析集中在将要部署的特定版本上
由于LLVM中间代码可以编译多种源语言，目前已经有一些工具来特化LLVM bit码，包括OCCAM[13]，LLPE[20]，Trimmer[19]. 然而，它们只能使用编译器转换来完成任务，相比之下，我们的工具OCCAM-v2，结合了更深入的静态分析，实用抽象解释框架，以及鼎泰分析。这种组合提供了更好的结果。
OCCAM-v2是我们之前工具OCCAM的扩展。将自动化构建复杂bit码的功能分解为一个单独的工具gllvm[8]。本文首先提供关于OCCAM的相关背景，然后描述其静态分析扩展，这些扩展提供了与OCCAM相同的健全性保证。接下来，将解释了使用了动态分析的可选的激进特化，最后报告了在一组应用程序上评估该工具的结果。
1 背景
OCCAM-v1 使用部分估值法来简化大的应用和他们的依赖，如下图示（虚线框内的组件是 OCCAM-v2 中新增的。）
具体而言，OCCAM 允许将静态信息通过一个包含特定环境细节的专用清单传递给目标程序的入口。该工具工作在LLVM bit码上，这是一个中间表示，可以从多种源语言编译。
每个模块的函数和调用点被计算并保存在外部接口定义中，利用这个信息，OCCAM接着搜索具有具体参数的跨模块调用，如果找到这样一个调用，将根据策略确定是否需要特化该函数。 当这种情况发生时，会构建新函数的代码并将其添加到相关的LLVM位代码模块中，相应的接口将被更新以反映新函数的特征；具有相同签名的其他调用点将使用特化版本
OCCAM从程序入口出发，并使用应用程序清单所提供的任何静态信息。然后对包含在main中的调用点所识别的函数模块进行特化，该过程一直持续到找到所有可达模块。在每个步骤中，调用LLVM的内部优化。特别是，使用全局优化器进行进行常量折叠和传播，去除死代码，修建未使用的分支和不可达代码，这也是OCCAM的模块内特化。
由于这个过程可能会发现新的特化机会，所以整个过程将持续到能够达到全局稳态。通过这种方式，OCCAM能够完成整个程序的特化，在最后一步，OCCAM调用LLVM的编译器将位码转换为本机对象，并调用链接器生成特化的本机应用。
2 扩展的的静态分析
OCCAM-v2 的静态分析改进源于它引入了自定义指针分析和值分析。这两者都基于抽象解释。
LLVM 的 PoolAlloc DSA（数据结构分析）可以被OCCVM-v2使用来解析间接函数调用以及其他指针。
OCCAM-v2 使用了改进的 DSA 变种计算的调用图：开源的类型敏感指针分析工具 SeaDSA。
2.1 更精确的调用图构造
跨模块接口的改进
为了支持对大型软件的应用，OCCAM一次只对一个模块进行操作。
然而为了促进整个程序的分析，对一个模块的更改必须意识到该模块与其它代码的交互。
通过对每个模块构建一个接口来实现这一点，该接口在更新其它模块的过程中使用。
特别地，接口提供了在模块内使用的外部符号和调用的描述。
OCCAM-v1中，接口生成使用了LLVM计算的调用图，OCCAM-v2 使用了由 SeaDSA 计算的调用图。这个调用图比LLVM的更精确。
这反过来提高了模块接口的特异性，从而优化了跨模块的特化
当一个模块的接口被计算出，它刚开始包括所有的非内部链接调用点（因此可以跨模块调用）。
此外，到达函数的来自其它模块调用的调用点也会被识别出来
这些调用是在间接的情况下，目标可以是任何函数，使用已经解析的调用图，OCCAM-v2减少了可能的集合
处理函数指针参数
当对一个在模块外的函数进行调用时，其签名会出现在包含调用方的模块的接口中
当调用点包含一个常量参数时，可以对调用进行特化；如果参数是一个函数指针，OCCAM 仅限于使用 null 值的情况，这无法处理将函数作为参数按引用传递的情况
OCCAM-v2 支持对具有函数指针参数的外部调用进行特化。如果在调用方的上下文中函数接受一个或多个常量参数，那么该函数现在也可以被专门化。这是特别值得注意的，因为它涵盖了常见的编程模式，如回调函数的使用。
基于签名的候选调用消除
使用DSA会导致对实际程序的调用图的过度估计，因为DSA忽略了函数调用参数的类型，因此，具有与调用点签名不匹配的函数可能被错误地认为是有效候选函数
为解决这个问题，通过SeaDSA地的指针分析，将间接调用替换为一个switch语句，其中每个case对应一个候选地址，此后生成的调用图将不含间接调用
在某些情况下，调用点和候选函数地址的签名可能不匹配，该分析可以根据参数类型正确地过滤出这种情况
基于类层次分析的候选调用消除
当间接调用解析为一组候选地址时，生成的调用图与原程序的调用图相比不够精确，通过减少候选集可以提高之后静态分析的精度。如果LLVM比特码的实例源于用C++编写的程序，则可以使用CHG（class hierarchy graph 类层次图）来提高分析的精度
OCCAM-v2构建了一个CHG，其节点是一个C类，两类之间的边表示父子类。CHG用于解析C 虚拟函数的间接调用（指针分析支持C++虚拟调用，但是CHG通常可以通过分析从LLVM比特码中提取的虚拟表的信息来细化SeaDSA的推断）
对于来自C++程序的虚拟调用的调用点，执行以下步骤
确定包含调用方法的对象所关联的类C
计算所有直接或间接派生的C类的子类（CHG可用时该步骤可很快得到）
使用每个子类的虚拟表，手机所有具有与步骤1中提到的被调用方法匹配的类型签名的方法（通过检查比特码构造类的虚拟表）
此时，对于一个间接调用，所有来自虚拟调用的可能的调用被找到，这将允许使用该调用集合的间接调用被解析。
基于别名分析的优化
LLVM框架提供了AliasAnalysis基础结构。
该客户端的API可以查询两个LLVM值是否为别名，这对于在优化目标代码时，两个值不能指向相同位置的变换非常有用。 实现必须对内存建模并支持回答这些查询
SeaDSA实现了AliasAnalysis的API，这使得OCCAM-v2可以使用整个LLVM passes套件来增加指向信息的精度。
改进的别名分析也促进了其它优化，如死存储消除，可以帮助静态变量的识别
2.2 权值分析的使用
OCCAM在简化软件时使用死代码消除，简化算法的核心依赖于构建从变量到常量的映射，这意味着该变量在所有可能的程序执行中都具有可以识别的常量值。
为了创建更多的特化机会，OCCAM-v2构建了从变量到区间的映射，这将使得分支推理依赖于变量的值的范围
抽象解释Abstract interpretation 是一种程序进行形式推理的常用技术，是静态分析设计的数学基础。
该技术的一个经典用途是推断每个程序变量可以取地可能的值。这些可能的值使用不同的方式进行近似（称为抽象域）：区间最大最小值；两个变量间的差异；八角形约束；变量间地线性不等式
尽管该分析很强大，但在LLVM中不可用。
原因之一是大多数实现只考虑整数，而LLVM中的整数为机器算术。将这种分析调整为可以在机器算术中的工作是具有挑战性的，因为很难在精度和效率之间找到良好的平衡
推断不变量
C++库Crab7支持使用抽象解释对程序进行静态分析
Crab在目标程序的CFG（控制流图）上进行操作，该形式语言无关
Clam4前端将LLVM IR转换为Crab的表示形式，随后使用Crab来推断目标程序中的不变量，通常接着进行常量传播和死代码消除（使用LLVM passes优化）。 已识别出的不变量可以让passes作出更强的假设，达到更好的优化
字段敏感的常量传播
OCCAM的模块内特化依赖于LLVM的SCCP (sparse conditional constant propagation)。
这个pass在分析时受到限制，因为其设计是 为了效率，在编译器的工作流程中使用
特别是，如果常量存储在C数组或结构体字段中,SCCP无法识别这个静态数据
Clam 依赖于SeaDSA的字段敏感推理来维护内存的抽象表示。
SeaDAS将内存划分为有限的区域，每个区域映射到一个逻辑数组，此时，区域由一个逻辑表达式建模，该表达式描述了受内存访问操作影响的位置。这使得能够有效地推理关于由SeaDSA处理的内存的情况，其中包括别名分析。
当LLVM位码转化为crab的CFG时，内存存储被建模位弱更新（知道受影响区域但确切位置不知道）。clam为若更新定义了一个抽象与，crab在CFG推理时使用。
虽然在域中推理是高效的，但不够精准，为了提高精准度，特别在结果体字段的情况下，开发了一种新的抽象域。其提供了混合抽象，这里在特殊情况下，内存被建模为强更新（将旧值替换为新值）
函数内部分析的优化
对不变量的了解有助于编译器优化，提高了OCCAM-v2的特化和消除目标应用程序及其依赖中代码片段的能力。
为此，我们开发了一种上下文敏感的构成分析，提供了比基础型更高的精准度。
为了提高性能，增加对函数内部分析备忘录。 尽管可能导致内存的额外消耗，但可以通过限制备忘录大小随后同构循环利用解决
3 集成的动态分析
作为在线部分求值器，OCCAM依赖于具体的已知的代码简化。
这些信息的一个重要来源是用户指定的参数集，在实践中，这些参数由类似于getopt()的功能在程序入口附近处理。
这样的代码通常在循环中处理复杂字符串操作，此外，循环的界限可能不是静态的，这对静态分析技术构成了挑战
OCCAM-v2的DCA（deployment context analysis）将特化分为两个阶段
从概念上讲，目前程序的执行跟踪为第一阶段的前缀，使用动态分析计算，同时在第一阶段后缀也有，用于代表第一阶段未执行的程序
动态分析从程序入口开始，只要仍处在关键的混合状态，动态分析就要继续。具体来说，任何分支选择必须取决于已知的值
内存快照是前缀执行结束时的程序状态。它用于使用静态分析简化后缀。
这个功能是通过修改LLVM的解释器lli来实现的。这个新的passes与lli有三个不同之处：
当遇到虚拟寄存器或在栈或堆上分配的内存位置的值，在执行期间可能是未知的。例如，程序可能使用第一个参数的值（在C中称为argv[1]），但在运行时用户可能在调用程序时没有提供任何参数。在这种情况LLVM解释器将中止执行。相反，新的pass将移动到下一个位代码指令并继续解释。
当遇到值未知的寄存器或内存位置时，新的传递将跟踪此事实。当后续指令依赖于未知值时，其结果也将被跟踪为未知。通过这种方式，新功能提供了一种轻量级的绑定时间分析，将动态值的污点向前传播。
在解释的位代码指令是依赖于未知值的条件时，执行将被停止。这使得程序可以在分支存在的情况下继续运行，只要可以评估它们。停止执行的条件是为了避免探索潜在的指数级状态空间，如果必须跟踪依赖于未知值的分支，将会导致这种情况发生。
选项处理
多模块动态分析
保守排除
变量函数
处理算术内在函数
暴露封装的 libc 调用
4 评估
使用20个应用软件，是Trimmer中使用的，在Trimmer中有解释原因
Ubuntu 18.04 ，LLVM 10
Effectiveness 效果
程序被编译成LLVM位码，随后位码中指令的数量。
分别计算 仅使用静态分析的OCCAM-v2，使用静态分析和动态分析的OCCAM-v2 删除指令的百分比
每种情况下，特化上下文于Trimmer评估中的上下文相同。
从数据中可以看出，OCCAM-v2动态分析和静态分析结合总是比单独使用静态分析可以删除更多的指令，平均而言，OCCAM-v2的混合分析可以删除原程序40.6%的LLVM IR指令
Efficiency 效率
OCCAM-v2的静态分析被设计为 支持大规模且高效，必要时可以牺牲精度来换取效率。具体来说
所使用的指针分析基于Bjarne Steensgard的算法
抽象解释框架配置为仅使用计算上高效的推理域，包括布尔值、区间和步幅
因此当使用静态分析模式时，平均特化时间为6.7s
与Trimmer进行对比，其使用基于Lars Andersen的算法的指针分析（在SVF框架中实现）来选择精度而非可伸缩性。这一效果可以在配置注释通行证的成本中看到。
对于Trimmer分析时间最长的三个程序，它们分别是objdump、yices和gprof，其分别使用了41.4、23.6和16.3分钟。
相比之下，OCCAM-v2对这三个程序进行的整个基于静态分析的专门化分别在34、34和27秒内完成。
下图展示了每个程序的特化时间，其中包括静态分析和混合分析的时间。注意时间刻度为指数增长
对于大多数程序，两种方法时间相似，bzip2例外，因为特化被配置为利用目标文件的内容，需要解释器遍历整个运行，尽管有此异常值，混合分析特化平均时间为22.4s
5 限制和缓解措施
整个程序假设
OCCAM假设在特化时可以访问“整个程序”——即目标应用程序及其所有依赖的所有代码。这使得其能够把整个程序中调用的任何代码都可以作为待删除项，这种方法对许多程序有效，但并非对所有程序都适用。
存在多种原因导致这种担忧。
一个重要的情况是，一个对象的源代码必须链接到程序中，但只能以汇编的形式提供。在这种情况下，OCCAM的分析将不会意识到在这样的对象中对外部全局变量的任何函数调用或访问，因为汇编不能构建成LLVM位代码。因此，OCCAM可能会删除所需的符号和函数。我们在musl libc和Linux内核中都遇到过这种情况。
在没有汇编的情况下，也可能发生类似的情况——例如，Apache根据其配置文件动态加载模块。这些模块可能会引入反向依赖性，即主程序包含特定函数的假设，这些函数可能已经基于对它们的调用缺失而被删除。为了解决这些情况，我们在OCCAM-v2中添加了对指定一组不应被内部化的函数和全局变量的支持。这样可以防止死代码消除删除这些元素
链接时符号冲突措施
OCCAM在模块内迭代执行常量传播和死代码消除，以及跨模块的函数特化。当达到一个固定点时，特化的模块被链接在一起。在这个阶段，模块中的符号可能会发生冲突。
符号冲突可能发生在应用程序中使用了相同的符号，以及它的一个库中使用了相同的符号，或者在多个库中定义了相同的符号。特化函数的命名方案最大程度地减少了新冲突可能性。OCCAM-v2通过一个中间步骤解决了这个问题。链接在内部进行分阶段，允许在参数中指定的位代码文件中的符号覆盖后续的重复符号。使用llvm-link构建中间链接的位代码文件，然后使用clang++将其与在清单中指定的本机库链接。
6 未来方向
后缀简化
在完成第一阶段后，内存快照包含两种类型的状态。
第一种类型包括寄存器中的值，可以安全地用于简化后缀。这种简化包括使用LLVM内部的优化，以及由于Crab在配置的域上的抽象解释而可能的优化。
第二种类型包括内存中的值。为了使用这些值，有两种选择。一种方法识别通常情况下安全的特殊情况。第二种方法涉及使用指针分析以确保后缀简化的合理性。由于这会产生显著的计算成本，因此尚未纳入。在未来，可以添加对此的支持，用户将需要在愿意在特化过程中承担开销的情况下显式激活它。
减少过度特化
DCA依赖一个事实，即前缀是目标应用程序将根据特定输入始终执行的路径。这种方法的好处在于，它承诺提供一种捕获外部输入的通用机制。当前的实现探索了一种策略，该策略默认假定这些值与从后缀中获得的值独立。然后，根据需要添加约束来处理违反该假设的特定情况。
例如，考虑快照中的一个变量，它是指向内存位置的指针。假设在动态分析过程中为其分配了一个具体值。如果它在程序的一个后缀中出现，它将不会被替换为常量。这是因为在运行时，该指针可能具有不同的值。在没有这些排除的情况下，生成的二进制将包含过度特化的实例，即错误的正面具体化。另一种策略是实施互补的方法：默认情况下假定值除非来自指定的输入，否则不能被具体化。
7 结论
OCCAM-v2使用可扩展的指针分析，权值分析和动态分析创造了一个高效的特化工具，服务于LLVM位码。
所实现的代码大小减少取决于具体的部署配置。
每个需要特化的应用程序需要伴有一个清单，该清单制定了在运行时提供的已知的具体参数，以及在运行时需要提供的其它参数的数量。
OCCAM-v2使用指针分析来去除虚拟化调用，从而能够消除任何直接调用都无法到达的函数的整体。
混合分析特征可以处理对于静态分析有挑战的情况，例如输入循环，字符串处理和外部数据（如文件中的数据）。
在评估的程序集合中，OCCAM-v2平均能够将指令数减少40.6%,运行时间中位数2.4s
_1.png)
_2.png)
_3.png)