Page 202 - 《软件学报》2025年第7期

张逍怡 等: 面向智能体路径规划算法的动态随机测试方法 3123

可以有很多种, 这里我们选择经典的二叉树结构.

3.2.2 DRT-PP 设置
对于 DRT-PP 方法, 我们将任务空间 M 的分割份数设为 20, 即令 D 1 = D 2 = D = 20. 如图 5 所示, 当对任务空
间 M 做足够细致的划分时, 我们就能够涵盖多样的威胁分布, 如当 D = 20 时可能的威胁分布情况 (即测试用例)
就有 2 400 种. 在测试开始时, 我们将初始测试剖面的特征矩阵设为 Q 0 = (0.5) 20×20 , 即每个子区域包含威胁的概率为
0.5, 即纯随机测试 (见公式 (17)). 此外, DRT-PP 的可调参数就是每次测试用例执行过后测试剖面的更新幅度 ε, 根
据已有 DRT 相关工作 [18] , 我们分别考察 0.05、0.1、0.15、0.2 这 4 个参数, 即测试剖面的融合率为 5%、10%、
15%、20%. 这里, 我们用 DRT-05、DRT-10、DRT-15、DRT-20 分别代表这 4 个参数下的 DRT-PP 方法.

3.2.3 基线方法设置
本文采用随机测试 RT 作为 DRT-PP 的对比方法. 具体来说, 我们将测试剖面始终设置为 Q 0 = (0.5) 20×20 , 这样
就能对离散化的输入空间进行纯随机采样. 目前, 现有工作并没有针对路径规划算法提出整体性的测试方法, 而为
了进一步凸显 DRT-PP 的优势, 我们基于自适应随机测试思想, 设计一种面向路径规划算法的自适应随机测试方
法 ART, 并将其同样作为测试策略. 具体来说, 每当生成下一个测试用例 t N T +1 时, 我们先通过随机方法生成 N Can 个
候选测试用例, 并计算各测试用例到已生成测试用例集的距离, 最后选择距离已生成测试用例集最近的测试用例
c
c
作为 t N T +1 . 这里, 在计算候选测试用例 t 和已经生成测试用例集 T 的距离 dis(t ,T) 时, 我们分别计算 t 与 c T 包含的
t ∈ T 的距离, 并将距 c c t 2 的
所有测试用例 t 最近的测试用例的距离作为 dis(t ,T) 的值. 而在计算两个测试用例 t 1 和
距离时, 我们先根据公式 (19) 计算它们的威胁分布矩阵 A 和 A , 并将这两个矩阵差的 1-范数 (见公式 (18)) 作为
t 2
t 1
t 1 和 t 2 的距离. 可以看出, ART 同样旨在提升生成测试用例的多样性, 但其没有考虑场景威胁分布的连续性以及测
试过程中对于失效测试用例的寻优性. 对于 ART 算法, 候选集的数量是可以调整的参数, 本文采用较为通用的配
置, 即候选测试用例集包含的测试用例数量为 3 (记为 ART3), 同时我们也考察了候选测试用例集的数量为 5 时的
情况 (记为 ART5).

3.2.4 测试过程设置
为了计算失效度 S (t), 我们在实验过程中将每个测试用例 t 执行 10 次, 即令 N repeat = 10, 并保存每次执行后的
PTH = {pth , pth ,..., pth }. 进一步地, 对于每一种测试策略 (包括 RT、ART、DRT-PP) 的每一次测试
t
t
t
t
输出路径 1 2 10
过程, 我们生成并执行 1 000 个测试用例 t 1 ,t 2 ,...,t 1000 , 并计算它们的失效度 S (t 1 ),S (t 2 ),...,S (t 1000 ), 即令 N limit = 1000.
无论是 RT 还是 DRT-PP 都具有随机性, 此外, 在执行 DRT-PP 时, 测试剖面的演变过程还受初始测试剖面下纯随
机测试生成的测试用例 t 1 的影响, 因此, 对于每一个测试策略, 我们都重复执行 10 次, 并观测整体的测试效果. 总
的来说, 包括 RT、ART (包含 ART3、ART5) 和 DRT-PP (包含 DRT-05、DRT-10、DRT-15、DRT-20) 在内, 共有
7 种测试配置, 每个配置下, 我们进行 10 次测试流程, 每次测试流程生成 1 000 个测试用例, 并且每个测试用例要
被 RRT 算法执行 10 次, 因此, 路径规划算法总共被执行的次数为 700 000 次. 据统计, 每次 RRT 算法的执行时间
约为 2 s, 执行一个测试用例的时间 (即重复 10 次) 约为 20 s, 因此, 单线程运行实验的总时间约为 16.2 天 (实际我
们采用并行方式运行实验). 这里需指出, DRT-PP 方法在测试剖面更新时的计算时间通常小于 5 ms, 因此, DRT-PP
的计算时间远远小于测试用例的执行时间 (见第 2.4 节的讨论), 因此本节不对 DRT-PP 的效率做进一步讨论.

3.2.5 评价指标设置
本文通过计算失效度 S (t) 来评价测试用例质量, 即我们希望生成失效度较大的测试用例. 因此, 一个测试流程
完成时, 我们会得到 1 000 个测试用例的 S (t) 值, 而我们通过计算失效度 S (t) 的平均值来评价生成测试用例集的整
体质量. 假设某测试策略生成的测试用例集为 T = {t 1 ,t 2 ,...,t 1000 }, 则 S (t) 平均值可由公式 (23) 计算.

1000
∑
S (t i )
S avg = i=1 (23)
1000
此外, 对于每次测试, 我们同样考察 S (t) 的最大值, 因为失效度 S (t) 最大的测试用例最有可能暴露被测算法的
失效风险. 同样对于测试用例集 T, S (t) 的最大值可由公式 (24) 计算.