一种基于调用依赖图的测试用例聚类分组方法

1.本发明涉及一种针对随机单元测试用例生成工具自动化创建的大量测试用例进行调用依赖图的构建以及聚类分组的方法，属于软件测试技术领域。


背景技术：

2.自动化单元测试用例生成工具能够生成具有较高质量的单元测试，有效地减小手工编写测试的成本，提高软件开发的效率。其中，使用随机方法的单元测试用例生成工具具有易于实施、可扩展性强、代码覆盖率高等特点，它从程序的输入空间中随机地选择测试输入，并增量地产生方法序列。然而，随机单元测试用例生成工具自动构建的测试用例的数量过大，并且可读性较差。现有的可读性增强工具大多通过为自动生成的测试用例添加注释或者创建更具描述性的测试方法名称等方式来提高可读性，却忽略了随机单元测试用例生成工具构建的大量测试用例通常会具有重复相似的功能行为，同时也忽略了由此导致的缺乏归纳、杂乱无章、随机性强、可读性差等问题。


技术实现要素：

3.发明目的：随机单元测试用例生成工具尽管能够自动化地构建可扩展性强、代码覆盖率高的测试用例，但是生成的测试用例数量较大，同时是随机、杂乱无章的，并且其中有些测试用例具有重复相似的功能行为。针对现有技术中存在的问题与不足，本发明提供一种基于调用依赖图的测试用例聚类分组方法，通过聚类的方式将测试用例按照结构和内容进行归纳和分组，进而提高测试用例的可读性，降低维护成本，提高软件开发过程的效率。
4.技术方案：一种基于调用依赖图的测试用例聚类分组方法，包含以下步骤：
5.步骤1，首先对自动化工具创建的单元测试用例代码进行静态分析，从每条断言出发，构造测试用例的调用依赖图；
6.步骤2，将测试用例的调用依赖图转换成带属性图(attributed graph)；
7.步骤3，使用基于图内核的方法计算测试用例的带属性图之间的相似度，并获取整个测试套件的相似度矩阵；
8.步骤4，将相似度矩阵作为输入，使用谱聚类算法基于输入矩阵为测试用例进行聚类，并得到聚类结果；
9.步骤5，基于聚类结果将测试用例进行分组，并输出分组后的测试用例文件。
10.所述步骤1中，在获取自动化测试生成工具创建的测试用例后，利用静态分析方法构造相应的调用依赖图，具体实现过程为：
11.11)使用javaparser提取出测试套件中所有标记@test注解的测试用例；
12.12)分析测试用例中每个断言与其他代码语句之间的调用依赖关系；通过定义规则来识别标识符和寻找调用依赖关系。
13.代码表达式声明了对象，但表达式中不包含其他任何变量，只需检测声明的对象
的名称是否为前向节点寻找的标识符；若是，则添加当前节点至图中，无需更新标识符集，并继续寻找后继节点；若不是，则继续寻找目标节点。
14.代码表达式声明了对象，并通过调用构造器、使用类实例的静态字段、调用方法等方式来给对象赋值或实例化，且表达式中使用了其他变量，则先检查声明的对象名称是否为前向节点寻找的标识符。若是，则添加当前节点至图中，并更新当前的标识符集，继续寻找后继邻居节点；若不是，但检测到前向节点寻找的标识符是表达式中的其他变量(如参数)，则依然添加当前节点至图中，并更新当前的标识符集，接着寻找后继邻居节点。
15.代码表达式只有方法调用，没有声明任何对象，只需检测表达式中是否使用了前向节点寻找的标识符；若包含，则添加当前节点至图中，并更新当前的标识符集，继续寻找后继邻居节点；若不包含，则继续寻找目标节点。
16.13)从每个断言开始，根据调用依赖关系逆向地构造测试用例的调用依赖图。调用依赖图的节点和边的定义为：节点包含编号、代码语句、后继邻居节点等内容信息；边表示其连接的两个节点的代码语句之间存在直接的调用行为，但不存储实际内容。构造调用依赖图是从测试用例的断言出发，并不断地寻找代码语句之间的调用依赖关系，直至依赖结束。首先，获取测试用例代码中所有的断言语句并封装成节点，将它们作为头部节点的后继邻居节点。接着，自每个断言节点开始，进行基于工作队列的调用依赖关系的构建和迭代过程，工作队列是指包含着当前所有待处理节点的队列，工作队列的初始状态只包含当前断言节点。调用依赖关系的分析过程如下：识别并迭代工作队列中节点的代码语句中包含的每个标识符，对于标识符的每次使用和定义，都会将对应的节点和边添加到图中，并更新工作队列以及当前节点的后继邻居节点列表。当工作队列为空时，该断言节点的调用依赖关系结束。最后，对于每个断言节点，执行上述调用依赖关系的分析过程，直至所有断言节点的调用依赖关系结束，则调用依赖图的构建完毕。
17.所述步骤2中，分析测试用例的调用依赖图的拓扑结构和节点信息，并将调用依赖图转换成节点带属性图，带属性图可以被图内核工具grakel处理。grakel是一个包含多种图内核和通用框架的库，可用于图聚类任务。具体实现过程为：
18.21)构造带属性图的节点，并将调用依赖图中节点之间的关系映射到带属性图的边，需要保持带属性图节点之间的关系与调用依赖图一致。
19.22)提取调用依赖图中节点的代码语句中声明的对象类型和被测方法名称，并求取相应的独热编码特征向量作为带属性图节点的属性值。
20.所述步骤3中，具体实现过程为：
21.31)使用grakel提供的最短路径图内核来计算两个测试用例的带属性图之间的相似度。最短路径内核是一种典型的图内核方法，它将图分解为最短路径，并根据节点之间最短路径长度以及节点属性值之间的点积来比较最短路径对。
22.32)通过步骤31)介绍的方式计算所有测试用例之间的相似度，最终求取代表整个测试套件相似关系的相似度矩阵。
23.所述步骤4中，使用谱聚类算法来求取测试用例的聚类结果，具体实现过程为：
24.41)将步骤3中获取的相似度矩阵作为谱聚类算法的输入，相似度矩阵可以看作是图模型的邻接矩阵，通常用来构建图模型。具体来说，相似度矩阵中的元素表示样本之间的相似程度，可以将其看作是一个无向加权图中的边权值。然后谱聚类算法会基于相似度矩
阵计算拉普拉斯矩阵和谱矩阵，再得到其特征值和特征向量。
25.42)先从小到大对特征值进行排列，再选取最小的k个特征值对应的特征向量作为降维后的特征向量矩阵，矩阵的每一行即为样本映射的特征。本发明采用最大化特征裂隙的方法来求取最优的k值。
26.43)最后使用kmeans聚类算法对降维后的特征向量矩阵进行聚类，最终获得测试用例的聚类结果。kmeans是一种迭代求解的聚类分析算法，它随机选取k个初始的聚类中心(此处k值与42)中求取的k值相同)，然后将每个数据点分配到最近的簇，同时保持簇内对象到该簇中心的距离尽可能小。
27.一种计算机设备，该计算机设备包括存储器、处理器及存储在存储器上并可在处理器上运行的计算机程序，处理器执行上述计算机程序时实现如上所述的基于调用依赖图的测试用例聚类分组方法。
28.一种计算机可读存储介质，该计算机可读存储介质存储有执行如上所述的基于调用依赖图的测试用例聚类分组方法的计算机程序。
29.本发明与现有技术相比具有如下优点：
30.1)基于断言与其他代码语句之间的关系构建测试用例的调用依赖图，并使用最短路径图内核方法计算图与图之间的相似度，即求得了两个测试用例之间的相似度。相比传统的jaccard相似性指标和结合余弦相似性的词频逆文档频率(tf-idf)方法而言，这种相似度计算方法同时考虑到了调用依赖图的拓扑结构和节点内容信息，能够有效衡量测试用例的语句调用、依赖关系和断言检测行为，并且能够有助于获得更好的聚类效果。
31.2)本发明通过构建调用依赖图并使用图内核计算相似度，能够得到代表整个测试套件相似关系的相似度矩阵，并使用能够处理相似度矩阵作为输入的谱聚类算法对测试用例进行分组。聚类能够使得自动化生成的测试用例按照功能行为进行分组，使其更加清晰有序，提高了测试用例的可读性和可理解性。
附图说明
32.图1为本发明实施例的基于调用依赖图的测试用例聚类分组方法概览图。
具体实施方式
33.下面结合具体实施例，进一步阐明本发明，应理解这些实施例仅用于说明本发明而不用于限制本发明的范围，在阅读了本发明之后，本领域技术人员对本发明的各种等价形式的修改均落于本技术所附权利要求所限定的范围。
34.本实施例提供一种基于调用依赖图的测试用例聚类分组方法，提高单元测试用例的可读性，降低维护成本。
35.第一步，对自动化单元测试生成工具创建的单元测试用例代码进行静态分析，从每条断言出发构造测试用例的调用依赖图。具体步骤为：
36.1)使用javaparser提取出测试套件中所有标记@test注解的测试用例；
37.2)接下来，分析每个断言与其他代码语句之间的调用依赖关系，并通过定义规则来识别标识符、根据调用依赖关系寻找节点和构造调用依赖图，具体规则为：代码表达式声明了对象，但表达式中不包含其他任何变量，只需检测声明的对象的名称是否为前向节点
寻找的标识符；若是，则添加当前节点至图中，无需更新标识符集，并继续寻找后继节点；若不是，则继续寻找目标节点。代码表达式声明了对象，并通过new关键字调用构造器、类实例的静态字段、调用方法等方式来给对象赋值或实例化，且表达式中使用了其他变量，则先检查声明的对象名称是否为前向节点寻找的标识符；若是，则添加当前节点至图中，并更新当前的标识符集，继续寻找后继邻居节点；若不是，但检测到前向节点寻找的标识符是表达式中的其他变量(如参数)，则依然添加当前节点至图中，并更新当前的标识符集，接着寻找后继邻居节点。代码表达式只有方法调用，没有声明任何对象，那么只需检测表达式中是否使用了前向节点寻找的标识符；若包含，则添加当前节点至图中，并更新当前的标识符集，继续寻找后继邻居节点；若不包含，则继续寻找目标节点。
38.3)从每个断言开始，根据调用依赖关系逆向地构造测试用例的调用依赖图。调用依赖图的节点和边的定义为：节点包含编号、代码语句、后继邻居节点等内容信息；边表示其连接的两个节点的代码语句之间存在直接的调用行为，但不存储实际内容。首先，获取测试用例代码中所有的断言语句并封装成节点，将它们作为头部节点的后继邻居节点。接着，自每个断言节点开始，进行基于工作队列(queue)的迭代过程，工作队列初始状态只包含当前断言节点。识别并迭代工作队列中节点的代码语句中包含的每个标识符，对于标识符的每次使用和定义，都会将对应的节点和边添加到图中，并更新工作队列以及当前节点的后继邻居节点列表。当工作队列为空时，该断言节点的调用依赖关系结束。对于每个断言节点，执行上述调用依赖关系的分析过程，直至所有断言节点的调用依赖关系结束，则调用依赖图的构建完毕。
39.第二步，将测试用例的调用依赖图转换成带属性图(attributed graph)。分析测试用例的调用依赖图的拓扑结构和节点信息，并将其转换成节点带属性图，先构造带属性图的节点，再将调用依赖图中节点之间的关系映射到带属性图的边，需要保持带属性图节点之间的关系与调用依赖图一致。接下来，提取调用依赖图中节点的代码语句中声明的对象类型和被测方法名称，并求取相应的独热编码特征向量作为带属性图节点的属性值。带属性图可以被图内核工具grakel处理。
40.第三步，使用基于图内核的方法计算测试用例属性图之间的相似度，并获取整个测试套件的相似度矩阵。使用图内核工具grakel提供的最短路径图内核来计算两个测试用例的带属性图之间的相似度，grakel是一个包含多种图内核和通用框架的库，可用于图聚类任务。最短路径内核是一种典型的图内核方法，它将图分解为最短路径，并根据节点之间最短路径长度以及节点属性值之间的点积来比较最短路径对。接下来，计算所有测试用例之间的相似度，最终求取代表整个测试套件相似关系的相似度矩阵。
41.第四步，将相似度矩阵作为输入，使用谱聚类算法基于输入矩阵为测试用例进行聚类，并得到聚类结果。将获取的相似度矩阵作为谱聚类算法的输入，相似度矩阵可以看作是图模型的邻接矩阵，通常用来构建图模型。具体来说，相似度矩阵中的元素表示样本之间的相似程度，可以将其看作是一个无向加权图中的边权值。然后谱聚类算法会基于相似度矩阵计算拉普拉斯矩阵和谱矩阵，再得到其特征值和特征向量。先从小到大对特征值进行排列，再选取最小的k个特征值对应的特征向量作为降维后的特征向量矩阵，矩阵的每一行即为样本映射的特征。本发明采用最大化特征裂隙的方法来求取最优的k值。最后使用kmeans聚类算法对降维后的特征向量矩阵进行聚类，最终获得测试用例的聚类结果。
kmeans是一种迭代求解的聚类分析算法，它随机选取k个初始的聚类中心，然后将每个数据点分配到最近的簇，同时保持簇内对象到该簇中心的距离尽可能小。
42.第五步，基于聚类结果将测试套件中的测试用例进行分组，并输出所有分组测试文件，其中每个测试文件包含一个分组的测试用例。
43.显然，本领域的技术人员应该明白，上述的本发明实施例的基于调用依赖图的测试用例聚类分组方法各步骤可以用通用的计算装置来实现，它们可以集中在单个的计算装置上，或者分布在多个计算装置所组成的网络上，可选地，它们可以用计算装置可执行的程序代码来实现，从而，可以将它们存储在存储装置中由计算装置来执行，并且在某些情况下，可以以不同于此处的顺序执行所示出或描述的步骤，或者将它们分别制作成各个集成电路模块，或者将它们中的多个模块或步骤制作成单个集成电路模块来实现。这样，本发明实施例不限制于任何特定的硬件和软件结合。

技术特征：
1.一种基于调用依赖图的测试用例聚类分组方法，其特征在于，包含以下步骤：步骤1，首先对自动化工具创建的单元测试用例代码进行静态分析，从每条断言出发，构造测试用例的调用依赖图；步骤2，将测试用例的调用依赖图转换成带属性图；步骤3，使用基于图内核的方法计算测试用例的带属性图之间的相似度，并获取整个测试套件的相似度矩阵；步骤4，将相似度矩阵作为输入，使用谱聚类算法基于输入矩阵为测试用例进行聚类，并得到聚类结果；步骤5，基于聚类结果将测试用例进行分组，并输出分组后的测试用例文件。2.根据权利要求1所述的基于调用依赖图的测试用例聚类分组方法，其特征在于，所述步骤1中，在获取自动化测试生成工具创建的测试用例后，利用静态分析方法构造相应的调用依赖图，具体实现过程为：11)使用javaparser提取出测试套件中所有标记@test注解的测试用例；12)分析测试用例中每个断言与其他代码语句之间的调用依赖关系；13)从每个断言开始，根据调用依赖关系逆向地构造测试用例的调用依赖图。3.根据权利要求1所述的基于调用依赖图的测试用例聚类分组方法，其特征在于，所述步骤2中，分析测试用例的调用依赖图的拓扑结构和节点信息，并将调用依赖图转换成节点带属性图，带属性图可以被图内核工具grakel处理；具体实现过程为：21)构造带属性图的节点，并将调用依赖图中节点之间的关系映射到带属性图的边，需要保持带属性图节点之间的关系与调用依赖图一致；22)提取调用依赖图中节点的代码语句中声明的对象类型和被测方法名称，并求取相应的独热编码特征向量作为带属性图节点的属性值。4.根据权利要求1所述的基于调用依赖图的测试用例聚类分组方法，其特征在于，所述步骤3中，具体实现过程为：31)使用grakel提供的最短路径图内核来计算两个测试用例的带属性图之间的相似度；32)通过步骤31)介绍的方式计算所有测试用例之间的相似度，最终求取代表整个测试套件相似关系的相似度矩阵。5.根据权利要求1所述的基于调用依赖图的测试用例聚类分组方法，其特征在于，所述步骤4中，使用谱聚类算法来求取测试用例的聚类结果，具体实现过程为：41)将相似度矩阵作为谱聚类算法的输入，相似度矩阵可以看作是图模型的邻接矩阵，通常用来构建图模型；具体来说，相似度矩阵中的元素表示样本之间的相似程度，将其看作是一个无向加权图中的边权值；然后谱聚类算法会基于相似度矩阵计算拉普拉斯矩阵和谱矩阵，再得到其特征值和特征向量；42)先从小到大对特征值进行排列，再选取最小的k个特征值对应的特征向量作为降维后的特征向量矩阵，矩阵的每一行即为样本映射的特征；43)最后使用kmeans聚类算法对降维后的特征向量矩阵进行聚类，最终获得测试用例的聚类结果。6.根据权利要求5所述的基于调用依赖图的测试用例聚类分组方法，其特征在于，采用
最大化特征裂隙的方法来求取最优的k值。7.根据权利要求2所述的基于调用依赖图的测试用例聚类分组方法，其特征在于，所述步骤12)中，通过定义规则来识别标识符、根据调用依赖关系寻找节点和构造调用依赖图，具体内容为：分析测试用例中每个断言与其他代码语句之间的调用依赖关系；121)代码表达式声明了对象，但表达式中不包含其他任何变量，只需检测声明的对象的名称是否为前向节点寻找的标识符；若是，则添加当前节点至图中，无需更新标识符集，并继续寻找后继节点；若不是，则继续寻找目标节点；122)代码表达式声明了对象，并通过调用构造器、使用类实例的静态字段、调用方法的方式来给对象赋值或实例化，且表达式中使用了其他变量，则先检查声明的对象名称是否为前向节点寻找的标识符；若是，则添加当前节点至图中，并更新当前的标识符集，继续寻找后继邻居节点；若不是，但检测到前向节点寻找的标识符是表达式中的其他变量，则依然添加当前节点至图中，并更新当前的标识符集，接着寻找后继邻居节点；123)代码表达式只有方法调用，没有声明任何对象，只需检测表达式中是否使用了前向节点寻找的标识符；若包含，则添加当前节点至图中，并更新当前的标识符集，继续寻找后继邻居节点；若不包含，则继续寻找目标节点。8.根据权利要求2所述的基于调用依赖图的测试用例聚类分组方法，其特征在于，所述步骤13)从每个断言开始，根据调用依赖关系逆向地构造测试用例的调用依赖图；调用依赖图的节点和边的定义为：节点包含编号、代码语句、后继邻居节点信息；边表示其连接的两个节点的代码语句之间存在直接的调用行为；构造调用依赖图是从测试用例的断言出发，并不断地寻找代码语句之间的调用依赖关系，直至依赖结束；具体实现过程为：131)获取测试用例代码中所有的断言语句并封装成节点，将它们作为头部节点的后继邻居节点；132)自每个断言节点开始，进行基于工作队列的迭代过程，工作队列初始状态只包含当前断言节点；识别并迭代工作队列中节点的代码语句中包含的每个标识符，对于标识符的每次使用和定义，都会将对应的节点和边添加到图中，并更新工作队列以及当前节点的后继邻居节点列表；当工作队列为空时，该断言节点的调用依赖关系结束；133)对于每个断言节点，执行上述调用依赖关系的分析过程，直至所有断言节点的调用依赖关系结束，则调用依赖图的构建完毕。9.一种计算机设备，其特征在于：该计算机设备包括存储器、处理器及存储在存储器上并可在处理器上运行的计算机程序，处理器执行上述计算机程序时实现如权利要求1-8中任一项所述的基于调用依赖图的测试用例聚类分组方法。10.一种计算机可读存储介质，其特征在于：该计算机可读存储介质存储有执行如权利要求1-8中任一项所述的基于调用依赖图的测试用例聚类分组方法的计算机程序。

技术总结
本发明公开一种基于调用依赖图的测试用例聚类分组方法，首先构建测试用例的调用依赖图，并将其转换为节点带属性的图，然后使用最短路径图内核计算测试用例的带属性图之间的相似度，再求取代表整个测试套件相似性的相似度矩阵，最后为测试用例进行聚类分组。本发明利用JavaParser提取出测试套件中所有的测试用例，并分析断言与其他代码语句之间的调用依赖关系。相比其他的可读性增强工具，本发明解决了随机单元测试用例生成工具自动构建的大量测试用例的顺序随机杂乱且其中有些测试用例检查相似的功能行为等问题，利用相似关系和聚类算法为测试用例进行分组归纳，进而提高测试用例的可读性和可理解性，降低维护成本，提高软件开发和测试的效率。高软件开发和测试的效率。高软件开发和测试的效率。


技术研发人员：余萍 刘相君 万玲
受保护的技术使用者：南京大学
技术研发日：2023.04.24
技术公布日：2023/8/9