一种基于分布式图可达计算的过程间程序静态分析方法

摘要

本发明公开了一种基于分布式图可达计算的过程间程序静态分析方法，包括以下步骤：（a）将程序表示图和对应分析语法作为算法输入，图中传递边根据源顶点和目标顶点进行分区，将连接到同一个节点的边移动到同一个分区中；（b）对不同分区中的边执行分析语法的标签匹配操作，产生新边；（c）对新边进行全局和局部去重，保留新生成的传递边；（d）对各分区进行对应可达关系的添加，重复（b）‑（c），直到不再产生新的传递边为止，得到过程间静态分析结果。本方法能够提高大规模程序静态分析的性能和可扩展性，促进其应用与解决实际问题。

说明书

技术领域

本发明涉及软件工程领域，特别涉及一种基于分布式图可达计算的过程间程序静态分析方法。

背景技术

生产实践中常用基于模式或规则的分析工具和过程内分析方法，对软件进行静态分析，运算速度较快，但精度较低，难以获得可用性高的分析结果。与过程内分析相比，过程间分析能够提供精确的分析结果，但其计算复杂度也较高。Yannakakis和Reps等采用CFL可达性来制定一系列复杂的静态分析，这为许多过程间静态分析任务开辟了一扇新的大门。

然而，在实际场景下对大型软件进行基于图可达的过程间程序静态分析的计算复杂度非常高。随着现代软件规模的扩大，对现代软件系统（如Linux内核等）进行精确分析变得越来越具有挑战性。在对Linux内核（超过16M行代码）进行上下文有关的过程间别名分析中，有超过10亿条边生成，前沿的程序静态分析工具均难以完成分析任务。由于硬件资源和传统方法的限制，单机计算已难以支撑大规模图数据的高效处理，从而导致了静态分析方法的可扩展性较差。

发明内容

本发明要解决的技术问题是提供一种基于分布式图可达计算的过程间程序静态分析方法，能够提高大规模程序静态分析的性能和可扩展性，促进其应用与解决实际问题。

为了解决上述技术问题，本发明的技术方案为：

一种基于分布式图可达计算的过程间程序静态分析方法，包括以下步骤：

（a）将程序表示图和对应分析语法作为算法输入，图中传递边根据源顶点和目标顶点进行分区，将连接到同一个节点的边移动到同一个分区中；

（b）对不同分区中的边执行分析语法的标签匹配操作，产生新边；

（c）对新边进行全局和局部去重，保留新生成的传递边；

（d）对各分区进行对应可达关系的添加，重复（b）-（c），直到不再产生新的传递边为止，得到过程间静态分析结果。

优选地，在步骤（a）中还包括以下步骤：

（a1）所有边都分别根据它们的源顶点和目标顶点进行分区；

（a2）分区完成后，对所有边分区进行以下join操作（连接操作）；

（a3）join操作完成后，分区中的边集被处理为以顶点为键，与顶点相连的边集为值的key-value形式（键-值形式）。

优选地，其中步骤（a2）中的join操作为：如果一条边的源顶点与另一条边的目标顶点相同，则会连接两条边。

优选地，在步骤（b）中每个分区由多个键值对组成，执行map操作（映射操作）并行处理所有分区的键值对集合。

优选地，在步骤（b）中通过变换产生式和输入图，在Process（处理）过程中产生新边。

优选地，在步骤（c）中还包括以下步骤：

（c1）Process完成后，会在每个分区中生成新边集 ；

（c2）通过分布式数据库从中去除所有在传递闭包TC中已存在的边；

（c3）通过全局distinct（去重）操作消除不同分区间产生的E重复边。

优选地，在步骤（c2）中所述全局去重通过分布式数据库，在各分区内部并行执行。

优选地，在步骤（c3）中还包括以下步骤：

（c31）通过先全局shuffle（混洗操作）数据，将相同边发送到同一个分区；

（c32）在各分区内部并行执行合并相同边。

优选地，每轮计算结束后，需要对传递闭包TC和分布式数据库执行union操作。

优选地，在步骤（d）中还包括以下步骤：

（d1）将上一轮产生的边集加入到传递闭包中，使传递闭包得到更新，以备下一轮标签匹配计算；

（d2）将新产生的传递边更新到数据库中，为全局去重做准备。

采用上述技术方案，结合动态规划Worklist算法，从数据并行的角度重新设计并行化的传递闭包算法，并将其抽象为由大规模数据集和该数据集上的简单计算组成的大数据问题，使得本发明的有益效果在于：

首先，Map/Reduce操作直观地将共享数据划分为多个小块。数据以分而治之的方式处理，从而减少了同步开销并实现了高并行性；

其次，可以根据数据局部性（locality）执行各自的计算过程，无需相互依赖、相互通信，大幅降低了分布式环境中的通信成本；

最后，在计算期间使用成熟的分布式文件系统实现内存与磁盘的交互，避免因内存不足导致计算失败。

附图说明

图1为本发明的总体执行流程示意图；

图2为本发明的数据划分设计示意图；

图3为本发明的数据结构设计示意图；

图4为本发明的局部闭包计算优化示意图；

图5为本发明的Pre-shuffle优化示意图；

图6为本发明的负载均衡优化示意图；

图7为本发明的Process过程示意图。

具体实施方式

下面结合附图对本发明的具体实施方式作进一步说明。在此需要说明的是，对于这些实施方式的说明用于帮助理解本发明，但并不构成对本发明的限定。此外，下面所描述的本发明各个实施方式中所涉及的技术特征只要彼此之间未构成冲突就可以相互组合。

本发明提出一种基于分布式图可达计算的过程间程序静态分析算法，解决了现有方法效率低和可扩展性差的问题。如图1所示，本发明方法主要包括以下4个步骤：

（1）将程序表示图和对应分析语法作为算法输入，图中传递边（可达关系）根据源顶点和目标顶点进行分区，将连接到同一个节点的边移动到同一个分区中。

（2）对不同分区中的边执行分析语法的标签匹配操作，产生新边。

（3）对新边进行全局和局部去重，保留新生成的可达关系。

（4）对各分区进行对应可达关系的添加，重复（2）-（3），直到不再产生新的可达关系为止，得到过程间静态分析结果。

下面以图1中所示的两个分区数据为例，说明本发明的具体的实施方式。结合本例，本发明的具体的实施方式为：

发明内容里的步骤（1）的具体实施方式为：传递闭包TC和列表W中的所有边都分别根据它们的源顶点和目标顶点进行分区，即通过对边的复制，解除中间节点的边集共享问题。分区完成后，对所有边分区进行以下join操作：如果一条边的源顶点与另一条边的目标顶点相同，则会连接两条边。join操作完成后，分区中的边集被处理为以顶点为键，与顶点相连的边集为值的key-value形式。

发明内容里的技术方案步骤（2）的具体实施方式为： 本发明获得了多个分区，每个分区由多个键值对组成。执行map操作并行处理所有分区的键值对集合。每个分区所需的计算仅仅是通过基于语法规则匹配边标签来生成新边，如图7所示。Process过程虽然是可达关系计算的核心，但计算过程对不同分析类型来说是通用的，通过变换产生式和输入图，即可在Process过程中产生不同的可达关系。

发明内容里的技术方案步骤（3）的具体实施方式为：Process完成后，会在每个分区中生成新边集E。从图3-5可以看出，产生的新边与所在分区的键（顶点）可能并不相关，例如新边x□(→┴C ) z和中间节点y没有相连，因此不同分区间可能产生相同的边，多轮迭代计算之间也会产生相同的边(如图中C-边所示)。

为了算法正确收敛和消除冗余计算，本发明需要过滤掉所有重复的边。去重包括两个阶段：（1）全局去重（global filtering），它通过分布式数据库从E中去除所有在传递闭包TC中已存在的边;（2）本轮局部去重（local filtering）通过全局distinct操作消除不同分区间产生的E重复边。

借助于分布式数据库，全局去重可在各分区内部并行执行。而消除不同分区间的重复边，则需要使用典型的reduce操作：先全局shuffle数据，将相同边发送到用一个分区，然后在各分区内部并行执行合并相同边。因此先执行全局去重，可以有效减少distinct操作时的数据量。

发明内容里的技术方案步骤（4）的具体实施方式为：每轮计算结束后，需要对传递闭包TC和分布式数据库执行union操作。对传递闭包TC执行union操作，是指将上一轮产生的传递边集W^'与加入到传递闭包中，使传递闭包得到更新，以备下一轮标签匹配计算；对数据库执行union操作，是指将新产生的传递边更新到数据库中，为全局去重做准备。重复（2）-（3），直到不再产生新的可达关系为止。迭代结束后图中的传递边表明的可达关系，反映了过程间静态分析结果。

上述算法方法中，从数据并行的角度重新设计并行化的传递闭包算法，并将其抽象为由大规模数据集和该数据集上的简单计算组成的大数据问题，提出了一种基于Map/Reduce风格操作的多机分布式数据并行算法。许多数据并行分布式系统通常支持本发明的算法中所需的操作。

数据并行Worklist算法伪代码如下所示。该过程以迭代方式执行。可达关系以边的形式添加到传递闭包TC中，W表示待计算的边，W^' 表示上一轮迭代中生成的W， TC表示被W^'更新的传递闭包，每次迭代首先在TC和W上执行join操作连接所有边对（P）。接下来，按照map操作在每个边对上执行标签匹配（label matching），产生新边集E，例如连接于同一个中间节点的边对 x□(→┴A ) y□(→┴B ) z可根据语法C∷=A B生成新边x□(→┴C ) z。由于相同边可以在不同路径上生成，E中可能会有重复的边。为了避免此后的冗余计算，本发明需要过滤掉所有重复边，以获得真正的新边集合。

从数据并行的角度重新设计并行化的传递闭包算法，并将其抽象为由大规模数据集和该数据集上的简单计算组成的大数据问题，提出了一种基于Map/Reduce风格操作的多机分布式数据并行算法。许多数据并行分布式系统通常支持本发明的算法中所需的操作。

数据并行Worklist算法伪代码如下所示。该过程以迭代方式执行。可达关系以边的形式添加到传递闭包TC中，W表示待计算的边，W^' 表示上一轮迭代中生成的W， TC表示被W^'更新的传递闭包，每次迭代首先在TC和W上执行join操作连接所有边对（P）。接下来，按照map操作在每个边对上执行标签匹配（label matching），产生新边集E，例如连接于同一个中间节点的边对 x□(→┴A ) y□(→┴B ) z可根据语法C∷=A B生成新边x□(→┴C ) z。由于相同边可以在不同路径上生成，E中可能会有重复的边。为了避免此后的冗余计算，本发明需要过滤掉所有重复边，以获得真正的新边集合。

传递闭包TC的更新与W的更新是错开的，每轮迭代结束时，TC与上一轮生成的W^('’)通过union操作进行合并，和本轮生成的W一起投入下一轮计算。

当算法收敛时（不再有新边产生），迭代结束。因此去重（去除重复边）极为重要，它的实现不仅影响算法的运行速度，也决定了算法是否能及时收敛。

算法在以下三个方面具有显著优势。首先，Map/Reduce操作直观地将共享数据划分为多个小块。数据以分而治之的方式处理，从而减少了同步开销并实现了高并行性。其次，本发明可以根据数据局部性（locality）执行各自的计算过程，无需相互依赖、相互通信，大幅降低了分布式环境中的通信成本。最后，本发明在计算期间使用成熟的分布式文件系统实现内存与磁盘的交互，避免因内存不足导致计算失败。

下面从数据划分、数据结构、算法和系统级优化等方面，阐述本发明为提高性能、减少同步开销进行的并行化设计和优化。

数据划分：在每次迭代开始时，传递闭包TC和列表W中的所有边都分别根据它们的源顶点和目标顶点进行分区，即通过对边的复制，解除中间节点的边集共享问题。这样做可以使边同时完成双向的路径传递，实现标签匹配操作的并行化。复制操作如图2所示。具有相同源或目标顶点（键）的边被放在与图2框中矩形相对应的相同分区中。分区内部计算是并行执行的，提高了并行效率和资源利用率。join和filter操作的并行化基于上述分区完成。

数据结构：分区中边集（包括待计算边集W和原传递闭包TC的边）被处理为以顶点为键，与顶点相连的边集为值的key-value形式。用三元组（src,dst,label）定义一条边，分别表示边的源节点、目标节点和标签，当三个值都相等时，判断两条边相同。若直接以三元组作为边的表示，则需要三倍于边数的存储空间，且三元组不适用于process过程的连接和配对的查找。为了减少内存与磁盘之间的交互，本发明对此数据结构进行了压缩，并针对上述计算特点，添加了索引优化。原先的边集被压缩为一个长数组和索引映射。长数组中仅存储与中间节点m相邻的节点，索引映射表示边的分类到边所在长数组索引的映射，映射中的每个元素表示为<(direction，status，label)，index range>的键值对，键为(direction，status，label)三元组，表示边的方向、状态和标签，以确定边的分类，值为相应分类的边在长数组中的存储区间。

已知边的分类共有4L种，则索引映射的长度最多为4L。假设有X条边，当X≫4L时，存储的数据量由3X降为X，即当边数较多时，存储量降为原来的三分之一（忽略平台实现差异）。数据结构示意图如图3所示。

算法优化：局部闭包计算优化：检查CFL语法，发现在迭代过程中某些终结符标记的边是静态的。静态的含义是指，这些终结符没有出现在产生式的左部，即它们标记的边不可能被生成，不可能出现在分区的计算结果中。局部闭包计算优化示意图如图4所示，分析语法为N∷=Ne。

将静态边广播到所有工作节点，以便在本地访问这些边，无需与其他节点共享。在每次迭代时，每个节点利用本地的静态边尽可能多地生成传递边，直到本地的传递边与静态边匹配无法再生成新的传递边为止，即形成传递闭包。然后进行Filter过程，进行下一轮数据划分和分区计算。

系统级优化：

（1）、Pre-shuffle：Pre-shuffle策略通过预先使用相同的分区器划分两个数据集，并且通过直接在相同节点中加入相应的分区来避免这种网络通信。本发明在迭代过程持续期间维护一个全局分区程序，并确保传递闭包TC始终由全局分区程序进行分区。生成W时，本发明使用相同的全局分区器对其进行分区，并通过Pre-shuffle策略将其分区直接移动到与TC相同的节点上。如图5所示，由于在每轮迭代中被W^'更新的TC会自动继承全局分区程序作为其分区程序，因此只需要进行一次shuffle操作即可确定TC的分区，在之后的计算中TC的数据都不再移动。仅在每次迭代产生新边集W时，才会触发对W的全局shuffle。随着传递边的不断生成，TC的数据量会快速膨胀，通过Pre-shuffle策略，本发明以对小批量数据W的移动取代对大规模传递闭包TC的全局shuffle，有效地减少了网络流量和序列化、反序列化开销。

（2）、负载均衡：节点本身与大量的邻边相关联，或笛卡尔积形式的标签匹配算法使得产生的传递边数量急速膨胀，或以上两种情况合并出现时，单个节点产生的传递边数量能达到亿以上数量级。本发明通过节点分裂策略解决上述负载不均衡的情况，节点分裂示意图如图6所示，将节点3的入边拆成多份，并将出边分别复制到不同入边的所在节点中。每条入边仍然能和所有出边进行标签匹配，正确生成下一轮待计算的边集。

根据上述算法和具体内容，本发明进一步地提供了一种基于分布式图可达计算的过程间程序静态分析方法，包括以下步骤：

（a）将程序表示图和对应分析语法作为算法输入，图中传递边根据源顶点和目标顶点进行分区，将连接到同一个节点的边移动到同一个分区中；

（b）对不同分区中的边执行分析语法的标签匹配操作，产生新边；

（c）对新边进行全局和局部去重，保留新生成的传递边；

（d）对各分区进行对应可达关系的添加，重复（b）-（c），直到不再产生新的传递边为止，得到过程间静态分析结果。

优选地，在步骤（a）中还包括以下步骤：

（a1）所有边都分别根据它们的源顶点和目标顶点进行分区；

（a2）分区完成后，对所有边分区进行以下join操作；

（a3）join操作完成后，分区中的边集被处理为以顶点为键，与顶点相连的边集为值的key-value形式。

优选地，其中步骤（a2）中的join操作为：如果一条边的源顶点与另一条边的目标顶点相同，则会连接两条边。

优选地，在步骤（b）中每个分区由多个键值对组成，执行map操作并行处理所有分区的键值对集合。

优选地，在步骤（b）中通过变换产生式和输入图，在Process过程中产生新边。

优选地，在步骤（c）中还包括以下步骤：

（c1）Process完成后，会在每个分区中生成新边集 ；

（c2）通过分布式数据库从E中去除所有在传递闭包TC中已存在的边；

（c3）通过全局distinct操作消除不同分区间产生的E重复边。

优选地，在步骤（c2）中所述全局去重通过分布式数据库，在各分区内部并行执行。

优选地，在步骤（c3）中还包括以下步骤：

（c31）通过先全局shuffle数据，将相同边发送到同一个分区；

（c32）在各分区内部并行执行合并相同边。

优选地，每轮计算结束后，需要对传递闭包TC和分布式数据库执行union操作。

优选地，在步骤（d）中还包括以下步骤：

（d1）将上一轮产生的边集加入到传递闭包中，使传递闭包得到更新，以备下一轮标签匹配计算；

（d2）将新产生的传递边更新到数据库中，为全局去重做准备。

以上结合附图对本发明的实施方式作了详细说明，但本发明不限于所描述的实施方式。对于本领域的技术人员而言，在不脱离本发明原理和精神的情况下，对这些实施方式进行多种变化、修改、替换和变型，仍落入本发明的保护范围内。