Fork me on GitHub

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

本期作者

图片

王京京
哔哩哔哩工程效能团队
高级开发工程师

01 背景

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

02 相关技术

2.1 什么是TCP

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

图片

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

2.2 如何衡量TCP的效果

我们介绍了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遗漏的情况。

2.3 推荐算法

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

03 方法

3.1问题映射

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

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

图片

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

图片

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

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

图片

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

3.2 数据

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

图片

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

图片

3.3 模型

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



04 实验结果

为了探究将推荐算法应用到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的漏测率,但两者本质上并无太大差距。

05 实际落地

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

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

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

图片

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

图片

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

图片

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

图片

06 展望

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

参考文献:

[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


本文地址:https://www.6aiq.com/article/1671626902722
本文版权归作者和AIQ共有,欢迎转载,但未经作者同意必须保留此段声明,且在文章页面明显位置给出