光一样的少年|大规模下加速源代码分析( 四 ) 123456789101112131415161

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 执行的约简。