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

钱忠胜 等: 结合 SVM 与 XGBoost 的链式多路径覆盖测试用例生成 2799

其中, n 为测试样本数; C 为惩罚参数 (C > 0); ξ i 为松弛变量 (ξ i = max(0,1−y i (ω i +b))) , 即为 hinge 损失函数; ω 为
分离超平面系数, b 为分离超平面常量参数, 这两个参数均需通过模型训练获取; x i 为第 i 个训练样本, y i 为第 i 个
样本对应的路径节点状态.

C-SVMXGBoost 链式模型构建模块
SVM XGBoost C-SVMXGBoost
原始
样本 … … 子模型 1
… … 建立第 1 个子模型 构建 子模型 2
提取测试 … … 建立第 3 个子模型 Y 轴 … 获取 模型
建立第 2 个子模型
数据和路径 模型 子模型 3
… … … …
建立第 n 个子模型 X 轴
… …
子模型 n
保存模型 更新模型库 更新模型 ( 满足条件

K(x i ∗ x j ) 为高斯核函数. 根据公式
模型库 ) 更
获取样本 新样本 新
( 更新前 获取模型 获取模型 ( 更新后 样
本
C-SVMXGBoost 链式模型
更新模块
)
)
遗传进化测试 输入 获取相似路径
生成模块 输出 C-SVMXGBoost 模型
子模型 1 … …
输入
输出 … 插桩 …
子模型 2 … …
输入 … 验证 …
… 进化 输出结果 …
子模型 3 输出 … … … …
输入 … … 生成
…
输出
… … … 搜索
输入 输出 相似路径
预测
输出
子模型 n 路径 …
… … … …
重用优秀测试用例
图 1 链式模型构建与用例生成框架

通过拉格朗日乘子法可将上述有约束条件的目标函数转化为无约束的, 并采用高斯核函数将非线性分类问题
转换为某个空间维度的线性分类, 如公式 (2) 所示:
 n
 1 n ∑∑ n ∑


 min
 α i α j y i y j K(x i ∗ x j )− α i

 2

 i=1 j=1 i=1 (2)
 n ∑



 s.t. α i y i = 0, 0 ⩽ α i ⩽ C, i = 1,2,...,n




i=1
其中, α i 和 α j 分别为第 i 和 j 个样本对应目标函数中的拉格朗日乘子, 且 α i ,α j ⩾ 0 ; y i 和 y j 分别为第 i 和第 j 个样
∗ T
∗
∗
∗
本的分类值, 即路径节点状态; (2) 即可求得最优 α = (α ,α ,...,α ) .
1 2 n
n ∑
ω = α y i x i (3)
∗
∗
i
i=1
n ∑
∗ ∗
b = y j − α y i (x i ∗ x i ) (4)
i
i=1