无人机机载软件测试用例优先级排序技术研究

霍婷婷

（牡丹江师范学院 黑龙江·牡丹江 157012）

0 前言

目前，在无人机系统中，不管是系统控制软件，还是导航系统软件、机载软件，都是以软件技术作为核心的。所以，无人机机载软件的可靠性保证了无人机系统运行安全。同时，无人机系统软件门类很多，每款软件都起着不同的作用。随着无人机已经广泛应用于农作物植保、电力巡检、测绘等领域，无人机系统软件产品规模和复杂性的急剧增加，软件产品质量问题日益突出，事故频频发生，软件产品质量问题已成为人们日益关注的焦点。软件测试作为发现软件问题的一种方法受到了广泛关注。软件测试是软件开发整个流程中必不可少的一环，也是保障软件可靠性的重要手段。软件测试从普通意义上讲，就是为了发现错误而执行程序的过程，其根本目的是在软件产品投入市场之前，通过发现并更正软件中的错误，使软件中的错误密度满足可控要求。软件测试需要在限定的人力、物力和时间内，找出软件中存在的缺陷，并对这些缺陷进行修正，以此来提高软件产品的质量，降低软件使用的风险。

众所周知，在进行软件测试的过程中，软件的复杂程度、开发人员的自身素质以及经验、选择的测试方法以及运用的技术等等都会对软件测试造成重大的影响，那么为了保证测试的质量，人们提出一个新的名词——测试用例。然而，软件测试又是一个十分复杂的过程，其中软件测试计划的制定和相应的测试用例的设计又是至关重要的环节，这两个过程将需要投入大量的时间和人力，其结果将直接决定软件测试的费用、效率和质量。如何对测试用例集进行有效的优化，对系统进行充分有效的测试，是目前软件测试研究领域的关键课题，也是迫切需要解决的课题之一。测试用例集优化技术大致可以分为三类：测试用例选择(Test case selection，TCS)、测试用例约简(Test case reduction，TCR)和测试用例优先级排序(Test case prioritization，TCP)。其中，TCS技术和TCR技术在回归测试中会丢弃一些测试用例，而这些废弃的测试用例也可能会发现软件的缺陷，但TCP技术不会有添加、删除、修改等不可逆操作，因此不会导致可能发现软件缺陷的测试用例的丢失。

1 测试用例优先级排序技术

TCP技术作为典型的回归测试用例预优化方法的一部分，其在提高回归测试效率方面发挥着巨大作用，逐渐成为当前软件行业的研究热点之一。

1.1 测试用例优先级排序技术研究现状

1998年TCP的思想被首次提出，该思想一经提出就指出：首先对测试用例集进行初步选择，然后根据优先级对选择的测试用例进行排序，并通过实验初步验证了该方法的有效性。然后文献[4]给出了TCP的形式化定义，提出了总体策略和附加策略，并基于不同的覆盖率验证了这两种策略的有效性，同时文章还最早提出了平均缺陷检测率（Average Percentage of Fault Detection，APFD）的概念，它是用来评价、比较不同测试用例优先级排序技术有效性的度量法则。实践表明，TCP技术可以帮助测试人员提高缺陷检测率，从而尽快开展软件修复工作。

在无人机机载软件的回归测试中，测试用例同时受到多个排序标准的影响，因此很难按照单一的排序标准对测试用例进行排序以满足实际需要。因此，许多研究者开始将多目标测试用例优先排序(Multi objective test case prioritization，MOTCP)，即将多目标优化与传统TCP技术相结合，从而达到适应于实际工程应用的目的。现有的MOTCP算法根据排序方法的不同可分为两类：加权法和Pareto最优法，其中前者占大多数，后者的使用相对较少。加权法是在确定测试用例的优先级时，将权重分配给多个优化目标，然后根据求和值对测试用例进行排序。实际上，使用加权求和的加权法最终是把多目标问题转化为单目标问题进行求解。而Pareto最优法通过计算Pareto最优解集，给出一组备选的最优TCP方案，其研究算法主要集中在以NSGA-II算法为代表的群体智能算法领域。另外，有研究者将群体智能算法应用于多目标优化领域，主要包括基于粒子群算法和蚁群算法的多目标TCP技术等。

1.2 多目标测试用例优先级排序建模

多目标TCP是在传统排序方法的基础上同时考虑多个排序准则而出现的一种排序方法，根据参考文献[5]给出的多目标优化的定义，可以用以下数学模型对该问题进行描述：

无人机机载软件的回归测试的主要目的是在短时间内发现更多的软件错误，并能利用APFD作为度量准则。对测试用例进行排序后，APFD计算的结果表示测试用例集的缺陷检测率，其中，d为代码的缺陷数，第一个检测到缺陷i的测试用例在执行序列中的位置用TFi表示，则APFD的计算公式可表示为式（1）。

在无人机机载软件的回归测试过程中，如果测试用例还没有被执行，则APFD的值是未知的。因此，代码覆盖率(Code coverage)通常用来代替APFD值作为优化目标，而将APFD值作为衡量TCP效果的准则。为了优先考虑代码覆盖率高、执行时间短的测试用例，本文以平均块覆盖率(Average Percentage of Block Coverage，APBC)为优化目标，计算方法如式（2）所示。在执行测试用例之前，可以通过覆盖率分析工具获取测试用例的覆盖率信息，因此可以在所有测试用例执行之前使用APBC来指导TCP。

其中TBi是序列中发现的第一个错误的用例的位置号，n是测试用例的数量，m是该测试用例集中发现的错误的数量，并且是ETt测试用例t的执行时间。由于APBC是测试用例序列块覆盖率(Percentage of Block Coverage，PBC)的平均值，值越大表示这个序列能尽早地达到更高的块覆盖率。如表1所示，其中A，B，C，D，E为测试用例，相应的行表示这个测试用例覆盖的块。

表1：测试用例和PBC信息对应表

假设测试用例序列Ts1=，Ts2=，其测试用例序列与块覆盖率之间的关系如图1所示。测试用例序列Ts1=执行完测试用例A后覆盖了1块，执行完B后一共覆盖了3块，以此类推。而测试用例序列Ts2=执行完测试用例E后覆盖了3块，执行完A后一共覆盖了4块，执行完C后即覆盖了全部程序块。

图1：测试用例序列与PBC之间的关系

2 无人机机载软件测试用例优先级排序的研究方向

尽管在近几年，对测试用例优先级排序这一课题的研究，研究人员逐渐提出多种技术方法以及度量准则来指导快速有效的回归测试。即使在相关研究领域已取得了丰硕的研究成果，但随着无人机机载软件规模以及种类不断地扩大，现有的TCP技术还将面临更多的挑战。首先要解决 TCP算法的复杂度问题，因此一个重要的研究方向就是找出影响测试用例使用的各种因素，并综合各种因素优化TCP技术。其次，采用更灵活的TCP算法，并利用测试过程的实时反馈信息对它进行动态调整，使其不断地适应不同的测试环境，从而提高回归测试的有效性。

3 结束语

无人机机载软件与传统领域中的银行金融软件一样，本身有着高可靠性和高安全性的要求，在机载软件回归测试的过程中，适当测试用例排序会使得测试人员及早发现源代码中的错误，因此可以使用TCP技术对测试用例集进行优化。随着机载软件的规模及种类不断地扩大，在多目标TCP数学模型的基础上，本文从算法复杂度及实时效果两方面提出了无人机机载软件测试用例优先级排序可能的研究方向。