源代码评估（大规模下加速源代码分析）

引用：Upadhyaya G , Rajan H . On Accelerating Source Code Analysis At Massive Scale[J]. IEEE Transactions on Software Engineering, 2017, PP(99):669-688.

摘要

数据驱动软件工程（SE）技术的成功，使我们发现了许多不同的应用，例如在缺陷预测、规范推理、大规模挖掘和分析源代码存储库需求的应用数量均显着增加。但是，对于当今某些无法解决 SE 问题的数据驱动解决方案而言，大规模分析源代码仍然很昂贵。现有技术集中于利用分布式计算来解决该问题，但是随之而来的是计算资源需求的增加。这项工作提出了一种减少超大规模源代码挖掘任务执行计算量的技术，尤其是利用控制和数据流分析的任务。我们的关键思想是在运行挖掘任务之前分析挖掘任务，以识别并删除源代码中不相关的部分。我们展示了我们对挖掘和分析大量源代码控制流图集合的见解。我们使用 16 个经典的控制/数据流分析（它们是挖掘任务的典型组成部分）和 700 万个 CFG 进行评估，结果表明，我们的技术平均可以将任务计算时间减少 40％。我们的案例研究证明了我们的技术在大规模源代码挖掘任务中的适用性。

1 介绍

最近，分析大型源代码存储库以解决广泛的软件工程问题激发了我们极大的兴趣并获取了相应的进展。大规模执行源代码挖掘和分析的方法可能很昂贵。幸运的是，现有的工作集中是在利用分布式计算技术来加速超大规模源代码挖掘，但是随之而来的是计算资源需求的增加。通过增加更多的 CPU 来提高基础架构的功能当然是可行的，但是非盈利基础架构例如 Boa 受到其资源的限制，而在这种任务中使用商业云可能会非常昂贵。

在这项工作中，我们提出了一种补充技术，该技术可以在不需要额外计算资源的情况下加速超大型挖掘任务。给定一个挖掘任务和需要运行挖掘任务的程序的超大型数据集，我们的技术将首先分析挖掘任务，以提取与该挖掘任务相关的部分输入程序信息，然后使用此信息进行预分析，从而在输入程序上运行挖掘任务之前，先从输入程序中删除不相关的部分。我们的技术通过分析挖掘任务源代码自动提取有关语句的信息，并在运行挖掘任务之前从输入程序中删除所有不相关的语句。

贡献。总而言之，我们的论文做出了以下贡献：

• 我们提出了用于扩展源代码挖掘任务的加速技术，该任务可分析数百万个控制流图。
• 我们提供了一个静态分析，该分析分析了挖掘任务，以自动提取与挖掘任务相关的部分源代码信息。
• 我们的证明，通过在运行挖掘任务之前对源代码进行轻量级的预分析，以识别并删除不相关的部分，可以在不牺牲挖掘结果准确性的情况下极大地加快整个挖掘过程。
• 我们已经在 Boa 领域专用语言和基础架构中实现了用于超大规模采矿的技术[10]。
• 我们的评估表明，对于极少的挖掘任务，我们的技术可以将任务计算时间减少多达 90％，而在我们的 16 种分析中，平均可以减少 40％。

2 动机

为了衡量挖掘任务的成本，我们使用三个数据集来挖掘 Java 开发工具包（JDK）1.6 中的所有 3168 种 API 方法：D1（包含 6,741,465 CFG），D2（88,066,029CFG），D3（161,577,735CFG）。 数据集越大，API 前提条件挖掘任务就可以产生更准确的前提条件。在 D1 上运行任务花费了 36 分钟，而 D2 则花费了 8 小时 40 分钟。我们希望任务在 D3 上花费几天，因此我们选择使用分布式计算基础结构在 D3 上运行任务，该任务花费了 23 分钟。从这个实验中，我们可以看到，在没有并行基础架构的情况下进行大规模的源代码挖掘可能非常昂贵。

图 1 来自 Apache Tomcat GitHub 项目的代码片段。

为了详细说明，让我们重新审视 API 前提条件挖掘示例。让我们考虑一下，我们想挖掘 substring（int，int）API 方法的 API 前提条件。图 1 显示了示例客户端方法，该方法在第 7 行调用 substring（int，int）API 方法。此 API 方法调用由第六行的条件冒号> = 0 保护，因此该条件被视为重设条件。为了提取该前提条件，挖掘任务首先构建如图 2 所示的方法的 CFG（CFG 节点号对应于图 1 中的行号）。该任务执行 CFG 的多个遍历。对于此分析，相关的节点为：i）包含 substring（int，int）API 方法调用的节点，以及 ii）条件节点。在图 1 所示的客户端方法中，只有第 6 和 7 行是相关的（图 2 中所示的相应 CFG 中的节点 6 和 7）。所有其他节点都不相关，并且在这些节点上执行的任何计算都不会影响挖掘结果。

在没有我们的技术的情况下，API 前提条件挖掘任务将遍历所有三个遍历中的 CFG 中的所有节点，其中遍历和不相关节点的计算可以避免，以节省不必要的计算。

3 方法

图 3 概述了我们的方法。我们方法的主要三个组成部分是：i）静态分析以提取规则，ii）遍历分析以标识与分析相关的节点，以及 iii）简化以删除与分析无关的节点。

图 2 在图 1 所示代码的 CFG 上进行 API 前提条件挖掘分析时，它将访问 CFG 中的每个节点，并查询这些节点是否具有谓词表达式或 substring（int，int）API 方法调用。 如果是这样，则此类节点与 API 前提条件挖掘相关。

图 3 方法总览

给定一个挖掘任务和一个输入 CFG，而不是直接在输入 CFG 上运行挖掘任务，我们执行轻量级的预分析，该分析为挖掘任务标识了相关节点，并对不相关的节点进行修剪以获得简化的 CFG。静态分析可帮助进行预分析阶段，该静态分析提供了一组规则来标识相关节点。规则集包含 CFG 节点上的谓词表达式，在输入 CFG 的节点上进行评估时，这些表达式有助于识别相关节点。

源代码挖掘任务。 我们为源代码挖掘任务假设以下公式：源代码挖掘任务可能包含一组分析。诸如控制流分析，数据流分析之类的源代码分析可以表示为对控制流图（CFG）的一次或多次遍历。遍历 CFG 中的每个节点并执行一段代码，通常称为分析功能。

图 4 API 前提条件挖掘 Boa 程序

图 4 显示了用 Boa（用于挖掘源代码存储库的领域特定语言）编写的示例 API 前提条件的源代码挖掘任务。

3.1 提取规则以推断相关节点

给定一个包含一个或多个遍历的挖掘任务，我们的静态分析通过构造遍历的控制流图表示并枚举其中的所有非循环路径来分析每个遍历。

定义 1.程序的控制流图（CFG）定义为 G =（N，E，>，⊥），其中 G 是一个有向图，其中节点 N 代表程序语句，边缘 E 代表语句之间的控制流。>和 ⊥ 表示 CFG 的入口和出口节点。

我们使用符号 GA =（NA，EA，> A，⊥A）表示分析遍历的 CFG，并使用 G =（N，E，>，⊥）表示输入到分析的代码集 CFG。 GA 的（控制流）路径 π 是一个有限序列，因此 n1，n2，...，nk∈NA 且对于任何 1≤i A 且 nk =⊥A。一组路径{π0，π1，...}是遍历（或分析函数）的控制流图 GA 中的一组非循环路径。非循环路径包含只出现一次的节点，而循环头节点可能出现两次。静态分析的关键思想是根据两个条件选择所有非循环路径的子集：1）路径包含在输入变量（CFG 节点）上提供谓词的语句，以及 2）路径包含对输入变量起作用的语句 到分析输出。

遍历（或分析函数）的输入变量始终是 CFG 节点，如遍历定义中所述。 例如，在 mineT 遍历定义中，节点是输入变量。 分析函数的输出变量可以是以下三种类型之一：1）遍历返回的变量作为输出，例如，在 domT 遍历的情况下为 doms； 2）全局变量，例如在 apiT 遍历的情况下为 apiCallNodes 和 conditionsAtNodes mineT 遍历，或 3）作为输出写入控制台的变量，例如，在进行 analysisT 遍历的情况下的前提条件。

每个选定的路径都会产生一个作为路径条件的规则。给定遍历（或分析函数）的一组非循环路径，以及遍历的输入/输出变量，算法 1 计算规则集 R，该规则集 R 包含从非循环路径提取的路径条件。对于每个路径，算法 1 访问该路径中的节点并检查该节点是否为分支节点。然后，算法 1 提取输入变量（iv）的别名列表，以检查分支节点是否包含输入变量或其别名（第 8-9 行），如果是，则使用以下命令获取包含在节点中的谓词表达式： 辅助函数 getPredicate（第 7 行）。 getPredicate 辅助函数可以返回 null 或 true 或谓词表达式。

当分支节点的谓词表达式不包含任何使用输入变量（iv）或其别名访问语句/表达式的表达式时，getPredicate 函数将返回 null。 例如，图 4c 中第 4 行中的谓词表达式“ contains（apiCallNodes，node.id）”不访问该语句/表达式，而谓词表达式“ def（node.expr）&& hasSubstring（node.expr）”访问该表达式使用输入变量节点。表 1 提供了分支节点上的谓词表达式的几个示例，以及图 4 中描述的示例挖掘任务的 getPredicate 函数所返回的值。当 getPredicate 返回 null 时，算法 1 只会忽略分支节点并继续处理其他节点。

表 1 getPredicate 辅助功能的谓词提取方案

如果存在一个谓词表达式，该谓词表达式包含一个使用输入变量（iv）或其别名访问语句/表达式的表达式，但并非所有谓词表达式中的符号都可以解析，则 getPredicate 函数将返回 true。这可能在几种情况下发生，例如，谓词表达式包含全局变量，或者其值无法解析的局部变量，或者函数调用又不是局部的（调用的函数可以访问全局变量）。我们已经考虑了分析语言可能发生的所有可能情况，并在表 1 中列出了一些示例。getPredicate 函数返回 true 失败案例，它表明存在一个谓词但无法提取。我们注意到使用 failToExtract 布尔值（在算法 1 中）会导致失败，该布尔值稍后将在第 24 行中使用，它以合理的行为终止规则提取，该行为假设输入 CFG 中的所有节点都与挖掘任务相关。

最后的情况是 getPredicate 函数能够从分支节点成功提取谓词表达式。请注意，在这种情况下返回的谓词表达式已完全根据符号进行了解析，并且仅包含基于输入变量的语句/表达式。在这种情况下，我们根据路径中后继节点所属的分支（真或假分支）确定是否添加谓词表达式或其否定。路径条件是路径中所有谓词表达式的“逻辑和”（第 16-19 行）。如果当前访问的节点不是分支节点，则获取输出变量 ov 的别名，并检查该节点是否包含输出变量或其别名（第 21-22 行）。这里的想法是仅保留那些有助于测试输出的路径条件。在访问路径中的所有节点结束时，如果当前路径对输出有所贡献，则将计算出的路径条件添加到规则集 R 中（第 26-27 行）。

图 5 我们通过静态分析为 API 前提条件挖掘任务生成的规则集 R 如图 4 所示

3.2 带注释的控制流程图

在第 3.1 节中，我们描述了提取规则的静态分析。静态分析的输出是一组规则，其中包含 CFG 节点上的谓词表达式。例如，用于 API 前提条件挖掘的规则集包含三个规则，如图 5 所示。使用这些规则集，我们执行预分析遍历，该遍历访问 CFG 中的每个节点，检查是否存在规则 r∈R，从而求值（ r，n）为真，并创建一个节点集 NR ⊆ N，其中节点包含规则集 R 中至少一个规则求值为真的节点。辅助函数评估给定的规则 r（这是一个谓词）和一个 CFG 节点，检查是否满足返回 true 或 false 的要求。集合 NR 代表分析相关节点的可能集合。请注意，如算法 2 所示，还向集合 NR 中添加了一些特殊节点。这些是入口节点，出口节点和分支节点。最后，将新创建的集合 NR 添加到 CFG 中以创建修改后的 CFG，我们称为带注释的控制流图（ACFG）。

定义 4. CFG G =（N，E，>，⊥）的一个带注释的控制流图（ACFG）是一个 CFG G’ =（N，E，NR，>,⊥），G’的节点（NR ⊆ N）集使用算法 2 计算得出。

定义 5.给定 ACFG G’ =（N，E，NR，>, ⊥），如果满足以下条件，则节点 n∈N 是与分析相关的节点：

• n 是 a>或 a⊥node，
• n 也位于 NR 中，但不是一个分支节点；
• n 是一个分支节点，其中至少一个分支具有与分析相关的节点。

3.3 简化的控制流程图

使用包含控制分析相关节点的一组 NR 的带注释的控制流图（ACFG），我们执行了声音还原，以精炼该 NR 集，并且还删除了与分析无关的节点，以创建称为简化控制流图的简化或压缩 CFG（RCFG）。 RCFG 是修剪的 CFG，仅包含与分析相关的节点。 RCFG 是通过对 ACFG 进行缩减来构造的。

定义 6. ACFG G’ =（N，E，NR，>，⊥）的简化控制流图（RCFG）是修剪的 ACFG，其中修剪了与分析无关的节点。 RCFG 定义为 G’’ =（N’，E’，>’，⊥’），其中 G’’是一个有向图，其中一组节点 N0⊆N 表示程序语句，而一组边 E’表示语句之间的控制流。 是入口和出口节点。 边缘 E-E’是已删除的边缘，E’-E 是新创建的边缘。

3.4 从 ACFG 到 RCFG 的规约

算法 3 描述了从 ACFG 到 RCFG 的规约。该算法将访问 ACFG 中的节点，并检查该节点是否存在于 NR 中。NR 中不存在的节点将被修剪（第 2-5 行）。在删除与分析无关的节点之前，在要删除的节点的前任和后继之间创建新的边（第 4 行和算法 4）。删除所有与分析无关的节点后，我们将通过 RCFG 并删除不相关的分支节点（第 6-11 行）。不相关的分支节点是那些在 RCFG 中仅具有一个成功的分支节点（此节点不再是有效的分支节点）。请注意，我们对分析相关节点的定义（定义 5）包括分支节点，该分支节点至少具有一个分支，该分支具有与分析有关的节点。

图 6 显示了几个示例软件推导。例如，在第一个示例中，修剪节点 j 时，将在 i 和 k 之间创建一个新边。考虑我们的第二个示例，其中删除了作为分支一部分的节点 k。删除 k 导致删除 j，这是一个只有一个后继节点（无效分支）的分支节点。接下来，在第五个示例中考虑删除节点 l 的有趣情况。节点 l 具有循环条件节点 i，并且有从 j 到 l 的两条路径（j→l 和 j→ k→l）。删除节点 1 会导致其他循环。这是因为 CFG 中存在从 j 到 i 的两条路径。 同样，其他示例显示了由算法 3 执行的约简。

图 6 ACFG 到 RCFG 减少示例

4 实证评估

表 2 通过 16 个分析，减少了 DaCapo 和 SourceForge 数据集的分析时间并减少了图形大小。 CFG 列提供了基线方法中的分析时间，RCFG 列提供了我们方法中的分析时间。 RCFG 分析时间包括注释和缩减开销。 R 列减少了分析时间，％R 提供了减少了分析时间的百分比。 在“图形大小（缩减百分比）”下，列 N，E，B，L 代表节点，边，分支和循环。 该表还提供了分析时间中减少量（R）和减少量百分比（％R）的最小值，最大值，平均值和中位数。

4.1 实验设置

4.1.1 分析

表 2 列出了用于评估方法的 16 个流分析的集合。该集合主要包含在超大规模源代码挖掘任务或编译器中的源代码优化中使用的分析。

4.1.2 数据集

我们使用了两个 Boa 数据集：DaCapo 和 SourceForge。

4.1.3 方法论

我们将方法（RCFG）的执行时间与基准的执行时间进行了比较。执行基准分析的时间是在数据集中所有控制流图（CFG）上运行分析的总时间，其中，我们分析方法的执行时间是在所有控制图上运行分析的总时间。数据集中的简化控制流图（RCFG）以及所有运行时开销。我们的方法中的各种运行时开销包括标识和注释相关节点的时间以及执行控制流图（删除不相关节点）以减少控制流图（RCFG）的时间。

4.2 分析时间的减少

我们测量了 RCFG 的分析时间相对于基线的减少。分析时间的减少源于 RCFG 的图形大小相对于 CFG 的减小，因此为了了解分析时间的减少，我们从节点，边，分支和循环的角度测量了图形大小的减小。我们在数据集中的所有图形上累积了这些指标。结果在表 2 中的“图形大小（减少百分比）”下显示了软测量。图形大小的减少与分析时间的减少高度相关。图形大小的减少程度越高，分析时间的减少程度就越大。

总而言之，可以看出，对于 16 个分析中的 11 个，我们的技术能够显着减少分析时间（11 个分析平均减少 60％以上，所有分析平均减少 40％以上）。使用节点，边缘，分支和循环的图形缩减可以解释这种缩减。此外，表 3 列出了代码的相关部分，以进行各种分析，以提供有关缩减的更多见解。

表 3 有关各种分析的相关源代码部分

对于 5 个分析，分析时间的减少很小或没有减少。这 5 种分析的图形大小减少幅度也很小。这些分析是：恒定传播（CP），复制传播（CP’），无效代码（DC），活动变量（LV）和到达定义（RD）。我们可以得出结论，对于图形尺寸减小不大（或相关语句为通用语句）的分析，RCFG 可能会产生开销，从而导致分析时间比“基线”长。

此外，可以在运行分析之前通过在评估规则的预分析遍历过程中计算相关节点的数量（从我们的静态分析中提取）以标记相关节点，从而从分析中检测是否可以减小 CFG 大小，从而有助于分析。我们在分析前遍历中计算相关节点与所有节点的数量之比，并决定是在运行分析之前修剪还是跳过修剪而仅运行分析。

同一套方法可以为各种分析证明不同数量的相关陈述。例如，图 7 对于 PM，相关的语句较少，因此有更多的减少机会。而如果考虑 LV 分析，所有包含变量定义和变量访问的语句都是相关的，则图 7 所示的三种方法中的所有语句都是相关的，因此无法执行减少操作。

图 7 DaCapo 数据集中的三种方法。 突出显示的部分是用于 PM 分析的相关声明

图 8 减少了 16％的 DaCapo 和 SourceForge 数据集的分析时间减少的箱形图以及图形大小指标

图 8 显示了所有 16 种分析的百分比减少和图形大小减少的箱线图。我们可以从箱线图中得出以下结论：i）在大多数分析中，分析时间的减少是可观的，ii）对于非 RCFG 方法无益的分析，不会造成过多的开销。总而言之，我们的 16 组分析显示，在我们的方法能够实现的分析时间减少方面，差异很大。关于可以从我们的方法中受益的分析，我们可以看到，分析时间的减少既取决于分析的复杂性，也取决于与分析相关的程序的百分比。

4.3 可扩展性

在本节中，我们针对 16 种分析方法，在增加数据集大小的基础上，测量了 Baseline 和 RCFG 方法的可扩展性。

4.4 减少的准确性和效率

我们通过比较 RCFG 和基线方法的结果来评估减少的准确性。为了评估减少的效率，我们测量了 RCFG 方法不同组件的时间。

4.5 静态分析的开销

表 4 列出了这些开销以及分析的一些特征，还显示了我们的静态分析的总开销（Ttotal）以及其每个组成部分的开销。根据 16 次分析的中值，开销约为 300ms。这意味着，分析程序的编译时间增加了 300 毫秒。这些分析具有深层嵌套的分支和循环，这是其分析功能的一部分，这会增加路径数量和路径枚举时间。总而言之，当我们的静态分析探索分析中的路径时，具有许多路径的分析可能会产生不可忽略的开销，但是这种开销是一次性的编译开销。

表 4 静态分析开销。 #LOC：分析代码行数，＃F：分析函数（或 CFG）数，＃P：分析路径数，T1：CFG 建立时间，T2：路径枚举时间，T3：别名分析时间， T4：规则提取时间，Ttotal = T1 T2 T3 T4。 T1-T4 和 Ttotal 的单位是毫秒

4.6 有效性威胁

有效性威胁在于我们的结果的适用性。我们研究了几种执行控制和数据流分析的源代码挖掘任务，并表明可以实现显着的加速（平均 40％）。但是，这些结果在构成任务方面可能与被研究对象完全不同，因此可能并不正确。为了减轻这种威胁，我们将需要进行 CFG 遍历的次数以及执行的操作纳入了复杂程度不同的任务。

5 结论

数据驱动的软件工程需要大规模挖掘和分析源代码存储库，而此活动可能会很昂贵。现有技术集中于利用分布式计算技术来解决该问题，但是随之而来的是计算资源需求的增加。这项工作提出了一种补充技术，该技术可以减少超大规模源代码挖掘任务执行的计算量，而不会影响结果的准确性。虽然所提出的技术已经显示出可以扩展执行方法级控制和数据流分析的大规模源代码挖掘任务，但未来工作的直接途径是将我们的技术扩展到可以扩展执行跨方法控制和数据流分析的挖掘任务（或项目级分析）。基于其他源代码中间表示形式（例如抽象语法树（AST），调用图（CG）和程序依赖图（PDG））的源代码挖掘任务也可以从我们技术的核心思想中受益。我们计划研究这些未来的方向，以进一步实现扩展大规模源代码挖掘任务的总体目标。

本文由南京大学软件学院 2020 级硕士王旭翻译转述

,