Page 246 - 《软件学报》2024年第6期

2822 软件学报 2024 年第 35 卷第 6 期

1 引 言

软件产品线 (software product line, SPL) 是一种有效的软件开发方法, 它在满足软件产品共性的基础上, 可灵
[1]
活地根据用户需求实现软件定制. 国内外众多知名企业, 如华为 (Huawei)、波音 (Boeing)、西门子 (Siemens)、东
芝 (Toshiba) 等, 均有采用软件产品线进行产品研发的经历 [2,3] . 该技术一方面可更好地满足终端用户多样化的需
求, 实现产品定制; 另一方面又可节约开发成本、降低维护工作量以及缩短产品上市周期等 [4] . 例如, 著名的 Linux
操作系统、Eclipse IDE、Drupal 网站开发系统、Amazon 等均是借助产品线技术开发的软件产品. 事实上, 软件产
品线技术采用可复用的模块化软件构件实现软件产品集的开发, 该集合中的软件产品通常由特征模型 (feature
model, FM) 进行描述 [5,6] . 其中, 一个特征通常指系统的某个功能 [1] , 而一个产品则是一个特征的集合. 特征模型明
确了特征之间的约束关系, 进而定义构成有效 (或可行) 软件产品的所有特征组合.
软件产品线带来诸多益处的同时, 也带来一些挑战, 其中之一便是如何保障软件产品线的可靠性. 显然, 软件
产品线测试是降低缺陷 (faults) 在产品间传播风险的关键所在 [7] . 事实上, 单一特征中的缺陷有可能存在于成千上
万个产品之中 [2] . 若不进行充分的测试, 那么将可能出现大量有缺陷的产品. 然而, 软件产品线测试又是一项非常
无法确保
困难的工作, 其原因在于待测试的软件产品数随特征数的增加而呈指数式增长. 理想情况下, 所有有效软件产品均
需被测试, 但这在实际中几乎不可行 (因为待测试的软件产品数量极大). 此外, 即使对小规模软件产品线而言, 测
试所有软件产品是可行的, 但这将导致效率低下. 现实中, 软件测试工程师的测试资源, 如时间和成本等, 往往是有
限的.
因此, 软件测试工程师正不断寻找能减少测试用例个数的测试方法 [8] . 其中, 组合交互测试 [9] 是一种既能减小
测试集规模, 同时又能保证覆盖一定特征组合的测试方法 [10,11] . 该测试方法的基本假设是: 绝大多数缺陷是由少量
特征的交互触发的 [12] . 特别地, t-组合测试要求找到一个可覆盖任意 t 个特征所有可能组合的最小测试集 [13] . 这是
一个 NP 难问题, 研究者们提出了众多贪心和启发式方法予以求解. 典型算法有 CASA [14] , ICPL [15] , ACTS [16] 和
IncLing [17] 等. 然而, 现有的 t-组合测试算法面临可扩展性差的问题 [18] . 对大规模的真实 SPLs, 这些方法经常遇到内
存占用率过高、无法停止和运行时间过长等难题 [18−20] . 虽然 t-组合测试较穷举测试可显著地减少待测试的软件产
品个数, 但这个数可能还是过大而无法满足实际需求. 例如, 由文献 [15] 知, 为特征数为 6 888 的 Linux 内核特征
模型 (即 2.6.28.6-icse11) [21] 实现完全 2-组合覆盖, 需产生至少 480 个软件产品. 事实上, n 个特征的最大 t-组合数为
t t [12] . 显然, 当 和 t 至少一个较大时, 覆盖所有特征组合需产生大量的软件产品. 然而, 这在现实世界中非常
C ·2 n
n
容易发生: 一方面, 绝大多数真实 SPLs 是大规模的, 包含成千上万个特征 (即 n 很大) [21] ; 另一方面, 为了发现更多
缺陷, 高交互强度 ( t > 2 ) 往往是必要的 [22−24] . 例如, Kuhn 等人 [12] 指出, 若实现完全 6-组合覆盖, 则可检测出几乎
所有缺陷. 考虑到以上事实, t-组合测试在实际应用中可能会受到一定限制, 因为它难以有效处理所涉及的大规模
和高交互强度的情形.
解决 t-组合测试可扩展性差的可行途径之一是引入基于相似性的测试方法 [25,26] , 其基本假设是: 不相似的测
试用例较相似的测试用例能检测到更多的软件缺陷 [27,28] . 它与前面提及的 t-组合测试显著不同. 具体地, t-组合测
试运用测试端标准, 即 t-组合覆盖率, 来决定何时停止增加新的测试用例. 当测试集生成后, 必然获得完全 t-组合
覆盖. 相反, 基于相似性的测试则运用相似性 (或距离) 度量作为选择下一个测试用例的标准. 在生成测试集的任
何时候, 需增强当前测试集的多样性以实现特定目标, 如最大化缺陷检测率或覆盖率等. 因此, 基于相似性的测试
100% 的 t-组合覆盖率, 可能会在一定程度上影响测试集的缺陷检测能力 [29] . 此外, 在 t-组合测试中, 测
试用例个数及算法的终止均无法人为控制. 相反, 基于相似性的测试则可灵活地设置待生成的测试用例个数及运
行时间 [20] . 在实际应用中测试资源有限的情形下, 上述灵活性大有裨益. 当前, 已存在一些基于相似性的软件产品
线测试方法 [20,29−33] . 有关这些方法的详细介绍将在第 2 节给出.
在基于相似性的软件产品线测试方法中, 如何产生可行且多样的测试用例以及如何维护所产生测试用例的多
样性是两个关键问题. 针对前者, 实践表明 [20,33,34] : 采用可满足性 (satisfiability, SAT) 求解器是生成可行测试用例
[5]
的一种有效方法. 数学上, 特征之间的约束可表达为合取范式 (conjunction normal form, CNF) , 这正是 SAT 求解