推荐算法在用例排序优化上的应用

随着持续集成和敏捷开发的不断发展，移动应用的发布变得越来越频繁。以B站应用为例，主站粉版APP每周都会发布一次新的版本，主站HD应用的Android端与ipad端每周交替发布新的版本。在应用快速迭代的同时，QA需要在规定时间内进行大量的回归测试以保证应用的质量。一方面，大量的测试用例需要耗费较多的人力和时间，另一方面，BUG检出时间的不确定性导致给予研发修复的时间并不是很充足。因此急需一种技术来帮助QA快速筛选出高风险用例，将BUG的发现时间提前，从而给研发更多时间去修复BUG。在此背景下，我们经过调研后，选择了使用测试用例排序优化技术(Test Case Prioritization，以下简称TCP)来帮助QA对测试用例进行优先级排序，提高测试效率。

测试用例排序优化技术(Test Case Prioritization)最早由Rothermel[1]提出，他对测试优化问题给出了如下定义：

通俗地讲，就是对测试用例集合 T 进行排列，找到一种最优排列 T' ，使得按照这种排列顺序进行测试，能够给到我们最大的收益。TCP的目标标准可能各不相同，在本文及实际应用中，我们希望经过排序后的测试集合能够更早地发现BUG。换句话说，我们希望排列越靠前的用例，检出BUG的概率能够更高。这样一来给予了研发充足的时间去修复BUG，二来帮助QA筛选出冗余的用例，从而降低测试成本。

我们介绍了TCP技术的定义，但还没有对评价函数 f 给出具体的实现方案。一般而言，评价函数 f 可以划分为两类：特定评价函数以及通用评价函数。针对前者，学术界提出了 APFD(Average Percentage of Fault Detection)^[1]指标，这也是TCP问题最常用的评价函数，它的设计目标是衡量TCP技术发现BUG的时机。APFD的定义如下：

APFD的值越接近1，表示发现BUG的时机越早。

针对通用评价函数，我们采用了BUG召回率(recall)作为评价标准。但同时召回率指标又与测试数量高度相关，即如果所有测试用例都被执行，那召回率永远都是100%，因为所有的BUG都被召回了。因此我们设计了 recall_p ，只针对部分测试用例计算其召回率，定义如下 ：

recall越接近1，表示遗漏的BUG越少。

我们利用APFD来评估应用TCP技术后BUG发现的时机是否提前了，同时利用recall来观察在仅使用部分测试用例的情况下BUG遗漏的情况。

推荐算法目前被广泛地运用在广告、搜索等相关领域，业界也有不少成熟的解决方案。简单地讲，推荐算法的输入为用户特征和物品/广告特征，在经过特定模型计算后，算法会给出一个推荐的物品/广告列表。常用的推荐算法包括协同过滤算法、基于内容推荐以及混合推荐。

如何从成千上万个测试用例中，挑选出具有高风险、容易出BUG的测试用例，这看上去是一个相当有挑战的任务。传统上大家都在对测试用例的特征进行深入分析，希望发现那些具有高风险的用例具有的相同特征。但实际上，应用是否出BUG，本质上取决于改动了什么代码。也就是说，我们在分析测试用例特征的同时，还需要对改动代码的特征进行分析，而对代码的分析则更加具有难度。Pan^[2]的研究显示，大部分TCP技术针对代码的特征都仅仅使用了代码行数这种比较浅显、易获取的特征。

既然对代码的分析困难重重，那么有没有办法可以减少甚至跳过对代码的分析呢？受到推荐系统的启发，我们认为可以通过加入需求特征的方式，跳过对代码特征的分析。

如图所示，在推荐系统中，用户通常会有不同的喜好，不同的喜好对应可能不同的感兴趣的物品。而这种喜好可能并不会显示地告诉系统，因此推荐系统会根据用户的特征，结合物品的特征对用户进行推荐。

类似地，不同的需求通常会改动不同的代码，而这些代码则对应会影响某些测试用例。我们希望TCP能够像推荐系统一样，结合需求及用例特征推荐测试用例。

为了将推荐算法应用到TCP问题上，我们将TCP问题重新建模，进行如下定义：

这样我们就将一个TCP问题转化为推荐算法问题，从而可以使用推荐算法解决。

目前我们拥有了需求数据和测试用例数据，如何将它们关联起来从而可以进行模型训练呢？比较容易想到的方法就是将需求数据与测试用例数据做笛卡尔积，也就是对于每一份需求数据，都将其与所有的测试用例进行关联，也即认为一个需求对所有的测试用例都可能产生影响。这种关联方法优点在于减少了遗漏，不会漏掉需求或者测试用例，但也有明显的缺点，需求并不会对所有的测试用例都产生影响。

为此，我们设计了关键词关联法，在不增加工作量的基础上，加强需求与测试用例的关联关系。该方法通过将需求和测试用例拆分为关键词词组，若需求关键词词组与用例关键词词组存在交集，则认为两者存在关联。这也是一种非常直观的方法，即需求对应的业务与测试用例对应的业务如果相同，那么两者之间有较大概率存在关联，反之亦然。

我们使用的需求数据与测试用例数据的特征非常稀疏，且样本数量与业界动则上亿的样本数量相比显得非常少，因此需要精心挑选推荐模型，以求模型能够达到最佳拟合效果。我们比较了Logistic Regression(LR)、Factorization Machine(FM)、Deep Structured Semantic Model(DSSM)、XGBoost、RandomForest等模型算法，并进行了相关实验，最终我们选择了FM模型作为主要的推荐模型。

为了探究将推荐算法应用到TCP问题上的效果，我们设计了以下3个问题来验证我们方法的有效性。

问题1. 我们的方法对比用例随机排序有提升吗？

问题2. 使用需求数据与不使用需求数据，有多大的区别？

问题3. 关键词关联法到底有没有效果？

我们使用了哔哩哔哩粉版6.53.0~6.84.0共计31个版本的应用来进行实验。

问题1的实验结果如上图。APFD的箱型图显示，采用FM算法后，发现BUG的时机相比随机结果提前了非常多，这表明我们的整体方法是有效的。同时，我们使用Recall_{0.5} 来观察BUG的遗漏情况，可以看到在使用一半的测试用例的情况下，平均召回率可以达到90%，即只有10%左右的BUG会遗漏。

问题2的实验结果如上图。从APFD箱型图我们可以看到，尽管使用需求数据与不使用需求数据的APFD在均值上相差仅4~5个百分点，但不使用需求数据的APFD分布更加分散，即仅使用测试用例的情况下，预测BUG的效果并不稳定，并不能稳定将BUG的发现时机提前。再看召回率图则更加明显，仅使用测试用例的模型，其召回率非常不稳定，极端情况甚至出现低于50%的召回率，即使用一半的测试用例，甚至无法召回一半的BUG。这个实验表明，在增加了需求数据后，采用FM算法对测试用例进行排序，其效果更加稳定。

问题3的实验结果如上图。出乎意料的是，全量关联法在APFD上要比关键词关联法表现稍好，即其排列的测试用例，发现BUG的时机要提前一些，但是在召回率上的表现要比关键词关联法稍低一些，且稳定性也不如关键词关联法。因此，是否采用关键词关联法，取决于我们更关注BUG的发现时机，还是BUG的漏测率，但两者本质上并无太大差距。

如何将TCP技术应用于实际的生产中呢？我们选择采用例推荐的方式来应用TCP技术。具体的过程如下：

输入当前版本的需求数据及测试用例数据后，我们会通过已经训练好的FM模型给测试用例打分，进而排序。同时，系统会给排序在前 p % 的用例打上“推荐”标签。QA们在回归测试时，选择优先去测试打上“推荐”标签的用例。在时间充足的情况，QA可以选择回归全量测试用例，由于BUG的发现时间提前了，研发们会有更多时间去修复BUG。而一旦测试时间比较紧急，则可以选择延后测试那些没有被推荐的测试用例，这样可以在尽量保证应用质量的同时，不影响应用迭代发布的时间。

以哔哩哔哩粉版应用为例，首先选择应用及要对用例进行排序的版本，然后根据实际需求选择推荐的用例比例。

点击【用例推荐】后，Jenkins会自动运行数据下载、模型训练、模型预测等过程。

模型在执行完打分程序后，会同步更新至TAPD平台，在每条用例上更新【出BUG概率分】和【是否优先推荐】属性。

在执行完回归测试后，我们也会收集发现的BUG，并计算召回覆盖率，从而观察模型的性能，并进行调整优化。

目前我们已经将需求及测试用例的特征挖掘地差不多了，实际更改模型后也并未取得更好的效果。因此我们还需要将目光投向代码特征，如何在尽可能不增加复杂度及工作量的情况下，获取更多更丰富的代码特征，并加入模型训练，成为我们下一步的目标。

参考文献：

[1] Gregg Rothermel, Roland H Untch, Chengyun Chu, and Mary Jean Harrold, “Test case prioritization: An empirical study”,Proceedings IEEE International Conference on Software Maintenance-1999(ICSM’99).’Software Maintenance for Business Change’(Cat.No. 99CB36360), pp. 179-188, 1999

[2]  Pan, Rongqi and Bagherzadeh, Mojtaba and Ghaleb, Taher A and Briand,Lionel, “Test case selection and prioritization using machine learning: a
systematic literature review”, Empirical Software Engineering, vol. 27,no. 2, pp. 1-43, 2022

以上是今天的分享内容，如果你有什么想法或疑问，欢迎大家在留言区与我们互动，如果喜欢本期内容的话，欢迎点个“在看”吧！