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

向毅 等: 基于多样性 SAT 求解器和新颖性搜索的软件产品线测试 2825

定义 2. 特征模型的一个配置 (configuration) 或产品 (product) 是一个集合 cf = {±x 1 ,±x 2 ,...,±x n } , 其中 +x i 和 −x i
分别表示第 i 个特征 x i 被选中和未被选中. 注意一个特征仅有被选中和未被选中两种状态, 且必居其一. 这种集合式
b i 取 1 (或 b i 取 0 (或
表示的产品可自然地转换成二元向量 b = [b 1 ,b 2 ,...,b n ] , 其中 true) 当且仅当 x i 被选中; 否则,
false). 一个配置 cf 是有效 (或可行) 的当且仅当特征模型的约束集 L 均得以满足. 否则, 称该配置是无效的 (或不
可行的). 集合形式的定义便于解释如何计算配置之间的距离, 而向量形式的定义则与本文所提算法的实现直接相关.

Mobile phone x 1

Calls GPS
x 2 x 3 Screen x 4 Media x 5

Basic Color High resolution Camera MP3
算法的核心思想是: 采用多样性

x 6 x 7 x 8 x 9 x 10

Mandatory Xor Requires
Optional Or Excludes
图 1 简化的移动手机软件产品线所对应的特征模型 [40]

3.2 软件产品线测试相关定义
关于软件产品线测试有以下定义.
定义 3. 软件产品线的测试集 (test suite) 是一个列表 TS = [tc 1 ,tc 2 ,...,tc N ] , 其中 tc i 表示一个测试用例 (test
case), 即某个有效的软件配置, N 表示测试集规模.
软件产品线测试旨在覆盖所有 (或尽可能多) 的 t 个特征的组合, 其中 t=1, 2,…, 于是, 我们有:
定义 4. 若 π 1 ,π 2 ,...,π t 表示集合 {1,2,...,n} 的任意 t ( ⩽ n ) 个不同元素, 则称集合 { ±x π 1 ,±x π 2 ,...,±x π t } 为一个 t-
集合 (t-set). 事实上, t-集合是一个部分配置的产品, 它是有效的当且仅当它未违反 L 中的任何约束.
定义 5. 软件配置 cf 覆盖某个有效的 t-集合 (记为 tset), 当且仅当 cf ⊇ tset 成立. 注意, 测试时我们无需覆盖无
效的 t-集合.
定义 6. 一个测试集 TS 的 t-组合覆盖率 (简称覆盖率) 定义为比率:

N ∪

VT tc i
i=1
×100% (2)
|VT fm |
其中, VT fm 表示给定特征模型 (记作 fm) 的所有有效 t-集合的集合; VT tc i 表示测试用例 tc i 所覆盖的所有有效 t-集
合的集合; |·| 表示集合的势. 显然, 覆盖率最大为 100%, 是测试所追求的最高目标.
4 基于多样性 SAT 求解器和新颖性搜索的软件产品线测试方法
本文所提出的 dSATNS SAT 求解器产生测试用例, 运用 NS 算法的归档策略
维护测试集的多样性, 并以迭代改进的方式不断提升当前测试集的多样性, 进而覆盖更多特征组合或发现更多缺
陷. 如算法 1 所示, 首先采用 rSAT4J 随机地生成一个初始测试集 tc worst (第 1 行); 然后, 初始化概率向量 p =
[p 1 , p 2 ,..., p n ] (第 2 行); 接着, 算法进入迭代循环阶段 (第 3–10 行): 只要终止条件未满足, 则采用函数 Diver-
seSATSolving 生成测试用例 c 并随机地选择归档策略 GlobalArch 或 LocalArch 将 c 加入测试集 TS . 事实上, 算