医疗机器人控制软件测试数据的生成方法、注入方法

摘要

本发明提供了一种医疗机器人控制软件测试数据的生成方法、注入方法，生成方法包括步骤：S1、生成被测软件的CFG控制图；S2、计算CFG控制图内的有限路径数量；S3、以有限路径数量作为被测试软件的输入参数，进行总群的初始化；S4、若不存在未被覆盖的路径或者运行代数最大时，得到最佳染色体；S5、若存在未被覆盖的路径或者运行代数最大时，进行个体评价；S6、对染色体进行交叉操作和变异操作；S7、计算染色体的适应度值；S8、若适应度值不符合要求，则选择下一代个体，运行代数增加，并返回至步骤S4。采用本发明的方法能以更少的评估量提供更好的覆盖范围。

权利要求

1.一种医疗机器人控制软件测试数据的生成方法，其特征在于，包括步骤：S1、生成被测软件的CFG控制图；

S2、计算CFG控制图内的有限路径数量；

S3、以有限路径数量作为被测试软件的输入参数，进行总群的初始化；

S4、若不存在未被覆盖的路径或者运行代数最大时，得到最佳染色体；

S5、若存在未被覆盖的路径或者运行代数最大时，进行个体评价；

S6、对染色体进行交叉操作和变异操作；

S7、计算染色体的适应度值；

S8、若适应度值不符合要求，则选择下一代个体，运行代数增加，并返回至步骤S4。

2.根据权利要求1所述的生成方法，其特征在于，采用CFG内的循环数计算CFG控制图内的有限路径数量。

3.根据权利要求1所述的生成方法，其特征在于，所述交叉操作包括：以另一条染色体上的非重复测试用例对每条染色体上的重复测试用例进行替换。

4.根据权利要求1所述的生成方法，其特征在于，所述变异操作包括：找到染色体内所有重复的测试用例，选择其中一个测试用例进行突变。

5.根据权利要求1所述的生成方法，其特征在于，所述计算染色体的适应度值的步骤中，以给定测试用例作为输入参数，根据测试用例遍历的路径集、有限路径数量计算得到测试用例的适应度值。

6.根据权利要求1所述的生成方法，其特征在于，采用排序选择下一代个体。

7.根据权利要求1所述的生成方法，其特征在于，若适应度值符合要求，则采用Q‑learning，对测试用例进行了修改。

8.根据权利要求1所述的生成方法，其特征在于，选择下一代个体时，采用memtic操作提高染色体的适应度。

9.根据权利要求1所述的生成方法，其特征在于，在适应度值不符合要求时，采用额外的搜索步骤，选择下一代个体。

10.一种医疗机器人控制软件测试数据的注入方法，其特征在于，将由权利要求1～9任一项所述的生成方法生成的测试数据，注入到医疗机器人控制器的嵌入式软件中。

说明书

医疗机器人控制软件测试数据的生成方法、注入方法

技术领域

[0001] 本发明属于医疗机器人测试技术领域，涉及一种医疗机器人控制软件测试数据的生成方法、注入方法。

背景技术

[0002] 嵌入式软件在医疗机器人、交通系统、工业控制领域等应用越来越广泛。其应用需求的不断增长对嵌入式软件的质量提出更高要求。软件测试是保证其软件可靠性的主要手段。

[0003] 软件测试是一项繁琐、复杂的工作，自动化测试是提高效率、降低成本的有效途径，其中测试数据的生成是软件测试的关键，将智能优化算法如遗传算法、粒子群算法等应用到软件测试数据自动生成过程中，其生成的效率会有明显提高。

[0004] 但这些单一算法都有不足之处，如遗传算法、粒子群算法均存在早熟和局部搜索能力差等缺陷，禁忌搜索算法过多依赖初始解和迭代次数，不少研究者对这些算法进行改进，测试数据生成效率较传统优化算法得到明显提高。其中运用最广泛的遗传算法在测试数据生成方面是一种实用的算法，但是其自身存在局限性，如过早收敛、优化效率低等，并且种群规模大，迭代分析次数过多，导致了算法运行时间长，且易受参数影响。

发明内容

[0005] 本发明提供了一种医疗机器人控制软件测试数据的生成方法、注入方法，其能以更少的评估量提供更好的覆盖范围。

[0006] 本发明采用的技术方案是：

[0007] 一种医疗机器人控制软件测试数据的生成方法，包括步骤：

[0008] S1、生成被测软件的CFG控制图；

[0009] S2、计算CFG控制图内的有限路径数量；

[0010] S3、以有限路径数量作为被测试软件的输入参数，进行总群的初始化；

[0011] S4、若不存在未被覆盖的路径或者运行代数最大时，得到最佳染色体；

[0012] S5、若存在未被覆盖的路径或者运行代数最大时，进行个体评价；

[0013] S6、对染色体进行交叉操作和变异操作；

[0014] S7、计算染色体的适应度值；

[0015] S8、若适应度值不符合要求，则选择下一代个体，运行代数增加，并返回至步骤S4。

[0016] 作为本发明的进一步改进，采用CFG内的循环数计算CFG控制图内的有限路径数量。

[0017] 作为本发明的进一步改进，所述交叉操作包括：

[0018] 以另一条染色体上的非重复测试用例对每条染色体上的重复测试用例进行替换。

[0019] 作为本发明的进一步改进，所述变异操作包括：

[0020] 找到染色体内所有重复的测试用例，选择其中一个测试用例进行突变。

[0021] 作为本发明的进一步改进，所述计算染色体的适应度值的步骤中，以给定测试用例作为输入参数，根据测试用例遍历的路径集、有限路径数量计算得到测试用例的适应度值。

[0022] 作为本发明的进一步改进，采用排序选择下一代个体。

[0023] 作为本发明的进一步改进，若适应度值符合要求，则采用Q‑learning，对测试用例进行了修改。

[0024] 作为本发明的进一步改进，选择下一代个体时，采用memtic操作提高染色体的适应度。

[0025] 作为本发明的进一步改进，在适应度值不符合要求时，采用额外的搜索步骤，选择下一代个体。

[0026] 此外，本发明还提供了一种医疗机器人控制软件测试数据的注入方法，将由上述的生成方法生成的测试数据，注入到医疗机器人控制器的嵌入式软件中。

[0027] 与现有技术相比，本发明的有益效果是：本发明的生成方法，考虑了覆盖所有有限路径的准则，将问题转化为一个搜索问题，并求解，较于现有技术而言，测试数据生成速度将会比许多现有的进化或元启发式算法更快，并且可以以更少的评估量提供更好的覆盖范围。

[0028] 附图说明书

[0029] 图1为种群中一个给定染色体的示意图；

[0030] 图2为实施例1所述生成方法的流程图。

具体实施方式

[0031] 以下通过特定的具体实例说明本发明的实施方式，本领域技术人员可由本说明书所揭示的内容轻易地了解本发明的优点。本发明亦可通过其他不同的具体实例加以实施或应用，本说明书中的各项细节亦可基于不同观点与应用，在不背离本发明的精神下进行各种修饰与变更。

[0032] 名词解释：

[0033] CFG：控制流图(Control Flow Graph,CFG)也叫控制流程图，是一个过程或程序的抽象表现，是用在编译器中的一个抽象数据结构，由编译器在内部维护，代表了一个程序执行过程中会遍历到的所有路径。

[0034] SUT：(software under the test，SUT)处于测试中的软件，软件测试。

[0035] Memtic：(Memtic algorithm)本发明是结合了遗传算法和强化学习，作为其中的一个Memtic步骤。通过将Q‑Learning作为Memtic algorithm以提高染色体的适应度。

[0036] Jaccard：Jaccard index,又称为Jaccard相似系数(Jaccard similarity coefficient)用于比较有限样本集之间的相似性与差异性。Jaccard系数值越大，样本相似度越高。

[0037] Q‑learning：Q‑Learning是强化学习算法中value‑based的算法，Q即为Q(s，a)，就是在某一个时刻的state状态下，采取动作a能够获得收益的期望，环境会根据agent的动作反馈相应的reward奖赏，所以算法的主要思想就是将state和action构建成一张Q_table表来存储Q值，然后根据Q值来选取能够获得最大收益的动作。

[0038] 实施例1

[0039] 本实施例提供了一种医疗机器人控制软件测试数据的生成方法，如图1所示，包括步骤：

[0040] S1、生成被测软件的CFG控制图；CFG控制图的生成可以采用现有技术中的工具实现，如如pycfg，Visustin等。

[0041] S2、用CFG的循环数来计算CFG控制图内的有限路径数量Np。

[0042] S3、如图2所示，为了开始在问题的整个状态空间中进行搜索，将首先生成一个随机总体。这个群体中的每条染色体都代表了被测试软件的一个测试集。假设被测试软件的输入参数的数量为Nv，对应CFG内的有限路径数为Np。然后每个染色体的形式为：ti＝[ti(1),ti(2)……ti(Np)]，其中每个ti(k)代表一个测试用例，用一组特定的输入参数评估被测试软件的情况。这里ti(k)＝[xik(1),xik(2)……xik(Nv)]，xik(1)为指定测试用例ti(k)中被测试软件的第l个输入参数。

[0043] S4、若不存在未被覆盖的路径或者运行代数最大时，得到最佳染色体，即得到测试数据。

[0044] S5、若存在未被覆盖的路径或者运行代数最大时，采用公式(1)进行个体评价；

[0045] S6、为了获得更好的性能，本实施例还引入了新的交叉操作和变异操作，更适合于自动化测试数据生成的问题。如果是交叉算子，则考虑每个父节点的子部分，并根据每个子部分中编码的信息选择重组索引。只有当一个染色体中有重复或重复的亚片段时，才会进行突变。

[0046] 交叉操作包括：以另一条染色体上的非重复测试用例对每条染色体上的重复测试用例进行替换。

[0047] 变异操作包括：找到染色体内所有重复的测试用例，选择其中一个测试用例进行突变，突变是通过在这个测试用例中随机改变其中一个输入参数来执行的。利用这种突变方法，可以确保突变染色体的适应度不低于原始染色体。

[0048] S7、计算染色体的适应度值ti，此时，需要运行被测试软件Nv次，每次都以给定的ti(k)作为输入参数。每个执行都遵循控制流图CFG中的一个特定路径。让这个路径用ρi(k)表示，将所有ti(k)遍历的路径集表示为ρi，然后根据公式(1)计算ti的适应度值。

[0049]

[0050] 其中，||表示集合ρi中元素的数量。

[0051] S8、若适应度值不符合要求，则选择下一代个体，运行代数增加，并返回至步骤S4。

[0052] 具体地，采用排序选择下一代个体，同时采用memtic操作提高染色体的适应度，在这一阶段，根据由等式(1)给出的适应度函数是最好的染色体。让这条染色体成为最好。这条染色体通过一个memtic操作，以提高其适应度。如果tbest的适应度fbest为1，则可以找到解决方案，并且不需要进行其他操作。但是，如果fbest小于1，则意味着在最优中至少存在两个最优tbest(k)和tbest(m)，它们对应的路径ρbest(k)和ρbest(m)并且它们是相同。此时，将这种测试用例称为重复的测试用例。同时，很明显，在这种情况下，Np中有一些路径没有被tbest所覆盖。随机选择这样一种路径ρr∈Np，以提高tbest的适应度。其想法是从染色体内的一个测试用例tbest(h)开始，其对应的路径ρbest(h)与ρr最为相似。

[0053] 相似性是用Jaccard指数来度量的。然后修改此测试用例，目的是找到一个可以覆盖ρr的测试用例。如果这个过程成功了。那么，新识别的测试用例将被替换为染色体内的一个重复的测试用例。这样，染色体的适应度就会提高 为了使修改tbest(h)的过程有效，在适应度值符合要求时，采用Q‑learning，对测试用例进行了修改；

[0054] 应用Jaccard相似度指数：

[0055]

[0056] listi和listj是这两条路径。计算1与Jaccard(listi,listj)相似度之间的差值为Jaccard距离公式，即：

[0057] Distance(listi,listj)＝1‑Jaccard(listi,listj)              (3)[0058] 对于每个tbest(k)，计算距离(ρbest(k),ρr)，并根据下面给出的公式(4)[0059]

[0060] 确定ρbest(h)。然后，选择tbest(h)来进行下一步的memtic操作。ρr为未被tbest覆盖的路径，选tbest中与Jaccard距离最短的ρbest(k)为ρbest(h)，并对tbest(h)进行修改。

[0061] 选择tbest(h)后，tbest(h)＝tcur(h)开始强化学习操作。利用Q‑learning，对该测试用例进行了修改，希望能找到一个可以覆盖ρr的测试用例。我们将问题的状态数设置为Nv，被测试软件的输入参数的数量。即，将问题的状态空间定义为s＝{s(1)，s(2)，……，s(Nv)}。在每个状态s(l)中，都定义了动作，以更改tcur中相应的输入参数xcur(l)。让修改后的测试用例为tnext。

[0062] 为了防止一个被丢弃的测试用例覆盖的路径正好没有被被选择的染色体中所包含的测试用例覆盖，在适应度值不符合要求时，在每个遗传迭代结束时使用了一个额外的搜索步骤来检查是否存在这样的情况，如果是则用此测试用例替换种群最佳染色体中一个重复的测试用例。

[0063] 在本实施例中，采用了一种结构性的方法来自动化测试数据的生成过程，并考虑了覆盖所有有限路径的准则。在结构方法中，将问题转化为一个搜索问题，并使用元启发式算法进行求解，提出一种模因算法，其中将强化学习作为遗传算法中的局部搜索方法。该方法在测试数据生成方面比许多现有的进化或元启发式算法更快，并且可以以更少的评估提供更好的覆盖率。此外，本实施例提出的算法的每条染色体都是一个测试集，由许多测试用例组成。强化学习部分接受迄今为止在遗传算法中发现的最佳测试集，并试图通过修改其一个测试用例来改进它，目的是覆盖CFG中的另一条路径。此外还设计了重组和突变算子，它们比遗传算法的标准算子更适合于这一问题，并且该方法在适应度评价的次数和成功率方面都明显优于现代这些算法。

[0064] 实施例2

[0065] 本实施例提供了一种医疗机器人控制软件测试数据的注入方法，将由实施例1生成方法所生成的测试数据，采用专用的软硬件接口和特定的API或数据格式，向在数字孪生仿真环境中运行的机器人控制器软件注入测试数据等作为激励，驱动机器人的机械臂运动，进行机器人控制器嵌入式软件的测试。

[0066] 上述实施例仅例示性说明本发明的原理及其功效，而非用于限制本发明。任何本领域技术人员均可在不违背本发明的精神及范畴下，对上述实施例进行修饰与改变。因此，本发明的权利保护范围，应如权利要求书所列。