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

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

fitness values. In the crossover and mutation process, excellent test cases with a large path level depth in the sample set are introduced for
reuse to generate test data covering the target path. Finally, individuals with higher fitness during the evolutionary generation are saved,
and C-SVMXGBoost is updated, so as to further improve the test efficiency. Experiments show that C-SVMXGBoost is more suitable for
solving the path prediction problem and improving the test efficiency than other chained models. Moreover, compared with the existing
classical methods, the proposed method can increase the coverage rate by up to 15%. The mean evolutionary algebra is also reduced, and
the reduction percentage can reach 65% on programs of large size.
Key words: test case; support vector machine (SVM); extreme gradient boosting (XGBoost); chained model; multi-path coverage

1 引 言

手动测试生成满足测试目标的数据会花费测试人员大量时间, 且需测试的目标路径往往有多条. 因此, 自动生
成符合条件的测试数据, 并通过已有数据尝试覆盖多目标路径可有效减轻测试工程师的负担 [1] , 提高测试用例的
生成效率, 也避免了较多重复性的工作.
在多路径覆盖测试生成中 [2−6] , 挖掘覆盖路径与测试用例间的关联性或分析路径间的相似性有助于提高测试
1) 构建链式模型. 利用一定数量的样本优先训练更适用的模型
用例质量. 同时, 为尽早生成覆盖目标路径的测试数据还需建立在用例多样性的基础上. 遗传算法 (genetic algorithm,
GA) 具有生物进化、遗传变异、全局概率搜索等机制, 可生成丰富的测试数据, 其在自动生成测试数据方面的应
用十分广泛. 不过, 传统遗传算法也存在自身缺陷, 如, 容易陷入局部最优, 且随着程序规模增大, 插桩运行被测程
序的时间成本急剧增加, 但通过改进算法可有效缓解此类问题. 我们通过合理重用已有测试用例缓解遗传算法局
部最优问题 [7] , 提高测试效率. 姚香娟等人 [8] 利用后向传播 (back propagation, BP) 神经网络模拟计算个体适应度,
有效地解决了遗传操作中插桩程序耗费时间较长的问题.
此外, 随着机器学习方法的不断成熟, 已有较多学者结合机器学习模型与测试理论进行测试相关领域的研究.
Gong 等人 [9] 提出一种基于代理模型辅助进化的路径覆盖测试数据生成方法, 使用代理模型估计每个个体的适应
度值. 我们在文献 [10] 提出一种支持向量机 (support vector machine, SVM) 回归模型预测适应度值并重用已有测
试数据. 陈铁明等人 [11] 将抽象指令序列 N-Gram 编码作为随机森林 (random forest, RF) 的样本, 构建分类模型, 测
试出恶意代码. Esteves 等人 [12] 使用 XGBoost (extreme gradient boosting) 算法预测软件是否易出现缺陷. 以上机器
学习方法各有优缺点以及适用的场景, 合理利用这些方法可有效提高测试效率.
在众多机器学习模型中, SVM 和 XGBoost 具有小样本、低耗时、高准确性等优点而被广泛应用, 且它们对
于处理不同数据类型具有各自优势.
在真实测试场景中, 测试目标包含的多条目标路径存在一定的联系. 每条路径的每个路径节点均可表示为两
种状态 (即经过或未经过), 则节点状态的预测可看作一个二分类问题. 由于被测程序的输入数据类型各异, 使用单
一的模型进行路径预测具有一定的局限性. 而 SVM 模型训练速度快, 对于数值型样本具有较好的分类效果, XGBoost
模型具有良好的可扩展性, 对于非数值型样本分类效果更佳. 此外, 它们均适用于小样本、高维度的测试数据. 因
此, 融合 SVM 与 XGBoost 模型为生成覆盖目标路径的测试数据奠定基础, 该融合模型具有训练时间较短、可处
理不同数据类型等优势.
鉴于此, 本文提出一种融合 SVM 与 XGBoost 模型并用于遗传算法进行多路径覆盖测试用例生成的策略, 利
用融合模型代替插桩法获取测试数据覆盖的路径, 并通过分析预测路径与目标路径的相关性, 从而实现多目标路
径测试. 主要完成如下几个方面的工作.
(即, 预测效果更佳的模型), 若模型精度未达到
较优值, 则训练另一个模型, 选取每个路径节点的最优子模型, 并根据路径节点出现的顺序将最优子模型链接起
来, 构建 C-SVMXGBoost 链式模型, 将其代替插桩法来预测测试数据的覆盖路径.
2) 融入链式模型. 利用遗传算法进化生成测试用例时, 先初步筛选优秀个体, 通过训练好的链式模型预测当前
测试数据的路径, 并搜索与预测路径相似的目标路径; 再进一步筛选优秀个体, 若存在相似目标路径, 则进行插桩
验证, 获取精确路径, 计算适应度值. 通过计算原训练样本的覆盖路径与目标路径的路径层级深度, 在交叉、变异