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

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

一定数量的测试样本进行训练, 且它们均包含输入数据与预期输出结果. 每个子模型训练样本的输入数据格式不
同, 其表现形式如公式 (12) 所示, 输出结果为测试数据对应的某一路径节点状态.

(x 1 , x 2 , x 3 ,..., x n ), k= 1

X k =  (12)
 (x 1 , x 2 , x 3 ,..., x n , p 1 , p 2 ,..., p k−1 ), k> 1, k ∈ N
在公式 (12) 中, X k 表示第 k 个子模型样本的输入. 记被测程序的输入数据为 Inp=(x 1 , x 2 ,…, x n ), 其中 x a (a=1,
2, 3,…, n) 为第 a 个输入分量; 记当前测试数据输入插桩程序后获得的覆盖路径为 P=(p 1 , p 2 ,…, p k ) ( {k|k ⩾ 1, k ∈ N} ),
其中 p b (b=1, 2, 3,…, k) 为第 b 个路径节点状态, 且 p b ∈ {0,1} (即测试数据经过节点时其状态值为 1, 否则为 0). 需
注意的是, 每个预测路径节点子模型的训练样本输入均不包括预测节点本身, 例如第 k 个子模型的训练样本输入
不包括第 k 个路径节点状态值, 第 k 个节点状态是由输入数据及前 k – 1 个路径节点状态预测所得. 所有子模型依
′ ′ ′ ′ ′ ′
次输出的预测结果链成一条完整的预测路径 P , 即 P = (p , p , p ,...,p ) .
1
2
k
3
为使样本具有一定的代表性, 在随机生成时会进行筛选, 尽量使其均匀分布在被测程序的输入域. 选用样本的
容量不宜过大或过小. 若样本容量太小, 则无法体现模型的准确性; 若样本容量太大, 则需消耗更多计算资源以及
模型构建时间, 降低了测试效率.
难易覆盖性. 此外, 为避免路径相似度较低时可能丢弃覆盖目标路径中某些难覆盖节点的个体, 这里引入路径层级
3.2 适应度函数设计
适应度函数是筛选优秀个体的关键性影响因素, 根据不同需求设计适应度函数是遗传算法中必不可少的步
骤. 我们通过构建路径预测的链式模型, 从而找到更多相似的目标路径, 尽可能在进化生成过程中充分使用测试数
据, 以覆盖更多的目标路径.
生成易覆盖目标路径的测试数据没有太大意义, 而可通过难覆盖路径节点的测试数据被认为是较优种群个
体. 其中, 路径层级深度与插桩程序中路径节点出现的次序及状态有关, 是衡量路径节点关键性的因素之一.
综上所述, 适应度函数的设计需综合考虑测试数据的覆盖路径 (记为 P=(p 1 , p 2 ,…, p k )) 和目标路径 (记为
P = (p , p ,..., p ) ) 间的相似度, 以及路径层级深度. 本文方法的路径相似度 (记为 Sim)、路径层级深度 (记为
∗
∗
∗
∗
1 2 k
Depth level ) 的计算分别如公式 (13) 和公式 (14) 所示:
k ∑
∗
(p b = p )
b
Sim(P,P ) = b=1 (13)
∗
k
k ∑ *
(p b = p ) 表示测试数据覆盖路径 P 中第 b 个节点与目标路径 P 中第 b 个节点状态相同的数量. 测试数
∗
其中, b
b=1
据覆盖路径与目标路径间的相似度即为两条路径对应节点状态相同的节点数与单条路径总节点数的比值.
p b +ε
k ∑
Depth level = ×h (14)
k
b=1
其中, p b 为测试数据覆盖路径的第 b 个节点的状态; h 为当前路径节点的位置; ε (0< ε ≤0.01) 是一个很小的常量,
以保证在节点状态为 0 时, 该节点路径层级深度不为 0, 本方法设其值为 0.01.
路径相似度从测试用例覆盖能力方面筛选目标个体, 经链式模型选取的测试用例对应的精确覆盖路径与目标
路径间的相似性越高, 表明该个体越容易进化生成目标路径的用例. 同时, 相似性比较的过程涉及目标路径节点的
深度, 从路径节点关键性方面对目标个体择优, 个体穿越路径的层级越深, 表明该个体经过的路径节点越重要, 则
赋予其越大的适应度.
为平衡路径相似度与层级深度对个体适应度的综合影响, 设置了权重系数 α, 由于路径相似度是判别目标路
径是否被覆盖的主要因素, 其权重更大, 故有 0.5<α≤1. 当路径相似度 Sim 为 1 时, 表示当前测试用例已覆盖目标
路径, 则将 α 设置为 1, 此时个体适应度值仅受 Sim 影响, 即适应度值为 1; 当路径相似度 Sim 不为 1 时, 表示当前
测试用例未覆盖目标路径, 此时个体适应度值会受路径相似度与层级深度的共同影响, 因此, 需根据适应度值继续