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

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

法参数的影响.
基于树的分类模型准确率高、复杂度低, 具有较好的分类效果, 在软件缺陷检测方面应用相对广泛. Esteves
等人 [12] 使用 XGBoost 算法预测软件是否易出现缺陷, 并利用预测能力和模型可解释性间的联系, 提出模型采样方
法, 该方法可找到更易出现缺陷的模块, 在特征组合过程中采用穷举法, 这使得在构建模型前需对数据处理花费较
多时间. Bhati 等人 [20] 将 XGBoost 集成到 IDS 中, 为 IDS 提供防范位置攻击的安全性. 杨宏宇等人 [21] 将加权投票
思想引入随机森林分类模型, 加强对 Android 恶意软件的区分, 但解决 APK 文件批量反编译耗时较长.
从现有研究来看, 机器学习方法可很好地与软件测试相结合, 推进测试进程. 有学者将其与遗传算法相结合,
应用于模拟计算适应度值, 完成基于路径的测试用例生成. 但是, 他们未考虑将其应用于多目标路径中, 且有些模
型所需训练时间较长, 预测准确度较低, 这拖慢了测试的整体效率. 还有些学者将机器学习方法应用于二分类或多
分类问题的求解, 以检测软件缺陷.
对于测试用例生成而言, 获取测试数据覆盖被测程序的路径至关重要 [5] . 将路径节点状态看作分类问题, 通过
机器学习方法, 可预测出一条完整的路径, 而且, 随着程序规模的增加, 该方法可有效节省程序的插桩时间. 此外,
结合遗传算法可丰富测试数据的同时, 生成更优秀的测试用例 (即, 可覆盖目标路径的测试数据), 以提高测试效
以测试用例为样本, 几乎无法获得可将路径节点状态
率. 当被测程序较为复杂时, 测试数据的输入类型往往具有多样性. 这些种群个体作为模型的训练样本, 符合小样
本、非线性与高纬度的特征.
针对上面的分析, 本文结合 SVM 模型的小样本、非线性等特性以及 XGBoost 模型的低复杂度、高准确率等
优势, 构建一种基于路径预测的链式模型 C-SVMXGBoost, 代替插桩法获取测试数据的覆盖路径, 根据其路径寻
找并尝试覆盖更多的相似目标路径. 为使生成的测试数据可覆盖更多路径, 合理地重用训练样本中的部分数据
(即, 适应度值较高的个体), 辅助进化生成更优个体, 并将其保留, 用于更新 C-SVMXGBoost 链式模型.
3 总体框架与相关基础

本文利用 C-SVMXGBoost 链式模型实现多路径覆盖测试用例生成 (整体框架如后文图 1 所示), 包括 C-SVM-
XGBoost 链式模型构建 (算法设计见第 4.1 节)、遗传进化测试生成 (算法设计见第 4.2 节) 及 C-SVMXGBoost 链
式模型更新 (算法设计见第 4.3 节) 等过程. 此外, 从模型样本选择、C-SVMXGBoost 链式模型评估等角度设计对
比实验与消融实验等, 结果及其分析见第 5.3 节.
1) C-SVMXGBoost 链式模型构建模块. 根据测试数据及其对应的路径节点覆盖信息, 利用 SVM 和 XGBoost
模型构建每个路径节点的状态预测子模型, 并依据路径节点出现顺序筛选每个节点精度最高的子模型, 依次将其
链接构建路径预测链式模型.
2) 遗传进化测试生成模块. 将初始种群输入到链式模型中预测当前测试数据的覆盖路径, 搜索与预测路径相
似的目标路径, 对存在相似路径的测试用例获取精确路径, 计算个体适应度, 同时在种群进化中重用路径层级深度
较大的测试数据, 进而生成目标测试用例.
3) C-SVMXGBoost 链式模型更新模块. 在种群进化中保留优秀个体以及它们对应的精确路径, 将具有精确路
径的数据作为新样本, 更新 C-SVMXGBoost 链式模型, 在后续遗传进化中引用.
3.1 预备知识

SVM 模型是按监督学习方式对数据进行二元分类以获得较好泛化能力的广义分类器. 在实际的软件测试中,
(即: 测试数据覆盖节点时其状态值为 1, 反之为 0) 分离的超
平面, 故这里引入 hinge 损失函数, 利用 SVM 求解能将被覆盖节点与未被覆盖节点分离的最优超平面, 即为目标
函数, 如公式 (1) 所示:
 n ∑
 1
 2
 min ∥ ω ∥ +C

 ξ i
 2 (1)
 i=1



 T
 s.t. y i (ω x i +b) ⩾ 1−ξ i , ξ i ⩾ 0, i = 1,2,...,n