一种基于程序路径相似度的测试用例复用方法与流程

1.本发明属于计算机信息处理以及软件工程测试自动化领域，具体涉及一种基于程序路径相似度的测试用例复用方法。


背景技术：

2.在软件测试过程中，设计测试用例往往需要大量的人力和时间，而在代码版本变更后的回归测试中，如果可以复用之前版本设计好的测试用例，在其基础上进行增删和修改，就可以大大减少测试用例设计的工作量，提高测试效率，加快软件开发流程。
3.传统的测试用例复用方法主要都是基于关键词检索和形式化建模，不能敏感地根据不同代码版本之间的差异来准确复用测试用例。例如，对于目前流行的敏捷开发而言，软件的两个不同版本之间的区别可能仅仅加入了一个新的功能，而目前存在的测试用例复用方法大都不能利用软件两个不同版本之间的高相似度。
4.目前，主要的测试用例复用方法主要有：基于测试用例推理的复用，基于函数调用路径相似度的复用，基于bert计算测试数据语义向量相似度的复用等等。
5.以上几种方法中，基于测试用例推理的复用，建立了一个测试用例相似度度量模型，设计了测试用例库中检索测试用例的算法，忽略了测试用例与软件本身的关联性，只能找到语义上与目标测试用例相似的测试用例供用户修改后使用。基于函数调用路径相似度的复用，是利用新旧函数里发生变化的函数，找到其会影响到的相关函数，得到函数调用路径，根据调用路径与测试用例的对应关系形成复用测试用例集选择测试用例。它算法上比较简单，但是在待测改变路径确认方法中的“相关函数”的判定方法，以及在测试用例复用过程中测试用例的变更等步骤需要由人工完成，仍需要一定的人力和时间。基于bert计算测试数据向量相似度进行推荐，只关注两个测试数据向量相似度并根据相似度推荐用例，无关不同版本代码的高相似度，故在这种场景下用例复用效率和准确率也不甚理想。


技术实现要素：

6.针对现有测试用例复用方法考虑单元测试、回归测试的情况较少以及在面临大量测试数据时，复用的效率与质量都有较大程度降低，难以满足测试人员需求的问题。本发明提出一种基于程序路径相似度的测试用例复用方法，目的是在单元回归测试中能够有效复用先前版本程序的测试用例。
7.本发明包括以下步骤：
8.s1、使用clang编译器编译新旧版本代码，获得llvm ir中间代码，对其静态分析得到程序控制流图。
9.s2、基于s1中生成的程序控制流图，遍历并生成对应的静态程序路径序列列表。
10.s3、插桩并收集旧版本软件在使用原测试用例时运行的动态程序运行路径。
11.s4、比对每个测试用例的动态程序运行路径，并将其与对应的静态程序路径相绑定。
12.s5、根据新旧程序的静态程序路径序列列表，计算新程序路径与旧程序路径的相似度，根据相似度排名复用最相似的路径对应的测试用例。
13.s6、根据复用的测试用例在新版本程序的路径覆盖信息，找到未覆盖的路径。
14.s7、对于每条未覆盖的路径，遍历其基本块收集约束条件，使用z3约束求解器试图求解，生成新的测试用例加入新测试用例集。
15.本发明的有益效果在于：
16.采用本发明的方法，可以在程序源代码变更不多的情况下，根据新版本代码与旧版本代码之间的高相似度，复用先前版本代码的测试用例集。通过控制流分析程序路径以及计算程序路径的相似性，比较精确地复用对应旧路径的测试用例，并且能使用约束求解器为未覆盖的路径自动生成新的测试用例，大幅度地提高了程序员设计测试用例的效率。
17.现有的测试用例复用方法，忽略了程序测试数据与程序结构之间的关联绑定关系；本发明通过控制流静态分析和路径相似度计算，更好地体现程序的控制流信息的传递过程和新旧程序的异同之处，以及结合动态程序执行覆盖信息，保障了数据的准确度，将测试用例与源程序路径有机结合；同时，结合z3约束求解器的使用自动生成更完善的测试用例，也进一步提高了发明的实用性。
附图说明
18.图1是本发明所描述方法的流程示意图；
19.图2是一组简单示例程序的控制流图、路径列表信息；
20.图3是示例程序测试用例复用的信息。
具体实施方式
21.下面结合附图和实施方法对本发明做进一步的详细描述。
22.为实现上述目的，本发明的技术方案为如下几个步骤：
23.s1、使用clang编译器编译新旧版本代码，获得llvm ir中间代码(所述的llvm是一款开源的编译器基础设施，ir全称intermediate representation，即中间表示，是llvm对于其所有编译前端和后端都通用的中间表示文件，语法类似于汇编)，对其静态分析得到控制流图。
24.s2、基于s1中生成的程序控制流图，遍历并生成对应的静态程序路径序列列表。
25.s3、插桩并收集旧版本软件在使用原测试用例时运行的动态程序运行路径。
26.s4、比对每个测试用例的动态程序运行路径，并将其与对应的静态程序路径相绑定。
27.s5、根据新旧程序的静态程序路径序列列表，计算新程序路径与旧程序路径的相似度，根据相似度排名复用最相似的路径对应的测试用例。
28.s6、根据复用的测试用例在新版本程序的路径覆盖信息，找到未覆盖的路径。
29.s7、对于每条未覆盖的路径，遍历其基本块收集约束条件，使用z3约束求解器试图求解，生成新的测试用例加入新测试用例集。
30.在某一实施例中，在s1中，使用llvm项目的clang编译器，对于新旧版本程序编译生成llvm ir格式的中间代码文件，由于llvm对于ir文件有内置的cfg(控制流图)结构，因
此可以获得程序的控制流图。
31.在某一实施例中，在s2中，对ir文件静态分析，使用深度优先搜索遍历步骤s1中生成的新旧两个版本程序中目标函数的控制流图，生成静态程序路径列表(s1得到的是整个程序的控制流图，而由于本技术只针对单元函数测试中的用例复用，s2只需要对目标函数进行分析)。
32.在某一实施例中，在s3中，对新旧版本代码的ir文件的基本块分别进行插桩，使其在被执行到时能够记录，编译生成测试对象可执行程序；利用准备的旧版本测试用例，在旧版本程序上执行测试；测试完成后收集分析每个测试用例与其相对应的执行路径信息(基本块序列列表)。
33.在某一实施例中，在s4中，根据s3中收集的每个测试用例的执行路径信息，与步骤s2中的旧版本程序的静态程序路径序列列表相比对，把对应的测试用例和静态路径进行绑定。
34.在某一实施例中，在s5中，根据s2中的新版本静态程序路径序列列表，由以下公式计算每条新路径与旧路径的相似度，并复用旧版本程序的测试用例集中每条最相似的路径所对应的测试用例，加入到新版本测试用例集中。
[0035][0036]
其中，pi与pj分别是需要计算的新路径与旧路径，sim(pi,pj)：针对新版本程序路径pi和旧版本程序路径pj，两条路径的相似程度；n：程序路径的属性总数量；sim2(ar(pi),ar(pj))：针对新版本程序路径pi和旧版本程序路径pj的第r个属性，两条路径在此属性上的相似程度；ar：针对每条程序路径，提前定义好的各种属性，例如节点数量、路径的约束条件的字符串表示等；ωr：针对每条路径的属性，提前设置好的计算权值。
[0037]
在某一实施例中，在s6中，利用s5中得到的可复用测试用例，在新版本程序上执行测试，获取用例覆盖到的路径信息，关联绑定新版本程序的静态路径，并将将未覆盖的路径加入待求解路径集。
[0038]
在某一实施例中，在s7中，对于s6中获取的待求解路径集中的每条程序路径，遍历其所有基本块获得与测试变量相关的约束条件并序列化，使用z3约束求解器对序列化的约束条件尝试求解，若成功求解，则将计算结果当作新生成的测试用例加入新版本测试用例集中，否则该路径复用s5中得到的旧版本程序中最相似路径的测试用例，并标记为待修改，测试人员利用人机接口确认或修改。
[0039]
实施例：
[0040]
根据上述技术步骤，如图1所示，本实施例的步骤如下：
[0041]
(1)通过llvm编译器框架开源项目的clang编译器对测试对象新旧版本程序，分别编译得到llvm ir格式的中间代码文件，对于ir中间文件，llvm有内置的cfg(控制流图)结构，其基本节点是llvm的basicblock(基本块)结构，即包含若干顺序执行的指令的基本块，根据分支条件，基本块之间有跳转关系，这些跳转关系构成了程序的控制流关系，如图2中的控制流图所示。
[0042]
(2)对ir后对其进行静态分析，在不修改整个程序ir的情况下，对于目标待测函数，深度优先遍历其控制流图中的各个基本块节点，并用定义好的列表存放路径上的所有节点序列，形成静态程序路径列表，如图2所示。其中由于cfg中可能出现环形结构，因此需要使用染色法记录每个基本块是否已访问，防止陷入死循环。
[0043]
(3)对ir进行修改，从而完成插桩，具体为：对于目标待测函数，在每个基本块basicblock第一条指令前插入探针，当代码执行到该基本块时，就将该基本块的唯一标识符序列化并加入到执行信息字符串中。实际测试程序运行后，将执行信息字符串反序列化并保存成执行路径，这时就能记录每个测试用例的动态执行路径了。
[0044]
(4)将步骤(3)中每个测试用例的动态执行路径与步骤(2)中的静态路径集做比对，将测试用例绑定到旧版本程序的目标函数中对应的静态路径上，如图3中的旧路径对应的“testcase”信息。
[0045]
(5)计算新版本程序的所有静态路径与旧版本程序静态路径间的总相似度，步骤是分别计算路径各个属性的相似度后，加权求方均根。根据相似度排名复用最相似的路径对应的测试用例，如图3中的相似度信息所示。
[0046][0047]
进一步的，其中每条路径的节点数量属性(a
r1
(p)为路径的基本块数量)，使用以下公式计算：
[0048][0049]
对于路径的约束条件字符串属性(a
r2
(p)为路径的约束条件字符串)，使用编辑距离算法计算：
[0050][0051]
其中str1、str2分别是两条路径的约束条件字符串；levenshtein函数用动态规划算法计算两个字符串之间的编辑距离；strlen函数用于计算字符串长度。
[0052]
(6)将得到的可复用测试用例，在插桩后的新版本程序上执行测试，获取用例覆盖到的路径信息，并将测试用例与新版本程序的静态路径相绑定，将未覆盖的路径加入待求解路径集，如图3中的新路径的覆盖信息所示。
[0053]
(7)对于步骤(6)中获取的待求解路径集中的每条程序路径，遍历其所有基本块获得与测试变量相关的约束条件并序列化，使用z3约束求解器(由微软研究院开发的一个高性能定理证明器，可用于约束条件求解)的c++api对序列化的约束条件尝试求解，若成功求解，则将计算结果当作新生成的测试用例加入新版本测试用例集中，如图3中的新测试用例所示。
[0054]
本发明所述的方法并不限于具体实施方式中所述的实施例，本领域技术人员根据本发明的技术方案得出其他的实施方式，同样属于本发明的保护范围。

技术特征：
1.一种基于程序路径相似度的测试用例复用方法，其特征在于该方法包括以下步骤：s1、使用clang编译器编译新旧版本代码，获得llvm ir中间代码，对其静态分析得到程序控制流图；s2、基于s1中生成的程序控制流图，遍历并生成对应的静态程序路径序列列表；s3、插桩并收集旧版本软件在使用原测试用例时运行的动态程序运行路径；s4、比对每个测试用例的动态程序运行路径，并将其与对应的静态程序路径相绑定；s5、根据新旧程序的静态程序路径序列列表，计算新程序路径与旧程序路径的相似度，根据相似度排名复用最相似的路径对应的测试用例；s6、根据复用的测试用例在新版本程序的路径覆盖信息，找到未覆盖的路径；s7、对于每条未覆盖的路径，遍历其基本块收集约束条件，使用z3约束求解器试图求解，生成新的测试用例加入新测试用例集。2.根据权利要求1所述的一种基于程序路径相似度的测试用例复用方法，其特征在于：在s2中，使用深度优先搜索遍历步骤s1中生成的新旧两个版本程序中目标函数的控制流图，生成静态程序路径列表。3.根据权利要求1所述的一种基于程序路径相似度的测试用例复用方法，其特征在于：在s3中，对新旧版本代码的ir文件的基本块分别进行插桩，使其在被执行到时能够记录，编译生成测试对象可执行程序；利用准备的旧版本测试用例，在旧版本程序上执行测试；测试完成后收集分析每个测试用例与其相对应的执行路径信息。4.根据权利要求1所述的一种基于程序路径相似度的测试用例复用方法，其特征在于：在s4中，根据s3中收集的每个测试用例的执行路径信息，与步骤s2中的旧版本程序的静态程序路径序列列表相比对，把对应的测试用例和静态路径进行绑定。5.根据权利要求1所述的一种基于程序路径相似度的测试用例复用方法，其特征在于：在s5中，根据s2中的新版本静态程序路径序列列表，由以下公式计算每条新路径与旧路径的相似度，并复用旧版本程序的测试用例集中每条最相似的路径所对应的测试用例，加入到新版本测试用例集中；其中，p
i
与p
j
分别是需要计算的新路径与旧路径，n是程序路径的属性总数量；sim2(a
r
(p
i
),a
r
(p
j
))是新路径p
i
与旧路径p
j
在第r个属性上的相似程度；a
r
是每条程序路径的属性；ω
r
是每条路径的属性计算权值。6.根据权利要求5所述的一种基于程序路径相似度的测试用例复用方法，其特征在于：所述的每条程序路径的属性包括节点数量属性和对于路径的约束条件字符串属性。7.根据权利要求1所述的一种基于程序路径相似度的测试用例复用方法，其特征在于：在s6中，利用s5中得到的可复用测试用例，在新版本程序上执行测试，获取用例覆盖到的路径信息，关联绑定新版本程序的静态路径，并将未覆盖的路径加入待求解路径集。8.根据权利要求7所述的一种基于程序路径相似度的测试用例复用方法，其特征在于：
在s7中，对于s6中获取的待求解路径集中的每条程序路径，遍历其所有基本块获得与测试变量相关的约束条件并序列化，使用z3约束求解器对序列化的约束条件尝试求解，若成功求解，则将计算结果当作新生成的测试用例加入新版本测试用例集中，否则该路径复用s5中得到的旧版本程序中最相似路径的测试用例，并标记为待修改，测试人员利用人机接口确认或修改。

技术总结
本发明公开了一种基于程序路径相似度的测试用例复用方法。现有的测试用例复用方法，忽略了程序测试数据与程序结构之间的关联绑定关系；本发明通过控制流静态分析和路径相似度计算，更好地体现程序的控制流信息的传递过程和新旧程序的异同之处，以及结合动态程序执行覆盖信息，保障了数据的准确度，将测试用例与源程序路径有机结合；同时，结合Z3约束求解器的使用自动生成更完善的测试用例，也进一步提高了发明的实用性。另外采用本发明可以在程序源代码变更不多的情况下，根据新版本代码与旧版本代码之间的高相似度，复用先前版本代码的测试用例集。通过控制流分析程序路径以及计算程序路径的相似性，比较精确地复用对应旧路径的测试用例。径的测试用例。径的测试用例。


技术研发人员：陈祥献 陈思农 吴建林 于金玲
受保护的技术使用者：杭州金衡昇科技有限公司
技术研发日：2023.05.23
技术公布日：2023/8/24